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': 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': 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 swap.

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': 1+sum(x[2] for x in (l,r) if x),
    'swap': ln<rn,
    'parent_assignments': [[x[0],d["root"]] for x in (l,) 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)

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):
    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+sum(x[2] for x in (l,r) if x),
    'swap': ln<rn,
    'parent_assignments': [[d["root"],x[0]] 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 parent assignments.

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

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

N = 1
observations = []
def solve(d):
    old=d['old_left']; result=d['result']; sizes=d['sizes']
    return {'new_left': result if old is None else old,
    'new_right': old,
    'size': 1+sum(sizes),
    'rewrites': [[x,d["winner"]] for x in (result,old) if x is not None],
    'preorder_children': [x for x in (result,old) if x is not None],
    'leaf': old is None and result is None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [8, 10]}, {'new_left': 8, 'new_right': 4, 'size': 19, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [9, 11]}, {'new_left': 8, 'new_right': 4, 'size': 21, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [10, 12]}, {'new_left': 8, 'new_right': 4, 'size': 23, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [11, 13]}, {'new_left': 8, 'new_right': 4, 'size': 25, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [12, 14]}, {'new_left': 8, 'new_right': 4, 'size': 27, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
The bounded skew meld step certificate reports an incorrect new left.

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

split: open-access


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

N = 1
observations = []
def solve(d):
    old=d['old_left']; result=d['result']; sizes=d['sizes']
    return {'new_left': result,
    'new_right': result,
    'size': 1+sum(sizes),
    'rewrites': [[x,d["winner"]] for x in (result,old) if x is not None],
    'preorder_children': [x for x in (result,old) if x is not None],
    'leaf': old is None and result is None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [8, 10]}, {'new_left': 8, 'new_right': 4, 'size': 19, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [9, 11]}, {'new_left': 8, 'new_right': 4, 'size': 21, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [10, 12]}, {'new_left': 8, 'new_right': 4, 'size': 23, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [11, 13]}, {'new_left': 8, 'new_right': 4, 'size': 25, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [12, 14]}, {'new_left': 8, 'new_right': 4, 'size': 27, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

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

N = 1
observations = []
def solve(d):
    old=d['old_left']; result=d['result']; sizes=d['sizes']
    return {'new_left': result,
    'new_right': None,
    'size': 1+sum(sizes),
    'rewrites': [[x,d["winner"]] for x in (result,old) if x is not None],
    'preorder_children': [x for x in (result,old) if x is not None],
    'leaf': old is None and result is None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [8, 10]}, {'new_left': 8, 'new_right': 4, 'size': 19, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [9, 11]}, {'new_left': 8, 'new_right': 4, 'size': 21, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [10, 12]}, {'new_left': 8, 'new_right': 4, 'size': 23, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [11, 13]}, {'new_left': 8, 'new_right': 4, 'size': 25, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [12, 14]}, {'new_left': 8, 'new_right': 4, 'size': 27, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
The bounded skew meld step certificate reports an incorrect new right.

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

split: open-access


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

N = 1
observations = []
def solve(d):
    old=d['old_left']; result=d['result']; sizes=d['sizes']
    return {'new_left': result,
    'new_right': old,
    'size': max(sizes,default=0)+1,
    'rewrites': [[x,d["winner"]] for x in (result,old) if x is not None],
    'preorder_children': [x for x in (result,old) if x is not None],
    'leaf': old is None and result is None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [8, 10]}, {'new_left': 8, 'new_right': 4, 'size': 19, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [9, 11]}, {'new_left': 8, 'new_right': 4, 'size': 21, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [10, 12]}, {'new_left': 8, 'new_right': 4, 'size': 23, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [11, 13]}, {'new_left': 8, 'new_right': 4, 'size': 25, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [12, 14]}, {'new_left': 8, 'new_right': 4, 'size': 27, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

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

N = 1
observations = []
def solve(d):
    old=d['old_left']; result=d['result']; sizes=d['sizes']
    return {'new_left': result,
    'new_right': old,
    'size': sum(sizes),
    'rewrites': [[x,d["winner"]] for x in (result,old) if x is not None],
    'preorder_children': [x for x in (result,old) if x is not None],
    'leaf': old is None and result is None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [8, 10]}, {'new_left': 8, 'new_right': 4, 'size': 19, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [9, 11]}, {'new_left': 8, 'new_right': 4, 'size': 21, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [10, 12]}, {'new_left': 8, 'new_right': 4, 'size': 23, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [11, 13]}, {'new_left': 8, 'new_right': 4, 'size': 25, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [12, 14]}, {'new_left': 8, 'new_right': 4, 'size': 27, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
The bounded skew meld step certificate reports an incorrect size.

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

split: open-access


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

N = 1
observations = []
def solve(d):
    old=d['old_left']; result=d['result']; sizes=d['sizes']
    return {'new_left': result,
    'new_right': old,
    'size': 1+sum(sizes),
    'rewrites': [[x,d["winner"]] for x in (result,) if x is not None],
    'preorder_children': [x for x in (result,old) if x is not None],
    'leaf': old is None and result is None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [8, 10]}, {'new_left': 8, 'new_right': 4, 'size': 19, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [9, 11]}, {'new_left': 8, 'new_right': 4, 'size': 21, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [10, 12]}, {'new_left': 8, 'new_right': 4, 'size': 23, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [11, 13]}, {'new_left': 8, 'new_right': 4, 'size': 25, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [12, 14]}, {'new_left': 8, 'new_right': 4, 'size': 27, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

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

N = 1
observations = []
def solve(d):
    old=d['old_left']; result=d['result']; sizes=d['sizes']
    return {'new_left': result,
    'new_right': old,
    'size': 1+sum(sizes),
    'rewrites': [[d["winner"],x] for x in (result,old) if x is not None],
    'preorder_children': [x for x in (result,old) if x is not None],
    'leaf': old is None and result is None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [8, 10]}, {'new_left': 8, 'new_right': 4, 'size': 19, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [9, 11]}, {'new_left': 8, 'new_right': 4, 'size': 21, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [10, 12]}, {'new_left': 8, 'new_right': 4, 'size': 23, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [11, 13]}, {'new_left': 8, 'new_right': 4, 'size': 25, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [12, 14]}, {'new_left': 8, 'new_right': 4, 'size': 27, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
The bounded skew meld step certificate reports an incorrect rewrites.

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

split: open-access