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

N = 1
observations = []
def solve(d):
    a=d['nodes']; m=d['minimum']; n=len(a)
    return {'reciprocity': [i for i,x in enumerate(a) if a[x[2]][3]!=i or a[x[3]][2]!=i],
    'backlinks': [[i,j] for i,x in enumerate(a) for j in x[6] if a[j][1]!=i],
    'degrees': [i for i,x in enumerate(a) if x[4]!=len(x[6])],
    'root_marks': [i for i,x in enumerate(a) if x[1]!=-1 and x[5]],
    'root_ids': [i for i,x in enumerate(a) if x[1]==-1],
    'minimum_valid': m is None if not a else (m is not None and a[m][1]==-1 and all(a[m][0]<=x[0] for x in a if x[1]==-1))}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[10, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})], [({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[11, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})], [({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[12, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})], [({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[13, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})], [({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[14, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

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

N = 1
observations = []
def solve(d):
    a=d['nodes']; m=d['minimum']; n=len(a)
    return {'reciprocity': [i for i,x in enumerate(a) if a[x[2]][3]!=i or a[x[3]][2]!=i],
    'backlinks': [[i,j] for i,x in enumerate(a) for j in x[6] if a[j][1]!=i],
    'degrees': [i for i,x in enumerate(a) if x[4]!=len(x[6])],
    'root_marks': [i for i,x in enumerate(a) if x[1]==-1 and x[5] and x[4]>0],
    'root_ids': [i for i,x in enumerate(a) if x[1]==-1],
    'minimum_valid': m is None if not a else (m is not None and a[m][1]==-1 and all(a[m][0]<=x[0] for x in a if x[1]==-1))}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[10, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})], [({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[11, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})], [({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[12, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})], [({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[13, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})], [({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[14, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})]][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 rings certificate reports an incorrect root marks.

A finite Fibonacci-ring certificate stores nodes [key,parent,left,right,degree,mark,children]. All references are in range or parent=-1. Report broken circular-link reciprocity, parent-child backlinks, degree mismatch, marked roots, roots, and designated minimum validity.

split: open-access


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

N = 1
observations = []
def solve(d):
    a=d['nodes']; m=d['minimum']; n=len(a)
    return {'reciprocity': [i for i,x in enumerate(a) if a[x[2]][3]!=i or a[x[3]][2]!=i],
    'backlinks': [[i,j] for i,x in enumerate(a) for j in x[6] if a[j][1]!=i],
    'degrees': [i for i,x in enumerate(a) if x[4]!=len(x[6])],
    'root_marks': [i for i,x in enumerate(a) if x[1]==-1 and x[5]],
    'root_ids': [i for i,x in enumerate(a) if x[2]==i and x[3]==i],
    'minimum_valid': m is None if not a else (m is not None and a[m][1]==-1 and all(a[m][0]<=x[0] for x in a if x[1]==-1))}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[10, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})], [({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[11, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})], [({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[12, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})], [({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[13, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})], [({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[14, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})]][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):
    a=d['nodes']; m=d['minimum']; n=len(a)
    return {'reciprocity': [i for i,x in enumerate(a) if a[x[2]][3]!=i or a[x[3]][2]!=i],
    'backlinks': [[i,j] for i,x in enumerate(a) for j in x[6] if a[j][1]!=i],
    'degrees': [i for i,x in enumerate(a) if x[4]!=len(x[6])],
    'root_marks': [i for i,x in enumerate(a) if x[1]==-1 and x[5]],
    'root_ids': [i for i,x in enumerate(a) if x[4]>0 and x[1]==-1],
    'minimum_valid': m is None if not a else (m is not None and a[m][1]==-1 and all(a[m][0]<=x[0] for x in a if x[1]==-1))}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[10, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})], [({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[11, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})], [({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[12, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})], [({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[13, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})], [({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[14, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})]][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 rings certificate reports an incorrect root ids.

A finite Fibonacci-ring certificate stores nodes [key,parent,left,right,degree,mark,children]. All references are in range or parent=-1. Report broken circular-link reciprocity, parent-child backlinks, degree mismatch, marked roots, roots, and designated minimum validity.

split: open-access


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

N = 1
observations = []
def solve(d):
    a=d['nodes']; m=d['minimum']; n=len(a)
    return {'reciprocity': [i for i,x in enumerate(a) if a[x[2]][3]!=i or a[x[3]][2]!=i],
    'backlinks': [[i,j] for i,x in enumerate(a) for j in x[6] if a[j][1]!=i],
    'degrees': [i for i,x in enumerate(a) if x[4]!=len(x[6])],
    'root_marks': [i for i,x in enumerate(a) if x[1]==-1 and x[5]],
    'root_ids': [i for i,x in enumerate(a) if x[1]==-1],
    'minimum_valid': m is None if not a else (m is not None and all(a[m][0]<=x[0] for x in a))}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[10, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})], [({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[11, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})], [({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[12, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})], [({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[13, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})], [({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[14, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

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

N = 1
observations = []
def solve(d):
    a=d['nodes']; m=d['minimum']; n=len(a)
    return {'reciprocity': [i for i,x in enumerate(a) if a[x[2]][3]!=i or a[x[3]][2]!=i],
    'backlinks': [[i,j] for i,x in enumerate(a) for j in x[6] if a[j][1]!=i],
    'degrees': [i for i,x in enumerate(a) if x[4]!=len(x[6])],
    'root_marks': [i for i,x in enumerate(a) if x[1]==-1 and x[5]],
    'root_ids': [i for i,x in enumerate(a) if x[1]==-1],
    'minimum_valid': m is None if not a else (m is not None and a[m][1]==-1)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[10, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})], [({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[11, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})], [({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[12, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})], [({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[13, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})], [({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[14, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})]][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 rings certificate reports an incorrect minimum valid.

A finite Fibonacci-ring certificate stores nodes [key,parent,left,right,degree,mark,children]. All references are in range or parent=-1. Report broken circular-link reciprocity, parent-child backlinks, degree mismatch, marked roots, roots, and designated minimum validity.

split: open-access


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

N = 1
observations = []
def solve(d):
    a=d['nodes']; root=d['root']
    def rank(i): return -1 if i==-1 else a[i][3]
    spine=[]; q=root
    while q!=-1 and q not in spine:
        spine.append(q); q=a[q][2]
    return {'heap_edges': [[i,x[1]] for i,x in enumerate(a) if x[1]!=-1 and a[x[1]][0]<x[0]],
    'rank_recurrence': [i for i,x in enumerate(a) if x[3]!=1+min(rank(x[1]),rank(x[2]))],
    'orientation': [i for i,x in enumerate(a) if rank(x[1])<rank(x[2])],
    'leaves': [i for i,x in enumerate(a) if x[1]==-1 and x[2]==-1],
    'right_orphans': [i for i,x in enumerate(a) if x[1]==-1 and x[2]!=-1],
    'spine_length': len(spine)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'nodes': [], 'root': -1}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [], 'right_orphans': [], 'spine_length': 0}), ({'nodes': [[4, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [0], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[1, 1, 2, 1], [5, -1, -1, 0], [7, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1, 2], 'right_orphans': [], 'spine_length': 2}), ({'nodes': [[5, 1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[8, -1, 1, 1], [2, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 1]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1], 'right_orphans': [0], 'spine_length': 2}), ({'nodes': [[2, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3}), ({'nodes': [[3, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3})], [({'nodes': [], 'root': -1}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [], 'right_orphans': [], 'spine_length': 0}), ({'nodes': [[4, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [0], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[1, 1, 2, 1], [5, -1, -1, 0], [7, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1, 2], 'right_orphans': [], 'spine_length': 2}), ({'nodes': [[5, 1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[8, -1, 1, 1], [2, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 1]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1], 'right_orphans': [0], 'spine_length': 2}), ({'nodes': [[2, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3}), ({'nodes': [[4, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3})], [({'nodes': [], 'root': -1}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [], 'right_orphans': [], 'spine_length': 0}), ({'nodes': [[4, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [0], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[1, 1, 2, 1], [5, -1, -1, 0], [7, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1, 2], 'right_orphans': [], 'spine_length': 2}), ({'nodes': [[5, 1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[8, -1, 1, 1], [2, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 1]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1], 'right_orphans': [0], 'spine_length': 2}), ({'nodes': [[2, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3}), ({'nodes': [[5, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3})], [({'nodes': [], 'root': -1}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [], 'right_orphans': [], 'spine_length': 0}), ({'nodes': [[4, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [0], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[1, 1, 2, 1], [5, -1, -1, 0], [7, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1, 2], 'right_orphans': [], 'spine_length': 2}), ({'nodes': [[5, 1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[8, -1, 1, 1], [2, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 1]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1], 'right_orphans': [0], 'spine_length': 2}), ({'nodes': [[2, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3}), ({'nodes': [[6, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3})], [({'nodes': [], 'root': -1}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [], 'right_orphans': [], 'spine_length': 0}), ({'nodes': [[4, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [0], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[1, 1, 2, 1], [5, -1, -1, 0], [7, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1, 2], 'right_orphans': [], 'spine_length': 2}), ({'nodes': [[5, 1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[8, -1, 1, 1], [2, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 1]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1], 'right_orphans': [0], 'spine_length': 2}), ({'nodes': [[2, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3}), ({'nodes': [[7, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

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

N = 1
observations = []
def solve(d):
    a=d['nodes']; root=d['root']
    def rank(i): return -1 if i==-1 else a[i][3]
    spine=[]; q=root
    while q!=-1 and q not in spine:
        spine.append(q); q=a[q][2]
    return {'heap_edges': [[i,j] for i,x in enumerate(a) for j in x[1:3] if j!=-1 and a[j][0]<=x[0]],
    'rank_recurrence': [i for i,x in enumerate(a) if x[3]!=1+min(rank(x[1]),rank(x[2]))],
    'orientation': [i for i,x in enumerate(a) if rank(x[1])<rank(x[2])],
    'leaves': [i for i,x in enumerate(a) if x[1]==-1 and x[2]==-1],
    'right_orphans': [i for i,x in enumerate(a) if x[1]==-1 and x[2]!=-1],
    'spine_length': len(spine)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'nodes': [], 'root': -1}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [], 'right_orphans': [], 'spine_length': 0}), ({'nodes': [[4, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [0], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[1, 1, 2, 1], [5, -1, -1, 0], [7, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1, 2], 'right_orphans': [], 'spine_length': 2}), ({'nodes': [[5, 1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[8, -1, 1, 1], [2, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 1]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1], 'right_orphans': [0], 'spine_length': 2}), ({'nodes': [[2, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3}), ({'nodes': [[3, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3})], [({'nodes': [], 'root': -1}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [], 'right_orphans': [], 'spine_length': 0}), ({'nodes': [[4, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [0], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[1, 1, 2, 1], [5, -1, -1, 0], [7, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1, 2], 'right_orphans': [], 'spine_length': 2}), ({'nodes': [[5, 1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[8, -1, 1, 1], [2, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 1]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1], 'right_orphans': [0], 'spine_length': 2}), ({'nodes': [[2, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3}), ({'nodes': [[4, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3})], [({'nodes': [], 'root': -1}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [], 'right_orphans': [], 'spine_length': 0}), ({'nodes': [[4, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [0], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[1, 1, 2, 1], [5, -1, -1, 0], [7, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1, 2], 'right_orphans': [], 'spine_length': 2}), ({'nodes': [[5, 1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[8, -1, 1, 1], [2, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 1]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1], 'right_orphans': [0], 'spine_length': 2}), ({'nodes': [[2, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3}), ({'nodes': [[5, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3})], [({'nodes': [], 'root': -1}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [], 'right_orphans': [], 'spine_length': 0}), ({'nodes': [[4, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [0], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[1, 1, 2, 1], [5, -1, -1, 0], [7, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1, 2], 'right_orphans': [], 'spine_length': 2}), ({'nodes': [[5, 1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[8, -1, 1, 1], [2, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 1]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1], 'right_orphans': [0], 'spine_length': 2}), ({'nodes': [[2, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3}), ({'nodes': [[6, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3})], [({'nodes': [], 'root': -1}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [], 'right_orphans': [], 'spine_length': 0}), ({'nodes': [[4, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [0], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[1, 1, 2, 1], [5, -1, -1, 0], [7, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1, 2], 'right_orphans': [], 'spine_length': 2}), ({'nodes': [[5, 1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[8, -1, 1, 1], [2, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 1]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1], 'right_orphans': [0], 'spine_length': 2}), ({'nodes': [[2, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3}), ({'nodes': [[7, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3})]][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 leftist ranks certificate reports an incorrect heap edges.

A leftist-tree certificate has nodes [key,left,right,stored_npl] with missing child=-1 and valid references. Null-path length of null is -1. Report local heap-edge violations, rank recurrence violations, leftist orientation violations, leaves, unary-right nodes, and root-to-right-spine length; spine traversal stops on repeated node.

split: open-access


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

N = 1
observations = []
def solve(d):
    a=d['nodes']; root=d['root']
    def rank(i): return -1 if i==-1 else a[i][3]
    spine=[]; q=root
    while q!=-1 and q not in spine:
        spine.append(q); q=a[q][2]
    return {'heap_edges': [[i,j] for i,x in enumerate(a) for j in x[1:3] if j!=-1 and a[j][0]<x[0]],
    'rank_recurrence': [i for i,x in enumerate(a) if x[3]!=1+max(rank(x[1]),rank(x[2]))],
    'orientation': [i for i,x in enumerate(a) if rank(x[1])<rank(x[2])],
    'leaves': [i for i,x in enumerate(a) if x[1]==-1 and x[2]==-1],
    'right_orphans': [i for i,x in enumerate(a) if x[1]==-1 and x[2]!=-1],
    'spine_length': len(spine)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'nodes': [], 'root': -1}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [], 'right_orphans': [], 'spine_length': 0}), ({'nodes': [[4, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [0], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[1, 1, 2, 1], [5, -1, -1, 0], [7, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1, 2], 'right_orphans': [], 'spine_length': 2}), ({'nodes': [[5, 1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[8, -1, 1, 1], [2, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 1]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1], 'right_orphans': [0], 'spine_length': 2}), ({'nodes': [[2, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3}), ({'nodes': [[3, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3})], [({'nodes': [], 'root': -1}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [], 'right_orphans': [], 'spine_length': 0}), ({'nodes': [[4, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [0], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[1, 1, 2, 1], [5, -1, -1, 0], [7, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1, 2], 'right_orphans': [], 'spine_length': 2}), ({'nodes': [[5, 1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[8, -1, 1, 1], [2, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 1]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1], 'right_orphans': [0], 'spine_length': 2}), ({'nodes': [[2, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3}), ({'nodes': [[4, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3})], [({'nodes': [], 'root': -1}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [], 'right_orphans': [], 'spine_length': 0}), ({'nodes': [[4, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [0], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[1, 1, 2, 1], [5, -1, -1, 0], [7, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1, 2], 'right_orphans': [], 'spine_length': 2}), ({'nodes': [[5, 1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[8, -1, 1, 1], [2, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 1]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1], 'right_orphans': [0], 'spine_length': 2}), ({'nodes': [[2, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3}), ({'nodes': [[5, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3})], [({'nodes': [], 'root': -1}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [], 'right_orphans': [], 'spine_length': 0}), ({'nodes': [[4, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [0], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[1, 1, 2, 1], [5, -1, -1, 0], [7, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1, 2], 'right_orphans': [], 'spine_length': 2}), ({'nodes': [[5, 1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[8, -1, 1, 1], [2, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 1]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1], 'right_orphans': [0], 'spine_length': 2}), ({'nodes': [[2, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3}), ({'nodes': [[6, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3})], [({'nodes': [], 'root': -1}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [], 'right_orphans': [], 'spine_length': 0}), ({'nodes': [[4, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [0], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[1, 1, 2, 1], [5, -1, -1, 0], [7, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1, 2], 'right_orphans': [], 'spine_length': 2}), ({'nodes': [[5, 1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[8, -1, 1, 1], [2, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 1]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1], 'right_orphans': [0], 'spine_length': 2}), ({'nodes': [[2, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3}), ({'nodes': [[7, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

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

N = 1
observations = []
def solve(d):
    a=d['nodes']; root=d['root']
    def rank(i): return -1 if i==-1 else a[i][3]
    spine=[]; q=root
    while q!=-1 and q not in spine:
        spine.append(q); q=a[q][2]
    return {'heap_edges': [[i,j] for i,x in enumerate(a) for j in x[1:3] if j!=-1 and a[j][0]<x[0]],
    'rank_recurrence': [i for i,x in enumerate(a) if x[3]!=min(rank(x[1]),rank(x[2]))],
    'orientation': [i for i,x in enumerate(a) if rank(x[1])<rank(x[2])],
    'leaves': [i for i,x in enumerate(a) if x[1]==-1 and x[2]==-1],
    'right_orphans': [i for i,x in enumerate(a) if x[1]==-1 and x[2]!=-1],
    'spine_length': len(spine)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'nodes': [], 'root': -1}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [], 'right_orphans': [], 'spine_length': 0}), ({'nodes': [[4, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [0], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[1, 1, 2, 1], [5, -1, -1, 0], [7, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1, 2], 'right_orphans': [], 'spine_length': 2}), ({'nodes': [[5, 1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[8, -1, 1, 1], [2, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 1]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1], 'right_orphans': [0], 'spine_length': 2}), ({'nodes': [[2, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3}), ({'nodes': [[3, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3})], [({'nodes': [], 'root': -1}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [], 'right_orphans': [], 'spine_length': 0}), ({'nodes': [[4, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [0], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[1, 1, 2, 1], [5, -1, -1, 0], [7, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1, 2], 'right_orphans': [], 'spine_length': 2}), ({'nodes': [[5, 1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[8, -1, 1, 1], [2, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 1]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1], 'right_orphans': [0], 'spine_length': 2}), ({'nodes': [[2, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3}), ({'nodes': [[4, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3})], [({'nodes': [], 'root': -1}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [], 'right_orphans': [], 'spine_length': 0}), ({'nodes': [[4, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [0], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[1, 1, 2, 1], [5, -1, -1, 0], [7, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1, 2], 'right_orphans': [], 'spine_length': 2}), ({'nodes': [[5, 1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[8, -1, 1, 1], [2, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 1]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1], 'right_orphans': [0], 'spine_length': 2}), ({'nodes': [[2, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3}), ({'nodes': [[5, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3})], [({'nodes': [], 'root': -1}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [], 'right_orphans': [], 'spine_length': 0}), ({'nodes': [[4, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [0], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[1, 1, 2, 1], [5, -1, -1, 0], [7, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1, 2], 'right_orphans': [], 'spine_length': 2}), ({'nodes': [[5, 1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[8, -1, 1, 1], [2, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 1]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1], 'right_orphans': [0], 'spine_length': 2}), ({'nodes': [[2, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3}), ({'nodes': [[6, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3})], [({'nodes': [], 'root': -1}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [], 'right_orphans': [], 'spine_length': 0}), ({'nodes': [[4, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [0], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[1, 1, 2, 1], [5, -1, -1, 0], [7, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1, 2], 'right_orphans': [], 'spine_length': 2}), ({'nodes': [[5, 1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [], 'rank_recurrence': [], 'orientation': [], 'leaves': [1], 'right_orphans': [], 'spine_length': 1}), ({'nodes': [[8, -1, 1, 1], [2, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 1]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1], 'right_orphans': [0], 'spine_length': 2}), ({'nodes': [[2, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3}), ({'nodes': [[7, 1, 2, 2], [9, -1, -1, 0], [1, 3, 4, 1], [4, -1, -1, 0], [5, -1, -1, 0]], 'root': 0}, {'heap_edges': [[0, 2]], 'rank_recurrence': [0], 'orientation': [0], 'leaves': [1, 3, 4], 'right_orphans': [], 'spine_length': 3})]][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 leftist ranks certificate reports an incorrect rank recurrence.

A leftist-tree certificate has nodes [key,left,right,stored_npl] with missing child=-1 and valid references. Null-path length of null is -1. Report local heap-edge violations, rank recurrence violations, leftist orientation violations, leaves, unary-right nodes, and root-to-right-spine length; spine traversal stops on repeated node.

split: open-access