FAILURE MAP
← Case archive

FA-41091 / Heap invariants / Open access

Replacement selection has no current candidate when every replacement is frozen · case 01

The bounded replacement selection certificate reports an incorrect next.

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

ROOT CAUSE

Replacement selection has no current candidate when every replacement is frozen.

VERIFIED REPAIR

Derive next using min((x[1] for x in active),default=None) under the stated bounded certificate contract.

Unsuccessful approach: The local patch uses last if not active else active[0][1] and still violates the stated relation.

Case contract

A replacement-selection external-sort heap receives last emitted key and new records [id,key]. Keys >=last remain active for current run; smaller keys freeze for next run. Return active ids, frozen ids, active sorted order, frozen sorted order, next current-run key, and end-run flag. Equal keys stay active.

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):
    last=d['last']; a=d['arrivals']; active=[x for x in a if x[1]>=last]; frozen=[x for x in a if x[1]<last]
    return {'active': [x[0] for x in active],
    'frozen': [x[0] for x in frozen],
    'active_order': [x[0] for x in sorted(active,key=lambda x:x[1])],
    'frozen_order': [x[0] for x in sorted(frozen,key=lambda x:x[1])],
    'next': min((x[1] for x in a),default=None),
    'run_ended': not active}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'last': 3, 'arrivals': []}, {'active': [], 'frozen': [], 'active_order': [], 'frozen_order': [], 'next': None, 'run_ended': True}), ({'last': 3, 'arrivals': [['a', 3]]}, {'active': ['a'], 'frozen': [], 'active_order': ['a'], 'frozen_order': [], 'next': 3, 'run_ended': False}), ({'last': 5, 'arrivals': [['a', 7], ['b', 2], ['c', 5], ['d', 1], ['e', 6]]}, {'active': ['a', 'c', 'e'], 'frozen': ['b', 'd'], 'active_order': ['c', 'e', 'a'], 'frozen_order': ['d', 'b'], 'next': 5, 'run_ended': False}), ({'last': 8, 'arrivals': [['a', 4], ['b', 2], ['c', 6]]}, {'active': [], 'frozen': ['a', 'b', 'c'], 'active_order': [], 'frozen_order': ['b', 'a', 'c'], 'next': None, 'run_ended': True}), ({'last': 0, 'arrivals': [['a', 3], ['b', 1], ['c', 2]]}, {'active': ['a', 'b', 'c'], 'frozen': [], 'active_order': ['b', 'c', 'a'], 'frozen_order': [], 'next': 1, 'run_ended': False}), ({'last': 4, 'arrivals': [['a', 4], ['b', 4], ['c', 3]]}, {'active': ['a', 'b'], 'frozen': ['c'], 'active_order': ['a', 'b'], 'frozen_order': ['c'], 'next': 4, 'run_ended': False}), ({'last': 5, 'arrivals': [['a', 4], ['b', 4], ['c', 3]]}, {'active': [], 'frozen': ['a', 'b', 'c'], 'active_order': [], 'frozen_order': ['c', 'a', 'b'], 'next': None, 'run_ended': True})], [({'last': 3, 'arrivals': []}, {'active': [], 'frozen': [], 'active_order': [], 'frozen_order': [], 'next': None, 'run_ended': True}), ({'last': 3, 'arrivals': [['a', 3]]}, {'active': ['a'], 'frozen': [], 'active_order': ['a'], 'frozen_order': [], 'next': 3, 'run_ended': False}), ({'last': 5, 'arrivals': [['a', 7], ['b', 2], ['c', 5], ['d', 1], ['e', 6]]}, {'active': ['a', 'c', 'e'], 'frozen': ['b', 'd'], 'active_order': ['c', 'e', 'a'], 'frozen_order': ['d', 'b'], 'next': 5, 'run_ended': False}), ({'last': 8, 'arrivals': [['a', 4], ['b', 2], ['c', 6]]}, {'active': [], 'frozen': ['a', 'b', 'c'], 'active_order': [], 'frozen_order': ['b', 'a', 'c'], 'next': None, 'run_ended': True}), ({'last': 0, 'arrivals': [['a', 3], ['b', 1], ['c', 2]]}, {'active': ['a', 'b', 'c'], 'frozen': [], 'active_order': ['b', 'c', 'a'], 'frozen_order': [], 'next': 1, 'run_ended': False}), ({'last': 4, 'arrivals': [['a', 4], ['b', 4], ['c', 3]]}, {'active': ['a', 'b'], 'frozen': ['c'], 'active_order': ['a', 'b'], 'frozen_order': ['c'], 'next': 4, 'run_ended': False}), ({'last': 6, 'arrivals': [['a', 4], ['b', 4], ['c', 3]]}, {'active': [], 'frozen': ['a', 'b', 'c'], 'active_order': [], 'frozen_order': ['c', 'a', 'b'], 'next': None, 'run_ended': True})], [({'last': 3, 'arrivals': []}, {'active': [], 'frozen': [], 'active_order': [], 'frozen_order': [], 'next': None, 'run_ended': True}), ({'last': 3, 'arrivals': [['a', 3]]}, {'active': ['a'], 'frozen': [], 'active_order': ['a'], 'frozen_order': [], 'next': 3, 'run_ended': False}), ({'last': 5, 'arrivals': [['a', 7], ['b', 2], ['c', 5], ['d', 1], ['e', 6]]}, {'active': ['a', 'c', 'e'], 'frozen': ['b', 'd'], 'active_order': ['c', 'e', 'a'], 'frozen_order': ['d', 'b'], 'next': 5, 'run_ended': False}), ({'last': 8, 'arrivals': [['a', 4], ['b', 2], ['c', 6]]}, {'active': [], 'frozen': ['a', 'b', 'c'], 'active_order': [], 'frozen_order': ['b', 'a', 'c'], 'next': None, 'run_ended': True}), ({'last': 0, 'arrivals': [['a', 3], ['b', 1], ['c', 2]]}, {'active': ['a', 'b', 'c'], 'frozen': [], 'active_order': ['b', 'c', 'a'], 'frozen_order': [], 'next': 1, 'run_ended': False}), ({'last': 4, 'arrivals': [['a', 4], ['b', 4], ['c', 3]]}, {'active': ['a', 'b'], 'frozen': ['c'], 'active_order': ['a', 'b'], 'frozen_order': ['c'], 'next': 4, 'run_ended': False}), ({'last': 7, 'arrivals': [['a', 4], ['b', 4], ['c', 3]]}, {'active': [], 'frozen': ['a', 'b', 'c'], 'active_order': [], 'frozen_order': ['c', 'a', 'b'], 'next': None, 'run_ended': True})], [({'last': 3, 'arrivals': []}, {'active': [], 'frozen': [], 'active_order': [], 'frozen_order': [], 'next': None, 'run_ended': True}), ({'last': 3, 'arrivals': [['a', 3]]}, {'active': ['a'], 'frozen': [], 'active_order': ['a'], 'frozen_order': [], 'next': 3, 'run_ended': False}), ({'last': 5, 'arrivals': [['a', 7], ['b', 2], ['c', 5], ['d', 1], ['e', 6]]}, {'active': ['a', 'c', 'e'], 'frozen': ['b', 'd'], 'active_order': ['c', 'e', 'a'], 'frozen_order': ['d', 'b'], 'next': 5, 'run_ended': False}), ({'last': 8, 'arrivals': [['a', 4], ['b', 2], ['c', 6]]}, {'active': [], 'frozen': ['a', 'b', 'c'], 'active_order': [], 'frozen_order': ['b', 'a', 'c'], 'next': None, 'run_ended': True}), ({'last': 0, 'arrivals': [['a', 3], ['b', 1], ['c', 2]]}, {'active': ['a', 'b', 'c'], 'frozen': [], 'active_order': ['b', 'c', 'a'], 'frozen_order': [], 'next': 1, 'run_ended': False}), ({'last': 4, 'arrivals': [['a', 4], ['b', 4], ['c', 3]]}, {'active': ['a', 'b'], 'frozen': ['c'], 'active_order': ['a', 'b'], 'frozen_order': ['c'], 'next': 4, 'run_ended': False}), ({'last': 8, 'arrivals': [['a', 4], ['b', 4], ['c', 3]]}, {'active': [], 'frozen': ['a', 'b', 'c'], 'active_order': [], 'frozen_order': ['c', 'a', 'b'], 'next': None, 'run_ended': True})], [({'last': 3, 'arrivals': []}, {'active': [], 'frozen': [], 'active_order': [], 'frozen_order': [], 'next': None, 'run_ended': True}), ({'last': 3, 'arrivals': [['a', 3]]}, {'active': ['a'], 'frozen': [], 'active_order': ['a'], 'frozen_order': [], 'next': 3, 'run_ended': False}), ({'last': 5, 'arrivals': [['a', 7], ['b', 2], ['c', 5], ['d', 1], ['e', 6]]}, {'active': ['a', 'c', 'e'], 'frozen': ['b', 'd'], 'active_order': ['c', 'e', 'a'], 'frozen_order': ['d', 'b'], 'next': 5, 'run_ended': False}), ({'last': 8, 'arrivals': [['a', 4], ['b', 2], ['c', 6]]}, {'active': [], 'frozen': ['a', 'b', 'c'], 'active_order': [], 'frozen_order': ['b', 'a', 'c'], 'next': None, 'run_ended': True}), ({'last': 0, 'arrivals': [['a', 3], ['b', 1], ['c', 2]]}, {'active': ['a', 'b', 'c'], 'frozen': [], 'active_order': ['b', 'c', 'a'], 'frozen_order': [], 'next': 1, 'run_ended': False}), ({'last': 4, 'arrivals': [['a', 4], ['b', 4], ['c', 3]]}, {'active': ['a', 'b'], 'frozen': ['c'], 'active_order': ['a', 'b'], 'frozen_order': ['c'], 'next': 4, 'run_ended': False}), ({'last': 9, 'arrivals': [['a', 4], ['b', 4], ['c', 3]]}, {'active': [], 'frozen': ['a', 'b', 'c'], 'active_order': [], 'frozen_order': ['c', 'a', 'b'], 'next': None, 'run_ended': True})]][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{'active': [], 'active_order': [], 'frozen': [], 'frozen_order': [], 'next': None, 'run_ended': True}{'active': [], 'active_order': [], 'frozen': [], 'frozen_order': [], 'next': None, 'run_ended': True}Passed
regression certificate 2{'active': ['a'], 'active_order': ['a'], 'frozen': [], 'frozen_order': [], 'next': 3, 'run_ended': False}{'active': ['a'], 'active_order': ['a'], 'frozen': [], 'frozen_order': [], 'next': 3, 'run_ended': False}Passed
regression certificate 3{'active': ['a', 'c', 'e'], 'active_order': ['c', 'e', 'a'], 'frozen': ['b', 'd'], 'frozen_order': ['d', 'b'], 'next': 1, 'run_ended': False}{'active': ['a', 'c', 'e'], 'active_order': ['c', 'e', 'a'], 'frozen': ['b', 'd'], 'frozen_order': ['d', 'b'], 'next': 5, 'run_ended': False}Failed
regression certificate 4{'active': [], 'active_order': [], 'frozen': ['a', 'b', 'c'], 'frozen_order': ['b', 'a', 'c'], 'next': 2, 'run_ended': True}{'active': [], 'active_order': [], 'frozen': ['a', 'b', 'c'], 'frozen_order': ['b', 'a', 'c'], 'next': None, 'run_ended': True}Failed
regression certificate 5{'active': ['a', 'b', 'c'], 'active_order': ['b', 'c', 'a'], 'frozen': [], 'frozen_order': [], 'next': 1, 'run_ended': False}{'active': ['a', 'b', 'c'], 'active_order': ['b', 'c', 'a'], 'frozen': [], 'frozen_order': [], 'next': 1, 'run_ended': False}Passed
regression certificate 6{'active': ['a', 'b'], 'active_order': ['a', 'b'], 'frozen': ['c'], 'frozen_order': ['c'], 'next': 3, 'run_ended': False}{'active': ['a', 'b'], 'active_order': ['a', 'b'], 'frozen': ['c'], 'frozen_order': ['c'], 'next': 4, 'run_ended': False}Failed
variant-dependent certificate{'active': [], 'active_order': [], 'frozen': ['a', 'b', 'c'], 'frozen_order': ['c', 'a', 'b'], 'next': 3, 'run_ended': True}{'active': [], 'active_order': [], 'frozen': ['a', 'b', 'c'], 'frozen_order': ['c', 'a', 'b'], 'next': None, 'run_ended': True}Failed

SHA-256 / 0fb992832b611f2767f2aebad5912045795e21152e45bff4aab614a4a6883b9b

2 / The unsuccessful fix

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

N = 1
observations = []
def solve(d):
    last=d['last']; a=d['arrivals']; active=[x for x in a if x[1]>=last]; frozen=[x for x in a if x[1]<last]
    return {'active': [x[0] for x in active],
    'frozen': [x[0] for x in frozen],
    'active_order': [x[0] for x in sorted(active,key=lambda x:x[1])],
    'frozen_order': [x[0] for x in sorted(frozen,key=lambda x:x[1])],
    'next': last if not active else active[0][1],
    'run_ended': not active}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'last': 3, 'arrivals': []}, {'active': [], 'frozen': [], 'active_order': [], 'frozen_order': [], 'next': None, 'run_ended': True}), ({'last': 3, 'arrivals': [['a', 3]]}, {'active': ['a'], 'frozen': [], 'active_order': ['a'], 'frozen_order': [], 'next': 3, 'run_ended': False}), ({'last': 5, 'arrivals': [['a', 7], ['b', 2], ['c', 5], ['d', 1], ['e', 6]]}, {'active': ['a', 'c', 'e'], 'frozen': ['b', 'd'], 'active_order': ['c', 'e', 'a'], 'frozen_order': ['d', 'b'], 'next': 5, 'run_ended': False}), ({'last': 8, 'arrivals': [['a', 4], ['b', 2], ['c', 6]]}, {'active': [], 'frozen': ['a', 'b', 'c'], 'active_order': [], 'frozen_order': ['b', 'a', 'c'], 'next': None, 'run_ended': True}), ({'last': 0, 'arrivals': [['a', 3], ['b', 1], ['c', 2]]}, {'active': ['a', 'b', 'c'], 'frozen': [], 'active_order': ['b', 'c', 'a'], 'frozen_order': [], 'next': 1, 'run_ended': False}), ({'last': 4, 'arrivals': [['a', 4], ['b', 4], ['c', 3]]}, {'active': ['a', 'b'], 'frozen': ['c'], 'active_order': ['a', 'b'], 'frozen_order': ['c'], 'next': 4, 'run_ended': False}), ({'last': 5, 'arrivals': [['a', 4], ['b', 4], ['c', 3]]}, {'active': [], 'frozen': ['a', 'b', 'c'], 'active_order': [], 'frozen_order': ['c', 'a', 'b'], 'next': None, 'run_ended': True})], [({'last': 3, 'arrivals': []}, {'active': [], 'frozen': [], 'active_order': [], 'frozen_order': [], 'next': None, 'run_ended': True}), ({'last': 3, 'arrivals': [['a', 3]]}, {'active': ['a'], 'frozen': [], 'active_order': ['a'], 'frozen_order': [], 'next': 3, 'run_ended': False}), ({'last': 5, 'arrivals': [['a', 7], ['b', 2], ['c', 5], ['d', 1], ['e', 6]]}, {'active': ['a', 'c', 'e'], 'frozen': ['b', 'd'], 'active_order': ['c', 'e', 'a'], 'frozen_order': ['d', 'b'], 'next': 5, 'run_ended': False}), ({'last': 8, 'arrivals': [['a', 4], ['b', 2], ['c', 6]]}, {'active': [], 'frozen': ['a', 'b', 'c'], 'active_order': [], 'frozen_order': ['b', 'a', 'c'], 'next': None, 'run_ended': True}), ({'last': 0, 'arrivals': [['a', 3], ['b', 1], ['c', 2]]}, {'active': ['a', 'b', 'c'], 'frozen': [], 'active_order': ['b', 'c', 'a'], 'frozen_order': [], 'next': 1, 'run_ended': False}), ({'last': 4, 'arrivals': [['a', 4], ['b', 4], ['c', 3]]}, {'active': ['a', 'b'], 'frozen': ['c'], 'active_order': ['a', 'b'], 'frozen_order': ['c'], 'next': 4, 'run_ended': False}), ({'last': 6, 'arrivals': [['a', 4], ['b', 4], ['c', 3]]}, {'active': [], 'frozen': ['a', 'b', 'c'], 'active_order': [], 'frozen_order': ['c', 'a', 'b'], 'next': None, 'run_ended': True})], [({'last': 3, 'arrivals': []}, {'active': [], 'frozen': [], 'active_order': [], 'frozen_order': [], 'next': None, 'run_ended': True}), ({'last': 3, 'arrivals': [['a', 3]]}, {'active': ['a'], 'frozen': [], 'active_order': ['a'], 'frozen_order': [], 'next': 3, 'run_ended': False}), ({'last': 5, 'arrivals': [['a', 7], ['b', 2], ['c', 5], ['d', 1], ['e', 6]]}, {'active': ['a', 'c', 'e'], 'frozen': ['b', 'd'], 'active_order': ['c', 'e', 'a'], 'frozen_order': ['d', 'b'], 'next': 5, 'run_ended': False}), ({'last': 8, 'arrivals': [['a', 4], ['b', 2], ['c', 6]]}, {'active': [], 'frozen': ['a', 'b', 'c'], 'active_order': [], 'frozen_order': ['b', 'a', 'c'], 'next': None, 'run_ended': True}), ({'last': 0, 'arrivals': [['a', 3], ['b', 1], ['c', 2]]}, {'active': ['a', 'b', 'c'], 'frozen': [], 'active_order': ['b', 'c', 'a'], 'frozen_order': [], 'next': 1, 'run_ended': False}), ({'last': 4, 'arrivals': [['a', 4], ['b', 4], ['c', 3]]}, {'active': ['a', 'b'], 'frozen': ['c'], 'active_order': ['a', 'b'], 'frozen_order': ['c'], 'next': 4, 'run_ended': False}), ({'last': 7, 'arrivals': [['a', 4], ['b', 4], ['c', 3]]}, {'active': [], 'frozen': ['a', 'b', 'c'], 'active_order': [], 'frozen_order': ['c', 'a', 'b'], 'next': None, 'run_ended': True})], [({'last': 3, 'arrivals': []}, {'active': [], 'frozen': [], 'active_order': [], 'frozen_order': [], 'next': None, 'run_ended': True}), ({'last': 3, 'arrivals': [['a', 3]]}, {'active': ['a'], 'frozen': [], 'active_order': ['a'], 'frozen_order': [], 'next': 3, 'run_ended': False}), ({'last': 5, 'arrivals': [['a', 7], ['b', 2], ['c', 5], ['d', 1], ['e', 6]]}, {'active': ['a', 'c', 'e'], 'frozen': ['b', 'd'], 'active_order': ['c', 'e', 'a'], 'frozen_order': ['d', 'b'], 'next': 5, 'run_ended': False}), ({'last': 8, 'arrivals': [['a', 4], ['b', 2], ['c', 6]]}, {'active': [], 'frozen': ['a', 'b', 'c'], 'active_order': [], 'frozen_order': ['b', 'a', 'c'], 'next': None, 'run_ended': True}), ({'last': 0, 'arrivals': [['a', 3], ['b', 1], ['c', 2]]}, {'active': ['a', 'b', 'c'], 'frozen': [], 'active_order': ['b', 'c', 'a'], 'frozen_order': [], 'next': 1, 'run_ended': False}), ({'last': 4, 'arrivals': [['a', 4], ['b', 4], ['c', 3]]}, {'active': ['a', 'b'], 'frozen': ['c'], 'active_order': ['a', 'b'], 'frozen_order': ['c'], 'next': 4, 'run_ended': False}), ({'last': 8, 'arrivals': [['a', 4], ['b', 4], ['c', 3]]}, {'active': [], 'frozen': ['a', 'b', 'c'], 'active_order': [], 'frozen_order': ['c', 'a', 'b'], 'next': None, 'run_ended': True})], [({'last': 3, 'arrivals': []}, {'active': [], 'frozen': [], 'active_order': [], 'frozen_order': [], 'next': None, 'run_ended': True}), ({'last': 3, 'arrivals': [['a', 3]]}, {'active': ['a'], 'frozen': [], 'active_order': ['a'], 'frozen_order': [], 'next': 3, 'run_ended': False}), ({'last': 5, 'arrivals': [['a', 7], ['b', 2], ['c', 5], ['d', 1], ['e', 6]]}, {'active': ['a', 'c', 'e'], 'frozen': ['b', 'd'], 'active_order': ['c', 'e', 'a'], 'frozen_order': ['d', 'b'], 'next': 5, 'run_ended': False}), ({'last': 8, 'arrivals': [['a', 4], ['b', 2], ['c', 6]]}, {'active': [], 'frozen': ['a', 'b', 'c'], 'active_order': [], 'frozen_order': ['b', 'a', 'c'], 'next': None, 'run_ended': True}), ({'last': 0, 'arrivals': [['a', 3], ['b', 1], ['c', 2]]}, {'active': ['a', 'b', 'c'], 'frozen': [], 'active_order': ['b', 'c', 'a'], 'frozen_order': [], 'next': 1, 'run_ended': False}), ({'last': 4, 'arrivals': [['a', 4], ['b', 4], ['c', 3]]}, {'active': ['a', 'b'], 'frozen': ['c'], 'active_order': ['a', 'b'], 'frozen_order': ['c'], 'next': 4, 'run_ended': False}), ({'last': 9, 'arrivals': [['a', 4], ['b', 4], ['c', 3]]}, {'active': [], 'frozen': ['a', 'b', 'c'], 'active_order': [], 'frozen_order': ['c', 'a', 'b'], 'next': None, 'run_ended': True})]][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{'active': [], 'active_order': [], 'frozen': [], 'frozen_order': [], 'next': 3, 'run_ended': True}{'active': [], 'active_order': [], 'frozen': [], 'frozen_order': [], 'next': None, 'run_ended': True}Failed
regression certificate 2{'active': ['a'], 'active_order': ['a'], 'frozen': [], 'frozen_order': [], 'next': 3, 'run_ended': False}{'active': ['a'], 'active_order': ['a'], 'frozen': [], 'frozen_order': [], 'next': 3, 'run_ended': False}Passed
regression certificate 3{'active': ['a', 'c', 'e'], 'active_order': ['c', 'e', 'a'], 'frozen': ['b', 'd'], 'frozen_order': ['d', 'b'], 'next': 7, 'run_ended': False}{'active': ['a', 'c', 'e'], 'active_order': ['c', 'e', 'a'], 'frozen': ['b', 'd'], 'frozen_order': ['d', 'b'], 'next': 5, 'run_ended': False}Failed
regression certificate 4{'active': [], 'active_order': [], 'frozen': ['a', 'b', 'c'], 'frozen_order': ['b', 'a', 'c'], 'next': 8, 'run_ended': True}{'active': [], 'active_order': [], 'frozen': ['a', 'b', 'c'], 'frozen_order': ['b', 'a', 'c'], 'next': None, 'run_ended': True}Failed
regression certificate 5{'active': ['a', 'b', 'c'], 'active_order': ['b', 'c', 'a'], 'frozen': [], 'frozen_order': [], 'next': 3, 'run_ended': False}{'active': ['a', 'b', 'c'], 'active_order': ['b', 'c', 'a'], 'frozen': [], 'frozen_order': [], 'next': 1, 'run_ended': False}Failed
regression certificate 6{'active': ['a', 'b'], 'active_order': ['a', 'b'], 'frozen': ['c'], 'frozen_order': ['c'], 'next': 4, 'run_ended': False}{'active': ['a', 'b'], 'active_order': ['a', 'b'], 'frozen': ['c'], 'frozen_order': ['c'], 'next': 4, 'run_ended': False}Passed
variant-dependent certificate{'active': [], 'active_order': [], 'frozen': ['a', 'b', 'c'], 'frozen_order': ['c', 'a', 'b'], 'next': 5, 'run_ended': True}{'active': [], 'active_order': [], 'frozen': ['a', 'b', 'c'], 'frozen_order': ['c', 'a', 'b'], 'next': None, 'run_ended': True}Failed

SHA-256 / adddc1321596adbde9cb5814967e2a37a84ae98211a62a127a481c8c19d7e5ea

3 / The verified repair

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

N = 1
observations = []
def solve(d):
    last=d['last']; a=d['arrivals']; active=[x for x in a if x[1]>=last]; frozen=[x for x in a if x[1]<last]
    return {'active': [x[0] for x in active],
    'frozen': [x[0] for x in frozen],
    'active_order': [x[0] for x in sorted(active,key=lambda x:x[1])],
    'frozen_order': [x[0] for x in sorted(frozen,key=lambda x:x[1])],
    'next': min((x[1] for x in active),default=None),
    'run_ended': not active}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'last': 3, 'arrivals': []}, {'active': [], 'frozen': [], 'active_order': [], 'frozen_order': [], 'next': None, 'run_ended': True}), ({'last': 3, 'arrivals': [['a', 3]]}, {'active': ['a'], 'frozen': [], 'active_order': ['a'], 'frozen_order': [], 'next': 3, 'run_ended': False}), ({'last': 5, 'arrivals': [['a', 7], ['b', 2], ['c', 5], ['d', 1], ['e', 6]]}, {'active': ['a', 'c', 'e'], 'frozen': ['b', 'd'], 'active_order': ['c', 'e', 'a'], 'frozen_order': ['d', 'b'], 'next': 5, 'run_ended': False}), ({'last': 8, 'arrivals': [['a', 4], ['b', 2], ['c', 6]]}, {'active': [], 'frozen': ['a', 'b', 'c'], 'active_order': [], 'frozen_order': ['b', 'a', 'c'], 'next': None, 'run_ended': True}), ({'last': 0, 'arrivals': [['a', 3], ['b', 1], ['c', 2]]}, {'active': ['a', 'b', 'c'], 'frozen': [], 'active_order': ['b', 'c', 'a'], 'frozen_order': [], 'next': 1, 'run_ended': False}), ({'last': 4, 'arrivals': [['a', 4], ['b', 4], ['c', 3]]}, {'active': ['a', 'b'], 'frozen': ['c'], 'active_order': ['a', 'b'], 'frozen_order': ['c'], 'next': 4, 'run_ended': False}), ({'last': 5, 'arrivals': [['a', 4], ['b', 4], ['c', 3]]}, {'active': [], 'frozen': ['a', 'b', 'c'], 'active_order': [], 'frozen_order': ['c', 'a', 'b'], 'next': None, 'run_ended': True})], [({'last': 3, 'arrivals': []}, {'active': [], 'frozen': [], 'active_order': [], 'frozen_order': [], 'next': None, 'run_ended': True}), ({'last': 3, 'arrivals': [['a', 3]]}, {'active': ['a'], 'frozen': [], 'active_order': ['a'], 'frozen_order': [], 'next': 3, 'run_ended': False}), ({'last': 5, 'arrivals': [['a', 7], ['b', 2], ['c', 5], ['d', 1], ['e', 6]]}, {'active': ['a', 'c', 'e'], 'frozen': ['b', 'd'], 'active_order': ['c', 'e', 'a'], 'frozen_order': ['d', 'b'], 'next': 5, 'run_ended': False}), ({'last': 8, 'arrivals': [['a', 4], ['b', 2], ['c', 6]]}, {'active': [], 'frozen': ['a', 'b', 'c'], 'active_order': [], 'frozen_order': ['b', 'a', 'c'], 'next': None, 'run_ended': True}), ({'last': 0, 'arrivals': [['a', 3], ['b', 1], ['c', 2]]}, {'active': ['a', 'b', 'c'], 'frozen': [], 'active_order': ['b', 'c', 'a'], 'frozen_order': [], 'next': 1, 'run_ended': False}), ({'last': 4, 'arrivals': [['a', 4], ['b', 4], ['c', 3]]}, {'active': ['a', 'b'], 'frozen': ['c'], 'active_order': ['a', 'b'], 'frozen_order': ['c'], 'next': 4, 'run_ended': False}), ({'last': 6, 'arrivals': [['a', 4], ['b', 4], ['c', 3]]}, {'active': [], 'frozen': ['a', 'b', 'c'], 'active_order': [], 'frozen_order': ['c', 'a', 'b'], 'next': None, 'run_ended': True})], [({'last': 3, 'arrivals': []}, {'active': [], 'frozen': [], 'active_order': [], 'frozen_order': [], 'next': None, 'run_ended': True}), ({'last': 3, 'arrivals': [['a', 3]]}, {'active': ['a'], 'frozen': [], 'active_order': ['a'], 'frozen_order': [], 'next': 3, 'run_ended': False}), ({'last': 5, 'arrivals': [['a', 7], ['b', 2], ['c', 5], ['d', 1], ['e', 6]]}, {'active': ['a', 'c', 'e'], 'frozen': ['b', 'd'], 'active_order': ['c', 'e', 'a'], 'frozen_order': ['d', 'b'], 'next': 5, 'run_ended': False}), ({'last': 8, 'arrivals': [['a', 4], ['b', 2], ['c', 6]]}, {'active': [], 'frozen': ['a', 'b', 'c'], 'active_order': [], 'frozen_order': ['b', 'a', 'c'], 'next': None, 'run_ended': True}), ({'last': 0, 'arrivals': [['a', 3], ['b', 1], ['c', 2]]}, {'active': ['a', 'b', 'c'], 'frozen': [], 'active_order': ['b', 'c', 'a'], 'frozen_order': [], 'next': 1, 'run_ended': False}), ({'last': 4, 'arrivals': [['a', 4], ['b', 4], ['c', 3]]}, {'active': ['a', 'b'], 'frozen': ['c'], 'active_order': ['a', 'b'], 'frozen_order': ['c'], 'next': 4, 'run_ended': False}), ({'last': 7, 'arrivals': [['a', 4], ['b', 4], ['c', 3]]}, {'active': [], 'frozen': ['a', 'b', 'c'], 'active_order': [], 'frozen_order': ['c', 'a', 'b'], 'next': None, 'run_ended': True})], [({'last': 3, 'arrivals': []}, {'active': [], 'frozen': [], 'active_order': [], 'frozen_order': [], 'next': None, 'run_ended': True}), ({'last': 3, 'arrivals': [['a', 3]]}, {'active': ['a'], 'frozen': [], 'active_order': ['a'], 'frozen_order': [], 'next': 3, 'run_ended': False}), ({'last': 5, 'arrivals': [['a', 7], ['b', 2], ['c', 5], ['d', 1], ['e', 6]]}, {'active': ['a', 'c', 'e'], 'frozen': ['b', 'd'], 'active_order': ['c', 'e', 'a'], 'frozen_order': ['d', 'b'], 'next': 5, 'run_ended': False}), ({'last': 8, 'arrivals': [['a', 4], ['b', 2], ['c', 6]]}, {'active': [], 'frozen': ['a', 'b', 'c'], 'active_order': [], 'frozen_order': ['b', 'a', 'c'], 'next': None, 'run_ended': True}), ({'last': 0, 'arrivals': [['a', 3], ['b', 1], ['c', 2]]}, {'active': ['a', 'b', 'c'], 'frozen': [], 'active_order': ['b', 'c', 'a'], 'frozen_order': [], 'next': 1, 'run_ended': False}), ({'last': 4, 'arrivals': [['a', 4], ['b', 4], ['c', 3]]}, {'active': ['a', 'b'], 'frozen': ['c'], 'active_order': ['a', 'b'], 'frozen_order': ['c'], 'next': 4, 'run_ended': False}), ({'last': 8, 'arrivals': [['a', 4], ['b', 4], ['c', 3]]}, {'active': [], 'frozen': ['a', 'b', 'c'], 'active_order': [], 'frozen_order': ['c', 'a', 'b'], 'next': None, 'run_ended': True})], [({'last': 3, 'arrivals': []}, {'active': [], 'frozen': [], 'active_order': [], 'frozen_order': [], 'next': None, 'run_ended': True}), ({'last': 3, 'arrivals': [['a', 3]]}, {'active': ['a'], 'frozen': [], 'active_order': ['a'], 'frozen_order': [], 'next': 3, 'run_ended': False}), ({'last': 5, 'arrivals': [['a', 7], ['b', 2], ['c', 5], ['d', 1], ['e', 6]]}, {'active': ['a', 'c', 'e'], 'frozen': ['b', 'd'], 'active_order': ['c', 'e', 'a'], 'frozen_order': ['d', 'b'], 'next': 5, 'run_ended': False}), ({'last': 8, 'arrivals': [['a', 4], ['b', 2], ['c', 6]]}, {'active': [], 'frozen': ['a', 'b', 'c'], 'active_order': [], 'frozen_order': ['b', 'a', 'c'], 'next': None, 'run_ended': True}), ({'last': 0, 'arrivals': [['a', 3], ['b', 1], ['c', 2]]}, {'active': ['a', 'b', 'c'], 'frozen': [], 'active_order': ['b', 'c', 'a'], 'frozen_order': [], 'next': 1, 'run_ended': False}), ({'last': 4, 'arrivals': [['a', 4], ['b', 4], ['c', 3]]}, {'active': ['a', 'b'], 'frozen': ['c'], 'active_order': ['a', 'b'], 'frozen_order': ['c'], 'next': 4, 'run_ended': False}), ({'last': 9, 'arrivals': [['a', 4], ['b', 4], ['c', 3]]}, {'active': [], 'frozen': ['a', 'b', 'c'], 'active_order': [], 'frozen_order': ['c', 'a', 'b'], 'next': None, 'run_ended': True})]][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{'active': [], 'active_order': [], 'frozen': [], 'frozen_order': [], 'next': None, 'run_ended': True}{'active': [], 'active_order': [], 'frozen': [], 'frozen_order': [], 'next': None, 'run_ended': True}Passed
regression certificate 2{'active': ['a'], 'active_order': ['a'], 'frozen': [], 'frozen_order': [], 'next': 3, 'run_ended': False}{'active': ['a'], 'active_order': ['a'], 'frozen': [], 'frozen_order': [], 'next': 3, 'run_ended': False}Passed
regression certificate 3{'active': ['a', 'c', 'e'], 'active_order': ['c', 'e', 'a'], 'frozen': ['b', 'd'], 'frozen_order': ['d', 'b'], 'next': 5, 'run_ended': False}{'active': ['a', 'c', 'e'], 'active_order': ['c', 'e', 'a'], 'frozen': ['b', 'd'], 'frozen_order': ['d', 'b'], 'next': 5, 'run_ended': False}Passed
regression certificate 4{'active': [], 'active_order': [], 'frozen': ['a', 'b', 'c'], 'frozen_order': ['b', 'a', 'c'], 'next': None, 'run_ended': True}{'active': [], 'active_order': [], 'frozen': ['a', 'b', 'c'], 'frozen_order': ['b', 'a', 'c'], 'next': None, 'run_ended': True}Passed
regression certificate 5{'active': ['a', 'b', 'c'], 'active_order': ['b', 'c', 'a'], 'frozen': [], 'frozen_order': [], 'next': 1, 'run_ended': False}{'active': ['a', 'b', 'c'], 'active_order': ['b', 'c', 'a'], 'frozen': [], 'frozen_order': [], 'next': 1, 'run_ended': False}Passed
regression certificate 6{'active': ['a', 'b'], 'active_order': ['a', 'b'], 'frozen': ['c'], 'frozen_order': ['c'], 'next': 4, 'run_ended': False}{'active': ['a', 'b'], 'active_order': ['a', 'b'], 'frozen': ['c'], 'frozen_order': ['c'], 'next': 4, 'run_ended': False}Passed
variant-dependent certificate{'active': [], 'active_order': [], 'frozen': ['a', 'b', 'c'], 'frozen_order': ['c', 'a', 'b'], 'next': None, 'run_ended': True}{'active': [], 'active_order': [], 'frozen': ['a', 'b', 'c'], 'frozen_order': ['c', 'a', 'b'], 'next': None, 'run_ended': True}Passed

SHA-256 / 9e1e99e97427693a96676d3ebfcd8047b77347935d344db25c769f8be901d5b7

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

Case digest / b19b7c2b3d6c8ad88909218f36bd683f986e08e3e4f2ffe7f945d646425dd28a