FAILURE MAP
← Case archive

FA-40156 / Heap invariants / Open access

Pairing pass carries only an unpaired final child · case 01

The bounded pairing pass certificate reports an incorrect carry.

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

ROOT CAUSE

Pairing pass carries only an unpaired final child.

VERIFIED REPAIR

Derive carry using a[-1][0] if len(a)%2 else None under the stated bounded certificate contract.

Unsuccessful approach: The local patch uses a[0][0] if len(a)%2 else None and still violates the stated relation.

Case contract

For delete-min pairing pass, children are [id,key]. Pair adjacent children left-to-right, keeping the left on equal keys. An odd last child survives. Return pair indices, winning ids, losing ids, odd carry id, second-pass traversal order, and comparison count. The second pass folds from right to left.

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['children']; pairs=[(a[i],a[i+1]) for i in range(0,len(a)-1,2)]
    wins=[x if x[1]<=y[1] else y for x,y in pairs]
    loses=[y if x[1]<=y[1] else x for x,y in pairs]
    first=wins+([a[-1]] if len(a)%2 else [])
    return {'pairs': [[i,i+1] for i in range(0,len(a)-1,2)],
    'winners': [x[0] for x in wins],
    'losers': [x[0] for x in loses],
    'carry': a[-1][0] if a else None,
    'fold_order': [x[0] for x in reversed(first)],
    'comparisons': len(pairs)+max(0,len(first)-1)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': 100, 'fold_order': [100, 5, 6, 8], 'comparisons': 6})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 2], [101, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7]], 'winners': [8, 6, 5, 101], 'losers': [9, 7, 4, 100], 'carry': None, 'fold_order': [101, 5, 6, 8], 'comparisons': 7})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 3], [101, 2], [102, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7]], 'winners': [8, 6, 5, 101], 'losers': [9, 7, 4, 100], 'carry': 102, 'fold_order': [102, 101, 5, 6, 8], 'comparisons': 8})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 4], [101, 3], [102, 2], [103, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7], [8, 9]], 'winners': [8, 6, 5, 101, 103], 'losers': [9, 7, 4, 100, 102], 'carry': None, 'fold_order': [103, 101, 5, 6, 8], 'comparisons': 9})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 5], [101, 4], [102, 3], [103, 2], [104, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7], [8, 9]], 'winners': [8, 6, 5, 101, 103], 'losers': [9, 7, 4, 100, 102], 'carry': 104, 'fold_order': [104, 103, 101, 5, 6, 8], 'comparisons': 10})]][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{'carry': None, 'comparisons': 0, 'fold_order': [], 'losers': [], 'pairs': [], 'winners': []}{'carry': None, 'comparisons': 0, 'fold_order': [], 'losers': [], 'pairs': [], 'winners': []}Passed
regression certificate 2{'carry': 8, 'comparisons': 0, 'fold_order': [8], 'losers': [], 'pairs': [], 'winners': []}{'carry': 8, 'comparisons': 0, 'fold_order': [8], 'losers': [], 'pairs': [], 'winners': []}Passed
regression certificate 3{'carry': 2, 'comparisons': 1, 'fold_order': [2], 'losers': [8], 'pairs': [[0, 1]], 'winners': [2]}{'carry': None, 'comparisons': 1, 'fold_order': [2], 'losers': [8], 'pairs': [[0, 1]], 'winners': [2]}Failed
regression certificate 4{'carry': 1, 'comparisons': 2, 'fold_order': [1, 7], 'losers': [4], 'pairs': [[0, 1]], 'winners': [7]}{'carry': 1, 'comparisons': 2, 'fold_order': [1, 7], 'losers': [4], 'pairs': [[0, 1]], 'winners': [7]}Passed
regression certificate 5{'carry': 9, 'comparisons': 3, 'fold_order': [9, 4], 'losers': [7, 1], 'pairs': [[0, 1], [2, 3]], 'winners': [4, 9]}{'carry': None, 'comparisons': 3, 'fold_order': [9, 4], 'losers': [7, 1], 'pairs': [[0, 1], [2, 3]], 'winners': [4, 9]}Failed
regression certificate 6{'carry': 4, 'comparisons': 5, 'fold_order': [5, 6, 8], 'losers': [9, 7, 4], 'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5]}{'carry': None, 'comparisons': 5, 'fold_order': [5, 6, 8], 'losers': [9, 7, 4], 'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5]}Failed
variant-dependent certificate{'carry': 100, 'comparisons': 6, 'fold_order': [100, 5, 6, 8], 'losers': [9, 7, 4], 'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5]}{'carry': 100, 'comparisons': 6, 'fold_order': [100, 5, 6, 8], 'losers': [9, 7, 4], 'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5]}Passed

