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

N = 1
observations = []
def solve(d):
    a=d['entries']; c=d['capacity']; cursor=d['cursor']; active=[x for x in a if cursor<=x[1]<cursor+c]; nxt=min((x[1] for x in active),default=None)
    return {'buckets': [[x[0],x[1]%c] for x in a],
    'expired': [x[0] for x in a if x[1]<=cursor],
    'future': [x[0] for x in a if x[1]>=cursor+c],
    'next': nxt,
    'advance': None if nxt is None else nxt-cursor,
    'active_order': [x[0] for x in sorted(active,key=lambda x:x[1])]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 8, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['c'], 'future': [], 'next': 8, 'advance': 0, 'active_order': ['b', 'a', 'd']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 9, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['b', 'c'], 'future': [], 'next': 9, 'advance': 0, 'active_order': ['a', 'd']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 10, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['a', 'b', 'c'], 'future': [], 'next': 14, 'advance': 4, 'active_order': ['d']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 11, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['a', 'b', 'c'], 'future': [], 'next': 14, 'advance': 3, 'active_order': ['d']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 12, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['a', 'b', 'c'], 'future': [], 'next': 14, 'advance': 2, 'active_order': ['d']})]][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):
    a=d['entries']; c=d['capacity']; cursor=d['cursor']; active=[x for x in a if cursor<=x[1]<cursor+c]; nxt=min((x[1] for x in active),default=None)
    return {'buckets': [[x[0],x[1]%c] for x in a],
    'expired': [x[0] for x in a if x[1]%c<cursor%c],
    'future': [x[0] for x in a if x[1]>=cursor+c],
    'next': nxt,
    'advance': None if nxt is None else nxt-cursor,
    'active_order': [x[0] for x in sorted(active,key=lambda x:x[1])]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 8, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['c'], 'future': [], 'next': 8, 'advance': 0, 'active_order': ['b', 'a', 'd']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 9, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['b', 'c'], 'future': [], 'next': 9, 'advance': 0, 'active_order': ['a', 'd']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 10, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['a', 'b', 'c'], 'future': [], 'next': 14, 'advance': 4, 'active_order': ['d']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 11, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['a', 'b', 'c'], 'future': [], 'next': 14, 'advance': 3, 'active_order': ['d']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 12, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['a', 'b', 'c'], 'future': [], 'next': 14, 'advance': 2, 'active_order': ['d']})]][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 dial window certificate reports an incorrect expired.

A cyclic integer bucket queue with ring size C stores entries [id,absolute_key]. Cursor is last extracted absolute key. Only keys in [cursor,cursor+C) are in the active window. Report physical bucket indices, expired ids, future-window ids, next active key, rotation distance, and active ids in absolute-key order. Same-slot values from later revolutions must not be delivered.

split: open-access


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

N = 1
observations = []
def solve(d):
    a=d['entries']; c=d['capacity']; cursor=d['cursor']; active=[x for x in a if cursor<=x[1]<cursor+c]; nxt=min((x[1] for x in active),default=None)
    return {'buckets': [[x[0],x[1]%c] for x in a],
    'expired': [x[0] for x in a if x[1]<cursor],
    'future': [x[0] for x in a if x[1]>cursor+c],
    'next': nxt,
    'advance': None if nxt is None else nxt-cursor,
    'active_order': [x[0] for x in sorted(active,key=lambda x:x[1])]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 8, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['c'], 'future': [], 'next': 8, 'advance': 0, 'active_order': ['b', 'a', 'd']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 9, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['b', 'c'], 'future': [], 'next': 9, 'advance': 0, 'active_order': ['a', 'd']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 10, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['a', 'b', 'c'], 'future': [], 'next': 14, 'advance': 4, 'active_order': ['d']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 11, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['a', 'b', 'c'], 'future': [], 'next': 14, 'advance': 3, 'active_order': ['d']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 12, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['a', 'b', 'c'], 'future': [], 'next': 14, 'advance': 2, 'active_order': ['d']})]][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):
    a=d['entries']; c=d['capacity']; cursor=d['cursor']; active=[x for x in a if cursor<=x[1]<cursor+c]; nxt=min((x[1] for x in active),default=None)
    return {'buckets': [[x[0],x[1]%c] for x in a],
    'expired': [x[0] for x in a if x[1]<cursor],
    'future': [],
    'next': nxt,
    'advance': None if nxt is None else nxt-cursor,
    'active_order': [x[0] for x in sorted(active,key=lambda x:x[1])]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 8, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['c'], 'future': [], 'next': 8, 'advance': 0, 'active_order': ['b', 'a', 'd']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 9, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['b', 'c'], 'future': [], 'next': 9, 'advance': 0, 'active_order': ['a', 'd']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 10, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['a', 'b', 'c'], 'future': [], 'next': 14, 'advance': 4, 'active_order': ['d']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 11, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['a', 'b', 'c'], 'future': [], 'next': 14, 'advance': 3, 'active_order': ['d']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 12, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['a', 'b', 'c'], 'future': [], 'next': 14, 'advance': 2, 'active_order': ['d']})]][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 dial window certificate reports an incorrect future.

A cyclic integer bucket queue with ring size C stores entries [id,absolute_key]. Cursor is last extracted absolute key. Only keys in [cursor,cursor+C) are in the active window. Report physical bucket indices, expired ids, future-window ids, next active key, rotation distance, and active ids in absolute-key order. Same-slot values from later revolutions must not be delivered.

split: open-access


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

N = 1
observations = []
def solve(d):
    a=d['entries']; c=d['capacity']; cursor=d['cursor']; active=[x for x in a if cursor<=x[1]<cursor+c]; nxt=min((x[1] for x in active),default=None)
    return {'buckets': [[x[0],x[1]%c] for x in a],
    'expired': [x[0] for x in a if x[1]<cursor],
    'future': [x[0] for x in a if x[1]>=cursor+c],
    'next': min((x[1] for x in a),default=None),
    'advance': None if nxt is None else nxt-cursor,
    'active_order': [x[0] for x in sorted(active,key=lambda x:x[1])]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 8, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['c'], 'future': [], 'next': 8, 'advance': 0, 'active_order': ['b', 'a', 'd']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 9, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['b', 'c'], 'future': [], 'next': 9, 'advance': 0, 'active_order': ['a', 'd']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 10, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['a', 'b', 'c'], 'future': [], 'next': 14, 'advance': 4, 'active_order': ['d']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 11, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['a', 'b', 'c'], 'future': [], 'next': 14, 'advance': 3, 'active_order': ['d']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 12, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['a', 'b', 'c'], 'future': [], 'next': 14, 'advance': 2, 'active_order': ['d']})]][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):
    a=d['entries']; c=d['capacity']; cursor=d['cursor']; active=[x for x in a if cursor<=x[1]<cursor+c]; nxt=min((x[1] for x in active),default=None)
    return {'buckets': [[x[0],x[1]%c] for x in a],
    'expired': [x[0] for x in a if x[1]<cursor],
    'future': [x[0] for x in a if x[1]>=cursor+c],
    'next': min((x[1]%c for x in active),default=None),
    'advance': None if nxt is None else nxt-cursor,
    'active_order': [x[0] for x in sorted(active,key=lambda x:x[1])]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 8, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['c'], 'future': [], 'next': 8, 'advance': 0, 'active_order': ['b', 'a', 'd']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 9, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['b', 'c'], 'future': [], 'next': 9, 'advance': 0, 'active_order': ['a', 'd']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 10, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['a', 'b', 'c'], 'future': [], 'next': 14, 'advance': 4, 'active_order': ['d']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 11, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['a', 'b', 'c'], 'future': [], 'next': 14, 'advance': 3, 'active_order': ['d']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 12, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['a', 'b', 'c'], 'future': [], 'next': 14, 'advance': 2, 'active_order': ['d']})]][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 dial window certificate reports an incorrect next.

A cyclic integer bucket queue with ring size C stores entries [id,absolute_key]. Cursor is last extracted absolute key. Only keys in [cursor,cursor+C) are in the active window. Report physical bucket indices, expired ids, future-window ids, next active key, rotation distance, and active ids in absolute-key order. Same-slot values from later revolutions must not be delivered.

split: open-access


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

N = 1
observations = []
def solve(d):
    a=d['entries']; c=d['capacity']; cursor=d['cursor']; active=[x for x in a if cursor<=x[1]<cursor+c]; nxt=min((x[1] for x in active),default=None)
    return {'buckets': [[x[0],x[1]%c] for x in a],
    'expired': [x[0] for x in a if x[1]<cursor],
    'future': [x[0] for x in a if x[1]>=cursor+c],
    'next': nxt,
    'advance': None if nxt is None else (nxt%c)-(cursor%c),
    'active_order': [x[0] for x in sorted(active,key=lambda x:x[1])]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 8, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['c'], 'future': [], 'next': 8, 'advance': 0, 'active_order': ['b', 'a', 'd']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 9, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['b', 'c'], 'future': [], 'next': 9, 'advance': 0, 'active_order': ['a', 'd']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 10, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['a', 'b', 'c'], 'future': [], 'next': 14, 'advance': 4, 'active_order': ['d']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 11, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['a', 'b', 'c'], 'future': [], 'next': 14, 'advance': 3, 'active_order': ['d']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 12, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['a', 'b', 'c'], 'future': [], 'next': 14, 'advance': 2, 'active_order': ['d']})]][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):
    a=d['entries']; c=d['capacity']; cursor=d['cursor']; active=[x for x in a if cursor<=x[1]<cursor+c]; nxt=min((x[1] for x in active),default=None)
    return {'buckets': [[x[0],x[1]%c] for x in a],
    'expired': [x[0] for x in a if x[1]<cursor],
    'future': [x[0] for x in a if x[1]>=cursor+c],
    'next': nxt,
    'advance': 0 if nxt is None else nxt-cursor,
    'active_order': [x[0] for x in sorted(active,key=lambda x:x[1])]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 8, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['c'], 'future': [], 'next': 8, 'advance': 0, 'active_order': ['b', 'a', 'd']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 9, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['b', 'c'], 'future': [], 'next': 9, 'advance': 0, 'active_order': ['a', 'd']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 10, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['a', 'b', 'c'], 'future': [], 'next': 14, 'advance': 4, 'active_order': ['d']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 11, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['a', 'b', 'c'], 'future': [], 'next': 14, 'advance': 3, 'active_order': ['d']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 12, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['a', 'b', 'c'], 'future': [], 'next': 14, 'advance': 2, 'active_order': ['d']})]][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 dial window certificate reports an incorrect advance.

A cyclic integer bucket queue with ring size C stores entries [id,absolute_key]. Cursor is last extracted absolute key. Only keys in [cursor,cursor+C) are in the active window. Report physical bucket indices, expired ids, future-window ids, next active key, rotation distance, and active ids in absolute-key order. Same-slot values from later revolutions must not be delivered.

split: open-access


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

N = 1
observations = []
def solve(d):
    a=d['entries']; c=d['capacity']; cursor=d['cursor']; active=[x for x in a if cursor<=x[1]<cursor+c]; nxt=min((x[1] for x in active),default=None)
    return {'buckets': [[x[0],x[1]%c] for x in a],
    'expired': [x[0] for x in a if x[1]<cursor],
    'future': [x[0] for x in a if x[1]>=cursor+c],
    'next': nxt,
    'advance': None if nxt is None else nxt-cursor,
    'active_order': [x[0] for x in sorted(a,key=lambda x:x[1]%c)]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 8, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['c'], 'future': [], 'next': 8, 'advance': 0, 'active_order': ['b', 'a', 'd']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 9, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['b', 'c'], 'future': [], 'next': 9, 'advance': 0, 'active_order': ['a', 'd']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 10, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['a', 'b', 'c'], 'future': [], 'next': 14, 'advance': 4, 'active_order': ['d']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 11, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['a', 'b', 'c'], 'future': [], 'next': 14, 'advance': 3, 'active_order': ['d']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 12, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['a', 'b', 'c'], 'future': [], 'next': 14, 'advance': 2, 'active_order': ['d']})]][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):
    a=d['entries']; c=d['capacity']; cursor=d['cursor']; active=[x for x in a if cursor<=x[1]<cursor+c]; nxt=min((x[1] for x in active),default=None)
    return {'buckets': [[x[0],x[1]%c] for x in a],
    'expired': [x[0] for x in a if x[1]<cursor],
    'future': [x[0] for x in a if x[1]>=cursor+c],
    'next': nxt,
    'advance': None if nxt is None else nxt-cursor,
    'active_order': [x[0] for x in active]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 8, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['c'], 'future': [], 'next': 8, 'advance': 0, 'active_order': ['b', 'a', 'd']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 9, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['b', 'c'], 'future': [], 'next': 9, 'advance': 0, 'active_order': ['a', 'd']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 10, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['a', 'b', 'c'], 'future': [], 'next': 14, 'advance': 4, 'active_order': ['d']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 11, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['a', 'b', 'c'], 'future': [], 'next': 14, 'advance': 3, 'active_order': ['d']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 12, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['a', 'b', 'c'], 'future': [], 'next': 14, 'advance': 2, 'active_order': ['d']})]][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 dial window certificate reports an incorrect active order.

A cyclic integer bucket queue with ring size C stores entries [id,absolute_key]. Cursor is last extracted absolute key. Only keys in [cursor,cursor+C) are in the active window. Report physical bucket indices, expired ids, future-window ids, next active key, rotation distance, and active ids in absolute-key order. Same-slot values from later revolutions must not be delivered.

split: open-access


prompt:
The bounded calendar placement certificate reports an incorrect virtual.

A calendar priority queue uses integer tick origin O, positive bucket width W, and B buckets. Events [id,tick] map to virtual bucket floor((tick-O)/W), then physical index modulo B, with absolute interval boundaries retained. Report virtual and physical placements, lower and upper bounds, same-cycle eligibility relative to cursor virtual bucket, and exact-boundary events.

split: open-access


prompt:
The bounded calendar placement certificate reports an incorrect physical.

A calendar priority queue uses integer tick origin O, positive bucket width W, and B buckets. Events [id,tick] map to virtual bucket floor((tick-O)/W), then physical index modulo B, with absolute interval boundaries retained. Report virtual and physical placements, lower and upper bounds, same-cycle eligibility relative to cursor virtual bucket, and exact-boundary events.

split: open-access


prompt:
The bounded calendar placement certificate reports an incorrect lower bounds.

A calendar priority queue uses integer tick origin O, positive bucket width W, and B buckets. Events [id,tick] map to virtual bucket floor((tick-O)/W), then physical index modulo B, with absolute interval boundaries retained. Report virtual and physical placements, lower and upper bounds, same-cycle eligibility relative to cursor virtual bucket, and exact-boundary events.

split: open-access


prompt:
The bounded calendar placement certificate reports an incorrect upper bounds.

A calendar priority queue uses integer tick origin O, positive bucket width W, and B buckets. Events [id,tick] map to virtual bucket floor((tick-O)/W), then physical index modulo B, with absolute interval boundaries retained. Report virtual and physical placements, lower and upper bounds, same-cycle eligibility relative to cursor virtual bucket, and exact-boundary events.

split: open-access


prompt:
The bounded calendar placement certificate reports an incorrect cycle eligible.

A calendar priority queue uses integer tick origin O, positive bucket width W, and B buckets. Events [id,tick] map to virtual bucket floor((tick-O)/W), then physical index modulo B, with absolute interval boundaries retained. Report virtual and physical placements, lower and upper bounds, same-cycle eligibility relative to cursor virtual bucket, and exact-boundary events.

split: open-access


prompt:
The bounded calendar placement certificate reports an incorrect boundaries.

A calendar priority queue uses integer tick origin O, positive bucket width W, and B buckets. Events [id,tick] map to virtual bucket floor((tick-O)/W), then physical index modulo B, with absolute interval boundaries retained. Report virtual and physical placements, lower and upper bounds, same-cycle eligibility relative to cursor virtual bucket, and exact-boundary events.

split: open-access


prompt:
The bounded calendar rehash certificate reports an incorrect buckets.

Calendar queue resize receives events [id,tick], origin, old width/count and new width/count. Reinsert every event using new floor-divided virtual position; preserve arrival order within each destination. Report new bucket contents, moved ids, old aliases split by resize, occupancy, new interval span, and member count.

split: open-access


prompt:
The bounded calendar rehash certificate reports an incorrect moved.

Calendar queue resize receives events [id,tick], origin, old width/count and new width/count. Reinsert every event using new floor-divided virtual position; preserve arrival order within each destination. Report new bucket contents, moved ids, old aliases split by resize, occupancy, new interval span, and member count.

split: open-access


prompt:
The bounded calendar rehash certificate reports an incorrect split aliases.

Calendar queue resize receives events [id,tick], origin, old width/count and new width/count. Reinsert every event using new floor-divided virtual position; preserve arrival order within each destination. Report new bucket contents, moved ids, old aliases split by resize, occupancy, new interval span, and member count.

split: open-access


prompt:
The bounded calendar rehash certificate reports an incorrect occupancy.

Calendar queue resize receives events [id,tick], origin, old width/count and new width/count. Reinsert every event using new floor-divided virtual position; preserve arrival order within each destination. Report new bucket contents, moved ids, old aliases split by resize, occupancy, new interval span, and member count.

split: open-access


prompt:
The bounded calendar rehash certificate reports an incorrect cycle span.

Calendar queue resize receives events [id,tick], origin, old width/count and new width/count. Reinsert every event using new floor-divided virtual position; preserve arrival order within each destination. Report new bucket contents, moved ids, old aliases split by resize, occupancy, new interval span, and member count.

split: open-access


prompt:
The bounded calendar rehash certificate reports an incorrect members.

Calendar queue resize receives events [id,tick], origin, old width/count and new width/count. Reinsert every event using new floor-divided virtual position; preserve arrival order within each destination. Report new bucket contents, moved ids, old aliases split by resize, occupancy, new interval span, and member count.

split: open-access