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

N = 1
observations = []
def solve(d):
    old=d['old_left']; result=d['result']; sizes=d['sizes']
    return {'new_left': result,
    'new_right': old,
    'size': 1+sum(sizes),
    'rewrites': [[x,d["winner"]] for x in (result,old) if x is not None],
    'preorder_children': [x for x in (old,result) if x is not None],
    'leaf': old is None and result is None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [8, 10]}, {'new_left': 8, 'new_right': 4, 'size': 19, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [9, 11]}, {'new_left': 8, 'new_right': 4, 'size': 21, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [10, 12]}, {'new_left': 8, 'new_right': 4, 'size': 23, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [11, 13]}, {'new_left': 8, 'new_right': 4, 'size': 25, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [12, 14]}, {'new_left': 8, 'new_right': 4, 'size': 27, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})]][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):
    old=d['old_left']; result=d['result']; sizes=d['sizes']
    return {'new_left': result,
    'new_right': old,
    'size': 1+sum(sizes),
    'rewrites': [[x,d["winner"]] for x in (result,old) if x is not None],
    'preorder_children': sorted(x for x in (result,old) if x is not None),
    'leaf': old is None and result is None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [8, 10]}, {'new_left': 8, 'new_right': 4, 'size': 19, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [9, 11]}, {'new_left': 8, 'new_right': 4, 'size': 21, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [10, 12]}, {'new_left': 8, 'new_right': 4, 'size': 23, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [11, 13]}, {'new_left': 8, 'new_right': 4, 'size': 25, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [12, 14]}, {'new_left': 8, 'new_right': 4, 'size': 27, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})]][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 skew meld step certificate reports an incorrect preorder children.

A skew meld unwind chooses the smaller root, recursively melds its old right subtree with the other heap, and unconditionally swaps children. Record supplies winner, old_left, recursive_result and sizes. Missing subtrees are None. No rank-based swap condition is part of this model.

split: open-access


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

N = 1
observations = []
def solve(d):
    old=d['old_left']; result=d['result']; sizes=d['sizes']
    return {'new_left': result,
    'new_right': old,
    'size': 1+sum(sizes),
    'rewrites': [[x,d["winner"]] for x in (result,old) if x is not None],
    'preorder_children': [x for x in (result,old) if x is not None],
    'leaf': old is None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [8, 10]}, {'new_left': 8, 'new_right': 4, 'size': 19, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [9, 11]}, {'new_left': 8, 'new_right': 4, 'size': 21, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [10, 12]}, {'new_left': 8, 'new_right': 4, 'size': 23, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [11, 13]}, {'new_left': 8, 'new_right': 4, 'size': 25, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [12, 14]}, {'new_left': 8, 'new_right': 4, 'size': 27, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})]][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):
    old=d['old_left']; result=d['result']; sizes=d['sizes']
    return {'new_left': result,
    'new_right': old,
    'size': 1+sum(sizes),
    'rewrites': [[x,d["winner"]] for x in (result,old) if x is not None],
    'preorder_children': [x for x in (result,old) if x is not None],
    'leaf': result is None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [8, 10]}, {'new_left': 8, 'new_right': 4, 'size': 19, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [9, 11]}, {'new_left': 8, 'new_right': 4, 'size': 21, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [10, 12]}, {'new_left': 8, 'new_right': 4, 'size': 23, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [11, 13]}, {'new_left': 8, 'new_right': 4, 'size': 25, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [12, 14]}, {'new_left': 8, 'new_right': 4, 'size': 27, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})]][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 skew meld step certificate reports an incorrect leaf.

A skew meld unwind chooses the smaller root, recursively melds its old right subtree with the other heap, and unconditionally swaps children. Record supplies winner, old_left, recursive_result and sizes. Missing subtrees are None. No rank-based swap condition is part of this model.

split: open-access


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

N = 1
observations = []
def solve(d):
    a=d['entries']; old=d['old_last']; new=min(x[1] for x in a); dest=[(x[0],(x[1]^new).bit_length()) for x in a]
    return {'threshold': a[0][1],
    'destinations': [[i,b] for i,b in dest],
    'zero_ids': [x[0] for x in a if x[1]==new],
    'moved': len(a),
    'source_after': [],
    'largest_destination': max(b for i,b in dest)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [101, 9]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [101, 0]], 'zero_ids': [2, 101], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [102, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [102, 2]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [103, 11]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [103, 2]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [104, 12]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [104, 3]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [105, 13]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [105, 3]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})]][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']; old=d['old_last']; new=min(x[1] for x in a); dest=[(x[0],(x[1]^new).bit_length()) for x in a]
    return {'threshold': old,
    'destinations': [[i,b] for i,b in dest],
    'zero_ids': [x[0] for x in a if x[1]==new],
    'moved': len(a),
    'source_after': [],
    'largest_destination': max(b for i,b in dest)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [101, 9]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [101, 0]], 'zero_ids': [2, 101], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [102, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [102, 2]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [103, 11]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [103, 2]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [104, 12]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [104, 3]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [105, 13]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [105, 3]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})]][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 redistribute certificate reports an incorrect threshold.

Redistribute one nonempty radix bucket with entries [id,key], all keys at least old_last. Set new_last to bucket minimum and move every entry to bit_length(key XOR new_last); preserve entry order within each destination bucket. Report threshold, assignments, bucket-zero ids, moved count, old-bucket clearing, and maximum destination.

split: open-access


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

N = 1
observations = []
def solve(d):
    a=d['entries']; old=d['old_last']; new=min(x[1] for x in a); dest=[(x[0],(x[1]^new).bit_length()) for x in a]
    return {'threshold': new,
    'destinations': [[x[0],(x[1]^old).bit_length()] for x in a],
    'zero_ids': [x[0] for x in a if x[1]==new],
    'moved': len(a),
    'source_after': [],
    'largest_destination': max(b for i,b in dest)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [101, 9]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [101, 0]], 'zero_ids': [2, 101], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [102, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [102, 2]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [103, 11]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [103, 2]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [104, 12]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [104, 3]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [105, 13]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [105, 3]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})]][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']; old=d['old_last']; new=min(x[1] for x in a); dest=[(x[0],(x[1]^new).bit_length()) for x in a]
    return {'threshold': new,
    'destinations': [[x[0],(x[1]-new).bit_length()] for x in a],
    'zero_ids': [x[0] for x in a if x[1]==new],
    'moved': len(a),
    'source_after': [],
    'largest_destination': max(b for i,b in dest)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [101, 9]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [101, 0]], 'zero_ids': [2, 101], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [102, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [102, 2]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [103, 11]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [103, 2]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [104, 12]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [104, 3]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [105, 13]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [105, 3]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})]][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 redistribute certificate reports an incorrect destinations.

Redistribute one nonempty radix bucket with entries [id,key], all keys at least old_last. Set new_last to bucket minimum and move every entry to bit_length(key XOR new_last); preserve entry order within each destination bucket. Report threshold, assignments, bucket-zero ids, moved count, old-bucket clearing, and maximum destination.

split: open-access


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

N = 1
observations = []
def solve(d):
    a=d['entries']; old=d['old_last']; new=min(x[1] for x in a); dest=[(x[0],(x[1]^new).bit_length()) for x in a]
    return {'threshold': new,
    'destinations': [[i,b] for i,b in dest],
    'zero_ids': [a[0][0]],
    'moved': len(a),
    'source_after': [],
    'largest_destination': max(b for i,b in dest)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [101, 9]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [101, 0]], 'zero_ids': [2, 101], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [102, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [102, 2]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [103, 11]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [103, 2]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [104, 12]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [104, 3]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [105, 13]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [105, 3]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})]][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']; old=d['old_last']; new=min(x[1] for x in a); dest=[(x[0],(x[1]^new).bit_length()) for x in a]
    return {'threshold': new,
    'destinations': [[i,b] for i,b in dest],
    'zero_ids': [x[0] for x in a if x[1]==old],
    'moved': len(a),
    'source_after': [],
    'largest_destination': max(b for i,b in dest)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [101, 9]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [101, 0]], 'zero_ids': [2, 101], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [102, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [102, 2]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [103, 11]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [103, 2]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [104, 12]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [104, 3]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [105, 13]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [105, 3]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})]][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 redistribute certificate reports an incorrect zero ids.

Redistribute one nonempty radix bucket with entries [id,key], all keys at least old_last. Set new_last to bucket minimum and move every entry to bit_length(key XOR new_last); preserve entry order within each destination bucket. Report threshold, assignments, bucket-zero ids, moved count, old-bucket clearing, and maximum destination.

split: open-access


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

N = 1
observations = []
def solve(d):
    a=d['entries']; old=d['old_last']; new=min(x[1] for x in a); dest=[(x[0],(x[1]^new).bit_length()) for x in a]
    return {'threshold': new,
    'destinations': [[i,b] for i,b in dest],
    'zero_ids': [x[0] for x in a if x[1]==new],
    'moved': len(set(x[1] for x in a)),
    'source_after': [],
    'largest_destination': max(b for i,b in dest)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [101, 9]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [101, 0]], 'zero_ids': [2, 101], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [102, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [102, 2]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [103, 11]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [103, 2]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [104, 12]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [104, 3]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [105, 13]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [105, 3]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})]][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']; old=d['old_last']; new=min(x[1] for x in a); dest=[(x[0],(x[1]^new).bit_length()) for x in a]
    return {'threshold': new,
    'destinations': [[i,b] for i,b in dest],
    'zero_ids': [x[0] for x in a if x[1]==new],
    'moved': len(a)-1,
    'source_after': [],
    'largest_destination': max(b for i,b in dest)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [101, 9]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [101, 0]], 'zero_ids': [2, 101], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [102, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [102, 2]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [103, 11]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [103, 2]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [104, 12]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [104, 3]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})], [({'old_last': 0, 'entries': [[1, 8]]}, {'threshold': 8, 'destinations': [[1, 0]], 'zero_ids': [1], 'moved': 1, 'source_after': [], 'largest_destination': 0}), ({'old_last': 3, 'entries': [[1, 7], [2, 4], [3, 6]]}, {'threshold': 4, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 7, 'entries': [[1, 15], [2, 8], [3, 8], [4, 12]]}, {'threshold': 8, 'destinations': [[1, 3], [2, 0], [3, 0], [4, 3]], 'zero_ids': [2, 3], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 1, 'entries': [[1, 3], [2, 2]]}, {'threshold': 2, 'destinations': [[1, 1], [2, 0]], 'zero_ids': [2], 'moved': 2, 'source_after': [], 'largest_destination': 1}), ({'old_last': 4, 'entries': [[1, 7], [2, 5], [3, 6]]}, {'threshold': 5, 'destinations': [[1, 2], [2, 0], [3, 2]], 'zero_ids': [2], 'moved': 3, 'source_after': [], 'largest_destination': 2}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2]], 'zero_ids': [2], 'moved': 4, 'source_after': [], 'largest_destination': 3}), ({'old_last': 8, 'entries': [[1, 15], [2, 9], [3, 11], [4, 10], [105, 13]]}, {'threshold': 9, 'destinations': [[1, 3], [2, 0], [3, 2], [4, 2], [105, 3]], 'zero_ids': [2], 'moved': 5, 'source_after': [], 'largest_destination': 3})]][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 redistribute certificate reports an incorrect moved.

Redistribute one nonempty radix bucket with entries [id,key], all keys at least old_last. Set new_last to bucket minimum and move every entry to bit_length(key XOR new_last); preserve entry order within each destination bucket. Report threshold, assignments, bucket-zero ids, moved count, old-bucket clearing, and maximum destination.

split: open-access