FA-39881 / Heap invariants / Open access
Fibonacci degree accepts hidden extra children · case 01
The bounded fibonacci rings certificate reports an incorrect degrees.
ROOT CAUSE
Both underreported and overreported child counts corrupt consolidation.
VERIFIED REPAIR
Derive degrees using [i for i,x in enumerate(a) if x[4]!=len(x[6])] under the stated bounded certificate contract.
Unsuccessful approach: The local patch uses [i for i,x in enumerate(a) if x[4]>len(x[6])] 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[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 fixture | Actual | Expected | Outcome |
|---|---|---|---|
| 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], '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]} | Failed |
| regression certificate 6 | {'backlinks': [[0, 1], [2, 0]], 'degrees': [], '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]} | Failed |
| variant-dependent certificate | {'backlinks': [[0, 1], [2, 0]], 'degrees': [], '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]} | Failed |
SHA-256 / 6a092e748be23e80c7362f0f24b07c7f8293a5c036550cccda6318c7a056c7dd
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[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 fixture | Actual | Expected | Outcome |
|---|---|---|---|
| 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': [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]} | Failed |
| 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 / 9c16fa394ae060310fbe98d53e35bcc61a530603393f36e200fba8d1e45de919
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 fixture | Actual | Expected | Outcome |
|---|---|---|---|
| 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.679764+00:00.
Case digest / 02f778be69deeea54ac587a717b0d02bde51f1b2d83204ed29db87a219818f19