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

N = 1
observations = []
def solve(*args):
    pis, gates = args
    seen = set(pis)
    for out, op, ins in gates:
        if out in seen:
            return 'multiply driven ' + out
        seen.add(out)
    for out, op, ins in gates:
        for i in ins[:0]:
            if i not in seen:
                return 'undriven ' + i
    level = {p: 0 for p in pis}
    val = dict(pis)
    pending = list(gates)
    while pending:
        ready = [g for g in pending if all(i in level for i in g[2])]
        if not ready:
            return 'loop'
        for out, op, ins in ready:
            level[out] = 1 + max([level[i] for i in ins], default=-1)
            bits = [val[i] for i in ins]
            if op == 'and': v = int(all(bits))
            elif op == 'or': v = int(any(bits))
            elif op == 'xor': v = sum(bits) % 2
            elif op == 'nand': v = 1 - int(all(bits))
            elif op in ('tie0', 'tie1'): v = int(op == 'tie1')
            else: v = 1 - bits[0]
            val[out] = v
        pending = [g for g in pending if g not in ready]
    return {'depth': max(level.values()), 'values': [[k, val[k]] for k in sorted(val)]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('reconvergent netlist listed out of order', [{'a': 1, 'b': 1, 'c': 0}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 1], ['b', 1], ['c', 0], ['g1', 1], ['g2', 0], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 1, 'b': 1, 'c': 0}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 1], ['b', 1], ['c', 0], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 1, 'b': 1, 'c': 0}, [['g1', 'and', ['a', 'nosuch1']]]], 'undriven nosuch1'), ('real combinational loop', [{'a': 1, 'b': 1, 'c': 0}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 1, 'b': 1, 'c': 0}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 1, 'b': 1, 'c': 0}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 1}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 1], ['y', 1]]}), ('unbalanced depth', [{'a': 1, 'b': 1, 'c': 0}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'd3']]]], {'depth': 4, 'values': [['a', 1], ['b', 1], ['c', 0], ['d1', 0], ['d2', 1], ['d3', 1], ['d4', 1]]})], [('reconvergent netlist listed out of order', [{'a': 0, 'b': 1, 'c': 1}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 0], ['b', 1], ['c', 1], ['g1', 1], ['g2', 1], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 0, 'b': 1, 'c': 1}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 0], ['b', 1], ['c', 1], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 0, 'b': 1, 'c': 1}, [['g1', 'and', ['a', 'nosuch2']]]], 'undriven nosuch2'), ('real combinational loop', [{'a': 0, 'b': 1, 'c': 1}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 0, 'b': 1, 'c': 1}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 0, 'b': 1, 'c': 1}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 0}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 0], ['y', 1]]}), ('unbalanced depth', [{'a': 0, 'b': 1, 'c': 1}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'c', 'd3']]]], {'depth': 4, 'values': [['a', 0], ['b', 1], ['c', 1], ['d1', 1], ['d2', 0], ['d3', 0], ['d4', 1]]})], [('reconvergent netlist listed out of order', [{'a': 1, 'b': 1, 'c': 1}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 1], ['b', 1], ['c', 1], ['g1', 0], ['g2', 0], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 1, 'b': 1, 'c': 1}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 1], ['b', 1], ['c', 1], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 1, 'b': 1, 'c': 1}, [['g1', 'and', ['a', 'nosuch3']]]], 'undriven nosuch3'), ('real combinational loop', [{'a': 1, 'b': 1, 'c': 1}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 1, 'b': 1, 'c': 1}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 1, 'b': 1, 'c': 1}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 1}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 1], ['y', 1]]}), ('unbalanced depth', [{'a': 1, 'b': 1, 'c': 1}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'c', 'c', 'd3']]]], {'depth': 4, 'values': [['a', 1], ['b', 1], ['c', 1], ['d1', 0], ['d2', 1], ['d3', 1], ['d4', 1]]})], [('reconvergent netlist listed out of order', [{'a': 0, 'b': 1, 'c': 0}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 0], ['b', 1], ['c', 0], ['g1', 1], ['g2', 1], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 0, 'b': 1, 'c': 0}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 0], ['b', 1], ['c', 0], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 0, 'b': 1, 'c': 0}, [['g1', 'and', ['a', 'nosuch4']]]], 'undriven nosuch4'), ('real combinational loop', [{'a': 0, 'b': 1, 'c': 0}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 0, 'b': 1, 'c': 0}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 0, 'b': 1, 'c': 0}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 0}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 0], ['y', 1]]}), ('unbalanced depth', [{'a': 0, 'b': 1, 'c': 0}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'c', 'c', 'c', 'd3']]]], {'depth': 4, 'values': [['a', 0], ['b', 1], ['c', 0], ['d1', 1], ['d2', 0], ['d3', 0], ['d4', 0]]})], [('reconvergent netlist listed out of order', [{'a': 1, 'b': 1, 'c': 0}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 1], ['b', 1], ['c', 0], ['g1', 1], ['g2', 0], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 1, 'b': 1, 'c': 0}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 1], ['b', 1], ['c', 0], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 1, 'b': 1, 'c': 0}, [['g1', 'and', ['a', 'nosuch5']]]], 'undriven nosuch5'), ('real combinational loop', [{'a': 1, 'b': 1, 'c': 0}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 1, 'b': 1, 'c': 0}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 1, 'b': 1, 'c': 0}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 1}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 1], ['y', 1]]}), ('unbalanced depth', [{'a': 1, 'b': 1, 'c': 0}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'c', 'c', 'c', 'c', 'd3']]]], {'depth': 4, 'values': [['a', 1], ['b', 1], ['c', 0], ['d1', 0], ['d2', 1], ['d3', 1], ['d4', 1]]})]]
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 = args
    seen = set(pis)
    for out, op, ins in gates:
        if out in seen:
            return 'multiply driven ' + out
        seen.add(out)
    for out, op, ins in gates:
        for i in ins[:1]:
            if i not in seen:
                return 'undriven ' + i
    level = {p: 0 for p in pis}
    val = dict(pis)
    pending = list(gates)
    while pending:
        ready = [g for g in pending if all(i in level for i in g[2])]
        if not ready:
            return 'loop'
        for out, op, ins in ready:
            level[out] = 1 + max([level[i] for i in ins], default=-1)
            bits = [val[i] for i in ins]
            if op == 'and': v = int(all(bits))
            elif op == 'or': v = int(any(bits))
            elif op == 'xor': v = sum(bits) % 2
            elif op == 'nand': v = 1 - int(all(bits))
            elif op in ('tie0', 'tie1'): v = int(op == 'tie1')
            else: v = 1 - bits[0]
            val[out] = v
        pending = [g for g in pending if g not in ready]
    return {'depth': max(level.values()), 'values': [[k, val[k]] for k in sorted(val)]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('reconvergent netlist listed out of order', [{'a': 1, 'b': 1, 'c': 0}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 1], ['b', 1], ['c', 0], ['g1', 1], ['g2', 0], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 1, 'b': 1, 'c': 0}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 1], ['b', 1], ['c', 0], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 1, 'b': 1, 'c': 0}, [['g1', 'and', ['a', 'nosuch1']]]], 'undriven nosuch1'), ('real combinational loop', [{'a': 1, 'b': 1, 'c': 0}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 1, 'b': 1, 'c': 0}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 1, 'b': 1, 'c': 0}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 1}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 1], ['y', 1]]}), ('unbalanced depth', [{'a': 1, 'b': 1, 'c': 0}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'd3']]]], {'depth': 4, 'values': [['a', 1], ['b', 1], ['c', 0], ['d1', 0], ['d2', 1], ['d3', 1], ['d4', 1]]})], [('reconvergent netlist listed out of order', [{'a': 0, 'b': 1, 'c': 1}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 0], ['b', 1], ['c', 1], ['g1', 1], ['g2', 1], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 0, 'b': 1, 'c': 1}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 0], ['b', 1], ['c', 1], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 0, 'b': 1, 'c': 1}, [['g1', 'and', ['a', 'nosuch2']]]], 'undriven nosuch2'), ('real combinational loop', [{'a': 0, 'b': 1, 'c': 1}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 0, 'b': 1, 'c': 1}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 0, 'b': 1, 'c': 1}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 0}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 0], ['y', 1]]}), ('unbalanced depth', [{'a': 0, 'b': 1, 'c': 1}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'c', 'd3']]]], {'depth': 4, 'values': [['a', 0], ['b', 1], ['c', 1], ['d1', 1], ['d2', 0], ['d3', 0], ['d4', 1]]})], [('reconvergent netlist listed out of order', [{'a': 1, 'b': 1, 'c': 1}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 1], ['b', 1], ['c', 1], ['g1', 0], ['g2', 0], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 1, 'b': 1, 'c': 1}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 1], ['b', 1], ['c', 1], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 1, 'b': 1, 'c': 1}, [['g1', 'and', ['a', 'nosuch3']]]], 'undriven nosuch3'), ('real combinational loop', [{'a': 1, 'b': 1, 'c': 1}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 1, 'b': 1, 'c': 1}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 1, 'b': 1, 'c': 1}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 1}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 1], ['y', 1]]}), ('unbalanced depth', [{'a': 1, 'b': 1, 'c': 1}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'c', 'c', 'd3']]]], {'depth': 4, 'values': [['a', 1], ['b', 1], ['c', 1], ['d1', 0], ['d2', 1], ['d3', 1], ['d4', 1]]})], [('reconvergent netlist listed out of order', [{'a': 0, 'b': 1, 'c': 0}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 0], ['b', 1], ['c', 0], ['g1', 1], ['g2', 1], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 0, 'b': 1, 'c': 0}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 0], ['b', 1], ['c', 0], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 0, 'b': 1, 'c': 0}, [['g1', 'and', ['a', 'nosuch4']]]], 'undriven nosuch4'), ('real combinational loop', [{'a': 0, 'b': 1, 'c': 0}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 0, 'b': 1, 'c': 0}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 0, 'b': 1, 'c': 0}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 0}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 0], ['y', 1]]}), ('unbalanced depth', [{'a': 0, 'b': 1, 'c': 0}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'c', 'c', 'c', 'd3']]]], {'depth': 4, 'values': [['a', 0], ['b', 1], ['c', 0], ['d1', 1], ['d2', 0], ['d3', 0], ['d4', 0]]})], [('reconvergent netlist listed out of order', [{'a': 1, 'b': 1, 'c': 0}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 1], ['b', 1], ['c', 0], ['g1', 1], ['g2', 0], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 1, 'b': 1, 'c': 0}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 1], ['b', 1], ['c', 0], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 1, 'b': 1, 'c': 0}, [['g1', 'and', ['a', 'nosuch5']]]], 'undriven nosuch5'), ('real combinational loop', [{'a': 1, 'b': 1, 'c': 0}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 1, 'b': 1, 'c': 0}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 1, 'b': 1, 'c': 0}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 1}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 1], ['y', 1]]}), ('unbalanced depth', [{'a': 1, 'b': 1, 'c': 0}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'c', 'c', 'c', 'c', 'd3']]]], {'depth': 4, 'values': [['a', 1], ['b', 1], ['c', 0], ['d1', 0], ['d2', 1], ['d3', 1], ['d4', 1]]})]]
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 reading a net that nobody drives is reported as 'loop' because the gate never becomes ready.

