Problem:


Boolean Expression Compressor

You are asked to build a compressor for Boolean expressions
that transforms expressions to the shortest form keeping their meaning. 

The grammar of the Boolean expressions has terminals 
0 1 a b c d - ^ * ( ), start symbol <E> and the following production rule: 

<E>  ::=  0  |  1  |  a  |  b  |  c  |  d  |  -<E>  |  (<E>^<E>)  |  (<E>*<E>)

Letters a, b, c and d represent Boolean
variables that have values of either  0 or 1.
Operators are evaluated as shown in the Table below.
In other words, - means negation (NOT),
^ means exclusive disjunction (XOR), and 
* means logical conjunction (AND). 

Table: Evaluations of operators

Write a program that calculates the length of the shortest expression that
evaluates equal to the given expression with whatever values of the four variables.

For example, 0, that is the first expression in the sample input,
cannot be shortened further.
Therefore the shortest length for this expression is 1.

For another example, (a*(1*b)), the second in the sample input,
always evaluates equal to (a*b) and (b*a),
which are the shortest.   The output for this expression, thus, should be 5. 

Input

The input consists of multiple datasets.
A dataset consists of one line, containing an expression
conforming to the grammar described above.
The length of the expression is less than or equal to 16 characters.

The end of the input is indicated by a line containing one
. (period).
The number of datasets in the input is at most 200. 

Output

For each dataset, 
output a single line containing an integer which is the length of the
shortest expression that has the same value as the given expression for 
all combinations of values in the variables. 

Sample Input

0
(a*(1*b))
(1^a)
(-(-a*-b)*a)
(a^(b^(c^d)))
.

Output for the Sample Input

1
5
2
1
13



Sample input:
0
(a*(1*b))
(1^a)
(-(-a*-b)*a)
(a^(b^(c^d)))
.


Sample output:
1
5
2
1
13

Submission status: Accepted

Solution code:
def calc(s):
    def parse(a, b, c, d):
        nonlocal cur
        g = s[cur]; cur += 1
        if g == '-':
            return 1 ^ parse(a, b, c, d)
        if g == '(':
            p = parse(a, b, c, d)
            cmd = s[cur]; cur += 1
            q = parse(a, b, c, d)
            cur += 1 # ')'
            return p ^ q if cmd == '^' else p & q
        return eval(g)
    res = 0
    for b in range(16):
        cur = 0
        if parse(*map(int, format(b, '04b'))):
            res += 1 << b
    return res
base = "abcd10"
L = {}
for e in base:
    state = calc(e)
    L[state] = 1
ALL = 2**16-1
MAX = 10**18
for i in range(6):
    R = dict(L)
    for p in R:
        if R[p] < 16:
            L[p ^ ALL] = min(L.get(p ^ ALL, MAX), R[p] + 1)
        if R[p]+3 < 16:
            for q in R:
                if R[p] + R[q] + 3 <= 16:
                    L[p & q] = min(L.get(p & q, MAX), R[p] + R[q] + 3)
                    L[p ^ q] = min(L.get(p ^ q, MAX), R[p] + R[q] + 3)
while 1:
    s = input()
    if s == '.':
        break
    print(L[calc(s)])

Submission status: Accepted

Solution code:
def calc(s):
    s = s.replace("-", "-~-")
    res = 0
    for bit in range(16):
        a, b, c, d = map(int, format(bit, '04b'))
        if eval(s):
            res += 1 << bit
    return res
base = "abcd10"
L = {}
for e in base:
    state = calc(e)
    L[state] = 1
ALL = 2**16-1
MAX = 10**18
for i in range(6):
    R = dict(L)
    for p in R:
        if R[p] < 16:
            L[p ^ ALL] = min(L.get(p ^ ALL, MAX), R[p] + 1)
        if R[p]+3 < 16:
            for q in R:
                if R[p] + R[q] + 3 <= 16:
                    L[p & q] = min(L.get(p & q, MAX), R[p] + R[q] + 3)
                    L[p ^ q] = min(L.get(p ^ q, MAX), R[p] + R[q] + 3)
