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

N = 1
observations = []
def solve(d):
    table={int(k):v for k,v in d['table'].items()}; start=d['degree']; degree=start; collisions=[]
    while degree in table:
        collisions.append(table[degree]); degree+=1
    out={k:v for k,v in table.items() if not start<=k<degree}; out[degree]=d['root']
    return {'collisions': collisions,
    'final_degree': degree,
    'cleared': list(range(start,degree+1)),
    'occupied': sorted(out),
    'capacity': max(out,default=-1)+1,
    'carry_steps': len(collisions)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'table': {}, 'degree': 0, 'root': 'x'}, {'collisions': [], 'final_degree': 0, 'cleared': [], 'occupied': [0], 'capacity': 1, 'carry_steps': 0}), ({'table': {'0': 'a'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a'], 'final_degree': 1, 'cleared': [0], 'occupied': [1], 'capacity': 2, 'carry_steps': 1}), ({'table': {'0': 'a', '1': 'b', '3': 'c'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a', 'b'], 'final_degree': 2, 'cleared': [0, 1], 'occupied': [2, 3], 'capacity': 4, 'carry_steps': 2}), ({'table': {'0': 'a', '2': 'b', '3': 'c'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [0, 4], 'capacity': 5, 'carry_steps': 2}), ({'table': {'4': 'a'}, 'degree': 1, 'root': 'x'}, {'collisions': [], 'final_degree': 1, 'cleared': [], 'occupied': [1, 4], 'capacity': 5, 'carry_steps': 0}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3})], [({'table': {}, 'degree': 0, 'root': 'x'}, {'collisions': [], 'final_degree': 0, 'cleared': [], 'occupied': [0], 'capacity': 1, 'carry_steps': 0}), ({'table': {'0': 'a'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a'], 'final_degree': 1, 'cleared': [0], 'occupied': [1], 'capacity': 2, 'carry_steps': 1}), ({'table': {'0': 'a', '1': 'b', '3': 'c'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a', 'b'], 'final_degree': 2, 'cleared': [0, 1], 'occupied': [2, 3], 'capacity': 4, 'carry_steps': 2}), ({'table': {'0': 'a', '2': 'b', '3': 'c'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [0, 4], 'capacity': 5, 'carry_steps': 2}), ({'table': {'4': 'a'}, 'degree': 1, 'root': 'x'}, {'collisions': [], 'final_degree': 1, 'cleared': [], 'occupied': [1, 4], 'capacity': 5, 'carry_steps': 0}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [1, 4, 6], 'capacity': 7, 'carry_steps': 2})], [({'table': {}, 'degree': 0, 'root': 'x'}, {'collisions': [], 'final_degree': 0, 'cleared': [], 'occupied': [0], 'capacity': 1, 'carry_steps': 0}), ({'table': {'0': 'a'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a'], 'final_degree': 1, 'cleared': [0], 'occupied': [1], 'capacity': 2, 'carry_steps': 1}), ({'table': {'0': 'a', '1': 'b', '3': 'c'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a', 'b'], 'final_degree': 2, 'cleared': [0, 1], 'occupied': [2, 3], 'capacity': 4, 'carry_steps': 2}), ({'table': {'0': 'a', '2': 'b', '3': 'c'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [0, 4], 'capacity': 5, 'carry_steps': 2}), ({'table': {'4': 'a'}, 'degree': 1, 'root': 'x'}, {'collisions': [], 'final_degree': 1, 'cleared': [], 'occupied': [1, 4], 'capacity': 5, 'carry_steps': 0}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 3, 'root': 'x'}, {'collisions': ['c'], 'final_degree': 4, 'cleared': [3], 'occupied': [1, 2, 4, 6], 'capacity': 7, 'carry_steps': 1})], [({'table': {}, 'degree': 0, 'root': 'x'}, {'collisions': [], 'final_degree': 0, 'cleared': [], 'occupied': [0], 'capacity': 1, 'carry_steps': 0}), ({'table': {'0': 'a'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a'], 'final_degree': 1, 'cleared': [0], 'occupied': [1], 'capacity': 2, 'carry_steps': 1}), ({'table': {'0': 'a', '1': 'b', '3': 'c'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a', 'b'], 'final_degree': 2, 'cleared': [0, 1], 'occupied': [2, 3], 'capacity': 4, 'carry_steps': 2}), ({'table': {'0': 'a', '2': 'b', '3': 'c'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [0, 4], 'capacity': 5, 'carry_steps': 2}), ({'table': {'4': 'a'}, 'degree': 1, 'root': 'x'}, {'collisions': [], 'final_degree': 1, 'cleared': [], 'occupied': [1, 4], 'capacity': 5, 'carry_steps': 0}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 4, 'root': 'x'}, {'collisions': [], 'final_degree': 4, 'cleared': [], 'occupied': [1, 2, 3, 4, 6], 'capacity': 7, 'carry_steps': 0})], [({'table': {}, 'degree': 0, 'root': 'x'}, {'collisions': [], 'final_degree': 0, 'cleared': [], 'occupied': [0], 'capacity': 1, 'carry_steps': 0}), ({'table': {'0': 'a'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a'], 'final_degree': 1, 'cleared': [0], 'occupied': [1], 'capacity': 2, 'carry_steps': 1}), ({'table': {'0': 'a', '1': 'b', '3': 'c'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a', 'b'], 'final_degree': 2, 'cleared': [0, 1], 'occupied': [2, 3], 'capacity': 4, 'carry_steps': 2}), ({'table': {'0': 'a', '2': 'b', '3': 'c'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [0, 4], 'capacity': 5, 'carry_steps': 2}), ({'table': {'4': 'a'}, 'degree': 1, 'root': 'x'}, {'collisions': [], 'final_degree': 1, 'cleared': [], 'occupied': [1, 4], 'capacity': 5, 'carry_steps': 0}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 5, 'root': 'x'}, {'collisions': [], 'final_degree': 5, 'cleared': [], 'occupied': [1, 2, 3, 5, 6], 'capacity': 7, 'carry_steps': 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):
    table={int(k):v for k,v in d['table'].items()}; start=d['degree']; degree=start; collisions=[]
    while degree in table:
        collisions.append(table[degree]); degree+=1
    out={k:v for k,v in table.items() if not start<=k<degree}; out[degree]=d['root']
    return {'collisions': collisions,
    'final_degree': degree,
    'cleared': [],
    'occupied': sorted(out),
    'capacity': max(out,default=-1)+1,
    'carry_steps': len(collisions)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'table': {}, 'degree': 0, 'root': 'x'}, {'collisions': [], 'final_degree': 0, 'cleared': [], 'occupied': [0], 'capacity': 1, 'carry_steps': 0}), ({'table': {'0': 'a'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a'], 'final_degree': 1, 'cleared': [0], 'occupied': [1], 'capacity': 2, 'carry_steps': 1}), ({'table': {'0': 'a', '1': 'b', '3': 'c'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a', 'b'], 'final_degree': 2, 'cleared': [0, 1], 'occupied': [2, 3], 'capacity': 4, 'carry_steps': 2}), ({'table': {'0': 'a', '2': 'b', '3': 'c'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [0, 4], 'capacity': 5, 'carry_steps': 2}), ({'table': {'4': 'a'}, 'degree': 1, 'root': 'x'}, {'collisions': [], 'final_degree': 1, 'cleared': [], 'occupied': [1, 4], 'capacity': 5, 'carry_steps': 0}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3})], [({'table': {}, 'degree': 0, 'root': 'x'}, {'collisions': [], 'final_degree': 0, 'cleared': [], 'occupied': [0], 'capacity': 1, 'carry_steps': 0}), ({'table': {'0': 'a'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a'], 'final_degree': 1, 'cleared': [0], 'occupied': [1], 'capacity': 2, 'carry_steps': 1}), ({'table': {'0': 'a', '1': 'b', '3': 'c'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a', 'b'], 'final_degree': 2, 'cleared': [0, 1], 'occupied': [2, 3], 'capacity': 4, 'carry_steps': 2}), ({'table': {'0': 'a', '2': 'b', '3': 'c'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [0, 4], 'capacity': 5, 'carry_steps': 2}), ({'table': {'4': 'a'}, 'degree': 1, 'root': 'x'}, {'collisions': [], 'final_degree': 1, 'cleared': [], 'occupied': [1, 4], 'capacity': 5, 'carry_steps': 0}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [1, 4, 6], 'capacity': 7, 'carry_steps': 2})], [({'table': {}, 'degree': 0, 'root': 'x'}, {'collisions': [], 'final_degree': 0, 'cleared': [], 'occupied': [0], 'capacity': 1, 'carry_steps': 0}), ({'table': {'0': 'a'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a'], 'final_degree': 1, 'cleared': [0], 'occupied': [1], 'capacity': 2, 'carry_steps': 1}), ({'table': {'0': 'a', '1': 'b', '3': 'c'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a', 'b'], 'final_degree': 2, 'cleared': [0, 1], 'occupied': [2, 3], 'capacity': 4, 'carry_steps': 2}), ({'table': {'0': 'a', '2': 'b', '3': 'c'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [0, 4], 'capacity': 5, 'carry_steps': 2}), ({'table': {'4': 'a'}, 'degree': 1, 'root': 'x'}, {'collisions': [], 'final_degree': 1, 'cleared': [], 'occupied': [1, 4], 'capacity': 5, 'carry_steps': 0}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 3, 'root': 'x'}, {'collisions': ['c'], 'final_degree': 4, 'cleared': [3], 'occupied': [1, 2, 4, 6], 'capacity': 7, 'carry_steps': 1})], [({'table': {}, 'degree': 0, 'root': 'x'}, {'collisions': [], 'final_degree': 0, 'cleared': [], 'occupied': [0], 'capacity': 1, 'carry_steps': 0}), ({'table': {'0': 'a'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a'], 'final_degree': 1, 'cleared': [0], 'occupied': [1], 'capacity': 2, 'carry_steps': 1}), ({'table': {'0': 'a', '1': 'b', '3': 'c'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a', 'b'], 'final_degree': 2, 'cleared': [0, 1], 'occupied': [2, 3], 'capacity': 4, 'carry_steps': 2}), ({'table': {'0': 'a', '2': 'b', '3': 'c'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [0, 4], 'capacity': 5, 'carry_steps': 2}), ({'table': {'4': 'a'}, 'degree': 1, 'root': 'x'}, {'collisions': [], 'final_degree': 1, 'cleared': [], 'occupied': [1, 4], 'capacity': 5, 'carry_steps': 0}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 4, 'root': 'x'}, {'collisions': [], 'final_degree': 4, 'cleared': [], 'occupied': [1, 2, 3, 4, 6], 'capacity': 7, 'carry_steps': 0})], [({'table': {}, 'degree': 0, 'root': 'x'}, {'collisions': [], 'final_degree': 0, 'cleared': [], 'occupied': [0], 'capacity': 1, 'carry_steps': 0}), ({'table': {'0': 'a'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a'], 'final_degree': 1, 'cleared': [0], 'occupied': [1], 'capacity': 2, 'carry_steps': 1}), ({'table': {'0': 'a', '1': 'b', '3': 'c'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a', 'b'], 'final_degree': 2, 'cleared': [0, 1], 'occupied': [2, 3], 'capacity': 4, 'carry_steps': 2}), ({'table': {'0': 'a', '2': 'b', '3': 'c'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [0, 4], 'capacity': 5, 'carry_steps': 2}), ({'table': {'4': 'a'}, 'degree': 1, 'root': 'x'}, {'collisions': [], 'final_degree': 1, 'cleared': [], 'occupied': [1, 4], 'capacity': 5, 'carry_steps': 0}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 5, 'root': 'x'}, {'collisions': [], 'final_degree': 5, 'cleared': [], 'occupied': [1, 2, 3, 5, 6], 'capacity': 7, 'carry_steps': 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 fibonacci degree table certificate reports an incorrect cleared.

A Fibonacci consolidation trace gives occupied degree slots table degree->root id, incoming degree, and incoming root. Pop consecutive occupied degrees starting at incoming degree, collecting collision roots, then place incoming representative in first vacant slot. Report collisions, final degree, emptied slots, resulting occupied degree keys, required array capacity, and carry-step count. This is the degree-routing portion; key comparisons are outside this bounded model.

split: open-access


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

N = 1
observations = []
def solve(d):
    table={int(k):v for k,v in d['table'].items()}; start=d['degree']; degree=start; collisions=[]
    while degree in table:
        collisions.append(table[degree]); degree+=1
    out={k:v for k,v in table.items() if not start<=k<degree}; out[degree]=d['root']
    return {'collisions': collisions,
    'final_degree': degree,
    'cleared': list(range(start,degree)),
    'occupied': sorted(set(table)|{degree}),
    'capacity': max(out,default=-1)+1,
    'carry_steps': len(collisions)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'table': {}, 'degree': 0, 'root': 'x'}, {'collisions': [], 'final_degree': 0, 'cleared': [], 'occupied': [0], 'capacity': 1, 'carry_steps': 0}), ({'table': {'0': 'a'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a'], 'final_degree': 1, 'cleared': [0], 'occupied': [1], 'capacity': 2, 'carry_steps': 1}), ({'table': {'0': 'a', '1': 'b', '3': 'c'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a', 'b'], 'final_degree': 2, 'cleared': [0, 1], 'occupied': [2, 3], 'capacity': 4, 'carry_steps': 2}), ({'table': {'0': 'a', '2': 'b', '3': 'c'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [0, 4], 'capacity': 5, 'carry_steps': 2}), ({'table': {'4': 'a'}, 'degree': 1, 'root': 'x'}, {'collisions': [], 'final_degree': 1, 'cleared': [], 'occupied': [1, 4], 'capacity': 5, 'carry_steps': 0}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3})], [({'table': {}, 'degree': 0, 'root': 'x'}, {'collisions': [], 'final_degree': 0, 'cleared': [], 'occupied': [0], 'capacity': 1, 'carry_steps': 0}), ({'table': {'0': 'a'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a'], 'final_degree': 1, 'cleared': [0], 'occupied': [1], 'capacity': 2, 'carry_steps': 1}), ({'table': {'0': 'a', '1': 'b', '3': 'c'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a', 'b'], 'final_degree': 2, 'cleared': [0, 1], 'occupied': [2, 3], 'capacity': 4, 'carry_steps': 2}), ({'table': {'0': 'a', '2': 'b', '3': 'c'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [0, 4], 'capacity': 5, 'carry_steps': 2}), ({'table': {'4': 'a'}, 'degree': 1, 'root': 'x'}, {'collisions': [], 'final_degree': 1, 'cleared': [], 'occupied': [1, 4], 'capacity': 5, 'carry_steps': 0}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [1, 4, 6], 'capacity': 7, 'carry_steps': 2})], [({'table': {}, 'degree': 0, 'root': 'x'}, {'collisions': [], 'final_degree': 0, 'cleared': [], 'occupied': [0], 'capacity': 1, 'carry_steps': 0}), ({'table': {'0': 'a'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a'], 'final_degree': 1, 'cleared': [0], 'occupied': [1], 'capacity': 2, 'carry_steps': 1}), ({'table': {'0': 'a', '1': 'b', '3': 'c'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a', 'b'], 'final_degree': 2, 'cleared': [0, 1], 'occupied': [2, 3], 'capacity': 4, 'carry_steps': 2}), ({'table': {'0': 'a', '2': 'b', '3': 'c'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [0, 4], 'capacity': 5, 'carry_steps': 2}), ({'table': {'4': 'a'}, 'degree': 1, 'root': 'x'}, {'collisions': [], 'final_degree': 1, 'cleared': [], 'occupied': [1, 4], 'capacity': 5, 'carry_steps': 0}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 3, 'root': 'x'}, {'collisions': ['c'], 'final_degree': 4, 'cleared': [3], 'occupied': [1, 2, 4, 6], 'capacity': 7, 'carry_steps': 1})], [({'table': {}, 'degree': 0, 'root': 'x'}, {'collisions': [], 'final_degree': 0, 'cleared': [], 'occupied': [0], 'capacity': 1, 'carry_steps': 0}), ({'table': {'0': 'a'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a'], 'final_degree': 1, 'cleared': [0], 'occupied': [1], 'capacity': 2, 'carry_steps': 1}), ({'table': {'0': 'a', '1': 'b', '3': 'c'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a', 'b'], 'final_degree': 2, 'cleared': [0, 1], 'occupied': [2, 3], 'capacity': 4, 'carry_steps': 2}), ({'table': {'0': 'a', '2': 'b', '3': 'c'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [0, 4], 'capacity': 5, 'carry_steps': 2}), ({'table': {'4': 'a'}, 'degree': 1, 'root': 'x'}, {'collisions': [], 'final_degree': 1, 'cleared': [], 'occupied': [1, 4], 'capacity': 5, 'carry_steps': 0}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 4, 'root': 'x'}, {'collisions': [], 'final_degree': 4, 'cleared': [], 'occupied': [1, 2, 3, 4, 6], 'capacity': 7, 'carry_steps': 0})], [({'table': {}, 'degree': 0, 'root': 'x'}, {'collisions': [], 'final_degree': 0, 'cleared': [], 'occupied': [0], 'capacity': 1, 'carry_steps': 0}), ({'table': {'0': 'a'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a'], 'final_degree': 1, 'cleared': [0], 'occupied': [1], 'capacity': 2, 'carry_steps': 1}), ({'table': {'0': 'a', '1': 'b', '3': 'c'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a', 'b'], 'final_degree': 2, 'cleared': [0, 1], 'occupied': [2, 3], 'capacity': 4, 'carry_steps': 2}), ({'table': {'0': 'a', '2': 'b', '3': 'c'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [0, 4], 'capacity': 5, 'carry_steps': 2}), ({'table': {'4': 'a'}, 'degree': 1, 'root': 'x'}, {'collisions': [], 'final_degree': 1, 'cleared': [], 'occupied': [1, 4], 'capacity': 5, 'carry_steps': 0}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 5, 'root': 'x'}, {'collisions': [], 'final_degree': 5, 'cleared': [], 'occupied': [1, 2, 3, 5, 6], 'capacity': 7, 'carry_steps': 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):
    table={int(k):v for k,v in d['table'].items()}; start=d['degree']; degree=start; collisions=[]
    while degree in table:
        collisions.append(table[degree]); degree+=1
    out={k:v for k,v in table.items() if not start<=k<degree}; out[degree]=d['root']
    return {'collisions': collisions,
    'final_degree': degree,
    'cleared': list(range(start,degree)),
    'occupied': [degree],
    'capacity': max(out,default=-1)+1,
    'carry_steps': len(collisions)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'table': {}, 'degree': 0, 'root': 'x'}, {'collisions': [], 'final_degree': 0, 'cleared': [], 'occupied': [0], 'capacity': 1, 'carry_steps': 0}), ({'table': {'0': 'a'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a'], 'final_degree': 1, 'cleared': [0], 'occupied': [1], 'capacity': 2, 'carry_steps': 1}), ({'table': {'0': 'a', '1': 'b', '3': 'c'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a', 'b'], 'final_degree': 2, 'cleared': [0, 1], 'occupied': [2, 3], 'capacity': 4, 'carry_steps': 2}), ({'table': {'0': 'a', '2': 'b', '3': 'c'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [0, 4], 'capacity': 5, 'carry_steps': 2}), ({'table': {'4': 'a'}, 'degree': 1, 'root': 'x'}, {'collisions': [], 'final_degree': 1, 'cleared': [], 'occupied': [1, 4], 'capacity': 5, 'carry_steps': 0}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3})], [({'table': {}, 'degree': 0, 'root': 'x'}, {'collisions': [], 'final_degree': 0, 'cleared': [], 'occupied': [0], 'capacity': 1, 'carry_steps': 0}), ({'table': {'0': 'a'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a'], 'final_degree': 1, 'cleared': [0], 'occupied': [1], 'capacity': 2, 'carry_steps': 1}), ({'table': {'0': 'a', '1': 'b', '3': 'c'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a', 'b'], 'final_degree': 2, 'cleared': [0, 1], 'occupied': [2, 3], 'capacity': 4, 'carry_steps': 2}), ({'table': {'0': 'a', '2': 'b', '3': 'c'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [0, 4], 'capacity': 5, 'carry_steps': 2}), ({'table': {'4': 'a'}, 'degree': 1, 'root': 'x'}, {'collisions': [], 'final_degree': 1, 'cleared': [], 'occupied': [1, 4], 'capacity': 5, 'carry_steps': 0}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [1, 4, 6], 'capacity': 7, 'carry_steps': 2})], [({'table': {}, 'degree': 0, 'root': 'x'}, {'collisions': [], 'final_degree': 0, 'cleared': [], 'occupied': [0], 'capacity': 1, 'carry_steps': 0}), ({'table': {'0': 'a'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a'], 'final_degree': 1, 'cleared': [0], 'occupied': [1], 'capacity': 2, 'carry_steps': 1}), ({'table': {'0': 'a', '1': 'b', '3': 'c'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a', 'b'], 'final_degree': 2, 'cleared': [0, 1], 'occupied': [2, 3], 'capacity': 4, 'carry_steps': 2}), ({'table': {'0': 'a', '2': 'b', '3': 'c'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [0, 4], 'capacity': 5, 'carry_steps': 2}), ({'table': {'4': 'a'}, 'degree': 1, 'root': 'x'}, {'collisions': [], 'final_degree': 1, 'cleared': [], 'occupied': [1, 4], 'capacity': 5, 'carry_steps': 0}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 3, 'root': 'x'}, {'collisions': ['c'], 'final_degree': 4, 'cleared': [3], 'occupied': [1, 2, 4, 6], 'capacity': 7, 'carry_steps': 1})], [({'table': {}, 'degree': 0, 'root': 'x'}, {'collisions': [], 'final_degree': 0, 'cleared': [], 'occupied': [0], 'capacity': 1, 'carry_steps': 0}), ({'table': {'0': 'a'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a'], 'final_degree': 1, 'cleared': [0], 'occupied': [1], 'capacity': 2, 'carry_steps': 1}), ({'table': {'0': 'a', '1': 'b', '3': 'c'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a', 'b'], 'final_degree': 2, 'cleared': [0, 1], 'occupied': [2, 3], 'capacity': 4, 'carry_steps': 2}), ({'table': {'0': 'a', '2': 'b', '3': 'c'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [0, 4], 'capacity': 5, 'carry_steps': 2}), ({'table': {'4': 'a'}, 'degree': 1, 'root': 'x'}, {'collisions': [], 'final_degree': 1, 'cleared': [], 'occupied': [1, 4], 'capacity': 5, 'carry_steps': 0}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 4, 'root': 'x'}, {'collisions': [], 'final_degree': 4, 'cleared': [], 'occupied': [1, 2, 3, 4, 6], 'capacity': 7, 'carry_steps': 0})], [({'table': {}, 'degree': 0, 'root': 'x'}, {'collisions': [], 'final_degree': 0, 'cleared': [], 'occupied': [0], 'capacity': 1, 'carry_steps': 0}), ({'table': {'0': 'a'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a'], 'final_degree': 1, 'cleared': [0], 'occupied': [1], 'capacity': 2, 'carry_steps': 1}), ({'table': {'0': 'a', '1': 'b', '3': 'c'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a', 'b'], 'final_degree': 2, 'cleared': [0, 1], 'occupied': [2, 3], 'capacity': 4, 'carry_steps': 2}), ({'table': {'0': 'a', '2': 'b', '3': 'c'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [0, 4], 'capacity': 5, 'carry_steps': 2}), ({'table': {'4': 'a'}, 'degree': 1, 'root': 'x'}, {'collisions': [], 'final_degree': 1, 'cleared': [], 'occupied': [1, 4], 'capacity': 5, 'carry_steps': 0}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 5, 'root': 'x'}, {'collisions': [], 'final_degree': 5, 'cleared': [], 'occupied': [1, 2, 3, 5, 6], 'capacity': 7, 'carry_steps': 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 fibonacci degree table certificate reports an incorrect occupied.

A Fibonacci consolidation trace gives occupied degree slots table degree->root id, incoming degree, and incoming root. Pop consecutive occupied degrees starting at incoming degree, collecting collision roots, then place incoming representative in first vacant slot. Report collisions, final degree, emptied slots, resulting occupied degree keys, required array capacity, and carry-step count. This is the degree-routing portion; key comparisons are outside this bounded model.

split: open-access


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

N = 1
observations = []
def solve(d):
    table={int(k):v for k,v in d['table'].items()}; start=d['degree']; degree=start; collisions=[]
    while degree in table:
        collisions.append(table[degree]); degree+=1
    out={k:v for k,v in table.items() if not start<=k<degree}; out[degree]=d['root']
    return {'collisions': collisions,
    'final_degree': degree,
    'cleared': list(range(start,degree)),
    'occupied': sorted(out),
    'capacity': len(out),
    'carry_steps': len(collisions)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'table': {}, 'degree': 0, 'root': 'x'}, {'collisions': [], 'final_degree': 0, 'cleared': [], 'occupied': [0], 'capacity': 1, 'carry_steps': 0}), ({'table': {'0': 'a'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a'], 'final_degree': 1, 'cleared': [0], 'occupied': [1], 'capacity': 2, 'carry_steps': 1}), ({'table': {'0': 'a', '1': 'b', '3': 'c'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a', 'b'], 'final_degree': 2, 'cleared': [0, 1], 'occupied': [2, 3], 'capacity': 4, 'carry_steps': 2}), ({'table': {'0': 'a', '2': 'b', '3': 'c'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [0, 4], 'capacity': 5, 'carry_steps': 2}), ({'table': {'4': 'a'}, 'degree': 1, 'root': 'x'}, {'collisions': [], 'final_degree': 1, 'cleared': [], 'occupied': [1, 4], 'capacity': 5, 'carry_steps': 0}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3})], [({'table': {}, 'degree': 0, 'root': 'x'}, {'collisions': [], 'final_degree': 0, 'cleared': [], 'occupied': [0], 'capacity': 1, 'carry_steps': 0}), ({'table': {'0': 'a'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a'], 'final_degree': 1, 'cleared': [0], 'occupied': [1], 'capacity': 2, 'carry_steps': 1}), ({'table': {'0': 'a', '1': 'b', '3': 'c'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a', 'b'], 'final_degree': 2, 'cleared': [0, 1], 'occupied': [2, 3], 'capacity': 4, 'carry_steps': 2}), ({'table': {'0': 'a', '2': 'b', '3': 'c'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [0, 4], 'capacity': 5, 'carry_steps': 2}), ({'table': {'4': 'a'}, 'degree': 1, 'root': 'x'}, {'collisions': [], 'final_degree': 1, 'cleared': [], 'occupied': [1, 4], 'capacity': 5, 'carry_steps': 0}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [1, 4, 6], 'capacity': 7, 'carry_steps': 2})], [({'table': {}, 'degree': 0, 'root': 'x'}, {'collisions': [], 'final_degree': 0, 'cleared': [], 'occupied': [0], 'capacity': 1, 'carry_steps': 0}), ({'table': {'0': 'a'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a'], 'final_degree': 1, 'cleared': [0], 'occupied': [1], 'capacity': 2, 'carry_steps': 1}), ({'table': {'0': 'a', '1': 'b', '3': 'c'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a', 'b'], 'final_degree': 2, 'cleared': [0, 1], 'occupied': [2, 3], 'capacity': 4, 'carry_steps': 2}), ({'table': {'0': 'a', '2': 'b', '3': 'c'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [0, 4], 'capacity': 5, 'carry_steps': 2}), ({'table': {'4': 'a'}, 'degree': 1, 'root': 'x'}, {'collisions': [], 'final_degree': 1, 'cleared': [], 'occupied': [1, 4], 'capacity': 5, 'carry_steps': 0}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 3, 'root': 'x'}, {'collisions': ['c'], 'final_degree': 4, 'cleared': [3], 'occupied': [1, 2, 4, 6], 'capacity': 7, 'carry_steps': 1})], [({'table': {}, 'degree': 0, 'root': 'x'}, {'collisions': [], 'final_degree': 0, 'cleared': [], 'occupied': [0], 'capacity': 1, 'carry_steps': 0}), ({'table': {'0': 'a'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a'], 'final_degree': 1, 'cleared': [0], 'occupied': [1], 'capacity': 2, 'carry_steps': 1}), ({'table': {'0': 'a', '1': 'b', '3': 'c'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a', 'b'], 'final_degree': 2, 'cleared': [0, 1], 'occupied': [2, 3], 'capacity': 4, 'carry_steps': 2}), ({'table': {'0': 'a', '2': 'b', '3': 'c'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [0, 4], 'capacity': 5, 'carry_steps': 2}), ({'table': {'4': 'a'}, 'degree': 1, 'root': 'x'}, {'collisions': [], 'final_degree': 1, 'cleared': [], 'occupied': [1, 4], 'capacity': 5, 'carry_steps': 0}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 4, 'root': 'x'}, {'collisions': [], 'final_degree': 4, 'cleared': [], 'occupied': [1, 2, 3, 4, 6], 'capacity': 7, 'carry_steps': 0})], [({'table': {}, 'degree': 0, 'root': 'x'}, {'collisions': [], 'final_degree': 0, 'cleared': [], 'occupied': [0], 'capacity': 1, 'carry_steps': 0}), ({'table': {'0': 'a'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a'], 'final_degree': 1, 'cleared': [0], 'occupied': [1], 'capacity': 2, 'carry_steps': 1}), ({'table': {'0': 'a', '1': 'b', '3': 'c'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a', 'b'], 'final_degree': 2, 'cleared': [0, 1], 'occupied': [2, 3], 'capacity': 4, 'carry_steps': 2}), ({'table': {'0': 'a', '2': 'b', '3': 'c'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [0, 4], 'capacity': 5, 'carry_steps': 2}), ({'table': {'4': 'a'}, 'degree': 1, 'root': 'x'}, {'collisions': [], 'final_degree': 1, 'cleared': [], 'occupied': [1, 4], 'capacity': 5, 'carry_steps': 0}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 5, 'root': 'x'}, {'collisions': [], 'final_degree': 5, 'cleared': [], 'occupied': [1, 2, 3, 5, 6], 'capacity': 7, 'carry_steps': 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):
    table={int(k):v for k,v in d['table'].items()}; start=d['degree']; degree=start; collisions=[]
    while degree in table:
        collisions.append(table[degree]); degree+=1
    out={k:v for k,v in table.items() if not start<=k<degree}; out[degree]=d['root']
    return {'collisions': collisions,
    'final_degree': degree,
    'cleared': list(range(start,degree)),
    'occupied': sorted(out),
    'capacity': max(out,default=0),
    'carry_steps': len(collisions)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'table': {}, 'degree': 0, 'root': 'x'}, {'collisions': [], 'final_degree': 0, 'cleared': [], 'occupied': [0], 'capacity': 1, 'carry_steps': 0}), ({'table': {'0': 'a'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a'], 'final_degree': 1, 'cleared': [0], 'occupied': [1], 'capacity': 2, 'carry_steps': 1}), ({'table': {'0': 'a', '1': 'b', '3': 'c'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a', 'b'], 'final_degree': 2, 'cleared': [0, 1], 'occupied': [2, 3], 'capacity': 4, 'carry_steps': 2}), ({'table': {'0': 'a', '2': 'b', '3': 'c'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [0, 4], 'capacity': 5, 'carry_steps': 2}), ({'table': {'4': 'a'}, 'degree': 1, 'root': 'x'}, {'collisions': [], 'final_degree': 1, 'cleared': [], 'occupied': [1, 4], 'capacity': 5, 'carry_steps': 0}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3})], [({'table': {}, 'degree': 0, 'root': 'x'}, {'collisions': [], 'final_degree': 0, 'cleared': [], 'occupied': [0], 'capacity': 1, 'carry_steps': 0}), ({'table': {'0': 'a'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a'], 'final_degree': 1, 'cleared': [0], 'occupied': [1], 'capacity': 2, 'carry_steps': 1}), ({'table': {'0': 'a', '1': 'b', '3': 'c'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a', 'b'], 'final_degree': 2, 'cleared': [0, 1], 'occupied': [2, 3], 'capacity': 4, 'carry_steps': 2}), ({'table': {'0': 'a', '2': 'b', '3': 'c'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [0, 4], 'capacity': 5, 'carry_steps': 2}), ({'table': {'4': 'a'}, 'degree': 1, 'root': 'x'}, {'collisions': [], 'final_degree': 1, 'cleared': [], 'occupied': [1, 4], 'capacity': 5, 'carry_steps': 0}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [1, 4, 6], 'capacity': 7, 'carry_steps': 2})], [({'table': {}, 'degree': 0, 'root': 'x'}, {'collisions': [], 'final_degree': 0, 'cleared': [], 'occupied': [0], 'capacity': 1, 'carry_steps': 0}), ({'table': {'0': 'a'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a'], 'final_degree': 1, 'cleared': [0], 'occupied': [1], 'capacity': 2, 'carry_steps': 1}), ({'table': {'0': 'a', '1': 'b', '3': 'c'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a', 'b'], 'final_degree': 2, 'cleared': [0, 1], 'occupied': [2, 3], 'capacity': 4, 'carry_steps': 2}), ({'table': {'0': 'a', '2': 'b', '3': 'c'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [0, 4], 'capacity': 5, 'carry_steps': 2}), ({'table': {'4': 'a'}, 'degree': 1, 'root': 'x'}, {'collisions': [], 'final_degree': 1, 'cleared': [], 'occupied': [1, 4], 'capacity': 5, 'carry_steps': 0}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 3, 'root': 'x'}, {'collisions': ['c'], 'final_degree': 4, 'cleared': [3], 'occupied': [1, 2, 4, 6], 'capacity': 7, 'carry_steps': 1})], [({'table': {}, 'degree': 0, 'root': 'x'}, {'collisions': [], 'final_degree': 0, 'cleared': [], 'occupied': [0], 'capacity': 1, 'carry_steps': 0}), ({'table': {'0': 'a'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a'], 'final_degree': 1, 'cleared': [0], 'occupied': [1], 'capacity': 2, 'carry_steps': 1}), ({'table': {'0': 'a', '1': 'b', '3': 'c'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a', 'b'], 'final_degree': 2, 'cleared': [0, 1], 'occupied': [2, 3], 'capacity': 4, 'carry_steps': 2}), ({'table': {'0': 'a', '2': 'b', '3': 'c'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [0, 4], 'capacity': 5, 'carry_steps': 2}), ({'table': {'4': 'a'}, 'degree': 1, 'root': 'x'}, {'collisions': [], 'final_degree': 1, 'cleared': [], 'occupied': [1, 4], 'capacity': 5, 'carry_steps': 0}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 4, 'root': 'x'}, {'collisions': [], 'final_degree': 4, 'cleared': [], 'occupied': [1, 2, 3, 4, 6], 'capacity': 7, 'carry_steps': 0})], [({'table': {}, 'degree': 0, 'root': 'x'}, {'collisions': [], 'final_degree': 0, 'cleared': [], 'occupied': [0], 'capacity': 1, 'carry_steps': 0}), ({'table': {'0': 'a'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a'], 'final_degree': 1, 'cleared': [0], 'occupied': [1], 'capacity': 2, 'carry_steps': 1}), ({'table': {'0': 'a', '1': 'b', '3': 'c'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a', 'b'], 'final_degree': 2, 'cleared': [0, 1], 'occupied': [2, 3], 'capacity': 4, 'carry_steps': 2}), ({'table': {'0': 'a', '2': 'b', '3': 'c'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [0, 4], 'capacity': 5, 'carry_steps': 2}), ({'table': {'4': 'a'}, 'degree': 1, 'root': 'x'}, {'collisions': [], 'final_degree': 1, 'cleared': [], 'occupied': [1, 4], 'capacity': 5, 'carry_steps': 0}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 5, 'root': 'x'}, {'collisions': [], 'final_degree': 5, 'cleared': [], 'occupied': [1, 2, 3, 5, 6], 'capacity': 7, 'carry_steps': 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 fibonacci degree table certificate reports an incorrect capacity.

A Fibonacci consolidation trace gives occupied degree slots table degree->root id, incoming degree, and incoming root. Pop consecutive occupied degrees starting at incoming degree, collecting collision roots, then place incoming representative in first vacant slot. Report collisions, final degree, emptied slots, resulting occupied degree keys, required array capacity, and carry-step count. This is the degree-routing portion; key comparisons are outside this bounded model.

split: open-access


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

N = 1
observations = []
def solve(d):
    table={int(k):v for k,v in d['table'].items()}; start=d['degree']; degree=start; collisions=[]
    while degree in table:
        collisions.append(table[degree]); degree+=1
    out={k:v for k,v in table.items() if not start<=k<degree}; out[degree]=d['root']
    return {'collisions': collisions,
    'final_degree': degree,
    'cleared': list(range(start,degree)),
    'occupied': sorted(out),
    'capacity': max(out,default=-1)+1,
    'carry_steps': len(table)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'table': {}, 'degree': 0, 'root': 'x'}, {'collisions': [], 'final_degree': 0, 'cleared': [], 'occupied': [0], 'capacity': 1, 'carry_steps': 0}), ({'table': {'0': 'a'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a'], 'final_degree': 1, 'cleared': [0], 'occupied': [1], 'capacity': 2, 'carry_steps': 1}), ({'table': {'0': 'a', '1': 'b', '3': 'c'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a', 'b'], 'final_degree': 2, 'cleared': [0, 1], 'occupied': [2, 3], 'capacity': 4, 'carry_steps': 2}), ({'table': {'0': 'a', '2': 'b', '3': 'c'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [0, 4], 'capacity': 5, 'carry_steps': 2}), ({'table': {'4': 'a'}, 'degree': 1, 'root': 'x'}, {'collisions': [], 'final_degree': 1, 'cleared': [], 'occupied': [1, 4], 'capacity': 5, 'carry_steps': 0}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3})], [({'table': {}, 'degree': 0, 'root': 'x'}, {'collisions': [], 'final_degree': 0, 'cleared': [], 'occupied': [0], 'capacity': 1, 'carry_steps': 0}), ({'table': {'0': 'a'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a'], 'final_degree': 1, 'cleared': [0], 'occupied': [1], 'capacity': 2, 'carry_steps': 1}), ({'table': {'0': 'a', '1': 'b', '3': 'c'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a', 'b'], 'final_degree': 2, 'cleared': [0, 1], 'occupied': [2, 3], 'capacity': 4, 'carry_steps': 2}), ({'table': {'0': 'a', '2': 'b', '3': 'c'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [0, 4], 'capacity': 5, 'carry_steps': 2}), ({'table': {'4': 'a'}, 'degree': 1, 'root': 'x'}, {'collisions': [], 'final_degree': 1, 'cleared': [], 'occupied': [1, 4], 'capacity': 5, 'carry_steps': 0}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [1, 4, 6], 'capacity': 7, 'carry_steps': 2})], [({'table': {}, 'degree': 0, 'root': 'x'}, {'collisions': [], 'final_degree': 0, 'cleared': [], 'occupied': [0], 'capacity': 1, 'carry_steps': 0}), ({'table': {'0': 'a'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a'], 'final_degree': 1, 'cleared': [0], 'occupied': [1], 'capacity': 2, 'carry_steps': 1}), ({'table': {'0': 'a', '1': 'b', '3': 'c'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a', 'b'], 'final_degree': 2, 'cleared': [0, 1], 'occupied': [2, 3], 'capacity': 4, 'carry_steps': 2}), ({'table': {'0': 'a', '2': 'b', '3': 'c'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [0, 4], 'capacity': 5, 'carry_steps': 2}), ({'table': {'4': 'a'}, 'degree': 1, 'root': 'x'}, {'collisions': [], 'final_degree': 1, 'cleared': [], 'occupied': [1, 4], 'capacity': 5, 'carry_steps': 0}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 3, 'root': 'x'}, {'collisions': ['c'], 'final_degree': 4, 'cleared': [3], 'occupied': [1, 2, 4, 6], 'capacity': 7, 'carry_steps': 1})], [({'table': {}, 'degree': 0, 'root': 'x'}, {'collisions': [], 'final_degree': 0, 'cleared': [], 'occupied': [0], 'capacity': 1, 'carry_steps': 0}), ({'table': {'0': 'a'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a'], 'final_degree': 1, 'cleared': [0], 'occupied': [1], 'capacity': 2, 'carry_steps': 1}), ({'table': {'0': 'a', '1': 'b', '3': 'c'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a', 'b'], 'final_degree': 2, 'cleared': [0, 1], 'occupied': [2, 3], 'capacity': 4, 'carry_steps': 2}), ({'table': {'0': 'a', '2': 'b', '3': 'c'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [0, 4], 'capacity': 5, 'carry_steps': 2}), ({'table': {'4': 'a'}, 'degree': 1, 'root': 'x'}, {'collisions': [], 'final_degree': 1, 'cleared': [], 'occupied': [1, 4], 'capacity': 5, 'carry_steps': 0}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 4, 'root': 'x'}, {'collisions': [], 'final_degree': 4, 'cleared': [], 'occupied': [1, 2, 3, 4, 6], 'capacity': 7, 'carry_steps': 0})], [({'table': {}, 'degree': 0, 'root': 'x'}, {'collisions': [], 'final_degree': 0, 'cleared': [], 'occupied': [0], 'capacity': 1, 'carry_steps': 0}), ({'table': {'0': 'a'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a'], 'final_degree': 1, 'cleared': [0], 'occupied': [1], 'capacity': 2, 'carry_steps': 1}), ({'table': {'0': 'a', '1': 'b', '3': 'c'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a', 'b'], 'final_degree': 2, 'cleared': [0, 1], 'occupied': [2, 3], 'capacity': 4, 'carry_steps': 2}), ({'table': {'0': 'a', '2': 'b', '3': 'c'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [0, 4], 'capacity': 5, 'carry_steps': 2}), ({'table': {'4': 'a'}, 'degree': 1, 'root': 'x'}, {'collisions': [], 'final_degree': 1, 'cleared': [], 'occupied': [1, 4], 'capacity': 5, 'carry_steps': 0}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 5, 'root': 'x'}, {'collisions': [], 'final_degree': 5, 'cleared': [], 'occupied': [1, 2, 3, 5, 6], 'capacity': 7, 'carry_steps': 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):
    table={int(k):v for k,v in d['table'].items()}; start=d['degree']; degree=start; collisions=[]
    while degree in table:
        collisions.append(table[degree]); degree+=1
    out={k:v for k,v in table.items() if not start<=k<degree}; out[degree]=d['root']
    return {'collisions': collisions,
    'final_degree': degree,
    'cleared': list(range(start,degree)),
    'occupied': sorted(out),
    'capacity': max(out,default=-1)+1,
    'carry_steps': max(0,len(collisions)-1)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'table': {}, 'degree': 0, 'root': 'x'}, {'collisions': [], 'final_degree': 0, 'cleared': [], 'occupied': [0], 'capacity': 1, 'carry_steps': 0}), ({'table': {'0': 'a'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a'], 'final_degree': 1, 'cleared': [0], 'occupied': [1], 'capacity': 2, 'carry_steps': 1}), ({'table': {'0': 'a', '1': 'b', '3': 'c'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a', 'b'], 'final_degree': 2, 'cleared': [0, 1], 'occupied': [2, 3], 'capacity': 4, 'carry_steps': 2}), ({'table': {'0': 'a', '2': 'b', '3': 'c'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [0, 4], 'capacity': 5, 'carry_steps': 2}), ({'table': {'4': 'a'}, 'degree': 1, 'root': 'x'}, {'collisions': [], 'final_degree': 1, 'cleared': [], 'occupied': [1, 4], 'capacity': 5, 'carry_steps': 0}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3})], [({'table': {}, 'degree': 0, 'root': 'x'}, {'collisions': [], 'final_degree': 0, 'cleared': [], 'occupied': [0], 'capacity': 1, 'carry_steps': 0}), ({'table': {'0': 'a'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a'], 'final_degree': 1, 'cleared': [0], 'occupied': [1], 'capacity': 2, 'carry_steps': 1}), ({'table': {'0': 'a', '1': 'b', '3': 'c'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a', 'b'], 'final_degree': 2, 'cleared': [0, 1], 'occupied': [2, 3], 'capacity': 4, 'carry_steps': 2}), ({'table': {'0': 'a', '2': 'b', '3': 'c'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [0, 4], 'capacity': 5, 'carry_steps': 2}), ({'table': {'4': 'a'}, 'degree': 1, 'root': 'x'}, {'collisions': [], 'final_degree': 1, 'cleared': [], 'occupied': [1, 4], 'capacity': 5, 'carry_steps': 0}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [1, 4, 6], 'capacity': 7, 'carry_steps': 2})], [({'table': {}, 'degree': 0, 'root': 'x'}, {'collisions': [], 'final_degree': 0, 'cleared': [], 'occupied': [0], 'capacity': 1, 'carry_steps': 0}), ({'table': {'0': 'a'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a'], 'final_degree': 1, 'cleared': [0], 'occupied': [1], 'capacity': 2, 'carry_steps': 1}), ({'table': {'0': 'a', '1': 'b', '3': 'c'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a', 'b'], 'final_degree': 2, 'cleared': [0, 1], 'occupied': [2, 3], 'capacity': 4, 'carry_steps': 2}), ({'table': {'0': 'a', '2': 'b', '3': 'c'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [0, 4], 'capacity': 5, 'carry_steps': 2}), ({'table': {'4': 'a'}, 'degree': 1, 'root': 'x'}, {'collisions': [], 'final_degree': 1, 'cleared': [], 'occupied': [1, 4], 'capacity': 5, 'carry_steps': 0}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 3, 'root': 'x'}, {'collisions': ['c'], 'final_degree': 4, 'cleared': [3], 'occupied': [1, 2, 4, 6], 'capacity': 7, 'carry_steps': 1})], [({'table': {}, 'degree': 0, 'root': 'x'}, {'collisions': [], 'final_degree': 0, 'cleared': [], 'occupied': [0], 'capacity': 1, 'carry_steps': 0}), ({'table': {'0': 'a'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a'], 'final_degree': 1, 'cleared': [0], 'occupied': [1], 'capacity': 2, 'carry_steps': 1}), ({'table': {'0': 'a', '1': 'b', '3': 'c'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a', 'b'], 'final_degree': 2, 'cleared': [0, 1], 'occupied': [2, 3], 'capacity': 4, 'carry_steps': 2}), ({'table': {'0': 'a', '2': 'b', '3': 'c'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [0, 4], 'capacity': 5, 'carry_steps': 2}), ({'table': {'4': 'a'}, 'degree': 1, 'root': 'x'}, {'collisions': [], 'final_degree': 1, 'cleared': [], 'occupied': [1, 4], 'capacity': 5, 'carry_steps': 0}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 4, 'root': 'x'}, {'collisions': [], 'final_degree': 4, 'cleared': [], 'occupied': [1, 2, 3, 4, 6], 'capacity': 7, 'carry_steps': 0})], [({'table': {}, 'degree': 0, 'root': 'x'}, {'collisions': [], 'final_degree': 0, 'cleared': [], 'occupied': [0], 'capacity': 1, 'carry_steps': 0}), ({'table': {'0': 'a'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a'], 'final_degree': 1, 'cleared': [0], 'occupied': [1], 'capacity': 2, 'carry_steps': 1}), ({'table': {'0': 'a', '1': 'b', '3': 'c'}, 'degree': 0, 'root': 'x'}, {'collisions': ['a', 'b'], 'final_degree': 2, 'cleared': [0, 1], 'occupied': [2, 3], 'capacity': 4, 'carry_steps': 2}), ({'table': {'0': 'a', '2': 'b', '3': 'c'}, 'degree': 2, 'root': 'x'}, {'collisions': ['b', 'c'], 'final_degree': 4, 'cleared': [2, 3], 'occupied': [0, 4], 'capacity': 5, 'carry_steps': 2}), ({'table': {'4': 'a'}, 'degree': 1, 'root': 'x'}, {'collisions': [], 'final_degree': 1, 'cleared': [], 'occupied': [1, 4], 'capacity': 5, 'carry_steps': 0}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 1, 'root': 'x'}, {'collisions': ['a', 'b', 'c'], 'final_degree': 4, 'cleared': [1, 2, 3], 'occupied': [4, 6], 'capacity': 7, 'carry_steps': 3}), ({'table': {'1': 'a', '2': 'b', '3': 'c', '6': 'd'}, 'degree': 5, 'root': 'x'}, {'collisions': [], 'final_degree': 5, 'cleared': [], 'occupied': [1, 2, 3, 5, 6], 'capacity': 7, 'carry_steps': 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 fibonacci degree table certificate reports an incorrect carry steps.

A Fibonacci consolidation trace gives occupied degree slots table degree->root id, incoming degree, and incoming root. Pop consecutive occupied degrees starting at incoming degree, collecting collision roots, then place incoming representative in first vacant slot. Report collisions, final degree, emptied slots, resulting occupied degree keys, required array capacity, and carry-step count. This is the degree-routing portion; key comparisons are outside this bounded model.

split: open-access


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

N = 1
observations = []
def solve(d):
    p=d['parent']; cs=d['children']; c=d['child']; k=cs.index(c); before=cs[:k]; after=cs[k+1:]; kept=before+after
    return {'children': cs[:k],
    'first': kept[0] if kept else None,
    'successor_previous': None if not after else [after[0],before[-1] if before else p],
    'predecessor_next': None if not before else [before[-1],after[0] if after else None],
    'roots': d["roots"]+[c],
    'detached': [None,None,None]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'parent': 9, 'children': [1], 'child': 1, 'roots': [9, 8]}, {'children': [], 'first': None, 'successor_previous': None, 'predecessor_next': None, 'roots': [9, 8, 1], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2], 'child': 1, 'roots': [9, 8]}, {'children': [2], 'first': 2, 'successor_previous': [2, 9], 'predecessor_next': None, 'roots': [9, 8, 1], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2], 'child': 2, 'roots': [9, 8]}, {'children': [1], 'first': 1, 'successor_previous': None, 'predecessor_next': [1, None], 'roots': [9, 8, 2], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2, 3], 'child': 2, 'roots': [9, 8]}, {'children': [1, 3], 'first': 1, 'successor_previous': [3, 1], 'predecessor_next': [1, 3], 'roots': [9, 8, 2], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2, 3, 4], 'child': 3, 'roots': [9, 8]}, {'children': [1, 2, 4], 'first': 1, 'successor_previous': [4, 2], 'predecessor_next': [2, 4], 'roots': [9, 8, 3], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2, 3], 'child': 1, 'roots': [9, 8]}, {'children': [2, 3], 'first': 2, 'successor_previous': [2, 9], 'predecessor_next': None, 'roots': [9, 8, 1], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2, 3, 100], 'child': 100, 'roots': [9, 8]}, {'children': [1, 2, 3], 'first': 1, 'successor_previous': None, 'predecessor_next': [3, None], 'roots': [9, 8, 100], 'detached': [None, None, None]})], [({'parent': 9, 'children': [1], 'child': 1, 'roots': [9, 8]}, {'children': [], 'first': None, 'successor_previous': None, 'predecessor_next': None, 'roots': [9, 8, 1], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2], 'child': 1, 'roots': [9, 8]}, {'children': [2], 'first': 2, 'successor_previous': [2, 9], 'predecessor_next': None, 'roots': [9, 8, 1], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2], 'child': 2, 'roots': [9, 8]}, {'children': [1], 'first': 1, 'successor_previous': None, 'predecessor_next': [1, None], 'roots': [9, 8, 2], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2, 3], 'child': 2, 'roots': [9, 8]}, {'children': [1, 3], 'first': 1, 'successor_previous': [3, 1], 'predecessor_next': [1, 3], 'roots': [9, 8, 2], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2, 3, 4], 'child': 3, 'roots': [9, 8]}, {'children': [1, 2, 4], 'first': 1, 'successor_previous': [4, 2], 'predecessor_next': [2, 4], 'roots': [9, 8, 3], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2, 3], 'child': 1, 'roots': [9, 8]}, {'children': [2, 3], 'first': 2, 'successor_previous': [2, 9], 'predecessor_next': None, 'roots': [9, 8, 1], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2, 3, 100, 101], 'child': 101, 'roots': [9, 8]}, {'children': [1, 2, 3, 100], 'first': 1, 'successor_previous': None, 'predecessor_next': [100, None], 'roots': [9, 8, 101], 'detached': [None, None, None]})], [({'parent': 9, 'children': [1], 'child': 1, 'roots': [9, 8]}, {'children': [], 'first': None, 'successor_previous': None, 'predecessor_next': None, 'roots': [9, 8, 1], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2], 'child': 1, 'roots': [9, 8]}, {'children': [2], 'first': 2, 'successor_previous': [2, 9], 'predecessor_next': None, 'roots': [9, 8, 1], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2], 'child': 2, 'roots': [9, 8]}, {'children': [1], 'first': 1, 'successor_previous': None, 'predecessor_next': [1, None], 'roots': [9, 8, 2], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2, 3], 'child': 2, 'roots': [9, 8]}, {'children': [1, 3], 'first': 1, 'successor_previous': [3, 1], 'predecessor_next': [1, 3], 'roots': [9, 8, 2], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2, 3, 4], 'child': 3, 'roots': [9, 8]}, {'children': [1, 2, 4], 'first': 1, 'successor_previous': [4, 2], 'predecessor_next': [2, 4], 'roots': [9, 8, 3], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2, 3], 'child': 1, 'roots': [9, 8]}, {'children': [2, 3], 'first': 2, 'successor_previous': [2, 9], 'predecessor_next': None, 'roots': [9, 8, 1], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2, 3, 100, 101, 102], 'child': 102, 'roots': [9, 8]}, {'children': [1, 2, 3, 100, 101], 'first': 1, 'successor_previous': None, 'predecessor_next': [101, None], 'roots': [9, 8, 102], 'detached': [None, None, None]})], [({'parent': 9, 'children': [1], 'child': 1, 'roots': [9, 8]}, {'children': [], 'first': None, 'successor_previous': None, 'predecessor_next': None, 'roots': [9, 8, 1], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2], 'child': 1, 'roots': [9, 8]}, {'children': [2], 'first': 2, 'successor_previous': [2, 9], 'predecessor_next': None, 'roots': [9, 8, 1], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2], 'child': 2, 'roots': [9, 8]}, {'children': [1], 'first': 1, 'successor_previous': None, 'predecessor_next': [1, None], 'roots': [9, 8, 2], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2, 3], 'child': 2, 'roots': [9, 8]}, {'children': [1, 3], 'first': 1, 'successor_previous': [3, 1], 'predecessor_next': [1, 3], 'roots': [9, 8, 2], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2, 3, 4], 'child': 3, 'roots': [9, 8]}, {'children': [1, 2, 4], 'first': 1, 'successor_previous': [4, 2], 'predecessor_next': [2, 4], 'roots': [9, 8, 3], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2, 3], 'child': 1, 'roots': [9, 8]}, {'children': [2, 3], 'first': 2, 'successor_previous': [2, 9], 'predecessor_next': None, 'roots': [9, 8, 1], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2, 3, 100, 101, 102, 103], 'child': 103, 'roots': [9, 8]}, {'children': [1, 2, 3, 100, 101, 102], 'first': 1, 'successor_previous': None, 'predecessor_next': [102, None], 'roots': [9, 8, 103], 'detached': [None, None, None]})], [({'parent': 9, 'children': [1], 'child': 1, 'roots': [9, 8]}, {'children': [], 'first': None, 'successor_previous': None, 'predecessor_next': None, 'roots': [9, 8, 1], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2], 'child': 1, 'roots': [9, 8]}, {'children': [2], 'first': 2, 'successor_previous': [2, 9], 'predecessor_next': None, 'roots': [9, 8, 1], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2], 'child': 2, 'roots': [9, 8]}, {'children': [1], 'first': 1, 'successor_previous': None, 'predecessor_next': [1, None], 'roots': [9, 8, 2], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2, 3], 'child': 2, 'roots': [9, 8]}, {'children': [1, 3], 'first': 1, 'successor_previous': [3, 1], 'predecessor_next': [1, 3], 'roots': [9, 8, 2], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2, 3, 4], 'child': 3, 'roots': [9, 8]}, {'children': [1, 2, 4], 'first': 1, 'successor_previous': [4, 2], 'predecessor_next': [2, 4], 'roots': [9, 8, 3], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2, 3], 'child': 1, 'roots': [9, 8]}, {'children': [2, 3], 'first': 2, 'successor_previous': [2, 9], 'predecessor_next': None, 'roots': [9, 8, 1], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2, 3, 100, 101, 102, 103, 104], 'child': 104, 'roots': [9, 8]}, {'children': [1, 2, 3, 100, 101, 102, 103], 'first': 1, 'successor_previous': None, 'predecessor_next': [103, None], 'roots': [9, 8, 104], 'detached': [None, None, None]})]][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):
    p=d['parent']; cs=d['children']; c=d['child']; k=cs.index(c); before=cs[:k]; after=cs[k+1:]; kept=before+after
    return {'children': cs[k+1:],
    'first': kept[0] if kept else None,
    'successor_previous': None if not after else [after[0],before[-1] if before else p],
    'predecessor_next': None if not before else [before[-1],after[0] if after else None],
    'roots': d["roots"]+[c],
    'detached': [None,None,None]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'parent': 9, 'children': [1], 'child': 1, 'roots': [9, 8]}, {'children': [], 'first': None, 'successor_previous': None, 'predecessor_next': None, 'roots': [9, 8, 1], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2], 'child': 1, 'roots': [9, 8]}, {'children': [2], 'first': 2, 'successor_previous': [2, 9], 'predecessor_next': None, 'roots': [9, 8, 1], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2], 'child': 2, 'roots': [9, 8]}, {'children': [1], 'first': 1, 'successor_previous': None, 'predecessor_next': [1, None], 'roots': [9, 8, 2], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2, 3], 'child': 2, 'roots': [9, 8]}, {'children': [1, 3], 'first': 1, 'successor_previous': [3, 1], 'predecessor_next': [1, 3], 'roots': [9, 8, 2], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2, 3, 4], 'child': 3, 'roots': [9, 8]}, {'children': [1, 2, 4], 'first': 1, 'successor_previous': [4, 2], 'predecessor_next': [2, 4], 'roots': [9, 8, 3], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2, 3], 'child': 1, 'roots': [9, 8]}, {'children': [2, 3], 'first': 2, 'successor_previous': [2, 9], 'predecessor_next': None, 'roots': [9, 8, 1], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2, 3, 100], 'child': 100, 'roots': [9, 8]}, {'children': [1, 2, 3], 'first': 1, 'successor_previous': None, 'predecessor_next': [3, None], 'roots': [9, 8, 100], 'detached': [None, None, None]})], [({'parent': 9, 'children': [1], 'child': 1, 'roots': [9, 8]}, {'children': [], 'first': None, 'successor_previous': None, 'predecessor_next': None, 'roots': [9, 8, 1], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2], 'child': 1, 'roots': [9, 8]}, {'children': [2], 'first': 2, 'successor_previous': [2, 9], 'predecessor_next': None, 'roots': [9, 8, 1], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2], 'child': 2, 'roots': [9, 8]}, {'children': [1], 'first': 1, 'successor_previous': None, 'predecessor_next': [1, None], 'roots': [9, 8, 2], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2, 3], 'child': 2, 'roots': [9, 8]}, {'children': [1, 3], 'first': 1, 'successor_previous': [3, 1], 'predecessor_next': [1, 3], 'roots': [9, 8, 2], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2, 3, 4], 'child': 3, 'roots': [9, 8]}, {'children': [1, 2, 4], 'first': 1, 'successor_previous': [4, 2], 'predecessor_next': [2, 4], 'roots': [9, 8, 3], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2, 3], 'child': 1, 'roots': [9, 8]}, {'children': [2, 3], 'first': 2, 'successor_previous': [2, 9], 'predecessor_next': None, 'roots': [9, 8, 1], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2, 3, 100, 101], 'child': 101, 'roots': [9, 8]}, {'children': [1, 2, 3, 100], 'first': 1, 'successor_previous': None, 'predecessor_next': [100, None], 'roots': [9, 8, 101], 'detached': [None, None, None]})], [({'parent': 9, 'children': [1], 'child': 1, 'roots': [9, 8]}, {'children': [], 'first': None, 'successor_previous': None, 'predecessor_next': None, 'roots': [9, 8, 1], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2], 'child': 1, 'roots': [9, 8]}, {'children': [2], 'first': 2, 'successor_previous': [2, 9], 'predecessor_next': None, 'roots': [9, 8, 1], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2], 'child': 2, 'roots': [9, 8]}, {'children': [1], 'first': 1, 'successor_previous': None, 'predecessor_next': [1, None], 'roots': [9, 8, 2], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2, 3], 'child': 2, 'roots': [9, 8]}, {'children': [1, 3], 'first': 1, 'successor_previous': [3, 1], 'predecessor_next': [1, 3], 'roots': [9, 8, 2], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2, 3, 4], 'child': 3, 'roots': [9, 8]}, {'children': [1, 2, 4], 'first': 1, 'successor_previous': [4, 2], 'predecessor_next': [2, 4], 'roots': [9, 8, 3], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2, 3], 'child': 1, 'roots': [9, 8]}, {'children': [2, 3], 'first': 2, 'successor_previous': [2, 9], 'predecessor_next': None, 'roots': [9, 8, 1], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2, 3, 100, 101, 102], 'child': 102, 'roots': [9, 8]}, {'children': [1, 2, 3, 100, 101], 'first': 1, 'successor_previous': None, 'predecessor_next': [101, None], 'roots': [9, 8, 102], 'detached': [None, None, None]})], [({'parent': 9, 'children': [1], 'child': 1, 'roots': [9, 8]}, {'children': [], 'first': None, 'successor_previous': None, 'predecessor_next': None, 'roots': [9, 8, 1], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2], 'child': 1, 'roots': [9, 8]}, {'children': [2], 'first': 2, 'successor_previous': [2, 9], 'predecessor_next': None, 'roots': [9, 8, 1], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2], 'child': 2, 'roots': [9, 8]}, {'children': [1], 'first': 1, 'successor_previous': None, 'predecessor_next': [1, None], 'roots': [9, 8, 2], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2, 3], 'child': 2, 'roots': [9, 8]}, {'children': [1, 3], 'first': 1, 'successor_previous': [3, 1], 'predecessor_next': [1, 3], 'roots': [9, 8, 2], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2, 3, 4], 'child': 3, 'roots': [9, 8]}, {'children': [1, 2, 4], 'first': 1, 'successor_previous': [4, 2], 'predecessor_next': [2, 4], 'roots': [9, 8, 3], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2, 3], 'child': 1, 'roots': [9, 8]}, {'children': [2, 3], 'first': 2, 'successor_previous': [2, 9], 'predecessor_next': None, 'roots': [9, 8, 1], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2, 3, 100, 101, 102, 103], 'child': 103, 'roots': [9, 8]}, {'children': [1, 2, 3, 100, 101, 102], 'first': 1, 'successor_previous': None, 'predecessor_next': [102, None], 'roots': [9, 8, 103], 'detached': [None, None, None]})], [({'parent': 9, 'children': [1], 'child': 1, 'roots': [9, 8]}, {'children': [], 'first': None, 'successor_previous': None, 'predecessor_next': None, 'roots': [9, 8, 1], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2], 'child': 1, 'roots': [9, 8]}, {'children': [2], 'first': 2, 'successor_previous': [2, 9], 'predecessor_next': None, 'roots': [9, 8, 1], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2], 'child': 2, 'roots': [9, 8]}, {'children': [1], 'first': 1, 'successor_previous': None, 'predecessor_next': [1, None], 'roots': [9, 8, 2], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2, 3], 'child': 2, 'roots': [9, 8]}, {'children': [1, 3], 'first': 1, 'successor_previous': [3, 1], 'predecessor_next': [1, 3], 'roots': [9, 8, 2], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2, 3, 4], 'child': 3, 'roots': [9, 8]}, {'children': [1, 2, 4], 'first': 1, 'successor_previous': [4, 2], 'predecessor_next': [2, 4], 'roots': [9, 8, 3], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2, 3], 'child': 1, 'roots': [9, 8]}, {'children': [2, 3], 'first': 2, 'successor_previous': [2, 9], 'predecessor_next': None, 'roots': [9, 8, 1], 'detached': [None, None, None]}), ({'parent': 9, 'children': [1, 2, 3, 100, 101, 102, 103, 104], 'child': 104, 'roots': [9, 8]}, {'children': [1, 2, 3, 100, 101, 102, 103], 'first': 1, 'successor_previous': None, 'predecessor_next': [103, None], 'roots': [9, 8, 104], 'detached': [None, None, None]})]][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 pairing cut splice certificate reports an incorrect children.

A pairing-heap cut input contains parent id, ordered child ids, selected child, and preexisting roots. Remove the child while preserving sibling order. Return remaining children, new first child, successor previous pointer (parent if selected was first), predecessor next pointer, promoted root list, and detached child links [parent,previous,next] all None.

split: open-access