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

N = 1
observations = []
def solve(d):
    nodes={x[0]:x[1:] for x in d['nodes']}; root=d['root']; todo=[] if root is None else [(root,0)]; seen=[]; indices=[]; repeated=[]
    while todo:
        v,k=todo.pop(0)
        if v in seen:
            repeated.append(v); continue
        seen.append(v); indices.append(k)
        for offset,child in enumerate(nodes[v],1):
            if child is not None: todo.append((child,2*k+offset))
    return {'visits': seen,
    'unreachable': sorted(set(nodes)-set(seen)),
    'repeated': repeated,
    'complete': len(seen)==len(nodes),
    'right_only': [v for v,(l,r) in nodes.items() if l is None and r is not None],
    'incoming': {v:sum(v==c for pair in nodes.values() for c in pair) for v in nodes}}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'nodes': [], 'root': None}, {'visits': [], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {}}), ({'nodes': [['a', None, None]], 'root': 'a'}, {'visits': ['a'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'a': 0}}), ({'nodes': [['c', None, None], ['a', 'b', 'c'], ['b', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'c': 1, 'a': 0, 'b': 1}}), ({'nodes': [['a', None, 'b'], ['b', None, None], ['c', None, None]], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': ['c'], 'repeated': [], 'complete': False, 'right_only': ['a'], 'incoming': {'a': 0, 'b': 1, 'c': 0}}), ({'nodes': [['a', 'b', 'b'], ['b', 'a', 'a']], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': [], 'repeated': ['b', 'a', 'a'], 'complete': False, 'right_only': [], 'incoming': {'a': 2, 'b': 2}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': [], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None], ['100', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': ['100'], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1, '100': 0}})], [({'nodes': [], 'root': None}, {'visits': [], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {}}), ({'nodes': [['a', None, None]], 'root': 'a'}, {'visits': ['a'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'a': 0}}), ({'nodes': [['c', None, None], ['a', 'b', 'c'], ['b', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'c': 1, 'a': 0, 'b': 1}}), ({'nodes': [['a', None, 'b'], ['b', None, None], ['c', None, None]], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': ['c'], 'repeated': [], 'complete': False, 'right_only': ['a'], 'incoming': {'a': 0, 'b': 1, 'c': 0}}), ({'nodes': [['a', 'b', 'b'], ['b', 'a', 'a']], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': [], 'repeated': ['b', 'a', 'a'], 'complete': False, 'right_only': [], 'incoming': {'a': 2, 'b': 2}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': [], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None], ['100', None, None], ['101', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': ['100', '101'], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1, '100': 0, '101': 0}})], [({'nodes': [], 'root': None}, {'visits': [], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {}}), ({'nodes': [['a', None, None]], 'root': 'a'}, {'visits': ['a'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'a': 0}}), ({'nodes': [['c', None, None], ['a', 'b', 'c'], ['b', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'c': 1, 'a': 0, 'b': 1}}), ({'nodes': [['a', None, 'b'], ['b', None, None], ['c', None, None]], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': ['c'], 'repeated': [], 'complete': False, 'right_only': ['a'], 'incoming': {'a': 0, 'b': 1, 'c': 0}}), ({'nodes': [['a', 'b', 'b'], ['b', 'a', 'a']], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': [], 'repeated': ['b', 'a', 'a'], 'complete': False, 'right_only': [], 'incoming': {'a': 2, 'b': 2}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': [], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None], ['100', None, None], ['101', None, None], ['102', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': ['100', '101', '102'], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1, '100': 0, '101': 0, '102': 0}})], [({'nodes': [], 'root': None}, {'visits': [], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {}}), ({'nodes': [['a', None, None]], 'root': 'a'}, {'visits': ['a'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'a': 0}}), ({'nodes': [['c', None, None], ['a', 'b', 'c'], ['b', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'c': 1, 'a': 0, 'b': 1}}), ({'nodes': [['a', None, 'b'], ['b', None, None], ['c', None, None]], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': ['c'], 'repeated': [], 'complete': False, 'right_only': ['a'], 'incoming': {'a': 0, 'b': 1, 'c': 0}}), ({'nodes': [['a', 'b', 'b'], ['b', 'a', 'a']], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': [], 'repeated': ['b', 'a', 'a'], 'complete': False, 'right_only': [], 'incoming': {'a': 2, 'b': 2}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': [], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None], ['100', None, None], ['101', None, None], ['102', None, None], ['103', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': ['100', '101', '102', '103'], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1, '100': 0, '101': 0, '102': 0, '103': 0}})], [({'nodes': [], 'root': None}, {'visits': [], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {}}), ({'nodes': [['a', None, None]], 'root': 'a'}, {'visits': ['a'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'a': 0}}), ({'nodes': [['c', None, None], ['a', 'b', 'c'], ['b', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'c': 1, 'a': 0, 'b': 1}}), ({'nodes': [['a', None, 'b'], ['b', None, None], ['c', None, None]], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': ['c'], 'repeated': [], 'complete': False, 'right_only': ['a'], 'incoming': {'a': 0, 'b': 1, 'c': 0}}), ({'nodes': [['a', 'b', 'b'], ['b', 'a', 'a']], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': [], 'repeated': ['b', 'a', 'a'], 'complete': False, 'right_only': [], 'incoming': {'a': 2, 'b': 2}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': [], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None], ['100', None, None], ['101', None, None], ['102', None, None], ['103', None, None], ['104', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': ['100', '101', '102', '103', '104'], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1, '100': 0, '101': 0, '102': 0, '103': 0, '104': 0}})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
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(d):
    nodes={x[0]:x[1:] for x in d['nodes']}; root=d['root']; todo=[] if root is None else [(root,0)]; seen=[]; indices=[]; repeated=[]
    while todo:
        v,k=todo.pop(0)
        if v in seen:
            repeated.append(v); continue
        seen.append(v); indices.append(k)
        for offset,child in enumerate(nodes[v],1):
            if child is not None: todo.append((child,2*k+offset))
    return {'visits': seen,
    'unreachable': sorted(set(nodes)-set(seen)),
    'repeated': repeated,
    'complete': not repeated and len(seen)==len(nodes),
    'right_only': [v for v,(l,r) in nodes.items() if l is None and r is not None],
    'incoming': {v:sum(v==c for pair in nodes.values() for c in pair) for v in nodes}}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'nodes': [], 'root': None}, {'visits': [], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {}}), ({'nodes': [['a', None, None]], 'root': 'a'}, {'visits': ['a'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'a': 0}}), ({'nodes': [['c', None, None], ['a', 'b', 'c'], ['b', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'c': 1, 'a': 0, 'b': 1}}), ({'nodes': [['a', None, 'b'], ['b', None, None], ['c', None, None]], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': ['c'], 'repeated': [], 'complete': False, 'right_only': ['a'], 'incoming': {'a': 0, 'b': 1, 'c': 0}}), ({'nodes': [['a', 'b', 'b'], ['b', 'a', 'a']], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': [], 'repeated': ['b', 'a', 'a'], 'complete': False, 'right_only': [], 'incoming': {'a': 2, 'b': 2}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': [], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None], ['100', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': ['100'], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1, '100': 0}})], [({'nodes': [], 'root': None}, {'visits': [], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {}}), ({'nodes': [['a', None, None]], 'root': 'a'}, {'visits': ['a'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'a': 0}}), ({'nodes': [['c', None, None], ['a', 'b', 'c'], ['b', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'c': 1, 'a': 0, 'b': 1}}), ({'nodes': [['a', None, 'b'], ['b', None, None], ['c', None, None]], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': ['c'], 'repeated': [], 'complete': False, 'right_only': ['a'], 'incoming': {'a': 0, 'b': 1, 'c': 0}}), ({'nodes': [['a', 'b', 'b'], ['b', 'a', 'a']], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': [], 'repeated': ['b', 'a', 'a'], 'complete': False, 'right_only': [], 'incoming': {'a': 2, 'b': 2}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': [], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None], ['100', None, None], ['101', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': ['100', '101'], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1, '100': 0, '101': 0}})], [({'nodes': [], 'root': None}, {'visits': [], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {}}), ({'nodes': [['a', None, None]], 'root': 'a'}, {'visits': ['a'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'a': 0}}), ({'nodes': [['c', None, None], ['a', 'b', 'c'], ['b', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'c': 1, 'a': 0, 'b': 1}}), ({'nodes': [['a', None, 'b'], ['b', None, None], ['c', None, None]], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': ['c'], 'repeated': [], 'complete': False, 'right_only': ['a'], 'incoming': {'a': 0, 'b': 1, 'c': 0}}), ({'nodes': [['a', 'b', 'b'], ['b', 'a', 'a']], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': [], 'repeated': ['b', 'a', 'a'], 'complete': False, 'right_only': [], 'incoming': {'a': 2, 'b': 2}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': [], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None], ['100', None, None], ['101', None, None], ['102', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': ['100', '101', '102'], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1, '100': 0, '101': 0, '102': 0}})], [({'nodes': [], 'root': None}, {'visits': [], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {}}), ({'nodes': [['a', None, None]], 'root': 'a'}, {'visits': ['a'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'a': 0}}), ({'nodes': [['c', None, None], ['a', 'b', 'c'], ['b', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'c': 1, 'a': 0, 'b': 1}}), ({'nodes': [['a', None, 'b'], ['b', None, None], ['c', None, None]], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': ['c'], 'repeated': [], 'complete': False, 'right_only': ['a'], 'incoming': {'a': 0, 'b': 1, 'c': 0}}), ({'nodes': [['a', 'b', 'b'], ['b', 'a', 'a']], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': [], 'repeated': ['b', 'a', 'a'], 'complete': False, 'right_only': [], 'incoming': {'a': 2, 'b': 2}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': [], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None], ['100', None, None], ['101', None, None], ['102', None, None], ['103', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': ['100', '101', '102', '103'], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1, '100': 0, '101': 0, '102': 0, '103': 0}})], [({'nodes': [], 'root': None}, {'visits': [], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {}}), ({'nodes': [['a', None, None]], 'root': 'a'}, {'visits': ['a'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'a': 0}}), ({'nodes': [['c', None, None], ['a', 'b', 'c'], ['b', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'c': 1, 'a': 0, 'b': 1}}), ({'nodes': [['a', None, 'b'], ['b', None, None], ['c', None, None]], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': ['c'], 'repeated': [], 'complete': False, 'right_only': ['a'], 'incoming': {'a': 0, 'b': 1, 'c': 0}}), ({'nodes': [['a', 'b', 'b'], ['b', 'a', 'a']], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': [], 'repeated': ['b', 'a', 'a'], 'complete': False, 'right_only': [], 'incoming': {'a': 2, 'b': 2}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': [], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None], ['100', None, None], ['101', None, None], ['102', None, None], ['103', None, None], ['104', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': ['100', '101', '102', '103', '104'], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1, '100': 0, '101': 0, '102': 0, '103': 0, '104': 0}})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
The bounded complete tree certificate certificate reports an incorrect complete.

A bounded binary pointer-tree certificate gives node records [id,left_id,right_id], root id or None; references name existing nodes or None. Breadth-first traversal stops expanding previously seen ids. Assign conceptual heap indices root=0,left=2i+1,right=2i+2. Report visit ids, unreachable ids, shared/cyclic references encountered, completeness (unique indices 0..n-1 and all nodes reached without repeats), right-only parents, and parent multiplicities.

split: open-access


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

N = 1
observations = []
def solve(d):
    nodes={x[0]:x[1:] for x in d['nodes']}; root=d['root']; todo=[] if root is None else [(root,0)]; seen=[]; indices=[]; repeated=[]
    while todo:
        v,k=todo.pop(0)
        if v in seen:
            repeated.append(v); continue
        seen.append(v); indices.append(k)
        for offset,child in enumerate(nodes[v],1):
            if child is not None: todo.append((child,2*k+offset))
    return {'visits': seen,
    'unreachable': sorted(set(nodes)-set(seen)),
    'repeated': repeated,
    'complete': not repeated and len(seen)==len(nodes) and sorted(indices)==list(range(len(nodes))),
    'right_only': [v for v,(l,r) in nodes.items() if l is not None and r is None],
    'incoming': {v:sum(v==c for pair in nodes.values() for c in pair) for v in nodes}}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'nodes': [], 'root': None}, {'visits': [], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {}}), ({'nodes': [['a', None, None]], 'root': 'a'}, {'visits': ['a'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'a': 0}}), ({'nodes': [['c', None, None], ['a', 'b', 'c'], ['b', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'c': 1, 'a': 0, 'b': 1}}), ({'nodes': [['a', None, 'b'], ['b', None, None], ['c', None, None]], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': ['c'], 'repeated': [], 'complete': False, 'right_only': ['a'], 'incoming': {'a': 0, 'b': 1, 'c': 0}}), ({'nodes': [['a', 'b', 'b'], ['b', 'a', 'a']], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': [], 'repeated': ['b', 'a', 'a'], 'complete': False, 'right_only': [], 'incoming': {'a': 2, 'b': 2}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': [], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None], ['100', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': ['100'], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1, '100': 0}})], [({'nodes': [], 'root': None}, {'visits': [], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {}}), ({'nodes': [['a', None, None]], 'root': 'a'}, {'visits': ['a'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'a': 0}}), ({'nodes': [['c', None, None], ['a', 'b', 'c'], ['b', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'c': 1, 'a': 0, 'b': 1}}), ({'nodes': [['a', None, 'b'], ['b', None, None], ['c', None, None]], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': ['c'], 'repeated': [], 'complete': False, 'right_only': ['a'], 'incoming': {'a': 0, 'b': 1, 'c': 0}}), ({'nodes': [['a', 'b', 'b'], ['b', 'a', 'a']], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': [], 'repeated': ['b', 'a', 'a'], 'complete': False, 'right_only': [], 'incoming': {'a': 2, 'b': 2}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': [], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None], ['100', None, None], ['101', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': ['100', '101'], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1, '100': 0, '101': 0}})], [({'nodes': [], 'root': None}, {'visits': [], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {}}), ({'nodes': [['a', None, None]], 'root': 'a'}, {'visits': ['a'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'a': 0}}), ({'nodes': [['c', None, None], ['a', 'b', 'c'], ['b', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'c': 1, 'a': 0, 'b': 1}}), ({'nodes': [['a', None, 'b'], ['b', None, None], ['c', None, None]], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': ['c'], 'repeated': [], 'complete': False, 'right_only': ['a'], 'incoming': {'a': 0, 'b': 1, 'c': 0}}), ({'nodes': [['a', 'b', 'b'], ['b', 'a', 'a']], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': [], 'repeated': ['b', 'a', 'a'], 'complete': False, 'right_only': [], 'incoming': {'a': 2, 'b': 2}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': [], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None], ['100', None, None], ['101', None, None], ['102', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': ['100', '101', '102'], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1, '100': 0, '101': 0, '102': 0}})], [({'nodes': [], 'root': None}, {'visits': [], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {}}), ({'nodes': [['a', None, None]], 'root': 'a'}, {'visits': ['a'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'a': 0}}), ({'nodes': [['c', None, None], ['a', 'b', 'c'], ['b', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'c': 1, 'a': 0, 'b': 1}}), ({'nodes': [['a', None, 'b'], ['b', None, None], ['c', None, None]], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': ['c'], 'repeated': [], 'complete': False, 'right_only': ['a'], 'incoming': {'a': 0, 'b': 1, 'c': 0}}), ({'nodes': [['a', 'b', 'b'], ['b', 'a', 'a']], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': [], 'repeated': ['b', 'a', 'a'], 'complete': False, 'right_only': [], 'incoming': {'a': 2, 'b': 2}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': [], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None], ['100', None, None], ['101', None, None], ['102', None, None], ['103', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': ['100', '101', '102', '103'], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1, '100': 0, '101': 0, '102': 0, '103': 0}})], [({'nodes': [], 'root': None}, {'visits': [], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {}}), ({'nodes': [['a', None, None]], 'root': 'a'}, {'visits': ['a'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'a': 0}}), ({'nodes': [['c', None, None], ['a', 'b', 'c'], ['b', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'c': 1, 'a': 0, 'b': 1}}), ({'nodes': [['a', None, 'b'], ['b', None, None], ['c', None, None]], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': ['c'], 'repeated': [], 'complete': False, 'right_only': ['a'], 'incoming': {'a': 0, 'b': 1, 'c': 0}}), ({'nodes': [['a', 'b', 'b'], ['b', 'a', 'a']], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': [], 'repeated': ['b', 'a', 'a'], 'complete': False, 'right_only': [], 'incoming': {'a': 2, 'b': 2}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': [], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None], ['100', None, None], ['101', None, None], ['102', None, None], ['103', None, None], ['104', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': ['100', '101', '102', '103', '104'], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1, '100': 0, '101': 0, '102': 0, '103': 0, '104': 0}})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
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(d):
    nodes={x[0]:x[1:] for x in d['nodes']}; root=d['root']; todo=[] if root is None else [(root,0)]; seen=[]; indices=[]; repeated=[]
    while todo:
        v,k=todo.pop(0)
        if v in seen:
            repeated.append(v); continue
        seen.append(v); indices.append(k)
        for offset,child in enumerate(nodes[v],1):
            if child is not None: todo.append((child,2*k+offset))
    return {'visits': seen,
    'unreachable': sorted(set(nodes)-set(seen)),
    'repeated': repeated,
    'complete': not repeated and len(seen)==len(nodes) and sorted(indices)==list(range(len(nodes))),
    'right_only': [v for v,(l,r) in nodes.items() if r is not None],
    'incoming': {v:sum(v==c for pair in nodes.values() for c in pair) for v in nodes}}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'nodes': [], 'root': None}, {'visits': [], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {}}), ({'nodes': [['a', None, None]], 'root': 'a'}, {'visits': ['a'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'a': 0}}), ({'nodes': [['c', None, None], ['a', 'b', 'c'], ['b', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'c': 1, 'a': 0, 'b': 1}}), ({'nodes': [['a', None, 'b'], ['b', None, None], ['c', None, None]], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': ['c'], 'repeated': [], 'complete': False, 'right_only': ['a'], 'incoming': {'a': 0, 'b': 1, 'c': 0}}), ({'nodes': [['a', 'b', 'b'], ['b', 'a', 'a']], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': [], 'repeated': ['b', 'a', 'a'], 'complete': False, 'right_only': [], 'incoming': {'a': 2, 'b': 2}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': [], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None], ['100', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': ['100'], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1, '100': 0}})], [({'nodes': [], 'root': None}, {'visits': [], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {}}), ({'nodes': [['a', None, None]], 'root': 'a'}, {'visits': ['a'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'a': 0}}), ({'nodes': [['c', None, None], ['a', 'b', 'c'], ['b', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'c': 1, 'a': 0, 'b': 1}}), ({'nodes': [['a', None, 'b'], ['b', None, None], ['c', None, None]], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': ['c'], 'repeated': [], 'complete': False, 'right_only': ['a'], 'incoming': {'a': 0, 'b': 1, 'c': 0}}), ({'nodes': [['a', 'b', 'b'], ['b', 'a', 'a']], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': [], 'repeated': ['b', 'a', 'a'], 'complete': False, 'right_only': [], 'incoming': {'a': 2, 'b': 2}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': [], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None], ['100', None, None], ['101', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': ['100', '101'], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1, '100': 0, '101': 0}})], [({'nodes': [], 'root': None}, {'visits': [], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {}}), ({'nodes': [['a', None, None]], 'root': 'a'}, {'visits': ['a'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'a': 0}}), ({'nodes': [['c', None, None], ['a', 'b', 'c'], ['b', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'c': 1, 'a': 0, 'b': 1}}), ({'nodes': [['a', None, 'b'], ['b', None, None], ['c', None, None]], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': ['c'], 'repeated': [], 'complete': False, 'right_only': ['a'], 'incoming': {'a': 0, 'b': 1, 'c': 0}}), ({'nodes': [['a', 'b', 'b'], ['b', 'a', 'a']], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': [], 'repeated': ['b', 'a', 'a'], 'complete': False, 'right_only': [], 'incoming': {'a': 2, 'b': 2}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': [], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None], ['100', None, None], ['101', None, None], ['102', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': ['100', '101', '102'], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1, '100': 0, '101': 0, '102': 0}})], [({'nodes': [], 'root': None}, {'visits': [], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {}}), ({'nodes': [['a', None, None]], 'root': 'a'}, {'visits': ['a'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'a': 0}}), ({'nodes': [['c', None, None], ['a', 'b', 'c'], ['b', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'c': 1, 'a': 0, 'b': 1}}), ({'nodes': [['a', None, 'b'], ['b', None, None], ['c', None, None]], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': ['c'], 'repeated': [], 'complete': False, 'right_only': ['a'], 'incoming': {'a': 0, 'b': 1, 'c': 0}}), ({'nodes': [['a', 'b', 'b'], ['b', 'a', 'a']], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': [], 'repeated': ['b', 'a', 'a'], 'complete': False, 'right_only': [], 'incoming': {'a': 2, 'b': 2}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': [], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None], ['100', None, None], ['101', None, None], ['102', None, None], ['103', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': ['100', '101', '102', '103'], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1, '100': 0, '101': 0, '102': 0, '103': 0}})], [({'nodes': [], 'root': None}, {'visits': [], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {}}), ({'nodes': [['a', None, None]], 'root': 'a'}, {'visits': ['a'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'a': 0}}), ({'nodes': [['c', None, None], ['a', 'b', 'c'], ['b', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'c': 1, 'a': 0, 'b': 1}}), ({'nodes': [['a', None, 'b'], ['b', None, None], ['c', None, None]], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': ['c'], 'repeated': [], 'complete': False, 'right_only': ['a'], 'incoming': {'a': 0, 'b': 1, 'c': 0}}), ({'nodes': [['a', 'b', 'b'], ['b', 'a', 'a']], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': [], 'repeated': ['b', 'a', 'a'], 'complete': False, 'right_only': [], 'incoming': {'a': 2, 'b': 2}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': [], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None], ['100', None, None], ['101', None, None], ['102', None, None], ['103', None, None], ['104', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': ['100', '101', '102', '103', '104'], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1, '100': 0, '101': 0, '102': 0, '103': 0, '104': 0}})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
The bounded complete tree certificate certificate reports an incorrect right only.

A bounded binary pointer-tree certificate gives node records [id,left_id,right_id], root id or None; references name existing nodes or None. Breadth-first traversal stops expanding previously seen ids. Assign conceptual heap indices root=0,left=2i+1,right=2i+2. Report visit ids, unreachable ids, shared/cyclic references encountered, completeness (unique indices 0..n-1 and all nodes reached without repeats), right-only parents, and parent multiplicities.

split: open-access


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

N = 1
observations = []
def solve(d):
    nodes={x[0]:x[1:] for x in d['nodes']}; root=d['root']; todo=[] if root is None else [(root,0)]; seen=[]; indices=[]; repeated=[]
    while todo:
        v,k=todo.pop(0)
        if v in seen:
            repeated.append(v); continue
        seen.append(v); indices.append(k)
        for offset,child in enumerate(nodes[v],1):
            if child is not None: todo.append((child,2*k+offset))
    return {'visits': seen,
    'unreachable': sorted(set(nodes)-set(seen)),
    'repeated': repeated,
    'complete': not repeated and len(seen)==len(nodes) and sorted(indices)==list(range(len(nodes))),
    'right_only': [v for v,(l,r) in nodes.items() if l is None and r is not None],
    'incoming': {v:int(any(v in pair for pair in nodes.values())) for v in nodes}}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'nodes': [], 'root': None}, {'visits': [], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {}}), ({'nodes': [['a', None, None]], 'root': 'a'}, {'visits': ['a'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'a': 0}}), ({'nodes': [['c', None, None], ['a', 'b', 'c'], ['b', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'c': 1, 'a': 0, 'b': 1}}), ({'nodes': [['a', None, 'b'], ['b', None, None], ['c', None, None]], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': ['c'], 'repeated': [], 'complete': False, 'right_only': ['a'], 'incoming': {'a': 0, 'b': 1, 'c': 0}}), ({'nodes': [['a', 'b', 'b'], ['b', 'a', 'a']], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': [], 'repeated': ['b', 'a', 'a'], 'complete': False, 'right_only': [], 'incoming': {'a': 2, 'b': 2}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': [], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None], ['100', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': ['100'], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1, '100': 0}})], [({'nodes': [], 'root': None}, {'visits': [], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {}}), ({'nodes': [['a', None, None]], 'root': 'a'}, {'visits': ['a'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'a': 0}}), ({'nodes': [['c', None, None], ['a', 'b', 'c'], ['b', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'c': 1, 'a': 0, 'b': 1}}), ({'nodes': [['a', None, 'b'], ['b', None, None], ['c', None, None]], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': ['c'], 'repeated': [], 'complete': False, 'right_only': ['a'], 'incoming': {'a': 0, 'b': 1, 'c': 0}}), ({'nodes': [['a', 'b', 'b'], ['b', 'a', 'a']], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': [], 'repeated': ['b', 'a', 'a'], 'complete': False, 'right_only': [], 'incoming': {'a': 2, 'b': 2}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': [], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None], ['100', None, None], ['101', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': ['100', '101'], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1, '100': 0, '101': 0}})], [({'nodes': [], 'root': None}, {'visits': [], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {}}), ({'nodes': [['a', None, None]], 'root': 'a'}, {'visits': ['a'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'a': 0}}), ({'nodes': [['c', None, None], ['a', 'b', 'c'], ['b', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'c': 1, 'a': 0, 'b': 1}}), ({'nodes': [['a', None, 'b'], ['b', None, None], ['c', None, None]], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': ['c'], 'repeated': [], 'complete': False, 'right_only': ['a'], 'incoming': {'a': 0, 'b': 1, 'c': 0}}), ({'nodes': [['a', 'b', 'b'], ['b', 'a', 'a']], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': [], 'repeated': ['b', 'a', 'a'], 'complete': False, 'right_only': [], 'incoming': {'a': 2, 'b': 2}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': [], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None], ['100', None, None], ['101', None, None], ['102', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': ['100', '101', '102'], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1, '100': 0, '101': 0, '102': 0}})], [({'nodes': [], 'root': None}, {'visits': [], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {}}), ({'nodes': [['a', None, None]], 'root': 'a'}, {'visits': ['a'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'a': 0}}), ({'nodes': [['c', None, None], ['a', 'b', 'c'], ['b', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'c': 1, 'a': 0, 'b': 1}}), ({'nodes': [['a', None, 'b'], ['b', None, None], ['c', None, None]], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': ['c'], 'repeated': [], 'complete': False, 'right_only': ['a'], 'incoming': {'a': 0, 'b': 1, 'c': 0}}), ({'nodes': [['a', 'b', 'b'], ['b', 'a', 'a']], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': [], 'repeated': ['b', 'a', 'a'], 'complete': False, 'right_only': [], 'incoming': {'a': 2, 'b': 2}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': [], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None], ['100', None, None], ['101', None, None], ['102', None, None], ['103', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': ['100', '101', '102', '103'], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1, '100': 0, '101': 0, '102': 0, '103': 0}})], [({'nodes': [], 'root': None}, {'visits': [], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {}}), ({'nodes': [['a', None, None]], 'root': 'a'}, {'visits': ['a'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'a': 0}}), ({'nodes': [['c', None, None], ['a', 'b', 'c'], ['b', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'c': 1, 'a': 0, 'b': 1}}), ({'nodes': [['a', None, 'b'], ['b', None, None], ['c', None, None]], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': ['c'], 'repeated': [], 'complete': False, 'right_only': ['a'], 'incoming': {'a': 0, 'b': 1, 'c': 0}}), ({'nodes': [['a', 'b', 'b'], ['b', 'a', 'a']], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': [], 'repeated': ['b', 'a', 'a'], 'complete': False, 'right_only': [], 'incoming': {'a': 2, 'b': 2}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': [], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None], ['100', None, None], ['101', None, None], ['102', None, None], ['103', None, None], ['104', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': ['100', '101', '102', '103', '104'], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1, '100': 0, '101': 0, '102': 0, '103': 0, '104': 0}})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
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(d):
    nodes={x[0]:x[1:] for x in d['nodes']}; root=d['root']; todo=[] if root is None else [(root,0)]; seen=[]; indices=[]; repeated=[]
    while todo:
        v,k=todo.pop(0)
        if v in seen:
            repeated.append(v); continue
        seen.append(v); indices.append(k)
        for offset,child in enumerate(nodes[v],1):
            if child is not None: todo.append((child,2*k+offset))
    return {'visits': seen,
    'unreachable': sorted(set(nodes)-set(seen)),
    'repeated': repeated,
    'complete': not repeated and len(seen)==len(nodes) and sorted(indices)==list(range(len(nodes))),
    'right_only': [v for v,(l,r) in nodes.items() if l is None and r is not None],
    'incoming': {v:sum(v in pair for pair in nodes.values()) for v in nodes}}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'nodes': [], 'root': None}, {'visits': [], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {}}), ({'nodes': [['a', None, None]], 'root': 'a'}, {'visits': ['a'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'a': 0}}), ({'nodes': [['c', None, None], ['a', 'b', 'c'], ['b', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'c': 1, 'a': 0, 'b': 1}}), ({'nodes': [['a', None, 'b'], ['b', None, None], ['c', None, None]], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': ['c'], 'repeated': [], 'complete': False, 'right_only': ['a'], 'incoming': {'a': 0, 'b': 1, 'c': 0}}), ({'nodes': [['a', 'b', 'b'], ['b', 'a', 'a']], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': [], 'repeated': ['b', 'a', 'a'], 'complete': False, 'right_only': [], 'incoming': {'a': 2, 'b': 2}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': [], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None], ['100', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': ['100'], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1, '100': 0}})], [({'nodes': [], 'root': None}, {'visits': [], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {}}), ({'nodes': [['a', None, None]], 'root': 'a'}, {'visits': ['a'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'a': 0}}), ({'nodes': [['c', None, None], ['a', 'b', 'c'], ['b', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'c': 1, 'a': 0, 'b': 1}}), ({'nodes': [['a', None, 'b'], ['b', None, None], ['c', None, None]], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': ['c'], 'repeated': [], 'complete': False, 'right_only': ['a'], 'incoming': {'a': 0, 'b': 1, 'c': 0}}), ({'nodes': [['a', 'b', 'b'], ['b', 'a', 'a']], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': [], 'repeated': ['b', 'a', 'a'], 'complete': False, 'right_only': [], 'incoming': {'a': 2, 'b': 2}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': [], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None], ['100', None, None], ['101', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': ['100', '101'], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1, '100': 0, '101': 0}})], [({'nodes': [], 'root': None}, {'visits': [], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {}}), ({'nodes': [['a', None, None]], 'root': 'a'}, {'visits': ['a'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'a': 0}}), ({'nodes': [['c', None, None], ['a', 'b', 'c'], ['b', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'c': 1, 'a': 0, 'b': 1}}), ({'nodes': [['a', None, 'b'], ['b', None, None], ['c', None, None]], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': ['c'], 'repeated': [], 'complete': False, 'right_only': ['a'], 'incoming': {'a': 0, 'b': 1, 'c': 0}}), ({'nodes': [['a', 'b', 'b'], ['b', 'a', 'a']], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': [], 'repeated': ['b', 'a', 'a'], 'complete': False, 'right_only': [], 'incoming': {'a': 2, 'b': 2}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': [], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None], ['100', None, None], ['101', None, None], ['102', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': ['100', '101', '102'], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1, '100': 0, '101': 0, '102': 0}})], [({'nodes': [], 'root': None}, {'visits': [], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {}}), ({'nodes': [['a', None, None]], 'root': 'a'}, {'visits': ['a'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'a': 0}}), ({'nodes': [['c', None, None], ['a', 'b', 'c'], ['b', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'c': 1, 'a': 0, 'b': 1}}), ({'nodes': [['a', None, 'b'], ['b', None, None], ['c', None, None]], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': ['c'], 'repeated': [], 'complete': False, 'right_only': ['a'], 'incoming': {'a': 0, 'b': 1, 'c': 0}}), ({'nodes': [['a', 'b', 'b'], ['b', 'a', 'a']], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': [], 'repeated': ['b', 'a', 'a'], 'complete': False, 'right_only': [], 'incoming': {'a': 2, 'b': 2}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': [], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None], ['100', None, None], ['101', None, None], ['102', None, None], ['103', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': ['100', '101', '102', '103'], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1, '100': 0, '101': 0, '102': 0, '103': 0}})], [({'nodes': [], 'root': None}, {'visits': [], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {}}), ({'nodes': [['a', None, None]], 'root': 'a'}, {'visits': ['a'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'a': 0}}), ({'nodes': [['c', None, None], ['a', 'b', 'c'], ['b', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c'], 'unreachable': [], 'repeated': [], 'complete': True, 'right_only': [], 'incoming': {'c': 1, 'a': 0, 'b': 1}}), ({'nodes': [['a', None, 'b'], ['b', None, None], ['c', None, None]], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': ['c'], 'repeated': [], 'complete': False, 'right_only': ['a'], 'incoming': {'a': 0, 'b': 1, 'c': 0}}), ({'nodes': [['a', 'b', 'b'], ['b', 'a', 'a']], 'root': 'a'}, {'visits': ['a', 'b'], 'unreachable': [], 'repeated': ['b', 'a', 'a'], 'complete': False, 'right_only': [], 'incoming': {'a': 2, 'b': 2}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': [], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1}}), ({'nodes': [['a', 'b', 'c'], ['b', None, 'd'], ['c', None, None], ['d', None, None], ['100', None, None], ['101', None, None], ['102', None, None], ['103', None, None], ['104', None, None]], 'root': 'a'}, {'visits': ['a', 'b', 'c', 'd'], 'unreachable': ['100', '101', '102', '103', '104'], 'repeated': [], 'complete': False, 'right_only': ['b'], 'incoming': {'a': 0, 'b': 1, 'c': 1, 'd': 1, '100': 0, '101': 0, '102': 0, '103': 0, '104': 0}})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
The bounded complete tree certificate certificate reports an incorrect incoming.

A bounded binary pointer-tree certificate gives node records [id,left_id,right_id], root id or None; references name existing nodes or None. Breadth-first traversal stops expanding previously seen ids. Assign conceptual heap indices root=0,left=2i+1,right=2i+2. Report visit ids, unreachable ids, shared/cyclic references encountered, completeness (unique indices 0..n-1 and all nodes reached without repeats), right-only parents, and parent multiplicities.

split: open-access


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

N = 1
observations = []
def solve(d):
    a=d['leaves']; m=len(a); c=1
    while c<m: c*=2
    padded=a+[None]*(c-m); champion=min(range(m),key=lambda i:a[i][1]) if m else None
    return {'capacity': max(1,m),
    'leaves': padded,
    'champion': None if champion is None else a[champion][0],
    'rounds': c.bit_length()-1,
    'active_indices': list(range(m)),
    'key_comparisons': max(0,m-1)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], None, None], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5], 'key_comparisons': 5})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], None], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5, 6], 'key_comparisons': 6})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2]], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7], 'key_comparisons': 7})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3]]}, {'capacity': 16, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], None, None, None, None, None, None, None], 'champion': '100', 'rounds': 4, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7, 8], 'key_comparisons': 8})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], ['104', 4]]}, {'capacity': 16, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], ['104', 4], None, None, None, None, None, None], 'champion': '100', 'rounds': 4, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 'key_comparisons': 9})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
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(d):
    a=d['leaves']; m=len(a); c=1
    while c<m: c*=2
    padded=a+[None]*(c-m); champion=min(range(m),key=lambda i:a[i][1]) if m else None
    return {'capacity': 1<<m.bit_length(),
    'leaves': padded,
    'champion': None if champion is None else a[champion][0],
    'rounds': c.bit_length()-1,
    'active_indices': list(range(m)),
    'key_comparisons': max(0,m-1)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], None, None], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5], 'key_comparisons': 5})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], None], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5, 6], 'key_comparisons': 6})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2]], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7], 'key_comparisons': 7})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3]]}, {'capacity': 16, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], None, None, None, None, None, None, None], 'champion': '100', 'rounds': 4, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7, 8], 'key_comparisons': 8})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], ['104', 4]]}, {'capacity': 16, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], ['104', 4], None, None, None, None, None, None], 'champion': '100', 'rounds': 4, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 'key_comparisons': 9})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
