broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(*args):
    pis, gates, outs, period, setup = args
    arr = dict(pis)
    g = {name: (dl, fi) for name, dl, fi in gates}
    order = [name for name, _, _ in gates]
    for n in order:
        dl, fi = g[n]
        arr[n] = dl + max(arr[f] for f in fi)
    req = {}
    for n in reversed(order):
        fos = [m for m in order if n in g[m][1]]
        cands = [req[m] - g[n][0] for m in fos]
        if n in outs:
            cands.append(period - setup)
        req[n] = min(cands)
    slack = {n: req[n] - arr[n] for n in req}
    worst = min(slack.values())
    end = min(outs, key=lambda n: (slack[n], n))
    path = [end]
    while path[-1] in g:
        fi = g[path[-1]][1]
        path.append(max(sorted(fi), key=lambda f: arr[f]))
    return [worst, path[::-1], [[k, slack[k]] for k in sorted(slack)]]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('diamond with shared fanout', [{'a': 0, 'b': 1, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [4, ['b', 'g1', 'g4'], [['g1', 4], ['g2', 6], ['g3', 6], ['g4', 4]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 9, 2], [-1, ['a', 'g1', 'g4'], [['g1', -1], ['g2', 2], ['g3', 2], ['g4', -1]]]), ('long branch through internal output', [{'a': 0, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [1, ['a', 'u', 'w'], [['u', 1], ['v', 1], ['w', 1], ['x', 1], ['y', 1]]]), ('internal output with fanout', [{'a': 1, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 10, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 2], ['w', 1], ['x', 1], ['y', 2]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 12, 1], [1, ['c', 'p', 'r', 's'], [['p', 1], ['q', 7], ['r', 1], ['s', 1]]]), ('reconvergent with late input', [{'a': 3, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [0, ['a', 'p', 'r', 's'], [['p', 0], ['q', 6], ['r', 0], ['s', 0]]])], [('diamond with shared fanout', [{'a': 0, 'b': 2, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [3, ['b', 'g1', 'g4'], [['g1', 3], ['g2', 5], ['g3', 5], ['g4', 3]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 2}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 10, 2], [0, ['a', 'g1', 'g4'], [['g1', 0], ['g2', 2], ['g3', 2], ['g4', 0]]]), ('long branch through internal output', [{'a': 0, 'b': 2}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [0, ['b', 'v', 'y'], [['u', 1], ['v', 0], ['w', 1], ['x', 1], ['y', 0]]]), ('internal output with fanout', [{'a': 2, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 11, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 3], ['w', 1], ['x', 1], ['y', 3]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 13, 1], [2, ['c', 'p', 'r', 's'], [['p', 2], ['q', 8], ['r', 2], ['s', 2]]]), ('reconvergent with late input', [{'a': 3, 'c': 2}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [0, ['a', 'p', 'r', 's'], [['p', 0], ['q', 6], ['r', 0], ['s', 0]]])], [('diamond with shared fanout', [{'a': 0, 'b': 3, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [2, ['b', 'g1', 'g4'], [['g1', 2], ['g2', 4], ['g3', 4], ['g4', 2]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 3}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 11, 2], [1, ['a', 'g1', 'g4'], [['g1', 1], ['g2', 2], ['g3', 2], ['g4', 1]]]), ('long branch through internal output', [{'a': 0, 'b': 0}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [1, ['a', 'u', 'w'], [['u', 1], ['v', 2], ['w', 1], ['x', 1], ['y', 2]]]), ('internal output with fanout', [{'a': 3, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 12, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 4], ['w', 1], ['x', 1], ['y', 4]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 14, 1], [3, ['c', 'p', 'r', 's'], [['p', 3], ['q', 9], ['r', 3], ['s', 3]]]), ('reconvergent with late input', [{'a': 3, 'c': 3}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [0, ['a', 'p', 'r', 's'], [['p', 0], ['q', 6], ['r', 0], ['s', 0]]])], [('diamond with shared fanout', [{'a': 0, 'b': 4, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [1, ['b', 'g1', 'g4'], [['g1', 1], ['g2', 3], ['g3', 3], ['g4', 1]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 4}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 2], [2, ['c', 'g2', 'g3'], [['g1', 2], ['g2', 2], ['g3', 2], ['g4', 2]]]), ('long branch through internal output', [{'a': 0, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [1, ['a', 'u', 'w'], [['u', 1], ['v', 1], ['w', 1], ['x', 1], ['y', 1]]]), ('internal output with fanout', [{'a': 4, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 13, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 5], ['w', 1], ['x', 1], ['y', 5]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 15, 1], [4, ['c', 'p', 'r', 's'], [['p', 4], ['q', 10], ['r', 4], ['s', 4]]]), ('reconvergent with late input', [{'a': 3, 'c': 4}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [-1, ['c', 'p', 'r', 's'], [['p', -1], ['q', 5], ['r', -1], ['s', -1]]])], [('diamond with shared fanout', [{'a': 0, 'b': 5, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [0, ['b', 'g1', 'g4'], [['g1', 0], ['g2', 2], ['g3', 2], ['g4', 0]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 5}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 13, 2], [2, ['c', 'g2', 'g3'], [['g1', 3], ['g2', 2], ['g3', 2], ['g4', 3]]]), ('long branch through internal output', [{'a': 0, 'b': 2}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [0, ['b', 'v', 'y'], [['u', 1], ['v', 0], ['w', 1], ['x', 1], ['y', 0]]]), ('internal output with fanout', [{'a': 5, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 14, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 6], ['w', 1], ['x', 1], ['y', 6]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 16, 1], [5, ['c', 'p', 'r', 's'], [['p', 5], ['q', 11], ['r', 5], ['s', 5]]]), ('reconvergent with late input', [{'a': 3, 'c': 5}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [-2, ['c', 'p', 'r', 's'], [['p', -2], ['q', 4], ['r', -2], ['s', -2]]])]]
for label, args, expected in fixtures[N-1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(*args):
    pis, gates, outs, period, setup = args
    arr = dict(pis)
    g = {name: (dl, fi) for name, dl, fi in gates}
    order = [name for name, _, _ in gates]
    for n in order:
        dl, fi = g[n]
        arr[n] = dl + max(arr[f] for f in fi)
    req = {}
    for n in reversed(order):
        fos = [m for m in order if n in g[m][1]]
        cands = [req[m] for m in fos]
        if n in outs:
            cands.append(period - setup)
        req[n] = min(cands)
    slack = {n: req[n] - arr[n] for n in req}
    worst = min(slack.values())
    end = min(outs, key=lambda n: (slack[n], n))
    path = [end]
    while path[-1] in g:
        fi = g[path[-1]][1]
        path.append(max(sorted(fi), key=lambda f: arr[f]))
    return [worst, path[::-1], [[k, slack[k]] for k in sorted(slack)]]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('diamond with shared fanout', [{'a': 0, 'b': 1, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [4, ['b', 'g1', 'g4'], [['g1', 4], ['g2', 6], ['g3', 6], ['g4', 4]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 9, 2], [-1, ['a', 'g1', 'g4'], [['g1', -1], ['g2', 2], ['g3', 2], ['g4', -1]]]), ('long branch through internal output', [{'a': 0, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [1, ['a', 'u', 'w'], [['u', 1], ['v', 1], ['w', 1], ['x', 1], ['y', 1]]]), ('internal output with fanout', [{'a': 1, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 10, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 2], ['w', 1], ['x', 1], ['y', 2]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 12, 1], [1, ['c', 'p', 'r', 's'], [['p', 1], ['q', 7], ['r', 1], ['s', 1]]]), ('reconvergent with late input', [{'a': 3, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [0, ['a', 'p', 'r', 's'], [['p', 0], ['q', 6], ['r', 0], ['s', 0]]])], [('diamond with shared fanout', [{'a': 0, 'b': 2, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [3, ['b', 'g1', 'g4'], [['g1', 3], ['g2', 5], ['g3', 5], ['g4', 3]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 2}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 10, 2], [0, ['a', 'g1', 'g4'], [['g1', 0], ['g2', 2], ['g3', 2], ['g4', 0]]]), ('long branch through internal output', [{'a': 0, 'b': 2}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [0, ['b', 'v', 'y'], [['u', 1], ['v', 0], ['w', 1], ['x', 1], ['y', 0]]]), ('internal output with fanout', [{'a': 2, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 11, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 3], ['w', 1], ['x', 1], ['y', 3]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 13, 1], [2, ['c', 'p', 'r', 's'], [['p', 2], ['q', 8], ['r', 2], ['s', 2]]]), ('reconvergent with late input', [{'a': 3, 'c': 2}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [0, ['a', 'p', 'r', 's'], [['p', 0], ['q', 6], ['r', 0], ['s', 0]]])], [('diamond with shared fanout', [{'a': 0, 'b': 3, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [2, ['b', 'g1', 'g4'], [['g1', 2], ['g2', 4], ['g3', 4], ['g4', 2]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 3}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 11, 2], [1, ['a', 'g1', 'g4'], [['g1', 1], ['g2', 2], ['g3', 2], ['g4', 1]]]), ('long branch through internal output', [{'a': 0, 'b': 0}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [1, ['a', 'u', 'w'], [['u', 1], ['v', 2], ['w', 1], ['x', 1], ['y', 2]]]), ('internal output with fanout', [{'a': 3, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 12, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 4], ['w', 1], ['x', 1], ['y', 4]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 14, 1], [3, ['c', 'p', 'r', 's'], [['p', 3], ['q', 9], ['r', 3], ['s', 3]]]), ('reconvergent with late input', [{'a': 3, 'c': 3}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [0, ['a', 'p', 'r', 's'], [['p', 0], ['q', 6], ['r', 0], ['s', 0]]])], [('diamond with shared fanout', [{'a': 0, 'b': 4, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [1, ['b', 'g1', 'g4'], [['g1', 1], ['g2', 3], ['g3', 3], ['g4', 1]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 4}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 2], [2, ['c', 'g2', 'g3'], [['g1', 2], ['g2', 2], ['g3', 2], ['g4', 2]]]), ('long branch through internal output', [{'a': 0, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [1, ['a', 'u', 'w'], [['u', 1], ['v', 1], ['w', 1], ['x', 1], ['y', 1]]]), ('internal output with fanout', [{'a': 4, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 13, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 5], ['w', 1], ['x', 1], ['y', 5]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 15, 1], [4, ['c', 'p', 'r', 's'], [['p', 4], ['q', 10], ['r', 4], ['s', 4]]]), ('reconvergent with late input', [{'a': 3, 'c': 4}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [-1, ['c', 'p', 'r', 's'], [['p', -1], ['q', 5], ['r', -1], ['s', -1]]])], [('diamond with shared fanout', [{'a': 0, 'b': 5, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [0, ['b', 'g1', 'g4'], [['g1', 0], ['g2', 2], ['g3', 2], ['g4', 0]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 5}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 13, 2], [2, ['c', 'g2', 'g3'], [['g1', 3], ['g2', 2], ['g3', 2], ['g4', 3]]]), ('long branch through internal output', [{'a': 0, 'b': 2}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [0, ['b', 'v', 'y'], [['u', 1], ['v', 0], ['w', 1], ['x', 1], ['y', 0]]]), ('internal output with fanout', [{'a': 5, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 14, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 6], ['w', 1], ['x', 1], ['y', 6]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 16, 1], [5, ['c', 'p', 'r', 's'], [['p', 5], ['q', 11], ['r', 5], ['s', 5]]]), ('reconvergent with late input', [{'a': 3, 'c': 5}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [-2, ['c', 'p', 'r', 's'], [['p', -2], ['q', 4], ['r', -2], ['s', -2]]])]]
for label, args, expected in fixtures[N-1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
Slack of internal gates is wrong whenever a gate and its fanout have different delays.

Input [pis, gates, outs, period, setup]: pis maps input -> arrival time; gates are [name, delay, fanins] in topological order. arrival(g) = delay + max fanin arrival. required(g) = min over fanout gates m of (required(m) - delay(m)), plus period - setup if g is an output. Slack = required - arrival over gates. Return [worst slack, critical path, sorted [gate, slack]] where the path ends at the output with least slack (ties by name) and walks back through the fanin with the latest arrival (ties by smallest name) to a primary input.

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(*args):
    pis, gates, outs, period, setup = args
    arr = dict(pis)
    g = {name: (dl, fi) for name, dl, fi in gates}
    order = [name for name, _, _ in gates]
    for n in order:
        dl, fi = g[n]
        arr[n] = dl + max(arr[f] for f in fi)
    req = {}
    for n in reversed(order):
        fos = [m for m in order if n in g[m][1]]
        cands = [req[m] - g[m][0] for m in fos]
        if n in outs:
            cands.append(period - setup)
        req[n] = max(cands)
    slack = {n: req[n] - arr[n] for n in req}
    worst = min(slack.values())
    end = min(outs, key=lambda n: (slack[n], n))
    path = [end]
    while path[-1] in g:
        fi = g[path[-1]][1]
        path.append(max(sorted(fi), key=lambda f: arr[f]))
    return [worst, path[::-1], [[k, slack[k]] for k in sorted(slack)]]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('diamond with shared fanout', [{'a': 0, 'b': 1, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [4, ['b', 'g1', 'g4'], [['g1', 4], ['g2', 6], ['g3', 6], ['g4', 4]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 9, 2], [-1, ['a', 'g1', 'g4'], [['g1', -1], ['g2', 2], ['g3', 2], ['g4', -1]]]), ('long branch through internal output', [{'a': 0, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [1, ['a', 'u', 'w'], [['u', 1], ['v', 1], ['w', 1], ['x', 1], ['y', 1]]]), ('internal output with fanout', [{'a': 1, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 10, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 2], ['w', 1], ['x', 1], ['y', 2]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 12, 1], [1, ['c', 'p', 'r', 's'], [['p', 1], ['q', 7], ['r', 1], ['s', 1]]]), ('reconvergent with late input', [{'a': 3, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [0, ['a', 'p', 'r', 's'], [['p', 0], ['q', 6], ['r', 0], ['s', 0]]])], [('diamond with shared fanout', [{'a': 0, 'b': 2, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [3, ['b', 'g1', 'g4'], [['g1', 3], ['g2', 5], ['g3', 5], ['g4', 3]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 2}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 10, 2], [0, ['a', 'g1', 'g4'], [['g1', 0], ['g2', 2], ['g3', 2], ['g4', 0]]]), ('long branch through internal output', [{'a': 0, 'b': 2}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [0, ['b', 'v', 'y'], [['u', 1], ['v', 0], ['w', 1], ['x', 1], ['y', 0]]]), ('internal output with fanout', [{'a': 2, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 11, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 3], ['w', 1], ['x', 1], ['y', 3]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 13, 1], [2, ['c', 'p', 'r', 's'], [['p', 2], ['q', 8], ['r', 2], ['s', 2]]]), ('reconvergent with late input', [{'a': 3, 'c': 2}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [0, ['a', 'p', 'r', 's'], [['p', 0], ['q', 6], ['r', 0], ['s', 0]]])], [('diamond with shared fanout', [{'a': 0, 'b': 3, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [2, ['b', 'g1', 'g4'], [['g1', 2], ['g2', 4], ['g3', 4], ['g4', 2]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 3}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 11, 2], [1, ['a', 'g1', 'g4'], [['g1', 1], ['g2', 2], ['g3', 2], ['g4', 1]]]), ('long branch through internal output', [{'a': 0, 'b': 0}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [1, ['a', 'u', 'w'], [['u', 1], ['v', 2], ['w', 1], ['x', 1], ['y', 2]]]), ('internal output with fanout', [{'a': 3, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 12, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 4], ['w', 1], ['x', 1], ['y', 4]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 14, 1], [3, ['c', 'p', 'r', 's'], [['p', 3], ['q', 9], ['r', 3], ['s', 3]]]), ('reconvergent with late input', [{'a': 3, 'c': 3}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [0, ['a', 'p', 'r', 's'], [['p', 0], ['q', 6], ['r', 0], ['s', 0]]])], [('diamond with shared fanout', [{'a': 0, 'b': 4, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [1, ['b', 'g1', 'g4'], [['g1', 1], ['g2', 3], ['g3', 3], ['g4', 1]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 4}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 2], [2, ['c', 'g2', 'g3'], [['g1', 2], ['g2', 2], ['g3', 2], ['g4', 2]]]), ('long branch through internal output', [{'a': 0, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [1, ['a', 'u', 'w'], [['u', 1], ['v', 1], ['w', 1], ['x', 1], ['y', 1]]]), ('internal output with fanout', [{'a': 4, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 13, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 5], ['w', 1], ['x', 1], ['y', 5]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 15, 1], [4, ['c', 'p', 'r', 's'], [['p', 4], ['q', 10], ['r', 4], ['s', 4]]]), ('reconvergent with late input', [{'a': 3, 'c': 4}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [-1, ['c', 'p', 'r', 's'], [['p', -1], ['q', 5], ['r', -1], ['s', -1]]])], [('diamond with shared fanout', [{'a': 0, 'b': 5, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [0, ['b', 'g1', 'g4'], [['g1', 0], ['g2', 2], ['g3', 2], ['g4', 0]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 5}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 13, 2], [2, ['c', 'g2', 'g3'], [['g1', 3], ['g2', 2], ['g3', 2], ['g4', 3]]]), ('long branch through internal output', [{'a': 0, 'b': 2}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [0, ['b', 'v', 'y'], [['u', 1], ['v', 0], ['w', 1], ['x', 1], ['y', 0]]]), ('internal output with fanout', [{'a': 5, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 14, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 6], ['w', 1], ['x', 1], ['y', 6]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 16, 1], [5, ['c', 'p', 'r', 's'], [['p', 5], ['q', 11], ['r', 5], ['s', 5]]]), ('reconvergent with late input', [{'a': 3, 'c': 5}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [-2, ['c', 'p', 'r', 's'], [['p', -2], ['q', 4], ['r', -2], ['s', -2]]])]]
for label, args, expected in fixtures[N-1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

meaning: Fixture-count band, not measured model difficulty

deps: stdlib

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(*args):
    pis, gates, outs, period, setup = args
    arr = dict(pis)
    g = {name: (dl, fi) for name, dl, fi in gates}
    order = [name for name, _, _ in gates]
    for n in order:
        dl, fi = g[n]
        arr[n] = dl + max(arr[f] for f in fi)
    req = {}
    for n in reversed(order):
        fos = [m for m in order if n in g[m][1]]
        cands = [req[m] - g[m][0] for m in fos]
        if n in outs:
            cands.append(period - setup)
        req[n] = cands[0]
    slack = {n: req[n] - arr[n] for n in req}
    worst = min(slack.values())
    end = min(outs, key=lambda n: (slack[n], n))
    path = [end]
    while path[-1] in g:
        fi = g[path[-1]][1]
        path.append(max(sorted(fi), key=lambda f: arr[f]))
    return [worst, path[::-1], [[k, slack[k]] for k in sorted(slack)]]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('diamond with shared fanout', [{'a': 0, 'b': 1, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [4, ['b', 'g1', 'g4'], [['g1', 4], ['g2', 6], ['g3', 6], ['g4', 4]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 9, 2], [-1, ['a', 'g1', 'g4'], [['g1', -1], ['g2', 2], ['g3', 2], ['g4', -1]]]), ('long branch through internal output', [{'a': 0, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [1, ['a', 'u', 'w'], [['u', 1], ['v', 1], ['w', 1], ['x', 1], ['y', 1]]]), ('internal output with fanout', [{'a': 1, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 10, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 2], ['w', 1], ['x', 1], ['y', 2]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 12, 1], [1, ['c', 'p', 'r', 's'], [['p', 1], ['q', 7], ['r', 1], ['s', 1]]]), ('reconvergent with late input', [{'a': 3, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [0, ['a', 'p', 'r', 's'], [['p', 0], ['q', 6], ['r', 0], ['s', 0]]])], [('diamond with shared fanout', [{'a': 0, 'b': 2, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [3, ['b', 'g1', 'g4'], [['g1', 3], ['g2', 5], ['g3', 5], ['g4', 3]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 2}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 10, 2], [0, ['a', 'g1', 'g4'], [['g1', 0], ['g2', 2], ['g3', 2], ['g4', 0]]]), ('long branch through internal output', [{'a': 0, 'b': 2}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [0, ['b', 'v', 'y'], [['u', 1], ['v', 0], ['w', 1], ['x', 1], ['y', 0]]]), ('internal output with fanout', [{'a': 2, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 11, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 3], ['w', 1], ['x', 1], ['y', 3]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 13, 1], [2, ['c', 'p', 'r', 's'], [['p', 2], ['q', 8], ['r', 2], ['s', 2]]]), ('reconvergent with late input', [{'a': 3, 'c': 2}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [0, ['a', 'p', 'r', 's'], [['p', 0], ['q', 6], ['r', 0], ['s', 0]]])], [('diamond with shared fanout', [{'a': 0, 'b': 3, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [2, ['b', 'g1', 'g4'], [['g1', 2], ['g2', 4], ['g3', 4], ['g4', 2]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 3}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 11, 2], [1, ['a', 'g1', 'g4'], [['g1', 1], ['g2', 2], ['g3', 2], ['g4', 1]]]), ('long branch through internal output', [{'a': 0, 'b': 0}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [1, ['a', 'u', 'w'], [['u', 1], ['v', 2], ['w', 1], ['x', 1], ['y', 2]]]), ('internal output with fanout', [{'a': 3, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 12, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 4], ['w', 1], ['x', 1], ['y', 4]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 14, 1], [3, ['c', 'p', 'r', 's'], [['p', 3], ['q', 9], ['r', 3], ['s', 3]]]), ('reconvergent with late input', [{'a': 3, 'c': 3}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [0, ['a', 'p', 'r', 's'], [['p', 0], ['q', 6], ['r', 0], ['s', 0]]])], [('diamond with shared fanout', [{'a': 0, 'b': 4, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [1, ['b', 'g1', 'g4'], [['g1', 1], ['g2', 3], ['g3', 3], ['g4', 1]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 4}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 2], [2, ['c', 'g2', 'g3'], [['g1', 2], ['g2', 2], ['g3', 2], ['g4', 2]]]), ('long branch through internal output', [{'a': 0, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [1, ['a', 'u', 'w'], [['u', 1], ['v', 1], ['w', 1], ['x', 1], ['y', 1]]]), ('internal output with fanout', [{'a': 4, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 13, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 5], ['w', 1], ['x', 1], ['y', 5]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 15, 1], [4, ['c', 'p', 'r', 's'], [['p', 4], ['q', 10], ['r', 4], ['s', 4]]]), ('reconvergent with late input', [{'a': 3, 'c': 4}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [-1, ['c', 'p', 'r', 's'], [['p', -1], ['q', 5], ['r', -1], ['s', -1]]])], [('diamond with shared fanout', [{'a': 0, 'b': 5, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [0, ['b', 'g1', 'g4'], [['g1', 0], ['g2', 2], ['g3', 2], ['g4', 0]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 5}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 13, 2], [2, ['c', 'g2', 'g3'], [['g1', 3], ['g2', 2], ['g3', 2], ['g4', 3]]]), ('long branch through internal output', [{'a': 0, 'b': 2}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [0, ['b', 'v', 'y'], [['u', 1], ['v', 0], ['w', 1], ['x', 1], ['y', 0]]]), ('internal output with fanout', [{'a': 5, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 14, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 6], ['w', 1], ['x', 1], ['y', 6]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 16, 1], [5, ['c', 'p', 'r', 's'], [['p', 5], ['q', 11], ['r', 5], ['s', 5]]]), ('reconvergent with late input', [{'a': 3, 'c': 5}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [-2, ['c', 'p', 'r', 's'], [['p', -2], ['q', 4], ['r', -2], ['s', -2]]])]]
for label, args, expected in fixtures[N-1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
A gate driving a slow and a fast branch is reported with the slack of the fast branch.

Input [pis, gates, outs, period, setup]: pis maps input -> arrival time; gates are [name, delay, fanins] in topological order. arrival(g) = delay + max fanin arrival. required(g) = min over fanout gates m of (required(m) - delay(m)), plus period - setup if g is an output. Slack = required - arrival over gates. Return [worst slack, critical path, sorted [gate, slack]] where the path ends at the output with least slack (ties by name) and walks back through the fanin with the latest arrival (ties by smallest name) to a primary input.

split: open-access


source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(*args):
    pis, gates, outs, period, setup = args
    arr = dict(pis)
    g = {name: (dl, fi) for name, dl, fi in gates}
    order = [name for name, _, _ in gates]
    for n in order:
        dl, fi = g[n]
        arr[n] = dl + max(arr[f] for f in fi)
    req = {}
    for n in reversed(order):
        fos = [m for m in order if n in g[m][1]]
        cands = [req[m] - g[m][0] for m in fos]
        if n in outs:
            cands.append(period - setup)
        req[n] = min(cands)
    slack = {n: req[n] - arr[n] for n in req}
    worst = min(slack.values())
    end = min(outs, key=lambda n: (slack[n], n))
    path = [end]
    while path[-1] in g:
        fi = g[path[-1]][1]
        path.append(max(sorted(fi), key=lambda f: g[f][0] if f in g else 0))
    return [worst, path[::-1], [[k, slack[k]] for k in sorted(slack)]]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('diamond with shared fanout', [{'a': 0, 'b': 1, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [4, ['b', 'g1', 'g4'], [['g1', 4], ['g2', 6], ['g3', 6], ['g4', 4]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 9, 2], [-1, ['a', 'g1', 'g4'], [['g1', -1], ['g2', 2], ['g3', 2], ['g4', -1]]]), ('long branch through internal output', [{'a': 0, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [1, ['a', 'u', 'w'], [['u', 1], ['v', 1], ['w', 1], ['x', 1], ['y', 1]]]), ('internal output with fanout', [{'a': 1, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 10, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 2], ['w', 1], ['x', 1], ['y', 2]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 12, 1], [1, ['c', 'p', 'r', 's'], [['p', 1], ['q', 7], ['r', 1], ['s', 1]]]), ('reconvergent with late input', [{'a': 3, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [0, ['a', 'p', 'r', 's'], [['p', 0], ['q', 6], ['r', 0], ['s', 0]]])], [('diamond with shared fanout', [{'a': 0, 'b': 2, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [3, ['b', 'g1', 'g4'], [['g1', 3], ['g2', 5], ['g3', 5], ['g4', 3]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 2}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 10, 2], [0, ['a', 'g1', 'g4'], [['g1', 0], ['g2', 2], ['g3', 2], ['g4', 0]]]), ('long branch through internal output', [{'a': 0, 'b': 2}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [0, ['b', 'v', 'y'], [['u', 1], ['v', 0], ['w', 1], ['x', 1], ['y', 0]]]), ('internal output with fanout', [{'a': 2, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 11, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 3], ['w', 1], ['x', 1], ['y', 3]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 13, 1], [2, ['c', 'p', 'r', 's'], [['p', 2], ['q', 8], ['r', 2], ['s', 2]]]), ('reconvergent with late input', [{'a': 3, 'c': 2}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [0, ['a', 'p', 'r', 's'], [['p', 0], ['q', 6], ['r', 0], ['s', 0]]])], [('diamond with shared fanout', [{'a': 0, 'b': 3, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [2, ['b', 'g1', 'g4'], [['g1', 2], ['g2', 4], ['g3', 4], ['g4', 2]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 3}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 11, 2], [1, ['a', 'g1', 'g4'], [['g1', 1], ['g2', 2], ['g3', 2], ['g4', 1]]]), ('long branch through internal output', [{'a': 0, 'b': 0}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [1, ['a', 'u', 'w'], [['u', 1], ['v', 2], ['w', 1], ['x', 1], ['y', 2]]]), ('internal output with fanout', [{'a': 3, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 12, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 4], ['w', 1], ['x', 1], ['y', 4]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 14, 1], [3, ['c', 'p', 'r', 's'], [['p', 3], ['q', 9], ['r', 3], ['s', 3]]]), ('reconvergent with late input', [{'a': 3, 'c': 3}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [0, ['a', 'p', 'r', 's'], [['p', 0], ['q', 6], ['r', 0], ['s', 0]]])], [('diamond with shared fanout', [{'a': 0, 'b': 4, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [1, ['b', 'g1', 'g4'], [['g1', 1], ['g2', 3], ['g3', 3], ['g4', 1]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 4}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 2], [2, ['c', 'g2', 'g3'], [['g1', 2], ['g2', 2], ['g3', 2], ['g4', 2]]]), ('long branch through internal output', [{'a': 0, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [1, ['a', 'u', 'w'], [['u', 1], ['v', 1], ['w', 1], ['x', 1], ['y', 1]]]), ('internal output with fanout', [{'a': 4, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 13, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 5], ['w', 1], ['x', 1], ['y', 5]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 15, 1], [4, ['c', 'p', 'r', 's'], [['p', 4], ['q', 10], ['r', 4], ['s', 4]]]), ('reconvergent with late input', [{'a': 3, 'c': 4}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [-1, ['c', 'p', 'r', 's'], [['p', -1], ['q', 5], ['r', -1], ['s', -1]]])], [('diamond with shared fanout', [{'a': 0, 'b': 5, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [0, ['b', 'g1', 'g4'], [['g1', 0], ['g2', 2], ['g3', 2], ['g4', 0]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 5}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 13, 2], [2, ['c', 'g2', 'g3'], [['g1', 3], ['g2', 2], ['g3', 2], ['g4', 3]]]), ('long branch through internal output', [{'a': 0, 'b': 2}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [0, ['b', 'v', 'y'], [['u', 1], ['v', 0], ['w', 1], ['x', 1], ['y', 0]]]), ('internal output with fanout', [{'a': 5, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 14, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 6], ['w', 1], ['x', 1], ['y', 6]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 16, 1], [5, ['c', 'p', 'r', 's'], [['p', 5], ['q', 11], ['r', 5], ['s', 5]]]), ('reconvergent with late input', [{'a': 3, 'c': 5}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [-2, ['c', 'p', 'r', 's'], [['p', -2], ['q', 4], ['r', -2], ['s', -2]]])]]
for label, args, expected in fixtures[N-1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
The reported critical path passes through a fanin that does not determine the arrival time.

Input [pis, gates, outs, period, setup]: pis maps input -> arrival time; gates are [name, delay, fanins] in topological order. arrival(g) = delay + max fanin arrival. required(g) = min over fanout gates m of (required(m) - delay(m)), plus period - setup if g is an output. Slack = required - arrival over gates. Return [worst slack, critical path, sorted [gate, slack]] where the path ends at the output with least slack (ties by name) and walks back through the fanin with the latest arrival (ties by smallest name) to a primary input.

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(*args):
    pis, gates, pos, vectors, faults = args
    def ev(op, bits):
        if op == 'and': return int(all(bits))
        if op == 'or': return int(any(bits))
        if op == 'nand': return 1 - int(all(bits))
        if op == 'nor': return 1 - int(any(bits))
        return 1 - bits[0]
    def sim(vec, fault):
        net, pin, sv = fault if fault else (None, None, None)
        val = {}
        for p in pis:
            val[p] = vec[p]
        for out, op, ins in gates:
            bits = [sv if (i == net and pin == out) else val[i] for i in ins]
            v = ev(op, bits)
            val[out] = sv if (out == net and pin is None) else v
        return [val[o] for o in pos]
    res = []
    for f in faults:
        first = None
        for idx, vec in enumerate(vectors):
            if sim(vec, f) != sim(vec, None):
                first = idx
                break
        res.append([f[0], f[1], f[2], first])
    return res
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('primary input stuck-at-1', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}], [['a', None, 1]]], [['a', None, 1, 1]]), ('primary input stuck-at-0', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}], [['b', None, 0]]], [['b', None, 0, 1]]), ('fanout branch fault into n4', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}], [['n1', 'n4', 1]]], [['n1', 'n4', 1, 5]]), ('fanout branch fault into n2', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}], [['n1', 'n2', 0]]], [['n1', 'n2', 0, 1]]), ('fault visible only at the second output', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}], [['n4', None, 1]]], [['n4', None, 1, 0]]), ('fault visible only at the first output', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}], [['n2', None, 0]]], [['n2', None, 0, 0]]), ('stem fault on internal net', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 0, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}], [['n1', None, 0], ['n3', None, 0]]], [['n1', None, 0, 0], ['n3', None, 0, 2]]), ('branch fault masked on its reader', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}], [['n1', 'n4', 0]]], [['n1', 'n4', 0, None]]), ('input fault masked downstream', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}], [['c', 'n5', 1]]], [['c', 'n5', 1, 1]])], [('primary input stuck-at-1', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}], [['a', None, 1]]], [['a', None, 1, 0]]), ('primary input stuck-at-0', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}], [['b', None, 0]]], [['b', None, 0, 0]]), ('fanout branch fault into n4', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}], [['n1', 'n4', 1]]], [['n1', 'n4', 1, 4]]), ('fanout branch fault into n2', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}], [['n1', 'n2', 0]]], [['n1', 'n2', 0, 0]]), ('fault visible only at the second output', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}], [['n4', None, 1]]], [['n4', None, 1, 2]]), ('fault visible only at the first output', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}], [['n2', None, 0]]], [['n2', None, 0, 0]]), ('stem fault on internal net', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}], [['n1', None, 0], ['n3', None, 0]]], [['n1', None, 0, 1], ['n3', None, 0, 3]]), ('branch fault masked on its reader', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 1, 'c': 0}], [['n1', 'n4', 0]]], [['n1', 'n4', 0, None]]), ('input fault masked downstream', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}], [['c', 'n5', 1]]], [['c', 'n5', 1, 0]])], [('primary input stuck-at-1', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}], [['a', None, 1]]], [['a', None, 1, 0]]), ('primary input stuck-at-0', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}], [['b', None, 0]]], [['b', None, 0, 0]]), ('fanout branch fault into n4', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}], [['n1', 'n4', 1]]], [['n1', 'n4', 1, 3]]), ('fanout branch fault into n2', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}], [['n1', 'n2', 0]]], [['n1', 'n2', 0, 1]]), ('fault visible only at the second output', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}], [['n4', None, 1]]], [['n4', None, 1, 1]]), ('fault visible only at the first output', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}], [['n2', None, 0]]], [['n2', None, 0, 0]]), ('stem fault on internal net', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}], [['n1', None, 0], ['n3', None, 0]]], [['n1', None, 0, 0], ['n3', None, 0, 4]]), ('branch fault masked on its reader', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}], [['n1', 'n4', 0]]], [['n1', 'n4', 0, None]]), ('input fault masked downstream', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}], [['c', 'n5', 1]]], [['c', 'n5', 1, 1]])], [('primary input stuck-at-1', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}], [['a', None, 1]]], [['a', None, 1, 6]]), ('primary input stuck-at-0', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}], [['b', None, 0]]], [['b', None, 0, 2]]), ('fanout branch fault into n4', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}], [['n1', 'n4', 1]]], [['n1', 'n4', 1, 2]]), ('fanout branch fault into n2', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}], [['n1', 'n2', 0]]], [['n1', 'n2', 0, 0]]), ('fault visible only at the second output', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}], [['n4', None, 1]]], [['n4', None, 1, 0]]), ('fault visible only at the first output', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}], [['n2', None, 0]]], [['n2', None, 0, 0]]), ('stem fault on internal net', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 1, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}], [['n1', None, 0], ['n3', None, 0]]], [['n1', None, 0, 0], ['n3', None, 0, 5]]), ('branch fault masked on its reader', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 1, 'c': 0}], [['n1', 'n4', 0]]], [['n1', 'n4', 0, None]]), ('input fault masked downstream', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}], [['c', 'n5', 1]]], [['c', 'n5', 1, 0]])], [('primary input stuck-at-1', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}], [['a', None, 1]]], [['a', None, 1, 5]]), ('primary input stuck-at-0', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}], [['b', None, 0]]], [['b', None, 0, 1]]), ('fanout branch fault into n4', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}], [['n1', 'n4', 1]]], [['n1', 'n4', 1, 1]]), ('fanout branch fault into n2', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}], [['n1', 'n2', 0]]], [['n1', 'n2', 0, 3]]), ('fault visible only at the second output', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}], [['n4', None, 1]]], [['n4', None, 1, 0]]), ('fault visible only at the first output', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}], [['n2', None, 0]]], [['n2', None, 0, 0]]), ('stem fault on internal net', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 1, 'b': 0, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}], [['n1', None, 0], ['n3', None, 0]]], [['n1', None, 0, 0], ['n3', None, 0, 6]]), ('branch fault masked on its reader', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}], [['n1', 'n4', 0]]], [['n1', 'n4', 0, None]]), ('input fault masked downstream', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}], [['c', 'n5', 1]]], [['c', 'n5', 1, None]])]]
for label, args, expected in fixtures[N-1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(*args):
    pis, gates, pos, vectors, faults = args
    def ev(op, bits):
        if op == 'and': return int(all(bits))
        if op == 'or': return int(any(bits))
        if op == 'nand': return 1 - int(all(bits))
        if op == 'nor': return 1 - int(any(bits))
        return 1 - bits[0]
    def sim(vec, fault):
        net, pin, sv = fault if fault else (None, None, None)
        val = {}
        for p in pis:
            val[p] = sv if (p == net and pin is None and sv == 0) else vec[p]
        for out, op, ins in gates:
            bits = [sv if (i == net and pin == out) else val[i] for i in ins]
            v = ev(op, bits)
            val[out] = sv if (out == net and pin is None) else v
        return [val[o] for o in pos]
    res = []
    for f in faults:
        first = None
        for idx, vec in enumerate(vectors):
            if sim(vec, f) != sim(vec, None):
                first = idx
                break
        res.append([f[0], f[1], f[2], first])
    return res
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('primary input stuck-at-1', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}], [['a', None, 1]]], [['a', None, 1, 1]]), ('primary input stuck-at-0', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}], [['b', None, 0]]], [['b', None, 0, 1]]), ('fanout branch fault into n4', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}], [['n1', 'n4', 1]]], [['n1', 'n4', 1, 5]]), ('fanout branch fault into n2', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}], [['n1', 'n2', 0]]], [['n1', 'n2', 0, 1]]), ('fault visible only at the second output', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}], [['n4', None, 1]]], [['n4', None, 1, 0]]), ('fault visible only at the first output', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}], [['n2', None, 0]]], [['n2', None, 0, 0]]), ('stem fault on internal net', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 0, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}], [['n1', None, 0], ['n3', None, 0]]], [['n1', None, 0, 0], ['n3', None, 0, 2]]), ('branch fault masked on its reader', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}], [['n1', 'n4', 0]]], [['n1', 'n4', 0, None]]), ('input fault masked downstream', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}], [['c', 'n5', 1]]], [['c', 'n5', 1, 1]])], [('primary input stuck-at-1', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}], [['a', None, 1]]], [['a', None, 1, 0]]), ('primary input stuck-at-0', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}], [['b', None, 0]]], [['b', None, 0, 0]]), ('fanout branch fault into n4', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}], [['n1', 'n4', 1]]], [['n1', 'n4', 1, 4]]), ('fanout branch fault into n2', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}], [['n1', 'n2', 0]]], [['n1', 'n2', 0, 0]]), ('fault visible only at the second output', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}], [['n4', None, 1]]], [['n4', None, 1, 2]]), ('fault visible only at the first output', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}], [['n2', None, 0]]], [['n2', None, 0, 0]]), ('stem fault on internal net', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}], [['n1', None, 0], ['n3', None, 0]]], [['n1', None, 0, 1], ['n3', None, 0, 3]]), ('branch fault masked on its reader', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 1, 'c': 0}], [['n1', 'n4', 0]]], [['n1', 'n4', 0, None]]), ('input fault masked downstream', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}], [['c', 'n5', 1]]], [['c', 'n5', 1, 0]])], [('primary input stuck-at-1', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}], [['a', None, 1]]], [['a', None, 1, 0]]), ('primary input stuck-at-0', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}], [['b', None, 0]]], [['b', None, 0, 0]]), ('fanout branch fault into n4', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}], [['n1', 'n4', 1]]], [['n1', 'n4', 1, 3]]), ('fanout branch fault into n2', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}], [['n1', 'n2', 0]]], [['n1', 'n2', 0, 1]]), ('fault visible only at the second output', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}], [['n4', None, 1]]], [['n4', None, 1, 1]]), ('fault visible only at the first output', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}], [['n2', None, 0]]], [['n2', None, 0, 0]]), ('stem fault on internal net', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}], [['n1', None, 0], ['n3', None, 0]]], [['n1', None, 0, 0], ['n3', None, 0, 4]]), ('branch fault masked on its reader', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}], [['n1', 'n4', 0]]], [['n1', 'n4', 0, None]]), ('input fault masked downstream', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}], [['c', 'n5', 1]]], [['c', 'n5', 1, 1]])], [('primary input stuck-at-1', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}], [['a', None, 1]]], [['a', None, 1, 6]]), ('primary input stuck-at-0', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}], [['b', None, 0]]], [['b', None, 0, 2]]), ('fanout branch fault into n4', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}], [['n1', 'n4', 1]]], [['n1', 'n4', 1, 2]]), ('fanout branch fault into n2', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}], [['n1', 'n2', 0]]], [['n1', 'n2', 0, 0]]), ('fault visible only at the second output', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}], [['n4', None, 1]]], [['n4', None, 1, 0]]), ('fault visible only at the first output', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}], [['n2', None, 0]]], [['n2', None, 0, 0]]), ('stem fault on internal net', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 0, 'b': 1, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}], [['n1', None, 0], ['n3', None, 0]]], [['n1', None, 0, 0], ['n3', None, 0, 5]]), ('branch fault masked on its reader', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 1, 'c': 0}], [['n1', 'n4', 0]]], [['n1', 'n4', 0, None]]), ('input fault masked downstream', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}], [['c', 'n5', 1]]], [['c', 'n5', 1, 0]])], [('primary input stuck-at-1', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}], [['a', None, 1]]], [['a', None, 1, 5]]), ('primary input stuck-at-0', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}], [['b', None, 0]]], [['b', None, 0, 1]]), ('fanout branch fault into n4', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}], [['n1', 'n4', 1]]], [['n1', 'n4', 1, 1]]), ('fanout branch fault into n2', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}], [['n1', 'n2', 0]]], [['n1', 'n2', 0, 3]]), ('fault visible only at the second output', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}], [['n4', None, 1]]], [['n4', None, 1, 0]]), ('fault visible only at the first output', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 0, 'c': 0}], [['n2', None, 0]]], [['n2', None, 0, 0]]), ('stem fault on internal net', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 1, 'b': 0, 'c': 0}, {'a': 0, 'b': 1, 'c': 1}, {'a': 0, 'b': 1, 'c': 0}, {'a': 0, 'b': 0, 'c': 1}, {'a': 0, 'b': 0, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}, {'a': 1, 'b': 0, 'c': 1}], [['n1', None, 0], ['n3', None, 0]]], [['n1', None, 0, 0], ['n3', None, 0, 6]]), ('branch fault masked on its reader', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 1, 'b': 0, 'c': 0}, {'a': 1, 'b': 1, 'c': 1}], [['n1', 'n4', 0]]], [['n1', 'n4', 0, None]]), ('input fault masked downstream', [['a', 'b', 'c'], [['n1', 'nand', ['a', 'b']], ['n2', 'or', ['n1', 'c']], ['n3', 'not', ['n1']], ['n4', 'and', ['n1', 'b']], ['n5', 'nor', ['n3', 'c']]], ['n2', 'n4', 'n5'], [{'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 0}], [['c', 'n5', 1]]], [['c', 'n5', 1, None]])]]
for label, args, expected in fixtures[N-1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
Faults on primary inputs are reported as undetected by every vector.

Input [pis, gates, pos, vectors, faults]. Gates [out, op, ins] are topologically ordered (and/or/nand/nor/not). A fault [net, None, v] is a stem stuck-at on a primary input or gate output; [net, reader, v] is a branch fault that forces only the pin of gate 'reader' that reads 'net'. A fault is detected by a vector when any primary output differs from the fault-free circuit. Return [net, reader, v, first detecting vector index or None] per fault.

split: open-access