FAILURE MAP
← Case archive

FA-41271 / Heap invariants / Open access

Tournament active leaves occupy original slots before trailing padding · case 01

The bounded tournament padding certificate reports an incorrect active indices.

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

ROOT CAUSE

Tournament active leaves occupy original slots before trailing padding.

VERIFIED REPAIR

Derive active indices using list(range(m)) under the stated bounded certificate contract.

Unsuccessful approach: The local patch uses list(range(c-m,c)) and still violates the stated relation.

Case contract

A tournament is built from m real leaves [id,key]. Round leaf capacity to the next power of two (empty capacity one) and append inactive None pads. Inactive pads always lose without numeric sentinel assumptions. Report capacity, padded leaves, champion id with arrival-order ties, match rounds, active-leaf indices, and key-comparison count m-1 for m>0.

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['leaves']; m=len(a); c=1
    while c<m: c*=2
    padded=a+[None]*(c-m); champion=min(range(m),key=lambda i:a[i][1]) if m else None
    return {'capacity': c,
    'leaves': padded,
    'champion': None if champion is None else a[champion][0],
    'rounds': c.bit_length()-1,
    'active_indices': list(range(c)),
    'key_comparisons': max(0,m-1)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], None, None], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5], 'key_comparisons': 5})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], None], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5, 6], 'key_comparisons': 6})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2]], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7], 'key_comparisons': 7})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3]]}, {'capacity': 16, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], None, None, None, None, None, None, None], 'champion': '100', 'rounds': 4, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7, 8], 'key_comparisons': 8})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], ['104', 4]]}, {'capacity': 16, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], ['104', 4], None, None, None, None, None, None], 'champion': '100', 'rounds': 4, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 'key_comparisons': 9})]][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{'active_indices': [0], 'capacity': 1, 'champion': None, 'key_comparisons': 0, 'leaves': [None], 'rounds': 0}{'active_indices': [], 'capacity': 1, 'champion': None, 'key_comparisons': 0, 'leaves': [None], 'rounds': 0}Failed
regression certificate 2{'active_indices': [0], 'capacity': 1, 'champion': 'x', 'key_comparisons': 0, 'leaves': [['x', 50]], 'rounds': 0}{'active_indices': [0], 'capacity': 1, 'champion': 'x', 'key_comparisons': 0, 'leaves': [['x', 50]], 'rounds': 0}Passed
regression certificate 3{'active_indices': [0, 1], 'capacity': 2, 'champion': 'z', 'key_comparisons': 1, 'leaves': [['z', 3], ['a', 3]], 'rounds': 1}{'active_indices': [0, 1], 'capacity': 2, 'champion': 'z', 'key_comparisons': 1, 'leaves': [['z', 3], ['a', 3]], 'rounds': 1}Passed
regression certificate 4{'active_indices': [0, 1, 2, 3], 'capacity': 4, 'champion': 'b', 'key_comparisons': 2, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'rounds': 2}{'active_indices': [0, 1, 2], 'capacity': 4, 'champion': 'b', 'key_comparisons': 2, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'rounds': 2}Failed
regression certificate 5{'active_indices': [0, 1, 2, 3], 'capacity': 4, 'champion': 'a', 'key_comparisons': 3, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'rounds': 2}{'active_indices': [0, 1, 2, 3], 'capacity': 4, 'champion': 'a', 'key_comparisons': 3, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'rounds': 2}Passed
regression certificate 6{'active_indices': [0, 1, 2, 3, 4, 5, 6, 7], 'capacity': 8, 'champion': 'a', 'key_comparisons': 4, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'rounds': 3}{'active_indices': [0, 1, 2, 3, 4], 'capacity': 8, 'champion': 'a', 'key_comparisons': 4, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'rounds': 3}Failed
variant-dependent certificate{'active_indices': [0, 1, 2, 3, 4, 5, 6, 7], 'capacity': 8, 'champion': '100', 'key_comparisons': 5, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], None, None], 'rounds': 3}{'active_indices': [0, 1, 2, 3, 4, 5], 'capacity': 8, 'champion': '100', 'key_comparisons': 5, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], None, None], 'rounds': 3}Failed

SHA-256 / 9e685f77d63c14926d3319d1383395f36434d7601b813b2717a107972da683c7

2 / The unsuccessful fix

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

