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

N = 1
observations = []
def solve(d):
    a=d['keys']; start=d['start']; path=[start]; moved=[]; compares=0; i=start
    while 2*i+1<len(a):
        l=2*i+1; r=l+1; j=l
        if r<len(a):
            compares+=1
            if a[r]<a[l]: j=r
        moved.append(a[j]); path.append(j); i=j
    return {'path': path,
    'moved_keys': moved,
    'leaf_slot': i,
    'displaced': a[start],
    'untouched': [j for j in range(len(a)) if j!=start],
    'comparisons': compares}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'keys': [5], 'start': 0}, {'path': [0], 'moved_keys': [], 'leaf_slot': 0, 'displaced': 5, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 2], 'start': 0}, {'path': [0, 1], 'moved_keys': [2], 'leaf_slot': 1, 'displaced': 9, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 5, 8, 2, 7, 6, 4], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [5, 2], 'leaf_slot': 3, 'displaced': 9, 'untouched': [2, 4, 5, 6], 'comparisons': 2}), ({'keys': [8, 2, 2, 5, 6, 7], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [2, 5], 'leaf_slot': 3, 'displaced': 8, 'untouched': [2, 4, 5], 'comparisons': 2}), ({'keys': [0, 9, 3, 4, 2, 8, 6, 7, 8, 5], 'start': 1}, {'path': [1, 4, 9], 'moved_keys': [2, 5], 'leaf_slot': 9, 'displaced': 9, 'untouched': [0, 2, 3, 5, 6, 7, 8], 'comparisons': 1}), ({'keys': [1, 4, 2, 5, 6, 7, 8], 'start': 2}, {'path': [2, 5], 'moved_keys': [7], 'leaf_slot': 5, 'displaced': 2, 'untouched': [0, 1, 3, 4, 6], 'comparisons': 1}), ({'keys': [2, 4, 2, 5, 6, 7, 8], 'start': 1}, {'path': [1, 3], 'moved_keys': [5], 'leaf_slot': 3, 'displaced': 4, 'untouched': [0, 2, 4, 5, 6], 'comparisons': 1})], [({'keys': [5], 'start': 0}, {'path': [0], 'moved_keys': [], 'leaf_slot': 0, 'displaced': 5, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 2], 'start': 0}, {'path': [0, 1], 'moved_keys': [2], 'leaf_slot': 1, 'displaced': 9, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 5, 8, 2, 7, 6, 4], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [5, 2], 'leaf_slot': 3, 'displaced': 9, 'untouched': [2, 4, 5, 6], 'comparisons': 2}), ({'keys': [8, 2, 2, 5, 6, 7], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [2, 5], 'leaf_slot': 3, 'displaced': 8, 'untouched': [2, 4, 5], 'comparisons': 2}), ({'keys': [0, 9, 3, 4, 2, 8, 6, 7, 8, 5], 'start': 1}, {'path': [1, 4, 9], 'moved_keys': [2, 5], 'leaf_slot': 9, 'displaced': 9, 'untouched': [0, 2, 3, 5, 6, 7, 8], 'comparisons': 1}), ({'keys': [1, 4, 2, 5, 6, 7, 8], 'start': 2}, {'path': [2, 5], 'moved_keys': [7], 'leaf_slot': 5, 'displaced': 2, 'untouched': [0, 1, 3, 4, 6], 'comparisons': 1}), ({'keys': [3, 4, 2, 5, 6, 7, 8], 'start': 2}, {'path': [2, 5], 'moved_keys': [7], 'leaf_slot': 5, 'displaced': 2, 'untouched': [0, 1, 3, 4, 6], 'comparisons': 1})], [({'keys': [5], 'start': 0}, {'path': [0], 'moved_keys': [], 'leaf_slot': 0, 'displaced': 5, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 2], 'start': 0}, {'path': [0, 1], 'moved_keys': [2], 'leaf_slot': 1, 'displaced': 9, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 5, 8, 2, 7, 6, 4], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [5, 2], 'leaf_slot': 3, 'displaced': 9, 'untouched': [2, 4, 5, 6], 'comparisons': 2}), ({'keys': [8, 2, 2, 5, 6, 7], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [2, 5], 'leaf_slot': 3, 'displaced': 8, 'untouched': [2, 4, 5], 'comparisons': 2}), ({'keys': [0, 9, 3, 4, 2, 8, 6, 7, 8, 5], 'start': 1}, {'path': [1, 4, 9], 'moved_keys': [2, 5], 'leaf_slot': 9, 'displaced': 9, 'untouched': [0, 2, 3, 5, 6, 7, 8], 'comparisons': 1}), ({'keys': [1, 4, 2, 5, 6, 7, 8], 'start': 2}, {'path': [2, 5], 'moved_keys': [7], 'leaf_slot': 5, 'displaced': 2, 'untouched': [0, 1, 3, 4, 6], 'comparisons': 1}), ({'keys': [4, 4, 2, 5, 6, 7, 8], 'start': 3}, {'path': [3], 'moved_keys': [], 'leaf_slot': 3, 'displaced': 5, 'untouched': [0, 1, 2, 4, 5, 6], 'comparisons': 0})], [({'keys': [5], 'start': 0}, {'path': [0], 'moved_keys': [], 'leaf_slot': 0, 'displaced': 5, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 2], 'start': 0}, {'path': [0, 1], 'moved_keys': [2], 'leaf_slot': 1, 'displaced': 9, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 5, 8, 2, 7, 6, 4], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [5, 2], 'leaf_slot': 3, 'displaced': 9, 'untouched': [2, 4, 5, 6], 'comparisons': 2}), ({'keys': [8, 2, 2, 5, 6, 7], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [2, 5], 'leaf_slot': 3, 'displaced': 8, 'untouched': [2, 4, 5], 'comparisons': 2}), ({'keys': [0, 9, 3, 4, 2, 8, 6, 7, 8, 5], 'start': 1}, {'path': [1, 4, 9], 'moved_keys': [2, 5], 'leaf_slot': 9, 'displaced': 9, 'untouched': [0, 2, 3, 5, 6, 7, 8], 'comparisons': 1}), ({'keys': [1, 4, 2, 5, 6, 7, 8], 'start': 2}, {'path': [2, 5], 'moved_keys': [7], 'leaf_slot': 5, 'displaced': 2, 'untouched': [0, 1, 3, 4, 6], 'comparisons': 1}), ({'keys': [5, 4, 2, 5, 6, 7, 8], 'start': 4}, {'path': [4], 'moved_keys': [], 'leaf_slot': 4, 'displaced': 6, 'untouched': [0, 1, 2, 3, 5, 6], 'comparisons': 0})], [({'keys': [5], 'start': 0}, {'path': [0], 'moved_keys': [], 'leaf_slot': 0, 'displaced': 5, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 2], 'start': 0}, {'path': [0, 1], 'moved_keys': [2], 'leaf_slot': 1, 'displaced': 9, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 5, 8, 2, 7, 6, 4], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [5, 2], 'leaf_slot': 3, 'displaced': 9, 'untouched': [2, 4, 5, 6], 'comparisons': 2}), ({'keys': [8, 2, 2, 5, 6, 7], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [2, 5], 'leaf_slot': 3, 'displaced': 8, 'untouched': [2, 4, 5], 'comparisons': 2}), ({'keys': [0, 9, 3, 4, 2, 8, 6, 7, 8, 5], 'start': 1}, {'path': [1, 4, 9], 'moved_keys': [2, 5], 'leaf_slot': 9, 'displaced': 9, 'untouched': [0, 2, 3, 5, 6, 7, 8], 'comparisons': 1}), ({'keys': [1, 4, 2, 5, 6, 7, 8], 'start': 2}, {'path': [2, 5], 'moved_keys': [7], 'leaf_slot': 5, 'displaced': 2, 'untouched': [0, 1, 3, 4, 6], 'comparisons': 1}), ({'keys': [6, 4, 2, 5, 6, 7, 8], 'start': 5}, {'path': [5], 'moved_keys': [], 'leaf_slot': 5, 'displaced': 7, 'untouched': [0, 1, 2, 3, 4, 6], 'comparisons': 0})]][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['keys']; start=d['start']; path=[start]; moved=[]; compares=0; i=start
    while 2*i+1<len(a):
        l=2*i+1; r=l+1; j=l
        if r<len(a):
            compares+=1
            if a[r]<a[l]: j=r
        moved.append(a[j]); path.append(j); i=j
    return {'path': path,
    'moved_keys': moved,
    'leaf_slot': i,
    'displaced': a[start],
    'untouched': [],
    'comparisons': compares}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'keys': [5], 'start': 0}, {'path': [0], 'moved_keys': [], 'leaf_slot': 0, 'displaced': 5, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 2], 'start': 0}, {'path': [0, 1], 'moved_keys': [2], 'leaf_slot': 1, 'displaced': 9, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 5, 8, 2, 7, 6, 4], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [5, 2], 'leaf_slot': 3, 'displaced': 9, 'untouched': [2, 4, 5, 6], 'comparisons': 2}), ({'keys': [8, 2, 2, 5, 6, 7], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [2, 5], 'leaf_slot': 3, 'displaced': 8, 'untouched': [2, 4, 5], 'comparisons': 2}), ({'keys': [0, 9, 3, 4, 2, 8, 6, 7, 8, 5], 'start': 1}, {'path': [1, 4, 9], 'moved_keys': [2, 5], 'leaf_slot': 9, 'displaced': 9, 'untouched': [0, 2, 3, 5, 6, 7, 8], 'comparisons': 1}), ({'keys': [1, 4, 2, 5, 6, 7, 8], 'start': 2}, {'path': [2, 5], 'moved_keys': [7], 'leaf_slot': 5, 'displaced': 2, 'untouched': [0, 1, 3, 4, 6], 'comparisons': 1}), ({'keys': [2, 4, 2, 5, 6, 7, 8], 'start': 1}, {'path': [1, 3], 'moved_keys': [5], 'leaf_slot': 3, 'displaced': 4, 'untouched': [0, 2, 4, 5, 6], 'comparisons': 1})], [({'keys': [5], 'start': 0}, {'path': [0], 'moved_keys': [], 'leaf_slot': 0, 'displaced': 5, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 2], 'start': 0}, {'path': [0, 1], 'moved_keys': [2], 'leaf_slot': 1, 'displaced': 9, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 5, 8, 2, 7, 6, 4], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [5, 2], 'leaf_slot': 3, 'displaced': 9, 'untouched': [2, 4, 5, 6], 'comparisons': 2}), ({'keys': [8, 2, 2, 5, 6, 7], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [2, 5], 'leaf_slot': 3, 'displaced': 8, 'untouched': [2, 4, 5], 'comparisons': 2}), ({'keys': [0, 9, 3, 4, 2, 8, 6, 7, 8, 5], 'start': 1}, {'path': [1, 4, 9], 'moved_keys': [2, 5], 'leaf_slot': 9, 'displaced': 9, 'untouched': [0, 2, 3, 5, 6, 7, 8], 'comparisons': 1}), ({'keys': [1, 4, 2, 5, 6, 7, 8], 'start': 2}, {'path': [2, 5], 'moved_keys': [7], 'leaf_slot': 5, 'displaced': 2, 'untouched': [0, 1, 3, 4, 6], 'comparisons': 1}), ({'keys': [3, 4, 2, 5, 6, 7, 8], 'start': 2}, {'path': [2, 5], 'moved_keys': [7], 'leaf_slot': 5, 'displaced': 2, 'untouched': [0, 1, 3, 4, 6], 'comparisons': 1})], [({'keys': [5], 'start': 0}, {'path': [0], 'moved_keys': [], 'leaf_slot': 0, 'displaced': 5, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 2], 'start': 0}, {'path': [0, 1], 'moved_keys': [2], 'leaf_slot': 1, 'displaced': 9, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 5, 8, 2, 7, 6, 4], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [5, 2], 'leaf_slot': 3, 'displaced': 9, 'untouched': [2, 4, 5, 6], 'comparisons': 2}), ({'keys': [8, 2, 2, 5, 6, 7], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [2, 5], 'leaf_slot': 3, 'displaced': 8, 'untouched': [2, 4, 5], 'comparisons': 2}), ({'keys': [0, 9, 3, 4, 2, 8, 6, 7, 8, 5], 'start': 1}, {'path': [1, 4, 9], 'moved_keys': [2, 5], 'leaf_slot': 9, 'displaced': 9, 'untouched': [0, 2, 3, 5, 6, 7, 8], 'comparisons': 1}), ({'keys': [1, 4, 2, 5, 6, 7, 8], 'start': 2}, {'path': [2, 5], 'moved_keys': [7], 'leaf_slot': 5, 'displaced': 2, 'untouched': [0, 1, 3, 4, 6], 'comparisons': 1}), ({'keys': [4, 4, 2, 5, 6, 7, 8], 'start': 3}, {'path': [3], 'moved_keys': [], 'leaf_slot': 3, 'displaced': 5, 'untouched': [0, 1, 2, 4, 5, 6], 'comparisons': 0})], [({'keys': [5], 'start': 0}, {'path': [0], 'moved_keys': [], 'leaf_slot': 0, 'displaced': 5, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 2], 'start': 0}, {'path': [0, 1], 'moved_keys': [2], 'leaf_slot': 1, 'displaced': 9, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 5, 8, 2, 7, 6, 4], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [5, 2], 'leaf_slot': 3, 'displaced': 9, 'untouched': [2, 4, 5, 6], 'comparisons': 2}), ({'keys': [8, 2, 2, 5, 6, 7], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [2, 5], 'leaf_slot': 3, 'displaced': 8, 'untouched': [2, 4, 5], 'comparisons': 2}), ({'keys': [0, 9, 3, 4, 2, 8, 6, 7, 8, 5], 'start': 1}, {'path': [1, 4, 9], 'moved_keys': [2, 5], 'leaf_slot': 9, 'displaced': 9, 'untouched': [0, 2, 3, 5, 6, 7, 8], 'comparisons': 1}), ({'keys': [1, 4, 2, 5, 6, 7, 8], 'start': 2}, {'path': [2, 5], 'moved_keys': [7], 'leaf_slot': 5, 'displaced': 2, 'untouched': [0, 1, 3, 4, 6], 'comparisons': 1}), ({'keys': [5, 4, 2, 5, 6, 7, 8], 'start': 4}, {'path': [4], 'moved_keys': [], 'leaf_slot': 4, 'displaced': 6, 'untouched': [0, 1, 2, 3, 5, 6], 'comparisons': 0})], [({'keys': [5], 'start': 0}, {'path': [0], 'moved_keys': [], 'leaf_slot': 0, 'displaced': 5, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 2], 'start': 0}, {'path': [0, 1], 'moved_keys': [2], 'leaf_slot': 1, 'displaced': 9, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 5, 8, 2, 7, 6, 4], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [5, 2], 'leaf_slot': 3, 'displaced': 9, 'untouched': [2, 4, 5, 6], 'comparisons': 2}), ({'keys': [8, 2, 2, 5, 6, 7], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [2, 5], 'leaf_slot': 3, 'displaced': 8, 'untouched': [2, 4, 5], 'comparisons': 2}), ({'keys': [0, 9, 3, 4, 2, 8, 6, 7, 8, 5], 'start': 1}, {'path': [1, 4, 9], 'moved_keys': [2, 5], 'leaf_slot': 9, 'displaced': 9, 'untouched': [0, 2, 3, 5, 6, 7, 8], 'comparisons': 1}), ({'keys': [1, 4, 2, 5, 6, 7, 8], 'start': 2}, {'path': [2, 5], 'moved_keys': [7], 'leaf_slot': 5, 'displaced': 2, 'untouched': [0, 1, 3, 4, 6], 'comparisons': 1}), ({'keys': [6, 4, 2, 5, 6, 7, 8], 'start': 5}, {'path': [5], 'moved_keys': [], 'leaf_slot': 5, 'displaced': 7, 'untouched': [0, 1, 2, 3, 4, 6], 'comparisons': 0})]][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 hole descent certificate reports an incorrect untouched.

A binary heap hole descent receives array keys and starting internal or leaf index. Repeatedly choose smaller existing child (left on ties), move that child into the hole, and stop at a leaf; the displaced root value is returned separately for later upward placement. Return path, moved keys, leaf slot, displaced value, remaining untouched slots, and comparison count between sibling pairs.

split: open-access


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

N = 1
observations = []
def solve(d):
    a=d['keys']; start=d['start']; path=[start]; moved=[]; compares=0; i=start
    while 2*i+1<len(a):
        l=2*i+1; r=l+1; j=l
        if r<len(a):
            compares+=1
            if a[r]<a[l]: j=r
        moved.append(a[j]); path.append(j); i=j
    return {'path': path,
    'moved_keys': moved,
    'leaf_slot': i,
    'displaced': a[start],
    'untouched': [j for j in range(len(a)) if j not in path],
    'comparisons': len(path)-1}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'keys': [5], 'start': 0}, {'path': [0], 'moved_keys': [], 'leaf_slot': 0, 'displaced': 5, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 2], 'start': 0}, {'path': [0, 1], 'moved_keys': [2], 'leaf_slot': 1, 'displaced': 9, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 5, 8, 2, 7, 6, 4], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [5, 2], 'leaf_slot': 3, 'displaced': 9, 'untouched': [2, 4, 5, 6], 'comparisons': 2}), ({'keys': [8, 2, 2, 5, 6, 7], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [2, 5], 'leaf_slot': 3, 'displaced': 8, 'untouched': [2, 4, 5], 'comparisons': 2}), ({'keys': [0, 9, 3, 4, 2, 8, 6, 7, 8, 5], 'start': 1}, {'path': [1, 4, 9], 'moved_keys': [2, 5], 'leaf_slot': 9, 'displaced': 9, 'untouched': [0, 2, 3, 5, 6, 7, 8], 'comparisons': 1}), ({'keys': [1, 4, 2, 5, 6, 7, 8], 'start': 2}, {'path': [2, 5], 'moved_keys': [7], 'leaf_slot': 5, 'displaced': 2, 'untouched': [0, 1, 3, 4, 6], 'comparisons': 1}), ({'keys': [2, 4, 2, 5, 6, 7, 8], 'start': 1}, {'path': [1, 3], 'moved_keys': [5], 'leaf_slot': 3, 'displaced': 4, 'untouched': [0, 2, 4, 5, 6], 'comparisons': 1})], [({'keys': [5], 'start': 0}, {'path': [0], 'moved_keys': [], 'leaf_slot': 0, 'displaced': 5, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 2], 'start': 0}, {'path': [0, 1], 'moved_keys': [2], 'leaf_slot': 1, 'displaced': 9, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 5, 8, 2, 7, 6, 4], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [5, 2], 'leaf_slot': 3, 'displaced': 9, 'untouched': [2, 4, 5, 6], 'comparisons': 2}), ({'keys': [8, 2, 2, 5, 6, 7], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [2, 5], 'leaf_slot': 3, 'displaced': 8, 'untouched': [2, 4, 5], 'comparisons': 2}), ({'keys': [0, 9, 3, 4, 2, 8, 6, 7, 8, 5], 'start': 1}, {'path': [1, 4, 9], 'moved_keys': [2, 5], 'leaf_slot': 9, 'displaced': 9, 'untouched': [0, 2, 3, 5, 6, 7, 8], 'comparisons': 1}), ({'keys': [1, 4, 2, 5, 6, 7, 8], 'start': 2}, {'path': [2, 5], 'moved_keys': [7], 'leaf_slot': 5, 'displaced': 2, 'untouched': [0, 1, 3, 4, 6], 'comparisons': 1}), ({'keys': [3, 4, 2, 5, 6, 7, 8], 'start': 2}, {'path': [2, 5], 'moved_keys': [7], 'leaf_slot': 5, 'displaced': 2, 'untouched': [0, 1, 3, 4, 6], 'comparisons': 1})], [({'keys': [5], 'start': 0}, {'path': [0], 'moved_keys': [], 'leaf_slot': 0, 'displaced': 5, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 2], 'start': 0}, {'path': [0, 1], 'moved_keys': [2], 'leaf_slot': 1, 'displaced': 9, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 5, 8, 2, 7, 6, 4], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [5, 2], 'leaf_slot': 3, 'displaced': 9, 'untouched': [2, 4, 5, 6], 'comparisons': 2}), ({'keys': [8, 2, 2, 5, 6, 7], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [2, 5], 'leaf_slot': 3, 'displaced': 8, 'untouched': [2, 4, 5], 'comparisons': 2}), ({'keys': [0, 9, 3, 4, 2, 8, 6, 7, 8, 5], 'start': 1}, {'path': [1, 4, 9], 'moved_keys': [2, 5], 'leaf_slot': 9, 'displaced': 9, 'untouched': [0, 2, 3, 5, 6, 7, 8], 'comparisons': 1}), ({'keys': [1, 4, 2, 5, 6, 7, 8], 'start': 2}, {'path': [2, 5], 'moved_keys': [7], 'leaf_slot': 5, 'displaced': 2, 'untouched': [0, 1, 3, 4, 6], 'comparisons': 1}), ({'keys': [4, 4, 2, 5, 6, 7, 8], 'start': 3}, {'path': [3], 'moved_keys': [], 'leaf_slot': 3, 'displaced': 5, 'untouched': [0, 1, 2, 4, 5, 6], 'comparisons': 0})], [({'keys': [5], 'start': 0}, {'path': [0], 'moved_keys': [], 'leaf_slot': 0, 'displaced': 5, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 2], 'start': 0}, {'path': [0, 1], 'moved_keys': [2], 'leaf_slot': 1, 'displaced': 9, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 5, 8, 2, 7, 6, 4], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [5, 2], 'leaf_slot': 3, 'displaced': 9, 'untouched': [2, 4, 5, 6], 'comparisons': 2}), ({'keys': [8, 2, 2, 5, 6, 7], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [2, 5], 'leaf_slot': 3, 'displaced': 8, 'untouched': [2, 4, 5], 'comparisons': 2}), ({'keys': [0, 9, 3, 4, 2, 8, 6, 7, 8, 5], 'start': 1}, {'path': [1, 4, 9], 'moved_keys': [2, 5], 'leaf_slot': 9, 'displaced': 9, 'untouched': [0, 2, 3, 5, 6, 7, 8], 'comparisons': 1}), ({'keys': [1, 4, 2, 5, 6, 7, 8], 'start': 2}, {'path': [2, 5], 'moved_keys': [7], 'leaf_slot': 5, 'displaced': 2, 'untouched': [0, 1, 3, 4, 6], 'comparisons': 1}), ({'keys': [5, 4, 2, 5, 6, 7, 8], 'start': 4}, {'path': [4], 'moved_keys': [], 'leaf_slot': 4, 'displaced': 6, 'untouched': [0, 1, 2, 3, 5, 6], 'comparisons': 0})], [({'keys': [5], 'start': 0}, {'path': [0], 'moved_keys': [], 'leaf_slot': 0, 'displaced': 5, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 2], 'start': 0}, {'path': [0, 1], 'moved_keys': [2], 'leaf_slot': 1, 'displaced': 9, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 5, 8, 2, 7, 6, 4], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [5, 2], 'leaf_slot': 3, 'displaced': 9, 'untouched': [2, 4, 5, 6], 'comparisons': 2}), ({'keys': [8, 2, 2, 5, 6, 7], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [2, 5], 'leaf_slot': 3, 'displaced': 8, 'untouched': [2, 4, 5], 'comparisons': 2}), ({'keys': [0, 9, 3, 4, 2, 8, 6, 7, 8, 5], 'start': 1}, {'path': [1, 4, 9], 'moved_keys': [2, 5], 'leaf_slot': 9, 'displaced': 9, 'untouched': [0, 2, 3, 5, 6, 7, 8], 'comparisons': 1}), ({'keys': [1, 4, 2, 5, 6, 7, 8], 'start': 2}, {'path': [2, 5], 'moved_keys': [7], 'leaf_slot': 5, 'displaced': 2, 'untouched': [0, 1, 3, 4, 6], 'comparisons': 1}), ({'keys': [6, 4, 2, 5, 6, 7, 8], 'start': 5}, {'path': [5], 'moved_keys': [], 'leaf_slot': 5, 'displaced': 7, 'untouched': [0, 1, 2, 3, 4, 6], 'comparisons': 0})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

