Render k-map & Quine-McClusky table from minterms, doesn't care lists

kmap.py

def int2elem(x):
    rep = []
    for i in range(n):
        rep.append(x&1)
        x >>= 1;
    return tuple(rep)

def elem2int(block):
    x = 0
    for i,b in enumerate(block):
        x |= b << i
    return x

def collect_PIs_kmap(ss):
    pis = set()
    for x in ss:
        el = int2elem(x)
        pis |= collect_PIs_from(ss, el)
    return pis


def collect_PIs_from(ss, block):
    ret = set()
    for i,b in enumerate(block):
        if b == '-': continue
        nblock = list(block)
        nblock[i] = '-'
        nblock = tuple(nblock)
        if not is_block_good(ss, nblock): continue

        pis = collect_PIs_from(ss, nblock)
        ret |= pis

    return ret if ret else set([block])


def is_block_good(ss, block):
    for el in block_elems(block):
        x = elem2int(el)
        if x not in ss: return False
    return True

def is_in_block(e, block):
    for el in block_elems(block):
        if e == el: return True
    return False

def block_elems(block):
    for i,b in enumerate(block):
        if b != '-': continue
        nblock = list(block)
        nblock[i] = 0
        for el in block_elems(tuple(nblock)): yield el
        nblock[i] = 1
        for el in block_elems(tuple(nblock)): yield el
        return
    yield block

import math

def kmap_table(greys, x, block):
    if not greys: return render_cell(ss, x, block)

    ret = []
    grey = greys[0]
    grest = greys[1:]
    width = int(round(math.log2(len(grey))))
    for g in grey:
        nx = (x << width) | g
        sub = kmap_table(grest, nx, block)
        ret.append(sub)
    return ret

def draw_kmap(tags, greys, block):
    table = kmap_table(greys, 0, block)
    draw_kmap_(tags, greys, table, [])

def draw_kmap_(tags, greys, table, acc):
    if len(tags) == 2:
        if acc: print(""); print(' '.join(f"{a}={b}" for a,b in acc))
        draw_kmap_table(tags[0], tags[1], greys[0], greys[1], table)
        return

    grey = greys[0]
    grest = greys[1:]
    tag = tags[0]
    trest = tags[1:]
    width = int(round(math.log2(len(grey))))
    for i,g in enumerate(grey):
        acc.append((tag, f"{g:b}".rjust(width,'0')))
        draw_kmap_(trest, grest, table[i], acc)
        acc.pop()

def draw_kmap_table(tag1, tag2, grey1, grey2, table):
    tagwidth = int(round(math.log2(len(grey1))))
    colwidth = int(round(math.log2(len(grey2))))

    print(f"{tag1} \ {tag2}")
    print(' ' * tagwidth + '|' + ' '.join(f"{g:b}".rjust(colwidth,'0') for g in grey2))
    for i,row in enumerate(table):
        print(f"{grey1[i]:b}".rjust(tagwidth,'0')+ '|' + (' '*colwidth).join(e for e in row))

def render_cell(ss, x, block):
    val = '\x1b[38;5;250mx' if x in dd else ('1' if x in ss else ' ')

    e = int2elem(x)
    if is_in_block(e, block):
        val = '\x1b[1;30;43m' + val

    return val + '\x1b[0m'

def showblock(block):
    return ''.join(str(b) for b in reversed(block))

def block2mint(tags, block):
    ret = []
    for i,b in enumerate(reversed(block)):
        if b == '-': continue;
        ret.append(tags[i])
        if b == 0: ret.append("'")
    return ''.join(ret)

#n = 4
#ss = set((4,8,10,11,12,15))
#dd = set((9,14))
#
#assert(int2elem( 3) == (1,1,0,0))
#assert(int2elem( 5) == (1,0,1,0))
#assert(int2elem(14) == (0,1,1,1))
#assert(int2elem(10) == (0,1,0,1))
#
#assert(elem2int(int2elem( 3)) ==  3)
#assert(elem2int(int2elem( 5)) ==  5)
#assert(elem2int(int2elem(14)) == 14)
#assert(elem2int(int2elem(10)) == 10)
#
#print(elem2int([0,0,'-',1,1]))
#for el in block_elems(['-',0,'-',1,0]): print(el) #print(elem2int(el))