N = 1
observations = []
def solve(d):
    a=d['leaves']; m=len(a); c=1
    while c<m: c*=2
    padded=a+[None]*(c-m); champion=min(range(m),key=lambda i:a[i][1]) if m else None
    return {'capacity': c,
    'leaves': padded,
    'champion': None if champion is None else a[champion][0],
    'rounds': c.bit_length()-1,
    'active_indices': list(range(c-m,c)),
    'key_comparisons': max(0,m-1)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], None, None], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5], 'key_comparisons': 5})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], None], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5, 6], 'key_comparisons': 6})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2]], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7], 'key_comparisons': 7})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3]]}, {'capacity': 16, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], None, None, None, None, None, None, None], 'champion': '100', 'rounds': 4, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7, 8], 'key_comparisons': 8})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], ['104', 4]]}, {'capacity': 16, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], ['104', 4], None, None, None, None, None, None], 'champion': '100', 'rounds': 4, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 'key_comparisons': 9})]][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{'active_indices': [], 'capacity': 1, 'champion': None, 'key_comparisons': 0, 'leaves': [None], 'rounds': 0}{'active_indices': [], 'capacity': 1, 'champion': None, 'key_comparisons': 0, 'leaves': [None], 'rounds': 0}Passed
regression certificate 2{'active_indices': [0], 'capacity': 1, 'champion': 'x', 'key_comparisons': 0, 'leaves': [['x', 50]], 'rounds': 0}{'active_indices': [0], 'capacity': 1, 'champion': 'x', 'key_comparisons': 0, 'leaves': [['x', 50]], 'rounds': 0}Passed
regression certificate 3{'active_indices': [0, 1], 'capacity': 2, 'champion': 'z', 'key_comparisons': 1, 'leaves': [['z', 3], ['a', 3]], 'rounds': 1}{'active_indices': [0, 1], 'capacity': 2, 'champion': 'z', 'key_comparisons': 1, 'leaves': [['z', 3], ['a', 3]], 'rounds': 1}Passed
regression certificate 4{'active_indices': [1, 2, 3], 'capacity': 4, 'champion': 'b', 'key_comparisons': 2, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'rounds': 2}{'active_indices': [0, 1, 2], 'capacity': 4, 'champion': 'b', 'key_comparisons': 2, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'rounds': 2}Failed
regression certificate 5{'active_indices': [0, 1, 2, 3], 'capacity': 4, 'champion': 'a', 'key_comparisons': 3, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'rounds': 2}{'active_indices': [0, 1, 2, 3], 'capacity': 4, 'champion': 'a', 'key_comparisons': 3, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'rounds': 2}Passed
regression certificate 6{'active_indices': [3, 4, 5, 6, 7], 'capacity': 8, 'champion': 'a', 'key_comparisons': 4, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'rounds': 3}{'active_indices': [0, 1, 2, 3, 4], 'capacity': 8, 'champion': 'a', 'key_comparisons': 4, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'rounds': 3}Failed
variant-dependent certificate{'active_indices': [2, 3, 4, 5, 6, 7], 'capacity': 8, 'champion': '100', 'key_comparisons': 5, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], None, None], 'rounds': 3}{'active_indices': [0, 1, 2, 3, 4, 5], 'capacity': 8, 'champion': '100', 'key_comparisons': 5, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], None, None], 'rounds': 3}Failed

SHA-256 / 7755388d4b9138b0f60921b9a759141dc24a6997fb4838853aac9f8c077cc2b2

3 / The verified repair

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

N = 1
observations = []
def solve(d):
    a=d['leaves']; m=len(a); c=1
    while c<m: c*=2
    padded=a+[None]*(c-m); champion=min(range(m),key=lambda i:a[i][1]) if m else None
    return {'capacity': c,
    'leaves': padded,
    'champion': None if champion is None else a[champion][0],
    'rounds': c.bit_length()-1,
    'active_indices': list(range(m)),
    'key_comparisons': max(0,m-1)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], None, None], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5], 'key_comparisons': 5})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], None], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5, 6], 'key_comparisons': 6})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2]], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7], 'key_comparisons': 7})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3]]}, {'capacity': 16, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], None, None, None, None, None, None, None], 'champion': '100', 'rounds': 4, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7, 8], 'key_comparisons': 8})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], ['104', 4]]}, {'capacity': 16, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], ['104', 4], None, None, None, None, None, None], 'champion': '100', 'rounds': 4, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 'key_comparisons': 9})]][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{'active_indices': [], 'capacity': 1, 'champion': None, 'key_comparisons': 0, 'leaves': [None], 'rounds': 0}{'active_indices': [], 'capacity': 1, 'champion': None, 'key_comparisons': 0, 'leaves': [None], 'rounds': 0}Passed
regression certificate 2{'active_indices': [0], 'capacity': 1, 'champion': 'x', 'key_comparisons': 0, 'leaves': [['x', 50]], 'rounds': 0}{'active_indices': [0], 'capacity': 1, 'champion': 'x', 'key_comparisons': 0, 'leaves': [['x', 50]], 'rounds': 0}Passed
regression certificate 3{'active_indices': [0, 1], 'capacity': 2, 'champion': 'z', 'key_comparisons': 1, 'leaves': [['z', 3], ['a', 3]], 'rounds': 1}{'active_indices': [0, 1], 'capacity': 2, 'champion': 'z', 'key_comparisons': 1, 'leaves': [['z', 3], ['a', 3]], 'rounds': 1}Passed
regression certificate 4{'active_indices': [0, 1, 2], 'capacity': 4, 'champion': 'b', 'key_comparisons': 2, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'rounds': 2}{'active_indices': [0, 1, 2], 'capacity': 4, 'champion': 'b', 'key_comparisons': 2, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'rounds': 2}Passed
regression certificate 5{'active_indices': [0, 1, 2, 3], 'capacity': 4, 'champion': 'a', 'key_comparisons': 3, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'rounds': 2}{'active_indices': [0, 1, 2, 3], 'capacity': 4, 'champion': 'a', 'key_comparisons': 3, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'rounds': 2}Passed
regression certificate 6{'active_indices': [0, 1, 2, 3, 4], 'capacity': 8, 'champion': 'a', 'key_comparisons': 4, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'rounds': 3}{'active_indices': [0, 1, 2, 3, 4], 'capacity': 8, 'champion': 'a', 'key_comparisons': 4, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'rounds': 3}Passed
variant-dependent certificate{'active_indices': [0, 1, 2, 3, 4, 5], 'capacity': 8, 'champion': '100', 'key_comparisons': 5, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], None, None], 'rounds': 3}{'active_indices': [0, 1, 2, 3, 4, 5], 'capacity': 8, 'champion': '100', 'key_comparisons': 5, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], None, None], 'rounds': 3}Passed

SHA-256 / 32147abfda0ff11c9090177e2e25e22e0c7cceaba3c6fb8ce2ae71d0ec3f1cbd

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

Case digest / 0e557bb7edc66dbe5eab91708997af7cd65b6f73d7a3c371737fabaa5aa6d756