FAILURE MAP
← Case archive

FA-40016 / Heap invariants / Open access

Binomial link removes the loser from the root collection · case 01

The bounded binomial link certificate reports an incorrect root set.

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

ROOT CAUSE

Binomial link removes the loser from the root collection.

VERIFIED REPAIR

Derive root set using [w[0]] under the stated bounded certificate contract.

Unsuccessful approach: The local patch uses [l[0]] and still violates the stated relation.

Case contract

Link two equal-rank binomial roots a and b, each [id,key,rank,child_ids]. Ties keep a. Return winner, loser, winner rank, child-chain prepend, comparison cost, and removed-root identities. Certificate input is two distinct roots of equal rank.

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['a']; b=d['b']; w,l=(a,b) if a[1]<=b[1] else (b,a)
    return {'winner': w[0],
    'loser': l[0],
    'new_rank': w[2]+1,
    'children': [l[0]]+w[3],
    'parent_updates': [[l[0],w[0]]],
    'root_set': [a[0],b[0]]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'a': [8, 2, 0, []], 'b': [3, 5, 0, []]}, {'winner': 8, 'loser': 3, 'new_rank': 1, 'children': [3], 'parent_updates': [[3, 8]], 'root_set': [8]}), ({'a': [2, 9, 0, []], 'b': [7, 1, 0, []]}, {'winner': 7, 'loser': 2, 'new_rank': 1, 'children': [2], 'parent_updates': [[2, 7]], 'root_set': [7]}), ({'a': [5, 4, 1, [1]], 'b': [9, 4, 1, [3]]}, {'winner': 5, 'loser': 9, 'new_rank': 2, 'children': [9, 1], 'parent_updates': [[9, 5]], 'root_set': [5]}), ({'a': [4, 8, 2, [10, 11]], 'b': [6, 3, 2, [12, 13]]}, {'winner': 6, 'loser': 4, 'new_rank': 3, 'children': [4, 12, 13], 'parent_updates': [[4, 6]], 'root_set': [6]}), ({'a': [1, 0, 3, [2, 3, 4]], 'b': [9, 8, 3, [10, 11, 12]]}, {'winner': 1, 'loser': 9, 'new_rank': 4, 'children': [9, 2, 3, 4], 'parent_updates': [[9, 1]], 'root_set': [1]}), ({'a': [7, 5, 1, [8]], 'b': [2, 2, 1, [3]]}, {'winner': 2, 'loser': 7, 'new_rank': 2, 'children': [7, 3], 'parent_updates': [[7, 2]], 'root_set': [2]}), ({'a': [7, 6, 1, [8]], 'b': [2, 2, 1, [3]]}, {'winner': 2, 'loser': 7, 'new_rank': 2, 'children': [7, 3], 'parent_updates': [[7, 2]], 'root_set': [2]})], [({'a': [8, 2, 0, []], 'b': [3, 5, 0, []]}, {'winner': 8, 'loser': 3, 'new_rank': 1, 'children': [3], 'parent_updates': [[3, 8]], 'root_set': [8]}), ({'a': [2, 9, 0, []], 'b': [7, 1, 0, []]}, {'winner': 7, 'loser': 2, 'new_rank': 1, 'children': [2], 'parent_updates': [[2, 7]], 'root_set': [7]}), ({'a': [5, 4, 1, [1]], 'b': [9, 4, 1, [3]]}, {'winner': 5, 'loser': 9, 'new_rank': 2, 'children': [9, 1], 'parent_updates': [[9, 5]], 'root_set': [5]}), ({'a': [4, 8, 2, [10, 11]], 'b': [6, 3, 2, [12, 13]]}, {'winner': 6, 'loser': 4, 'new_rank': 3, 'children': [4, 12, 13], 'parent_updates': [[4, 6]], 'root_set': [6]}), ({'a': [1, 0, 3, [2, 3, 4]], 'b': [9, 8, 3, [10, 11, 12]]}, {'winner': 1, 'loser': 9, 'new_rank': 4, 'children': [9, 2, 3, 4], 'parent_updates': [[9, 1]], 'root_set': [1]}), ({'a': [7, 5, 1, [8]], 'b': [2, 2, 1, [3]]}, {'winner': 2, 'loser': 7, 'new_rank': 2, 'children': [7, 3], 'parent_updates': [[7, 2]], 'root_set': [2]}), ({'a': [7, 7, 1, [8]], 'b': [2, 2, 1, [3]]}, {'winner': 2, 'loser': 7, 'new_rank': 2, 'children': [7, 3], 'parent_updates': [[7, 2]], 'root_set': [2]})], [({'a': [8, 2, 0, []], 'b': [3, 5, 0, []]}, {'winner': 8, 'loser': 3, 'new_rank': 1, 'children': [3], 'parent_updates': [[3, 8]], 'root_set': [8]}), ({'a': [2, 9, 0, []], 'b': [7, 1, 0, []]}, {'winner': 7, 'loser': 2, 'new_rank': 1, 'children': [2], 'parent_updates': [[2, 7]], 'root_set': [7]}), ({'a': [5, 4, 1, [1]], 'b': [9, 4, 1, [3]]}, {'winner': 5, 'loser': 9, 'new_rank': 2, 'children': [9, 1], 'parent_updates': [[9, 5]], 'root_set': [5]}), ({'a': [4, 8, 2, [10, 11]], 'b': [6, 3, 2, [12, 13]]}, {'winner': 6, 'loser': 4, 'new_rank': 3, 'children': [4, 12, 13], 'parent_updates': [[4, 6]], 'root_set': [6]}), ({'a': [1, 0, 3, [2, 3, 4]], 'b': [9, 8, 3, [10, 11, 12]]}, {'winner': 1, 'loser': 9, 'new_rank': 4, 'children': [9, 2, 3, 4], 'parent_updates': [[9, 1]], 'root_set': [1]}), ({'a': [7, 5, 1, [8]], 'b': [2, 2, 1, [3]]}, {'winner': 2, 'loser': 7, 'new_rank': 2, 'children': [7, 3], 'parent_updates': [[7, 2]], 'root_set': [2]}), ({'a': [7, 8, 1, [8]], 'b': [2, 2, 1, [3]]}, {'winner': 2, 'loser': 7, 'new_rank': 2, 'children': [7, 3], 'parent_updates': [[7, 2]], 'root_set': [2]})], [({'a': [8, 2, 0, []], 'b': [3, 5, 0, []]}, {'winner': 8, 'loser': 3, 'new_rank': 1, 'children': [3], 'parent_updates': [[3, 8]], 'root_set': [8]}), ({'a': [2, 9, 0, []], 'b': [7, 1, 0, []]}, {'winner': 7, 'loser': 2, 'new_rank': 1, 'children': [2], 'parent_updates': [[2, 7]], 'root_set': [7]}), ({'a': [5, 4, 1, [1]], 'b': [9, 4, 1, [3]]}, {'winner': 5, 'loser': 9, 'new_rank': 2, 'children': [9, 1], 'parent_updates': [[9, 5]], 'root_set': [5]}), ({'a': [4, 8, 2, [10, 11]], 'b': [6, 3, 2, [12, 13]]}, {'winner': 6, 'loser': 4, 'new_rank': 3, 'children': [4, 12, 13], 'parent_updates': [[4, 6]], 'root_set': [6]}), ({'a': [1, 0, 3, [2, 3, 4]], 'b': [9, 8, 3, [10, 11, 12]]}, {'winner': 1, 'loser': 9, 'new_rank': 4, 'children': [9, 2, 3, 4], 'parent_updates': [[9, 1]], 'root_set': [1]}), ({'a': [7, 5, 1, [8]], 'b': [2, 2, 1, [3]]}, {'winner': 2, 'loser': 7, 'new_rank': 2, 'children': [7, 3], 'parent_updates': [[7, 2]], 'root_set': [2]}), ({'a': [7, 9, 1, [8]], 'b': [2, 2, 1, [3]]}, {'winner': 2, 'loser': 7, 'new_rank': 2, 'children': [7, 3], 'parent_updates': [[7, 2]], 'root_set': [2]})], [({'a': [8, 2, 0, []], 'b': [3, 5, 0, []]}, {'winner': 8, 'loser': 3, 'new_rank': 1, 'children': [3], 'parent_updates': [[3, 8]], 'root_set': [8]}), ({'a': [2, 9, 0, []], 'b': [7, 1, 0, []]}, {'winner': 7, 'loser': 2, 'new_rank': 1, 'children': [2], 'parent_updates': [[2, 7]], 'root_set': [7]}), ({'a': [5, 4, 1, [1]], 'b': [9, 4, 1, [3]]}, {'winner': 5, 'loser': 9, 'new_rank': 2, 'children': [9, 1], 'parent_updates': [[9, 5]], 'root_set': [5]}), ({'a': [4, 8, 2, [10, 11]], 'b': [6, 3, 2, [12, 13]]}, {'winner': 6, 'loser': 4, 'new_rank': 3, 'children': [4, 12, 13], 'parent_updates': [[4, 6]], 'root_set': [6]}), ({'a': [1, 0, 3, [2, 3, 4]], 'b': [9, 8, 3, [10, 11, 12]]}, {'winner': 1, 'loser': 9, 'new_rank': 4, 'children': [9, 2, 3, 4], 'parent_updates': [[9, 1]], 'root_set': [1]}), ({'a': [7, 5, 1, [8]], 'b': [2, 2, 1, [3]]}, {'winner': 2, 'loser': 7, 'new_rank': 2, 'children': [7, 3], 'parent_updates': [[7, 2]], 'root_set': [2]}), ({'a': [7, 10, 1, [8]], 'b': [2, 2, 1, [3]]}, {'winner': 2, 'loser': 7, 'new_rank': 2, 'children': [7, 3], 'parent_updates': [[7, 2]], 'root_set': [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{'children': [3], 'loser': 3, 'new_rank': 1, 'parent_updates': [[3, 8]], 'root_set': [8, 3], 'winner': 8}{'children': [3], 'loser': 3, 'new_rank': 1, 'parent_updates': [[3, 8]], 'root_set': [8], 'winner': 8}Failed
regression certificate 2{'children': [2], 'loser': 2, 'new_rank': 1, 'parent_updates': [[2, 7]], 'root_set': [2, 7], 'winner': 7}{'children': [2], 'loser': 2, 'new_rank': 1, 'parent_updates': [[2, 7]], 'root_set': [7], 'winner': 7}Failed
regression certificate 3{'children': [9, 1], 'loser': 9, 'new_rank': 2, 'parent_updates': [[9, 5]], 'root_set': [5, 9], 'winner': 5}{'children': [9, 1], 'loser': 9, 'new_rank': 2, 'parent_updates': [[9, 5]], 'root_set': [5], 'winner': 5}Failed
regression certificate 4{'children': [4, 12, 13], 'loser': 4, 'new_rank': 3, 'parent_updates': [[4, 6]], 'root_set': [4, 6], 'winner': 6}{'children': [4, 12, 13], 'loser': 4, 'new_rank': 3, 'parent_updates': [[4, 6]], 'root_set': [6], 'winner': 6}Failed
regression certificate 5{'children': [9, 2, 3, 4], 'loser': 9, 'new_rank': 4, 'parent_updates': [[9, 1]], 'root_set': [1, 9], 'winner': 1}{'children': [9, 2, 3, 4], 'loser': 9, 'new_rank': 4, 'parent_updates': [[9, 1]], 'root_set': [1], 'winner': 1}Failed
regression certificate 6{'children': [7, 3], 'loser': 7, 'new_rank': 2, 'parent_updates': [[7, 2]], 'root_set': [7, 2], 'winner': 2}{'children': [7, 3], 'loser': 7, 'new_rank': 2, 'parent_updates': [[7, 2]], 'root_set': [2], 'winner': 2}Failed
variant-dependent certificate{'children': [7, 3], 'loser': 7, 'new_rank': 2, 'parent_updates': [[7, 2]], 'root_set': [7, 2], 'winner': 2}{'children': [7, 3], 'loser': 7, 'new_rank': 2, 'parent_updates': [[7, 2]], 'root_set': [2], 'winner': 2}Failed

SHA-256 / 950636cfd7c32623abd09e39b7c93269db908f645d3807a76b5538d49469c12f

2 / The unsuccessful fix

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

N = 1
observations = []
def solve(d):
    a=d['a']; b=d['b']; w,l=(a,b) if a[1]<=b[1] else (b,a)
    return {'winner': w[0],
    'loser': l[0],
    'new_rank': w[2]+1,
    'children': [l[0]]+w[3],
    'parent_updates': [[l[0],w[0]]],
    'root_set': [l[0]]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'a': [8, 2, 0, []], 'b': [3, 5, 0, []]}, {'winner': 8, 'loser': 3, 'new_rank': 1, 'children': [3], 'parent_updates': [[3, 8]], 'root_set': [8]}), ({'a': [2, 9, 0, []], 'b': [7, 1, 0, []]}, {'winner': 7, 'loser': 2, 'new_rank': 1, 'children': [2], 'parent_updates': [[2, 7]], 'root_set': [7]}), ({'a': [5, 4, 1, [1]], 'b': [9, 4, 1, [3]]}, {'winner': 5, 'loser': 9, 'new_rank': 2, 'children': [9, 1], 'parent_updates': [[9, 5]], 'root_set': [5]}), ({'a': [4, 8, 2, [10, 11]], 'b': [6, 3, 2, [12, 13]]}, {'winner': 6, 'loser': 4, 'new_rank': 3, 'children': [4, 12, 13], 'parent_updates': [[4, 6]], 'root_set': [6]}), ({'a': [1, 0, 3, [2, 3, 4]], 'b': [9, 8, 3, [10, 11, 12]]}, {'winner': 1, 'loser': 9, 'new_rank': 4, 'children': [9, 2, 3, 4], 'parent_updates': [[9, 1]], 'root_set': [1]}), ({'a': [7, 5, 1, [8]], 'b': [2, 2, 1, [3]]}, {'winner': 2, 'loser': 7, 'new_rank': 2, 'children': [7, 3], 'parent_updates': [[7, 2]], 'root_set': [2]}), ({'a': [7, 6, 1, [8]], 'b': [2, 2, 1, [3]]}, {'winner': 2, 'loser': 7, 'new_rank': 2, 'children': [7, 3], 'parent_updates': [[7, 2]], 'root_set': [2]})], [({'a': [8, 2, 0, []], 'b': [3, 5, 0, []]}, {'winner': 8, 'loser': 3, 'new_rank': 1, 'children': [3], 'parent_updates': [[3, 8]], 'root_set': [8]}), ({'a': [2, 9, 0, []], 'b': [7, 1, 0, []]}, {'winner': 7, 'loser': 2, 'new_rank': 1, 'children': [2], 'parent_updates': [[2, 7]], 'root_set': [7]}), ({'a': [5, 4, 1, [1]], 'b': [9, 4, 1, [3]]}, {'winner': 5, 'loser': 9, 'new_rank': 2, 'children': [9, 1], 'parent_updates': [[9, 5]], 'root_set': [5]}), ({'a': [4, 8, 2, [10, 11]], 'b': [6, 3, 2, [12, 13]]}, {'winner': 6, 'loser': 4, 'new_rank': 3, 'children': [4, 12, 13], 'parent_updates': [[4, 6]], 'root_set': [6]}), ({'a': [1, 0, 3, [2, 3, 4]], 'b': [9, 8, 3, [10, 11, 12]]}, {'winner': 1, 'loser': 9, 'new_rank': 4, 'children': [9, 2, 3, 4], 'parent_updates': [[9, 1]], 'root_set': [1]}), ({'a': [7, 5, 1, [8]], 'b': [2, 2, 1, [3]]}, {'winner': 2, 'loser': 7, 'new_rank': 2, 'children': [7, 3], 'parent_updates': [[7, 2]], 'root_set': [2]}), ({'a': [7, 7, 1, [8]], 'b': [2, 2, 1, [3]]}, {'winner': 2, 'loser': 7, 'new_rank': 2, 'children': [7, 3], 'parent_updates': [[7, 2]], 'root_set': [2]})], [({'a': [8, 2, 0, []], 'b': [3, 5, 0, []]}, {'winner': 8, 'loser': 3, 'new_rank': 1, 'children': [3], 'parent_updates': [[3, 8]], 'root_set': [8]}), ({'a': [2, 9, 0, []], 'b': [7, 1, 0, []]}, {'winner': 7, 'loser': 2, 'new_rank': 1, 'children': [2], 'parent_updates': [[2, 7]], 'root_set': [7]}), ({'a': [5, 4, 1, [1]], 'b': [9, 4, 1, [3]]}, {'winner': 5, 'loser': 9, 'new_rank': 2, 'children': [9, 1], 'parent_updates': [[9, 5]], 'root_set': [5]}), ({'a': [4, 8, 2, [10, 11]], 'b': [6, 3, 2, [12, 13]]}, {'winner': 6, 'loser': 4, 'new_rank': 3, 'children': [4, 12, 13], 'parent_updates': [[4, 6]], 'root_set': [6]}), ({'a': [1, 0, 3, [2, 3, 4]], 'b': [9, 8, 3, [10, 11, 12]]}, {'winner': 1, 'loser': 9, 'new_rank': 4, 'children': [9, 2, 3, 4], 'parent_updates': [[9, 1]], 'root_set': [1]}), ({'a': [7, 5, 1, [8]], 'b': [2, 2, 1, [3]]}, {'winner': 2, 'loser': 7, 'new_rank': 2, 'children': [7, 3], 'parent_updates': [[7, 2]], 'root_set': [2]}), ({'a': [7, 8, 1, [8]], 'b': [2, 2, 1, [3]]}, {'winner': 2, 'loser': 7, 'new_rank': 2, 'children': [7, 3], 'parent_updates': [[7, 2]], 'root_set': [2]})], [({'a': [8, 2, 0, []], 'b': [3, 5, 0, []]}, {'winner': 8, 'loser': 3, 'new_rank': 1, 'children': [3], 'parent_updates': [[3, 8]], 'root_set': [8]}), ({'a': [2, 9, 0, []], 'b': [7, 1, 0, []]}, {'winner': 7, 'loser': 2, 'new_rank': 1, 'children': [2], 'parent_updates': [[2, 7]], 'root_set': [7]}), ({'a': [5, 4, 1, [1]], 'b': [9, 4, 1, [3]]}, {'winner': 5, 'loser': 9, 'new_rank': 2, 'children': [9, 1], 'parent_updates': [[9, 5]], 'root_set': [5]}), ({'a': [4, 8, 2, [10, 11]], 'b': [6, 3, 2, [12, 13]]}, {'winner': 6, 'loser': 4, 'new_rank': 3, 'children': [4, 12, 13], 'parent_updates': [[4, 6]], 'root_set': [6]}), ({'a': [1, 0, 3, [2, 3, 4]], 'b': [9, 8, 3, [10, 11, 12]]}, {'winner': 1, 'loser': 9, 'new_rank': 4, 'children': [9, 2, 3, 4], 'parent_updates': [[9, 1]], 'root_set': [1]}), ({'a': [7, 5, 1, [8]], 'b': [2, 2, 1, [3]]}, {'winner': 2, 'loser': 7, 'new_rank': 2, 'children': [7, 3], 'parent_updates': [[7, 2]], 'root_set': [2]}), ({'a': [7, 9, 1, [8]], 'b': [2, 2, 1, [3]]}, {'winner': 2, 'loser': 7, 'new_rank': 2, 'children': [7, 3], 'parent_updates': [[7, 2]], 'root_set': [2]})], [({'a': [8, 2, 0, []], 'b': [3, 5, 0, []]}, {'winner': 8, 'loser': 3, 'new_rank': 1, 'children': [3], 'parent_updates': [[3, 8]], 'root_set': [8]}), ({'a': [2, 9, 0, []], 'b': [7, 1, 0, []]}, {'winner': 7, 'loser': 2, 'new_rank': 1, 'children': [2], 'parent_updates': [[2, 7]], 'root_set': [7]}), ({'a': [5, 4, 1, [1]], 'b': [9, 4, 1, [3]]}, {'winner': 5, 'loser': 9, 'new_rank': 2, 'children': [9, 1], 'parent_updates': [[9, 5]], 'root_set': [5]}), ({'a': [4, 8, 2, [10, 11]], 'b': [6, 3, 2, [12, 13]]}, {'winner': 6, 'loser': 4, 'new_rank': 3, 'children': [4, 12, 13], 'parent_updates': [[4, 6]], 'root_set': [6]}), ({'a': [1, 0, 3, [2, 3, 4]], 'b': [9, 8, 3, [10, 11, 12]]}, {'winner': 1, 'loser': 9, 'new_rank': 4, 'children': [9, 2, 3, 4], 'parent_updates': [[9, 1]], 'root_set': [1]}), ({'a': [7, 5, 1, [8]], 'b': [2, 2, 1, [3]]}, {'winner': 2, 'loser': 7, 'new_rank': 2, 'children': [7, 3], 'parent_updates': [[7, 2]], 'root_set': [2]}), ({'a': [7, 10, 1, [8]], 'b': [2, 2, 1, [3]]}, {'winner': 2, 'loser': 7, 'new_rank': 2, 'children': [7, 3], 'parent_updates': [[7, 2]], 'root_set': [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{'children': [3], 'loser': 3, 'new_rank': 1, 'parent_updates': [[3, 8]], 'root_set': [3], 'winner': 8}{'children': [3], 'loser': 3, 'new_rank': 1, 'parent_updates': [[3, 8]], 'root_set': [8], 'winner': 8}Failed
regression certificate 2{'children': [2], 'loser': 2, 'new_rank': 1, 'parent_updates': [[2, 7]], 'root_set': [2], 'winner': 7}{'children': [2], 'loser': 2, 'new_rank': 1, 'parent_updates': [[2, 7]], 'root_set': [7], 'winner': 7}Failed
regression certificate 3{'children': [9, 1], 'loser': 9, 'new_rank': 2, 'parent_updates': [[9, 5]], 'root_set': [9], 'winner': 5}{'children': [9, 1], 'loser': 9, 'new_rank': 2, 'parent_updates': [[9, 5]], 'root_set': [5], 'winner': 5}Failed
regression certificate 4{'children': [4, 12, 13], 'loser': 4, 'new_rank': 3, 'parent_updates': [[4, 6]], 'root_set': [4], 'winner': 6}{'children': [4, 12, 13], 'loser': 4, 'new_rank': 3, 'parent_updates': [[4, 6]], 'root_set': [6], 'winner': 6}Failed
regression certificate 5{'children': [9, 2, 3, 4], 'loser': 9, 'new_rank': 4, 'parent_updates': [[9, 1]], 'root_set': [9], 'winner': 1}{'children': [9, 2, 3, 4], 'loser': 9, 'new_rank': 4, 'parent_updates': [[9, 1]], 'root_set': [1], 'winner': 1}Failed
regression certificate 6{'children': [7, 3], 'loser': 7, 'new_rank': 2, 'parent_updates': [[7, 2]], 'root_set': [7], 'winner': 2}{'children': [7, 3], 'loser': 7, 'new_rank': 2, 'parent_updates': [[7, 2]], 'root_set': [2], 'winner': 2}Failed
variant-dependent certificate{'children': [7, 3], 'loser': 7, 'new_rank': 2, 'parent_updates': [[7, 2]], 'root_set': [7], 'winner': 2}{'children': [7, 3], 'loser': 7, 'new_rank': 2, 'parent_updates': [[7, 2]], 'root_set': [2], 'winner': 2}Failed

SHA-256 / 3cbdd5ef7e0b0e2d5219609061806b89b88fd94cd7fe883b72eee0643d96b4b4

3 / The verified repair

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

N = 1
observations = []
def solve(d):
    a=d['a']; b=d['b']; w,l=(a,b) if a[1]<=b[1] else (b,a)
    return {'winner': w[0],
    'loser': l[0],
    'new_rank': w[2]+1,
    'children': [l[0]]+w[3],
    'parent_updates': [[l[0],w[0]]],
    'root_set': [w[0]]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'a': [8, 2, 0, []], 'b': [3, 5, 0, []]}, {'winner': 8, 'loser': 3, 'new_rank': 1, 'children': [3], 'parent_updates': [[3, 8]], 'root_set': [8]}), ({'a': [2, 9, 0, []], 'b': [7, 1, 0, []]}, {'winner': 7, 'loser': 2, 'new_rank': 1, 'children': [2], 'parent_updates': [[2, 7]], 'root_set': [7]}), ({'a': [5, 4, 1, [1]], 'b': [9, 4, 1, [3]]}, {'winner': 5, 'loser': 9, 'new_rank': 2, 'children': [9, 1], 'parent_updates': [[9, 5]], 'root_set': [5]}), ({'a': [4, 8, 2, [10, 11]], 'b': [6, 3, 2, [12, 13]]}, {'winner': 6, 'loser': 4, 'new_rank': 3, 'children': [4, 12, 13], 'parent_updates': [[4, 6]], 'root_set': [6]}), ({'a': [1, 0, 3, [2, 3, 4]], 'b': [9, 8, 3, [10, 11, 12]]}, {'winner': 1, 'loser': 9, 'new_rank': 4, 'children': [9, 2, 3, 4], 'parent_updates': [[9, 1]], 'root_set': [1]}), ({'a': [7, 5, 1, [8]], 'b': [2, 2, 1, [3]]}, {'winner': 2, 'loser': 7, 'new_rank': 2, 'children': [7, 3], 'parent_updates': [[7, 2]], 'root_set': [2]}), ({'a': [7, 6, 1, [8]], 'b': [2, 2, 1, [3]]}, {'winner': 2, 'loser': 7, 'new_rank': 2, 'children': [7, 3], 'parent_updates': [[7, 2]], 'root_set': [2]})], [({'a': [8, 2, 0, []], 'b': [3, 5, 0, []]}, {'winner': 8, 'loser': 3, 'new_rank': 1, 'children': [3], 'parent_updates': [[3, 8]], 'root_set': [8]}), ({'a': [2, 9, 0, []], 'b': [7, 1, 0, []]}, {'winner': 7, 'loser': 2, 'new_rank': 1, 'children': [2], 'parent_updates': [[2, 7]], 'root_set': [7]}), ({'a': [5, 4, 1, [1]], 'b': [9, 4, 1, [3]]}, {'winner': 5, 'loser': 9, 'new_rank': 2, 'children': [9, 1], 'parent_updates': [[9, 5]], 'root_set': [5]}), ({'a': [4, 8, 2, [10, 11]], 'b': [6, 3, 2, [12, 13]]}, {'winner': 6, 'loser': 4, 'new_rank': 3, 'children': [4, 12, 13], 'parent_updates': [[4, 6]], 'root_set': [6]}), ({'a': [1, 0, 3, [2, 3, 4]], 'b': [9, 8, 3, [10, 11, 12]]}, {'winner': 1, 'loser': 9, 'new_rank': 4, 'children': [9, 2, 3, 4], 'parent_updates': [[9, 1]], 'root_set': [1]}), ({'a': [7, 5, 1, [8]], 'b': [2, 2, 1, [3]]}, {'winner': 2, 'loser': 7, 'new_rank': 2, 'children': [7, 3], 'parent_updates': [[7, 2]], 'root_set': [2]}), ({'a': [7, 7, 1, [8]], 'b': [2, 2, 1, [3]]}, {'winner': 2, 'loser': 7, 'new_rank': 2, 'children': [7, 3], 'parent_updates': [[7, 2]], 'root_set': [2]})], [({'a': [8, 2, 0, []], 'b': [3, 5, 0, []]}, {'winner': 8, 'loser': 3, 'new_rank': 1, 'children': [3], 'parent_updates': [[3, 8]], 'root_set': [8]}), ({'a': [2, 9, 0, []], 'b': [7, 1, 0, []]}, {'winner': 7, 'loser': 2, 'new_rank': 1, 'children': [2], 'parent_updates': [[2, 7]], 'root_set': [7]}), ({'a': [5, 4, 1, [1]], 'b': [9, 4, 1, [3]]}, {'winner': 5, 'loser': 9, 'new_rank': 2, 'children': [9, 1], 'parent_updates': [[9, 5]], 'root_set': [5]}), ({'a': [4, 8, 2, [10, 11]], 'b': [6, 3, 2, [12, 13]]}, {'winner': 6, 'loser': 4, 'new_rank': 3, 'children': [4, 12, 13], 'parent_updates': [[4, 6]], 'root_set': [6]}), ({'a': [1, 0, 3, [2, 3, 4]], 'b': [9, 8, 3, [10, 11, 12]]}, {'winner': 1, 'loser': 9, 'new_rank': 4, 'children': [9, 2, 3, 4], 'parent_updates': [[9, 1]], 'root_set': [1]}), ({'a': [7, 5, 1, [8]], 'b': [2, 2, 1, [3]]}, {'winner': 2, 'loser': 7, 'new_rank': 2, 'children': [7, 3], 'parent_updates': [[7, 2]], 'root_set': [2]}), ({'a': [7, 8, 1, [8]], 'b': [2, 2, 1, [3]]}, {'winner': 2, 'loser': 7, 'new_rank': 2, 'children': [7, 3], 'parent_updates': [[7, 2]], 'root_set': [2]})], [({'a': [8, 2, 0, []], 'b': [3, 5, 0, []]}, {'winner': 8, 'loser': 3, 'new_rank': 1, 'children': [3], 'parent_updates': [[3, 8]], 'root_set': [8]}), ({'a': [2, 9, 0, []], 'b': [7, 1, 0, []]}, {'winner': 7, 'loser': 2, 'new_rank': 1, 'children': [2], 'parent_updates': [[2, 7]], 'root_set': [7]}), ({'a': [5, 4, 1, [1]], 'b': [9, 4, 1, [3]]}, {'winner': 5, 'loser': 9, 'new_rank': 2, 'children': [9, 1], 'parent_updates': [[9, 5]], 'root_set': [5]}), ({'a': [4, 8, 2, [10, 11]], 'b': [6, 3, 2, [12, 13]]}, {'winner': 6, 'loser': 4, 'new_rank': 3, 'children': [4, 12, 13], 'parent_updates': [[4, 6]], 'root_set': [6]}), ({'a': [1, 0, 3, [2, 3, 4]], 'b': [9, 8, 3, [10, 11, 12]]}, {'winner': 1, 'loser': 9, 'new_rank': 4, 'children': [9, 2, 3, 4], 'parent_updates': [[9, 1]], 'root_set': [1]}), ({'a': [7, 5, 1, [8]], 'b': [2, 2, 1, [3]]}, {'winner': 2, 'loser': 7, 'new_rank': 2, 'children': [7, 3], 'parent_updates': [[7, 2]], 'root_set': [2]}), ({'a': [7, 9, 1, [8]], 'b': [2, 2, 1, [3]]}, {'winner': 2, 'loser': 7, 'new_rank': 2, 'children': [7, 3], 'parent_updates': [[7, 2]], 'root_set': [2]})], [({'a': [8, 2, 0, []], 'b': [3, 5, 0, []]}, {'winner': 8, 'loser': 3, 'new_rank': 1, 'children': [3], 'parent_updates': [[3, 8]], 'root_set': [8]}), ({'a': [2, 9, 0, []], 'b': [7, 1, 0, []]}, {'winner': 7, 'loser': 2, 'new_rank': 1, 'children': [2], 'parent_updates': [[2, 7]], 'root_set': [7]}), ({'a': [5, 4, 1, [1]], 'b': [9, 4, 1, [3]]}, {'winner': 5, 'loser': 9, 'new_rank': 2, 'children': [9, 1], 'parent_updates': [[9, 5]], 'root_set': [5]}), ({'a': [4, 8, 2, [10, 11]], 'b': [6, 3, 2, [12, 13]]}, {'winner': 6, 'loser': 4, 'new_rank': 3, 'children': [4, 12, 13], 'parent_updates': [[4, 6]], 'root_set': [6]}), ({'a': [1, 0, 3, [2, 3, 4]], 'b': [9, 8, 3, [10, 11, 12]]}, {'winner': 1, 'loser': 9, 'new_rank': 4, 'children': [9, 2, 3, 4], 'parent_updates': [[9, 1]], 'root_set': [1]}), ({'a': [7, 5, 1, [8]], 'b': [2, 2, 1, [3]]}, {'winner': 2, 'loser': 7, 'new_rank': 2, 'children': [7, 3], 'parent_updates': [[7, 2]], 'root_set': [2]}), ({'a': [7, 10, 1, [8]], 'b': [2, 2, 1, [3]]}, {'winner': 2, 'loser': 7, 'new_rank': 2, 'children': [7, 3], 'parent_updates': [[7, 2]], 'root_set': [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{'children': [3], 'loser': 3, 'new_rank': 1, 'parent_updates': [[3, 8]], 'root_set': [8], 'winner': 8}{'children': [3], 'loser': 3, 'new_rank': 1, 'parent_updates': [[3, 8]], 'root_set': [8], 'winner': 8}Passed
regression certificate 2{'children': [2], 'loser': 2, 'new_rank': 1, 'parent_updates': [[2, 7]], 'root_set': [7], 'winner': 7}{'children': [2], 'loser': 2, 'new_rank': 1, 'parent_updates': [[2, 7]], 'root_set': [7], 'winner': 7}Passed
regression certificate 3{'children': [9, 1], 'loser': 9, 'new_rank': 2, 'parent_updates': [[9, 5]], 'root_set': [5], 'winner': 5}{'children': [9, 1], 'loser': 9, 'new_rank': 2, 'parent_updates': [[9, 5]], 'root_set': [5], 'winner': 5}Passed
regression certificate 4{'children': [4, 12, 13], 'loser': 4, 'new_rank': 3, 'parent_updates': [[4, 6]], 'root_set': [6], 'winner': 6}{'children': [4, 12, 13], 'loser': 4, 'new_rank': 3, 'parent_updates': [[4, 6]], 'root_set': [6], 'winner': 6}Passed
regression certificate 5{'children': [9, 2, 3, 4], 'loser': 9, 'new_rank': 4, 'parent_updates': [[9, 1]], 'root_set': [1], 'winner': 1}{'children': [9, 2, 3, 4], 'loser': 9, 'new_rank': 4, 'parent_updates': [[9, 1]], 'root_set': [1], 'winner': 1}Passed
regression certificate 6{'children': [7, 3], 'loser': 7, 'new_rank': 2, 'parent_updates': [[7, 2]], 'root_set': [2], 'winner': 2}{'children': [7, 3], 'loser': 7, 'new_rank': 2, 'parent_updates': [[7, 2]], 'root_set': [2], 'winner': 2}Passed
variant-dependent certificate{'children': [7, 3], 'loser': 7, 'new_rank': 2, 'parent_updates': [[7, 2]], 'root_set': [2], 'winner': 2}{'children': [7, 3], 'loser': 7, 'new_rank': 2, 'parent_updates': [[7, 2]], 'root_set': [2], 'winner': 2}Passed

SHA-256 / 764807bf70dffddb2e86c25c3dae841745349f2017ab4b9a2797d6a001b487e7

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

Case digest / 4c75a70136e24c97d5985da4b64600ca27044cd5a70a3a03fbfb761fb164d8ea