SHA-256 / b7e3bdf4922980899ef9f40ea2d466b065364aea902dc119495d4e7860d4590f

2 / The unsuccessful fix

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

N = 1
observations = []
def solve(d):
    a=d['children']; pairs=[(a[i],a[i+1]) for i in range(0,len(a)-1,2)]
    wins=[x if x[1]<=y[1] else y for x,y in pairs]
    loses=[y if x[1]<=y[1] else x for x,y in pairs]
    first=wins+([a[-1]] if len(a)%2 else [])
    return {'pairs': [[i,i+1] for i in range(0,len(a)-1,2)],
    'winners': [x[0] for x in wins],
    'losers': [x[0] for x in loses],
    'carry': a[0][0] if len(a)%2 else None,
    'fold_order': [x[0] for x in reversed(first)],
    'comparisons': len(pairs)+max(0,len(first)-1)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': 100, 'fold_order': [100, 5, 6, 8], 'comparisons': 6})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 2], [101, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7]], 'winners': [8, 6, 5, 101], 'losers': [9, 7, 4, 100], 'carry': None, 'fold_order': [101, 5, 6, 8], 'comparisons': 7})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 3], [101, 2], [102, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7]], 'winners': [8, 6, 5, 101], 'losers': [9, 7, 4, 100], 'carry': 102, 'fold_order': [102, 101, 5, 6, 8], 'comparisons': 8})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 4], [101, 3], [102, 2], [103, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7], [8, 9]], 'winners': [8, 6, 5, 101, 103], 'losers': [9, 7, 4, 100, 102], 'carry': None, 'fold_order': [103, 101, 5, 6, 8], 'comparisons': 9})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 5], [101, 4], [102, 3], [103, 2], [104, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7], [8, 9]], 'winners': [8, 6, 5, 101, 103], 'losers': [9, 7, 4, 100, 102], 'carry': 104, 'fold_order': [104, 103, 101, 5, 6, 8], 'comparisons': 10})]][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{'carry': None, 'comparisons': 0, 'fold_order': [], 'losers': [], 'pairs': [], 'winners': []}{'carry': None, 'comparisons': 0, 'fold_order': [], 'losers': [], 'pairs': [], 'winners': []}Passed
regression certificate 2{'carry': 8, 'comparisons': 0, 'fold_order': [8], 'losers': [], 'pairs': [], 'winners': []}{'carry': 8, 'comparisons': 0, 'fold_order': [8], 'losers': [], 'pairs': [], 'winners': []}Passed
regression certificate 3{'carry': None, 'comparisons': 1, 'fold_order': [2], 'losers': [8], 'pairs': [[0, 1]], 'winners': [2]}{'carry': None, 'comparisons': 1, 'fold_order': [2], 'losers': [8], 'pairs': [[0, 1]], 'winners': [2]}Passed
regression certificate 4{'carry': 4, 'comparisons': 2, 'fold_order': [1, 7], 'losers': [4], 'pairs': [[0, 1]], 'winners': [7]}{'carry': 1, 'comparisons': 2, 'fold_order': [1, 7], 'losers': [4], 'pairs': [[0, 1]], 'winners': [7]}Failed
regression certificate 5{'carry': None, 'comparisons': 3, 'fold_order': [9, 4], 'losers': [7, 1], 'pairs': [[0, 1], [2, 3]], 'winners': [4, 9]}{'carry': None, 'comparisons': 3, 'fold_order': [9, 4], 'losers': [7, 1], 'pairs': [[0, 1], [2, 3]], 'winners': [4, 9]}Passed
regression certificate 6{'carry': None, 'comparisons': 5, 'fold_order': [5, 6, 8], 'losers': [9, 7, 4], 'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5]}{'carry': None, 'comparisons': 5, 'fold_order': [5, 6, 8], 'losers': [9, 7, 4], 'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5]}Passed
variant-dependent certificate{'carry': 9, 'comparisons': 6, 'fold_order': [100, 5, 6, 8], 'losers': [9, 7, 4], 'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5]}{'carry': 100, 'comparisons': 6, 'fold_order': [100, 5, 6, 8], 'losers': [9, 7, 4], 'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5]}Failed

