FAILURE MAP
← Case archive

FA-39891 / Heap invariants / Open access

Fibonacci root detection mistakes a self-ring for a root · case 01

The bounded fibonacci rings certificate reports an incorrect root ids.

Verified by executionVariant 1 · 7 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

Singleton child rings are not root lists and leaf roots remain roots.

VERIFIED REPAIR

Derive root ids using [i for i,x in enumerate(a) if x[1]==-1] under the stated bounded certificate contract.

Unsuccessful approach: The local patch uses [i for i,x in enumerate(a) if x[4]>0 and x[1]==-1] and still violates the stated relation.

Case contract

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.

Why this case matters

This isolates an internal heap representation or priority-structure invariant using deterministic finite records.

1 / The failure

Exit 1
"""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)
Boundary fixtureActualExpectedOutcome
regression certificate 1{'backlinks': [], 'degrees': [], 'minimum_valid': True, 'reciprocity': [], 'root_ids': [], 'root_marks': []}{'backlinks': [], 'degrees': [], 'minimum_valid': True, 'reciprocity': [], 'root_ids': [], 'root_marks': []}Passed
regression certificate 2{'backlinks': [], 'degrees': [], 'minimum_valid': True, 'reciprocity': [], 'root_ids': [0], 'root_marks': []}{'backlinks': [], 'degrees': [], 'minimum_valid': True, 'reciprocity': [], 'root_ids': [0], 'root_marks': []}Passed
regression certificate 3{'backlinks': [], 'degrees': [], 'minimum_valid': True, 'reciprocity': [], 'root_ids': [0], 'root_marks': []}{'backlinks': [], 'degrees': [], 'minimum_valid': True, 'reciprocity': [], 'root_ids': [0], 'root_marks': []}Passed
regression certificate 4{'backlinks': [], 'degrees': [], 'minimum_valid': False, 'reciprocity': [], 'root_ids': [], 'root_marks': [0]}{'backlinks': [], 'degrees': [], 'minimum_valid': False, 'reciprocity': [], 'root_ids': [0, 1], 'root_marks': [0]}Failed
regression certificate 5{'backlinks': [[0, 2]], 'degrees': [0, 2], 'minimum_valid': False, 'reciprocity': [1, 2], 'root_ids': [0], 'root_marks': [0, 2]}{'backlinks': [[0, 2]], 'degrees': [0, 2], 'minimum_valid': False, 'reciprocity': [1, 2], 'root_ids': [0, 2], 'root_marks': [0, 2]}Failed
regression certificate 6{'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'minimum_valid': True, 'reciprocity': [0, 1, 2], 'root_ids': [], 'root_marks': [2]}{'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'minimum_valid': True, 'reciprocity': [0, 1, 2], 'root_ids': [0, 2], 'root_marks': [2]}Failed
variant-dependent certificate{'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'minimum_valid': True, 'reciprocity': [0, 1, 2], 'root_ids': [], 'root_marks': [2]}{'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'minimum_valid': True, 'reciprocity': [0, 1, 2], 'root_ids': [0, 2], 'root_marks': [2]}Failed

SHA-256 / 36a6d62cc4fce2f7e9140e968373b6cee924e1a036dfcbc000ee7c077e653d5c

2 / The unsuccessful fix

Exit 1
"""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)
Boundary fixtureActualExpectedOutcome
regression certificate 1{'backlinks': [], 'degrees': [], 'minimum_valid': True, 'reciprocity': [], 'root_ids': [], 'root_marks': []}{'backlinks': [], 'degrees': [], 'minimum_valid': True, 'reciprocity': [], 'root_ids': [], 'root_marks': []}Passed
regression certificate 2{'backlinks': [], 'degrees': [], 'minimum_valid': True, 'reciprocity': [], 'root_ids': [], 'root_marks': []}{'backlinks': [], 'degrees': [], 'minimum_valid': True, 'reciprocity': [], 'root_ids': [0], 'root_marks': []}Failed
regression certificate 3{'backlinks': [], 'degrees': [], 'minimum_valid': True, 'reciprocity': [], 'root_ids': [0], 'root_marks': []}{'backlinks': [], 'degrees': [], 'minimum_valid': True, 'reciprocity': [], 'root_ids': [0], 'root_marks': []}Passed
regression certificate 4{'backlinks': [], 'degrees': [], 'minimum_valid': False, 'reciprocity': [], 'root_ids': [], 'root_marks': [0]}{'backlinks': [], 'degrees': [], 'minimum_valid': False, 'reciprocity': [], 'root_ids': [0, 1], 'root_marks': [0]}Failed
regression certificate 5{'backlinks': [[0, 2]], 'degrees': [0, 2], 'minimum_valid': False, 'reciprocity': [1, 2], 'root_ids': [0, 2], 'root_marks': [0, 2]}{'backlinks': [[0, 2]], 'degrees': [0, 2], 'minimum_valid': False, 'reciprocity': [1, 2], 'root_ids': [0, 2], 'root_marks': [0, 2]}Passed
regression certificate 6{'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'minimum_valid': True, 'reciprocity': [0, 1, 2], 'root_ids': [0, 2], 'root_marks': [2]}{'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'minimum_valid': True, 'reciprocity': [0, 1, 2], 'root_ids': [0, 2], 'root_marks': [2]}Passed
variant-dependent certificate{'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'minimum_valid': True, 'reciprocity': [0, 1, 2], 'root_ids': [0, 2], 'root_marks': [2]}{'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'minimum_valid': True, 'reciprocity': [0, 1, 2], 'root_ids': [0, 2], 'root_marks': [2]}Passed

