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)+len(b),
    'writes': len(h)+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(h)+len(b),
    'writes': cap 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 writes.

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):
    runs=d['runs']; offsets=d['offsets']; r=d['pop_run']; out=list(offsets); value=runs[r][out[r]]; out[r]+=1; heads=sorted([[runs[i][k],i] for i,k in enumerate(out) if k<len(runs[i])])
    return {'emitted': runs[r][0],
    'offsets': out,
    'heads': heads,
    'exhausted': [i for i,k in enumerate(out) if k==len(runs[i])],
    'remaining': sum(len(x)-k for x,k in zip(runs,out)),
    'next_run': heads[0][1] if heads else None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 4], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 4, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 5], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 5, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 6], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 6, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 7], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 7, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 8], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 8, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})]][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):
    runs=d['runs']; offsets=d['offsets']; r=d['pop_run']; out=list(offsets); value=runs[r][out[r]]; out[r]+=1; heads=sorted([[runs[i][k],i] for i,k in enumerate(out) if k<len(runs[i])])
    return {'emitted': r,
    'offsets': out,
    'heads': heads,
    'exhausted': [i for i,k in enumerate(out) if k==len(runs[i])],
    'remaining': sum(len(x)-k for x,k in zip(runs,out)),
    'next_run': heads[0][1] if heads else None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 4], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 4, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 5], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 5, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 6], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 6, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 7], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 7, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 8], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 8, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})]][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 run frontier certificate reports an incorrect emitted.

A k-way heap merge frontier stores one cursor per sorted run. A frontier item identifies run r and its current offset. Pop run r current item, advance only its offset, omit exhausted runs, and report next head candidates sorted by (value,run). Return emitted value, cursor vector, heads, exhausted runs, remaining item count, and next run.

split: open-access


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

N = 1
observations = []
def solve(d):
    runs=d['runs']; offsets=d['offsets']; r=d['pop_run']; out=list(offsets); value=runs[r][out[r]]; out[r]+=1; heads=sorted([[runs[i][k],i] for i,k in enumerate(out) if k<len(runs[i])])
    return {'emitted': value,
    'offsets': [x+1 for x in offsets],
    'heads': heads,
    'exhausted': [i for i,k in enumerate(out) if k==len(runs[i])],
    'remaining': sum(len(x)-k for x,k in zip(runs,out)),
    'next_run': heads[0][1] if heads else None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 4], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 4, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 5], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 5, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 6], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 6, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 7], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 7, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 8], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 8, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})]][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):
    runs=d['runs']; offsets=d['offsets']; r=d['pop_run']; out=list(offsets); value=runs[r][out[r]]; out[r]+=1; heads=sorted([[runs[i][k],i] for i,k in enumerate(out) if k<len(runs[i])])
    return {'emitted': value,
    'offsets': offsets,
    'heads': heads,
    'exhausted': [i for i,k in enumerate(out) if k==len(runs[i])],
    'remaining': sum(len(x)-k for x,k in zip(runs,out)),
    'next_run': heads[0][1] if heads else None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 4], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 4, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 5], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 5, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 6], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 6, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 7], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 7, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 8], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 8, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})]][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 run frontier certificate reports an incorrect offsets.

A k-way heap merge frontier stores one cursor per sorted run. A frontier item identifies run r and its current offset. Pop run r current item, advance only its offset, omit exhausted runs, and report next head candidates sorted by (value,run). Return emitted value, cursor vector, heads, exhausted runs, remaining item count, and next run.

split: open-access


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

N = 1
observations = []
def solve(d):
    runs=d['runs']; offsets=d['offsets']; r=d['pop_run']; out=list(offsets); value=runs[r][out[r]]; out[r]+=1; heads=sorted([[runs[i][k],i] for i,k in enumerate(out) if k<len(runs[i])])
    return {'emitted': value,
    'offsets': out,
    'heads': sorted([[runs[i][0],i] for i,k in enumerate(out) if k<len(runs[i])]),
    'exhausted': [i for i,k in enumerate(out) if k==len(runs[i])],
    'remaining': sum(len(x)-k for x,k in zip(runs,out)),
    'next_run': heads[0][1] if heads else None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 4], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 4, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 5], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 5, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 6], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 6, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 7], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 7, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 8], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 8, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})]][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):
    runs=d['runs']; offsets=d['offsets']; r=d['pop_run']; out=list(offsets); value=runs[r][out[r]]; out[r]+=1; heads=sorted([[runs[i][k],i] for i,k in enumerate(out) if k<len(runs[i])])
    return {'emitted': value,
    'offsets': out,
    'heads': sorted([[runs[i][k],i] for i,k in enumerate(offsets) if k<len(runs[i])]),
    'exhausted': [i for i,k in enumerate(out) if k==len(runs[i])],
    'remaining': sum(len(x)-k for x,k in zip(runs,out)),
    'next_run': heads[0][1] if heads else None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 4], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 4, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 5], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 5, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 6], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 6, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 7], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 7, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 8], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 8, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})]][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 run frontier certificate reports an incorrect heads.

A k-way heap merge frontier stores one cursor per sorted run. A frontier item identifies run r and its current offset. Pop run r current item, advance only its offset, omit exhausted runs, and report next head candidates sorted by (value,run). Return emitted value, cursor vector, heads, exhausted runs, remaining item count, and next run.

split: open-access


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

N = 1
observations = []
def solve(d):
    runs=d['runs']; offsets=d['offsets']; r=d['pop_run']; out=list(offsets); value=runs[r][out[r]]; out[r]+=1; heads=sorted([[runs[i][k],i] for i,k in enumerate(out) if k<len(runs[i])])
    return {'emitted': value,
    'offsets': out,
    'heads': heads,
    'exhausted': [i for i,k in enumerate(out) if k>len(runs[i])],
    'remaining': sum(len(x)-k for x,k in zip(runs,out)),
    'next_run': heads[0][1] if heads else None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 4], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 4, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 5], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 5, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 6], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 6, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 7], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 7, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 8], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 8, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})]][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):
    runs=d['runs']; offsets=d['offsets']; r=d['pop_run']; out=list(offsets); value=runs[r][out[r]]; out[r]+=1; heads=sorted([[runs[i][k],i] for i,k in enumerate(out) if k<len(runs[i])])
    return {'emitted': value,
    'offsets': out,
    'heads': heads,
    'exhausted': [i for i,x in enumerate(runs) if not x],
    'remaining': sum(len(x)-k for x,k in zip(runs,out)),
    'next_run': heads[0][1] if heads else None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 4], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 4, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 5], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 5, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 6], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 6, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 7], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 7, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 8], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 8, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})]][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 run frontier certificate reports an incorrect exhausted.

A k-way heap merge frontier stores one cursor per sorted run. A frontier item identifies run r and its current offset. Pop run r current item, advance only its offset, omit exhausted runs, and report next head candidates sorted by (value,run). Return emitted value, cursor vector, heads, exhausted runs, remaining item count, and next run.

split: open-access


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

N = 1
observations = []
def solve(d):
    runs=d['runs']; offsets=d['offsets']; r=d['pop_run']; out=list(offsets); value=runs[r][out[r]]; out[r]+=1; heads=sorted([[runs[i][k],i] for i,k in enumerate(out) if k<len(runs[i])])
    return {'emitted': value,
    'offsets': out,
    'heads': heads,
    'exhausted': [i for i,k in enumerate(out) if k==len(runs[i])],
    'remaining': sum(len(x) for x in runs)-1,
    'next_run': heads[0][1] if heads else None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 4], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 4, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 5], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 5, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 6], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 6, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 7], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 7, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 8], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 8, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})]][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):
    runs=d['runs']; offsets=d['offsets']; r=d['pop_run']; out=list(offsets); value=runs[r][out[r]]; out[r]+=1; heads=sorted([[runs[i][k],i] for i,k in enumerate(out) if k<len(runs[i])])
    return {'emitted': value,
    'offsets': out,
    'heads': heads,
    'exhausted': [i for i,k in enumerate(out) if k==len(runs[i])],
    'remaining': sum(len(x)-k for x,k in zip(runs,offsets)),
    'next_run': heads[0][1] if heads else None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 4], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 4, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 5], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 5, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 6], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 6, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 7], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 7, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 8], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 8, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})]][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 run frontier certificate reports an incorrect remaining.

A k-way heap merge frontier stores one cursor per sorted run. A frontier item identifies run r and its current offset. Pop run r current item, advance only its offset, omit exhausted runs, and report next head candidates sorted by (value,run). Return emitted value, cursor vector, heads, exhausted runs, remaining item count, and next run.

split: open-access