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

N = 1
observations = []
def solve(d):
    last=d['last']; entries=d['entries']; width=d['width']
    return {'monotone': [x[1] for x in entries if x[0]<=last],
    'placement': [x[1] for x in entries if x[2]!=(x[0]^last).bit_length()],
    'zero_members': [x[1] for x in entries if x[0]==last],
    'next_bucket': min([x[2] for x in entries if x[2]>0],default=None),
    'new_last': min([x[0] for x in entries],default=last),
    'overflow': [x[1] for x in entries if x[0]>=2**width]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [16, 'variant', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})], [({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [32, 'variant', 6]], 'width': 5}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})], [({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [64, 'variant', 7]], 'width': 6}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})], [({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [128, 'variant', 8]], 'width': 7}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})], [({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [256, 'variant', 9]], 'width': 8}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

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

N = 1
observations = []
def solve(d):
    last=d['last']; entries=d['entries']; width=d['width']
    return {'monotone': [x[1] for x in entries if x[0]<0],
    'placement': [x[1] for x in entries if x[2]!=(x[0]^last).bit_length()],
    'zero_members': [x[1] for x in entries if x[0]==last],
    'next_bucket': min([x[2] for x in entries if x[2]>0],default=None),
    'new_last': min([x[0] for x in entries],default=last),
    'overflow': [x[1] for x in entries if x[0]>=2**width]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [16, 'variant', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})], [({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [32, 'variant', 6]], 'width': 5}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})], [({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [64, 'variant', 7]], 'width': 6}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})], [({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [128, 'variant', 8]], 'width': 7}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})], [({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [256, 'variant', 9]], 'width': 8}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})]][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 radix buckets certificate reports an incorrect monotone.

A monotone integer radix-heap certificate has nonnegative last, entries [key,id,bucket], and width. Bucket index is bit_length(key XOR last). Report monotonicity violations, bucket assignment violations, zero-bucket members, next nonempty bucket, next extraction threshold, and overflow keys. This is an unsigned bounded toy representation.

split: open-access


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

N = 1
observations = []
def solve(d):
    last=d['last']; entries=d['entries']; width=d['width']
    return {'monotone': [x[1] for x in entries if x[0]<last],
    'placement': [x[1] for x in entries if x[2]!=(x[0]-last).bit_length()],
    'zero_members': [x[1] for x in entries if x[0]==last],
    'next_bucket': min([x[2] for x in entries if x[2]>0],default=None),
    'new_last': min([x[0] for x in entries],default=last),
    'overflow': [x[1] for x in entries if x[0]>=2**width]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [16, 'variant', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})], [({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [32, 'variant', 6]], 'width': 5}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})], [({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [64, 'variant', 7]], 'width': 6}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})], [({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [128, 'variant', 8]], 'width': 7}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})], [({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [256, 'variant', 9]], 'width': 8}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})]][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):
    last=d['last']; entries=d['entries']; width=d['width']
    return {'monotone': [x[1] for x in entries if x[0]<last],
    'placement': [x[1] for x in entries if x[2]!=x[0].bit_length()],
    'zero_members': [x[1] for x in entries if x[0]==last],
    'next_bucket': min([x[2] for x in entries if x[2]>0],default=None),
    'new_last': min([x[0] for x in entries],default=last),
    'overflow': [x[1] for x in entries if x[0]>=2**width]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [16, 'variant', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})], [({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [32, 'variant', 6]], 'width': 5}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})], [({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [64, 'variant', 7]], 'width': 6}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})], [({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [128, 'variant', 8]], 'width': 7}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})], [({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [256, 'variant', 9]], 'width': 8}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})]][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 radix buckets certificate reports an incorrect placement.

A monotone integer radix-heap certificate has nonnegative last, entries [key,id,bucket], and width. Bucket index is bit_length(key XOR last). Report monotonicity violations, bucket assignment violations, zero-bucket members, next nonempty bucket, next extraction threshold, and overflow keys. This is an unsigned bounded toy representation.

split: open-access


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

N = 1
observations = []
def solve(d):
    last=d['last']; entries=d['entries']; width=d['width']
    return {'monotone': [x[1] for x in entries if x[0]<last],
    'placement': [x[1] for x in entries if x[2]!=(x[0]^last).bit_length()],
    'zero_members': [x[1] for x in entries if (x[0]^last).bit_length()<=1],
    'next_bucket': min([x[2] for x in entries if x[2]>0],default=None),
    'new_last': min([x[0] for x in entries],default=last),
    'overflow': [x[1] for x in entries if x[0]>=2**width]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [16, 'variant', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})], [({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [32, 'variant', 6]], 'width': 5}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})], [({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [64, 'variant', 7]], 'width': 6}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})], [({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [128, 'variant', 8]], 'width': 7}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})], [({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [256, 'variant', 9]], 'width': 8}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

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

N = 1
observations = []
def solve(d):
    last=d['last']; entries=d['entries']; width=d['width']
    return {'monotone': [x[1] for x in entries if x[0]<last],
    'placement': [x[1] for x in entries if x[2]!=(x[0]^last).bit_length()],
    'zero_members': [x[1] for x in entries if x[0]==0],
    'next_bucket': min([x[2] for x in entries if x[2]>0],default=None),
    'new_last': min([x[0] for x in entries],default=last),
    'overflow': [x[1] for x in entries if x[0]>=2**width]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [16, 'variant', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})], [({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [32, 'variant', 6]], 'width': 5}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})], [({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [64, 'variant', 7]], 'width': 6}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})], [({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [128, 'variant', 8]], 'width': 7}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})], [({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [256, 'variant', 9]], 'width': 8}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})]][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 radix buckets certificate reports an incorrect zero members.

A monotone integer radix-heap certificate has nonnegative last, entries [key,id,bucket], and width. Bucket index is bit_length(key XOR last). Report monotonicity violations, bucket assignment violations, zero-bucket members, next nonempty bucket, next extraction threshold, and overflow keys. This is an unsigned bounded toy representation.

split: open-access


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

N = 1
observations = []
def solve(d):
    last=d['last']; entries=d['entries']; width=d['width']
    return {'monotone': [x[1] for x in entries if x[0]<last],
    'placement': [x[1] for x in entries if x[2]!=(x[0]^last).bit_length()],
    'zero_members': [x[1] for x in entries if x[0]==last],
    'next_bucket': max([x[2] for x in entries if x[2]>0],default=None),
    'new_last': min([x[0] for x in entries],default=last),
    'overflow': [x[1] for x in entries if x[0]>=2**width]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [16, 'variant', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})], [({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [32, 'variant', 6]], 'width': 5}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})], [({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [64, 'variant', 7]], 'width': 6}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})], [({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [128, 'variant', 8]], 'width': 7}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})], [({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [256, 'variant', 9]], 'width': 8}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

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

N = 1
observations = []
def solve(d):
    last=d['last']; entries=d['entries']; width=d['width']
    return {'monotone': [x[1] for x in entries if x[0]<last],
    'placement': [x[1] for x in entries if x[2]!=(x[0]^last).bit_length()],
    'zero_members': [x[1] for x in entries if x[0]==last],
    'next_bucket': min([x[2] for x in entries],default=None),
    'new_last': min([x[0] for x in entries],default=last),
    'overflow': [x[1] for x in entries if x[0]>=2**width]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [16, 'variant', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})], [({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [32, 'variant', 6]], 'width': 5}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})], [({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [64, 'variant', 7]], 'width': 6}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})], [({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [128, 'variant', 8]], 'width': 7}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})], [({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [256, 'variant', 9]], 'width': 8}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})]][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 radix buckets certificate reports an incorrect next bucket.

A monotone integer radix-heap certificate has nonnegative last, entries [key,id,bucket], and width. Bucket index is bit_length(key XOR last). Report monotonicity violations, bucket assignment violations, zero-bucket members, next nonempty bucket, next extraction threshold, and overflow keys. This is an unsigned bounded toy representation.

split: open-access


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

N = 1
observations = []
def solve(d):
    last=d['last']; entries=d['entries']; width=d['width']
    return {'monotone': [x[1] for x in entries if x[0]<last],
    'placement': [x[1] for x in entries if x[2]!=(x[0]^last).bit_length()],
    'zero_members': [x[1] for x in entries if x[0]==last],
    'next_bucket': min([x[2] for x in entries if x[2]>0],default=None),
    'new_last': entries[0][0] if entries else last,
    'overflow': [x[1] for x in entries if x[0]>=2**width]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [16, 'variant', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})], [({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [32, 'variant', 6]], 'width': 5}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})], [({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [64, 'variant', 7]], 'width': 6}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})], [({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [128, 'variant', 8]], 'width': 7}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})], [({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [256, 'variant', 9]], 'width': 8}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

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

N = 1
observations = []
def solve(d):
    last=d['last']; entries=d['entries']; width=d['width']
    return {'monotone': [x[1] for x in entries if x[0]<last],
    'placement': [x[1] for x in entries if x[2]!=(x[0]^last).bit_length()],
    'zero_members': [x[1] for x in entries if x[0]==last],
    'next_bucket': min([x[2] for x in entries if x[2]>0],default=None),
    'new_last': min([x[0] for x in entries],default=0),
    'overflow': [x[1] for x in entries if x[0]>=2**width]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [16, 'variant', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})], [({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [32, 'variant', 6]], 'width': 5}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})], [({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [64, 'variant', 7]], 'width': 6}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})], [({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [128, 'variant', 8]], 'width': 7}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})], [({'last': 3, 'entries': [], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': [], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 3, 'entries': [[3, 'a', 0]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['a'], 'next_bucket': None, 'new_last': 3, 'overflow': []}), ({'last': 7, 'entries': [[8, 'a', 4], [7, 'b', 0], [15, 'c', 4], [16, 'd', 5]], 'width': 4}, {'monotone': [], 'placement': [], 'zero_members': ['b'], 'next_bucket': 4, 'new_last': 7, 'overflow': ['d']}), ({'last': 4, 'entries': [[7, 'a', 2], [5, 'b', 1], [4, 'c', 1]], 'width': 3}, {'monotone': [], 'placement': ['c'], 'zero_members': ['c'], 'next_bucket': 1, 'new_last': 4, 'overflow': []}), ({'last': 9, 'entries': [[8, 'a', 1], [9, 'b', 0], [12, 'c', 3], [2, 'd', 4]], 'width': 4}, {'monotone': ['a', 'd'], 'placement': [], 'zero_members': ['b'], 'next_bucket': 1, 'new_last': 2, 'overflow': []}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0]], 'width': 3}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['a']}), ({'last': 1, 'entries': [[8, 'a', 4], [3, 'b', 2], [2, 'c', 2], [1, 'd', 0], [256, 'variant', 9]], 'width': 8}, {'monotone': [], 'placement': [], 'zero_members': ['d'], 'next_bucket': 2, 'new_last': 1, 'overflow': ['variant']})]][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 radix buckets certificate reports an incorrect new last.

A monotone integer radix-heap certificate has nonnegative last, entries [key,id,bucket], and width. Bucket index is bit_length(key XOR last). Report monotonicity violations, bucket assignment violations, zero-bucket members, next nonempty bucket, next extraction threshold, and overflow keys. This is an unsigned bounded toy representation.

split: open-access