while 1:
    s = input()
    if s == '.':
        break
    print(L[calc(s)])

Submission status: Accepted

Solution code:
a=65280; b=61680; c=52428; d=43690; e=65535
def calc(s):
    res = eval(s.replace("-", "~").replace("*", "&").replace("1", "e"))
    return e ^ ~res if res < 0 else res
base = [a, b, c, d, e, 0]
L = {el: 1 for el in base}
for i in range(6):
    R = dict(L)
    for p in R:
        if R[p] < 16:
            L[p ^ e] = min(L.get(p ^ e, 16), R[p] + 1)
        if R[p]+3 < 16:
            for q in R:
                if R[p] + R[q] + 3 <= 16:
                    L[p & q] = min(L.get(p & q, 16), R[p] + R[q] + 3)
                    L[p ^ q] = min(L.get(p ^ q, 16), R[p] + R[q] + 3)
while 1:
    s = input()
    if s == '.':
        break
    print(L[calc(s)])

Submission status: Accepted

Solution code:
a=65280; b=61680; c=52428; d=43690; e=65535
base = [a, b, c, d, e, 0]
L = {el: 1 for el in base}
for i in range(6):
    R = dict(L)
    for p in R:
        if R[p] < 16:
            L[p ^ e] = min(L.get(p ^ e, 16), R[p] + 1)
        if R[p]+3 < 16:
            for q in R:
                if R[p] + R[q] + 3 <= 16:
                    L[p & q] = min(L.get(p & q, 16), R[p] + R[q] + 3)
                    L[p ^ q] = min(L.get(p ^ q, 16), R[p] + R[q] + 3)
while 1:
    s = input()
    if s == '.':
        break
    print(L[e & eval(s.replace("-", "~").replace("*", "&").replace("1", "e"))])

Submission status: Accepted

Solution code:
a=65280; b=61680; c=52428; d=43690; e=65535
base = [a, b, c, d, e, 0]
L = {el: 1 for el in base}
for i in range(6):
    R = dict(L)
    for p in R:
        if R[p] < 16:
            L[p ^ e] = min(L.get(p ^ e, 16), R[p] + 1)
        if R[p]+3 < 16:
            for q in R:
                if R[p] + R[q] + 3 <= 16:
                    L[p & q] = min(L.get(p & q, 16), R[p] + R[q] + 3)
                    L[p ^ q] = min(L.get(p ^ q, 16), R[p] + R[q] + 3)
print(*(L[e & eval(s)] for s in open(0).read().replace("-", "~").replace("*", "&").replace("1", "e").split()[:-1]),sep="\n")

Submission status: Accepted

Solution code:
a=65280; b=61680; c=52428; d=43690; e=65535
L = {el: 1 for el in [a, b, c, d, e, 0]}
for i in range(6):
    R = sorted(L.items(), key=lambda x: x[1])
    for p, l in R:
        if l < 16:
            L[p ^ e] = min(L.get(p ^ e, 16), l+1)
            if l+3 < 16:
                for q, r in R:
                    if l+r+3 <= 16:
                        L[p & q] = min(L.get(p & q, 16), l+r+3)
                        L[p ^ q] = min(L.get(p ^ q, 16), l+r+3)
                    else: break
        else: break
print(*(L[e & eval(s)] for s in open(0).read().replace(*"-~").replace(*"*&").replace(*"1e").split()[:-1]),sep='\n')

Submission status: Accepted

Solution code:
a=65280; b=61680; c=52428; d=43690; e=65535
from heapq import heappush, heappop
base = [a, b, c, d, e, 0]
Q = [(1, el) for el in base]
L = {el: 1 for el in base}
H = []
while Q:
    l, p = heappop(Q)
    if L[p] < l: continue
    if l+1 < L.get(p ^ e, 17):
        L[p^e] = l+1
        if l+1 < 16: heappush(Q, (l+1, p^e))
    if l+3 < 16:
        for q, r in H:
            if l+r+3 <= 16:
                if l+r+3 < L.get(p & q, 17):
                    L[p & q] = l+r+3
                    if l+r+3 < 16: heappush(Q, (l+r+3, p & q))
                if l+r+3 < L.get(p ^ q, 17):
                    L[p ^ q] = l+r+3
                    if l+r+3 < 16: heappush(Q, (l+r+3, p ^ q))
            else: break
    if l < 7: H.append((p, l))