The bounded tournament padding certificate reports an incorrect capacity.

A tournament is built from m real leaves [id,key]. Round leaf capacity to the next power of two (empty capacity one) and append inactive None pads. Inactive pads always lose without numeric sentinel assumptions. Report capacity, padded leaves, champion id with arrival-order ties, match rounds, active-leaf indices, and key-comparison count m-1 for m>0.

split: open-access


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

N = 1
observations = []
def solve(d):
    a=d['leaves']; m=len(a); c=1
    while c<m: c*=2
    padded=a+[None]*(c-m); champion=min(range(m),key=lambda i:a[i][1]) if m else None
    return {'capacity': c,
    'leaves': a+[["pad",0]]*(c-m),
    'champion': None if champion is None else a[champion][0],
    'rounds': c.bit_length()-1,
    'active_indices': list(range(m)),
    'key_comparisons': max(0,m-1)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], None, None], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5], 'key_comparisons': 5})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], None], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5, 6], 'key_comparisons': 6})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2]], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7], 'key_comparisons': 7})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3]]}, {'capacity': 16, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], None, None, None, None, None, None, None], 'champion': '100', 'rounds': 4, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7, 8], 'key_comparisons': 8})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], ['104', 4]]}, {'capacity': 16, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], ['104', 4], None, None, None, None, None, None], 'champion': '100', 'rounds': 4, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 'key_comparisons': 9})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
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(d):
    a=d['leaves']; m=len(a); c=1
    while c<m: c*=2
    padded=a+[None]*(c-m); champion=min(range(m),key=lambda i:a[i][1]) if m else None
    return {'capacity': c,
    'leaves': [None]*(c-m)+a,
    'champion': None if champion is None else a[champion][0],
    'rounds': c.bit_length()-1,
    'active_indices': list(range(m)),
    'key_comparisons': max(0,m-1)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], None, None], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5], 'key_comparisons': 5})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], None], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5, 6], 'key_comparisons': 6})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2]], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7], 'key_comparisons': 7})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3]]}, {'capacity': 16, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], None, None, None, None, None, None, None], 'champion': '100', 'rounds': 4, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7, 8], 'key_comparisons': 8})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], ['104', 4]]}, {'capacity': 16, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], ['104', 4], None, None, None, None, None, None], 'champion': '100', 'rounds': 4, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 'key_comparisons': 9})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
The bounded tournament padding certificate reports an incorrect leaves.

A tournament is built from m real leaves [id,key]. Round leaf capacity to the next power of two (empty capacity one) and append inactive None pads. Inactive pads always lose without numeric sentinel assumptions. Report capacity, padded leaves, champion id with arrival-order ties, match rounds, active-leaf indices, and key-comparison count m-1 for m>0.

split: open-access