Input [pis, gates]: pis maps primary input net -> 0/1; gates are [out, op, ins] in any order with ops and/or/xor/nand/not/tie0/tie1. Reject with 'undriven <net>' (first gate in list order, first pin) if a gate reads a net driven by nobody, or 'multiply driven <net>' if a net has two drivers (a gate driving a primary input counts). Otherwise evaluate in dependency waves; return 'loop' if no gate becomes ready. Level: primary inputs 0, gate = 1 + max input level, tie cells 0. Return {'depth': max level, 'values': sorted [net, value]}.

split: open-access


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

N = 1
observations = []
def solve(*args):
    pis, gates = args
    seen = set(pis)
    for out, op, ins in gates:
        if False:
            return 'multiply driven ' + out
        seen.add(out)
    for out, op, ins in gates:
        for i in ins:
            if i not in seen:
                return 'undriven ' + i
    level = {p: 0 for p in pis}
    val = dict(pis)
    pending = list(gates)
    while pending:
        ready = [g for g in pending if all(i in level for i in g[2])]
        if not ready:
            return 'loop'
        for out, op, ins in ready:
            level[out] = 1 + max([level[i] for i in ins], default=-1)
            bits = [val[i] for i in ins]
            if op == 'and': v = int(all(bits))
            elif op == 'or': v = int(any(bits))
            elif op == 'xor': v = sum(bits) % 2
            elif op == 'nand': v = 1 - int(all(bits))
            elif op in ('tie0', 'tie1'): v = int(op == 'tie1')
            else: v = 1 - bits[0]
            val[out] = v
        pending = [g for g in pending if g not in ready]
    return {'depth': max(level.values()), 'values': [[k, val[k]] for k in sorted(val)]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('reconvergent netlist listed out of order', [{'a': 1, 'b': 1, 'c': 0}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 1], ['b', 1], ['c', 0], ['g1', 1], ['g2', 0], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 1, 'b': 1, 'c': 0}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 1], ['b', 1], ['c', 0], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 1, 'b': 1, 'c': 0}, [['g1', 'and', ['a', 'nosuch1']]]], 'undriven nosuch1'), ('real combinational loop', [{'a': 1, 'b': 1, 'c': 0}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 1, 'b': 1, 'c': 0}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 1, 'b': 1, 'c': 0}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 1}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 1], ['y', 1]]}), ('unbalanced depth', [{'a': 1, 'b': 1, 'c': 0}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'd3']]]], {'depth': 4, 'values': [['a', 1], ['b', 1], ['c', 0], ['d1', 0], ['d2', 1], ['d3', 1], ['d4', 1]]})], [('reconvergent netlist listed out of order', [{'a': 0, 'b': 1, 'c': 1}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 0], ['b', 1], ['c', 1], ['g1', 1], ['g2', 1], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 0, 'b': 1, 'c': 1}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 0], ['b', 1], ['c', 1], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 0, 'b': 1, 'c': 1}, [['g1', 'and', ['a', 'nosuch2']]]], 'undriven nosuch2'), ('real combinational loop', [{'a': 0, 'b': 1, 'c': 1}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 0, 'b': 1, 'c': 1}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 0, 'b': 1, 'c': 1}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 0}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 0], ['y', 1]]}), ('unbalanced depth', [{'a': 0, 'b': 1, 'c': 1}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'c', 'd3']]]], {'depth': 4, 'values': [['a', 0], ['b', 1], ['c', 1], ['d1', 1], ['d2', 0], ['d3', 0], ['d4', 1]]})], [('reconvergent netlist listed out of order', [{'a': 1, 'b': 1, 'c': 1}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 1], ['b', 1], ['c', 1], ['g1', 0], ['g2', 0], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 1, 'b': 1, 'c': 1}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 1], ['b', 1], ['c', 1], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 1, 'b': 1, 'c': 1}, [['g1', 'and', ['a', 'nosuch3']]]], 'undriven nosuch3'), ('real combinational loop', [{'a': 1, 'b': 1, 'c': 1}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 1, 'b': 1, 'c': 1}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 1, 'b': 1, 'c': 1}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 1}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 1], ['y', 1]]}), ('unbalanced depth', [{'a': 1, 'b': 1, 'c': 1}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'c', 'c', 'd3']]]], {'depth': 4, 'values': [['a', 1], ['b', 1], ['c', 1], ['d1', 0], ['d2', 1], ['d3', 1], ['d4', 1]]})], [('reconvergent netlist listed out of order', [{'a': 0, 'b': 1, 'c': 0}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 0], ['b', 1], ['c', 0], ['g1', 1], ['g2', 1], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 0, 'b': 1, 'c': 0}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 0], ['b', 1], ['c', 0], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 0, 'b': 1, 'c': 0}, [['g1', 'and', ['a', 'nosuch4']]]], 'undriven nosuch4'), ('real combinational loop', [{'a': 0, 'b': 1, 'c': 0}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 0, 'b': 1, 'c': 0}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 0, 'b': 1, 'c': 0}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 0}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 0], ['y', 1]]}), ('unbalanced depth', [{'a': 0, 'b': 1, 'c': 0}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'c', 'c', 'c', 'd3']]]], {'depth': 4, 'values': [['a', 0], ['b', 1], ['c', 0], ['d1', 1], ['d2', 0], ['d3', 0], ['d4', 0]]})], [('reconvergent netlist listed out of order', [{'a': 1, 'b': 1, 'c': 0}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 1], ['b', 1], ['c', 0], ['g1', 1], ['g2', 0], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 1, 'b': 1, 'c': 0}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 1], ['b', 1], ['c', 0], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 1, 'b': 1, 'c': 0}, [['g1', 'and', ['a', 'nosuch5']]]], 'undriven nosuch5'), ('real combinational loop', [{'a': 1, 'b': 1, 'c': 0}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 1, 'b': 1, 'c': 0}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 1, 'b': 1, 'c': 0}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 1}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 1], ['y', 1]]}), ('unbalanced depth', [{'a': 1, 'b': 1, 'c': 0}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'c', 'c', 'c', 'c', 'd3']]]], {'depth': 4, 'values': [['a', 1], ['b', 1], ['c', 0], ['d1', 0], ['d2', 1], ['d3', 1], ['d4', 1]]})]]
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 = args
    seen = set(pis)
    for out, op, ins in gates:
        if out in pis:
            return 'multiply driven ' + out
        seen.add(out)
    for out, op, ins in gates:
        for i in ins:
            if i not in seen:
                return 'undriven ' + i
    level = {p: 0 for p in pis}
    val = dict(pis)
    pending = list(gates)
    while pending:
        ready = [g for g in pending if all(i in level for i in g[2])]
        if not ready:
            return 'loop'
        for out, op, ins in ready:
            level[out] = 1 + max([level[i] for i in ins], default=-1)
            bits = [val[i] for i in ins]
            if op == 'and': v = int(all(bits))
            elif op == 'or': v = int(any(bits))
            elif op == 'xor': v = sum(bits) % 2
            elif op == 'nand': v = 1 - int(all(bits))
            elif op in ('tie0', 'tie1'): v = int(op == 'tie1')
            else: v = 1 - bits[0]
            val[out] = v
        pending = [g for g in pending if g not in ready]
    return {'depth': max(level.values()), 'values': [[k, val[k]] for k in sorted(val)]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('reconvergent netlist listed out of order', [{'a': 1, 'b': 1, 'c': 0}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 1], ['b', 1], ['c', 0], ['g1', 1], ['g2', 0], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 1, 'b': 1, 'c': 0}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 1], ['b', 1], ['c', 0], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 1, 'b': 1, 'c': 0}, [['g1', 'and', ['a', 'nosuch1']]]], 'undriven nosuch1'), ('real combinational loop', [{'a': 1, 'b': 1, 'c': 0}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 1, 'b': 1, 'c': 0}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 1, 'b': 1, 'c': 0}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 1}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 1], ['y', 1]]}), ('unbalanced depth', [{'a': 1, 'b': 1, 'c': 0}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'd3']]]], {'depth': 4, 'values': [['a', 1], ['b', 1], ['c', 0], ['d1', 0], ['d2', 1], ['d3', 1], ['d4', 1]]})], [('reconvergent netlist listed out of order', [{'a': 0, 'b': 1, 'c': 1}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 0], ['b', 1], ['c', 1], ['g1', 1], ['g2', 1], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 0, 'b': 1, 'c': 1}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 0], ['b', 1], ['c', 1], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 0, 'b': 1, 'c': 1}, [['g1', 'and', ['a', 'nosuch2']]]], 'undriven nosuch2'), ('real combinational loop', [{'a': 0, 'b': 1, 'c': 1}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 0, 'b': 1, 'c': 1}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 0, 'b': 1, 'c': 1}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 0}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 0], ['y', 1]]}), ('unbalanced depth', [{'a': 0, 'b': 1, 'c': 1}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'c', 'd3']]]], {'depth': 4, 'values': [['a', 0], ['b', 1], ['c', 1], ['d1', 1], ['d2', 0], ['d3', 0], ['d4', 1]]})], [('reconvergent netlist listed out of order', [{'a': 1, 'b': 1, 'c': 1}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 1], ['b', 1], ['c', 1], ['g1', 0], ['g2', 0], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 1, 'b': 1, 'c': 1}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 1], ['b', 1], ['c', 1], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 1, 'b': 1, 'c': 1}, [['g1', 'and', ['a', 'nosuch3']]]], 'undriven nosuch3'), ('real combinational loop', [{'a': 1, 'b': 1, 'c': 1}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 1, 'b': 1, 'c': 1}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 1, 'b': 1, 'c': 1}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 1}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 1], ['y', 1]]}), ('unbalanced depth', [{'a': 1, 'b': 1, 'c': 1}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'c', 'c', 'd3']]]], {'depth': 4, 'values': [['a', 1], ['b', 1], ['c', 1], ['d1', 0], ['d2', 1], ['d3', 1], ['d4', 1]]})], [('reconvergent netlist listed out of order', [{'a': 0, 'b': 1, 'c': 0}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 0], ['b', 1], ['c', 0], ['g1', 1], ['g2', 1], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 0, 'b': 1, 'c': 0}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 0], ['b', 1], ['c', 0], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 0, 'b': 1, 'c': 0}, [['g1', 'and', ['a', 'nosuch4']]]], 'undriven nosuch4'), ('real combinational loop', [{'a': 0, 'b': 1, 'c': 0}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 0, 'b': 1, 'c': 0}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 0, 'b': 1, 'c': 0}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 0}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 0], ['y', 1]]}), ('unbalanced depth', [{'a': 0, 'b': 1, 'c': 0}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'c', 'c', 'c', 'd3']]]], {'depth': 4, 'values': [['a', 0], ['b', 1], ['c', 0], ['d1', 1], ['d2', 0], ['d3', 0], ['d4', 0]]})], [('reconvergent netlist listed out of order', [{'a': 1, 'b': 1, 'c': 0}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 1], ['b', 1], ['c', 0], ['g1', 1], ['g2', 0], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 1, 'b': 1, 'c': 0}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 1], ['b', 1], ['c', 0], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 1, 'b': 1, 'c': 0}, [['g1', 'and', ['a', 'nosuch5']]]], 'undriven nosuch5'), ('real combinational loop', [{'a': 1, 'b': 1, 'c': 0}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 1, 'b': 1, 'c': 0}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 1, 'b': 1, 'c': 0}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 1}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 1], ['y', 1]]}), ('unbalanced depth', [{'a': 1, 'b': 1, 'c': 0}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'c', 'c', 'c', 'c', 'd3']]]], {'depth': 4, 'values': [['a', 1], ['b', 1], ['c', 0], ['d1', 0], ['d2', 1], ['d3', 1], ['d4', 1]]})]]
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:
Two gates driving the same net are accepted and the later one wins.