meaning: Fixture-count band, not measured model difficulty

deps: stdlib

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

N = 1
observations = []
def solve(d):
    a=d['keys']; start=d['start']; path=[start]; moved=[]; compares=0; i=start
    while 2*i+1<len(a):
        l=2*i+1; r=l+1; j=l
        if r<len(a):
            compares+=1
            if a[r]<a[l]: j=r
        moved.append(a[j]); path.append(j); i=j
    return {'path': path,
    'moved_keys': moved,
    'leaf_slot': i,
    'displaced': a[start],
    'untouched': [j for j in range(len(a)) if j not in path],
    'comparisons': max(0,len(path)-2)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'keys': [5], 'start': 0}, {'path': [0], 'moved_keys': [], 'leaf_slot': 0, 'displaced': 5, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 2], 'start': 0}, {'path': [0, 1], 'moved_keys': [2], 'leaf_slot': 1, 'displaced': 9, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 5, 8, 2, 7, 6, 4], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [5, 2], 'leaf_slot': 3, 'displaced': 9, 'untouched': [2, 4, 5, 6], 'comparisons': 2}), ({'keys': [8, 2, 2, 5, 6, 7], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [2, 5], 'leaf_slot': 3, 'displaced': 8, 'untouched': [2, 4, 5], 'comparisons': 2}), ({'keys': [0, 9, 3, 4, 2, 8, 6, 7, 8, 5], 'start': 1}, {'path': [1, 4, 9], 'moved_keys': [2, 5], 'leaf_slot': 9, 'displaced': 9, 'untouched': [0, 2, 3, 5, 6, 7, 8], 'comparisons': 1}), ({'keys': [1, 4, 2, 5, 6, 7, 8], 'start': 2}, {'path': [2, 5], 'moved_keys': [7], 'leaf_slot': 5, 'displaced': 2, 'untouched': [0, 1, 3, 4, 6], 'comparisons': 1}), ({'keys': [2, 4, 2, 5, 6, 7, 8], 'start': 1}, {'path': [1, 3], 'moved_keys': [5], 'leaf_slot': 3, 'displaced': 4, 'untouched': [0, 2, 4, 5, 6], 'comparisons': 1})], [({'keys': [5], 'start': 0}, {'path': [0], 'moved_keys': [], 'leaf_slot': 0, 'displaced': 5, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 2], 'start': 0}, {'path': [0, 1], 'moved_keys': [2], 'leaf_slot': 1, 'displaced': 9, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 5, 8, 2, 7, 6, 4], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [5, 2], 'leaf_slot': 3, 'displaced': 9, 'untouched': [2, 4, 5, 6], 'comparisons': 2}), ({'keys': [8, 2, 2, 5, 6, 7], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [2, 5], 'leaf_slot': 3, 'displaced': 8, 'untouched': [2, 4, 5], 'comparisons': 2}), ({'keys': [0, 9, 3, 4, 2, 8, 6, 7, 8, 5], 'start': 1}, {'path': [1, 4, 9], 'moved_keys': [2, 5], 'leaf_slot': 9, 'displaced': 9, 'untouched': [0, 2, 3, 5, 6, 7, 8], 'comparisons': 1}), ({'keys': [1, 4, 2, 5, 6, 7, 8], 'start': 2}, {'path': [2, 5], 'moved_keys': [7], 'leaf_slot': 5, 'displaced': 2, 'untouched': [0, 1, 3, 4, 6], 'comparisons': 1}), ({'keys': [3, 4, 2, 5, 6, 7, 8], 'start': 2}, {'path': [2, 5], 'moved_keys': [7], 'leaf_slot': 5, 'displaced': 2, 'untouched': [0, 1, 3, 4, 6], 'comparisons': 1})], [({'keys': [5], 'start': 0}, {'path': [0], 'moved_keys': [], 'leaf_slot': 0, 'displaced': 5, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 2], 'start': 0}, {'path': [0, 1], 'moved_keys': [2], 'leaf_slot': 1, 'displaced': 9, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 5, 8, 2, 7, 6, 4], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [5, 2], 'leaf_slot': 3, 'displaced': 9, 'untouched': [2, 4, 5, 6], 'comparisons': 2}), ({'keys': [8, 2, 2, 5, 6, 7], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [2, 5], 'leaf_slot': 3, 'displaced': 8, 'untouched': [2, 4, 5], 'comparisons': 2}), ({'keys': [0, 9, 3, 4, 2, 8, 6, 7, 8, 5], 'start': 1}, {'path': [1, 4, 9], 'moved_keys': [2, 5], 'leaf_slot': 9, 'displaced': 9, 'untouched': [0, 2, 3, 5, 6, 7, 8], 'comparisons': 1}), ({'keys': [1, 4, 2, 5, 6, 7, 8], 'start': 2}, {'path': [2, 5], 'moved_keys': [7], 'leaf_slot': 5, 'displaced': 2, 'untouched': [0, 1, 3, 4, 6], 'comparisons': 1}), ({'keys': [4, 4, 2, 5, 6, 7, 8], 'start': 3}, {'path': [3], 'moved_keys': [], 'leaf_slot': 3, 'displaced': 5, 'untouched': [0, 1, 2, 4, 5, 6], 'comparisons': 0})], [({'keys': [5], 'start': 0}, {'path': [0], 'moved_keys': [], 'leaf_slot': 0, 'displaced': 5, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 2], 'start': 0}, {'path': [0, 1], 'moved_keys': [2], 'leaf_slot': 1, 'displaced': 9, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 5, 8, 2, 7, 6, 4], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [5, 2], 'leaf_slot': 3, 'displaced': 9, 'untouched': [2, 4, 5, 6], 'comparisons': 2}), ({'keys': [8, 2, 2, 5, 6, 7], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [2, 5], 'leaf_slot': 3, 'displaced': 8, 'untouched': [2, 4, 5], 'comparisons': 2}), ({'keys': [0, 9, 3, 4, 2, 8, 6, 7, 8, 5], 'start': 1}, {'path': [1, 4, 9], 'moved_keys': [2, 5], 'leaf_slot': 9, 'displaced': 9, 'untouched': [0, 2, 3, 5, 6, 7, 8], 'comparisons': 1}), ({'keys': [1, 4, 2, 5, 6, 7, 8], 'start': 2}, {'path': [2, 5], 'moved_keys': [7], 'leaf_slot': 5, 'displaced': 2, 'untouched': [0, 1, 3, 4, 6], 'comparisons': 1}), ({'keys': [5, 4, 2, 5, 6, 7, 8], 'start': 4}, {'path': [4], 'moved_keys': [], 'leaf_slot': 4, 'displaced': 6, 'untouched': [0, 1, 2, 3, 5, 6], 'comparisons': 0})], [({'keys': [5], 'start': 0}, {'path': [0], 'moved_keys': [], 'leaf_slot': 0, 'displaced': 5, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 2], 'start': 0}, {'path': [0, 1], 'moved_keys': [2], 'leaf_slot': 1, 'displaced': 9, 'untouched': [], 'comparisons': 0}), ({'keys': [9, 5, 8, 2, 7, 6, 4], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [5, 2], 'leaf_slot': 3, 'displaced': 9, 'untouched': [2, 4, 5, 6], 'comparisons': 2}), ({'keys': [8, 2, 2, 5, 6, 7], 'start': 0}, {'path': [0, 1, 3], 'moved_keys': [2, 5], 'leaf_slot': 3, 'displaced': 8, 'untouched': [2, 4, 5], 'comparisons': 2}), ({'keys': [0, 9, 3, 4, 2, 8, 6, 7, 8, 5], 'start': 1}, {'path': [1, 4, 9], 'moved_keys': [2, 5], 'leaf_slot': 9, 'displaced': 9, 'untouched': [0, 2, 3, 5, 6, 7, 8], 'comparisons': 1}), ({'keys': [1, 4, 2, 5, 6, 7, 8], 'start': 2}, {'path': [2, 5], 'moved_keys': [7], 'leaf_slot': 5, 'displaced': 2, 'untouched': [0, 1, 3, 4, 6], 'comparisons': 1}), ({'keys': [6, 4, 2, 5, 6, 7, 8], 'start': 5}, {'path': [5], 'moved_keys': [], 'leaf_slot': 5, 'displaced': 7, 'untouched': [0, 1, 2, 3, 4, 6], 'comparisons': 0})]][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 hole descent certificate reports an incorrect comparisons.

A binary heap hole descent receives array keys and starting internal or leaf index. Repeatedly choose smaller existing child (left on ties), move that child into the hole, and stop at a leaf; the displaced root value is returned separately for later upward placement. Return path, moved keys, leaf slot, displaced value, remaining untouched slots, and comparison count between sibling pairs.

split: open-access


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

N = 1
observations = []
def solve(d):
    nodes=d['nodes']; original=d['payloads']; p=[list(x) for x in original]; p[0][1]=d['new_key']; swaps=[]; i=0
    while i+1<len(p) and p[i][1]<p[i+1][1]:
        p[i],p[i+1]=p[i+1],p[i]; swaps.append([nodes[i],nodes[i+1]]); i+=1
    return {'payloads': [[original[k][0],x[1]] for k,x in enumerate(p)],
    'locations': {x[0]:nodes[k] for k,x in enumerate(p)},
    'swaps': swaps,
    'changed_location': nodes[i],
    'structural_nodes': nodes,
    'minimum': min(x[1] for x in p)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 2}, {'payloads': [['b', 7], ['c', 5], ['a', 2], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1})], [({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 1}, {'payloads': [['b', 7], ['c', 5], ['a', 1], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1})], [({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 0}, {'payloads': [['b', 7], ['c', 5], ['d', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'd': 12, 'a': 13}, 'swaps': [[10, 11], [11, 12], [12, 13]], 'changed_location': 13, 'structural_nodes': [10, 11, 12, 13], 'minimum': 0})], [({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': -1}, {'payloads': [['b', 7], ['c', 5], ['d', 1], ['a', -1]], 'locations': {'b': 10, 'c': 11, 'd': 12, 'a': 13}, 'swaps': [[10, 11], [11, 12], [12, 13]], 'changed_location': 13, 'structural_nodes': [10, 11, 12, 13], 'minimum': -1})], [({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': -2}, {'payloads': [['b', 7], ['c', 5], ['d', 1], ['a', -2]], 'locations': {'b': 10, 'c': 11, 'd': 12, 'a': 13}, 'swaps': [[10, 11], [11, 12], [12, 13]], 'changed_location': 13, 'structural_nodes': [10, 11, 12, 13], 'minimum': -2})]][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):
    nodes=d['nodes']; original=d['payloads']; p=[list(x) for x in original]; p[0][1]=d['new_key']; swaps=[]; i=0
    while i+1<len(p) and p[i][1]<p[i+1][1]:
        p[i],p[i+1]=p[i+1],p[i]; swaps.append([nodes[i],nodes[i+1]]); i+=1
    return {'payloads': [[x[0],original[k][1]] for k,x in enumerate(p)],
    'locations': {x[0]:nodes[k] for k,x in enumerate(p)},
    'swaps': swaps,
    'changed_location': nodes[i],
    'structural_nodes': nodes,
    'minimum': min(x[1] for x in p)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 2}, {'payloads': [['b', 7], ['c', 5], ['a', 2], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1})], [({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 1}, {'payloads': [['b', 7], ['c', 5], ['a', 1], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1})], [({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 0}, {'payloads': [['b', 7], ['c', 5], ['d', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'd': 12, 'a': 13}, 'swaps': [[10, 11], [11, 12], [12, 13]], 'changed_location': 13, 'structural_nodes': [10, 11, 12, 13], 'minimum': 0})], [({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': -1}, {'payloads': [['b', 7], ['c', 5], ['d', 1], ['a', -1]], 'locations': {'b': 10, 'c': 11, 'd': 12, 'a': 13}, 'swaps': [[10, 11], [11, 12], [12, 13]], 'changed_location': 13, 'structural_nodes': [10, 11, 12, 13], 'minimum': -1})], [({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': -2}, {'payloads': [['b', 7], ['c', 5], ['d', 1], ['a', -2]], 'locations': {'b': 10, 'c': 11, 'd': 12, 'a': 13}, 'swaps': [[10, 11], [11, 12], [12, 13]], 'changed_location': 13, 'structural_nodes': [10, 11, 12, 13], 'minimum': -2})]][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 binomial payload bubble certificate reports an incorrect payloads.

A binomial decrease-key bubble supplies the node-id path from leaf toward root, payloads [handle,key] at those nodes, and a decreased key for the first payload. While smaller than parent, exchange complete payloads. Structural nodes remain fixed; return final payload sequence, handle locations, swaps, decreased handle location, untouched structural path, and final minimum on this path.

split: open-access


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

N = 1
observations = []
def solve(d):
    nodes=d['nodes']; original=d['payloads']; p=[list(x) for x in original]; p[0][1]=d['new_key']; swaps=[]; i=0
    while i+1<len(p) and p[i][1]<p[i+1][1]:
        p[i],p[i+1]=p[i+1],p[i]; swaps.append([nodes[i],nodes[i+1]]); i+=1
    return {'payloads': p,
    'locations': {x[0]:nodes[k] for k,x in enumerate(original)},
    'swaps': swaps,
    'changed_location': nodes[i],
    'structural_nodes': nodes,
    'minimum': min(x[1] for x in p)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 2}, {'payloads': [['b', 7], ['c', 5], ['a', 2], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1})], [({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 1}, {'payloads': [['b', 7], ['c', 5], ['a', 1], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1})], [({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 0}, {'payloads': [['b', 7], ['c', 5], ['d', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'd': 12, 'a': 13}, 'swaps': [[10, 11], [11, 12], [12, 13]], 'changed_location': 13, 'structural_nodes': [10, 11, 12, 13], 'minimum': 0})], [({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': -1}, {'payloads': [['b', 7], ['c', 5], ['d', 1], ['a', -1]], 'locations': {'b': 10, 'c': 11, 'd': 12, 'a': 13}, 'swaps': [[10, 11], [11, 12], [12, 13]], 'changed_location': 13, 'structural_nodes': [10, 11, 12, 13], 'minimum': -1})], [({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': -2}, {'payloads': [['b', 7], ['c', 5], ['d', 1], ['a', -2]], 'locations': {'b': 10, 'c': 11, 'd': 12, 'a': 13}, 'swaps': [[10, 11], [11, 12], [12, 13]], 'changed_location': 13, 'structural_nodes': [10, 11, 12, 13], 'minimum': -2})]][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):
    nodes=d['nodes']; original=d['payloads']; p=[list(x) for x in original]; p[0][1]=d['new_key']; swaps=[]; i=0
    while i+1<len(p) and p[i][1]<p[i+1][1]:
        p[i],p[i+1]=p[i+1],p[i]; swaps.append([nodes[i],nodes[i+1]]); i+=1
    return {'payloads': p,
    'locations': {x[0]:k for k,x in enumerate(p)},
    'swaps': swaps,
    'changed_location': nodes[i],
    'structural_nodes': nodes,
    'minimum': min(x[1] for x in p)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 2}, {'payloads': [['b', 7], ['c', 5], ['a', 2], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1})], [({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 1}, {'payloads': [['b', 7], ['c', 5], ['a', 1], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1})], [({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 0}, {'payloads': [['b', 7], ['c', 5], ['d', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'd': 12, 'a': 13}, 'swaps': [[10, 11], [11, 12], [12, 13]], 'changed_location': 13, 'structural_nodes': [10, 11, 12, 13], 'minimum': 0})], [({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': -1}, {'payloads': [['b', 7], ['c', 5], ['d', 1], ['a', -1]], 'locations': {'b': 10, 'c': 11, 'd': 12, 'a': 13}, 'swaps': [[10, 11], [11, 12], [12, 13]], 'changed_location': 13, 'structural_nodes': [10, 11, 12, 13], 'minimum': -1})], [({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': -2}, {'payloads': [['b', 7], ['c', 5], ['d', 1], ['a', -2]], 'locations': {'b': 10, 'c': 11, 'd': 12, 'a': 13}, 'swaps': [[10, 11], [11, 12], [12, 13]], 'changed_location': 13, 'structural_nodes': [10, 11, 12, 13], 'minimum': -2})]][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 binomial payload bubble certificate reports an incorrect locations.

A binomial decrease-key bubble supplies the node-id path from leaf toward root, payloads [handle,key] at those nodes, and a decreased key for the first payload. While smaller than parent, exchange complete payloads. Structural nodes remain fixed; return final payload sequence, handle locations, swaps, decreased handle location, untouched structural path, and final minimum on this path.

split: open-access


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

N = 1
observations = []
def solve(d):
    nodes=d['nodes']; original=d['payloads']; p=[list(x) for x in original]; p[0][1]=d['new_key']; swaps=[]; i=0
    while i+1<len(p) and p[i][1]<p[i+1][1]:
        p[i],p[i+1]=p[i+1],p[i]; swaps.append([nodes[i],nodes[i+1]]); i+=1
    return {'payloads': p,
    'locations': {x[0]:nodes[k] for k,x in enumerate(p)},
    'swaps': list(reversed(swaps)),
    'changed_location': nodes[i],
    'structural_nodes': nodes,
    'minimum': min(x[1] for x in p)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 2}, {'payloads': [['b', 7], ['c', 5], ['a', 2], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1})], [({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 1}, {'payloads': [['b', 7], ['c', 5], ['a', 1], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1})], [({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 0}, {'payloads': [['b', 7], ['c', 5], ['d', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'd': 12, 'a': 13}, 'swaps': [[10, 11], [11, 12], [12, 13]], 'changed_location': 13, 'structural_nodes': [10, 11, 12, 13], 'minimum': 0})], [({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': -1}, {'payloads': [['b', 7], ['c', 5], ['d', 1], ['a', -1]], 'locations': {'b': 10, 'c': 11, 'd': 12, 'a': 13}, 'swaps': [[10, 11], [11, 12], [12, 13]], 'changed_location': 13, 'structural_nodes': [10, 11, 12, 13], 'minimum': -1})], [({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': -2}, {'payloads': [['b', 7], ['c', 5], ['d', 1], ['a', -2]], 'locations': {'b': 10, 'c': 11, 'd': 12, 'a': 13}, 'swaps': [[10, 11], [11, 12], [12, 13]], 'changed_location': 13, 'structural_nodes': [10, 11, 12, 13], 'minimum': -2})]][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):
    nodes=d['nodes']; original=d['payloads']; p=[list(x) for x in original]; p[0][1]=d['new_key']; swaps=[]; i=0
    while i+1<len(p) and p[i][1]<p[i+1][1]:
        p[i],p[i+1]=p[i+1],p[i]; swaps.append([nodes[i],nodes[i+1]]); i+=1
    return {'payloads': p,
    'locations': {x[0]:nodes[k] for k,x in enumerate(p)},
    'swaps': [[b,a] for a,b in swaps],
    'changed_location': nodes[i],
    'structural_nodes': nodes,
    'minimum': min(x[1] for x in p)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 2}, {'payloads': [['b', 7], ['c', 5], ['a', 2], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1})], [({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 1}, {'payloads': [['b', 7], ['c', 5], ['a', 1], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1})], [({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 0}, {'payloads': [['b', 7], ['c', 5], ['d', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'd': 12, 'a': 13}, 'swaps': [[10, 11], [11, 12], [12, 13]], 'changed_location': 13, 'structural_nodes': [10, 11, 12, 13], 'minimum': 0})], [({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': -1}, {'payloads': [['b', 7], ['c', 5], ['d', 1], ['a', -1]], 'locations': {'b': 10, 'c': 11, 'd': 12, 'a': 13}, 'swaps': [[10, 11], [11, 12], [12, 13]], 'changed_location': 13, 'structural_nodes': [10, 11, 12, 13], 'minimum': -1})], [({'nodes': [10], 'payloads': [['a', 5]], 'new_key': 4}, {'payloads': [['a', 4]], 'locations': {'a': 10}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10], 'minimum': 4}), ({'nodes': [10, 11], 'payloads': [['a', 8], ['b', 3]], 'new_key': 1}, {'payloads': [['b', 3], ['a', 1]], 'locations': {'b': 10, 'a': 11}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11], 'minimum': 1}), ({'nodes': [10, 11, 12], 'payloads': [['a', 9], ['b', 6], ['c', 2]], 'new_key': 4}, {'payloads': [['b', 6], ['a', 4], ['c', 2]], 'locations': {'b': 10, 'a': 11, 'c': 12}, 'swaps': [[10, 11]], 'changed_location': 11, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12], 'payloads': [['a', 7], ['b', 5], ['c', 1]], 'new_key': 0}, {'payloads': [['b', 5], ['c', 1], ['a', 0]], 'locations': {'b': 10, 'c': 11, 'a': 12}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12], 'minimum': 0}), ({'nodes': [10, 11, 12], 'payloads': [['a', 8], ['b', 5], ['c', 2]], 'new_key': 5}, {'payloads': [['a', 5], ['b', 5], ['c', 2]], 'locations': {'a': 10, 'b': 11, 'c': 12}, 'swaps': [], 'changed_location': 10, 'structural_nodes': [10, 11, 12], 'minimum': 2}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': 3}, {'payloads': [['b', 7], ['c', 5], ['a', 3], ['d', 1]], 'locations': {'b': 10, 'c': 11, 'a': 12, 'd': 13}, 'swaps': [[10, 11], [11, 12]], 'changed_location': 12, 'structural_nodes': [10, 11, 12, 13], 'minimum': 1}), ({'nodes': [10, 11, 12, 13], 'payloads': [['a', 9], ['b', 7], ['c', 5], ['d', 1]], 'new_key': -2}, {'payloads': [['b', 7], ['c', 5], ['d', 1], ['a', -2]], 'locations': {'b': 10, 'c': 11, 'd': 12, 'a': 13}, 'swaps': [[10, 11], [11, 12], [12, 13]], 'changed_location': 13, 'structural_nodes': [10, 11, 12, 13], 'minimum': -2})]][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 binomial payload bubble certificate reports an incorrect swaps.

A binomial decrease-key bubble supplies the node-id path from leaf toward root, payloads [handle,key] at those nodes, and a decreased key for the first payload. While smaller than parent, exchange complete payloads. Structural nodes remain fixed; return final payload sequence, handle locations, swaps, decreased handle location, untouched structural path, and final minimum on this path.

split: open-access