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

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

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

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

prompt:
The bounded replacement selection certificate reports an incorrect run ended.

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

split: open-access


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

N = 1
observations = []
def solve(d):
    h=d['heap']; b=d['buffer']; cap=d['capacity']; flush=len(b)>=cap; merged=sorted(h+b,key=lambda x:(x[1],x[0]))
    return {'trigger': len(b)>cap,
    'resident': merged if flush else h,
    'buffer': [] if flush else b,
    'minimum': merged[0][1] if merged else None,
    'size': len(h)+len(b),
    'writes': len(b) if flush else 0}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['a', 1], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 3, 'writes': 2})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 4, 'writes': 3})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1], ['102', 2]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['102', 2], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 5, 'writes': 4})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1], ['102', 2], ['103', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['102', 2], ['103', 3], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 6, 'writes': 5})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1], ['102', 2], ['103', 3], ['104', 4]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['102', 2], ['103', 3], ['b', 3], ['104', 4]], 'buffer': [], 'minimum': 0, 'size': 7, 'writes': 6})]][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):
    h=d['heap']; b=d['buffer']; cap=d['capacity']; flush=len(b)>=cap; merged=sorted(h+b,key=lambda x:(x[1],x[0]))
    return {'trigger': len(h)+len(b)>=cap,
    'resident': merged if flush else h,
    'buffer': [] if flush else b,
    'minimum': merged[0][1] if merged else None,
    'size': len(h)+len(b),
    'writes': len(b) if flush else 0}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['a', 1], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 3, 'writes': 2})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 4, 'writes': 3})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1], ['102', 2]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['102', 2], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 5, 'writes': 4})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1], ['102', 2], ['103', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['102', 2], ['103', 3], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 6, 'writes': 5})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1], ['102', 2], ['103', 3], ['104', 4]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['102', 2], ['103', 3], ['b', 3], ['104', 4]], 'buffer': [], 'minimum': 0, 'size': 7, 'writes': 6})]][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 buffered flush certificate reports an incorrect trigger.

A buffered priority heap has sorted resident entries [id,key] and unsorted insertion buffer of unique ids disjoint from residents. Flush only when buffer length reaches capacity; then merge all records ordered by key then id. Report triggering flag, resident after flush, buffer after flush, visible minimum across both tiers, logical size, and write count of promoted buffer entries.

split: open-access


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

N = 1
observations = []
def solve(d):
    h=d['heap']; b=d['buffer']; cap=d['capacity']; flush=len(b)>=cap; merged=sorted(h+b,key=lambda x:(x[1],x[0]))
    return {'trigger': flush,
    'resident': h+sorted(b,key=lambda x:x[1]) if flush else h,
    'buffer': [] if flush else b,
    'minimum': merged[0][1] if merged else None,
    'size': len(h)+len(b),
    'writes': len(b) if flush else 0}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['a', 1], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 3, 'writes': 2})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 4, 'writes': 3})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1], ['102', 2]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['102', 2], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 5, 'writes': 4})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1], ['102', 2], ['103', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['102', 2], ['103', 3], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 6, 'writes': 5})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1], ['102', 2], ['103', 3], ['104', 4]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['102', 2], ['103', 3], ['b', 3], ['104', 4]], 'buffer': [], 'minimum': 0, 'size': 7, 'writes': 6})]][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):
    h=d['heap']; b=d['buffer']; cap=d['capacity']; flush=len(b)>=cap; merged=sorted(h+b,key=lambda x:(x[1],x[0]))
    return {'trigger': flush,
    'resident': sorted(h+b,key=lambda x:x[1]) if flush else h,
    'buffer': [] if flush else b,
    'minimum': merged[0][1] if merged else None,
    'size': len(h)+len(b),
    'writes': len(b) if flush else 0}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['a', 1], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 3, 'writes': 2})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 4, 'writes': 3})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1], ['102', 2]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['102', 2], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 5, 'writes': 4})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1], ['102', 2], ['103', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['102', 2], ['103', 3], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 6, 'writes': 5})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1], ['102', 2], ['103', 3], ['104', 4]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['102', 2], ['103', 3], ['b', 3], ['104', 4]], 'buffer': [], 'minimum': 0, 'size': 7, 'writes': 6})]][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 buffered flush certificate reports an incorrect resident.

A buffered priority heap has sorted resident entries [id,key] and unsorted insertion buffer of unique ids disjoint from residents. Flush only when buffer length reaches capacity; then merge all records ordered by key then id. Report triggering flag, resident after flush, buffer after flush, visible minimum across both tiers, logical size, and write count of promoted buffer entries.

split: open-access


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

N = 1
observations = []
def solve(d):
    h=d['heap']; b=d['buffer']; cap=d['capacity']; flush=len(b)>=cap; merged=sorted(h+b,key=lambda x:(x[1],x[0]))
    return {'trigger': flush,
    'resident': merged if flush else h,
    'buffer': b,
    'minimum': merged[0][1] if merged else None,
    'size': len(h)+len(b),
    'writes': len(b) if flush else 0}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['a', 1], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 3, 'writes': 2})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 4, 'writes': 3})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1], ['102', 2]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['102', 2], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 5, 'writes': 4})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1], ['102', 2], ['103', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['102', 2], ['103', 3], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 6, 'writes': 5})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1], ['102', 2], ['103', 3], ['104', 4]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['102', 2], ['103', 3], ['b', 3], ['104', 4]], 'buffer': [], 'minimum': 0, 'size': 7, 'writes': 6})]][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):
    h=d['heap']; b=d['buffer']; cap=d['capacity']; flush=len(b)>=cap; merged=sorted(h+b,key=lambda x:(x[1],x[0]))
    return {'trigger': flush,
    'resident': merged if flush else h,
    'buffer': [],
    'minimum': merged[0][1] if merged else None,
    'size': len(h)+len(b),
    'writes': len(b) if flush else 0}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['a', 1], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 3, 'writes': 2})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 4, 'writes': 3})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1], ['102', 2]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['102', 2], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 5, 'writes': 4})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1], ['102', 2], ['103', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['102', 2], ['103', 3], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 6, 'writes': 5})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1], ['102', 2], ['103', 3], ['104', 4]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['102', 2], ['103', 3], ['b', 3], ['104', 4]], 'buffer': [], 'minimum': 0, 'size': 7, 'writes': 6})]][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 buffered flush certificate reports an incorrect buffer.

A buffered priority heap has sorted resident entries [id,key] and unsorted insertion buffer of unique ids disjoint from residents. Flush only when buffer length reaches capacity; then merge all records ordered by key then id. Report triggering flag, resident after flush, buffer after flush, visible minimum across both tiers, logical size, and write count of promoted buffer entries.

split: open-access


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

N = 1
observations = []
def solve(d):
    h=d['heap']; b=d['buffer']; cap=d['capacity']; flush=len(b)>=cap; merged=sorted(h+b,key=lambda x:(x[1],x[0]))
    return {'trigger': flush,
    'resident': merged if flush else h,
    'buffer': [] if flush else b,
    'minimum': h[0][1] if h else None,
    'size': len(h)+len(b),
    'writes': len(b) if flush else 0}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['a', 1], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 3, 'writes': 2})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 4, 'writes': 3})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1], ['102', 2]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['102', 2], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 5, 'writes': 4})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1], ['102', 2], ['103', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['102', 2], ['103', 3], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 6, 'writes': 5})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1], ['102', 2], ['103', 3], ['104', 4]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['102', 2], ['103', 3], ['b', 3], ['104', 4]], 'buffer': [], 'minimum': 0, 'size': 7, 'writes': 6})]][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):
    h=d['heap']; b=d['buffer']; cap=d['capacity']; flush=len(b)>=cap; merged=sorted(h+b,key=lambda x:(x[1],x[0]))
    return {'trigger': flush,
    'resident': merged if flush else h,
    'buffer': [] if flush else b,
    'minimum': b[0][1] if b else h[0][1] if h else None,
    'size': len(h)+len(b),
    'writes': len(b) if flush else 0}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['a', 1], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 3, 'writes': 2})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 4, 'writes': 3})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1], ['102', 2]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['102', 2], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 5, 'writes': 4})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1], ['102', 2], ['103', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['102', 2], ['103', 3], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 6, 'writes': 5})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1], ['102', 2], ['103', 3], ['104', 4]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['102', 2], ['103', 3], ['b', 3], ['104', 4]], 'buffer': [], 'minimum': 0, 'size': 7, 'writes': 6})]][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 buffered flush certificate reports an incorrect minimum.

A buffered priority heap has sorted resident entries [id,key] and unsorted insertion buffer of unique ids disjoint from residents. Flush only when buffer length reaches capacity; then merge all records ordered by key then id. Report triggering flag, resident after flush, buffer after flush, visible minimum across both tiers, logical size, and write count of promoted buffer entries.

split: open-access


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

N = 1
observations = []
def solve(d):
    h=d['heap']; b=d['buffer']; cap=d['capacity']; flush=len(b)>=cap; merged=sorted(h+b,key=lambda x:(x[1],x[0]))
    return {'trigger': flush,
    'resident': merged if flush else h,
    'buffer': [] if flush else b,
    'minimum': merged[0][1] if merged else None,
    'size': len(h),
    'writes': len(b) if flush else 0}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['a', 1], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 3, 'writes': 2})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 4, 'writes': 3})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1], ['102', 2]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['102', 2], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 5, 'writes': 4})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1], ['102', 2], ['103', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['102', 2], ['103', 3], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 6, 'writes': 5})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1], ['102', 2], ['103', 3], ['104', 4]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['102', 2], ['103', 3], ['b', 3], ['104', 4]], 'buffer': [], 'minimum': 0, 'size': 7, 'writes': 6})]][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):
    h=d['heap']; b=d['buffer']; cap=d['capacity']; flush=len(b)>=cap; merged=sorted(h+b,key=lambda x:(x[1],x[0]))
    return {'trigger': flush,
    'resident': merged if flush else h,
    'buffer': [] if flush else b,
    'minimum': merged[0][1] if merged else None,
    'size': len(merged)+len(b) if flush else len(h)+len(b),
    'writes': len(b) if flush else 0}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['a', 1], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 3, 'writes': 2})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 4, 'writes': 3})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1], ['102', 2]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['102', 2], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 5, 'writes': 4})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1], ['102', 2], ['103', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['102', 2], ['103', 3], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 6, 'writes': 5})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1], ['102', 2], ['103', 3], ['104', 4]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['102', 2], ['103', 3], ['b', 3], ['104', 4]], 'buffer': [], 'minimum': 0, 'size': 7, 'writes': 6})]][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 buffered flush certificate reports an incorrect size.

A buffered priority heap has sorted resident entries [id,key] and unsorted insertion buffer of unique ids disjoint from residents. Flush only when buffer length reaches capacity; then merge all records ordered by key then id. Report triggering flag, resident after flush, buffer after flush, visible minimum across both tiers, logical size, and write count of promoted buffer entries.

split: open-access