Input [pis, gates]: pis maps primary input net -> 0/1; gates are [out, op, ins] in any order with ops and/or/xor/nand/not/tie0/tie1. Reject with 'undriven <net>' (first gate in list order, first pin) if a gate reads a net driven by nobody, or 'multiply driven <net>' if a net has two drivers (a gate driving a primary input counts). Otherwise evaluate in dependency waves; return 'loop' if no gate becomes ready. Level: primary inputs 0, gate = 1 + max input level, tie cells 0. Return {'depth': max level, 'values': sorted [net, value]}.

split: open-access


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

N = 1
observations = []
def solve(*args):
    pis, gates = args
    seen = set(pis)
    for out, op, ins in gates:
        if out in seen:
            return 'multiply driven ' + out
        seen.add(out)
    for out, op, ins in gates:
        for i in ins:
            if i not in seen:
                return 'undriven ' + i
    level = {p: 0 for p in pis}
    val = dict(pis)
    pending = list(gates)
    while pending:
        ready = [g for g in pending if all(i in level for i in g[2])]
        if not ready:
            return 'loop'
        for out, op, ins in ready:
            level[out] = 1 + max([level[i] for i in ins], default=-1)
            bits = [val[i] for i in ins]
            if op == 'and': v = int(all(bits))
            elif op == 'or': v = int(any(bits))
            elif op == 'xor': v = sum(bits) % 2
            elif op == 'nand': v = int(not any(bits))
            elif op in ('tie0', 'tie1'): v = int(op == 'tie1')
            else: v = 1 - bits[0]
            val[out] = v
        pending = [g for g in pending if g not in ready]
    return {'depth': max(level.values()), 'values': [[k, val[k]] for k in sorted(val)]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('reconvergent netlist listed out of order', [{'a': 1, 'b': 1, 'c': 0}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 1], ['b', 1], ['c', 0], ['g1', 1], ['g2', 0], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 1, 'b': 1, 'c': 0}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 1], ['b', 1], ['c', 0], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 1, 'b': 1, 'c': 0}, [['g1', 'and', ['a', 'nosuch1']]]], 'undriven nosuch1'), ('real combinational loop', [{'a': 1, 'b': 1, 'c': 0}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 1, 'b': 1, 'c': 0}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 1, 'b': 1, 'c': 0}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 1}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 1], ['y', 1]]}), ('unbalanced depth', [{'a': 1, 'b': 1, 'c': 0}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'd3']]]], {'depth': 4, 'values': [['a', 1], ['b', 1], ['c', 0], ['d1', 0], ['d2', 1], ['d3', 1], ['d4', 1]]})], [('reconvergent netlist listed out of order', [{'a': 0, 'b': 1, 'c': 1}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 0], ['b', 1], ['c', 1], ['g1', 1], ['g2', 1], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 0, 'b': 1, 'c': 1}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 0], ['b', 1], ['c', 1], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 0, 'b': 1, 'c': 1}, [['g1', 'and', ['a', 'nosuch2']]]], 'undriven nosuch2'), ('real combinational loop', [{'a': 0, 'b': 1, 'c': 1}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 0, 'b': 1, 'c': 1}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 0, 'b': 1, 'c': 1}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 0}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 0], ['y', 1]]}), ('unbalanced depth', [{'a': 0, 'b': 1, 'c': 1}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'c', 'd3']]]], {'depth': 4, 'values': [['a', 0], ['b', 1], ['c', 1], ['d1', 1], ['d2', 0], ['d3', 0], ['d4', 1]]})], [('reconvergent netlist listed out of order', [{'a': 1, 'b': 1, 'c': 1}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 1], ['b', 1], ['c', 1], ['g1', 0], ['g2', 0], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 1, 'b': 1, 'c': 1}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 1], ['b', 1], ['c', 1], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 1, 'b': 1, 'c': 1}, [['g1', 'and', ['a', 'nosuch3']]]], 'undriven nosuch3'), ('real combinational loop', [{'a': 1, 'b': 1, 'c': 1}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 1, 'b': 1, 'c': 1}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 1, 'b': 1, 'c': 1}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 1}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 1], ['y', 1]]}), ('unbalanced depth', [{'a': 1, 'b': 1, 'c': 1}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'c', 'c', 'd3']]]], {'depth': 4, 'values': [['a', 1], ['b', 1], ['c', 1], ['d1', 0], ['d2', 1], ['d3', 1], ['d4', 1]]})], [('reconvergent netlist listed out of order', [{'a': 0, 'b': 1, 'c': 0}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 0], ['b', 1], ['c', 0], ['g1', 1], ['g2', 1], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 0, 'b': 1, 'c': 0}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 0], ['b', 1], ['c', 0], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 0, 'b': 1, 'c': 0}, [['g1', 'and', ['a', 'nosuch4']]]], 'undriven nosuch4'), ('real combinational loop', [{'a': 0, 'b': 1, 'c': 0}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 0, 'b': 1, 'c': 0}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 0, 'b': 1, 'c': 0}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 0}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 0], ['y', 1]]}), ('unbalanced depth', [{'a': 0, 'b': 1, 'c': 0}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'c', 'c', 'c', 'd3']]]], {'depth': 4, 'values': [['a', 0], ['b', 1], ['c', 0], ['d1', 1], ['d2', 0], ['d3', 0], ['d4', 0]]})], [('reconvergent netlist listed out of order', [{'a': 1, 'b': 1, 'c': 0}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 1], ['b', 1], ['c', 0], ['g1', 1], ['g2', 0], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 1, 'b': 1, 'c': 0}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 1], ['b', 1], ['c', 0], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 1, 'b': 1, 'c': 0}, [['g1', 'and', ['a', 'nosuch5']]]], 'undriven nosuch5'), ('real combinational loop', [{'a': 1, 'b': 1, 'c': 0}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 1, 'b': 1, 'c': 0}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 1, 'b': 1, 'c': 0}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 1}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 1], ['y', 1]]}), ('unbalanced depth', [{'a': 1, 'b': 1, 'c': 0}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'c', 'c', 'c', 'c', 'd3']]]], {'depth': 4, 'values': [['a', 1], ['b', 1], ['c', 0], ['d1', 0], ['d2', 1], ['d3', 1], ['d4', 1]]})]]
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 = args
    seen = set(pis)
    for out, op, ins in gates:
        if out in seen:
            return 'multiply driven ' + out
        seen.add(out)
    for out, op, ins in gates:
        for i in ins:
            if i not in seen:
                return 'undriven ' + i
    level = {p: 0 for p in pis}
    val = dict(pis)
    pending = list(gates)
    while pending:
        ready = [g for g in pending if all(i in level for i in g[2])]
        if not ready:
            return 'loop'
        for out, op, ins in ready:
            level[out] = 1 + max([level[i] for i in ins], default=-1)
            bits = [val[i] for i in ins]
            if op == 'and': v = int(all(bits))
            elif op == 'or': v = int(any(bits))
            elif op == 'xor': v = sum(bits) % 2
            elif op == 'nand': v = 1 - bits[0] * bits[1]
            elif op in ('tie0', 'tie1'): v = int(op == 'tie1')
            else: v = 1 - bits[0]
            val[out] = v
        pending = [g for g in pending if g not in ready]
    return {'depth': max(level.values()), 'values': [[k, val[k]] for k in sorted(val)]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('reconvergent netlist listed out of order', [{'a': 1, 'b': 1, 'c': 0}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 1], ['b', 1], ['c', 0], ['g1', 1], ['g2', 0], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 1, 'b': 1, 'c': 0}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 1], ['b', 1], ['c', 0], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 1, 'b': 1, 'c': 0}, [['g1', 'and', ['a', 'nosuch1']]]], 'undriven nosuch1'), ('real combinational loop', [{'a': 1, 'b': 1, 'c': 0}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 1, 'b': 1, 'c': 0}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 1, 'b': 1, 'c': 0}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 1}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 1], ['y', 1]]}), ('unbalanced depth', [{'a': 1, 'b': 1, 'c': 0}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'd3']]]], {'depth': 4, 'values': [['a', 1], ['b', 1], ['c', 0], ['d1', 0], ['d2', 1], ['d3', 1], ['d4', 1]]})], [('reconvergent netlist listed out of order', [{'a': 0, 'b': 1, 'c': 1}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 0], ['b', 1], ['c', 1], ['g1', 1], ['g2', 1], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 0, 'b': 1, 'c': 1}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 0], ['b', 1], ['c', 1], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 0, 'b': 1, 'c': 1}, [['g1', 'and', ['a', 'nosuch2']]]], 'undriven nosuch2'), ('real combinational loop', [{'a': 0, 'b': 1, 'c': 1}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 0, 'b': 1, 'c': 1}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 0, 'b': 1, 'c': 1}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 0}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 0], ['y', 1]]}), ('unbalanced depth', [{'a': 0, 'b': 1, 'c': 1}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'c', 'd3']]]], {'depth': 4, 'values': [['a', 0], ['b', 1], ['c', 1], ['d1', 1], ['d2', 0], ['d3', 0], ['d4', 1]]})], [('reconvergent netlist listed out of order', [{'a': 1, 'b': 1, 'c': 1}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 1], ['b', 1], ['c', 1], ['g1', 0], ['g2', 0], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 1, 'b': 1, 'c': 1}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 1], ['b', 1], ['c', 1], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 1, 'b': 1, 'c': 1}, [['g1', 'and', ['a', 'nosuch3']]]], 'undriven nosuch3'), ('real combinational loop', [{'a': 1, 'b': 1, 'c': 1}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 1, 'b': 1, 'c': 1}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 1, 'b': 1, 'c': 1}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 1}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 1], ['y', 1]]}), ('unbalanced depth', [{'a': 1, 'b': 1, 'c': 1}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'c', 'c', 'd3']]]], {'depth': 4, 'values': [['a', 1], ['b', 1], ['c', 1], ['d1', 0], ['d2', 1], ['d3', 1], ['d4', 1]]})], [('reconvergent netlist listed out of order', [{'a': 0, 'b': 1, 'c': 0}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 0], ['b', 1], ['c', 0], ['g1', 1], ['g2', 1], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 0, 'b': 1, 'c': 0}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 0], ['b', 1], ['c', 0], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 0, 'b': 1, 'c': 0}, [['g1', 'and', ['a', 'nosuch4']]]], 'undriven nosuch4'), ('real combinational loop', [{'a': 0, 'b': 1, 'c': 0}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 0, 'b': 1, 'c': 0}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 0, 'b': 1, 'c': 0}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 0}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 0], ['y', 1]]}), ('unbalanced depth', [{'a': 0, 'b': 1, 'c': 0}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'c', 'c', 'c', 'd3']]]], {'depth': 4, 'values': [['a', 0], ['b', 1], ['c', 0], ['d1', 1], ['d2', 0], ['d3', 0], ['d4', 0]]})], [('reconvergent netlist listed out of order', [{'a': 1, 'b': 1, 'c': 0}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 1], ['b', 1], ['c', 0], ['g1', 1], ['g2', 0], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 1, 'b': 1, 'c': 0}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 1], ['b', 1], ['c', 0], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 1, 'b': 1, 'c': 0}, [['g1', 'and', ['a', 'nosuch5']]]], 'undriven nosuch5'), ('real combinational loop', [{'a': 1, 'b': 1, 'c': 0}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 1, 'b': 1, 'c': 0}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 1, 'b': 1, 'c': 0}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 1}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 1], ['y', 1]]}), ('unbalanced depth', [{'a': 1, 'b': 1, 'c': 0}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'c', 'c', 'c', 'c', 'd3']]]], {'depth': 4, 'values': [['a', 1], ['b', 1], ['c', 0], ['d1', 0], ['d2', 1], ['d3', 1], ['d4', 1]]})]]
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 NAND gate with mixed inputs evaluates to 0.