SHA-256 / 1c354400f838776a045e88510e00b14779758698e7663333db4d6c78046331ba

3 / The verified repair

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

N = 1
observations = []
def solve(d):
    a=d['children']; pairs=[(a[i],a[i+1]) for i in range(0,len(a)-1,2)]
    wins=[x if x[1]<=y[1] else y for x,y in pairs]
    loses=[y if x[1]<=y[1] else x for x,y in pairs]
    first=wins+([a[-1]] if len(a)%2 else [])
    return {'pairs': [[i,i+1] for i in range(0,len(a)-1,2)],
    'winners': [x[0] for x in wins],
    'losers': [x[0] for x in loses],
    'carry': a[-1][0] if len(a)%2 else None,
    'fold_order': [x[0] for x in reversed(first)],
    'comparisons': len(pairs)+max(0,len(first)-1)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': 100, 'fold_order': [100, 5, 6, 8], 'comparisons': 6})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 2], [101, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7]], 'winners': [8, 6, 5, 101], 'losers': [9, 7, 4, 100], 'carry': None, 'fold_order': [101, 5, 6, 8], 'comparisons': 7})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 3], [101, 2], [102, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7]], 'winners': [8, 6, 5, 101], 'losers': [9, 7, 4, 100], 'carry': 102, 'fold_order': [102, 101, 5, 6, 8], 'comparisons': 8})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 4], [101, 3], [102, 2], [103, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7], [8, 9]], 'winners': [8, 6, 5, 101, 103], 'losers': [9, 7, 4, 100, 102], 'carry': None, 'fold_order': [103, 101, 5, 6, 8], 'comparisons': 9})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 5], [101, 4], [102, 3], [103, 2], [104, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7], [8, 9]], 'winners': [8, 6, 5, 101, 103], 'losers': [9, 7, 4, 100, 102], 'carry': 104, 'fold_order': [104, 103, 101, 5, 6, 8], 'comparisons': 10})]][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{'carry': None, 'comparisons': 0, 'fold_order': [], 'losers': [], 'pairs': [], 'winners': []}{'carry': None, 'comparisons': 0, 'fold_order': [], 'losers': [], 'pairs': [], 'winners': []}Passed
regression certificate 2{'carry': 8, 'comparisons': 0, 'fold_order': [8], 'losers': [], 'pairs': [], 'winners': []}{'carry': 8, 'comparisons': 0, 'fold_order': [8], 'losers': [], 'pairs': [], 'winners': []}Passed
regression certificate 3{'carry': None, 'comparisons': 1, 'fold_order': [2], 'losers': [8], 'pairs': [[0, 1]], 'winners': [2]}{'carry': None, 'comparisons': 1, 'fold_order': [2], 'losers': [8], 'pairs': [[0, 1]], 'winners': [2]}Passed
regression certificate 4{'carry': 1, 'comparisons': 2, 'fold_order': [1, 7], 'losers': [4], 'pairs': [[0, 1]], 'winners': [7]}{'carry': 1, 'comparisons': 2, 'fold_order': [1, 7], 'losers': [4], 'pairs': [[0, 1]], 'winners': [7]}Passed
regression certificate 5{'carry': None, 'comparisons': 3, 'fold_order': [9, 4], 'losers': [7, 1], 'pairs': [[0, 1], [2, 3]], 'winners': [4, 9]}{'carry': None, 'comparisons': 3, 'fold_order': [9, 4], 'losers': [7, 1], 'pairs': [[0, 1], [2, 3]], 'winners': [4, 9]}Passed
regression certificate 6{'carry': None, 'comparisons': 5, 'fold_order': [5, 6, 8], 'losers': [9, 7, 4], 'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5]}{'carry': None, 'comparisons': 5, 'fold_order': [5, 6, 8], 'losers': [9, 7, 4], 'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5]}Passed
variant-dependent certificate{'carry': 100, 'comparisons': 6, 'fold_order': [100, 5, 6, 8], 'losers': [9, 7, 4], 'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5]}{'carry': 100, 'comparisons': 6, 'fold_order': [100, 5, 6, 8], 'losers': [9, 7, 4], 'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5]}Passed

SHA-256 / 0ae528ca62ac7c5f2183f60441cf0d55270d8552aefc0c0f6a74a1f8ffd532bd

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

Case digest / 3c9c7284292488d99ccec19edf8507671159e1c8f374b5b8c1b55e0aa461a103