FAILURE MAP
← Case archive

FA-40646 / Heap invariants / Open access

Heap hole avoids a sibling comparison when only the left child exists · case 01

The bounded hole descent certificate reports an incorrect comparisons.

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

ROOT CAUSE

Heap hole avoids a sibling comparison when only the left child exists.

VERIFIED REPAIR

Derive comparisons using compares under the stated bounded certificate contract.

Unsuccessful approach: The local patch uses max(0,len(path)-2) and still violates the stated relation.

Case contract

A binary heap hole descent receives array keys and starting internal or leaf index. Repeatedly choose smaller existing child (left on ties), move that child into the hole, and stop at a leaf; the displaced root value is returned separately for later upward placement. Return path, moved keys, leaf slot, displaced value, remaining untouched slots, and comparison count between sibling pairs.

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['keys']; start=d['start']; path=[start]; moved=[]; compares=0; i=start
    while 2*i+1<len(a):
        l=2*i+1; r=l+1; j=l
        if r<len(a):
            compares+=1
            if a[r]<a[l]: j=r
        moved.append(a[j]); path.append(j); i=j
    return {'path': path,
    'moved_keys': moved,
    'leaf_slot': i,
    'displaced': a[start],
    'untouched': [j for j in range(len(a)) if j not in path],
    'comparisons': len(path)-1}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'keys': [5], 'start': 0}, {'path': [0], 'moved_keys': [], 'leaf_slot': 0, 'displaced': 5, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 2], 'start': 0}, {'path': [0, 1], 'moved_keys': [2], 'leaf_slot': 1, 'displaced': 9, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 5, 8, 2, 7, 6, 4], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [5, 2], 'leaf_slot': 3, 'displaced': 9, 'untouched': [2, 4, 5, 6], 'comparisons': 2}), ({'keys': [8, 2, 2, 5, 6, 7], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [2, 5], 'leaf_slot': 3, 'displaced': 8, 'untouched': [2, 4, 5], 'comparisons': 2}), ({'keys': [0, 9, 3, 4, 2, 8, 6, 7, 8, 5], 'start': 1}, {'path': [1, 4, 9], 'moved_keys': [2, 5], 'leaf_slot': 9, 'displaced': 9, 'untouched': [0, 2, 3, 5, 6, 7, 8], 'comparisons': 1}), ({'keys': [1, 4, 2, 5, 6, 7, 8], 'start': 2}, {'path': [2, 5], 'moved_keys': [7], 'leaf_slot': 5, 'displaced': 2, 'untouched': [0, 1, 3, 4, 6], 'comparisons': 1}), ({'keys': [2, 4, 2, 5, 6, 7, 8], 'start': 1}, {'path': [1, 3], 'moved_keys': [5], 'leaf_slot': 3, 'displaced': 4, 'untouched': [0, 2, 4, 5, 6], 'comparisons': 1})], [({'keys': [5], 'start': 0}, {'path': [0], 'moved_keys': [], 'leaf_slot': 0, 'displaced': 5, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 2], 'start': 0}, {'path': [0, 1], 'moved_keys': [2], 'leaf_slot': 1, 'displaced': 9, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 5, 8, 2, 7, 6, 4], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [5, 2], 'leaf_slot': 3, 'displaced': 9, 'untouched': [2, 4, 5, 6], 'comparisons': 2}), ({'keys': [8, 2, 2, 5, 6, 7], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [2, 5], 'leaf_slot': 3, 'displaced': 8, 'untouched': [2, 4, 5], 'comparisons': 2}), ({'keys': [0, 9, 3, 4, 2, 8, 6, 7, 8, 5], 'start': 1}, {'path': [1, 4, 9], 'moved_keys': [2, 5], 'leaf_slot': 9, 'displaced': 9, 'untouched': [0, 2, 3, 5, 6, 7, 8], 'comparisons': 1}), ({'keys': [1, 4, 2, 5, 6, 7, 8], 'start': 2}, {'path': [2, 5], 'moved_keys': [7], 'leaf_slot': 5, 'displaced': 2, 'untouched': [0, 1, 3, 4, 6], 'comparisons': 1}), ({'keys': [3, 4, 2, 5, 6, 7, 8], 'start': 2}, {'path': [2, 5], 'moved_keys': [7], 'leaf_slot': 5, 'displaced': 2, 'untouched': [0, 1, 3, 4, 6], 'comparisons': 1})], [({'keys': [5], 'start': 0}, {'path': [0], 'moved_keys': [], 'leaf_slot': 0, 'displaced': 5, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 2], 'start': 0}, {'path': [0, 1], 'moved_keys': [2], 'leaf_slot': 1, 'displaced': 9, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 5, 8, 2, 7, 6, 4], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [5, 2], 'leaf_slot': 3, 'displaced': 9, 'untouched': [2, 4, 5, 6], 'comparisons': 2}), ({'keys': [8, 2, 2, 5, 6, 7], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [2, 5], 'leaf_slot': 3, 'displaced': 8, 'untouched': [2, 4, 5], 'comparisons': 2}), ({'keys': [0, 9, 3, 4, 2, 8, 6, 7, 8, 5], 'start': 1}, {'path': [1, 4, 9], 'moved_keys': [2, 5], 'leaf_slot': 9, 'displaced': 9, 'untouched': [0, 2, 3, 5, 6, 7, 8], 'comparisons': 1}), ({'keys': [1, 4, 2, 5, 6, 7, 8], 'start': 2}, {'path': [2, 5], 'moved_keys': [7], 'leaf_slot': 5, 'displaced': 2, 'untouched': [0, 1, 3, 4, 6], 'comparisons': 1}), ({'keys': [4, 4, 2, 5, 6, 7, 8], 'start': 3}, {'path': [3], 'moved_keys': [], 'leaf_slot': 3, 'displaced': 5, 'untouched': [0, 1, 2, 4, 5, 6], 'comparisons': 0})], [({'keys': [5], 'start': 0}, {'path': [0], 'moved_keys': [], 'leaf_slot': 0, 'displaced': 5, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 2], 'start': 0}, {'path': [0, 1], 'moved_keys': [2], 'leaf_slot': 1, 'displaced': 9, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 5, 8, 2, 7, 6, 4], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [5, 2], 'leaf_slot': 3, 'displaced': 9, 'untouched': [2, 4, 5, 6], 'comparisons': 2}), ({'keys': [8, 2, 2, 5, 6, 7], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [2, 5], 'leaf_slot': 3, 'displaced': 8, 'untouched': [2, 4, 5], 'comparisons': 2}), ({'keys': [0, 9, 3, 4, 2, 8, 6, 7, 8, 5], 'start': 1}, {'path': [1, 4, 9], 'moved_keys': [2, 5], 'leaf_slot': 9, 'displaced': 9, 'untouched': [0, 2, 3, 5, 6, 7, 8], 'comparisons': 1}), ({'keys': [1, 4, 2, 5, 6, 7, 8], 'start': 2}, {'path': [2, 5], 'moved_keys': [7], 'leaf_slot': 5, 'displaced': 2, 'untouched': [0, 1, 3, 4, 6], 'comparisons': 1}), ({'keys': [5, 4, 2, 5, 6, 7, 8], 'start': 4}, {'path': [4], 'moved_keys': [], 'leaf_slot': 4, 'displaced': 6, 'untouched': [0, 1, 2, 3, 5, 6], 'comparisons': 0})], [({'keys': [5], 'start': 0}, {'path': [0], 'moved_keys': [], 'leaf_slot': 0, 'displaced': 5, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 2], 'start': 0}, {'path': [0, 1], 'moved_keys': [2], 'leaf_slot': 1, 'displaced': 9, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 5, 8, 2, 7, 6, 4], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [5, 2], 'leaf_slot': 3, 'displaced': 9, 'untouched': [2, 4, 5, 6], 'comparisons': 2}), ({'keys': [8, 2, 2, 5, 6, 7], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [2, 5], 'leaf_slot': 3, 'displaced': 8, 'untouched': [2, 4, 5], 'comparisons': 2}), ({'keys': [0, 9, 3, 4, 2, 8, 6, 7, 8, 5], 'start': 1}, {'path': [1, 4, 9], 'moved_keys': [2, 5], 'leaf_slot': 9, 'displaced': 9, 'untouched': [0, 2, 3, 5, 6, 7, 8], 'comparisons': 1}), ({'keys': [1, 4, 2, 5, 6, 7, 8], 'start': 2}, {'path': [2, 5], 'moved_keys': [7], 'leaf_slot': 5, 'displaced': 2, 'untouched': [0, 1, 3, 4, 6], 'comparisons': 1}), ({'keys': [6, 4, 2, 5, 6, 7, 8], 'start': 5}, {'path': [5], 'moved_keys': [], 'leaf_slot': 5, 'displaced': 7, 'untouched': [0, 1, 2, 3, 4, 6], 'comparisons': 0})]][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{'comparisons': 0, 'displaced': 5, 'leaf_slot': 0, 'moved_keys': [], 'path': [0], 'untouched': []}{'comparisons': 0, 'displaced': 5, 'leaf_slot': 0, 'moved_keys': [], 'path': [0], 'untouched': []}Passed
regression certificate 2{'comparisons': 1, 'displaced': 9, 'leaf_slot': 1, 'moved_keys': [2], 'path': [0, 1], 'untouched': []}{'comparisons': 0, 'displaced': 9, 'leaf_slot': 1, 'moved_keys': [2], 'path': [0, 1], 'untouched': []}Failed
regression certificate 3{'comparisons': 2, 'displaced': 9, 'leaf_slot': 3, 'moved_keys': [5, 2], 'path': [0, 1, 3], 'untouched': [2, 4, 5, 6]}{'comparisons': 2, 'displaced': 9, 'leaf_slot': 3, 'moved_keys': [5, 2], 'path': [0, 1, 3], 'untouched': [2, 4, 5, 6]}Passed
regression certificate 4{'comparisons': 2, 'displaced': 8, 'leaf_slot': 3, 'moved_keys': [2, 5], 'path': [0, 1, 3], 'untouched': [2, 4, 5]}{'comparisons': 2, 'displaced': 8, 'leaf_slot': 3, 'moved_keys': [2, 5], 'path': [0, 1, 3], 'untouched': [2, 4, 5]}Passed
regression certificate 5{'comparisons': 2, 'displaced': 9, 'leaf_slot': 9, 'moved_keys': [2, 5], 'path': [1, 4, 9], 'untouched': [0, 2, 3, 5, 6, 7, 8]}{'comparisons': 1, 'displaced': 9, 'leaf_slot': 9, 'moved_keys': [2, 5], 'path': [1, 4, 9], 'untouched': [0, 2, 3, 5, 6, 7, 8]}Failed
regression certificate 6{'comparisons': 1, 'displaced': 2, 'leaf_slot': 5, 'moved_keys': [7], 'path': [2, 5], 'untouched': [0, 1, 3, 4, 6]}{'comparisons': 1, 'displaced': 2, 'leaf_slot': 5, 'moved_keys': [7], 'path': [2, 5], 'untouched': [0, 1, 3, 4, 6]}Passed
variant-dependent certificate{'comparisons': 1, 'displaced': 4, 'leaf_slot': 3, 'moved_keys': [5], 'path': [1, 3], 'untouched': [0, 2, 4, 5, 6]}{'comparisons': 1, 'displaced': 4, 'leaf_slot': 3, 'moved_keys': [5], 'path': [1, 3], 'untouched': [0, 2, 4, 5, 6]}Passed

SHA-256 / 99dfac52c1e6a0e864908268b92c8b66c86f60a696fa9349a503e5a4469d3710

2 / The unsuccessful fix

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

N = 1
observations = []
def solve(d):
    a=d['keys']; start=d['start']; path=[start]; moved=[]; compares=0; i=start
    while 2*i+1<len(a):
        l=2*i+1; r=l+1; j=l
        if r<len(a):
            compares+=1
            if a[r]<a[l]: j=r
        moved.append(a[j]); path.append(j); i=j
    return {'path': path,
    'moved_keys': moved,
    'leaf_slot': i,
    'displaced': a[start],
    'untouched': [j for j in range(len(a)) if j not in path],
    'comparisons': max(0,len(path)-2)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'keys': [5], 'start': 0}, {'path': [0], 'moved_keys': [], 'leaf_slot': 0, 'displaced': 5, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 2], 'start': 0}, {'path': [0, 1], 'moved_keys': [2], 'leaf_slot': 1, 'displaced': 9, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 5, 8, 2, 7, 6, 4], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [5, 2], 'leaf_slot': 3, 'displaced': 9, 'untouched': [2, 4, 5, 6], 'comparisons': 2}), ({'keys': [8, 2, 2, 5, 6, 7], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [2, 5], 'leaf_slot': 3, 'displaced': 8, 'untouched': [2, 4, 5], 'comparisons': 2}), ({'keys': [0, 9, 3, 4, 2, 8, 6, 7, 8, 5], 'start': 1}, {'path': [1, 4, 9], 'moved_keys': [2, 5], 'leaf_slot': 9, 'displaced': 9, 'untouched': [0, 2, 3, 5, 6, 7, 8], 'comparisons': 1}), ({'keys': [1, 4, 2, 5, 6, 7, 8], 'start': 2}, {'path': [2, 5], 'moved_keys': [7], 'leaf_slot': 5, 'displaced': 2, 'untouched': [0, 1, 3, 4, 6], 'comparisons': 1}), ({'keys': [2, 4, 2, 5, 6, 7, 8], 'start': 1}, {'path': [1, 3], 'moved_keys': [5], 'leaf_slot': 3, 'displaced': 4, 'untouched': [0, 2, 4, 5, 6], 'comparisons': 1})], [({'keys': [5], 'start': 0}, {'path': [0], 'moved_keys': [], 'leaf_slot': 0, 'displaced': 5, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 2], 'start': 0}, {'path': [0, 1], 'moved_keys': [2], 'leaf_slot': 1, 'displaced': 9, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 5, 8, 2, 7, 6, 4], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [5, 2], 'leaf_slot': 3, 'displaced': 9, 'untouched': [2, 4, 5, 6], 'comparisons': 2}), ({'keys': [8, 2, 2, 5, 6, 7], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [2, 5], 'leaf_slot': 3, 'displaced': 8, 'untouched': [2, 4, 5], 'comparisons': 2}), ({'keys': [0, 9, 3, 4, 2, 8, 6, 7, 8, 5], 'start': 1}, {'path': [1, 4, 9], 'moved_keys': [2, 5], 'leaf_slot': 9, 'displaced': 9, 'untouched': [0, 2, 3, 5, 6, 7, 8], 'comparisons': 1}), ({'keys': [1, 4, 2, 5, 6, 7, 8], 'start': 2}, {'path': [2, 5], 'moved_keys': [7], 'leaf_slot': 5, 'displaced': 2, 'untouched': [0, 1, 3, 4, 6], 'comparisons': 1}), ({'keys': [3, 4, 2, 5, 6, 7, 8], 'start': 2}, {'path': [2, 5], 'moved_keys': [7], 'leaf_slot': 5, 'displaced': 2, 'untouched': [0, 1, 3, 4, 6], 'comparisons': 1})], [({'keys': [5], 'start': 0}, {'path': [0], 'moved_keys': [], 'leaf_slot': 0, 'displaced': 5, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 2], 'start': 0}, {'path': [0, 1], 'moved_keys': [2], 'leaf_slot': 1, 'displaced': 9, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 5, 8, 2, 7, 6, 4], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [5, 2], 'leaf_slot': 3, 'displaced': 9, 'untouched': [2, 4, 5, 6], 'comparisons': 2}), ({'keys': [8, 2, 2, 5, 6, 7], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [2, 5], 'leaf_slot': 3, 'displaced': 8, 'untouched': [2, 4, 5], 'comparisons': 2}), ({'keys': [0, 9, 3, 4, 2, 8, 6, 7, 8, 5], 'start': 1}, {'path': [1, 4, 9], 'moved_keys': [2, 5], 'leaf_slot': 9, 'displaced': 9, 'untouched': [0, 2, 3, 5, 6, 7, 8], 'comparisons': 1}), ({'keys': [1, 4, 2, 5, 6, 7, 8], 'start': 2}, {'path': [2, 5], 'moved_keys': [7], 'leaf_slot': 5, 'displaced': 2, 'untouched': [0, 1, 3, 4, 6], 'comparisons': 1}), ({'keys': [4, 4, 2, 5, 6, 7, 8], 'start': 3}, {'path': [3], 'moved_keys': [], 'leaf_slot': 3, 'displaced': 5, 'untouched': [0, 1, 2, 4, 5, 6], 'comparisons': 0})], [({'keys': [5], 'start': 0}, {'path': [0], 'moved_keys': [], 'leaf_slot': 0, 'displaced': 5, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 2], 'start': 0}, {'path': [0, 1], 'moved_keys': [2], 'leaf_slot': 1, 'displaced': 9, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 5, 8, 2, 7, 6, 4], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [5, 2], 'leaf_slot': 3, 'displaced': 9, 'untouched': [2, 4, 5, 6], 'comparisons': 2}), ({'keys': [8, 2, 2, 5, 6, 7], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [2, 5], 'leaf_slot': 3, 'displaced': 8, 'untouched': [2, 4, 5], 'comparisons': 2}), ({'keys': [0, 9, 3, 4, 2, 8, 6, 7, 8, 5], 'start': 1}, {'path': [1, 4, 9], 'moved_keys': [2, 5], 'leaf_slot': 9, 'displaced': 9, 'untouched': [0, 2, 3, 5, 6, 7, 8], 'comparisons': 1}), ({'keys': [1, 4, 2, 5, 6, 7, 8], 'start': 2}, {'path': [2, 5], 'moved_keys': [7], 'leaf_slot': 5, 'displaced': 2, 'untouched': [0, 1, 3, 4, 6], 'comparisons': 1}), ({'keys': [5, 4, 2, 5, 6, 7, 8], 'start': 4}, {'path': [4], 'moved_keys': [], 'leaf_slot': 4, 'displaced': 6, 'untouched': [0, 1, 2, 3, 5, 6], 'comparisons': 0})], [({'keys': [5], 'start': 0}, {'path': [0], 'moved_keys': [], 'leaf_slot': 0, 'displaced': 5, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 2], 'start': 0}, {'path': [0, 1], 'moved_keys': [2], 'leaf_slot': 1, 'displaced': 9, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 5, 8, 2, 7, 6, 4], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [5, 2], 'leaf_slot': 3, 'displaced': 9, 'untouched': [2, 4, 5, 6], 'comparisons': 2}), ({'keys': [8, 2, 2, 5, 6, 7], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [2, 5], 'leaf_slot': 3, 'displaced': 8, 'untouched': [2, 4, 5], 'comparisons': 2}), ({'keys': [0, 9, 3, 4, 2, 8, 6, 7, 8, 5], 'start': 1}, {'path': [1, 4, 9], 'moved_keys': [2, 5], 'leaf_slot': 9, 'displaced': 9, 'untouched': [0, 2, 3, 5, 6, 7, 8], 'comparisons': 1}), ({'keys': [1, 4, 2, 5, 6, 7, 8], 'start': 2}, {'path': [2, 5], 'moved_keys': [7], 'leaf_slot': 5, 'displaced': 2, 'untouched': [0, 1, 3, 4, 6], 'comparisons': 1}), ({'keys': [6, 4, 2, 5, 6, 7, 8], 'start': 5}, {'path': [5], 'moved_keys': [], 'leaf_slot': 5, 'displaced': 7, 'untouched': [0, 1, 2, 3, 4, 6], 'comparisons': 0})]][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{'comparisons': 0, 'displaced': 5, 'leaf_slot': 0, 'moved_keys': [], 'path': [0], 'untouched': []}{'comparisons': 0, 'displaced': 5, 'leaf_slot': 0, 'moved_keys': [], 'path': [0], 'untouched': []}Passed
regression certificate 2{'comparisons': 0, 'displaced': 9, 'leaf_slot': 1, 'moved_keys': [2], 'path': [0, 1], 'untouched': []}{'comparisons': 0, 'displaced': 9, 'leaf_slot': 1, 'moved_keys': [2], 'path': [0, 1], 'untouched': []}Passed
regression certificate 3{'comparisons': 1, 'displaced': 9, 'leaf_slot': 3, 'moved_keys': [5, 2], 'path': [0, 1, 3], 'untouched': [2, 4, 5, 6]}{'comparisons': 2, 'displaced': 9, 'leaf_slot': 3, 'moved_keys': [5, 2], 'path': [0, 1, 3], 'untouched': [2, 4, 5, 6]}Failed
regression certificate 4{'comparisons': 1, 'displaced': 8, 'leaf_slot': 3, 'moved_keys': [2, 5], 'path': [0, 1, 3], 'untouched': [2, 4, 5]}{'comparisons': 2, 'displaced': 8, 'leaf_slot': 3, 'moved_keys': [2, 5], 'path': [0, 1, 3], 'untouched': [2, 4, 5]}Failed
regression certificate 5{'comparisons': 1, 'displaced': 9, 'leaf_slot': 9, 'moved_keys': [2, 5], 'path': [1, 4, 9], 'untouched': [0, 2, 3, 5, 6, 7, 8]}{'comparisons': 1, 'displaced': 9, 'leaf_slot': 9, 'moved_keys': [2, 5], 'path': [1, 4, 9], 'untouched': [0, 2, 3, 5, 6, 7, 8]}Passed
regression certificate 6{'comparisons': 0, 'displaced': 2, 'leaf_slot': 5, 'moved_keys': [7], 'path': [2, 5], 'untouched': [0, 1, 3, 4, 6]}{'comparisons': 1, 'displaced': 2, 'leaf_slot': 5, 'moved_keys': [7], 'path': [2, 5], 'untouched': [0, 1, 3, 4, 6]}Failed
variant-dependent certificate{'comparisons': 0, 'displaced': 4, 'leaf_slot': 3, 'moved_keys': [5], 'path': [1, 3], 'untouched': [0, 2, 4, 5, 6]}{'comparisons': 1, 'displaced': 4, 'leaf_slot': 3, 'moved_keys': [5], 'path': [1, 3], 'untouched': [0, 2, 4, 5, 6]}Failed

SHA-256 / 53bcbe2167ef16fcc1df0ee65fc6e6752403d6f49901adc49696b023185ff8d3

3 / The verified repair

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

N = 1
observations = []
def solve(d):
    a=d['keys']; start=d['start']; path=[start]; moved=[]; compares=0; i=start
    while 2*i+1<len(a):
        l=2*i+1; r=l+1; j=l
        if r<len(a):
            compares+=1
            if a[r]<a[l]: j=r
        moved.append(a[j]); path.append(j); i=j
    return {'path': path,
    'moved_keys': moved,
    'leaf_slot': i,
    'displaced': a[start],
    'untouched': [j for j in range(len(a)) if j not in path],
    'comparisons': compares}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'keys': [5], 'start': 0}, {'path': [0], 'moved_keys': [], 'leaf_slot': 0, 'displaced': 5, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 2], 'start': 0}, {'path': [0, 1], 'moved_keys': [2], 'leaf_slot': 1, 'displaced': 9, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 5, 8, 2, 7, 6, 4], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [5, 2], 'leaf_slot': 3, 'displaced': 9, 'untouched': [2, 4, 5, 6], 'comparisons': 2}), ({'keys': [8, 2, 2, 5, 6, 7], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [2, 5], 'leaf_slot': 3, 'displaced': 8, 'untouched': [2, 4, 5], 'comparisons': 2}), ({'keys': [0, 9, 3, 4, 2, 8, 6, 7, 8, 5], 'start': 1}, {'path': [1, 4, 9], 'moved_keys': [2, 5], 'leaf_slot': 9, 'displaced': 9, 'untouched': [0, 2, 3, 5, 6, 7, 8], 'comparisons': 1}), ({'keys': [1, 4, 2, 5, 6, 7, 8], 'start': 2}, {'path': [2, 5], 'moved_keys': [7], 'leaf_slot': 5, 'displaced': 2, 'untouched': [0, 1, 3, 4, 6], 'comparisons': 1}), ({'keys': [2, 4, 2, 5, 6, 7, 8], 'start': 1}, {'path': [1, 3], 'moved_keys': [5], 'leaf_slot': 3, 'displaced': 4, 'untouched': [0, 2, 4, 5, 6], 'comparisons': 1})], [({'keys': [5], 'start': 0}, {'path': [0], 'moved_keys': [], 'leaf_slot': 0, 'displaced': 5, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 2], 'start': 0}, {'path': [0, 1], 'moved_keys': [2], 'leaf_slot': 1, 'displaced': 9, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 5, 8, 2, 7, 6, 4], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [5, 2], 'leaf_slot': 3, 'displaced': 9, 'untouched': [2, 4, 5, 6], 'comparisons': 2}), ({'keys': [8, 2, 2, 5, 6, 7], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [2, 5], 'leaf_slot': 3, 'displaced': 8, 'untouched': [2, 4, 5], 'comparisons': 2}), ({'keys': [0, 9, 3, 4, 2, 8, 6, 7, 8, 5], 'start': 1}, {'path': [1, 4, 9], 'moved_keys': [2, 5], 'leaf_slot': 9, 'displaced': 9, 'untouched': [0, 2, 3, 5, 6, 7, 8], 'comparisons': 1}), ({'keys': [1, 4, 2, 5, 6, 7, 8], 'start': 2}, {'path': [2, 5], 'moved_keys': [7], 'leaf_slot': 5, 'displaced': 2, 'untouched': [0, 1, 3, 4, 6], 'comparisons': 1}), ({'keys': [3, 4, 2, 5, 6, 7, 8], 'start': 2}, {'path': [2, 5], 'moved_keys': [7], 'leaf_slot': 5, 'displaced': 2, 'untouched': [0, 1, 3, 4, 6], 'comparisons': 1})], [({'keys': [5], 'start': 0}, {'path': [0], 'moved_keys': [], 'leaf_slot': 0, 'displaced': 5, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 2], 'start': 0}, {'path': [0, 1], 'moved_keys': [2], 'leaf_slot': 1, 'displaced': 9, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 5, 8, 2, 7, 6, 4], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [5, 2], 'leaf_slot': 3, 'displaced': 9, 'untouched': [2, 4, 5, 6], 'comparisons': 2}), ({'keys': [8, 2, 2, 5, 6, 7], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [2, 5], 'leaf_slot': 3, 'displaced': 8, 'untouched': [2, 4, 5], 'comparisons': 2}), ({'keys': [0, 9, 3, 4, 2, 8, 6, 7, 8, 5], 'start': 1}, {'path': [1, 4, 9], 'moved_keys': [2, 5], 'leaf_slot': 9, 'displaced': 9, 'untouched': [0, 2, 3, 5, 6, 7, 8], 'comparisons': 1}), ({'keys': [1, 4, 2, 5, 6, 7, 8], 'start': 2}, {'path': [2, 5], 'moved_keys': [7], 'leaf_slot': 5, 'displaced': 2, 'untouched': [0, 1, 3, 4, 6], 'comparisons': 1}), ({'keys': [4, 4, 2, 5, 6, 7, 8], 'start': 3}, {'path': [3], 'moved_keys': [], 'leaf_slot': 3, 'displaced': 5, 'untouched': [0, 1, 2, 4, 5, 6], 'comparisons': 0})], [({'keys': [5], 'start': 0}, {'path': [0], 'moved_keys': [], 'leaf_slot': 0, 'displaced': 5, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 2], 'start': 0}, {'path': [0, 1], 'moved_keys': [2], 'leaf_slot': 1, 'displaced': 9, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 5, 8, 2, 7, 6, 4], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [5, 2], 'leaf_slot': 3, 'displaced': 9, 'untouched': [2, 4, 5, 6], 'comparisons': 2}), ({'keys': [8, 2, 2, 5, 6, 7], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [2, 5], 'leaf_slot': 3, 'displaced': 8, 'untouched': [2, 4, 5], 'comparisons': 2}), ({'keys': [0, 9, 3, 4, 2, 8, 6, 7, 8, 5], 'start': 1}, {'path': [1, 4, 9], 'moved_keys': [2, 5], 'leaf_slot': 9, 'displaced': 9, 'untouched': [0, 2, 3, 5, 6, 7, 8], 'comparisons': 1}), ({'keys': [1, 4, 2, 5, 6, 7, 8], 'start': 2}, {'path': [2, 5], 'moved_keys': [7], 'leaf_slot': 5, 'displaced': 2, 'untouched': [0, 1, 3, 4, 6], 'comparisons': 1}), ({'keys': [5, 4, 2, 5, 6, 7, 8], 'start': 4}, {'path': [4], 'moved_keys': [], 'leaf_slot': 4, 'displaced': 6, 'untouched': [0, 1, 2, 3, 5, 6], 'comparisons': 0})], [({'keys': [5], 'start': 0}, {'path': [0], 'moved_keys': [], 'leaf_slot': 0, 'displaced': 5, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 2], 'start': 0}, {'path': [0, 1], 'moved_keys': [2], 'leaf_slot': 1, 'displaced': 9, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 5, 8, 2, 7, 6, 4], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [5, 2], 'leaf_slot': 3, 'displaced': 9, 'untouched': [2, 4, 5, 6], 'comparisons': 2}), ({'keys': [8, 2, 2, 5, 6, 7], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [2, 5], 'leaf_slot': 3, 'displaced': 8, 'untouched': [2, 4, 5], 'comparisons': 2}), ({'keys': [0, 9, 3, 4, 2, 8, 6, 7, 8, 5], 'start': 1}, {'path': [1, 4, 9], 'moved_keys': [2, 5], 'leaf_slot': 9, 'displaced': 9, 'untouched': [0, 2, 3, 5, 6, 7, 8], 'comparisons': 1}), ({'keys': [1, 4, 2, 5, 6, 7, 8], 'start': 2}, {'path': [2, 5], 'moved_keys': [7], 'leaf_slot': 5, 'displaced': 2, 'untouched': [0, 1, 3, 4, 6], 'comparisons': 1}), ({'keys': [6, 4, 2, 5, 6, 7, 8], 'start': 5}, {'path': [5], 'moved_keys': [], 'leaf_slot': 5, 'displaced': 7, 'untouched': [0, 1, 2, 3, 4, 6], 'comparisons': 0})]][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{'comparisons': 0, 'displaced': 5, 'leaf_slot': 0, 'moved_keys': [], 'path': [0], 'untouched': []}{'comparisons': 0, 'displaced': 5, 'leaf_slot': 0, 'moved_keys': [], 'path': [0], 'untouched': []}Passed
regression certificate 2{'comparisons': 0, 'displaced': 9, 'leaf_slot': 1, 'moved_keys': [2], 'path': [0, 1], 'untouched': []}{'comparisons': 0, 'displaced': 9, 'leaf_slot': 1, 'moved_keys': [2], 'path': [0, 1], 'untouched': []}Passed
regression certificate 3{'comparisons': 2, 'displaced': 9, 'leaf_slot': 3, 'moved_keys': [5, 2], 'path': [0, 1, 3], 'untouched': [2, 4, 5, 6]}{'comparisons': 2, 'displaced': 9, 'leaf_slot': 3, 'moved_keys': [5, 2], 'path': [0, 1, 3], 'untouched': [2, 4, 5, 6]}Passed
regression certificate 4{'comparisons': 2, 'displaced': 8, 'leaf_slot': 3, 'moved_keys': [2, 5], 'path': [0, 1, 3], 'untouched': [2, 4, 5]}{'comparisons': 2, 'displaced': 8, 'leaf_slot': 3, 'moved_keys': [2, 5], 'path': [0, 1, 3], 'untouched': [2, 4, 5]}Passed
regression certificate 5{'comparisons': 1, 'displaced': 9, 'leaf_slot': 9, 'moved_keys': [2, 5], 'path': [1, 4, 9], 'untouched': [0, 2, 3, 5, 6, 7, 8]}{'comparisons': 1, 'displaced': 9, 'leaf_slot': 9, 'moved_keys': [2, 5], 'path': [1, 4, 9], 'untouched': [0, 2, 3, 5, 6, 7, 8]}Passed
regression certificate 6{'comparisons': 1, 'displaced': 2, 'leaf_slot': 5, 'moved_keys': [7], 'path': [2, 5], 'untouched': [0, 1, 3, 4, 6]}{'comparisons': 1, 'displaced': 2, 'leaf_slot': 5, 'moved_keys': [7], 'path': [2, 5], 'untouched': [0, 1, 3, 4, 6]}Passed
variant-dependent certificate{'comparisons': 1, 'displaced': 4, 'leaf_slot': 3, 'moved_keys': [5], 'path': [1, 3], 'untouched': [0, 2, 4, 5, 6]}{'comparisons': 1, 'displaced': 4, 'leaf_slot': 3, 'moved_keys': [5], 'path': [1, 3], 'untouched': [0, 2, 4, 5, 6]}Passed

SHA-256 / 0eab72fa811cc0ce0028c8c894106f68b1cbc22e6f2ced6fdbcab456cd3a6069

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

Case digest / 86819cbc23449307076d4a53d7c9acd3b634959653452546feae93f2321b048a