Input [pis, gates]: pis maps primary input net -> 0/1; gates are [out, op, ins] in any order with ops and/or/xor/nand/not/tie0/tie1. Reject with 'undriven <net>' (first gate in list order, first pin) if a gate reads a net driven by nobody, or 'multiply driven <net>' if a net has two drivers (a gate driving a primary input counts). Otherwise evaluate in dependency waves; return 'loop' if no gate becomes ready. Level: primary inputs 0, gate = 1 + max input level, tie cells 0. Return {'depth': max level, 'values': sorted [net, value]}.

split: open-access


prompt:
Asserting reset between clock edges leaves q at its old value until the next rising edge.

Input: samples [clk, d, en, rst_n] at successive instants. q starts as "x". Active-low rst_n==0 forces q=0 immediately regardless of clock. Otherwise a rising clock edge (previous sample clk 0, this sample clk 1; the first sample is never an edge) with en==1 loads d. The previous clock value is tracked on every sample, including while reset is asserted. Return q after each sample.

split: open-access


prompt:
q follows d on every sample the clock is high rather than only at the rising edge.

Input: samples [clk, d, en, rst_n] at successive instants. q starts as "x". Active-low rst_n==0 forces q=0 immediately regardless of clock. Otherwise a rising clock edge (previous sample clk 0, this sample clk 1; the first sample is never an edge) with en==1 loads d. The previous clock value is tracked on every sample, including while reset is asserted. Return q after each sample.