print(*(L[e & eval(s)] for s in open(0).read().replace(*"-~").replace(*"*&").replace(*"1e").split()[:-1]),sep='\n')

Submission status: Accepted

Solution code:
a=65280; b=61680; c=52428; d=43690; e=65535
from heapq import heappush, heappop
base = [a, b, c, d, e, 0]
Q = [(1, el) for el in base]
L = {el: 1 for el in base}
H = []
while Q:
    l, p = heappop(Q)
    if L[p] < l: continue
    if l+1 < L.get(p ^ e, 17):
        L[p ^ e] = l+1
        if l+1 < 16: heappush(Q, (l+1, p ^ e))
    if l+3 < 16:
        for q, r in H:
            if l+r+3 <= 16:
                if l+r+3 < L.get(p & q, 17):
                    L[p & q] = l+r+3
                    if l+r+3 < 16: heappush(Q, (l+r+3, p & q))
                if l+r+3 < L.get(p ^ q, 17):
                    L[p ^ q] = l+r+3
                    if l+r+3 < 16: heappush(Q, (l+r+3, p ^ q))
            else: break
    if l < 7: H.append((p, l))
print(*map(L.__getitem__, eval("e&%s"%",e&".join(open(0).read().replace(*"-~").replace(*"*&").replace(*"1e").split()[:-1]))),sep='\n')

Submission status: Accepted

Solution code:
a=65280; b=61680; c=52428; d=43690; e=65535
from heapq import heappush, heappop
base = [a, b, c, d, e, 0]
Q = [(1, el) for el in base]
L = {el: 1 for el in base}
H = []
get = L.get
push = H.append
while Q:
    l, p = heappop(Q)
    if L[p] < l: continue
    if l+1 < get(p ^ e, 17):
        L[p ^ e] = l+1
        if l+1 < 16: heappush(Q, (l+1, p ^ e))
    if l+3 < 16:
        for q, r in H:
            if l+r+3 <= 16:
                if l+r+3 < get(p & q, 17):
                    L[p & q] = l+r+3
                    if l+r+3 < 16: heappush(Q, (l+r+3, p & q))
                if l+r+3 < get(p ^ q, 17):
                    L[p ^ q] = l+r+3
                    if l+r+3 < 16: heappush(Q, (l+r+3, p ^ q))
            else: break
    if l < 7: push((p, l))
print(*map(L.__getitem__, eval("e&%s"%",e&".join(open(0).read().replace(*"-~").replace(*"*&").replace(*"1e").split()[:-1]))),sep='\n')

Submission status: Accepted

Solution code:
a=65280; b=61680; c=52428; d=43690; e=65535
from heapq import heappush, heappop
Q = [(1, a), (1, b), (1, c), (1, d)]
L = {a: 1, b: 1, c: 1, d: 1, e: 1, e: 1, 0: 1}
H = []
get = L.get
push = H.append
while Q:
    l, p = heappop(Q)
    if L[p] < l: continue
    if l+1 < get(p ^ e, 17):
        L[p ^ e] = l+1
        l < 15 and heappush(Q, (l+1, p ^ e))
    if l < 13:
        li = 13-l; l3 = 3+l
        for q, r in H:
            if r <= li:
                k = p & q
                if r < get(k, 17)-l3:
                    L[k] = l3+r
                    r < li and heappush(Q, (l3+r, k))
                k = p ^ q
                if r < get(k, 17)-l3:
                    L[k] = l3+r
                    r < li and heappush(Q, (l3+r, k))
            else: break
    if l < 7: push((p, l))
print(*map(L.__getitem__, eval("e&"+",e&".join(open(0).read().replace(*"-~").replace(*"*&").replace(*"1e").split()[:-1]))),sep='\n')

