FAILURE MAP
← Case archive

FA-40586 / Heap invariants / Open access

Weak join makes one comparison independently of distance and swap outcome · case 01

The bounded weak join certificate reports an incorrect comparisons.

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

ROOT CAUSE

Weak join makes one comparison independently of distance and swap outcome.

VERIFIED REPAIR

Derive comparisons using 1 under the stated bounded certificate contract.

Unsuccessful approach: The local patch uses abs(j-i) and still violates the stated relation.

Case contract

A weak-heap join receives keys, reverse bits, ancestor i and distinct descendant j. When keys[j]<keys[i], swap these keys and flip only reverse[j]; on equality do nothing. Return resulting keys, reversal bits, swapped status, winning key, changed reversal index, and comparison count.

Why this case matters

This isolates an internal heap representation or priority-structure invariant using deterministic finite records.

1 / The failure

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

N = 1
observations = []
def solve(d):
    a=d['keys']; r=d['reverse']; i=d['i']; j=d['j']; swap=a[j]<a[i]; out=list(a); bits=list(r)
    if swap: out[i],out[j]=out[j],out[i]; bits[j]^=1
    return {'keys': out,
    'bits': bits,
    'swapped': swap,
    'winner_key': out[i],
    'flipped': j if swap else None,
    'comparisons': int(swap)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 4], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 4], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 3], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 3], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 2], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 2], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 1], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 1, 3, 4, 2], 'bits': [0, 1, 0, 1, 1], 'swapped': True, 'winner_key': 1, 'flipped': 4, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 0], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 0, 3, 4, 2], 'bits': [0, 1, 0, 1, 1], 'swapped': True, 'winner_key': 0, 'flipped': 4, 'comparisons': 1})]][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{'bits': [0, 1], 'comparisons': 1, 'flipped': 1, 'keys': [2, 4], 'swapped': True, 'winner_key': 2}{'bits': [0, 1], 'comparisons': 1, 'flipped': 1, 'keys': [2, 4], 'swapped': True, 'winner_key': 2}Passed
regression certificate 2{'bits': [0, 1], 'comparisons': 0, 'flipped': None, 'keys': [1, 7], 'swapped': False, 'winner_key': 1}{'bits': [0, 1], 'comparisons': 1, 'flipped': None, 'keys': [1, 7], 'swapped': False, 'winner_key': 1}Failed
regression certificate 3{'bits': [0, 0], 'comparisons': 0, 'flipped': None, 'keys': [3, 3], 'swapped': False, 'winner_key': 3}{'bits': [0, 0], 'comparisons': 1, 'flipped': None, 'keys': [3, 3], 'swapped': False, 'winner_key': 3}Failed
regression certificate 4{'bits': [0, 1, 0, 0], 'comparisons': 1, 'flipped': 3, 'keys': [0, 2, 5, 8], 'swapped': True, 'winner_key': 2}{'bits': [0, 1, 0, 0], 'comparisons': 1, 'flipped': 3, 'keys': [0, 2, 5, 8], 'swapped': True, 'winner_key': 2}Passed
regression certificate 5{'bits': [0, 1, 0, 0], 'comparisons': 1, 'flipped': 2, 'keys': [7, 1, 9, 3], 'swapped': True, 'winner_key': 7}{'bits': [0, 1, 0, 0], 'comparisons': 1, 'flipped': 2, 'keys': [7, 1, 9, 3], 'swapped': True, 'winner_key': 7}Passed
regression certificate 6{'bits': [0, 1, 0, 1, 0], 'comparisons': 0, 'flipped': None, 'keys': [1, 2, 3, 4, 5], 'swapped': False, 'winner_key': 2}{'bits': [0, 1, 0, 1, 0], 'comparisons': 1, 'flipped': None, 'keys': [1, 2, 3, 4, 5], 'swapped': False, 'winner_key': 2}Failed
variant-dependent certificate{'bits': [0, 1, 0, 1, 0], 'comparisons': 0, 'flipped': None, 'keys': [1, 2, 3, 4, 4], 'swapped': False, 'winner_key': 2}{'bits': [0, 1, 0, 1, 0], 'comparisons': 1, 'flipped': None, 'keys': [1, 2, 3, 4, 4], 'swapped': False, 'winner_key': 2}Failed

SHA-256 / e6409c87eef6ef70147868efde00f83cf6ee02547a08607cd936600687379eeb

2 / The unsuccessful fix

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

N = 1
observations = []
def solve(d):
    a=d['keys']; r=d['reverse']; i=d['i']; j=d['j']; swap=a[j]<a[i]; out=list(a); bits=list(r)
    if swap: out[i],out[j]=out[j],out[i]; bits[j]^=1
    return {'keys': out,
    'bits': bits,
    'swapped': swap,
    'winner_key': out[i],
    'flipped': j if swap else None,
    'comparisons': abs(j-i)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 4], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 4], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 3], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 3], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 2], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 2], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 1], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 1, 3, 4, 2], 'bits': [0, 1, 0, 1, 1], 'swapped': True, 'winner_key': 1, 'flipped': 4, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 0], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 0, 3, 4, 2], 'bits': [0, 1, 0, 1, 1], 'swapped': True, 'winner_key': 0, 'flipped': 4, 'comparisons': 1})]][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{'bits': [0, 1], 'comparisons': 1, 'flipped': 1, 'keys': [2, 4], 'swapped': True, 'winner_key': 2}{'bits': [0, 1], 'comparisons': 1, 'flipped': 1, 'keys': [2, 4], 'swapped': True, 'winner_key': 2}Passed
regression certificate 2{'bits': [0, 1], 'comparisons': 1, 'flipped': None, 'keys': [1, 7], 'swapped': False, 'winner_key': 1}{'bits': [0, 1], 'comparisons': 1, 'flipped': None, 'keys': [1, 7], 'swapped': False, 'winner_key': 1}Passed
regression certificate 3{'bits': [0, 0], 'comparisons': 1, 'flipped': None, 'keys': [3, 3], 'swapped': False, 'winner_key': 3}{'bits': [0, 0], 'comparisons': 1, 'flipped': None, 'keys': [3, 3], 'swapped': False, 'winner_key': 3}Passed
regression certificate 4{'bits': [0, 1, 0, 0], 'comparisons': 2, 'flipped': 3, 'keys': [0, 2, 5, 8], 'swapped': True, 'winner_key': 2}{'bits': [0, 1, 0, 0], 'comparisons': 1, 'flipped': 3, 'keys': [0, 2, 5, 8], 'swapped': True, 'winner_key': 2}Failed
regression certificate 5{'bits': [0, 1, 0, 0], 'comparisons': 2, 'flipped': 2, 'keys': [7, 1, 9, 3], 'swapped': True, 'winner_key': 7}{'bits': [0, 1, 0, 0], 'comparisons': 1, 'flipped': 2, 'keys': [7, 1, 9, 3], 'swapped': True, 'winner_key': 7}Failed
regression certificate 6{'bits': [0, 1, 0, 1, 0], 'comparisons': 3, 'flipped': None, 'keys': [1, 2, 3, 4, 5], 'swapped': False, 'winner_key': 2}{'bits': [0, 1, 0, 1, 0], 'comparisons': 1, 'flipped': None, 'keys': [1, 2, 3, 4, 5], 'swapped': False, 'winner_key': 2}Failed
variant-dependent certificate{'bits': [0, 1, 0, 1, 0], 'comparisons': 3, 'flipped': None, 'keys': [1, 2, 3, 4, 4], 'swapped': False, 'winner_key': 2}{'bits': [0, 1, 0, 1, 0], 'comparisons': 1, 'flipped': None, 'keys': [1, 2, 3, 4, 4], 'swapped': False, 'winner_key': 2}Failed

SHA-256 / 97f615e0a0e33a26a9c23aa14a4ebc91220ddfc840418dfd06be6156757ce47c

3 / The verified repair

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

N = 1
observations = []
def solve(d):
    a=d['keys']; r=d['reverse']; i=d['i']; j=d['j']; swap=a[j]<a[i]; out=list(a); bits=list(r)
    if swap: out[i],out[j]=out[j],out[i]; bits[j]^=1
    return {'keys': out,
    'bits': bits,
    'swapped': swap,
    'winner_key': out[i],
    'flipped': j if swap else None,
    'comparisons': 1}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 4], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 4], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 3], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 3], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 2], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 2], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 1], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 1, 3, 4, 2], 'bits': [0, 1, 0, 1, 1], 'swapped': True, 'winner_key': 1, 'flipped': 4, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 0], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 0, 3, 4, 2], 'bits': [0, 1, 0, 1, 1], 'swapped': True, 'winner_key': 0, 'flipped': 4, 'comparisons': 1})]][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{'bits': [0, 1], 'comparisons': 1, 'flipped': 1, 'keys': [2, 4], 'swapped': True, 'winner_key': 2}{'bits': [0, 1], 'comparisons': 1, 'flipped': 1, 'keys': [2, 4], 'swapped': True, 'winner_key': 2}Passed
regression certificate 2{'bits': [0, 1], 'comparisons': 1, 'flipped': None, 'keys': [1, 7], 'swapped': False, 'winner_key': 1}{'bits': [0, 1], 'comparisons': 1, 'flipped': None, 'keys': [1, 7], 'swapped': False, 'winner_key': 1}Passed
regression certificate 3{'bits': [0, 0], 'comparisons': 1, 'flipped': None, 'keys': [3, 3], 'swapped': False, 'winner_key': 3}{'bits': [0, 0], 'comparisons': 1, 'flipped': None, 'keys': [3, 3], 'swapped': False, 'winner_key': 3}Passed
regression certificate 4{'bits': [0, 1, 0, 0], 'comparisons': 1, 'flipped': 3, 'keys': [0, 2, 5, 8], 'swapped': True, 'winner_key': 2}{'bits': [0, 1, 0, 0], 'comparisons': 1, 'flipped': 3, 'keys': [0, 2, 5, 8], 'swapped': True, 'winner_key': 2}Passed
regression certificate 5{'bits': [0, 1, 0, 0], 'comparisons': 1, 'flipped': 2, 'keys': [7, 1, 9, 3], 'swapped': True, 'winner_key': 7}{'bits': [0, 1, 0, 0], 'comparisons': 1, 'flipped': 2, 'keys': [7, 1, 9, 3], 'swapped': True, 'winner_key': 7}Passed
regression certificate 6{'bits': [0, 1, 0, 1, 0], 'comparisons': 1, 'flipped': None, 'keys': [1, 2, 3, 4, 5], 'swapped': False, 'winner_key': 2}{'bits': [0, 1, 0, 1, 0], 'comparisons': 1, 'flipped': None, 'keys': [1, 2, 3, 4, 5], 'swapped': False, 'winner_key': 2}Passed
variant-dependent certificate{'bits': [0, 1, 0, 1, 0], 'comparisons': 1, 'flipped': None, 'keys': [1, 2, 3, 4, 4], 'swapped': False, 'winner_key': 2}{'bits': [0, 1, 0, 1, 0], 'comparisons': 1, 'flipped': None, 'keys': [1, 2, 3, 4, 4], 'swapped': False, 'winner_key': 2}Passed

SHA-256 / 04c9ad21050bb033f96234fdb75e67519d85ede7a298ff5d297cb8706a30716f

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

Case digest / c1672f54927f63dea94cd14d2de4eb5067c7c713a3f10eddc4b27d43356e4189