split: open-access


prompt:
Releasing reset while the clock is already high produces a phantom capture edge.

Input: samples [clk, d, en, rst_n] at successive instants. q starts as "x". Active-low rst_n==0 forces q=0 immediately regardless of clock. Otherwise a rising clock edge (previous sample clk 0, this sample clk 1; the first sample is never an edge) with en==1 loads d. The previous clock value is tracked on every sample, including while reset is asserted. Return q after each sample.

split: open-access


prompt:
Before any reset or capture the register reports 0 instead of unknown.

Input: samples [clk, d, en, rst_n] at successive instants. q starts as "x". Active-low rst_n==0 forces q=0 immediately regardless of clock. Otherwise a rising clock edge (previous sample clk 0, this sample clk 1; the first sample is never an edge) with en==1 loads d. The previous clock value is tracked on every sample, including while reset is asserted. Return q after each sample.

split: open-access


prompt:
A rising edge while reset is held loads d, so q is not 0 during reset.

Input: samples [clk, d, en, rst_n] at successive instants. q starts as "x". Active-low rst_n==0 forces q=0 immediately regardless of clock. Otherwise a rising clock edge (previous sample clk 0, this sample clk 1; the first sample is never an edge) with en==1 loads d. The previous clock value is tracked on every sample, including while reset is asserted. Return q after each sample.