#table = kmap_table([[0,1,3,2],[0,1,3,2]], ss, [], 0)
#for l in table: print(l)

#table = kmap_table([[0,1,3,2],[0,1,3,2]], 0)
#draw_kmap_table("AB","CD", [0,1,3,2],[0,1,3,2], table)
#draw_kmap(["Z", "AB","CD"], [[0,1], [0,1,3,2],[0,1,3,2]])

#block = int2elem(15)
#print("from", showblock(block))
#pis = collect_PIs_from(ss|dd, block)
#for pi in pis:
#    print(showblock(pi))
#    draw_kmap(["AB","CD"], [[0,1,3,2],[0,1,3,2]], pi)
#    print('')

#pis = collect_PIs_kmap(ss|dd)
#for pi in pis:
#    print("\x1b[7m", showblock(pi), "\x1b[0m")
#    draw_kmap(["AB","CD"], [[0,1,3,2],[0,1,3,2]], pi)
#    print('')

def cover_order(block):
    return sum(b == '-' for b in block)

# is b1 < b2?
def compare_block(b1, b2):
    # cover size comp
    o1 = cover_order(b1)
    o2 = cover_order(b2)
    if o1 != o2: return o1 - o2

    # lexicographic order
    m1 = tuple(reversed(sorted(elem2int(e) for e in block_elems(b1))))
    m2 = tuple(reversed(sorted(elem2int(e) for e in block_elems(b2))))
    for t1, t2 in zip(m1, m2):
        if t1 == t2: continue
        return t1 - t2

def compare_bss(bss1, bss2):
    # cover size comp
    o1 = len(bss1)
    o2 = len(bss2)
    if o1 != o2: return o1 - o2

    # lexicographic order
    m1 = tuple(sorted(bss1))
    m2 = tuple(sorted(bss2))
    for t1, t2 in zip(m1, m2):
        if t1 == t2: continue
        return t1 - t2

def draw_cover(ss, tags, pis, select):
    ret = {s:[] for s in ss}
    mints = []
    for pi in pis:
        mint = block2mint(tags, pi)
        mints.append(mint)
        for el in block_elems(pi):
            x = elem2int(el)
            if x in ret:
                ret[x].append(mint)
            # discard x only in dd

    sol_s = []
    epis = set()
    for s,cover in ret.items():
        if len(cover) == 1:
            sol_s.append(s)
            epis.add(cover[0])

    for v in select: epis.add(block2mint(tags, v))
    print(epis)

    # covered by EPIs
    cov_s = { s for s,cover in ret.items() if any(pi in epis for pi in cover) }

    tagwidth = int(round(math.log10(n))) + 1
    colwidth = max(len(mint) for mint in mints)

    def show_mint(mint):
        val = mint.center(colwidth)
        if mint in epis:
            return "\x1b[30;46m" + val + "\x1b[0m"
        else: return val

    def show_s(s):
        #val = f"{s:b}".rjust(tagwidth,'0')
        val = str(s).rjust(tagwidth)
        if s in sol_s:
            return "\x1b[30;46m" + val + "\x1b[0m"
        elif s in cov_s:
            return "\x1b[36m" + val + "\x1b[0m"
        else: return val

    def show_ent(s,mint):
        val = ("o" if mint in ret[s] else ' ').center(colwidth)
        if s in sol_s or mint in epis:
            return "\x1b[30;46m" + val + "\x1b[0m"
        elif s in cov_s:
            return "\x1b[36m" + val + "\x1b[0m"
        else: return val


    print(' ' * tagwidth + '|' + ' '.join(showblock(pi).center(colwidth) for pi in pis))
    print(' ' * tagwidth + '|' + ' '.join(show_mint(mint) for mint in mints))

    for s in sorted(ss):
        print(show_s(s) + '|' + ' '.join(show_ent(s,mint) for mint in mints))


def collect_PIs_qm(ss):
  table = gen_qm_table(ss|dd)
  pis = draw_calc_table(table)
  print("")
  return pis

def count_1s(block):
    return sum(b == 1 for b in block)


def gen_I1(ss):
    ret = [[] for _ in range(n+1)]
    for s in ss:
        el = int2elem(s)
        i = count_1s(el)
        ret[i].append((el,(s,)))
    return ret


