FAILURE MAP
← Case archive

FA-40471 / Heap invariants / Open access

Winner tournament replay must recompute the immediate parent before its ancestors · case 01

The bounded tournament path certificate reports an incorrect replay.

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

ROOT CAUSE

Winner tournament replay must recompute the immediate parent before its ancestors.

VERIFIED REPAIR

Derive replay using path under the stated bounded certificate contract.

Unsuccessful approach: The local patch uses path[1:] and still violates the stated relation.

Case contract

A complete winner tournament has power-of-two leaf capacity c and updated leaf slot s. Tree leaves occupy c+s. Report ancestors in bottom-up replay order, sibling indices along that path, root index, comparison count, leaf index, and unaffected leaf slots. Capacity at least one; slot is in range.

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):
    c=d['capacity']; s=d['slot']; leaf=c+s; path=[]; siblings=[]; v=leaf
    while v>1:
        siblings.append(v^1); v//=2; path.append(v)
    return {'replay': list(reversed(path)),
    'siblings': siblings,
    'root': 1,
    'comparisons': len(path),
    'leaf': leaf,
    'untouched': [i for i in range(c) if i!=s]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 1}, {'replay': [8, 4, 2, 1], 'siblings': [16, 9, 5, 3], 'root': 1, 'comparisons': 4, 'leaf': 17, 'untouched': [0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 2}, {'replay': [9, 4, 2, 1], 'siblings': [19, 8, 5, 3], 'root': 1, 'comparisons': 4, 'leaf': 18, 'untouched': [0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 3}, {'replay': [9, 4, 2, 1], 'siblings': [18, 8, 5, 3], 'root': 1, 'comparisons': 4, 'leaf': 19, 'untouched': [0, 1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 4}, {'replay': [10, 5, 2, 1], 'siblings': [21, 11, 4, 3], 'root': 1, 'comparisons': 4, 'leaf': 20, 'untouched': [0, 1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 5}, {'replay': [10, 5, 2, 1], 'siblings': [20, 11, 4, 3], 'root': 1, 'comparisons': 4, 'leaf': 21, 'untouched': [0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})]][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, 'leaf': 1, 'replay': [], 'root': 1, 'siblings': [], 'untouched': []}{'comparisons': 0, 'leaf': 1, 'replay': [], 'root': 1, 'siblings': [], 'untouched': []}Passed
regression certificate 2{'comparisons': 1, 'leaf': 3, 'replay': [1], 'root': 1, 'siblings': [2], 'untouched': [0]}{'comparisons': 1, 'leaf': 3, 'replay': [1], 'root': 1, 'siblings': [2], 'untouched': [0]}Passed
regression certificate 3{'comparisons': 2, 'leaf': 4, 'replay': [1, 2], 'root': 1, 'siblings': [5, 3], 'untouched': [1, 2, 3]}{'comparisons': 2, 'leaf': 4, 'replay': [2, 1], 'root': 1, 'siblings': [5, 3], 'untouched': [1, 2, 3]}Failed
regression certificate 4{'comparisons': 2, 'leaf': 7, 'replay': [1, 3], 'root': 1, 'siblings': [6, 2], 'untouched': [0, 1, 2]}{'comparisons': 2, 'leaf': 7, 'replay': [3, 1], 'root': 1, 'siblings': [6, 2], 'untouched': [0, 1, 2]}Failed
regression certificate 5{'comparisons': 3, 'leaf': 13, 'replay': [1, 3, 6], 'root': 1, 'siblings': [12, 7, 2], 'untouched': [0, 1, 2, 3, 4, 6, 7]}{'comparisons': 3, 'leaf': 13, 'replay': [6, 3, 1], 'root': 1, 'siblings': [12, 7, 2], 'untouched': [0, 1, 2, 3, 4, 6, 7]}Failed
regression certificate 6{'comparisons': 4, 'leaf': 26, 'replay': [1, 3, 6, 13], 'root': 1, 'siblings': [27, 12, 7, 2], 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}{'comparisons': 4, 'leaf': 26, 'replay': [13, 6, 3, 1], 'root': 1, 'siblings': [27, 12, 7, 2], 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}Failed
variant-dependent certificate{'comparisons': 4, 'leaf': 17, 'replay': [1, 2, 4, 8], 'root': 1, 'siblings': [16, 9, 5, 3], 'untouched': [0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]}{'comparisons': 4, 'leaf': 17, 'replay': [8, 4, 2, 1], 'root': 1, 'siblings': [16, 9, 5, 3], 'untouched': [0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]}Failed

SHA-256 / 5e548e8be2b65ff1b7531d413fb3de9b13c14a6fbbaa1bafd9a23a498f675330

2 / The unsuccessful fix

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

N = 1
observations = []
def solve(d):
    c=d['capacity']; s=d['slot']; leaf=c+s; path=[]; siblings=[]; v=leaf
    while v>1:
        siblings.append(v^1); v//=2; path.append(v)
    return {'replay': path[1:],
    'siblings': siblings,
    'root': 1,
    'comparisons': len(path),
    'leaf': leaf,
    'untouched': [i for i in range(c) if i!=s]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 1}, {'replay': [8, 4, 2, 1], 'siblings': [16, 9, 5, 3], 'root': 1, 'comparisons': 4, 'leaf': 17, 'untouched': [0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 2}, {'replay': [9, 4, 2, 1], 'siblings': [19, 8, 5, 3], 'root': 1, 'comparisons': 4, 'leaf': 18, 'untouched': [0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 3}, {'replay': [9, 4, 2, 1], 'siblings': [18, 8, 5, 3], 'root': 1, 'comparisons': 4, 'leaf': 19, 'untouched': [0, 1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 4}, {'replay': [10, 5, 2, 1], 'siblings': [21, 11, 4, 3], 'root': 1, 'comparisons': 4, 'leaf': 20, 'untouched': [0, 1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 5}, {'replay': [10, 5, 2, 1], 'siblings': [20, 11, 4, 3], 'root': 1, 'comparisons': 4, 'leaf': 21, 'untouched': [0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})]][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, 'leaf': 1, 'replay': [], 'root': 1, 'siblings': [], 'untouched': []}{'comparisons': 0, 'leaf': 1, 'replay': [], 'root': 1, 'siblings': [], 'untouched': []}Passed
regression certificate 2{'comparisons': 1, 'leaf': 3, 'replay': [], 'root': 1, 'siblings': [2], 'untouched': [0]}{'comparisons': 1, 'leaf': 3, 'replay': [1], 'root': 1, 'siblings': [2], 'untouched': [0]}Failed
regression certificate 3{'comparisons': 2, 'leaf': 4, 'replay': [1], 'root': 1, 'siblings': [5, 3], 'untouched': [1, 2, 3]}{'comparisons': 2, 'leaf': 4, 'replay': [2, 1], 'root': 1, 'siblings': [5, 3], 'untouched': [1, 2, 3]}Failed
regression certificate 4{'comparisons': 2, 'leaf': 7, 'replay': [1], 'root': 1, 'siblings': [6, 2], 'untouched': [0, 1, 2]}{'comparisons': 2, 'leaf': 7, 'replay': [3, 1], 'root': 1, 'siblings': [6, 2], 'untouched': [0, 1, 2]}Failed
regression certificate 5{'comparisons': 3, 'leaf': 13, 'replay': [3, 1], 'root': 1, 'siblings': [12, 7, 2], 'untouched': [0, 1, 2, 3, 4, 6, 7]}{'comparisons': 3, 'leaf': 13, 'replay': [6, 3, 1], 'root': 1, 'siblings': [12, 7, 2], 'untouched': [0, 1, 2, 3, 4, 6, 7]}Failed
regression certificate 6{'comparisons': 4, 'leaf': 26, 'replay': [6, 3, 1], 'root': 1, 'siblings': [27, 12, 7, 2], 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}{'comparisons': 4, 'leaf': 26, 'replay': [13, 6, 3, 1], 'root': 1, 'siblings': [27, 12, 7, 2], 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}Failed
variant-dependent certificate{'comparisons': 4, 'leaf': 17, 'replay': [4, 2, 1], 'root': 1, 'siblings': [16, 9, 5, 3], 'untouched': [0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]}{'comparisons': 4, 'leaf': 17, 'replay': [8, 4, 2, 1], 'root': 1, 'siblings': [16, 9, 5, 3], 'untouched': [0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]}Failed

SHA-256 / 60ca5b047665cb9a6ee2b13f1d74d34431d0e8fc4f6d14ebeb62ac79ff531252

3 / The verified repair

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

N = 1
observations = []
def solve(d):
    c=d['capacity']; s=d['slot']; leaf=c+s; path=[]; siblings=[]; v=leaf
    while v>1:
        siblings.append(v^1); v//=2; path.append(v)
    return {'replay': path,
    'siblings': siblings,
    'root': 1,
    'comparisons': len(path),
    'leaf': leaf,
    'untouched': [i for i in range(c) if i!=s]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 1}, {'replay': [8, 4, 2, 1], 'siblings': [16, 9, 5, 3], 'root': 1, 'comparisons': 4, 'leaf': 17, 'untouched': [0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 2}, {'replay': [9, 4, 2, 1], 'siblings': [19, 8, 5, 3], 'root': 1, 'comparisons': 4, 'leaf': 18, 'untouched': [0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 3}, {'replay': [9, 4, 2, 1], 'siblings': [18, 8, 5, 3], 'root': 1, 'comparisons': 4, 'leaf': 19, 'untouched': [0, 1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 4}, {'replay': [10, 5, 2, 1], 'siblings': [21, 11, 4, 3], 'root': 1, 'comparisons': 4, 'leaf': 20, 'untouched': [0, 1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 5}, {'replay': [10, 5, 2, 1], 'siblings': [20, 11, 4, 3], 'root': 1, 'comparisons': 4, 'leaf': 21, 'untouched': [0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})]][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, 'leaf': 1, 'replay': [], 'root': 1, 'siblings': [], 'untouched': []}{'comparisons': 0, 'leaf': 1, 'replay': [], 'root': 1, 'siblings': [], 'untouched': []}Passed
regression certificate 2{'comparisons': 1, 'leaf': 3, 'replay': [1], 'root': 1, 'siblings': [2], 'untouched': [0]}{'comparisons': 1, 'leaf': 3, 'replay': [1], 'root': 1, 'siblings': [2], 'untouched': [0]}Passed
regression certificate 3{'comparisons': 2, 'leaf': 4, 'replay': [2, 1], 'root': 1, 'siblings': [5, 3], 'untouched': [1, 2, 3]}{'comparisons': 2, 'leaf': 4, 'replay': [2, 1], 'root': 1, 'siblings': [5, 3], 'untouched': [1, 2, 3]}Passed
regression certificate 4{'comparisons': 2, 'leaf': 7, 'replay': [3, 1], 'root': 1, 'siblings': [6, 2], 'untouched': [0, 1, 2]}{'comparisons': 2, 'leaf': 7, 'replay': [3, 1], 'root': 1, 'siblings': [6, 2], 'untouched': [0, 1, 2]}Passed
regression certificate 5{'comparisons': 3, 'leaf': 13, 'replay': [6, 3, 1], 'root': 1, 'siblings': [12, 7, 2], 'untouched': [0, 1, 2, 3, 4, 6, 7]}{'comparisons': 3, 'leaf': 13, 'replay': [6, 3, 1], 'root': 1, 'siblings': [12, 7, 2], 'untouched': [0, 1, 2, 3, 4, 6, 7]}Passed
regression certificate 6{'comparisons': 4, 'leaf': 26, 'replay': [13, 6, 3, 1], 'root': 1, 'siblings': [27, 12, 7, 2], 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}{'comparisons': 4, 'leaf': 26, 'replay': [13, 6, 3, 1], 'root': 1, 'siblings': [27, 12, 7, 2], 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}Passed
variant-dependent certificate{'comparisons': 4, 'leaf': 17, 'replay': [8, 4, 2, 1], 'root': 1, 'siblings': [16, 9, 5, 3], 'untouched': [0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]}{'comparisons': 4, 'leaf': 17, 'replay': [8, 4, 2, 1], 'root': 1, 'siblings': [16, 9, 5, 3], 'untouched': [0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]}Passed

SHA-256 / 83dc30358577aec25ac5b289cc4d0e6a2646988f56c9a8004756f4444acc5438

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

Case digest / 973cbaaec29bd3ec9213608567f3b5f249841950f77b8a5314d3ddeca17dd5e8