FAILURE MAP
← Case archive

FA-40801 / Heap invariants / Open access

Indexed erase fills the selected hole instead of shifting unrelated heap slots · case 01

The bounded indexed erase routing certificate reports an incorrect slots.

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

ROOT CAUSE

Indexed erase fills the selected hole instead of shifting unrelated heap slots.

VERIFIED REPAIR

Derive slots using out under the stated bounded certificate contract.

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

Case contract

An indexed heap erasure certificate gives slots [id,key], selected slot i, and a valid min-heap prefix before deletion. Fill the hole with the last record unless erasing the tail. Decide upward repair if replacement is smaller than its parent, otherwise downward; return shortened slots, removed id, direction, replacement handle location, retained identities, and logical size.

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['slots']; i=d['index']; last=len(a)-1; out=[list(x) for x in a[:-1]]
    if i<last: out[i]=list(a[-1])
    direction='none' if i==last else ('up' if i>0 and out[i][1]<out[(i-1)//2][1] else 'down')
    return {'slots': [x for k,x in enumerate(a) if k!=i],
    'removed': a[i][0],
    'direction': direction,
    'replacement_location': None if i==last else [a[-1][0],i],
    'retained': sorted(x[0] for x in out),
    'size': len(a)-1}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'slots': [['a', 1]], 'index': 0}, {'slots': [], 'removed': 'a', 'direction': 'none', 'replacement_location': None, 'retained': [], 'size': 0}), ({'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['e', 8], ['f', 3], ['g', 4]], 'index': 4}, {'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['g', 4], ['f', 3]], 'removed': 'e', 'direction': 'up', 'replacement_location': ['g', 4], 'retained': ['a', 'b', 'c', 'd', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 3]], 'index': 0}, {'slots': [['c', 3], ['b', 2]], 'removed': 'a', 'direction': 'down', 'replacement_location': ['c', 0], 'retained': ['b', 'c'], 'size': 2}), ({'slots': [['a', 1], ['b', 2], ['c', 3], ['d', 4]], 'index': 3}, {'slots': [['a', 1], ['b', 2], ['c', 3]], 'removed': 'd', 'direction': 'none', 'replacement_location': None, 'retained': ['a', 'b', 'c'], 'size': 3}), ({'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['e', 8], ['f', 3], ['g', 4]], 'index': 3}, {'slots': [['a', 1], ['b', 5], ['c', 2], ['g', 4], ['e', 8], ['f', 3]], 'removed': 'd', 'direction': 'up', 'replacement_location': ['g', 3], 'retained': ['a', 'b', 'c', 'e', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 2], ['d', 4], ['e', 5], ['f', 2], ['g', 3]], 'index': 1}, {'slots': [['a', 1], ['g', 3], ['c', 2], ['d', 4], ['e', 5], ['f', 2]], 'removed': 'b', 'direction': 'down', 'replacement_location': ['g', 1], 'retained': ['a', 'c', 'd', 'e', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 2], ['d', 4], ['e', 5], ['f', 2], ['g', 3]], 'index': 1}, {'slots': [['a', 1], ['g', 3], ['c', 2], ['d', 4], ['e', 5], ['f', 2]], 'removed': 'b', 'direction': 'down', 'replacement_location': ['g', 1], 'retained': ['a', 'c', 'd', 'e', 'f', 'g'], 'size': 6})], [({'slots': [['a', 1]], 'index': 0}, {'slots': [], 'removed': 'a', 'direction': 'none', 'replacement_location': None, 'retained': [], 'size': 0}), ({'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['e', 8], ['f', 3], ['g', 4]], 'index': 4}, {'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['g', 4], ['f', 3]], 'removed': 'e', 'direction': 'up', 'replacement_location': ['g', 4], 'retained': ['a', 'b', 'c', 'd', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 3]], 'index': 0}, {'slots': [['c', 3], ['b', 2]], 'removed': 'a', 'direction': 'down', 'replacement_location': ['c', 0], 'retained': ['b', 'c'], 'size': 2}), ({'slots': [['a', 1], ['b', 2], ['c', 3], ['d', 4]], 'index': 3}, {'slots': [['a', 1], ['b', 2], ['c', 3]], 'removed': 'd', 'direction': 'none', 'replacement_location': None, 'retained': ['a', 'b', 'c'], 'size': 3}), ({'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['e', 8], ['f', 3], ['g', 4]], 'index': 3}, {'slots': [['a', 1], ['b', 5], ['c', 2], ['g', 4], ['e', 8], ['f', 3]], 'removed': 'd', 'direction': 'up', 'replacement_location': ['g', 3], 'retained': ['a', 'b', 'c', 'e', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 2], ['d', 4], ['e', 5], ['f', 2], ['g', 3]], 'index': 1}, {'slots': [['a', 1], ['g', 3], ['c', 2], ['d', 4], ['e', 5], ['f', 2]], 'removed': 'b', 'direction': 'down', 'replacement_location': ['g', 1], 'retained': ['a', 'c', 'd', 'e', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 2], ['d', 4], ['e', 5], ['f', 2], ['g', 3]], 'index': 2}, {'slots': [['a', 1], ['b', 2], ['g', 3], ['d', 4], ['e', 5], ['f', 2]], 'removed': 'c', 'direction': 'down', 'replacement_location': ['g', 2], 'retained': ['a', 'b', 'd', 'e', 'f', 'g'], 'size': 6})], [({'slots': [['a', 1]], 'index': 0}, {'slots': [], 'removed': 'a', 'direction': 'none', 'replacement_location': None, 'retained': [], 'size': 0}), ({'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['e', 8], ['f', 3], ['g', 4]], 'index': 4}, {'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['g', 4], ['f', 3]], 'removed': 'e', 'direction': 'up', 'replacement_location': ['g', 4], 'retained': ['a', 'b', 'c', 'd', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 3]], 'index': 0}, {'slots': [['c', 3], ['b', 2]], 'removed': 'a', 'direction': 'down', 'replacement_location': ['c', 0], 'retained': ['b', 'c'], 'size': 2}), ({'slots': [['a', 1], ['b', 2], ['c', 3], ['d', 4]], 'index': 3}, {'slots': [['a', 1], ['b', 2], ['c', 3]], 'removed': 'd', 'direction': 'none', 'replacement_location': None, 'retained': ['a', 'b', 'c'], 'size': 3}), ({'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['e', 8], ['f', 3], ['g', 4]], 'index': 3}, {'slots': [['a', 1], ['b', 5], ['c', 2], ['g', 4], ['e', 8], ['f', 3]], 'removed': 'd', 'direction': 'up', 'replacement_location': ['g', 3], 'retained': ['a', 'b', 'c', 'e', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 2], ['d', 4], ['e', 5], ['f', 2], ['g', 3]], 'index': 1}, {'slots': [['a', 1], ['g', 3], ['c', 2], ['d', 4], ['e', 5], ['f', 2]], 'removed': 'b', 'direction': 'down', 'replacement_location': ['g', 1], 'retained': ['a', 'c', 'd', 'e', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 2], ['d', 4], ['e', 5], ['f', 2], ['g', 3]], 'index': 3}, {'slots': [['a', 1], ['b', 2], ['c', 2], ['g', 3], ['e', 5], ['f', 2]], 'removed': 'd', 'direction': 'down', 'replacement_location': ['g', 3], 'retained': ['a', 'b', 'c', 'e', 'f', 'g'], 'size': 6})], [({'slots': [['a', 1]], 'index': 0}, {'slots': [], 'removed': 'a', 'direction': 'none', 'replacement_location': None, 'retained': [], 'size': 0}), ({'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['e', 8], ['f', 3], ['g', 4]], 'index': 4}, {'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['g', 4], ['f', 3]], 'removed': 'e', 'direction': 'up', 'replacement_location': ['g', 4], 'retained': ['a', 'b', 'c', 'd', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 3]], 'index': 0}, {'slots': [['c', 3], ['b', 2]], 'removed': 'a', 'direction': 'down', 'replacement_location': ['c', 0], 'retained': ['b', 'c'], 'size': 2}), ({'slots': [['a', 1], ['b', 2], ['c', 3], ['d', 4]], 'index': 3}, {'slots': [['a', 1], ['b', 2], ['c', 3]], 'removed': 'd', 'direction': 'none', 'replacement_location': None, 'retained': ['a', 'b', 'c'], 'size': 3}), ({'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['e', 8], ['f', 3], ['g', 4]], 'index': 3}, {'slots': [['a', 1], ['b', 5], ['c', 2], ['g', 4], ['e', 8], ['f', 3]], 'removed': 'd', 'direction': 'up', 'replacement_location': ['g', 3], 'retained': ['a', 'b', 'c', 'e', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 2], ['d', 4], ['e', 5], ['f', 2], ['g', 3]], 'index': 1}, {'slots': [['a', 1], ['g', 3], ['c', 2], ['d', 4], ['e', 5], ['f', 2]], 'removed': 'b', 'direction': 'down', 'replacement_location': ['g', 1], 'retained': ['a', 'c', 'd', 'e', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 2], ['d', 4], ['e', 5], ['f', 2], ['g', 3]], 'index': 4}, {'slots': [['a', 1], ['b', 2], ['c', 2], ['d', 4], ['g', 3], ['f', 2]], 'removed': 'e', 'direction': 'down', 'replacement_location': ['g', 4], 'retained': ['a', 'b', 'c', 'd', 'f', 'g'], 'size': 6})], [({'slots': [['a', 1]], 'index': 0}, {'slots': [], 'removed': 'a', 'direction': 'none', 'replacement_location': None, 'retained': [], 'size': 0}), ({'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['e', 8], ['f', 3], ['g', 4]], 'index': 4}, {'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['g', 4], ['f', 3]], 'removed': 'e', 'direction': 'up', 'replacement_location': ['g', 4], 'retained': ['a', 'b', 'c', 'd', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 3]], 'index': 0}, {'slots': [['c', 3], ['b', 2]], 'removed': 'a', 'direction': 'down', 'replacement_location': ['c', 0], 'retained': ['b', 'c'], 'size': 2}), ({'slots': [['a', 1], ['b', 2], ['c', 3], ['d', 4]], 'index': 3}, {'slots': [['a', 1], ['b', 2], ['c', 3]], 'removed': 'd', 'direction': 'none', 'replacement_location': None, 'retained': ['a', 'b', 'c'], 'size': 3}), ({'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['e', 8], ['f', 3], ['g', 4]], 'index': 3}, {'slots': [['a', 1], ['b', 5], ['c', 2], ['g', 4], ['e', 8], ['f', 3]], 'removed': 'd', 'direction': 'up', 'replacement_location': ['g', 3], 'retained': ['a', 'b', 'c', 'e', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 2], ['d', 4], ['e', 5], ['f', 2], ['g', 3]], 'index': 1}, {'slots': [['a', 1], ['g', 3], ['c', 2], ['d', 4], ['e', 5], ['f', 2]], 'removed': 'b', 'direction': 'down', 'replacement_location': ['g', 1], 'retained': ['a', 'c', 'd', 'e', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 2], ['d', 4], ['e', 5], ['f', 2], ['g', 3]], 'index': 5}, {'slots': [['a', 1], ['b', 2], ['c', 2], ['d', 4], ['e', 5], ['g', 3]], 'removed': 'f', 'direction': 'down', 'replacement_location': ['g', 5], 'retained': ['a', 'b', 'c', 'd', 'e', 'g'], 'size': 6})]][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{'direction': 'none', 'removed': 'a', 'replacement_location': None, 'retained': [], 'size': 0, 'slots': []}{'direction': 'none', 'removed': 'a', 'replacement_location': None, 'retained': [], 'size': 0, 'slots': []}Passed
regression certificate 2{'direction': 'up', 'removed': 'e', 'replacement_location': ['g', 4], 'retained': ['a', 'b', 'c', 'd', 'f', 'g'], 'size': 6, 'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['f', 3], ['g', 4]]}{'direction': 'up', 'removed': 'e', 'replacement_location': ['g', 4], 'retained': ['a', 'b', 'c', 'd', 'f', 'g'], 'size': 6, 'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['g', 4], ['f', 3]]}Failed
regression certificate 3{'direction': 'down', 'removed': 'a', 'replacement_location': ['c', 0], 'retained': ['b', 'c'], 'size': 2, 'slots': [['b', 2], ['c', 3]]}{'direction': 'down', 'removed': 'a', 'replacement_location': ['c', 0], 'retained': ['b', 'c'], 'size': 2, 'slots': [['c', 3], ['b', 2]]}Failed
regression certificate 4{'direction': 'none', 'removed': 'd', 'replacement_location': None, 'retained': ['a', 'b', 'c'], 'size': 3, 'slots': [['a', 1], ['b', 2], ['c', 3]]}{'direction': 'none', 'removed': 'd', 'replacement_location': None, 'retained': ['a', 'b', 'c'], 'size': 3, 'slots': [['a', 1], ['b', 2], ['c', 3]]}Passed
regression certificate 5{'direction': 'up', 'removed': 'd', 'replacement_location': ['g', 3], 'retained': ['a', 'b', 'c', 'e', 'f', 'g'], 'size': 6, 'slots': [['a', 1], ['b', 5], ['c', 2], ['e', 8], ['f', 3], ['g', 4]]}{'direction': 'up', 'removed': 'd', 'replacement_location': ['g', 3], 'retained': ['a', 'b', 'c', 'e', 'f', 'g'], 'size': 6, 'slots': [['a', 1], ['b', 5], ['c', 2], ['g', 4], ['e', 8], ['f', 3]]}Failed
regression certificate 6{'direction': 'down', 'removed': 'b', 'replacement_location': ['g', 1], 'retained': ['a', 'c', 'd', 'e', 'f', 'g'], 'size': 6, 'slots': [['a', 1], ['c', 2], ['d', 4], ['e', 5], ['f', 2], ['g', 3]]}{'direction': 'down', 'removed': 'b', 'replacement_location': ['g', 1], 'retained': ['a', 'c', 'd', 'e', 'f', 'g'], 'size': 6, 'slots': [['a', 1], ['g', 3], ['c', 2], ['d', 4], ['e', 5], ['f', 2]]}Failed
variant-dependent certificate{'direction': 'down', 'removed': 'b', 'replacement_location': ['g', 1], 'retained': ['a', 'c', 'd', 'e', 'f', 'g'], 'size': 6, 'slots': [['a', 1], ['c', 2], ['d', 4], ['e', 5], ['f', 2], ['g', 3]]}{'direction': 'down', 'removed': 'b', 'replacement_location': ['g', 1], 'retained': ['a', 'c', 'd', 'e', 'f', 'g'], 'size': 6, 'slots': [['a', 1], ['g', 3], ['c', 2], ['d', 4], ['e', 5], ['f', 2]]}Failed

SHA-256 / c051f3da7e72399349fb00785d0167c57135c671237f89291a852d60a446bcd2

2 / The unsuccessful fix

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

N = 1
observations = []
def solve(d):
    a=d['slots']; i=d['index']; last=len(a)-1; out=[list(x) for x in a[:-1]]
    if i<last: out[i]=list(a[-1])
    direction='none' if i==last else ('up' if i>0 and out[i][1]<out[(i-1)//2][1] else 'down')
    return {'slots': a[:-1],
    'removed': a[i][0],
    'direction': direction,
    'replacement_location': None if i==last else [a[-1][0],i],
    'retained': sorted(x[0] for x in out),
    'size': len(a)-1}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'slots': [['a', 1]], 'index': 0}, {'slots': [], 'removed': 'a', 'direction': 'none', 'replacement_location': None, 'retained': [], 'size': 0}), ({'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['e', 8], ['f', 3], ['g', 4]], 'index': 4}, {'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['g', 4], ['f', 3]], 'removed': 'e', 'direction': 'up', 'replacement_location': ['g', 4], 'retained': ['a', 'b', 'c', 'd', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 3]], 'index': 0}, {'slots': [['c', 3], ['b', 2]], 'removed': 'a', 'direction': 'down', 'replacement_location': ['c', 0], 'retained': ['b', 'c'], 'size': 2}), ({'slots': [['a', 1], ['b', 2], ['c', 3], ['d', 4]], 'index': 3}, {'slots': [['a', 1], ['b', 2], ['c', 3]], 'removed': 'd', 'direction': 'none', 'replacement_location': None, 'retained': ['a', 'b', 'c'], 'size': 3}), ({'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['e', 8], ['f', 3], ['g', 4]], 'index': 3}, {'slots': [['a', 1], ['b', 5], ['c', 2], ['g', 4], ['e', 8], ['f', 3]], 'removed': 'd', 'direction': 'up', 'replacement_location': ['g', 3], 'retained': ['a', 'b', 'c', 'e', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 2], ['d', 4], ['e', 5], ['f', 2], ['g', 3]], 'index': 1}, {'slots': [['a', 1], ['g', 3], ['c', 2], ['d', 4], ['e', 5], ['f', 2]], 'removed': 'b', 'direction': 'down', 'replacement_location': ['g', 1], 'retained': ['a', 'c', 'd', 'e', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 2], ['d', 4], ['e', 5], ['f', 2], ['g', 3]], 'index': 1}, {'slots': [['a', 1], ['g', 3], ['c', 2], ['d', 4], ['e', 5], ['f', 2]], 'removed': 'b', 'direction': 'down', 'replacement_location': ['g', 1], 'retained': ['a', 'c', 'd', 'e', 'f', 'g'], 'size': 6})], [({'slots': [['a', 1]], 'index': 0}, {'slots': [], 'removed': 'a', 'direction': 'none', 'replacement_location': None, 'retained': [], 'size': 0}), ({'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['e', 8], ['f', 3], ['g', 4]], 'index': 4}, {'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['g', 4], ['f', 3]], 'removed': 'e', 'direction': 'up', 'replacement_location': ['g', 4], 'retained': ['a', 'b', 'c', 'd', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 3]], 'index': 0}, {'slots': [['c', 3], ['b', 2]], 'removed': 'a', 'direction': 'down', 'replacement_location': ['c', 0], 'retained': ['b', 'c'], 'size': 2}), ({'slots': [['a', 1], ['b', 2], ['c', 3], ['d', 4]], 'index': 3}, {'slots': [['a', 1], ['b', 2], ['c', 3]], 'removed': 'd', 'direction': 'none', 'replacement_location': None, 'retained': ['a', 'b', 'c'], 'size': 3}), ({'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['e', 8], ['f', 3], ['g', 4]], 'index': 3}, {'slots': [['a', 1], ['b', 5], ['c', 2], ['g', 4], ['e', 8], ['f', 3]], 'removed': 'd', 'direction': 'up', 'replacement_location': ['g', 3], 'retained': ['a', 'b', 'c', 'e', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 2], ['d', 4], ['e', 5], ['f', 2], ['g', 3]], 'index': 1}, {'slots': [['a', 1], ['g', 3], ['c', 2], ['d', 4], ['e', 5], ['f', 2]], 'removed': 'b', 'direction': 'down', 'replacement_location': ['g', 1], 'retained': ['a', 'c', 'd', 'e', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 2], ['d', 4], ['e', 5], ['f', 2], ['g', 3]], 'index': 2}, {'slots': [['a', 1], ['b', 2], ['g', 3], ['d', 4], ['e', 5], ['f', 2]], 'removed': 'c', 'direction': 'down', 'replacement_location': ['g', 2], 'retained': ['a', 'b', 'd', 'e', 'f', 'g'], 'size': 6})], [({'slots': [['a', 1]], 'index': 0}, {'slots': [], 'removed': 'a', 'direction': 'none', 'replacement_location': None, 'retained': [], 'size': 0}), ({'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['e', 8], ['f', 3], ['g', 4]], 'index': 4}, {'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['g', 4], ['f', 3]], 'removed': 'e', 'direction': 'up', 'replacement_location': ['g', 4], 'retained': ['a', 'b', 'c', 'd', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 3]], 'index': 0}, {'slots': [['c', 3], ['b', 2]], 'removed': 'a', 'direction': 'down', 'replacement_location': ['c', 0], 'retained': ['b', 'c'], 'size': 2}), ({'slots': [['a', 1], ['b', 2], ['c', 3], ['d', 4]], 'index': 3}, {'slots': [['a', 1], ['b', 2], ['c', 3]], 'removed': 'd', 'direction': 'none', 'replacement_location': None, 'retained': ['a', 'b', 'c'], 'size': 3}), ({'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['e', 8], ['f', 3], ['g', 4]], 'index': 3}, {'slots': [['a', 1], ['b', 5], ['c', 2], ['g', 4], ['e', 8], ['f', 3]], 'removed': 'd', 'direction': 'up', 'replacement_location': ['g', 3], 'retained': ['a', 'b', 'c', 'e', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 2], ['d', 4], ['e', 5], ['f', 2], ['g', 3]], 'index': 1}, {'slots': [['a', 1], ['g', 3], ['c', 2], ['d', 4], ['e', 5], ['f', 2]], 'removed': 'b', 'direction': 'down', 'replacement_location': ['g', 1], 'retained': ['a', 'c', 'd', 'e', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 2], ['d', 4], ['e', 5], ['f', 2], ['g', 3]], 'index': 3}, {'slots': [['a', 1], ['b', 2], ['c', 2], ['g', 3], ['e', 5], ['f', 2]], 'removed': 'd', 'direction': 'down', 'replacement_location': ['g', 3], 'retained': ['a', 'b', 'c', 'e', 'f', 'g'], 'size': 6})], [({'slots': [['a', 1]], 'index': 0}, {'slots': [], 'removed': 'a', 'direction': 'none', 'replacement_location': None, 'retained': [], 'size': 0}), ({'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['e', 8], ['f', 3], ['g', 4]], 'index': 4}, {'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['g', 4], ['f', 3]], 'removed': 'e', 'direction': 'up', 'replacement_location': ['g', 4], 'retained': ['a', 'b', 'c', 'd', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 3]], 'index': 0}, {'slots': [['c', 3], ['b', 2]], 'removed': 'a', 'direction': 'down', 'replacement_location': ['c', 0], 'retained': ['b', 'c'], 'size': 2}), ({'slots': [['a', 1], ['b', 2], ['c', 3], ['d', 4]], 'index': 3}, {'slots': [['a', 1], ['b', 2], ['c', 3]], 'removed': 'd', 'direction': 'none', 'replacement_location': None, 'retained': ['a', 'b', 'c'], 'size': 3}), ({'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['e', 8], ['f', 3], ['g', 4]], 'index': 3}, {'slots': [['a', 1], ['b', 5], ['c', 2], ['g', 4], ['e', 8], ['f', 3]], 'removed': 'd', 'direction': 'up', 'replacement_location': ['g', 3], 'retained': ['a', 'b', 'c', 'e', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 2], ['d', 4], ['e', 5], ['f', 2], ['g', 3]], 'index': 1}, {'slots': [['a', 1], ['g', 3], ['c', 2], ['d', 4], ['e', 5], ['f', 2]], 'removed': 'b', 'direction': 'down', 'replacement_location': ['g', 1], 'retained': ['a', 'c', 'd', 'e', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 2], ['d', 4], ['e', 5], ['f', 2], ['g', 3]], 'index': 4}, {'slots': [['a', 1], ['b', 2], ['c', 2], ['d', 4], ['g', 3], ['f', 2]], 'removed': 'e', 'direction': 'down', 'replacement_location': ['g', 4], 'retained': ['a', 'b', 'c', 'd', 'f', 'g'], 'size': 6})], [({'slots': [['a', 1]], 'index': 0}, {'slots': [], 'removed': 'a', 'direction': 'none', 'replacement_location': None, 'retained': [], 'size': 0}), ({'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['e', 8], ['f', 3], ['g', 4]], 'index': 4}, {'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['g', 4], ['f', 3]], 'removed': 'e', 'direction': 'up', 'replacement_location': ['g', 4], 'retained': ['a', 'b', 'c', 'd', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 3]], 'index': 0}, {'slots': [['c', 3], ['b', 2]], 'removed': 'a', 'direction': 'down', 'replacement_location': ['c', 0], 'retained': ['b', 'c'], 'size': 2}), ({'slots': [['a', 1], ['b', 2], ['c', 3], ['d', 4]], 'index': 3}, {'slots': [['a', 1], ['b', 2], ['c', 3]], 'removed': 'd', 'direction': 'none', 'replacement_location': None, 'retained': ['a', 'b', 'c'], 'size': 3}), ({'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['e', 8], ['f', 3], ['g', 4]], 'index': 3}, {'slots': [['a', 1], ['b', 5], ['c', 2], ['g', 4], ['e', 8], ['f', 3]], 'removed': 'd', 'direction': 'up', 'replacement_location': ['g', 3], 'retained': ['a', 'b', 'c', 'e', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 2], ['d', 4], ['e', 5], ['f', 2], ['g', 3]], 'index': 1}, {'slots': [['a', 1], ['g', 3], ['c', 2], ['d', 4], ['e', 5], ['f', 2]], 'removed': 'b', 'direction': 'down', 'replacement_location': ['g', 1], 'retained': ['a', 'c', 'd', 'e', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 2], ['d', 4], ['e', 5], ['f', 2], ['g', 3]], 'index': 5}, {'slots': [['a', 1], ['b', 2], ['c', 2], ['d', 4], ['e', 5], ['g', 3]], 'removed': 'f', 'direction': 'down', 'replacement_location': ['g', 5], 'retained': ['a', 'b', 'c', 'd', 'e', 'g'], 'size': 6})]][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{'direction': 'none', 'removed': 'a', 'replacement_location': None, 'retained': [], 'size': 0, 'slots': []}{'direction': 'none', 'removed': 'a', 'replacement_location': None, 'retained': [], 'size': 0, 'slots': []}Passed
regression certificate 2{'direction': 'up', 'removed': 'e', 'replacement_location': ['g', 4], 'retained': ['a', 'b', 'c', 'd', 'f', 'g'], 'size': 6, 'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['e', 8], ['f', 3]]}{'direction': 'up', 'removed': 'e', 'replacement_location': ['g', 4], 'retained': ['a', 'b', 'c', 'd', 'f', 'g'], 'size': 6, 'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['g', 4], ['f', 3]]}Failed
regression certificate 3{'direction': 'down', 'removed': 'a', 'replacement_location': ['c', 0], 'retained': ['b', 'c'], 'size': 2, 'slots': [['a', 1], ['b', 2]]}{'direction': 'down', 'removed': 'a', 'replacement_location': ['c', 0], 'retained': ['b', 'c'], 'size': 2, 'slots': [['c', 3], ['b', 2]]}Failed
regression certificate 4{'direction': 'none', 'removed': 'd', 'replacement_location': None, 'retained': ['a', 'b', 'c'], 'size': 3, 'slots': [['a', 1], ['b', 2], ['c', 3]]}{'direction': 'none', 'removed': 'd', 'replacement_location': None, 'retained': ['a', 'b', 'c'], 'size': 3, 'slots': [['a', 1], ['b', 2], ['c', 3]]}Passed
regression certificate 5{'direction': 'up', 'removed': 'd', 'replacement_location': ['g', 3], 'retained': ['a', 'b', 'c', 'e', 'f', 'g'], 'size': 6, 'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['e', 8], ['f', 3]]}{'direction': 'up', 'removed': 'd', 'replacement_location': ['g', 3], 'retained': ['a', 'b', 'c', 'e', 'f', 'g'], 'size': 6, 'slots': [['a', 1], ['b', 5], ['c', 2], ['g', 4], ['e', 8], ['f', 3]]}Failed
regression certificate 6{'direction': 'down', 'removed': 'b', 'replacement_location': ['g', 1], 'retained': ['a', 'c', 'd', 'e', 'f', 'g'], 'size': 6, 'slots': [['a', 1], ['b', 2], ['c', 2], ['d', 4], ['e', 5], ['f', 2]]}{'direction': 'down', 'removed': 'b', 'replacement_location': ['g', 1], 'retained': ['a', 'c', 'd', 'e', 'f', 'g'], 'size': 6, 'slots': [['a', 1], ['g', 3], ['c', 2], ['d', 4], ['e', 5], ['f', 2]]}Failed
variant-dependent certificate{'direction': 'down', 'removed': 'b', 'replacement_location': ['g', 1], 'retained': ['a', 'c', 'd', 'e', 'f', 'g'], 'size': 6, 'slots': [['a', 1], ['b', 2], ['c', 2], ['d', 4], ['e', 5], ['f', 2]]}{'direction': 'down', 'removed': 'b', 'replacement_location': ['g', 1], 'retained': ['a', 'c', 'd', 'e', 'f', 'g'], 'size': 6, 'slots': [['a', 1], ['g', 3], ['c', 2], ['d', 4], ['e', 5], ['f', 2]]}Failed

SHA-256 / ac741327e081b1624e119edfb546157f383d29afb783854fc5aa1ba210061bdb

3 / The verified repair

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

N = 1
observations = []
def solve(d):
    a=d['slots']; i=d['index']; last=len(a)-1; out=[list(x) for x in a[:-1]]
    if i<last: out[i]=list(a[-1])
    direction='none' if i==last else ('up' if i>0 and out[i][1]<out[(i-1)//2][1] else 'down')
    return {'slots': out,
    'removed': a[i][0],
    'direction': direction,
    'replacement_location': None if i==last else [a[-1][0],i],
    'retained': sorted(x[0] for x in out),
    'size': len(a)-1}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'slots': [['a', 1]], 'index': 0}, {'slots': [], 'removed': 'a', 'direction': 'none', 'replacement_location': None, 'retained': [], 'size': 0}), ({'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['e', 8], ['f', 3], ['g', 4]], 'index': 4}, {'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['g', 4], ['f', 3]], 'removed': 'e', 'direction': 'up', 'replacement_location': ['g', 4], 'retained': ['a', 'b', 'c', 'd', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 3]], 'index': 0}, {'slots': [['c', 3], ['b', 2]], 'removed': 'a', 'direction': 'down', 'replacement_location': ['c', 0], 'retained': ['b', 'c'], 'size': 2}), ({'slots': [['a', 1], ['b', 2], ['c', 3], ['d', 4]], 'index': 3}, {'slots': [['a', 1], ['b', 2], ['c', 3]], 'removed': 'd', 'direction': 'none', 'replacement_location': None, 'retained': ['a', 'b', 'c'], 'size': 3}), ({'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['e', 8], ['f', 3], ['g', 4]], 'index': 3}, {'slots': [['a', 1], ['b', 5], ['c', 2], ['g', 4], ['e', 8], ['f', 3]], 'removed': 'd', 'direction': 'up', 'replacement_location': ['g', 3], 'retained': ['a', 'b', 'c', 'e', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 2], ['d', 4], ['e', 5], ['f', 2], ['g', 3]], 'index': 1}, {'slots': [['a', 1], ['g', 3], ['c', 2], ['d', 4], ['e', 5], ['f', 2]], 'removed': 'b', 'direction': 'down', 'replacement_location': ['g', 1], 'retained': ['a', 'c', 'd', 'e', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 2], ['d', 4], ['e', 5], ['f', 2], ['g', 3]], 'index': 1}, {'slots': [['a', 1], ['g', 3], ['c', 2], ['d', 4], ['e', 5], ['f', 2]], 'removed': 'b', 'direction': 'down', 'replacement_location': ['g', 1], 'retained': ['a', 'c', 'd', 'e', 'f', 'g'], 'size': 6})], [({'slots': [['a', 1]], 'index': 0}, {'slots': [], 'removed': 'a', 'direction': 'none', 'replacement_location': None, 'retained': [], 'size': 0}), ({'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['e', 8], ['f', 3], ['g', 4]], 'index': 4}, {'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['g', 4], ['f', 3]], 'removed': 'e', 'direction': 'up', 'replacement_location': ['g', 4], 'retained': ['a', 'b', 'c', 'd', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 3]], 'index': 0}, {'slots': [['c', 3], ['b', 2]], 'removed': 'a', 'direction': 'down', 'replacement_location': ['c', 0], 'retained': ['b', 'c'], 'size': 2}), ({'slots': [['a', 1], ['b', 2], ['c', 3], ['d', 4]], 'index': 3}, {'slots': [['a', 1], ['b', 2], ['c', 3]], 'removed': 'd', 'direction': 'none', 'replacement_location': None, 'retained': ['a', 'b', 'c'], 'size': 3}), ({'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['e', 8], ['f', 3], ['g', 4]], 'index': 3}, {'slots': [['a', 1], ['b', 5], ['c', 2], ['g', 4], ['e', 8], ['f', 3]], 'removed': 'd', 'direction': 'up', 'replacement_location': ['g', 3], 'retained': ['a', 'b', 'c', 'e', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 2], ['d', 4], ['e', 5], ['f', 2], ['g', 3]], 'index': 1}, {'slots': [['a', 1], ['g', 3], ['c', 2], ['d', 4], ['e', 5], ['f', 2]], 'removed': 'b', 'direction': 'down', 'replacement_location': ['g', 1], 'retained': ['a', 'c', 'd', 'e', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 2], ['d', 4], ['e', 5], ['f', 2], ['g', 3]], 'index': 2}, {'slots': [['a', 1], ['b', 2], ['g', 3], ['d', 4], ['e', 5], ['f', 2]], 'removed': 'c', 'direction': 'down', 'replacement_location': ['g', 2], 'retained': ['a', 'b', 'd', 'e', 'f', 'g'], 'size': 6})], [({'slots': [['a', 1]], 'index': 0}, {'slots': [], 'removed': 'a', 'direction': 'none', 'replacement_location': None, 'retained': [], 'size': 0}), ({'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['e', 8], ['f', 3], ['g', 4]], 'index': 4}, {'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['g', 4], ['f', 3]], 'removed': 'e', 'direction': 'up', 'replacement_location': ['g', 4], 'retained': ['a', 'b', 'c', 'd', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 3]], 'index': 0}, {'slots': [['c', 3], ['b', 2]], 'removed': 'a', 'direction': 'down', 'replacement_location': ['c', 0], 'retained': ['b', 'c'], 'size': 2}), ({'slots': [['a', 1], ['b', 2], ['c', 3], ['d', 4]], 'index': 3}, {'slots': [['a', 1], ['b', 2], ['c', 3]], 'removed': 'd', 'direction': 'none', 'replacement_location': None, 'retained': ['a', 'b', 'c'], 'size': 3}), ({'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['e', 8], ['f', 3], ['g', 4]], 'index': 3}, {'slots': [['a', 1], ['b', 5], ['c', 2], ['g', 4], ['e', 8], ['f', 3]], 'removed': 'd', 'direction': 'up', 'replacement_location': ['g', 3], 'retained': ['a', 'b', 'c', 'e', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 2], ['d', 4], ['e', 5], ['f', 2], ['g', 3]], 'index': 1}, {'slots': [['a', 1], ['g', 3], ['c', 2], ['d', 4], ['e', 5], ['f', 2]], 'removed': 'b', 'direction': 'down', 'replacement_location': ['g', 1], 'retained': ['a', 'c', 'd', 'e', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 2], ['d', 4], ['e', 5], ['f', 2], ['g', 3]], 'index': 3}, {'slots': [['a', 1], ['b', 2], ['c', 2], ['g', 3], ['e', 5], ['f', 2]], 'removed': 'd', 'direction': 'down', 'replacement_location': ['g', 3], 'retained': ['a', 'b', 'c', 'e', 'f', 'g'], 'size': 6})], [({'slots': [['a', 1]], 'index': 0}, {'slots': [], 'removed': 'a', 'direction': 'none', 'replacement_location': None, 'retained': [], 'size': 0}), ({'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['e', 8], ['f', 3], ['g', 4]], 'index': 4}, {'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['g', 4], ['f', 3]], 'removed': 'e', 'direction': 'up', 'replacement_location': ['g', 4], 'retained': ['a', 'b', 'c', 'd', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 3]], 'index': 0}, {'slots': [['c', 3], ['b', 2]], 'removed': 'a', 'direction': 'down', 'replacement_location': ['c', 0], 'retained': ['b', 'c'], 'size': 2}), ({'slots': [['a', 1], ['b', 2], ['c', 3], ['d', 4]], 'index': 3}, {'slots': [['a', 1], ['b', 2], ['c', 3]], 'removed': 'd', 'direction': 'none', 'replacement_location': None, 'retained': ['a', 'b', 'c'], 'size': 3}), ({'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['e', 8], ['f', 3], ['g', 4]], 'index': 3}, {'slots': [['a', 1], ['b', 5], ['c', 2], ['g', 4], ['e', 8], ['f', 3]], 'removed': 'd', 'direction': 'up', 'replacement_location': ['g', 3], 'retained': ['a', 'b', 'c', 'e', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 2], ['d', 4], ['e', 5], ['f', 2], ['g', 3]], 'index': 1}, {'slots': [['a', 1], ['g', 3], ['c', 2], ['d', 4], ['e', 5], ['f', 2]], 'removed': 'b', 'direction': 'down', 'replacement_location': ['g', 1], 'retained': ['a', 'c', 'd', 'e', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 2], ['d', 4], ['e', 5], ['f', 2], ['g', 3]], 'index': 4}, {'slots': [['a', 1], ['b', 2], ['c', 2], ['d', 4], ['g', 3], ['f', 2]], 'removed': 'e', 'direction': 'down', 'replacement_location': ['g', 4], 'retained': ['a', 'b', 'c', 'd', 'f', 'g'], 'size': 6})], [({'slots': [['a', 1]], 'index': 0}, {'slots': [], 'removed': 'a', 'direction': 'none', 'replacement_location': None, 'retained': [], 'size': 0}), ({'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['e', 8], ['f', 3], ['g', 4]], 'index': 4}, {'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['g', 4], ['f', 3]], 'removed': 'e', 'direction': 'up', 'replacement_location': ['g', 4], 'retained': ['a', 'b', 'c', 'd', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 3]], 'index': 0}, {'slots': [['c', 3], ['b', 2]], 'removed': 'a', 'direction': 'down', 'replacement_location': ['c', 0], 'retained': ['b', 'c'], 'size': 2}), ({'slots': [['a', 1], ['b', 2], ['c', 3], ['d', 4]], 'index': 3}, {'slots': [['a', 1], ['b', 2], ['c', 3]], 'removed': 'd', 'direction': 'none', 'replacement_location': None, 'retained': ['a', 'b', 'c'], 'size': 3}), ({'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['e', 8], ['f', 3], ['g', 4]], 'index': 3}, {'slots': [['a', 1], ['b', 5], ['c', 2], ['g', 4], ['e', 8], ['f', 3]], 'removed': 'd', 'direction': 'up', 'replacement_location': ['g', 3], 'retained': ['a', 'b', 'c', 'e', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 2], ['d', 4], ['e', 5], ['f', 2], ['g', 3]], 'index': 1}, {'slots': [['a', 1], ['g', 3], ['c', 2], ['d', 4], ['e', 5], ['f', 2]], 'removed': 'b', 'direction': 'down', 'replacement_location': ['g', 1], 'retained': ['a', 'c', 'd', 'e', 'f', 'g'], 'size': 6}), ({'slots': [['a', 1], ['b', 2], ['c', 2], ['d', 4], ['e', 5], ['f', 2], ['g', 3]], 'index': 5}, {'slots': [['a', 1], ['b', 2], ['c', 2], ['d', 4], ['e', 5], ['g', 3]], 'removed': 'f', 'direction': 'down', 'replacement_location': ['g', 5], 'retained': ['a', 'b', 'c', 'd', 'e', 'g'], 'size': 6})]][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{'direction': 'none', 'removed': 'a', 'replacement_location': None, 'retained': [], 'size': 0, 'slots': []}{'direction': 'none', 'removed': 'a', 'replacement_location': None, 'retained': [], 'size': 0, 'slots': []}Passed
regression certificate 2{'direction': 'up', 'removed': 'e', 'replacement_location': ['g', 4], 'retained': ['a', 'b', 'c', 'd', 'f', 'g'], 'size': 6, 'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['g', 4], ['f', 3]]}{'direction': 'up', 'removed': 'e', 'replacement_location': ['g', 4], 'retained': ['a', 'b', 'c', 'd', 'f', 'g'], 'size': 6, 'slots': [['a', 1], ['b', 5], ['c', 2], ['d', 7], ['g', 4], ['f', 3]]}Passed
regression certificate 3{'direction': 'down', 'removed': 'a', 'replacement_location': ['c', 0], 'retained': ['b', 'c'], 'size': 2, 'slots': [['c', 3], ['b', 2]]}{'direction': 'down', 'removed': 'a', 'replacement_location': ['c', 0], 'retained': ['b', 'c'], 'size': 2, 'slots': [['c', 3], ['b', 2]]}Passed
regression certificate 4{'direction': 'none', 'removed': 'd', 'replacement_location': None, 'retained': ['a', 'b', 'c'], 'size': 3, 'slots': [['a', 1], ['b', 2], ['c', 3]]}{'direction': 'none', 'removed': 'd', 'replacement_location': None, 'retained': ['a', 'b', 'c'], 'size': 3, 'slots': [['a', 1], ['b', 2], ['c', 3]]}Passed
regression certificate 5{'direction': 'up', 'removed': 'd', 'replacement_location': ['g', 3], 'retained': ['a', 'b', 'c', 'e', 'f', 'g'], 'size': 6, 'slots': [['a', 1], ['b', 5], ['c', 2], ['g', 4], ['e', 8], ['f', 3]]}{'direction': 'up', 'removed': 'd', 'replacement_location': ['g', 3], 'retained': ['a', 'b', 'c', 'e', 'f', 'g'], 'size': 6, 'slots': [['a', 1], ['b', 5], ['c', 2], ['g', 4], ['e', 8], ['f', 3]]}Passed
regression certificate 6{'direction': 'down', 'removed': 'b', 'replacement_location': ['g', 1], 'retained': ['a', 'c', 'd', 'e', 'f', 'g'], 'size': 6, 'slots': [['a', 1], ['g', 3], ['c', 2], ['d', 4], ['e', 5], ['f', 2]]}{'direction': 'down', 'removed': 'b', 'replacement_location': ['g', 1], 'retained': ['a', 'c', 'd', 'e', 'f', 'g'], 'size': 6, 'slots': [['a', 1], ['g', 3], ['c', 2], ['d', 4], ['e', 5], ['f', 2]]}Passed
variant-dependent certificate{'direction': 'down', 'removed': 'b', 'replacement_location': ['g', 1], 'retained': ['a', 'c', 'd', 'e', 'f', 'g'], 'size': 6, 'slots': [['a', 1], ['g', 3], ['c', 2], ['d', 4], ['e', 5], ['f', 2]]}{'direction': 'down', 'removed': 'b', 'replacement_location': ['g', 1], 'retained': ['a', 'c', 'd', 'e', 'f', 'g'], 'size': 6, 'slots': [['a', 1], ['g', 3], ['c', 2], ['d', 4], ['e', 5], ['f', 2]]}Passed

SHA-256 / 6b1a6cecfd05fa25ff52a8e10d893a98f661cfec641351dcc27ecf7eff59ad01

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

Case digest / 0086e463187c3a9775d5df891dbbd78f5a68a4bf91352456a54bc66e076fcbcf