broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(d):
    mn=d['min']; mx=d['max']; live=d['live']; x=d['erase']; low=[i for i in mn if i!=x]; high=[i for i in mx if i!=x]; remain={i:p for i,p in live.items() if i!=x}
    return {'min_ids': mn,
    'max_ids': high,
    'records': remain,
    'cross_index': [high.index(i) for i in low],
    'minimum': live[low[0]] if low else None,
    'maximum': live[high[0]] if high else None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 1}, 'min': ['variant', 'b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b', 'variant'], 'erase': 'c'}, {'min_ids': ['variant', 'b', 'd', 'a'], 'max_ids': ['a', 'd', 'b', 'variant'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 1}, 'cross_index': [3, 2, 1, 0], 'minimum': 1, 'maximum': 7})], [({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 2}, 'min': ['b', 'variant', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b', 'variant'], 'erase': 'c'}, {'min_ids': ['b', 'variant', 'd', 'a'], 'max_ids': ['a', 'd', 'b', 'variant'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 2}, 'cross_index': [2, 3, 1, 0], 'minimum': 2, 'maximum': 7})], [({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 3}, 'min': ['b', 'd', 'variant', 'c', 'a'], 'max': ['a', 'c', 'd', 'variant', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'variant', 'a'], 'max_ids': ['a', 'd', 'variant', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 3}, 'cross_index': [3, 1, 2, 0], 'minimum': 2, 'maximum': 7})], [({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 4}, 'min': ['b', 'd', 'variant', 'c', 'a'], 'max': ['a', 'c', 'variant', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'variant', 'a'], 'max_ids': ['a', 'variant', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 4}, 'cross_index': [3, 2, 1, 0], 'minimum': 2, 'maximum': 7})], [({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 5}, 'min': ['b', 'd', 'c', 'variant', 'a'], 'max': ['a', 'c', 'variant', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'variant', 'a'], 'max_ids': ['a', 'variant', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 5}, 'cross_index': [3, 2, 1, 0], 'minimum': 2, 'maximum': 7})]][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)

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(d):
    mn=d['min']; mx=d['max']; live=d['live']; x=d['erase']; low=[i for i in mn if i!=x]; high=[i for i in mx if i!=x]; remain={i:p for i,p in live.items() if i!=x}
    return {'min_ids': [i for i in mn if live[i]!=live[x]],
    'max_ids': high,
    'records': remain,
    'cross_index': [high.index(i) for i in low],
    'minimum': live[low[0]] if low else None,
    'maximum': live[high[0]] if high else None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 1}, 'min': ['variant', 'b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b', 'variant'], 'erase': 'c'}, {'min_ids': ['variant', 'b', 'd', 'a'], 'max_ids': ['a', 'd', 'b', 'variant'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 1}, 'cross_index': [3, 2, 1, 0], 'minimum': 1, 'maximum': 7})], [({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 2}, 'min': ['b', 'variant', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b', 'variant'], 'erase': 'c'}, {'min_ids': ['b', 'variant', 'd', 'a'], 'max_ids': ['a', 'd', 'b', 'variant'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 2}, 'cross_index': [2, 3, 1, 0], 'minimum': 2, 'maximum': 7})], [({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 3}, 'min': ['b', 'd', 'variant', 'c', 'a'], 'max': ['a', 'c', 'd', 'variant', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'variant', 'a'], 'max_ids': ['a', 'd', 'variant', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 3}, 'cross_index': [3, 1, 2, 0], 'minimum': 2, 'maximum': 7})], [({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 4}, 'min': ['b', 'd', 'variant', 'c', 'a'], 'max': ['a', 'c', 'variant', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'variant', 'a'], 'max_ids': ['a', 'variant', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 4}, 'cross_index': [3, 2, 1, 0], 'minimum': 2, 'maximum': 7})], [({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 5}, 'min': ['b', 'd', 'c', 'variant', 'a'], 'max': ['a', 'c', 'variant', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'variant', 'a'], 'max_ids': ['a', 'variant', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 5}, 'cross_index': [3, 2, 1, 0], 'minimum': 2, 'maximum': 7})]][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)

prompt:
The bounded twin heap delete certificate reports an incorrect min ids.

A double-ended heap certificate has min-order ids, max-order ids, and unique live records id->priority. Erase id x from both heaps by identity, preserving surviving order for this logical model. Report min ids, max ids, live map, cross-index mapping from surviving min slots to max slots, next minimum, and next maximum. Equal priorities retain separate identities.

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(d):
    mn=d['min']; mx=d['max']; live=d['live']; x=d['erase']; low=[i for i in mn if i!=x]; high=[i for i in mx if i!=x]; remain={i:p for i,p in live.items() if i!=x}
    return {'min_ids': low,
    'max_ids': mx,
    'records': remain,
    'cross_index': [high.index(i) for i in low],
    'minimum': live[low[0]] if low else None,
    'maximum': live[high[0]] if high else None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 1}, 'min': ['variant', 'b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b', 'variant'], 'erase': 'c'}, {'min_ids': ['variant', 'b', 'd', 'a'], 'max_ids': ['a', 'd', 'b', 'variant'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 1}, 'cross_index': [3, 2, 1, 0], 'minimum': 1, 'maximum': 7})], [({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 2}, 'min': ['b', 'variant', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b', 'variant'], 'erase': 'c'}, {'min_ids': ['b', 'variant', 'd', 'a'], 'max_ids': ['a', 'd', 'b', 'variant'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 2}, 'cross_index': [2, 3, 1, 0], 'minimum': 2, 'maximum': 7})], [({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 3}, 'min': ['b', 'd', 'variant', 'c', 'a'], 'max': ['a', 'c', 'd', 'variant', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'variant', 'a'], 'max_ids': ['a', 'd', 'variant', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 3}, 'cross_index': [3, 1, 2, 0], 'minimum': 2, 'maximum': 7})], [({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 4}, 'min': ['b', 'd', 'variant', 'c', 'a'], 'max': ['a', 'c', 'variant', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'variant', 'a'], 'max_ids': ['a', 'variant', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 4}, 'cross_index': [3, 2, 1, 0], 'minimum': 2, 'maximum': 7})], [({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 5}, 'min': ['b', 'd', 'c', 'variant', 'a'], 'max': ['a', 'c', 'variant', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'variant', 'a'], 'max_ids': ['a', 'variant', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 5}, 'cross_index': [3, 2, 1, 0], 'minimum': 2, 'maximum': 7})]][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)

meaning: Fixture-count band, not measured model difficulty

deps: stdlib

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(d):
    mn=d['min']; mx=d['max']; live=d['live']; x=d['erase']; low=[i for i in mn if i!=x]; high=[i for i in mx if i!=x]; remain={i:p for i,p in live.items() if i!=x}
    return {'min_ids': low,
    'max_ids': [i for i in mx if live[i]!=live[x]],
    'records': remain,
    'cross_index': [high.index(i) for i in low],
    'minimum': live[low[0]] if low else None,
    'maximum': live[high[0]] if high else None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 1}, 'min': ['variant', 'b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b', 'variant'], 'erase': 'c'}, {'min_ids': ['variant', 'b', 'd', 'a'], 'max_ids': ['a', 'd', 'b', 'variant'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 1}, 'cross_index': [3, 2, 1, 0], 'minimum': 1, 'maximum': 7})], [({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 2}, 'min': ['b', 'variant', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b', 'variant'], 'erase': 'c'}, {'min_ids': ['b', 'variant', 'd', 'a'], 'max_ids': ['a', 'd', 'b', 'variant'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 2}, 'cross_index': [2, 3, 1, 0], 'minimum': 2, 'maximum': 7})], [({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 3}, 'min': ['b', 'd', 'variant', 'c', 'a'], 'max': ['a', 'c', 'd', 'variant', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'variant', 'a'], 'max_ids': ['a', 'd', 'variant', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 3}, 'cross_index': [3, 1, 2, 0], 'minimum': 2, 'maximum': 7})], [({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 4}, 'min': ['b', 'd', 'variant', 'c', 'a'], 'max': ['a', 'c', 'variant', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'variant', 'a'], 'max_ids': ['a', 'variant', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 4}, 'cross_index': [3, 2, 1, 0], 'minimum': 2, 'maximum': 7})], [({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 5}, 'min': ['b', 'd', 'c', 'variant', 'a'], 'max': ['a', 'c', 'variant', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'variant', 'a'], 'max_ids': ['a', 'variant', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 5}, 'cross_index': [3, 2, 1, 0], 'minimum': 2, 'maximum': 7})]][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)

prompt:
The bounded twin heap delete certificate reports an incorrect max ids.

A double-ended heap certificate has min-order ids, max-order ids, and unique live records id->priority. Erase id x from both heaps by identity, preserving surviving order for this logical model. Report min ids, max ids, live map, cross-index mapping from surviving min slots to max slots, next minimum, and next maximum. Equal priorities retain separate identities.

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(d):
    mn=d['min']; mx=d['max']; live=d['live']; x=d['erase']; low=[i for i in mn if i!=x]; high=[i for i in mx if i!=x]; remain={i:p for i,p in live.items() if i!=x}
    return {'min_ids': low,
    'max_ids': high,
    'records': live,
    'cross_index': [high.index(i) for i in low],
    'minimum': live[low[0]] if low else None,
    'maximum': live[high[0]] if high else None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 1}, 'min': ['variant', 'b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b', 'variant'], 'erase': 'c'}, {'min_ids': ['variant', 'b', 'd', 'a'], 'max_ids': ['a', 'd', 'b', 'variant'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 1}, 'cross_index': [3, 2, 1, 0], 'minimum': 1, 'maximum': 7})], [({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 2}, 'min': ['b', 'variant', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b', 'variant'], 'erase': 'c'}, {'min_ids': ['b', 'variant', 'd', 'a'], 'max_ids': ['a', 'd', 'b', 'variant'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 2}, 'cross_index': [2, 3, 1, 0], 'minimum': 2, 'maximum': 7})], [({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 3}, 'min': ['b', 'd', 'variant', 'c', 'a'], 'max': ['a', 'c', 'd', 'variant', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'variant', 'a'], 'max_ids': ['a', 'd', 'variant', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 3}, 'cross_index': [3, 1, 2, 0], 'minimum': 2, 'maximum': 7})], [({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 4}, 'min': ['b', 'd', 'variant', 'c', 'a'], 'max': ['a', 'c', 'variant', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'variant', 'a'], 'max_ids': ['a', 'variant', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 4}, 'cross_index': [3, 2, 1, 0], 'minimum': 2, 'maximum': 7})], [({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 5}, 'min': ['b', 'd', 'c', 'variant', 'a'], 'max': ['a', 'c', 'variant', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'variant', 'a'], 'max_ids': ['a', 'variant', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 5}, 'cross_index': [3, 2, 1, 0], 'minimum': 2, 'maximum': 7})]][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)

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(d):
    mn=d['min']; mx=d['max']; live=d['live']; x=d['erase']; low=[i for i in mn if i!=x]; high=[i for i in mx if i!=x]; remain={i:p for i,p in live.items() if i!=x}
    return {'min_ids': low,
    'max_ids': high,
    'records': {i:p for i,p in live.items() if p!=live[x]},
    'cross_index': [high.index(i) for i in low],
    'minimum': live[low[0]] if low else None,
    'maximum': live[high[0]] if high else None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 1}, 'min': ['variant', 'b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b', 'variant'], 'erase': 'c'}, {'min_ids': ['variant', 'b', 'd', 'a'], 'max_ids': ['a', 'd', 'b', 'variant'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 1}, 'cross_index': [3, 2, 1, 0], 'minimum': 1, 'maximum': 7})], [({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 2}, 'min': ['b', 'variant', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b', 'variant'], 'erase': 'c'}, {'min_ids': ['b', 'variant', 'd', 'a'], 'max_ids': ['a', 'd', 'b', 'variant'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 2}, 'cross_index': [2, 3, 1, 0], 'minimum': 2, 'maximum': 7})], [({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 3}, 'min': ['b', 'd', 'variant', 'c', 'a'], 'max': ['a', 'c', 'd', 'variant', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'variant', 'a'], 'max_ids': ['a', 'd', 'variant', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 3}, 'cross_index': [3, 1, 2, 0], 'minimum': 2, 'maximum': 7})], [({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 4}, 'min': ['b', 'd', 'variant', 'c', 'a'], 'max': ['a', 'c', 'variant', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'variant', 'a'], 'max_ids': ['a', 'variant', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 4}, 'cross_index': [3, 2, 1, 0], 'minimum': 2, 'maximum': 7})], [({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 5}, 'min': ['b', 'd', 'c', 'variant', 'a'], 'max': ['a', 'c', 'variant', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'variant', 'a'], 'max_ids': ['a', 'variant', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 5}, 'cross_index': [3, 2, 1, 0], 'minimum': 2, 'maximum': 7})]][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)

prompt:
The bounded twin heap delete certificate reports an incorrect records.

A double-ended heap certificate has min-order ids, max-order ids, and unique live records id->priority. Erase id x from both heaps by identity, preserving surviving order for this logical model. Report min ids, max ids, live map, cross-index mapping from surviving min slots to max slots, next minimum, and next maximum. Equal priorities retain separate identities.

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(d):
    mn=d['min']; mx=d['max']; live=d['live']; x=d['erase']; low=[i for i in mn if i!=x]; high=[i for i in mx if i!=x]; remain={i:p for i,p in live.items() if i!=x}
    return {'min_ids': low,
    'max_ids': high,
    'records': remain,
    'cross_index': [mx.index(i) for i in low],
    'minimum': live[low[0]] if low else None,
    'maximum': live[high[0]] if high else None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 1}, 'min': ['variant', 'b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b', 'variant'], 'erase': 'c'}, {'min_ids': ['variant', 'b', 'd', 'a'], 'max_ids': ['a', 'd', 'b', 'variant'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 1}, 'cross_index': [3, 2, 1, 0], 'minimum': 1, 'maximum': 7})], [({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 2}, 'min': ['b', 'variant', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b', 'variant'], 'erase': 'c'}, {'min_ids': ['b', 'variant', 'd', 'a'], 'max_ids': ['a', 'd', 'b', 'variant'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 2}, 'cross_index': [2, 3, 1, 0], 'minimum': 2, 'maximum': 7})], [({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 3}, 'min': ['b', 'd', 'variant', 'c', 'a'], 'max': ['a', 'c', 'd', 'variant', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'variant', 'a'], 'max_ids': ['a', 'd', 'variant', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 3}, 'cross_index': [3, 1, 2, 0], 'minimum': 2, 'maximum': 7})], [({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 4}, 'min': ['b', 'd', 'variant', 'c', 'a'], 'max': ['a', 'c', 'variant', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'variant', 'a'], 'max_ids': ['a', 'variant', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 4}, 'cross_index': [3, 2, 1, 0], 'minimum': 2, 'maximum': 7})], [({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 5}, 'min': ['b', 'd', 'c', 'variant', 'a'], 'max': ['a', 'c', 'variant', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'variant', 'a'], 'max_ids': ['a', 'variant', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 5}, 'cross_index': [3, 2, 1, 0], 'minimum': 2, 'maximum': 7})]][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)

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(d):
    mn=d['min']; mx=d['max']; live=d['live']; x=d['erase']; low=[i for i in mn if i!=x]; high=[i for i in mx if i!=x]; remain={i:p for i,p in live.items() if i!=x}
    return {'min_ids': low,
    'max_ids': high,
    'records': remain,
    'cross_index': list(range(len(low))),
    'minimum': live[low[0]] if low else None,
    'maximum': live[high[0]] if high else None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 1}, 'min': ['variant', 'b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b', 'variant'], 'erase': 'c'}, {'min_ids': ['variant', 'b', 'd', 'a'], 'max_ids': ['a', 'd', 'b', 'variant'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 1}, 'cross_index': [3, 2, 1, 0], 'minimum': 1, 'maximum': 7})], [({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 2}, 'min': ['b', 'variant', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b', 'variant'], 'erase': 'c'}, {'min_ids': ['b', 'variant', 'd', 'a'], 'max_ids': ['a', 'd', 'b', 'variant'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 2}, 'cross_index': [2, 3, 1, 0], 'minimum': 2, 'maximum': 7})], [({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 3}, 'min': ['b', 'd', 'variant', 'c', 'a'], 'max': ['a', 'c', 'd', 'variant', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'variant', 'a'], 'max_ids': ['a', 'd', 'variant', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 3}, 'cross_index': [3, 1, 2, 0], 'minimum': 2, 'maximum': 7})], [({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 4}, 'min': ['b', 'd', 'variant', 'c', 'a'], 'max': ['a', 'c', 'variant', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'variant', 'a'], 'max_ids': ['a', 'variant', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 4}, 'cross_index': [3, 2, 1, 0], 'minimum': 2, 'maximum': 7})], [({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 5}, 'min': ['b', 'd', 'c', 'variant', 'a'], 'max': ['a', 'c', 'variant', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'variant', 'a'], 'max_ids': ['a', 'variant', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 5}, 'cross_index': [3, 2, 1, 0], 'minimum': 2, 'maximum': 7})]][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)

prompt:
The bounded twin heap delete certificate reports an incorrect cross index.

A double-ended heap certificate has min-order ids, max-order ids, and unique live records id->priority. Erase id x from both heaps by identity, preserving surviving order for this logical model. Report min ids, max ids, live map, cross-index mapping from surviving min slots to max slots, next minimum, and next maximum. Equal priorities retain separate identities.

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(d):
    mn=d['min']; mx=d['max']; live=d['live']; x=d['erase']; low=[i for i in mn if i!=x]; high=[i for i in mx if i!=x]; remain={i:p for i,p in live.items() if i!=x}
    return {'min_ids': low,
    'max_ids': high,
    'records': remain,
    'cross_index': [high.index(i) for i in low],
    'minimum': live[mn[0]] if mn else None,
    'maximum': live[high[0]] if high else None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 1}, 'min': ['variant', 'b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b', 'variant'], 'erase': 'c'}, {'min_ids': ['variant', 'b', 'd', 'a'], 'max_ids': ['a', 'd', 'b', 'variant'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 1}, 'cross_index': [3, 2, 1, 0], 'minimum': 1, 'maximum': 7})], [({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 2}, 'min': ['b', 'variant', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b', 'variant'], 'erase': 'c'}, {'min_ids': ['b', 'variant', 'd', 'a'], 'max_ids': ['a', 'd', 'b', 'variant'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 2}, 'cross_index': [2, 3, 1, 0], 'minimum': 2, 'maximum': 7})], [({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 3}, 'min': ['b', 'd', 'variant', 'c', 'a'], 'max': ['a', 'c', 'd', 'variant', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'variant', 'a'], 'max_ids': ['a', 'd', 'variant', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 3}, 'cross_index': [3, 1, 2, 0], 'minimum': 2, 'maximum': 7})], [({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 4}, 'min': ['b', 'd', 'variant', 'c', 'a'], 'max': ['a', 'c', 'variant', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'variant', 'a'], 'max_ids': ['a', 'variant', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 4}, 'cross_index': [3, 2, 1, 0], 'minimum': 2, 'maximum': 7})], [({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 5}, 'min': ['b', 'd', 'c', 'variant', 'a'], 'max': ['a', 'c', 'variant', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'variant', 'a'], 'max_ids': ['a', 'variant', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 5}, 'cross_index': [3, 2, 1, 0], 'minimum': 2, 'maximum': 7})]][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)

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(d):
    mn=d['min']; mx=d['max']; live=d['live']; x=d['erase']; low=[i for i in mn if i!=x]; high=[i for i in mx if i!=x]; remain={i:p for i,p in live.items() if i!=x}
    return {'min_ids': low,
    'max_ids': high,
    'records': remain,
    'cross_index': [high.index(i) for i in low],
    'minimum': low[0] if low else None,
    'maximum': live[high[0]] if high else None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 1}, 'min': ['variant', 'b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b', 'variant'], 'erase': 'c'}, {'min_ids': ['variant', 'b', 'd', 'a'], 'max_ids': ['a', 'd', 'b', 'variant'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 1}, 'cross_index': [3, 2, 1, 0], 'minimum': 1, 'maximum': 7})], [({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 2}, 'min': ['b', 'variant', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b', 'variant'], 'erase': 'c'}, {'min_ids': ['b', 'variant', 'd', 'a'], 'max_ids': ['a', 'd', 'b', 'variant'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 2}, 'cross_index': [2, 3, 1, 0], 'minimum': 2, 'maximum': 7})], [({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 3}, 'min': ['b', 'd', 'variant', 'c', 'a'], 'max': ['a', 'c', 'd', 'variant', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'variant', 'a'], 'max_ids': ['a', 'd', 'variant', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 3}, 'cross_index': [3, 1, 2, 0], 'minimum': 2, 'maximum': 7})], [({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 4}, 'min': ['b', 'd', 'variant', 'c', 'a'], 'max': ['a', 'c', 'variant', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'variant', 'a'], 'max_ids': ['a', 'variant', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 4}, 'cross_index': [3, 2, 1, 0], 'minimum': 2, 'maximum': 7})], [({'live': {'a': 2}, 'min': ['a'], 'max': ['a'], 'erase': 'a'}, {'min_ids': [], 'max_ids': [], 'records': {}, 'cross_index': [], 'minimum': None, 'maximum': None}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'a'}, {'min_ids': ['b'], 'max_ids': ['b'], 'records': {'b': 5}, 'cross_index': [0], 'minimum': 5, 'maximum': 5}), ({'live': {'a': 1, 'b': 5}, 'min': ['a', 'b'], 'max': ['b', 'a'], 'erase': 'b'}, {'min_ids': ['a'], 'max_ids': ['a'], 'records': {'a': 1}, 'cross_index': [0], 'minimum': 1, 'maximum': 1}), ({'live': {'a': 3, 'b': 3, 'c': 6}, 'min': ['a', 'b', 'c'], 'max': ['c', 'a', 'b'], 'erase': 'a'}, {'min_ids': ['b', 'c'], 'max_ids': ['c', 'b'], 'records': {'b': 3, 'c': 6}, 'cross_index': [1, 0], 'minimum': 3, 'maximum': 6}), ({'live': {'a': 1, 'b': 8, 'c': 3, 'd': 8}, 'min': ['a', 'c', 'b', 'd'], 'max': ['b', 'd', 'c', 'a'], 'erase': 'd'}, {'min_ids': ['a', 'c', 'b'], 'max_ids': ['b', 'c', 'a'], 'records': {'a': 1, 'b': 8, 'c': 3}, 'cross_index': [2, 1, 0], 'minimum': 1, 'maximum': 8}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3}, 'min': ['b', 'd', 'c', 'a'], 'max': ['a', 'c', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'a'], 'max_ids': ['a', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3}, 'cross_index': [2, 1, 0], 'minimum': 2, 'maximum': 7}), ({'live': {'a': 7, 'b': 2, 'c': 5, 'd': 3, 'variant': 5}, 'min': ['b', 'd', 'c', 'variant', 'a'], 'max': ['a', 'c', 'variant', 'd', 'b'], 'erase': 'c'}, {'min_ids': ['b', 'd', 'variant', 'a'], 'max_ids': ['a', 'variant', 'd', 'b'], 'records': {'a': 7, 'b': 2, 'd': 3, 'variant': 5}, 'cross_index': [3, 2, 1, 0], 'minimum': 2, 'maximum': 7})]][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)

prompt:
The bounded twin heap delete certificate reports an incorrect minimum.

A double-ended heap certificate has min-order ids, max-order ids, and unique live records id->priority. Erase id x from both heaps by identity, preserving surviving order for this logical model. Report min ids, max ids, live map, cross-index mapping from surviving min slots to max slots, next minimum, and next maximum. Equal priorities retain separate identities.

split: open-access