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

N = 1
observations = []
def solve(d):
    c=d['children']; r=d['remaining']; removed=d['removed']; merged=r+list(reversed(c))
    return {'promoted': [x[0] for x in reversed(c)],
    'parents': [[x[0],None] for x in c],
    'size_delta': -1,
    'minimum': min(merged,key=lambda x:x[2])[0] if merged else None,
    'merge_ranks': sorted(x[1] for x in merged),
    'live_handles': sorted([removed]+[x[0] for x in merged])}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'children': [], 'remaining': [], 'removed': 9}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': None, 'merge_ranks': [], 'live_handles': []}), ({'children': [[3, 0, 7]], 'remaining': [], 'removed': 1}, {'promoted': [3], 'parents': [[3, None]], 'size_delta': -1, 'minimum': 3, 'merge_ranks': [0], 'live_handles': [3]}), ({'children': [[4, 2, 6], [3, 1, 5], [2, 0, 8]], 'remaining': [[7, 0, 4], [8, 3, 9]], 'removed': 1}, {'promoted': [2, 3, 4], 'parents': [[4, None], [3, None], [2, None]], 'size_delta': -1, 'minimum': 7, 'merge_ranks': [0, 0, 1, 2, 3], 'live_handles': [2, 3, 4, 7, 8]}), ({'children': [[6, 1, 3], [5, 0, 2]], 'remaining': [[8, 2, 7]], 'removed': 4}, {'promoted': [5, 6], 'parents': [[6, None], [5, None]], 'size_delta': -1, 'minimum': 5, 'merge_ranks': [0, 1, 2], 'live_handles': [5, 6, 8]}), ({'children': [], 'remaining': [[5, 0, 8], [2, 1, 1]], 'removed': 7}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': 2, 'merge_ranks': [0, 1], 'live_handles': [2, 5]}), ({'children': [[7, 1, 4], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]}), ({'children': [[7, 1, 5], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]})], [({'children': [], 'remaining': [], 'removed': 9}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': None, 'merge_ranks': [], 'live_handles': []}), ({'children': [[3, 0, 7]], 'remaining': [], 'removed': 1}, {'promoted': [3], 'parents': [[3, None]], 'size_delta': -1, 'minimum': 3, 'merge_ranks': [0], 'live_handles': [3]}), ({'children': [[4, 2, 6], [3, 1, 5], [2, 0, 8]], 'remaining': [[7, 0, 4], [8, 3, 9]], 'removed': 1}, {'promoted': [2, 3, 4], 'parents': [[4, None], [3, None], [2, None]], 'size_delta': -1, 'minimum': 7, 'merge_ranks': [0, 0, 1, 2, 3], 'live_handles': [2, 3, 4, 7, 8]}), ({'children': [[6, 1, 3], [5, 0, 2]], 'remaining': [[8, 2, 7]], 'removed': 4}, {'promoted': [5, 6], 'parents': [[6, None], [5, None]], 'size_delta': -1, 'minimum': 5, 'merge_ranks': [0, 1, 2], 'live_handles': [5, 6, 8]}), ({'children': [], 'remaining': [[5, 0, 8], [2, 1, 1]], 'removed': 7}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': 2, 'merge_ranks': [0, 1], 'live_handles': [2, 5]}), ({'children': [[7, 1, 4], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]}), ({'children': [[7, 1, 6], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]})], [({'children': [], 'remaining': [], 'removed': 9}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': None, 'merge_ranks': [], 'live_handles': []}), ({'children': [[3, 0, 7]], 'remaining': [], 'removed': 1}, {'promoted': [3], 'parents': [[3, None]], 'size_delta': -1, 'minimum': 3, 'merge_ranks': [0], 'live_handles': [3]}), ({'children': [[4, 2, 6], [3, 1, 5], [2, 0, 8]], 'remaining': [[7, 0, 4], [8, 3, 9]], 'removed': 1}, {'promoted': [2, 3, 4], 'parents': [[4, None], [3, None], [2, None]], 'size_delta': -1, 'minimum': 7, 'merge_ranks': [0, 0, 1, 2, 3], 'live_handles': [2, 3, 4, 7, 8]}), ({'children': [[6, 1, 3], [5, 0, 2]], 'remaining': [[8, 2, 7]], 'removed': 4}, {'promoted': [5, 6], 'parents': [[6, None], [5, None]], 'size_delta': -1, 'minimum': 5, 'merge_ranks': [0, 1, 2], 'live_handles': [5, 6, 8]}), ({'children': [], 'remaining': [[5, 0, 8], [2, 1, 1]], 'removed': 7}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': 2, 'merge_ranks': [0, 1], 'live_handles': [2, 5]}), ({'children': [[7, 1, 4], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]}), ({'children': [[7, 1, 7], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]})], [({'children': [], 'remaining': [], 'removed': 9}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': None, 'merge_ranks': [], 'live_handles': []}), ({'children': [[3, 0, 7]], 'remaining': [], 'removed': 1}, {'promoted': [3], 'parents': [[3, None]], 'size_delta': -1, 'minimum': 3, 'merge_ranks': [0], 'live_handles': [3]}), ({'children': [[4, 2, 6], [3, 1, 5], [2, 0, 8]], 'remaining': [[7, 0, 4], [8, 3, 9]], 'removed': 1}, {'promoted': [2, 3, 4], 'parents': [[4, None], [3, None], [2, None]], 'size_delta': -1, 'minimum': 7, 'merge_ranks': [0, 0, 1, 2, 3], 'live_handles': [2, 3, 4, 7, 8]}), ({'children': [[6, 1, 3], [5, 0, 2]], 'remaining': [[8, 2, 7]], 'removed': 4}, {'promoted': [5, 6], 'parents': [[6, None], [5, None]], 'size_delta': -1, 'minimum': 5, 'merge_ranks': [0, 1, 2], 'live_handles': [5, 6, 8]}), ({'children': [], 'remaining': [[5, 0, 8], [2, 1, 1]], 'removed': 7}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': 2, 'merge_ranks': [0, 1], 'live_handles': [2, 5]}), ({'children': [[7, 1, 4], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]}), ({'children': [[7, 1, 8], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]})], [({'children': [], 'remaining': [], 'removed': 9}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': None, 'merge_ranks': [], 'live_handles': []}), ({'children': [[3, 0, 7]], 'remaining': [], 'removed': 1}, {'promoted': [3], 'parents': [[3, None]], 'size_delta': -1, 'minimum': 3, 'merge_ranks': [0], 'live_handles': [3]}), ({'children': [[4, 2, 6], [3, 1, 5], [2, 0, 8]], 'remaining': [[7, 0, 4], [8, 3, 9]], 'removed': 1}, {'promoted': [2, 3, 4], 'parents': [[4, None], [3, None], [2, None]], 'size_delta': -1, 'minimum': 7, 'merge_ranks': [0, 0, 1, 2, 3], 'live_handles': [2, 3, 4, 7, 8]}), ({'children': [[6, 1, 3], [5, 0, 2]], 'remaining': [[8, 2, 7]], 'removed': 4}, {'promoted': [5, 6], 'parents': [[6, None], [5, None]], 'size_delta': -1, 'minimum': 5, 'merge_ranks': [0, 1, 2], 'live_handles': [5, 6, 8]}), ({'children': [], 'remaining': [[5, 0, 8], [2, 1, 1]], 'removed': 7}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': 2, 'merge_ranks': [0, 1], 'live_handles': [2, 5]}), ({'children': [[7, 1, 4], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]}), ({'children': [[7, 1, 9], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]})]][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):
    c=d['children']; r=d['remaining']; removed=d['removed']; merged=r+list(reversed(c))
    return {'promoted': [x[0] for x in reversed(c)],
    'parents': [[x[0],None] for x in c],
    'size_delta': -1,
    'minimum': min(merged,key=lambda x:x[2])[0] if merged else None,
    'merge_ranks': sorted(x[1] for x in merged),
    'live_handles': sorted(x[0] for x in r)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'children': [], 'remaining': [], 'removed': 9}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': None, 'merge_ranks': [], 'live_handles': []}), ({'children': [[3, 0, 7]], 'remaining': [], 'removed': 1}, {'promoted': [3], 'parents': [[3, None]], 'size_delta': -1, 'minimum': 3, 'merge_ranks': [0], 'live_handles': [3]}), ({'children': [[4, 2, 6], [3, 1, 5], [2, 0, 8]], 'remaining': [[7, 0, 4], [8, 3, 9]], 'removed': 1}, {'promoted': [2, 3, 4], 'parents': [[4, None], [3, None], [2, None]], 'size_delta': -1, 'minimum': 7, 'merge_ranks': [0, 0, 1, 2, 3], 'live_handles': [2, 3, 4, 7, 8]}), ({'children': [[6, 1, 3], [5, 0, 2]], 'remaining': [[8, 2, 7]], 'removed': 4}, {'promoted': [5, 6], 'parents': [[6, None], [5, None]], 'size_delta': -1, 'minimum': 5, 'merge_ranks': [0, 1, 2], 'live_handles': [5, 6, 8]}), ({'children': [], 'remaining': [[5, 0, 8], [2, 1, 1]], 'removed': 7}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': 2, 'merge_ranks': [0, 1], 'live_handles': [2, 5]}), ({'children': [[7, 1, 4], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]}), ({'children': [[7, 1, 5], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]})], [({'children': [], 'remaining': [], 'removed': 9}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': None, 'merge_ranks': [], 'live_handles': []}), ({'children': [[3, 0, 7]], 'remaining': [], 'removed': 1}, {'promoted': [3], 'parents': [[3, None]], 'size_delta': -1, 'minimum': 3, 'merge_ranks': [0], 'live_handles': [3]}), ({'children': [[4, 2, 6], [3, 1, 5], [2, 0, 8]], 'remaining': [[7, 0, 4], [8, 3, 9]], 'removed': 1}, {'promoted': [2, 3, 4], 'parents': [[4, None], [3, None], [2, None]], 'size_delta': -1, 'minimum': 7, 'merge_ranks': [0, 0, 1, 2, 3], 'live_handles': [2, 3, 4, 7, 8]}), ({'children': [[6, 1, 3], [5, 0, 2]], 'remaining': [[8, 2, 7]], 'removed': 4}, {'promoted': [5, 6], 'parents': [[6, None], [5, None]], 'size_delta': -1, 'minimum': 5, 'merge_ranks': [0, 1, 2], 'live_handles': [5, 6, 8]}), ({'children': [], 'remaining': [[5, 0, 8], [2, 1, 1]], 'removed': 7}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': 2, 'merge_ranks': [0, 1], 'live_handles': [2, 5]}), ({'children': [[7, 1, 4], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]}), ({'children': [[7, 1, 6], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]})], [({'children': [], 'remaining': [], 'removed': 9}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': None, 'merge_ranks': [], 'live_handles': []}), ({'children': [[3, 0, 7]], 'remaining': [], 'removed': 1}, {'promoted': [3], 'parents': [[3, None]], 'size_delta': -1, 'minimum': 3, 'merge_ranks': [0], 'live_handles': [3]}), ({'children': [[4, 2, 6], [3, 1, 5], [2, 0, 8]], 'remaining': [[7, 0, 4], [8, 3, 9]], 'removed': 1}, {'promoted': [2, 3, 4], 'parents': [[4, None], [3, None], [2, None]], 'size_delta': -1, 'minimum': 7, 'merge_ranks': [0, 0, 1, 2, 3], 'live_handles': [2, 3, 4, 7, 8]}), ({'children': [[6, 1, 3], [5, 0, 2]], 'remaining': [[8, 2, 7]], 'removed': 4}, {'promoted': [5, 6], 'parents': [[6, None], [5, None]], 'size_delta': -1, 'minimum': 5, 'merge_ranks': [0, 1, 2], 'live_handles': [5, 6, 8]}), ({'children': [], 'remaining': [[5, 0, 8], [2, 1, 1]], 'removed': 7}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': 2, 'merge_ranks': [0, 1], 'live_handles': [2, 5]}), ({'children': [[7, 1, 4], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]}), ({'children': [[7, 1, 7], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]})], [({'children': [], 'remaining': [], 'removed': 9}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': None, 'merge_ranks': [], 'live_handles': []}), ({'children': [[3, 0, 7]], 'remaining': [], 'removed': 1}, {'promoted': [3], 'parents': [[3, None]], 'size_delta': -1, 'minimum': 3, 'merge_ranks': [0], 'live_handles': [3]}), ({'children': [[4, 2, 6], [3, 1, 5], [2, 0, 8]], 'remaining': [[7, 0, 4], [8, 3, 9]], 'removed': 1}, {'promoted': [2, 3, 4], 'parents': [[4, None], [3, None], [2, None]], 'size_delta': -1, 'minimum': 7, 'merge_ranks': [0, 0, 1, 2, 3], 'live_handles': [2, 3, 4, 7, 8]}), ({'children': [[6, 1, 3], [5, 0, 2]], 'remaining': [[8, 2, 7]], 'removed': 4}, {'promoted': [5, 6], 'parents': [[6, None], [5, None]], 'size_delta': -1, 'minimum': 5, 'merge_ranks': [0, 1, 2], 'live_handles': [5, 6, 8]}), ({'children': [], 'remaining': [[5, 0, 8], [2, 1, 1]], 'removed': 7}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': 2, 'merge_ranks': [0, 1], 'live_handles': [2, 5]}), ({'children': [[7, 1, 4], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]}), ({'children': [[7, 1, 8], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]})], [({'children': [], 'remaining': [], 'removed': 9}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': None, 'merge_ranks': [], 'live_handles': []}), ({'children': [[3, 0, 7]], 'remaining': [], 'removed': 1}, {'promoted': [3], 'parents': [[3, None]], 'size_delta': -1, 'minimum': 3, 'merge_ranks': [0], 'live_handles': [3]}), ({'children': [[4, 2, 6], [3, 1, 5], [2, 0, 8]], 'remaining': [[7, 0, 4], [8, 3, 9]], 'removed': 1}, {'promoted': [2, 3, 4], 'parents': [[4, None], [3, None], [2, None]], 'size_delta': -1, 'minimum': 7, 'merge_ranks': [0, 0, 1, 2, 3], 'live_handles': [2, 3, 4, 7, 8]}), ({'children': [[6, 1, 3], [5, 0, 2]], 'remaining': [[8, 2, 7]], 'removed': 4}, {'promoted': [5, 6], 'parents': [[6, None], [5, None]], 'size_delta': -1, 'minimum': 5, 'merge_ranks': [0, 1, 2], 'live_handles': [5, 6, 8]}), ({'children': [], 'remaining': [[5, 0, 8], [2, 1, 1]], 'removed': 7}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': 2, 'merge_ranks': [0, 1], 'live_handles': [2, 5]}), ({'children': [[7, 1, 4], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]}), ({'children': [[7, 1, 9], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]})]][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 binomial extract certificate reports an incorrect live handles.

Extracted binomial root children are [id,rank,key] in descending rank. Remaining roots are [id,rank,key]. Return promoted root order, parent resets, cardinality delta, remaining minimum, merge rank sequence, and removed handle. Reversal restores ascending rank order before union.

split: open-access


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

N = 1
observations = []
def solve(d):
    c=d['child']; p=d['parent']; children=d['children']; roots=d['roots']; degree=d['degree']
    return {'parent_children': children[1:],
    'root_append': roots+[c],
    'degree': degree-1,
    'child_parent': None,
    'mark': False,
    'descendants': d["descendants"]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101, 102]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101, 102]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101, 102, 103]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101, 102, 103]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101, 102, 103, 104]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101, 102, 103, 104]})]][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):
    c=d['child']; p=d['parent']; children=d['children']; roots=d['roots']; degree=d['degree']
    return {'parent_children': [],
    'root_append': roots+[c],
    'degree': degree-1,
    'child_parent': None,
    'mark': False,
    'descendants': d["descendants"]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101, 102]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101, 102]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101, 102, 103]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101, 102, 103]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101, 102, 103, 104]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101, 102, 103, 104]})]][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 cut certificate reports an incorrect parent children.

A Fibonacci cut certificate has child c, parent p, ordered parent children, root ids, parent degree, child mark, and node keys. Cut detaches c, promotes it to the end of roots, clears its mark and parent, and decrements parent degree; it does not erase descendants.

split: open-access


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

N = 1
observations = []
def solve(d):
    c=d['child']; p=d['parent']; children=d['children']; roots=d['roots']; degree=d['degree']
    return {'parent_children': [x for x in children if x!=c],
    'root_append': [c],
    'degree': degree-1,
    'child_parent': None,
    'mark': False,
    'descendants': d["descendants"]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101, 102]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101, 102]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101, 102, 103]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101, 102, 103]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101, 102, 103, 104]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101, 102, 103, 104]})]][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):
    c=d['child']; p=d['parent']; children=d['children']; roots=d['roots']; degree=d['degree']
    return {'parent_children': [x for x in children if x!=c],
    'root_append': roots+[p],
    'degree': degree-1,
    'child_parent': None,
    'mark': False,
    'descendants': d["descendants"]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101, 102]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101, 102]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101, 102, 103]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101, 102, 103]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101, 102, 103, 104]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101, 102, 103, 104]})]][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 cut certificate reports an incorrect root append.

A Fibonacci cut certificate has child c, parent p, ordered parent children, root ids, parent degree, child mark, and node keys. Cut detaches c, promotes it to the end of roots, clears its mark and parent, and decrements parent degree; it does not erase descendants.

split: open-access


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

N = 1
observations = []
def solve(d):
    c=d['child']; p=d['parent']; children=d['children']; roots=d['roots']; degree=d['degree']
    return {'parent_children': [x for x in children if x!=c],
    'root_append': roots+[c],
    'degree': degree,
    'child_parent': None,
    'mark': False,
    'descendants': d["descendants"]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101, 102]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101, 102]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101, 102, 103]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101, 102, 103]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101, 102, 103, 104]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101, 102, 103, 104]})]][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):
    c=d['child']; p=d['parent']; children=d['children']; roots=d['roots']; degree=d['degree']
    return {'parent_children': [x for x in children if x!=c],
    'root_append': roots+[c],
    'degree': max(0,degree-2),
    'child_parent': None,
    'mark': False,
    'descendants': d["descendants"]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101, 102]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101, 102]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101, 102, 103]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101, 102, 103]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101, 102, 103, 104]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101, 102, 103, 104]})]][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 cut certificate reports an incorrect degree.

A Fibonacci cut certificate has child c, parent p, ordered parent children, root ids, parent degree, child mark, and node keys. Cut detaches c, promotes it to the end of roots, clears its mark and parent, and decrements parent degree; it does not erase descendants.

split: open-access


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

N = 1
observations = []
def solve(d):
    c=d['child']; p=d['parent']; children=d['children']; roots=d['roots']; degree=d['degree']
    return {'parent_children': [x for x in children if x!=c],
    'root_append': roots+[c],
    'degree': degree-1,
    'child_parent': p,
    'mark': False,
    'descendants': d["descendants"]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101, 102]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101, 102]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101, 102, 103]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101, 102, 103]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101, 102, 103, 104]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101, 102, 103, 104]})]][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):
    c=d['child']; p=d['parent']; children=d['children']; roots=d['roots']; degree=d['degree']
    return {'parent_children': [x for x in children if x!=c],
    'root_append': roots+[c],
    'degree': degree-1,
    'child_parent': c,
    'mark': False,
    'descendants': d["descendants"]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101, 102]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101, 102]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101, 102, 103]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101, 102, 103]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101, 102, 103, 104]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101, 102, 103, 104]})]][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 cut certificate reports an incorrect child parent.

A Fibonacci cut certificate has child c, parent p, ordered parent children, root ids, parent degree, child mark, and node keys. Cut detaches c, promotes it to the end of roots, clears its mark and parent, and decrements parent degree; it does not erase descendants.

split: open-access