SHA-256 / be246ed9d72a78b3fca6b70b44250aad7f65123f2de8481aed71347600ebcd48

3 / The verified repair

Exit 0
"""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)
Boundary fixtureActualExpectedOutcome
regression certificate 1{'backlinks': [], 'degrees': [], 'minimum_valid': True, 'reciprocity': [], 'root_ids': [], 'root_marks': []}{'backlinks': [], 'degrees': [], 'minimum_valid': True, 'reciprocity': [], 'root_ids': [], 'root_marks': []}Passed
regression certificate 2{'backlinks': [], 'degrees': [], 'minimum_valid': True, 'reciprocity': [], 'root_ids': [0], 'root_marks': []}{'backlinks': [], 'degrees': [], 'minimum_valid': True, 'reciprocity': [], 'root_ids': [0], 'root_marks': []}Passed
regression certificate 3{'backlinks': [], 'degrees': [], 'minimum_valid': True, 'reciprocity': [], 'root_ids': [0], 'root_marks': []}{'backlinks': [], 'degrees': [], 'minimum_valid': True, 'reciprocity': [], 'root_ids': [0], 'root_marks': []}Passed
regression certificate 4{'backlinks': [], 'degrees': [], 'minimum_valid': False, 'reciprocity': [], 'root_ids': [0, 1], 'root_marks': [0]}{'backlinks': [], 'degrees': [], 'minimum_valid': False, 'reciprocity': [], 'root_ids': [0, 1], 'root_marks': [0]}Passed
regression certificate 5{'backlinks': [[0, 2]], 'degrees': [0, 2], 'minimum_valid': False, 'reciprocity': [1, 2], 'root_ids': [0, 2], 'root_marks': [0, 2]}{'backlinks': [[0, 2]], 'degrees': [0, 2], 'minimum_valid': False, 'reciprocity': [1, 2], 'root_ids': [0, 2], 'root_marks': [0, 2]}Passed
regression certificate 6{'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'minimum_valid': True, 'reciprocity': [0, 1, 2], 'root_ids': [0, 2], 'root_marks': [2]}{'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'minimum_valid': True, 'reciprocity': [0, 1, 2], 'root_ids': [0, 2], 'root_marks': [2]}Passed
variant-dependent certificate{'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'minimum_valid': True, 'reciprocity': [0, 1, 2], 'root_ids': [0, 2], 'root_marks': [2]}{'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'minimum_valid': True, 'reciprocity': [0, 1, 2], 'root_ids': [0, 2], 'root_marks': [2]}Passed

SHA-256 / 98b9b085ea8e95b93b4acbd57a088b174d4d9092298dde96afeb44994d4e7b17

Verification & scope

A stipulated offline diagnostic model; it does not implement a production allocator, concurrency protocol, or complete heap library. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.

Observations recorded using Python 3.12.14 at 2026-09-29T14:43:25.746722+00:00.

Case digest / add23271c171907a4685940501a98ade866dd89baf715bc6258f5b36afc264fc