FAILURE MAP
← Case archive

FA-40531 / Heap invariants / Open access

Weak heap distinguished ancestor can be above the ordinary parent · case 01

The bounded weak ancestor certificate reports an incorrect ancestor.

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

ROOT CAUSE

Weak heap distinguished ancestor can be above the ordinary parent.

VERIFIED REPAIR

Derive ancestor using ancestor under the stated bounded certificate contract.

Unsuccessful approach: The local patch uses None if start==0 else (start-1)//2 and still violates the stated relation.

Case contract

A weak heap stores reverse bits r in a zero-based array. For nonroot node j, climb while j is a left child under its parent reverse bit: (j mod 2)==r[j//2]. Its distinguished ancestor is j//2 after climbing; zero has none. Report ancestor, climb path, climb count, stopping child, orientation bit, and whether direct parent suffices.

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):
    r=d['reverse']; start=d['node']; j=start; path=[]
    while j>0 and j%2==r[j//2]:
        path.append(j); j//=2
    ancestor=None if start==0 else j//2
    return {'ancestor': None if start==0 else start//2,
    'path': path,
    'cost': len(path),
    'stop': j,
    'orientation': None if start==0 else r[j//2],
    'direct': start!=0 and ancestor==start//2}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'reverse': [0], 'node': 0}, {'ancestor': None, 'path': [], 'cost': 0, 'stop': 0, 'orientation': None, 'direct': False}), ({'reverse': [0, 0], 'node': 1}, {'ancestor': 0, 'path': [], 'cost': 0, 'stop': 1, 'orientation': 0, 'direct': True}), ({'reverse': [0, 0, 0, 0, 0, 0, 0, 0], 'node': 4}, {'ancestor': 0, 'path': [4, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 0, 1, 0, 0, 0, 0], 'node': 7}, {'ancestor': 0, 'path': [7, 3], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 0, 1, 0, 0, 0, 0, 0], 'node': 5}, {'ancestor': 0, 'path': [5, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 6}, {'ancestor': 3, 'path': [], 'cost': 0, 'stop': 6, 'orientation': 1, 'direct': True}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 2}, {'ancestor': 1, 'path': [], 'cost': 0, 'stop': 2, 'orientation': 1, 'direct': True})], [({'reverse': [0], 'node': 0}, {'ancestor': None, 'path': [], 'cost': 0, 'stop': 0, 'orientation': None, 'direct': False}), ({'reverse': [0, 0], 'node': 1}, {'ancestor': 0, 'path': [], 'cost': 0, 'stop': 1, 'orientation': 0, 'direct': True}), ({'reverse': [0, 0, 0, 0, 0, 0, 0, 0], 'node': 4}, {'ancestor': 0, 'path': [4, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 0, 1, 0, 0, 0, 0], 'node': 7}, {'ancestor': 0, 'path': [7, 3], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 0, 1, 0, 0, 0, 0, 0], 'node': 5}, {'ancestor': 0, 'path': [5, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 6}, {'ancestor': 3, 'path': [], 'cost': 0, 'stop': 6, 'orientation': 1, 'direct': True}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 3}, {'ancestor': 0, 'path': [3], 'cost': 1, 'stop': 1, 'orientation': 0, 'direct': False})], [({'reverse': [0], 'node': 0}, {'ancestor': None, 'path': [], 'cost': 0, 'stop': 0, 'orientation': None, 'direct': False}), ({'reverse': [0, 0], 'node': 1}, {'ancestor': 0, 'path': [], 'cost': 0, 'stop': 1, 'orientation': 0, 'direct': True}), ({'reverse': [0, 0, 0, 0, 0, 0, 0, 0], 'node': 4}, {'ancestor': 0, 'path': [4, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 0, 1, 0, 0, 0, 0], 'node': 7}, {'ancestor': 0, 'path': [7, 3], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 0, 1, 0, 0, 0, 0, 0], 'node': 5}, {'ancestor': 0, 'path': [5, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 6}, {'ancestor': 3, 'path': [], 'cost': 0, 'stop': 6, 'orientation': 1, 'direct': True}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 4}, {'ancestor': 2, 'path': [], 'cost': 0, 'stop': 4, 'orientation': 1, 'direct': True})], [({'reverse': [0], 'node': 0}, {'ancestor': None, 'path': [], 'cost': 0, 'stop': 0, 'orientation': None, 'direct': False}), ({'reverse': [0, 0], 'node': 1}, {'ancestor': 0, 'path': [], 'cost': 0, 'stop': 1, 'orientation': 0, 'direct': True}), ({'reverse': [0, 0, 0, 0, 0, 0, 0, 0], 'node': 4}, {'ancestor': 0, 'path': [4, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 0, 1, 0, 0, 0, 0], 'node': 7}, {'ancestor': 0, 'path': [7, 3], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 0, 1, 0, 0, 0, 0, 0], 'node': 5}, {'ancestor': 0, 'path': [5, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 6}, {'ancestor': 3, 'path': [], 'cost': 0, 'stop': 6, 'orientation': 1, 'direct': True}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 5}, {'ancestor': 1, 'path': [5], 'cost': 1, 'stop': 2, 'orientation': 1, 'direct': False})], [({'reverse': [0], 'node': 0}, {'ancestor': None, 'path': [], 'cost': 0, 'stop': 0, 'orientation': None, 'direct': False}), ({'reverse': [0, 0], 'node': 1}, {'ancestor': 0, 'path': [], 'cost': 0, 'stop': 1, 'orientation': 0, 'direct': True}), ({'reverse': [0, 0, 0, 0, 0, 0, 0, 0], 'node': 4}, {'ancestor': 0, 'path': [4, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 0, 1, 0, 0, 0, 0], 'node': 7}, {'ancestor': 0, 'path': [7, 3], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 0, 1, 0, 0, 0, 0, 0], 'node': 5}, {'ancestor': 0, 'path': [5, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 6}, {'ancestor': 3, 'path': [], 'cost': 0, 'stop': 6, 'orientation': 1, 'direct': True}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 6}, {'ancestor': 3, 'path': [], 'cost': 0, 'stop': 6, 'orientation': 1, 'direct': 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{'ancestor': None, 'cost': 0, 'direct': False, 'orientation': None, 'path': [], 'stop': 0}{'ancestor': None, 'cost': 0, 'direct': False, 'orientation': None, 'path': [], 'stop': 0}Passed
regression certificate 2{'ancestor': 0, 'cost': 0, 'direct': True, 'orientation': 0, 'path': [], 'stop': 1}{'ancestor': 0, 'cost': 0, 'direct': True, 'orientation': 0, 'path': [], 'stop': 1}Passed
regression certificate 3{'ancestor': 2, 'cost': 2, 'direct': False, 'orientation': 0, 'path': [4, 2], 'stop': 1}{'ancestor': 0, 'cost': 2, 'direct': False, 'orientation': 0, 'path': [4, 2], 'stop': 1}Failed
regression certificate 4{'ancestor': 3, 'cost': 2, 'direct': False, 'orientation': 0, 'path': [7, 3], 'stop': 1}{'ancestor': 0, 'cost': 2, 'direct': False, 'orientation': 0, 'path': [7, 3], 'stop': 1}Failed
regression certificate 5{'ancestor': 2, 'cost': 2, 'direct': False, 'orientation': 0, 'path': [5, 2], 'stop': 1}{'ancestor': 0, 'cost': 2, 'direct': False, 'orientation': 0, 'path': [5, 2], 'stop': 1}Failed
regression certificate 6{'ancestor': 3, 'cost': 0, 'direct': True, 'orientation': 1, 'path': [], 'stop': 6}{'ancestor': 3, 'cost': 0, 'direct': True, 'orientation': 1, 'path': [], 'stop': 6}Passed
variant-dependent certificate{'ancestor': 1, 'cost': 0, 'direct': True, 'orientation': 1, 'path': [], 'stop': 2}{'ancestor': 1, 'cost': 0, 'direct': True, 'orientation': 1, 'path': [], 'stop': 2}Passed

SHA-256 / 00d327efbb7c0f7d44e99d8b078cef342b152935f0147d3229abd9f0fe437a5b

2 / The unsuccessful fix

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(d):
    r=d['reverse']; start=d['node']; j=start; path=[]
    while j>0 and j%2==r[j//2]:
        path.append(j); j//=2
    ancestor=None if start==0 else j//2
    return {'ancestor': None if start==0 else (start-1)//2,
    'path': path,
    'cost': len(path),
    'stop': j,
    'orientation': None if start==0 else r[j//2],
    'direct': start!=0 and ancestor==start//2}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'reverse': [0], 'node': 0}, {'ancestor': None, 'path': [], 'cost': 0, 'stop': 0, 'orientation': None, 'direct': False}), ({'reverse': [0, 0], 'node': 1}, {'ancestor': 0, 'path': [], 'cost': 0, 'stop': 1, 'orientation': 0, 'direct': True}), ({'reverse': [0, 0, 0, 0, 0, 0, 0, 0], 'node': 4}, {'ancestor': 0, 'path': [4, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 0, 1, 0, 0, 0, 0], 'node': 7}, {'ancestor': 0, 'path': [7, 3], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 0, 1, 0, 0, 0, 0, 0], 'node': 5}, {'ancestor': 0, 'path': [5, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 6}, {'ancestor': 3, 'path': [], 'cost': 0, 'stop': 6, 'orientation': 1, 'direct': True}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 2}, {'ancestor': 1, 'path': [], 'cost': 0, 'stop': 2, 'orientation': 1, 'direct': True})], [({'reverse': [0], 'node': 0}, {'ancestor': None, 'path': [], 'cost': 0, 'stop': 0, 'orientation': None, 'direct': False}), ({'reverse': [0, 0], 'node': 1}, {'ancestor': 0, 'path': [], 'cost': 0, 'stop': 1, 'orientation': 0, 'direct': True}), ({'reverse': [0, 0, 0, 0, 0, 0, 0, 0], 'node': 4}, {'ancestor': 0, 'path': [4, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 0, 1, 0, 0, 0, 0], 'node': 7}, {'ancestor': 0, 'path': [7, 3], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 0, 1, 0, 0, 0, 0, 0], 'node': 5}, {'ancestor': 0, 'path': [5, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 6}, {'ancestor': 3, 'path': [], 'cost': 0, 'stop': 6, 'orientation': 1, 'direct': True}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 3}, {'ancestor': 0, 'path': [3], 'cost': 1, 'stop': 1, 'orientation': 0, 'direct': False})], [({'reverse': [0], 'node': 0}, {'ancestor': None, 'path': [], 'cost': 0, 'stop': 0, 'orientation': None, 'direct': False}), ({'reverse': [0, 0], 'node': 1}, {'ancestor': 0, 'path': [], 'cost': 0, 'stop': 1, 'orientation': 0, 'direct': True}), ({'reverse': [0, 0, 0, 0, 0, 0, 0, 0], 'node': 4}, {'ancestor': 0, 'path': [4, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 0, 1, 0, 0, 0, 0], 'node': 7}, {'ancestor': 0, 'path': [7, 3], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 0, 1, 0, 0, 0, 0, 0], 'node': 5}, {'ancestor': 0, 'path': [5, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 6}, {'ancestor': 3, 'path': [], 'cost': 0, 'stop': 6, 'orientation': 1, 'direct': True}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 4}, {'ancestor': 2, 'path': [], 'cost': 0, 'stop': 4, 'orientation': 1, 'direct': True})], [({'reverse': [0], 'node': 0}, {'ancestor': None, 'path': [], 'cost': 0, 'stop': 0, 'orientation': None, 'direct': False}), ({'reverse': [0, 0], 'node': 1}, {'ancestor': 0, 'path': [], 'cost': 0, 'stop': 1, 'orientation': 0, 'direct': True}), ({'reverse': [0, 0, 0, 0, 0, 0, 0, 0], 'node': 4}, {'ancestor': 0, 'path': [4, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 0, 1, 0, 0, 0, 0], 'node': 7}, {'ancestor': 0, 'path': [7, 3], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 0, 1, 0, 0, 0, 0, 0], 'node': 5}, {'ancestor': 0, 'path': [5, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 6}, {'ancestor': 3, 'path': [], 'cost': 0, 'stop': 6, 'orientation': 1, 'direct': True}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 5}, {'ancestor': 1, 'path': [5], 'cost': 1, 'stop': 2, 'orientation': 1, 'direct': False})], [({'reverse': [0], 'node': 0}, {'ancestor': None, 'path': [], 'cost': 0, 'stop': 0, 'orientation': None, 'direct': False}), ({'reverse': [0, 0], 'node': 1}, {'ancestor': 0, 'path': [], 'cost': 0, 'stop': 1, 'orientation': 0, 'direct': True}), ({'reverse': [0, 0, 0, 0, 0, 0, 0, 0], 'node': 4}, {'ancestor': 0, 'path': [4, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 0, 1, 0, 0, 0, 0], 'node': 7}, {'ancestor': 0, 'path': [7, 3], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 0, 1, 0, 0, 0, 0, 0], 'node': 5}, {'ancestor': 0, 'path': [5, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 6}, {'ancestor': 3, 'path': [], 'cost': 0, 'stop': 6, 'orientation': 1, 'direct': True}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 6}, {'ancestor': 3, 'path': [], 'cost': 0, 'stop': 6, 'orientation': 1, 'direct': 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{'ancestor': None, 'cost': 0, 'direct': False, 'orientation': None, 'path': [], 'stop': 0}{'ancestor': None, 'cost': 0, 'direct': False, 'orientation': None, 'path': [], 'stop': 0}Passed
regression certificate 2{'ancestor': 0, 'cost': 0, 'direct': True, 'orientation': 0, 'path': [], 'stop': 1}{'ancestor': 0, 'cost': 0, 'direct': True, 'orientation': 0, 'path': [], 'stop': 1}Passed
regression certificate 3{'ancestor': 1, 'cost': 2, 'direct': False, 'orientation': 0, 'path': [4, 2], 'stop': 1}{'ancestor': 0, 'cost': 2, 'direct': False, 'orientation': 0, 'path': [4, 2], 'stop': 1}Failed
regression certificate 4{'ancestor': 3, 'cost': 2, 'direct': False, 'orientation': 0, 'path': [7, 3], 'stop': 1}{'ancestor': 0, 'cost': 2, 'direct': False, 'orientation': 0, 'path': [7, 3], 'stop': 1}Failed
regression certificate 5{'ancestor': 2, 'cost': 2, 'direct': False, 'orientation': 0, 'path': [5, 2], 'stop': 1}{'ancestor': 0, 'cost': 2, 'direct': False, 'orientation': 0, 'path': [5, 2], 'stop': 1}Failed
regression certificate 6{'ancestor': 2, 'cost': 0, 'direct': True, 'orientation': 1, 'path': [], 'stop': 6}{'ancestor': 3, 'cost': 0, 'direct': True, 'orientation': 1, 'path': [], 'stop': 6}Failed
variant-dependent certificate{'ancestor': 0, 'cost': 0, 'direct': True, 'orientation': 1, 'path': [], 'stop': 2}{'ancestor': 1, 'cost': 0, 'direct': True, 'orientation': 1, 'path': [], 'stop': 2}Failed

SHA-256 / 92fec6f62df5812492bd857cccb3f3953cc9c0f5112c70b035aeada311415efb

3 / The verified repair

Exit 0
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(d):
    r=d['reverse']; start=d['node']; j=start; path=[]
    while j>0 and j%2==r[j//2]:
        path.append(j); j//=2
    ancestor=None if start==0 else j//2
    return {'ancestor': ancestor,
    'path': path,
    'cost': len(path),
    'stop': j,
    'orientation': None if start==0 else r[j//2],
    'direct': start!=0 and ancestor==start//2}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'reverse': [0], 'node': 0}, {'ancestor': None, 'path': [], 'cost': 0, 'stop': 0, 'orientation': None, 'direct': False}), ({'reverse': [0, 0], 'node': 1}, {'ancestor': 0, 'path': [], 'cost': 0, 'stop': 1, 'orientation': 0, 'direct': True}), ({'reverse': [0, 0, 0, 0, 0, 0, 0, 0], 'node': 4}, {'ancestor': 0, 'path': [4, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 0, 1, 0, 0, 0, 0], 'node': 7}, {'ancestor': 0, 'path': [7, 3], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 0, 1, 0, 0, 0, 0, 0], 'node': 5}, {'ancestor': 0, 'path': [5, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 6}, {'ancestor': 3, 'path': [], 'cost': 0, 'stop': 6, 'orientation': 1, 'direct': True}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 2}, {'ancestor': 1, 'path': [], 'cost': 0, 'stop': 2, 'orientation': 1, 'direct': True})], [({'reverse': [0], 'node': 0}, {'ancestor': None, 'path': [], 'cost': 0, 'stop': 0, 'orientation': None, 'direct': False}), ({'reverse': [0, 0], 'node': 1}, {'ancestor': 0, 'path': [], 'cost': 0, 'stop': 1, 'orientation': 0, 'direct': True}), ({'reverse': [0, 0, 0, 0, 0, 0, 0, 0], 'node': 4}, {'ancestor': 0, 'path': [4, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 0, 1, 0, 0, 0, 0], 'node': 7}, {'ancestor': 0, 'path': [7, 3], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 0, 1, 0, 0, 0, 0, 0], 'node': 5}, {'ancestor': 0, 'path': [5, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 6}, {'ancestor': 3, 'path': [], 'cost': 0, 'stop': 6, 'orientation': 1, 'direct': True}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 3}, {'ancestor': 0, 'path': [3], 'cost': 1, 'stop': 1, 'orientation': 0, 'direct': False})], [({'reverse': [0], 'node': 0}, {'ancestor': None, 'path': [], 'cost': 0, 'stop': 0, 'orientation': None, 'direct': False}), ({'reverse': [0, 0], 'node': 1}, {'ancestor': 0, 'path': [], 'cost': 0, 'stop': 1, 'orientation': 0, 'direct': True}), ({'reverse': [0, 0, 0, 0, 0, 0, 0, 0], 'node': 4}, {'ancestor': 0, 'path': [4, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 0, 1, 0, 0, 0, 0], 'node': 7}, {'ancestor': 0, 'path': [7, 3], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 0, 1, 0, 0, 0, 0, 0], 'node': 5}, {'ancestor': 0, 'path': [5, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 6}, {'ancestor': 3, 'path': [], 'cost': 0, 'stop': 6, 'orientation': 1, 'direct': True}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 4}, {'ancestor': 2, 'path': [], 'cost': 0, 'stop': 4, 'orientation': 1, 'direct': True})], [({'reverse': [0], 'node': 0}, {'ancestor': None, 'path': [], 'cost': 0, 'stop': 0, 'orientation': None, 'direct': False}), ({'reverse': [0, 0], 'node': 1}, {'ancestor': 0, 'path': [], 'cost': 0, 'stop': 1, 'orientation': 0, 'direct': True}), ({'reverse': [0, 0, 0, 0, 0, 0, 0, 0], 'node': 4}, {'ancestor': 0, 'path': [4, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 0, 1, 0, 0, 0, 0], 'node': 7}, {'ancestor': 0, 'path': [7, 3], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 0, 1, 0, 0, 0, 0, 0], 'node': 5}, {'ancestor': 0, 'path': [5, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 6}, {'ancestor': 3, 'path': [], 'cost': 0, 'stop': 6, 'orientation': 1, 'direct': True}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 5}, {'ancestor': 1, 'path': [5], 'cost': 1, 'stop': 2, 'orientation': 1, 'direct': False})], [({'reverse': [0], 'node': 0}, {'ancestor': None, 'path': [], 'cost': 0, 'stop': 0, 'orientation': None, 'direct': False}), ({'reverse': [0, 0], 'node': 1}, {'ancestor': 0, 'path': [], 'cost': 0, 'stop': 1, 'orientation': 0, 'direct': True}), ({'reverse': [0, 0, 0, 0, 0, 0, 0, 0], 'node': 4}, {'ancestor': 0, 'path': [4, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 0, 1, 0, 0, 0, 0], 'node': 7}, {'ancestor': 0, 'path': [7, 3], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 0, 1, 0, 0, 0, 0, 0], 'node': 5}, {'ancestor': 0, 'path': [5, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 6}, {'ancestor': 3, 'path': [], 'cost': 0, 'stop': 6, 'orientation': 1, 'direct': True}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 6}, {'ancestor': 3, 'path': [], 'cost': 0, 'stop': 6, 'orientation': 1, 'direct': 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{'ancestor': None, 'cost': 0, 'direct': False, 'orientation': None, 'path': [], 'stop': 0}{'ancestor': None, 'cost': 0, 'direct': False, 'orientation': None, 'path': [], 'stop': 0}Passed
regression certificate 2{'ancestor': 0, 'cost': 0, 'direct': True, 'orientation': 0, 'path': [], 'stop': 1}{'ancestor': 0, 'cost': 0, 'direct': True, 'orientation': 0, 'path': [], 'stop': 1}Passed
regression certificate 3{'ancestor': 0, 'cost': 2, 'direct': False, 'orientation': 0, 'path': [4, 2], 'stop': 1}{'ancestor': 0, 'cost': 2, 'direct': False, 'orientation': 0, 'path': [4, 2], 'stop': 1}Passed
regression certificate 4{'ancestor': 0, 'cost': 2, 'direct': False, 'orientation': 0, 'path': [7, 3], 'stop': 1}{'ancestor': 0, 'cost': 2, 'direct': False, 'orientation': 0, 'path': [7, 3], 'stop': 1}Passed
regression certificate 5{'ancestor': 0, 'cost': 2, 'direct': False, 'orientation': 0, 'path': [5, 2], 'stop': 1}{'ancestor': 0, 'cost': 2, 'direct': False, 'orientation': 0, 'path': [5, 2], 'stop': 1}Passed
regression certificate 6{'ancestor': 3, 'cost': 0, 'direct': True, 'orientation': 1, 'path': [], 'stop': 6}{'ancestor': 3, 'cost': 0, 'direct': True, 'orientation': 1, 'path': [], 'stop': 6}Passed
variant-dependent certificate{'ancestor': 1, 'cost': 0, 'direct': True, 'orientation': 1, 'path': [], 'stop': 2}{'ancestor': 1, 'cost': 0, 'direct': True, 'orientation': 1, 'path': [], 'stop': 2}Passed

SHA-256 / 57fce4bbbb395f2d57a9a53ffc3bbc5556222049b8ae9a0673d013bb0b24f76b

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:32.056862+00:00.

Case digest / f6f5f8563eeea96ab29c6c0836740ec325ffcb033c2aef5856d65f5e8c9606f8