def gen_In(i1):
    ret = [set() for _ in range(n+1)]
    covered = set()
    for i, (bls1, bls2) in enumerate(zip(i1[0:], i1[1:])):
        for block1,ss1 in bls1:
            for block2,ss2 in bls2:
                nblock = merge_blocks(block1, block2)
                if nblock is None: continue
                nss = tuple(sorted(set(ss1 + ss2)))
                ret[i].add((nblock, nss))
                covered.add(block1)
                covered.add(block2)
    return ret, covered


def merge_blocks(block1, block2):
    ret = []
    has_been_diff = False
    for b1, b2 in zip(block1, block2):
        if b1 == b2:
            ret.append(b1)
            continue
        if has_been_diff: return None
        has_been_diff = True
        ret.append('-')
    return tuple(ret)

def gen_qm_table(ss):
    mints = gen_I1(ss)
    cov = set()

    ret = []
    while(sum(map(len,mints)) > 0):
        new_mints, new_cov = gen_In(mints)
        ret.append((mints,new_cov))
        mints = new_mints
    ret.append((mints,set()))
    return ret

from functools import cmp_to_key

def draw_calc_table(_tbl):

    def show_cell(block, bss):
        return f"{showblock(block)} {','.join(str(s) for s in bss)}"

    # transpose

    tbl = [
        [[] for _ in _tbl]
        for _ in range(n+1)
    ]

    colwidth = [0 for _ in _tbl]
    pis = []

    for order,(Is,cover) in enumerate(_tbl):
        for grp,rows in enumerate(Is):
            #tbl[i][lvl] = rows
            string_rows = []
            for block,bss in rows:
                string = show_cell(block,bss)
                covered = block in cover
                if not covered: pis.append(block)
                string_rows.append((string,covered,bss))
                colwidth[order] = max(colwidth[order], len(string))
            string_rows.sort(key=lambda t: cmp_to_key(compare_bss)(t[2]))
            tbl[grp][order] = [t[:2] for t in string_rows]

    print(f" N | " + ''.join(f"I{order}".rjust(colw)+' | ' for order,colw in enumerate(colwidth)))
    for grp,ord_rows in enumerate(tbl): # 0 <= grp <= n
        print('-'*(sum(colwidth) + 3*len(colwidth) + 4))
        nrows = max(len(rows) for rows in ord_rows)
        for i in range(nrows):
            if i == 0: print(f"{grp:2d} | ", end='')
            else: print(f"   | ", end='')
            for order,rows in enumerate(ord_rows):
                cell,covered = rows[i] if i < len(rows) else ('',True)
                colw = colwidth[order]
                val = cell.ljust(colw)
                if not covered: val = "\x1b[30;42m" + val + "\x1b[0m"
                print(val+' | ', end='')
            print("")

    return pis



# 5
#n = 5
#ss = set([0,2,3,4,9,11,18])
#dd = set([8,10,14,22,23,24,25,26,27,28,29,30,31])
#tags = "ABCDE"

# 6
#n = 5
#ss = set([5,7,10,13,14,15,21,23,29,31])
#dd = set([24,30])
#tags = "ABCDE"

#n = 4
#ss = set([0,1,2,4,5,6,8,9,10,11,12,13,15])
#dd = set()
#tags = "wxyz"

#n = 5
#ss = set([3,8,9,11,12,13,14,15,22,31])
#dd = set([0,2,7,17,20,21,23,30])
#tags = "ABCDE"

n = 4
ss = set([6,7,9,11,13])
dd = set([1,10,15])
tags = "ABCD"

pis_km = collect_PIs_kmap(ss|dd)
for pi in pis_km:
    print("\x1b[7m", showblock(pi), "\x1b[0m", "----------------------------")
    draw_kmap(["AB","CD"], [[0,1,3,2],[0,1,3,2]], pi)
    print('')

pis_qm = collect_PIs_qm(ss|dd)
draw_cover(ss, tags, pis_km, [])
#assert(list(sorted(pis_km)) == list(sorted(pis_qm)))
#select = []
#while True:
#  try:
#    a = tuple(int(x) if x != '-' else x for x in input().strip())
#    select.append(a)
#    print(select)
#    draw_cover(ss, tags, pis_km, select)
#  except Exception as e:
#    print(e)