Q-MC Algorithm

qmc.py

#!/usr/bin/env python

import sys
import math
import re

""" Find the index of the single difference between two strings """
def find_char_difference(str1, str2) :
    if len(str1) != len(str2) :
        return None;
    counter = 0
    for i in range(len(str1)) :
        if str1[i] != str2[i] :
            counter += 1
            index = i
    if counter != 1 :
        return None
    return index

""" Represent a minterm """
class Minterm :
    def __init__(self, terms, rep) :
        self.minterms = terms
        self.binary = rep
        self.done = False

""" Determine if a table is completely done """
def is_complete_table(table) :
    for m in table :
        if not m.done :
            return False
    return True

""" Combine two terms if possible """
def combine_terms(term1, term2) :
    if term1.done or term2.done :
        return None
    index = find_char_difference(term1.binary, term2.binary)
    if index == None :
        return None
    listterm = list(term1.binary)
    listterm[index] = '-'
    term = "".join(listterm)
    return Minterm(list(set(term1.minterms+term2.minterms)), term)

""" Imply a table and return the new reduced table """
def imply_table(table) :
    newTable = []
    for m in range(len(table)) :
        if table[m].done :
            newTable.append(table[m])
            continue
        wasCombined = False
        for n in range(m+1, len(table)) :
            if table[m].minterms == table[n].minterms :
                continue
            newTerm = combine_terms(table[m], table[n])
            if not newTerm :
                continue
            newTable.append(newTerm)
            wasCombined = True
        
        table[m].done = not wasCombined
        if table[m].done :
            newTable.append(table[m])
    # 'swallow' extraneous terms
    m = 0
    while m < len(newTable)-1 :
        n = m+1
        while n < len(newTable) :
            if set(newTable[n].minterms).issubset(newTable[m].minterms) :
                del newTable[n]
                n-= 1
            n+=1
        m+=1
    return newTable

""" Execute the script """
# read in and sanatize the data
data = sys.stdin.read()
data = re.sub(r'\s','',data)
N = math.log(len(data),2)
if N < 1 or N != int(N) :
    sys.exit(0)
N = int(N)
print "N = " + `N`
for c in data :
    if c != '0' and c != '1' :
        sys.exit(0)
# create a mintable with all of the terms
mintable = []
minlist = []
for i in range(len(data)) :
    if data[i] == '1' :
        mintable.append(Minterm([i], bin(i)[2:].zfill(N)))
        minlist.append(i)
# minimize prime table
while not is_complete_table(mintable) :
    mintable = imply_table(mintable)
# do the prime implication
# --- MISSING CODE ---
# print the result of the reduction
print "NOTE: NOT FULLY REDUCED (NEEDS PRIME IMPLICATION)"
string = "f(A"
for i in range(1,N) :
    string += "," + chr(65+i)
string += ") = "
for t in mintable :
    for i in range(N) :
        if t.binary[i] == '0' or t.binary[i] == '1' :
            string += chr(65+i)
            if t.binary[i] == '0' :
                string += "`"
    string += " + "
string = string[:-3]
print string