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

N = 1
observations = []
def solve(d):
    a=d['children']; pairs=[(a[i],a[i+1]) for i in range(0,len(a)-1,2)]
    wins=[x if x[1]<=y[1] else y for x,y in pairs]
    loses=[y if x[1]<=y[1] else x for x,y in pairs]
    first=wins+([a[-1]] if len(a)%2 else [])
    return {'pairs': [[i,i+1] for i in range(0,len(a)-1,2)],
    'winners': [x[0] for x in wins],
    'losers': [x[0] for x in loses],
    'carry': a[-1][0] if len(a)%2 else None,
    'fold_order': [x[0] for x in first],
    'comparisons': len(pairs)+max(0,len(first)-1)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': 100, 'fold_order': [100, 5, 6, 8], 'comparisons': 6})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 2], [101, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7]], 'winners': [8, 6, 5, 101], 'losers': [9, 7, 4, 100], 'carry': None, 'fold_order': [101, 5, 6, 8], 'comparisons': 7})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 3], [101, 2], [102, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7]], 'winners': [8, 6, 5, 101], 'losers': [9, 7, 4, 100], 'carry': 102, 'fold_order': [102, 101, 5, 6, 8], 'comparisons': 8})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 4], [101, 3], [102, 2], [103, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7], [8, 9]], 'winners': [8, 6, 5, 101, 103], 'losers': [9, 7, 4, 100, 102], 'carry': None, 'fold_order': [103, 101, 5, 6, 8], 'comparisons': 9})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 5], [101, 4], [102, 3], [103, 2], [104, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7], [8, 9]], 'winners': [8, 6, 5, 101, 103], 'losers': [9, 7, 4, 100, 102], 'carry': 104, 'fold_order': [104, 103, 101, 5, 6, 8], 'comparisons': 10})]][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['children']; pairs=[(a[i],a[i+1]) for i in range(0,len(a)-1,2)]
    wins=[x if x[1]<=y[1] else y for x,y in pairs]
    loses=[y if x[1]<=y[1] else x for x,y in pairs]
    first=wins+([a[-1]] if len(a)%2 else [])
    return {'pairs': [[i,i+1] for i in range(0,len(a)-1,2)],
    'winners': [x[0] for x in wins],
    'losers': [x[0] for x in loses],
    'carry': a[-1][0] if len(a)%2 else None,
    'fold_order': [x[0] for x in reversed(wins)],
    'comparisons': len(pairs)+max(0,len(first)-1)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': 100, 'fold_order': [100, 5, 6, 8], 'comparisons': 6})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 2], [101, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7]], 'winners': [8, 6, 5, 101], 'losers': [9, 7, 4, 100], 'carry': None, 'fold_order': [101, 5, 6, 8], 'comparisons': 7})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 3], [101, 2], [102, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7]], 'winners': [8, 6, 5, 101], 'losers': [9, 7, 4, 100], 'carry': 102, 'fold_order': [102, 101, 5, 6, 8], 'comparisons': 8})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 4], [101, 3], [102, 2], [103, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7], [8, 9]], 'winners': [8, 6, 5, 101, 103], 'losers': [9, 7, 4, 100, 102], 'carry': None, 'fold_order': [103, 101, 5, 6, 8], 'comparisons': 9})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 5], [101, 4], [102, 3], [103, 2], [104, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7], [8, 9]], 'winners': [8, 6, 5, 101, 103], 'losers': [9, 7, 4, 100, 102], 'carry': 104, 'fold_order': [104, 103, 101, 5, 6, 8], 'comparisons': 10})]][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 pairing pass certificate reports an incorrect fold order.

For delete-min pairing pass, children are [id,key]. Pair adjacent children left-to-right, keeping the left on equal keys. An odd last child survives. Return pair indices, winning ids, losing ids, odd carry id, second-pass traversal order, and comparison count. The second pass folds from right to left.

split: open-access


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

N = 1
observations = []
def solve(d):
    a=d['children']; pairs=[(a[i],a[i+1]) for i in range(0,len(a)-1,2)]
    wins=[x if x[1]<=y[1] else y for x,y in pairs]
    loses=[y if x[1]<=y[1] else x for x,y in pairs]
    first=wins+([a[-1]] if len(a)%2 else [])
    return {'pairs': [[i,i+1] for i in range(0,len(a)-1,2)],
    'winners': [x[0] for x in wins],
    'losers': [x[0] for x in loses],
    'carry': a[-1][0] if len(a)%2 else None,
    'fold_order': [x[0] for x in reversed(first)],
    'comparisons': len(pairs)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': 100, 'fold_order': [100, 5, 6, 8], 'comparisons': 6})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 2], [101, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7]], 'winners': [8, 6, 5, 101], 'losers': [9, 7, 4, 100], 'carry': None, 'fold_order': [101, 5, 6, 8], 'comparisons': 7})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 3], [101, 2], [102, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7]], 'winners': [8, 6, 5, 101], 'losers': [9, 7, 4, 100], 'carry': 102, 'fold_order': [102, 101, 5, 6, 8], 'comparisons': 8})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 4], [101, 3], [102, 2], [103, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7], [8, 9]], 'winners': [8, 6, 5, 101, 103], 'losers': [9, 7, 4, 100, 102], 'carry': None, 'fold_order': [103, 101, 5, 6, 8], 'comparisons': 9})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 5], [101, 4], [102, 3], [103, 2], [104, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7], [8, 9]], 'winners': [8, 6, 5, 101, 103], 'losers': [9, 7, 4, 100, 102], 'carry': 104, 'fold_order': [104, 103, 101, 5, 6, 8], 'comparisons': 10})]][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['children']; pairs=[(a[i],a[i+1]) for i in range(0,len(a)-1,2)]
    wins=[x if x[1]<=y[1] else y for x,y in pairs]
    loses=[y if x[1]<=y[1] else x for x,y in pairs]
    first=wins+([a[-1]] if len(a)%2 else [])
    return {'pairs': [[i,i+1] for i in range(0,len(a)-1,2)],
    'winners': [x[0] for x in wins],
    'losers': [x[0] for x in loses],
    'carry': a[-1][0] if len(a)%2 else None,
    'fold_order': [x[0] for x in reversed(first)],
    'comparisons': max(0,len(a)-2)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': 100, 'fold_order': [100, 5, 6, 8], 'comparisons': 6})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 2], [101, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7]], 'winners': [8, 6, 5, 101], 'losers': [9, 7, 4, 100], 'carry': None, 'fold_order': [101, 5, 6, 8], 'comparisons': 7})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 3], [101, 2], [102, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7]], 'winners': [8, 6, 5, 101], 'losers': [9, 7, 4, 100], 'carry': 102, 'fold_order': [102, 101, 5, 6, 8], 'comparisons': 8})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 4], [101, 3], [102, 2], [103, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7], [8, 9]], 'winners': [8, 6, 5, 101, 103], 'losers': [9, 7, 4, 100, 102], 'carry': None, 'fold_order': [103, 101, 5, 6, 8], 'comparisons': 9})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 5], [101, 4], [102, 3], [103, 2], [104, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7], [8, 9]], 'winners': [8, 6, 5, 101, 103], 'losers': [9, 7, 4, 100, 102], 'carry': 104, 'fold_order': [104, 103, 101, 5, 6, 8], 'comparisons': 10})]][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 pairing pass certificate reports an incorrect comparisons.

For delete-min pairing pass, children are [id,key]. Pair adjacent children left-to-right, keeping the left on equal keys. An odd last child survives. Return pair indices, winning ids, losing ids, odd carry id, second-pass traversal order, and comparison count. The second pass folds from right to left.

split: open-access


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

N = 1
observations = []
def solve(d):
    left=d['left']; right=d['right']; ln=-1 if left is None else left[1]; rn=-1 if right is None else right[1]
    l,r=(right,left) if ln<rn else (left,right)
    return {'left_id': left[0] if left else None,
    'right_id': r[0] if r else None,
    'npl': 1+(-1 if r is None else r[1]),
    'size': 1+sum(x[2] for x in (l,r) if x),
    'swap': ln<rn,
    'parent_assignments': [[x[0],d["root"]] for x in (l,r) if x]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 3], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 13, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 4], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 14, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 5], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 15, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 6], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 16, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 7], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 17, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})]][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):
    left=d['left']; right=d['right']; ln=-1 if left is None else left[1]; rn=-1 if right is None else right[1]
    l,r=(right,left) if ln<rn else (left,right)
    return {'left_id': right[0] if right else None,
    'right_id': r[0] if r else None,
    'npl': 1+(-1 if r is None else r[1]),
    'size': 1+sum(x[2] for x in (l,r) if x),
    'swap': ln<rn,
    'parent_assignments': [[x[0],d["root"]] for x in (l,r) if x]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 3], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 13, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 4], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 14, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 5], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 15, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 6], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 16, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 7], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 17, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})]][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 leftist meld step certificate reports an incorrect left id.

A leftist meld unwind record gives chosen root id, left subtree [id,npl,size] or None, returned right subtree similarly, and root key. Orient children by npl (null=-1), retain left on equal rank, set npl to right npl+1, and size to one plus both child sizes.

split: open-access


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

N = 1
observations = []
def solve(d):
    left=d['left']; right=d['right']; ln=-1 if left is None else left[1]; rn=-1 if right is None else right[1]
    l,r=(right,left) if ln<rn else (left,right)
    return {'left_id': l[0] if l else None,
    'right_id': right[0] if right else None,
    'npl': 1+(-1 if r is None else r[1]),
    'size': 1+sum(x[2] for x in (l,r) if x),
    'swap': ln<rn,
    'parent_assignments': [[x[0],d["root"]] for x in (l,r) if x]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 3], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 13, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 4], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 14, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 5], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 15, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 6], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 16, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 7], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 17, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})]][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):
    left=d['left']; right=d['right']; ln=-1 if left is None else left[1]; rn=-1 if right is None else right[1]
    l,r=(right,left) if ln<rn else (left,right)
    return {'left_id': l[0] if l else None,
    'right_id': left[0] if left else None,
    'npl': 1+(-1 if r is None else r[1]),
    'size': 1+sum(x[2] for x in (l,r) if x),
    'swap': ln<rn,
    'parent_assignments': [[x[0],d["root"]] for x in (l,r) if x]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 3], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 13, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 4], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 14, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 5], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 15, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 6], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 16, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 7], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 17, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})]][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 leftist meld step certificate reports an incorrect right id.

A leftist meld unwind record gives chosen root id, left subtree [id,npl,size] or None, returned right subtree similarly, and root key. Orient children by npl (null=-1), retain left on equal rank, set npl to right npl+1, and size to one plus both child sizes.

split: open-access


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

N = 1
observations = []
def solve(d):
    left=d['left']; right=d['right']; ln=-1 if left is None else left[1]; rn=-1 if right is None else right[1]
    l,r=(right,left) if ln<rn else (left,right)
    return {'left_id': l[0] if l else None,
    'right_id': r[0] if r else None,
    'npl': 1+(-1 if l is None else l[1]),
    'size': 1+sum(x[2] for x in (l,r) if x),
    'swap': ln<rn,
    'parent_assignments': [[x[0],d["root"]] for x in (l,r) if x]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 3], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 13, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 4], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 14, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 5], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 15, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 6], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 16, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 7], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 17, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})]][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):
    left=d['left']; right=d['right']; ln=-1 if left is None else left[1]; rn=-1 if right is None else right[1]
    l,r=(right,left) if ln<rn else (left,right)
    return {'left_id': l[0] if l else None,
    'right_id': r[0] if r else None,
    'npl': 0 if r is None else r[1],
    'size': 1+sum(x[2] for x in (l,r) if x),
    'swap': ln<rn,
    'parent_assignments': [[x[0],d["root"]] for x in (l,r) if x]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 3], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 13, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 4], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 14, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 5], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 15, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 6], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 16, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 7], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 17, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})]][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 leftist meld step certificate reports an incorrect npl.

A leftist meld unwind record gives chosen root id, left subtree [id,npl,size] or None, returned right subtree similarly, and root key. Orient children by npl (null=-1), retain left on equal rank, set npl to right npl+1, and size to one plus both child sizes.

split: open-access


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

N = 1
observations = []
def solve(d):
    left=d['left']; right=d['right']; ln=-1 if left is None else left[1]; rn=-1 if right is None else right[1]
    l,r=(right,left) if ln<rn else (left,right)
    return {'left_id': l[0] if l else None,
    'right_id': r[0] if r else None,
    'npl': 1+(-1 if r is None else r[1]),
    'size': sum(x[2] for x in (l,r) if x),
    'swap': ln<rn,
    'parent_assignments': [[x[0],d["root"]] for x in (l,r) if x]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 3], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 13, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 4], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 14, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 5], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 15, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 6], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 16, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 7], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 17, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})]][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):
    left=d['left']; right=d['right']; ln=-1 if left is None else left[1]; rn=-1 if right is None else right[1]
    l,r=(right,left) if ln<rn else (left,right)
    return {'left_id': l[0] if l else None,
    'right_id': r[0] if r else None,
    'npl': 1+(-1 if r is None else r[1]),
    'size': 1+max([x[2] for x in (l,r) if x],default=0),
    'swap': ln<rn,
    'parent_assignments': [[x[0],d["root"]] for x in (l,r) if x]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 3], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 13, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 4], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 14, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 5], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 15, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 6], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 16, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 7], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 17, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})]][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 leftist meld step certificate reports an incorrect size.

A leftist meld unwind record gives chosen root id, left subtree [id,npl,size] or None, returned right subtree similarly, and root key. Orient children by npl (null=-1), retain left on equal rank, set npl to right npl+1, and size to one plus both child sizes.

split: open-access