Submission status: Accepted

Solution code:
a=65280; b=61680; c=52428; d=43690; e=65535
QS = [[] for i in range(17)]
QS[1] = [a, b, c, d]
L = {a: 1, b: 1, c: 1, d: 1, e: 1, e: 1, 0: 1}
H = []
get = L.get
push = H.append
for l in range(1, 16):
    Q = QS[l]
    QN = QS[l+1]
    while Q:
        p = Q.pop()
        if L[p] < l: continue
        if l+1 < get(p ^ e, 17):
            L[p ^ e] = l+1
            l < 15 and QN.append(p ^ e)
        if l < 13:
            li = 13-l; l3 = 3+l
            for q, r in H:
                if r < li:
                    k = p & q
                    if r < get(k, 17)-l3: L[k] = l3+r; QS[l3+r].append(k)
                    k = p ^ q
                    if r < get(k, 17)-l3: L[k] = l3+r; QS[l3+r].append(k)
                elif r == li:
                    if p & q not in L: L[p & q] = 16
                    if p ^ q not in L: L[p ^ q] = 16
                else: break
        if l < 7: push((p, l))
print(*map(L.__getitem__, eval("e&"+",e&".join(open(0).read().replace(*"-~").replace(*"*&").replace(*"1e").split()[:-1]))),sep='\n')

Submission status: Accepted

Solution code:
a=65280; b=61680; c=52428; d=43690; e=65535
QS = [[] for i in range(17)]
QS[1] = [a, b, c, d]
L = {a: 1, b: 1, c: 1, d: 1, e: 1, e: 1, 0: 1}
H = []
get = L.get
push = H.append
for l in range(1, 16):
    Q = QS[l]
    li = 13-l; l3 = l+3; l1 = l+1
    pop = Q.pop
    pushQN = QS[l1].append
    while Q:
        p = pop()
        if L[p] < l: continue
        if l1 < get(p ^ e, 17):
            L[p ^ e] = l1
            l < 12 and pushQN(p ^ e)
        if l < 13:
            for q, r in H:
                if r < li:
                    if l3+r < get(p & q, 17): L[p & q] = l3+r; QS[l3+r].append(p & q)
                    if l3+r < get(p ^ q, 17): L[p ^ q] = l3+r; QS[l3+r].append(p ^ q)
                elif r == li:
                    if p & q not in L: L[p & q] = 16
                    if p ^ q not in L: L[p ^ q] = 16
                else: break
            if l < 7: push((p, l))
print(*map(L.__getitem__, eval("e&"+",e&".join(open(0).read().replace(*"-~").replace(*"*&").replace(*"1e").split()[:-1]))),sep='\n')

Submission status: Accepted

Solution code:
a=65280; b=61680; c=52428; d=43690; e=65535
QS = [[] for i in range(17)]
QS[1] = [a, b, c, d]
L = {a: 1, b: 1, c: 1, d: 1, e: 1, e: 1, 0: 1}
H = []
get = L.get
push = H.append
for l in range(1, 16):
    Q = QS[l]
    li = 13-l; l3 = l+3; l1 = l+1
    pop = Q.pop
    pushQN = QS[l1].append
    while Q:
        p = pop()
        if L[p] < l: continue
        if l < 13:
            if l1 < get(p ^ e, 17):
                L[p ^ e] = l1
                pushQN(p ^ e)
            for q, r in H:
                if r < li:
                    if l3+r < get(p & q, 17): L[p & q] = l3+r; QS[l3+r].append(p & q)
                    if l3+r < get(p ^ q, 17): L[p ^ q] = l3+r; QS[l3+r].append(p ^ q)
                elif r == li:
                    if p & q not in L: L[p & q] = 16
                    if p ^ q not in L: L[p ^ q] = 16
                else: break
            l < 7 and push((p, l))
        elif l1 < get(p ^ e, 17): L[p ^ e] = l1
print(*map(L.__getitem__, eval("e&"+",e&".join(open(0).read().replace(*"-~").replace(*"*&").replace(*"1e").split()[:-1]))),sep='\n')

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
import itertools

