FAILURE MAP
← Case archive

FA-40236 / Heap invariants / Open access

Radix redistribution recomputes differing bits against the new threshold · case 01

The bounded radix redistribute certificate reports an incorrect destinations.

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

ROOT CAUSE

Radix redistribution recomputes differing bits against the new threshold.

VERIFIED REPAIR

Derive destinations using [[i,b] for i,b in dest] under the stated bounded certificate contract.

Unsuccessful approach: The local patch uses [[x[0],(x[1]-new).bit_length()] for x in a] and still violates the stated relation.

Case contract

Redistribute one nonempty radix bucket with entries [id,key], all keys at least old_last. Set new_last to bucket minimum and move every entry to bit_length(key XOR new_last); preserve entry order within each destination bucket. Report threshold, assignments, bucket-zero ids, moved count, old-bucket clearing, and maximum destination.

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['entries']; old=d['old_last']; new=min(x[1] for x in a); dest=[(x[0],(x[1]^new).bit_length()) for x in a]
    return {'threshold': new,
    'destinations': [[x[0],(x[1]^old).bit_length()] for x in a],
    'zero_ids': [x[0] for x in a if x[1]==new],
    'moved': len(a),
    'source_after': [],
    'largest_destination': max(b for i,b in dest)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [101, 9]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [101, 0]], 'zero_ids': [2, 101], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [102, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [102, 2]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [103, 11]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [103, 2]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [104, 12]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [104, 3]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [105, 13]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [105, 3]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})]][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{'destinations': [[1, 4]], 'largest_destination': 0, 'moved': 1, 'source_after': [], 'threshold': 8, 'zero_ids': [1]}{'destinations': [[1, 0]], 'largest_destination': 0, 'moved': 1, 'source_after': [], 'threshold': 8, 'zero_ids': [1]}Failed
regression certificate 2{'destinations': [[1, 3], [2, 3], [3, 3]], 'largest_destination': 2, 'moved': 3, 'source_after': [], 'threshold': 4, 'zero_ids': [2]}{'destinations': [[1, 2], [2, 0], [3, 2]], 'largest_destination': 2, 'moved': 3, 'source_after': [], 'threshold': 4, 'zero_ids': [2]}Failed
regression certificate 3{'destinations': [[1, 4], [2, 4], [3, 4], [4, 4]], 'largest_destination': 3, 'moved': 4, 'source_after': [], 'threshold': 8, 'zero_ids': [2, 3]}{'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'largest_destination': 3, 'moved': 4, 'source_after': [], 'threshold': 8, 'zero_ids': [2, 3]}Failed
regression certificate 4{'destinations': [[1, 2], [2, 2]], 'largest_destination': 1, 'moved': 2, 'source_after': [], 'threshold': 2, 'zero_ids': [2]}{'destinations': [[1, 1], [2, 0]], 'largest_destination': 1, 'moved': 2, 'source_after': [], 'threshold': 2, 'zero_ids': [2]}Failed
regression certificate 5{'destinations': [[1, 2], [2, 1], [3, 2]], 'largest_destination': 2, 'moved': 3, 'source_after': [], 'threshold': 5, 'zero_ids': [2]}{'destinations': [[1, 2], [2, 0], [3, 2]], 'largest_destination': 2, 'moved': 3, 'source_after': [], 'threshold': 5, 'zero_ids': [2]}Failed
regression certificate 6{'destinations': [[1, 3], [2, 1], [3, 2], [4, 2]], 'largest_destination': 3, 'moved': 4, 'source_after': [], 'threshold': 9, 'zero_ids': [2]}{'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'largest_destination': 3, 'moved': 4, 'source_after': [], 'threshold': 9, 'zero_ids': [2]}Failed
variant-dependent certificate{'destinations': [[1, 3], [2, 1], [3, 2], [4, 2], [101, 1]], 'largest_destination': 3, 'moved': 5, 'source_after': [], 'threshold': 9, 'zero_ids': [2, 101]}{'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [101, 0]], 'largest_destination': 3, 'moved': 5, 'source_after': [], 'threshold': 9, 'zero_ids': [2, 101]}Failed

SHA-256 / fd2abe94cedd1b7881ff47f014b45df71309d1b05f4e24e0c2a9d1ff7d4a7c10

2 / The unsuccessful fix

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

N = 1
observations = []
def solve(d):
    a=d['entries']; old=d['old_last']; new=min(x[1] for x in a); dest=[(x[0],(x[1]^new).bit_length()) for x in a]
    return {'threshold': new,
    'destinations': [[x[0],(x[1]-new).bit_length()] for x in a],
    'zero_ids': [x[0] for x in a if x[1]==new],
    'moved': len(a),
    'source_after': [],
    'largest_destination': max(b for i,b in dest)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [101, 9]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [101, 0]], 'zero_ids': [2, 101], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [102, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [102, 2]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [103, 11]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [103, 2]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [104, 12]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [104, 3]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [105, 13]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [105, 3]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})]][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{'destinations': [[1, 0]], 'largest_destination': 0, 'moved': 1, 'source_after': [], 'threshold': 8, 'zero_ids': [1]}{'destinations': [[1, 0]], 'largest_destination': 0, 'moved': 1, 'source_after': [], 'threshold': 8, 'zero_ids': [1]}Passed
regression certificate 2{'destinations': [[1, 2], [2, 0], [3, 2]], 'largest_destination': 2, 'moved': 3, 'source_after': [], 'threshold': 4, 'zero_ids': [2]}{'destinations': [[1, 2], [2, 0], [3, 2]], 'largest_destination': 2, 'moved': 3, 'source_after': [], 'threshold': 4, 'zero_ids': [2]}Passed
regression certificate 3{'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'largest_destination': 3, 'moved': 4, 'source_after': [], 'threshold': 8, 'zero_ids': [2, 3]}{'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'largest_destination': 3, 'moved': 4, 'source_after': [], 'threshold': 8, 'zero_ids': [2, 3]}Passed
regression certificate 4{'destinations': [[1, 1], [2, 0]], 'largest_destination': 1, 'moved': 2, 'source_after': [], 'threshold': 2, 'zero_ids': [2]}{'destinations': [[1, 1], [2, 0]], 'largest_destination': 1, 'moved': 2, 'source_after': [], 'threshold': 2, 'zero_ids': [2]}Passed
regression certificate 5{'destinations': [[1, 2], [2, 0], [3, 1]], 'largest_destination': 2, 'moved': 3, 'source_after': [], 'threshold': 5, 'zero_ids': [2]}{'destinations': [[1, 2], [2, 0], [3, 2]], 'largest_destination': 2, 'moved': 3, 'source_after': [], 'threshold': 5, 'zero_ids': [2]}Failed
regression certificate 6{'destinations': [[1, 3], [2, 0], [3, 2], [4, 1]], 'largest_destination': 3, 'moved': 4, 'source_after': [], 'threshold': 9, 'zero_ids': [2]}{'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'largest_destination': 3, 'moved': 4, 'source_after': [], 'threshold': 9, 'zero_ids': [2]}Failed
variant-dependent certificate{'destinations': [[1, 3], [2, 0], [3, 2], [4, 1], [101, 0]], 'largest_destination': 3, 'moved': 5, 'source_after': [], 'threshold': 9, 'zero_ids': [2, 101]}{'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [101, 0]], 'largest_destination': 3, 'moved': 5, 'source_after': [], 'threshold': 9, 'zero_ids': [2, 101]}Failed

SHA-256 / 762dde110d03dc5afa68f14c491e4c0b3e2e7a9082ef4c747759233b0da29371

3 / The verified repair

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

N = 1
observations = []
def solve(d):
    a=d['entries']; old=d['old_last']; new=min(x[1] for x in a); dest=[(x[0],(x[1]^new).bit_length()) for x in a]
    return {'threshold': new,
    'destinations': [[i,b] for i,b in dest],
    'zero_ids': [x[0] for x in a if x[1]==new],
    'moved': len(a),
    'source_after': [],
    'largest_destination': max(b for i,b in dest)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [101, 9]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [101, 0]], 'zero_ids': [2, 101], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [102, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [102, 2]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [103, 11]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [103, 2]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [104, 12]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [104, 3]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [105, 13]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [105, 3]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})]][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{'destinations': [[1, 0]], 'largest_destination': 0, 'moved': 1, 'source_after': [], 'threshold': 8, 'zero_ids': [1]}{'destinations': [[1, 0]], 'largest_destination': 0, 'moved': 1, 'source_after': [], 'threshold': 8, 'zero_ids': [1]}Passed
regression certificate 2{'destinations': [[1, 2], [2, 0], [3, 2]], 'largest_destination': 2, 'moved': 3, 'source_after': [], 'threshold': 4, 'zero_ids': [2]}{'destinations': [[1, 2], [2, 0], [3, 2]], 'largest_destination': 2, 'moved': 3, 'source_after': [], 'threshold': 4, 'zero_ids': [2]}Passed
regression certificate 3{'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'largest_destination': 3, 'moved': 4, 'source_after': [], 'threshold': 8, 'zero_ids': [2, 3]}{'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'largest_destination': 3, 'moved': 4, 'source_after': [], 'threshold': 8, 'zero_ids': [2, 3]}Passed
regression certificate 4{'destinations': [[1, 1], [2, 0]], 'largest_destination': 1, 'moved': 2, 'source_after': [], 'threshold': 2, 'zero_ids': [2]}{'destinations': [[1, 1], [2, 0]], 'largest_destination': 1, 'moved': 2, 'source_after': [], 'threshold': 2, 'zero_ids': [2]}Passed
regression certificate 5{'destinations': [[1, 2], [2, 0], [3, 2]], 'largest_destination': 2, 'moved': 3, 'source_after': [], 'threshold': 5, 'zero_ids': [2]}{'destinations': [[1, 2], [2, 0], [3, 2]], 'largest_destination': 2, 'moved': 3, 'source_after': [], 'threshold': 5, 'zero_ids': [2]}Passed
regression certificate 6{'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'largest_destination': 3, 'moved': 4, 'source_after': [], 'threshold': 9, 'zero_ids': [2]}{'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'largest_destination': 3, 'moved': 4, 'source_after': [], 'threshold': 9, 'zero_ids': [2]}Passed
variant-dependent certificate{'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [101, 0]], 'largest_destination': 3, 'moved': 5, 'source_after': [], 'threshold': 9, 'zero_ids': [2, 101]}{'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [101, 0]], 'largest_destination': 3, 'moved': 5, 'source_after': [], 'threshold': 9, 'zero_ids': [2, 101]}Passed

SHA-256 / 65a5017af8402dda3420ee2b98a292a9c8b66f1c0a5d8e7c05ba2ce8f704d2ba

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

Case digest / 8607c434f39d78cfbda37fe3b62700480489c62ced3e30284fb4d082a65d22bd