FAILURE MAP
← Case archive

FA-40671 / Heap invariants / Open access

Binomial payload bubbling keeps the structural parent chain intact · case 01

The bounded binomial payload bubble certificate reports an incorrect structural nodes.

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

ROOT CAUSE

Binomial payload bubbling keeps the structural parent chain intact.

VERIFIED REPAIR

Derive structural nodes using nodes under the stated bounded certificate contract.

Unsuccessful approach: The local patch uses [nodes[k] for k in range(len(nodes)) if k!=i] and still violates the stated relation.

Case contract

A binomial decrease-key bubble supplies the node-id path from leaf toward root, payloads [handle,key] at those nodes, and a decreased key for the first payload. While smaller than parent, exchange complete payloads. Structural nodes remain fixed; return final payload sequence, handle locations, swaps, decreased handle location, untouched structural path, and final minimum on this path.

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):
    nodes=d['nodes']; original=d['payloads']; p=[list(x) for x in original]; p[0][1]=d['new_key']; swaps=[]; i=0
    while i+1<len(p) and p[i][1]<p[i+1][1]:
        p[i],p[i+1]=p[i+1],p[i]; swaps.append([nodes[i],nodes[i+1]]); i+=1
    return {'payloads': p,
    'locations': {x[0]:nodes[k] for k,x in enumerate(p)},
    'swaps': swaps,
    'changed_location': nodes[i],
    'structural_nodes': list(reversed(nodes)),
    'minimum': min(x[1] for x in p)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 2}, {'payloads': [['b', 7], ['c', 5], ['a', 2], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1})], [({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 1}, {'payloads': [['b', 7], ['c', 5], ['a', 1], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1})], [({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 0}, {'payloads': [['b', 7], ['c', 5], ['d', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'd': 12, 'a': 13}, 'swaps': [[10, 11], [11, 12], [12, 13]], 'changed_location': 13, 'structural_nodes': [10, 11, 12, 13], 'minimum': 0})], [({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': -1}, {'payloads': [['b', 7], ['c', 5], ['d', 1], ['a', -1]], 'locations': {'b': 10, 'c': 11, 'd': 12, 'a': 13}, 'swaps': [[10, 11], [11, 12], [12, 13]], 'changed_location': 13, 'structural_nodes': [10, 11, 12, 13], 'minimum': -1})], [({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': -2}, {'payloads': [['b', 7], ['c', 5], ['d', 1], ['a', -2]], 'locations': {'b': 10, 'c': 11, 'd': 12, 'a': 13}, 'swaps': [[10, 11], [11, 12], [12, 13]], 'changed_location': 13, 'structural_nodes': [10, 11, 12, 13], 'minimum': -2})]][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{'changed_location': 10, 'locations': {'a': 10}, 'minimum': 4, 'payloads': [['a', 4]], 'structural_nodes': [10], 'swaps': []}{'changed_location': 10, 'locations': {'a': 10}, 'minimum': 4, 'payloads': [['a', 4]], 'structural_nodes': [10], 'swaps': []}Passed
regression certificate 2{'changed_location': 11, 'locations': {'a': 11, 'b': 10}, 'minimum': 1, 'payloads': [['b', 3], ['a', 1]], 'structural_nodes': [11, 10], 'swaps': [[10, 11]]}{'changed_location': 11, 'locations': {'a': 11, 'b': 10}, 'minimum': 1, 'payloads': [['b', 3], ['a', 1]], 'structural_nodes': [10, 11], 'swaps': [[10, 11]]}Failed
regression certificate 3{'changed_location': 11, 'locations': {'a': 11, 'b': 10, 'c': 12}, 'minimum': 2, 'payloads': [['b', 6], ['a', 4], ['c', 2]], 'structural_nodes': [12, 11, 10], 'swaps': [[10, 11]]}{'changed_location': 11, 'locations': {'a': 11, 'b': 10, 'c': 12}, 'minimum': 2, 'payloads': [['b', 6], ['a', 4], ['c', 2]], 'structural_nodes': [10, 11, 12], 'swaps': [[10, 11]]}Failed
regression certificate 4{'changed_location': 12, 'locations': {'a': 12, 'b': 10, 'c': 11}, 'minimum': 0, 'payloads': [['b', 5], ['c', 1], ['a', 0]], 'structural_nodes': [12, 11, 10], 'swaps': [[10, 11], [11, 12]]}{'changed_location': 12, 'locations': {'a': 12, 'b': 10, 'c': 11}, 'minimum': 0, 'payloads': [['b', 5], ['c', 1], ['a', 0]], 'structural_nodes': [10, 11, 12], 'swaps': [[10, 11], [11, 12]]}Failed
regression certificate 5{'changed_location': 10, 'locations': {'a': 10, 'b': 11, 'c': 12}, 'minimum': 2, 'payloads': [['a', 5], ['b', 5], ['c', 2]], 'structural_nodes': [12, 11, 10], 'swaps': []}{'changed_location': 10, 'locations': {'a': 10, 'b': 11, 'c': 12}, 'minimum': 2, 'payloads': [['a', 5], ['b', 5], ['c', 2]], 'structural_nodes': [10, 11, 12], 'swaps': []}Failed
regression certificate 6{'changed_location': 12, 'locations': {'a': 12, 'b': 10, 'c': 11, 'd': 13}, 'minimum': 1, 'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'structural_nodes': [13, 12, 11, 10], 'swaps': [[10, 11], [11, 12]]}{'changed_location': 12, 'locations': {'a': 12, 'b': 10, 'c': 11, 'd': 13}, 'minimum': 1, 'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'structural_nodes': [10, 11, 12, 13], 'swaps': [[10, 11], [11, 12]]}Failed
variant-dependent certificate{'changed_location': 12, 'locations': {'a': 12, 'b': 10, 'c': 11, 'd': 13}, 'minimum': 1, 'payloads': [['b', 7], ['c', 5], ['a', 2], ['d', 1]], 'structural_nodes': [13, 12, 11, 10], 'swaps': [[10, 11], [11, 12]]}{'changed_location': 12, 'locations': {'a': 12, 'b': 10, 'c': 11, 'd': 13}, 'minimum': 1, 'payloads': [['b', 7], ['c', 5], ['a', 2], ['d', 1]], 'structural_nodes': [10, 11, 12, 13], 'swaps': [[10, 11], [11, 12]]}Failed

SHA-256 / b497196107b1aba3687f18e03b17dc85d70c405c49fdd87d6d928edde73591e9

2 / The unsuccessful fix

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

N = 1
observations = []
def solve(d):
    nodes=d['nodes']; original=d['payloads']; p=[list(x) for x in original]; p[0][1]=d['new_key']; swaps=[]; i=0
    while i+1<len(p) and p[i][1]<p[i+1][1]:
        p[i],p[i+1]=p[i+1],p[i]; swaps.append([nodes[i],nodes[i+1]]); i+=1
    return {'payloads': p,
    'locations': {x[0]:nodes[k] for k,x in enumerate(p)},
    'swaps': swaps,
    'changed_location': nodes[i],
    'structural_nodes': [nodes[k] for k in range(len(nodes)) if k!=i],
    'minimum': min(x[1] for x in p)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 2}, {'payloads': [['b', 7], ['c', 5], ['a', 2], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1})], [({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 1}, {'payloads': [['b', 7], ['c', 5], ['a', 1], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1})], [({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 0}, {'payloads': [['b', 7], ['c', 5], ['d', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'd': 12, 'a': 13}, 'swaps': [[10, 11], [11, 12], [12, 13]], 'changed_location': 13, 'structural_nodes': [10, 11, 12, 13], 'minimum': 0})], [({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': -1}, {'payloads': [['b', 7], ['c', 5], ['d', 1], ['a', -1]], 'locations': {'b': 10, 'c': 11, 'd': 12, 'a': 13}, 'swaps': [[10, 11], [11, 12], [12, 13]], 'changed_location': 13, 'structural_nodes': [10, 11, 12, 13], 'minimum': -1})], [({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': -2}, {'payloads': [['b', 7], ['c', 5], ['d', 1], ['a', -2]], 'locations': {'b': 10, 'c': 11, 'd': 12, 'a': 13}, 'swaps': [[10, 11], [11, 12], [12, 13]], 'changed_location': 13, 'structural_nodes': [10, 11, 12, 13], 'minimum': -2})]][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{'changed_location': 10, 'locations': {'a': 10}, 'minimum': 4, 'payloads': [['a', 4]], 'structural_nodes': [], 'swaps': []}{'changed_location': 10, 'locations': {'a': 10}, 'minimum': 4, 'payloads': [['a', 4]], 'structural_nodes': [10], 'swaps': []}Failed
regression certificate 2{'changed_location': 11, 'locations': {'a': 11, 'b': 10}, 'minimum': 1, 'payloads': [['b', 3], ['a', 1]], 'structural_nodes': [10], 'swaps': [[10, 11]]}{'changed_location': 11, 'locations': {'a': 11, 'b': 10}, 'minimum': 1, 'payloads': [['b', 3], ['a', 1]], 'structural_nodes': [10, 11], 'swaps': [[10, 11]]}Failed
regression certificate 3{'changed_location': 11, 'locations': {'a': 11, 'b': 10, 'c': 12}, 'minimum': 2, 'payloads': [['b', 6], ['a', 4], ['c', 2]], 'structural_nodes': [10, 12], 'swaps': [[10, 11]]}{'changed_location': 11, 'locations': {'a': 11, 'b': 10, 'c': 12}, 'minimum': 2, 'payloads': [['b', 6], ['a', 4], ['c', 2]], 'structural_nodes': [10, 11, 12], 'swaps': [[10, 11]]}Failed
regression certificate 4{'changed_location': 12, 'locations': {'a': 12, 'b': 10, 'c': 11}, 'minimum': 0, 'payloads': [['b', 5], ['c', 1], ['a', 0]], 'structural_nodes': [10, 11], 'swaps': [[10, 11], [11, 12]]}{'changed_location': 12, 'locations': {'a': 12, 'b': 10, 'c': 11}, 'minimum': 0, 'payloads': [['b', 5], ['c', 1], ['a', 0]], 'structural_nodes': [10, 11, 12], 'swaps': [[10, 11], [11, 12]]}Failed
regression certificate 5{'changed_location': 10, 'locations': {'a': 10, 'b': 11, 'c': 12}, 'minimum': 2, 'payloads': [['a', 5], ['b', 5], ['c', 2]], 'structural_nodes': [11, 12], 'swaps': []}{'changed_location': 10, 'locations': {'a': 10, 'b': 11, 'c': 12}, 'minimum': 2, 'payloads': [['a', 5], ['b', 5], ['c', 2]], 'structural_nodes': [10, 11, 12], 'swaps': []}Failed
regression certificate 6{'changed_location': 12, 'locations': {'a': 12, 'b': 10, 'c': 11, 'd': 13}, 'minimum': 1, 'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'structural_nodes': [10, 11, 13], 'swaps': [[10, 11], [11, 12]]}{'changed_location': 12, 'locations': {'a': 12, 'b': 10, 'c': 11, 'd': 13}, 'minimum': 1, 'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'structural_nodes': [10, 11, 12, 13], 'swaps': [[10, 11], [11, 12]]}Failed
variant-dependent certificate{'changed_location': 12, 'locations': {'a': 12, 'b': 10, 'c': 11, 'd': 13}, 'minimum': 1, 'payloads': [['b', 7], ['c', 5], ['a', 2], ['d', 1]], 'structural_nodes': [10, 11, 13], 'swaps': [[10, 11], [11, 12]]}{'changed_location': 12, 'locations': {'a': 12, 'b': 10, 'c': 11, 'd': 13}, 'minimum': 1, 'payloads': [['b', 7], ['c', 5], ['a', 2], ['d', 1]], 'structural_nodes': [10, 11, 12, 13], 'swaps': [[10, 11], [11, 12]]}Failed

SHA-256 / 9d365b5c387fb98abc6ff9789d6012a13e6638aa4a57315d2a6bc8fd8349058b

3 / The verified repair

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

N = 1
observations = []
def solve(d):
    nodes=d['nodes']; original=d['payloads']; p=[list(x) for x in original]; p[0][1]=d['new_key']; swaps=[]; i=0
    while i+1<len(p) and p[i][1]<p[i+1][1]:
        p[i],p[i+1]=p[i+1],p[i]; swaps.append([nodes[i],nodes[i+1]]); i+=1
    return {'payloads': p,
    'locations': {x[0]:nodes[k] for k,x in enumerate(p)},
    'swaps': swaps,
    'changed_location': nodes[i],
    'structural_nodes': nodes,
    'minimum': min(x[1] for x in p)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 2}, {'payloads': [['b', 7], ['c', 5], ['a', 2], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1})], [({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 1}, {'payloads': [['b', 7], ['c', 5], ['a', 1], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1})], [({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 0}, {'payloads': [['b', 7], ['c', 5], ['d', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'd': 12, 'a': 13}, 'swaps': [[10, 11], [11, 12], [12, 13]], 'changed_location': 13, 'structural_nodes': [10, 11, 12, 13], 'minimum': 0})], [({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': -1}, {'payloads': [['b', 7], ['c', 5], ['d', 1], ['a', -1]], 'locations': {'b': 10, 'c': 11, 'd': 12, 'a': 13}, 'swaps': [[10, 11], [11, 12], [12, 13]], 'changed_location': 13, 'structural_nodes': [10, 11, 12, 13], 'minimum': -1})], [({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': -2}, {'payloads': [['b', 7], ['c', 5], ['d', 1], ['a', -2]], 'locations': {'b': 10, 'c': 11, 'd': 12, 'a': 13}, 'swaps': [[10, 11], [11, 12], [12, 13]], 'changed_location': 13, 'structural_nodes': [10, 11, 12, 13], 'minimum': -2})]][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{'changed_location': 10, 'locations': {'a': 10}, 'minimum': 4, 'payloads': [['a', 4]], 'structural_nodes': [10], 'swaps': []}{'changed_location': 10, 'locations': {'a': 10}, 'minimum': 4, 'payloads': [['a', 4]], 'structural_nodes': [10], 'swaps': []}Passed
regression certificate 2{'changed_location': 11, 'locations': {'a': 11, 'b': 10}, 'minimum': 1, 'payloads': [['b', 3], ['a', 1]], 'structural_nodes': [10, 11], 'swaps': [[10, 11]]}{'changed_location': 11, 'locations': {'a': 11, 'b': 10}, 'minimum': 1, 'payloads': [['b', 3], ['a', 1]], 'structural_nodes': [10, 11], 'swaps': [[10, 11]]}Passed
regression certificate 3{'changed_location': 11, 'locations': {'a': 11, 'b': 10, 'c': 12}, 'minimum': 2, 'payloads': [['b', 6], ['a', 4], ['c', 2]], 'structural_nodes': [10, 11, 12], 'swaps': [[10, 11]]}{'changed_location': 11, 'locations': {'a': 11, 'b': 10, 'c': 12}, 'minimum': 2, 'payloads': [['b', 6], ['a', 4], ['c', 2]], 'structural_nodes': [10, 11, 12], 'swaps': [[10, 11]]}Passed
regression certificate 4{'changed_location': 12, 'locations': {'a': 12, 'b': 10, 'c': 11}, 'minimum': 0, 'payloads': [['b', 5], ['c', 1], ['a', 0]], 'structural_nodes': [10, 11, 12], 'swaps': [[10, 11], [11, 12]]}{'changed_location': 12, 'locations': {'a': 12, 'b': 10, 'c': 11}, 'minimum': 0, 'payloads': [['b', 5], ['c', 1], ['a', 0]], 'structural_nodes': [10, 11, 12], 'swaps': [[10, 11], [11, 12]]}Passed
regression certificate 5{'changed_location': 10, 'locations': {'a': 10, 'b': 11, 'c': 12}, 'minimum': 2, 'payloads': [['a', 5], ['b', 5], ['c', 2]], 'structural_nodes': [10, 11, 12], 'swaps': []}{'changed_location': 10, 'locations': {'a': 10, 'b': 11, 'c': 12}, 'minimum': 2, 'payloads': [['a', 5], ['b', 5], ['c', 2]], 'structural_nodes': [10, 11, 12], 'swaps': []}Passed
regression certificate 6{'changed_location': 12, 'locations': {'a': 12, 'b': 10, 'c': 11, 'd': 13}, 'minimum': 1, 'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'structural_nodes': [10, 11, 12, 13], 'swaps': [[10, 11], [11, 12]]}{'changed_location': 12, 'locations': {'a': 12, 'b': 10, 'c': 11, 'd': 13}, 'minimum': 1, 'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'structural_nodes': [10, 11, 12, 13], 'swaps': [[10, 11], [11, 12]]}Passed
variant-dependent certificate{'changed_location': 12, 'locations': {'a': 12, 'b': 10, 'c': 11, 'd': 13}, 'minimum': 1, 'payloads': [['b', 7], ['c', 5], ['a', 2], ['d', 1]], 'structural_nodes': [10, 11, 12, 13], 'swaps': [[10, 11], [11, 12]]}{'changed_location': 12, 'locations': {'a': 12, 'b': 10, 'c': 11, 'd': 13}, 'minimum': 1, 'payloads': [['b', 7], ['c', 5], ['a', 2], ['d', 1]], 'structural_nodes': [10, 11, 12, 13], 'swaps': [[10, 11], [11, 12]]}Passed

SHA-256 / 31002f4e7810a53139e9451e4f751f2cc7f7831013d36917d2ee3496c9fa6085

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

Case digest / 8bb6ac2519f93b83f34422f298157605fe281b9d24739ea7d868563a80707777