def rdp_resolve(e: str) -> int:
    def evaluate() -> int:
        nonlocal p
        if e[p] in env:
            p += 1
            return env[e[p - 1]]
        if e[p] == '-':
            p += 1
            return 1 - evaluate()
        p += 1
        lval = evaluate()
        op = e[p]
        p += 1
        rval = evaluate()
        p += 1
        if op == '^':
            return lval ^ rval
        else:
            return lval & rval
    res = 0
    env = {"0": 0, "1": 1}
    for a, b, c, d in itertools.product(range(2), range(2), range(2), range(2)):
        env.update({"a": a, "b": b, "c": c, "d": d})
        p = 0
        res = (res << 1) | evaluate()
    return res

def rdp_init() -> None:
    global rdp_sessions
    rdp_sessions = dict()
    rookies = dict()
    for ch in "01abcd":
        rookies[rdp_resolve(ch)] = 1
    while rookies:
        rdp_sessions.update(rookies)
        entries = dict()
        for k, v in rookies.items():
            candidate = 0xFFFF - k
            weight = v + 1
            if weight <= 16 and weight <= rdp_sessions.get(candidate, 16) and weight <= entries.get(candidate, 16):
                entries[candidate] = weight
        for (k1, v1), (k2, v2) in itertools.product(rookies.items(), rdp_sessions.items()):
            candidate = k1 ^ k2
            weight = v1 + v2 + 3
            if weight <= 16 and weight <= rdp_sessions.get(candidate, 16) and weight <= entries.get(candidate, 16):
                entries[candidate] = weight
            candidate = k1 & k2
            weight = v1 + v2 + 3
            if weight <= 16 and weight <= rdp_sessions.get(candidate, 16) and weight <= entries.get(candidate, 16):
                entries[candidate] = weight
        rookies = entries

        
if __name__ == '__main__':
    rdp_init()
    while True:
        line = input()
        if line == '.':
            break
        print(rdp_sessions[rdp_resolve(line)])

Submission status: Accepted

Solution code:
import heapq
import itertools
def evaluate(siki):
    return lambda a,b,c,d:eval(siki.replace("-","-~"))%2
def changenum(siki):
    res=0
    for seq in itertools.product(range(2),repeat=4):
        a,b,c,d=seq
        if evaluate(siki)(a,b,c,d)==1:
            res+=2**(a+2*b+4*c+8*d)
    return res
D=dict()
def dget(m):
    if m in D:
        return D[m]
    else:
        return 17
q=[]
heapq.heappush(q,(1,changenum("a")))
heapq.heappush(q,(1,changenum("b")))
heapq.heappush(q,(1,changenum("c")))
heapq.heappush(q,(1,changenum("d")))
heapq.heappush(q,(1,changenum("0")))
heapq.heappush(q,(1,changenum("1")))
D[changenum("a")]=1
D[changenum("b")]=1
D[changenum("c")]=1
D[changenum("d")]=1
D[changenum("0")]=1
D[changenum("1")]=1
while(len(q)>0):
    le,n=heapq.heappop(q)
    #print(le,n,dget(240),dget(255))
    if D[n]<le:
        continue
    D[n]=min(D[n],le)
    cost=1
    if dget(65535^n)>D[n]+cost and D[n]+cost<=16:
        D[65535^n]=D[n]+cost
        heapq.heappush(q,(D[65535^n],65535^n))
    tmp=dict()
    for k in D:
        if dget(n^k)>D[n]+D[k]+3 and D[n]+D[k]+3<=16:
            tmp[n^k]=D[n]+D[k]+3
            heapq.heappush(q,(tmp[n^k],n^k))
        if dget(n&k)>D[n]+D[k]+3 and D[n]+D[k]+3<=16:
            tmp[n&k]=D[n]+D[k]+3
            heapq.heappush(q,(tmp[n&k],n&k))
    for k in tmp:
        D[k]=tmp[k]
while(True):
    S=input()
    if S==".":
        break
    print(D[changenum(S)])