split: open-access


prompt:
Data that changes exactly setup time units before the clock edge is reported as a setup violation.

Input [c0, clock, data, setup, hold]: c0 is the initial clock level, clock is time-sorted [t, v] transitions (possibly redundant), data is a list of data transition times. Rising edges are 0->1 changes only. For every data time t and every rising edge e: e-setup < t < e is a 'setup' violation, e <= t < e+hold is a 'hold' violation. Return all [e, t, kind] sorted by edge, then time.

split: open-access


prompt:
A data transition exactly at the rising edge is not reported at all.

Input [c0, clock, data, setup, hold]: c0 is the initial clock level, clock is time-sorted [t, v] transitions (possibly redundant), data is a list of data transition times. Rising edges are 0->1 changes only. For every data time t and every rising edge e: e-setup < t < e is a 'setup' violation, e <= t < e+hold is a 'hold' violation. Return all [e, t, kind] sorted by edge, then time.

split: open-access


prompt:
Data transitions near falling clock edges are reported as violations.

Input [c0, clock, data, setup, hold]: c0 is the initial clock level, clock is time-sorted [t, v] transitions (possibly redundant), data is a list of data transition times. Rising edges are 0->1 changes only. For every data time t and every rising edge e: e-setup < t < e is a 'setup' violation, e <= t < e+hold is a 'hold' violation. Return all [e, t, kind] sorted by edge, then time.

split: open-access


prompt:
A clock that starts high reports a phantom rising edge at its first redundant transition.

Input [c0, clock, data, setup, hold]: c0 is the initial clock level, clock is time-sorted [t, v] transitions (possibly redundant), data is a list of data transition times. Rising edges are 0->1 changes only. For every data time t and every rising edge e: e-setup < t < e is a 'setup' violation, e <= t < e+hold is a 'hold' violation. Return all [e, t, kind] sorted by edge, then time.

split: open-access


prompt:
When windows of adjacent edges overlap, violations come out grouped by data time rather than by edge.

Input [c0, clock, data, setup, hold]: c0 is the initial clock level, clock is time-sorted [t, v] transitions (possibly redundant), data is a list of data transition times. Rising edges are 0->1 changes only. For every data time t and every rising edge e: e-setup < t < e is a 'setup' violation, e <= t < e+hold is a 'hold' violation. Return all [e, t, kind] sorted by edge, then time.

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 + min(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: 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 + sum(arr[f] for f in fi) // len(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: 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:
Reported slack is optimistic and the critical path follows a short 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


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)
        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] - 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: 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:
Every endpoint slack is too large by exactly the setup 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