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

N = 1
observations = []
def solve(d):
    b=d['buckets']; mask=d['mask']; p=d['pop']; actual=sum(1<<i for i,x in enumerate(b) if x); remaining=max(0,len(b[p])-1) if b else 0
    return {'actual_mask': actual,
    'minimum': actual.bit_length()-1 if actual else None,
    'maximum': actual.bit_length()-1 if actual else None,
    'ghosts': [i for i,x in enumerate(b) if mask&(1<<i) and not x],
    'missing': [i for i,x in enumerate(b) if x and not mask&(1<<i)],
    'after_pop': mask if remaining or not b else mask & ~(1<<p)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 1, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [0], 'missing': [1, 3, 4], 'after_pop': 1})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 2, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [3, 4], 'after_pop': 2})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 3, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [0], 'missing': [3, 4], 'after_pop': 3})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 4, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [2], 'missing': [1, 3, 4], 'after_pop': 4})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 5, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [0, 2], 'missing': [1, 3, 4], 'after_pop': 5})]][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):
    b=d['buckets']; mask=d['mask']; p=d['pop']; actual=sum(1<<i for i,x in enumerate(b) if x); remaining=max(0,len(b[p])-1) if b else 0
    return {'actual_mask': actual,
    'minimum': (actual & -actual).bit_length() if actual else None,
    'maximum': actual.bit_length()-1 if actual else None,
    'ghosts': [i for i,x in enumerate(b) if mask&(1<<i) and not x],
    'missing': [i for i,x in enumerate(b) if x and not mask&(1<<i)],
    'after_pop': mask if remaining or not b else mask & ~(1<<p)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 1, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [0], 'missing': [1, 3, 4], 'after_pop': 1})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 2, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [3, 4], 'after_pop': 2})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 3, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [0], 'missing': [3, 4], 'after_pop': 3})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 4, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [2], 'missing': [1, 3, 4], 'after_pop': 4})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 5, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [0, 2], 'missing': [1, 3, 4], 'after_pop': 5})]][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 priority bitset certificate reports an incorrect minimum.

A bounded bucket priority queue certificate supplies occupancy mask and bucket lists for priorities 0..width-1. Report actual occupancy mask, least occupied priority, greatest occupied priority, mask-only ghost priorities, missing-mask priorities, and popped-bucket bit clearing after removing one first element from requested priority. Empty buckets are valid.

split: open-access


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

N = 1
observations = []
def solve(d):
    b=d['buckets']; mask=d['mask']; p=d['pop']; actual=sum(1<<i for i,x in enumerate(b) if x); remaining=max(0,len(b[p])-1) if b else 0
    return {'actual_mask': actual,
    'minimum': (actual & -actual).bit_length()-1 if actual else None,
    'maximum': (actual & -actual).bit_length()-1 if actual else None,
    'ghosts': [i for i,x in enumerate(b) if mask&(1<<i) and not x],
    'missing': [i for i,x in enumerate(b) if x and not mask&(1<<i)],
    'after_pop': mask if remaining or not b else mask & ~(1<<p)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 1, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [0], 'missing': [1, 3, 4], 'after_pop': 1})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 2, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [3, 4], 'after_pop': 2})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 3, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [0], 'missing': [3, 4], 'after_pop': 3})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 4, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [2], 'missing': [1, 3, 4], 'after_pop': 4})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 5, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [0, 2], 'missing': [1, 3, 4], 'after_pop': 5})]][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):
    b=d['buckets']; mask=d['mask']; p=d['pop']; actual=sum(1<<i for i,x in enumerate(b) if x); remaining=max(0,len(b[p])-1) if b else 0
    return {'actual_mask': actual,
    'minimum': (actual & -actual).bit_length()-1 if actual else None,
    'maximum': actual.bit_length() if actual else None,
    'ghosts': [i for i,x in enumerate(b) if mask&(1<<i) and not x],
    'missing': [i for i,x in enumerate(b) if x and not mask&(1<<i)],
    'after_pop': mask if remaining or not b else mask & ~(1<<p)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 1, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [0], 'missing': [1, 3, 4], 'after_pop': 1})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 2, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [3, 4], 'after_pop': 2})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 3, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [0], 'missing': [3, 4], 'after_pop': 3})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 4, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [2], 'missing': [1, 3, 4], 'after_pop': 4})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 5, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [0, 2], 'missing': [1, 3, 4], 'after_pop': 5})]][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 priority bitset certificate reports an incorrect maximum.

A bounded bucket priority queue certificate supplies occupancy mask and bucket lists for priorities 0..width-1. Report actual occupancy mask, least occupied priority, greatest occupied priority, mask-only ghost priorities, missing-mask priorities, and popped-bucket bit clearing after removing one first element from requested priority. Empty buckets are valid.

split: open-access


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

N = 1
observations = []
def solve(d):
    b=d['buckets']; mask=d['mask']; p=d['pop']; actual=sum(1<<i for i,x in enumerate(b) if x); remaining=max(0,len(b[p])-1) if b else 0
    return {'actual_mask': actual,
    'minimum': (actual & -actual).bit_length()-1 if actual else None,
    'maximum': actual.bit_length()-1 if actual else None,
    'ghosts': [i for i,x in enumerate(b) if mask&(1<<i)],
    'missing': [i for i,x in enumerate(b) if x and not mask&(1<<i)],
    'after_pop': mask if remaining or not b else mask & ~(1<<p)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 1, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [0], 'missing': [1, 3, 4], 'after_pop': 1})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 2, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [3, 4], 'after_pop': 2})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 3, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [0], 'missing': [3, 4], 'after_pop': 3})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 4, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [2], 'missing': [1, 3, 4], 'after_pop': 4})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 5, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [0, 2], 'missing': [1, 3, 4], 'after_pop': 5})]][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):
    b=d['buckets']; mask=d['mask']; p=d['pop']; actual=sum(1<<i for i,x in enumerate(b) if x); remaining=max(0,len(b[p])-1) if b else 0
    return {'actual_mask': actual,
    'minimum': (actual & -actual).bit_length()-1 if actual else None,
    'maximum': actual.bit_length()-1 if actual else None,
    'ghosts': [i for i,x in enumerate(b) if not x],
    'missing': [i for i,x in enumerate(b) if x and not mask&(1<<i)],
    'after_pop': mask if remaining or not b else mask & ~(1<<p)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 1, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [0], 'missing': [1, 3, 4], 'after_pop': 1})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 2, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [3, 4], 'after_pop': 2})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 3, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [0], 'missing': [3, 4], 'after_pop': 3})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 4, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [2], 'missing': [1, 3, 4], 'after_pop': 4})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 5, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [0, 2], 'missing': [1, 3, 4], 'after_pop': 5})]][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 priority bitset certificate reports an incorrect ghosts.

A bounded bucket priority queue certificate supplies occupancy mask and bucket lists for priorities 0..width-1. Report actual occupancy mask, least occupied priority, greatest occupied priority, mask-only ghost priorities, missing-mask priorities, and popped-bucket bit clearing after removing one first element from requested priority. Empty buckets are valid.

split: open-access


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

N = 1
observations = []
def solve(d):
    b=d['buckets']; mask=d['mask']; p=d['pop']; actual=sum(1<<i for i,x in enumerate(b) if x); remaining=max(0,len(b[p])-1) if b else 0
    return {'actual_mask': actual,
    'minimum': (actual & -actual).bit_length()-1 if actual else None,
    'maximum': actual.bit_length()-1 if actual else None,
    'ghosts': [i for i,x in enumerate(b) if mask&(1<<i) and not x],
    'missing': [i for i,x in enumerate(b) if x and mask&(1<<i)],
    'after_pop': mask if remaining or not b else mask & ~(1<<p)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 1, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [0], 'missing': [1, 3, 4], 'after_pop': 1})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 2, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [3, 4], 'after_pop': 2})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 3, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [0], 'missing': [3, 4], 'after_pop': 3})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 4, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [2], 'missing': [1, 3, 4], 'after_pop': 4})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 5, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [0, 2], 'missing': [1, 3, 4], 'after_pop': 5})]][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):
    b=d['buckets']; mask=d['mask']; p=d['pop']; actual=sum(1<<i for i,x in enumerate(b) if x); remaining=max(0,len(b[p])-1) if b else 0
    return {'actual_mask': actual,
    'minimum': (actual & -actual).bit_length()-1 if actual else None,
    'maximum': actual.bit_length()-1 if actual else None,
    'ghosts': [i for i,x in enumerate(b) if mask&(1<<i) and not x],
    'missing': [i for i,x in enumerate(b) if not mask&(1<<i)],
    'after_pop': mask if remaining or not b else mask & ~(1<<p)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 1, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [0], 'missing': [1, 3, 4], 'after_pop': 1})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 2, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [3, 4], 'after_pop': 2})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 3, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [0], 'missing': [3, 4], 'after_pop': 3})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 4, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [2], 'missing': [1, 3, 4], 'after_pop': 4})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 5, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [0, 2], 'missing': [1, 3, 4], 'after_pop': 5})]][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 priority bitset certificate reports an incorrect missing.

A bounded bucket priority queue certificate supplies occupancy mask and bucket lists for priorities 0..width-1. Report actual occupancy mask, least occupied priority, greatest occupied priority, mask-only ghost priorities, missing-mask priorities, and popped-bucket bit clearing after removing one first element from requested priority. Empty buckets are valid.

split: open-access


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

N = 1
observations = []
def solve(d):
    b=d['buckets']; mask=d['mask']; p=d['pop']; actual=sum(1<<i for i,x in enumerate(b) if x); remaining=max(0,len(b[p])-1) if b else 0
    return {'actual_mask': actual,
    'minimum': (actual & -actual).bit_length()-1 if actual else None,
    'maximum': actual.bit_length()-1 if actual else None,
    'ghosts': [i for i,x in enumerate(b) if mask&(1<<i) and not x],
    'missing': [i for i,x in enumerate(b) if x and not mask&(1<<i)],
    'after_pop': mask & ~(1<<p) if b else mask}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 1, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [0], 'missing': [1, 3, 4], 'after_pop': 1})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 2, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [3, 4], 'after_pop': 2})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 3, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [0], 'missing': [3, 4], 'after_pop': 3})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 4, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [2], 'missing': [1, 3, 4], 'after_pop': 4})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 5, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [0, 2], 'missing': [1, 3, 4], 'after_pop': 5})]][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):
    b=d['buckets']; mask=d['mask']; p=d['pop']; actual=sum(1<<i for i,x in enumerate(b) if x); remaining=max(0,len(b[p])-1) if b else 0
    return {'actual_mask': actual,
    'minimum': (actual & -actual).bit_length()-1 if actual else None,
    'maximum': actual.bit_length()-1 if actual else None,
    'ghosts': [i for i,x in enumerate(b) if mask&(1<<i) and not x],
    'missing': [i for i,x in enumerate(b) if x and not mask&(1<<i)],
    'after_pop': mask ^ (1<<p) if b else mask}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 1, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [0], 'missing': [1, 3, 4], 'after_pop': 1})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 2, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [3, 4], 'after_pop': 2})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 3, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [0], 'missing': [3, 4], 'after_pop': 3})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 4, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [2], 'missing': [1, 3, 4], 'after_pop': 4})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 5, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [0, 2], 'missing': [1, 3, 4], 'after_pop': 5})]][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 priority bitset certificate reports an incorrect after pop.

A bounded bucket priority queue certificate supplies occupancy mask and bucket lists for priorities 0..width-1. Report actual occupancy mask, least occupied priority, greatest occupied priority, mask-only ghost priorities, missing-mask priorities, and popped-bucket bit clearing after removing one first element from requested priority. Empty buckets are valid.

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]-cursor)%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]<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)

prompt:
The bounded dial window certificate reports an incorrect buckets.

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