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

N = 1
observations = []
def solve(d):
    q=d['records']; live=d['live']; valid=[i for i,x in enumerate(q) if x[2] in live and live[x[2]][0]==x[3]]; j=valid[0] if valid else None
    return {'selected': None if j is None else q[j][2],
    'payload': None if j is None else live[q[j][2]][1],
    'discarded': len(q) if j is None else j,
    'suffix': [] if j is None else q[j+1:],
    'live_after': {k:v for k,v in live.items() if j is None or k!=q[j][2]},
    'empty': not q}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'records': [], 'live': {}}, {'selected': None, 'payload': None, 'discarded': 0, 'suffix': [], 'live_after': {}, 'empty': True}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': [0, 'A']}}, {'selected': 'a', 'payload': 'A', 'discarded': 0, 'suffix': [], 'live_after': {}, 'empty': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1], [3, 2, 'b', 0]], 'live': {'a': [1, 'new'], 'b': [0, 'B']}}, {'selected': 'a', 'payload': 'new', 'discarded': 1, 'suffix': [[3, 2, 'b', 0]], 'live_after': {'b': [0, 'B']}, 'empty': False}), ({'records': [[0, 0, 'x', 2], [1, 1, 'b', 0]], 'live': {'b': [0, 'B']}}, {'selected': 'b', 'payload': 'B', 'discarded': 1, 'suffix': [], 'live_after': {}, 'empty': False}), ({'records': [[1, 0, 'a', 1]], 'live': {'a': [2, 'A']}}, {'selected': None, 'payload': None, 'discarded': 1, 'suffix': [], 'live_after': {'a': [2, 'A']}, 'empty': True}), ({'records': [[1, 0, 'c', 0], [1, 1, 'b', 0], [2, 2, 'a', 1]], 'live': {'a': [1, 'A'], 'b': [0, 'B'], 'c': [0, 'C']}}, {'selected': 'c', 'payload': 'C', 'discarded': 0, 'suffix': [[1, 1, 'b', 0], [2, 2, 'a', 1]], 'live_after': {'a': [1, 'A'], 'b': [0, 'B']}, 'empty': False}), ({'records': [[0, -1, 'stale1', 0], [1, 0, 'c', 0], [1, 1, 'b', 0], [2, 2, 'a', 1]], 'live': {'a': [1, 'A'], 'b': [0, 'B'], 'c': [0, 'C']}}, {'selected': 'c', 'payload': 'C', 'discarded': 1, 'suffix': [[1, 1, 'b', 0], [2, 2, 'a', 1]], 'live_after': {'a': [1, 'A'], 'b': [0, 'B']}, 'empty': False})], [({'records': [], 'live': {}}, {'selected': None, 'payload': None, 'discarded': 0, 'suffix': [], 'live_after': {}, 'empty': True}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': [0, 'A']}}, {'selected': 'a', 'payload': 'A', 'discarded': 0, 'suffix': [], 'live_after': {}, 'empty': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1], [3, 2, 'b', 0]], 'live': {'a': [1, 'new'], 'b': [0, 'B']}}, {'selected': 'a', 'payload': 'new', 'discarded': 1, 'suffix': [[3, 2, 'b', 0]], 'live_after': {'b': [0, 'B']}, 'empty': False}), ({'records': [[0, 0, 'x', 2], [1, 1, 'b', 0]], 'live': {'b': [0, 'B']}}, {'selected': 'b', 'payload': 'B', 'discarded': 1, 'suffix': [], 'live_after': {}, 'empty': False}), ({'records': [[1, 0, 'a', 1]], 'live': {'a': [2, 'A']}}, {'selected': None, 'payload': None, 'discarded': 1, 'suffix': [], 'live_after': {'a': [2, 'A']}, 'empty': True}), ({'records': [[1, 0, 'c', 0], [1, 1, 'b', 0], [2, 2, 'a', 1]], 'live': {'a': [1, 'A'], 'b': [0, 'B'], 'c': [0, 'C']}}, {'selected': 'c', 'payload': 'C', 'discarded': 0, 'suffix': [[1, 1, 'b', 0], [2, 2, 'a', 1]], 'live_after': {'a': [1, 'A'], 'b': [0, 'B']}, 'empty': False}), ({'records': [[0, -2, 'stale2', 0], [0, -2, 'stale2', 0], [1, 0, 'c', 0], [1, 1, 'b', 0], [2, 2, 'a', 1]], 'live': {'a': [1, 'A'], 'b': [0, 'B'], 'c': [0, 'C']}}, {'selected': 'c', 'payload': 'C', 'discarded': 2, 'suffix': [[1, 1, 'b', 0], [2, 2, 'a', 1]], 'live_after': {'a': [1, 'A'], 'b': [0, 'B']}, 'empty': False})], [({'records': [], 'live': {}}, {'selected': None, 'payload': None, 'discarded': 0, 'suffix': [], 'live_after': {}, 'empty': True}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': [0, 'A']}}, {'selected': 'a', 'payload': 'A', 'discarded': 0, 'suffix': [], 'live_after': {}, 'empty': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1], [3, 2, 'b', 0]], 'live': {'a': [1, 'new'], 'b': [0, 'B']}}, {'selected': 'a', 'payload': 'new', 'discarded': 1, 'suffix': [[3, 2, 'b', 0]], 'live_after': {'b': [0, 'B']}, 'empty': False}), ({'records': [[0, 0, 'x', 2], [1, 1, 'b', 0]], 'live': {'b': [0, 'B']}}, {'selected': 'b', 'payload': 'B', 'discarded': 1, 'suffix': [], 'live_after': {}, 'empty': False}), ({'records': [[1, 0, 'a', 1]], 'live': {'a': [2, 'A']}}, {'selected': None, 'payload': None, 'discarded': 1, 'suffix': [], 'live_after': {'a': [2, 'A']}, 'empty': True}), ({'records': [[1, 0, 'c', 0], [1, 1, 'b', 0], [2, 2, 'a', 1]], 'live': {'a': [1, 'A'], 'b': [0, 'B'], 'c': [0, 'C']}}, {'selected': 'c', 'payload': 'C', 'discarded': 0, 'suffix': [[1, 1, 'b', 0], [2, 2, 'a', 1]], 'live_after': {'a': [1, 'A'], 'b': [0, 'B']}, 'empty': False}), ({'records': [[0, -3, 'stale3', 0], [0, -3, 'stale3', 0], [0, -3, 'stale3', 0], [1, 0, 'c', 0], [1, 1, 'b', 0], [2, 2, 'a', 1]], 'live': {'a': [1, 'A'], 'b': [0, 'B'], 'c': [0, 'C']}}, {'selected': 'c', 'payload': 'C', 'discarded': 3, 'suffix': [[1, 1, 'b', 0], [2, 2, 'a', 1]], 'live_after': {'a': [1, 'A'], 'b': [0, 'B']}, 'empty': False})], [({'records': [], 'live': {}}, {'selected': None, 'payload': None, 'discarded': 0, 'suffix': [], 'live_after': {}, 'empty': True}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': [0, 'A']}}, {'selected': 'a', 'payload': 'A', 'discarded': 0, 'suffix': [], 'live_after': {}, 'empty': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1], [3, 2, 'b', 0]], 'live': {'a': [1, 'new'], 'b': [0, 'B']}}, {'selected': 'a', 'payload': 'new', 'discarded': 1, 'suffix': [[3, 2, 'b', 0]], 'live_after': {'b': [0, 'B']}, 'empty': False}), ({'records': [[0, 0, 'x', 2], [1, 1, 'b', 0]], 'live': {'b': [0, 'B']}}, {'selected': 'b', 'payload': 'B', 'discarded': 1, 'suffix': [], 'live_after': {}, 'empty': False}), ({'records': [[1, 0, 'a', 1]], 'live': {'a': [2, 'A']}}, {'selected': None, 'payload': None, 'discarded': 1, 'suffix': [], 'live_after': {'a': [2, 'A']}, 'empty': True}), ({'records': [[1, 0, 'c', 0], [1, 1, 'b', 0], [2, 2, 'a', 1]], 'live': {'a': [1, 'A'], 'b': [0, 'B'], 'c': [0, 'C']}}, {'selected': 'c', 'payload': 'C', 'discarded': 0, 'suffix': [[1, 1, 'b', 0], [2, 2, 'a', 1]], 'live_after': {'a': [1, 'A'], 'b': [0, 'B']}, 'empty': False}), ({'records': [[0, -4, 'stale4', 0], [0, -4, 'stale4', 0], [0, -4, 'stale4', 0], [0, -4, 'stale4', 0], [1, 0, 'c', 0], [1, 1, 'b', 0], [2, 2, 'a', 1]], 'live': {'a': [1, 'A'], 'b': [0, 'B'], 'c': [0, 'C']}}, {'selected': 'c', 'payload': 'C', 'discarded': 4, 'suffix': [[1, 1, 'b', 0], [2, 2, 'a', 1]], 'live_after': {'a': [1, 'A'], 'b': [0, 'B']}, 'empty': False})], [({'records': [], 'live': {}}, {'selected': None, 'payload': None, 'discarded': 0, 'suffix': [], 'live_after': {}, 'empty': True}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': [0, 'A']}}, {'selected': 'a', 'payload': 'A', 'discarded': 0, 'suffix': [], 'live_after': {}, 'empty': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1], [3, 2, 'b', 0]], 'live': {'a': [1, 'new'], 'b': [0, 'B']}}, {'selected': 'a', 'payload': 'new', 'discarded': 1, 'suffix': [[3, 2, 'b', 0]], 'live_after': {'b': [0, 'B']}, 'empty': False}), ({'records': [[0, 0, 'x', 2], [1, 1, 'b', 0]], 'live': {'b': [0, 'B']}}, {'selected': 'b', 'payload': 'B', 'discarded': 1, 'suffix': [], 'live_after': {}, 'empty': False}), ({'records': [[1, 0, 'a', 1]], 'live': {'a': [2, 'A']}}, {'selected': None, 'payload': None, 'discarded': 1, 'suffix': [], 'live_after': {'a': [2, 'A']}, 'empty': True}), ({'records': [[1, 0, 'c', 0], [1, 1, 'b', 0], [2, 2, 'a', 1]], 'live': {'a': [1, 'A'], 'b': [0, 'B'], 'c': [0, 'C']}}, {'selected': 'c', 'payload': 'C', 'discarded': 0, 'suffix': [[1, 1, 'b', 0], [2, 2, 'a', 1]], 'live_after': {'a': [1, 'A'], 'b': [0, 'B']}, 'empty': False}), ({'records': [[0, -5, 'stale5', 0], [0, -5, 'stale5', 0], [0, -5, 'stale5', 0], [0, -5, 'stale5', 0], [0, -5, 'stale5', 0], [1, 0, 'c', 0], [1, 1, 'b', 0], [2, 2, 'a', 1]], 'live': {'a': [1, 'A'], 'b': [0, 'B'], 'c': [0, 'C']}}, {'selected': 'c', 'payload': 'C', 'discarded': 5, 'suffix': [[1, 1, 'b', 0], [2, 2, 'a', 1]], 'live_after': {'a': [1, 'A'], 'b': [0, 'B']}, 'empty': False})]][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):
    q=d['records']; live=d['live']; valid=[i for i,x in enumerate(q) if x[2] in live and live[x[2]][0]==x[3]]; j=valid[0] if valid else None
    return {'selected': None if j is None else q[j][2],
    'payload': None if j is None else live[q[j][2]][1],
    'discarded': len(q) if j is None else j,
    'suffix': [] if j is None else q[j+1:],
    'live_after': {k:v for k,v in live.items() if j is None or k!=q[j][2]},
    'empty': not live}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'records': [], 'live': {}}, {'selected': None, 'payload': None, 'discarded': 0, 'suffix': [], 'live_after': {}, 'empty': True}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': [0, 'A']}}, {'selected': 'a', 'payload': 'A', 'discarded': 0, 'suffix': [], 'live_after': {}, 'empty': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1], [3, 2, 'b', 0]], 'live': {'a': [1, 'new'], 'b': [0, 'B']}}, {'selected': 'a', 'payload': 'new', 'discarded': 1, 'suffix': [[3, 2, 'b', 0]], 'live_after': {'b': [0, 'B']}, 'empty': False}), ({'records': [[0, 0, 'x', 2], [1, 1, 'b', 0]], 'live': {'b': [0, 'B']}}, {'selected': 'b', 'payload': 'B', 'discarded': 1, 'suffix': [], 'live_after': {}, 'empty': False}), ({'records': [[1, 0, 'a', 1]], 'live': {'a': [2, 'A']}}, {'selected': None, 'payload': None, 'discarded': 1, 'suffix': [], 'live_after': {'a': [2, 'A']}, 'empty': True}), ({'records': [[1, 0, 'c', 0], [1, 1, 'b', 0], [2, 2, 'a', 1]], 'live': {'a': [1, 'A'], 'b': [0, 'B'], 'c': [0, 'C']}}, {'selected': 'c', 'payload': 'C', 'discarded': 0, 'suffix': [[1, 1, 'b', 0], [2, 2, 'a', 1]], 'live_after': {'a': [1, 'A'], 'b': [0, 'B']}, 'empty': False}), ({'records': [[0, -1, 'stale1', 0], [1, 0, 'c', 0], [1, 1, 'b', 0], [2, 2, 'a', 1]], 'live': {'a': [1, 'A'], 'b': [0, 'B'], 'c': [0, 'C']}}, {'selected': 'c', 'payload': 'C', 'discarded': 1, 'suffix': [[1, 1, 'b', 0], [2, 2, 'a', 1]], 'live_after': {'a': [1, 'A'], 'b': [0, 'B']}, 'empty': False})], [({'records': [], 'live': {}}, {'selected': None, 'payload': None, 'discarded': 0, 'suffix': [], 'live_after': {}, 'empty': True}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': [0, 'A']}}, {'selected': 'a', 'payload': 'A', 'discarded': 0, 'suffix': [], 'live_after': {}, 'empty': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1], [3, 2, 'b', 0]], 'live': {'a': [1, 'new'], 'b': [0, 'B']}}, {'selected': 'a', 'payload': 'new', 'discarded': 1, 'suffix': [[3, 2, 'b', 0]], 'live_after': {'b': [0, 'B']}, 'empty': False}), ({'records': [[0, 0, 'x', 2], [1, 1, 'b', 0]], 'live': {'b': [0, 'B']}}, {'selected': 'b', 'payload': 'B', 'discarded': 1, 'suffix': [], 'live_after': {}, 'empty': False}), ({'records': [[1, 0, 'a', 1]], 'live': {'a': [2, 'A']}}, {'selected': None, 'payload': None, 'discarded': 1, 'suffix': [], 'live_after': {'a': [2, 'A']}, 'empty': True}), ({'records': [[1, 0, 'c', 0], [1, 1, 'b', 0], [2, 2, 'a', 1]], 'live': {'a': [1, 'A'], 'b': [0, 'B'], 'c': [0, 'C']}}, {'selected': 'c', 'payload': 'C', 'discarded': 0, 'suffix': [[1, 1, 'b', 0], [2, 2, 'a', 1]], 'live_after': {'a': [1, 'A'], 'b': [0, 'B']}, 'empty': False}), ({'records': [[0, -2, 'stale2', 0], [0, -2, 'stale2', 0], [1, 0, 'c', 0], [1, 1, 'b', 0], [2, 2, 'a', 1]], 'live': {'a': [1, 'A'], 'b': [0, 'B'], 'c': [0, 'C']}}, {'selected': 'c', 'payload': 'C', 'discarded': 2, 'suffix': [[1, 1, 'b', 0], [2, 2, 'a', 1]], 'live_after': {'a': [1, 'A'], 'b': [0, 'B']}, 'empty': False})], [({'records': [], 'live': {}}, {'selected': None, 'payload': None, 'discarded': 0, 'suffix': [], 'live_after': {}, 'empty': True}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': [0, 'A']}}, {'selected': 'a', 'payload': 'A', 'discarded': 0, 'suffix': [], 'live_after': {}, 'empty': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1], [3, 2, 'b', 0]], 'live': {'a': [1, 'new'], 'b': [0, 'B']}}, {'selected': 'a', 'payload': 'new', 'discarded': 1, 'suffix': [[3, 2, 'b', 0]], 'live_after': {'b': [0, 'B']}, 'empty': False}), ({'records': [[0, 0, 'x', 2], [1, 1, 'b', 0]], 'live': {'b': [0, 'B']}}, {'selected': 'b', 'payload': 'B', 'discarded': 1, 'suffix': [], 'live_after': {}, 'empty': False}), ({'records': [[1, 0, 'a', 1]], 'live': {'a': [2, 'A']}}, {'selected': None, 'payload': None, 'discarded': 1, 'suffix': [], 'live_after': {'a': [2, 'A']}, 'empty': True}), ({'records': [[1, 0, 'c', 0], [1, 1, 'b', 0], [2, 2, 'a', 1]], 'live': {'a': [1, 'A'], 'b': [0, 'B'], 'c': [0, 'C']}}, {'selected': 'c', 'payload': 'C', 'discarded': 0, 'suffix': [[1, 1, 'b', 0], [2, 2, 'a', 1]], 'live_after': {'a': [1, 'A'], 'b': [0, 'B']}, 'empty': False}), ({'records': [[0, -3, 'stale3', 0], [0, -3, 'stale3', 0], [0, -3, 'stale3', 0], [1, 0, 'c', 0], [1, 1, 'b', 0], [2, 2, 'a', 1]], 'live': {'a': [1, 'A'], 'b': [0, 'B'], 'c': [0, 'C']}}, {'selected': 'c', 'payload': 'C', 'discarded': 3, 'suffix': [[1, 1, 'b', 0], [2, 2, 'a', 1]], 'live_after': {'a': [1, 'A'], 'b': [0, 'B']}, 'empty': False})], [({'records': [], 'live': {}}, {'selected': None, 'payload': None, 'discarded': 0, 'suffix': [], 'live_after': {}, 'empty': True}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': [0, 'A']}}, {'selected': 'a', 'payload': 'A', 'discarded': 0, 'suffix': [], 'live_after': {}, 'empty': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1], [3, 2, 'b', 0]], 'live': {'a': [1, 'new'], 'b': [0, 'B']}}, {'selected': 'a', 'payload': 'new', 'discarded': 1, 'suffix': [[3, 2, 'b', 0]], 'live_after': {'b': [0, 'B']}, 'empty': False}), ({'records': [[0, 0, 'x', 2], [1, 1, 'b', 0]], 'live': {'b': [0, 'B']}}, {'selected': 'b', 'payload': 'B', 'discarded': 1, 'suffix': [], 'live_after': {}, 'empty': False}), ({'records': [[1, 0, 'a', 1]], 'live': {'a': [2, 'A']}}, {'selected': None, 'payload': None, 'discarded': 1, 'suffix': [], 'live_after': {'a': [2, 'A']}, 'empty': True}), ({'records': [[1, 0, 'c', 0], [1, 1, 'b', 0], [2, 2, 'a', 1]], 'live': {'a': [1, 'A'], 'b': [0, 'B'], 'c': [0, 'C']}}, {'selected': 'c', 'payload': 'C', 'discarded': 0, 'suffix': [[1, 1, 'b', 0], [2, 2, 'a', 1]], 'live_after': {'a': [1, 'A'], 'b': [0, 'B']}, 'empty': False}), ({'records': [[0, -4, 'stale4', 0], [0, -4, 'stale4', 0], [0, -4, 'stale4', 0], [0, -4, 'stale4', 0], [1, 0, 'c', 0], [1, 1, 'b', 0], [2, 2, 'a', 1]], 'live': {'a': [1, 'A'], 'b': [0, 'B'], 'c': [0, 'C']}}, {'selected': 'c', 'payload': 'C', 'discarded': 4, 'suffix': [[1, 1, 'b', 0], [2, 2, 'a', 1]], 'live_after': {'a': [1, 'A'], 'b': [0, 'B']}, 'empty': False})], [({'records': [], 'live': {}}, {'selected': None, 'payload': None, 'discarded': 0, 'suffix': [], 'live_after': {}, 'empty': True}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': [0, 'A']}}, {'selected': 'a', 'payload': 'A', 'discarded': 0, 'suffix': [], 'live_after': {}, 'empty': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1], [3, 2, 'b', 0]], 'live': {'a': [1, 'new'], 'b': [0, 'B']}}, {'selected': 'a', 'payload': 'new', 'discarded': 1, 'suffix': [[3, 2, 'b', 0]], 'live_after': {'b': [0, 'B']}, 'empty': False}), ({'records': [[0, 0, 'x', 2], [1, 1, 'b', 0]], 'live': {'b': [0, 'B']}}, {'selected': 'b', 'payload': 'B', 'discarded': 1, 'suffix': [], 'live_after': {}, 'empty': False}), ({'records': [[1, 0, 'a', 1]], 'live': {'a': [2, 'A']}}, {'selected': None, 'payload': None, 'discarded': 1, 'suffix': [], 'live_after': {'a': [2, 'A']}, 'empty': True}), ({'records': [[1, 0, 'c', 0], [1, 1, 'b', 0], [2, 2, 'a', 1]], 'live': {'a': [1, 'A'], 'b': [0, 'B'], 'c': [0, 'C']}}, {'selected': 'c', 'payload': 'C', 'discarded': 0, 'suffix': [[1, 1, 'b', 0], [2, 2, 'a', 1]], 'live_after': {'a': [1, 'A'], 'b': [0, 'B']}, 'empty': False}), ({'records': [[0, -5, 'stale5', 0], [0, -5, 'stale5', 0], [0, -5, 'stale5', 0], [0, -5, 'stale5', 0], [0, -5, 'stale5', 0], [1, 0, 'c', 0], [1, 1, 'b', 0], [2, 2, 'a', 1]], 'live': {'a': [1, 'A'], 'b': [0, 'B'], 'c': [0, 'C']}}, {'selected': 'c', 'payload': 'C', 'discarded': 5, 'suffix': [[1, 1, 'b', 0], [2, 2, 'a', 1]], 'live_after': {'a': [1, 'A'], 'b': [0, 'B']}, 'empty': False})]][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 lazy pop certificate reports an incorrect empty.

Physical lazy-heap records [priority,serial,id,version] are already sorted lexicographically by priority then serial. Live map id->[version,payload]. Skip missing or version-stale records, pop the first current record, delete its live-map id, and retain the remaining physical suffix. No unindexed priority changes are allowed.

split: open-access


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

N = 1
observations = []
def solve(d):
    q=d['records']; live=d['live']; kept=[x for x in q if x[2] in live and x[3]==live[x[2]]]
    return {'kept': sorted([x for x in q if x[2] in live],key=lambda x:(x[0],x[1])),
    'stale': len(q)-len(kept),
    'duplicate_current': sorted({x[2] for x in kept if sum(y[2]==x[2] for y in kept)>1}),
    'missing': sorted(set(live)-{x[2] for x in kept}),
    'post_size': len(kept),
    'trigger': len(q)>2*len(live)+d["slack"]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 3}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 4}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 5}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 6}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})]][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):
    q=d['records']; live=d['live']; kept=[x for x in q if x[2] in live and x[3]==live[x[2]]]
    return {'kept': sorted(kept,key=lambda x:x[2]),
    'stale': len(q)-len(kept),
    'duplicate_current': sorted({x[2] for x in kept if sum(y[2]==x[2] for y in kept)>1}),
    'missing': sorted(set(live)-{x[2] for x in kept}),
    'post_size': len(kept),
    'trigger': len(q)>2*len(live)+d["slack"]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 3}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 4}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 5}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 6}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})]][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 lazy compaction certificate reports an incorrect kept.

A lazy heap compaction receives arbitrary physical records [priority,serial,id,version] and live map id->version. Preserve only records whose id and version match, retain duplicate physical records for diagnostic detection, heapify by (priority,serial), and report stale count, duplicate-current ids, live-id coverage, storage ratio numerator, and triggering condition physical>2*live+slack.

split: open-access


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

N = 1
observations = []
def solve(d):
    q=d['records']; live=d['live']; kept=[x for x in q if x[2] in live and x[3]==live[x[2]]]
    return {'kept': sorted(kept,key=lambda x:(x[0],x[1])),
    'stale': len(q)-len(live),
    'duplicate_current': sorted({x[2] for x in kept if sum(y[2]==x[2] for y in kept)>1}),
    'missing': sorted(set(live)-{x[2] for x in kept}),
    'post_size': len(kept),
    'trigger': len(q)>2*len(live)+d["slack"]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 3}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 4}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 5}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 6}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})]][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):
    q=d['records']; live=d['live']; kept=[x for x in q if x[2] in live and x[3]==live[x[2]]]
    return {'kept': sorted(kept,key=lambda x:(x[0],x[1])),
    'stale': len(kept),
    'duplicate_current': sorted({x[2] for x in kept if sum(y[2]==x[2] for y in kept)>1}),
    'missing': sorted(set(live)-{x[2] for x in kept}),
    'post_size': len(kept),
    'trigger': len(q)>2*len(live)+d["slack"]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 3}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 4}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 5}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 6}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})]][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 lazy compaction certificate reports an incorrect stale.

A lazy heap compaction receives arbitrary physical records [priority,serial,id,version] and live map id->version. Preserve only records whose id and version match, retain duplicate physical records for diagnostic detection, heapify by (priority,serial), and report stale count, duplicate-current ids, live-id coverage, storage ratio numerator, and triggering condition physical>2*live+slack.

split: open-access


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

N = 1
observations = []
def solve(d):
    q=d['records']; live=d['live']; kept=[x for x in q if x[2] in live and x[3]==live[x[2]]]
    return {'kept': sorted(kept,key=lambda x:(x[0],x[1])),
    'stale': len(q)-len(kept),
    'duplicate_current': sorted({x[2] for x in q if sum(y[2]==x[2] for y in q)>1}),
    'missing': sorted(set(live)-{x[2] for x in kept}),
    'post_size': len(kept),
    'trigger': len(q)>2*len(live)+d["slack"]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 3}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 4}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 5}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 6}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})]][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):
    q=d['records']; live=d['live']; kept=[x for x in q if x[2] in live and x[3]==live[x[2]]]
    return {'kept': sorted(kept,key=lambda x:(x[0],x[1])),
    'stale': len(q)-len(kept),
    'duplicate_current': [],
    'missing': sorted(set(live)-{x[2] for x in kept}),
    'post_size': len(kept),
    'trigger': len(q)>2*len(live)+d["slack"]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 3}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 4}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 5}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 6}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})]][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 lazy compaction certificate reports an incorrect duplicate current.

A lazy heap compaction receives arbitrary physical records [priority,serial,id,version] and live map id->version. Preserve only records whose id and version match, retain duplicate physical records for diagnostic detection, heapify by (priority,serial), and report stale count, duplicate-current ids, live-id coverage, storage ratio numerator, and triggering condition physical>2*live+slack.

split: open-access


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

N = 1
observations = []
def solve(d):
    q=d['records']; live=d['live']; kept=[x for x in q if x[2] in live and x[3]==live[x[2]]]
    return {'kept': sorted(kept,key=lambda x:(x[0],x[1])),
    'stale': len(q)-len(kept),
    'duplicate_current': sorted({x[2] for x in kept if sum(y[2]==x[2] for y in kept)>1}),
    'missing': sorted(set(live)-{x[2] for x in q}),
    'post_size': len(kept),
    'trigger': len(q)>2*len(live)+d["slack"]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 3}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 4}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 5}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 6}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})]][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):
    q=d['records']; live=d['live']; kept=[x for x in q if x[2] in live and x[3]==live[x[2]]]
    return {'kept': sorted(kept,key=lambda x:(x[0],x[1])),
    'stale': len(q)-len(kept),
    'duplicate_current': sorted({x[2] for x in kept if sum(y[2]==x[2] for y in kept)>1}),
    'missing': sorted({x[2] for x in q}-set(live)),
    'post_size': len(kept),
    'trigger': len(q)>2*len(live)+d["slack"]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 3}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 4}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 5}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 6}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})]][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 lazy compaction certificate reports an incorrect missing.

A lazy heap compaction receives arbitrary physical records [priority,serial,id,version] and live map id->version. Preserve only records whose id and version match, retain duplicate physical records for diagnostic detection, heapify by (priority,serial), and report stale count, duplicate-current ids, live-id coverage, storage ratio numerator, and triggering condition physical>2*live+slack.

split: open-access