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

N = 1
observations = []
def solve(d):
    x=d['x']; g=d['g']; p=d['p']; descend=g<x; correction=descend and x>p
    root=g if descend else x; gc=(p if correction else x) if descend else g; parent=x if correction else p
    return {'root_key': min(x,p),
    'grandchild_key': gc,
    'parent_key': parent,
    'correction': correction,
    'trace': (["grandchild"]+["parent"] if correction else ["grandchild"]) if descend else [],
    'multiset': sorted([root,gc,parent])}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 10, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 10, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 10]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 11, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 11, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 11]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 12, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 12, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 12]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 13, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 13, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 13]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 14, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 14, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 14]})]][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):
    x=d['x']; g=d['g']; p=d['p']; descend=g<x; correction=descend and x>p
    root=g if descend else x; gc=(p if correction else x) if descend else g; parent=x if correction else p
    return {'root_key': x,
    'grandchild_key': gc,
    'parent_key': parent,
    'correction': correction,
    'trace': (["grandchild"]+["parent"] if correction else ["grandchild"]) if descend else [],
    'multiset': sorted([root,gc,parent])}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 10, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 10, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 10]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 11, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 11, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 11]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 12, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 12, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 12]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 13, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 13, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 13]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 14, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 14, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 14]})]][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 minmax grandchild step certificate reports an incorrect root key.

A minimum-level trickle step receives current key x, chosen grandchild key g, its parent key p, and ids. After swapping x with smaller g, x at the grandchild must also be no greater than its maximum-level parent; if x>p exchange those two. Return root key, grandchild key, parent key, cross-level correction flag, two-step trace, and preserved multiset.

split: open-access


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

N = 1
observations = []
def solve(d):
    x=d['x']; g=d['g']; p=d['p']; descend=g<x; correction=descend and x>p
    root=g if descend else x; gc=(p if correction else x) if descend else g; parent=x if correction else p
    return {'root_key': root,
    'grandchild_key': x if descend else g,
    'parent_key': parent,
    'correction': correction,
    'trace': (["grandchild"]+["parent"] if correction else ["grandchild"]) if descend else [],
    'multiset': sorted([root,gc,parent])}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 10, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 10, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 10]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 11, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 11, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 11]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 12, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 12, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 12]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 13, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 13, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 13]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 14, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 14, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 14]})]][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):
    x=d['x']; g=d['g']; p=d['p']; descend=g<x; correction=descend and x>p
    root=g if descend else x; gc=(p if correction else x) if descend else g; parent=x if correction else p
    return {'root_key': root,
    'grandchild_key': g,
    'parent_key': parent,
    'correction': correction,
    'trace': (["grandchild"]+["parent"] if correction else ["grandchild"]) if descend else [],
    'multiset': sorted([root,gc,parent])}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 10, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 10, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 10]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 11, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 11, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 11]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 12, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 12, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 12]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 13, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 13, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 13]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 14, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 14, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 14]})]][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 minmax grandchild step certificate reports an incorrect grandchild key.

A minimum-level trickle step receives current key x, chosen grandchild key g, its parent key p, and ids. After swapping x with smaller g, x at the grandchild must also be no greater than its maximum-level parent; if x>p exchange those two. Return root key, grandchild key, parent key, cross-level correction flag, two-step trace, and preserved multiset.

split: open-access


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

N = 1
observations = []
def solve(d):
    x=d['x']; g=d['g']; p=d['p']; descend=g<x; correction=descend and x>p
    root=g if descend else x; gc=(p if correction else x) if descend else g; parent=x if correction else p
    return {'root_key': root,
    'grandchild_key': gc,
    'parent_key': p,
    'correction': correction,
    'trace': (["grandchild"]+["parent"] if correction else ["grandchild"]) if descend else [],
    'multiset': sorted([root,gc,parent])}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 10, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 10, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 10]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 11, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 11, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 11]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 12, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 12, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 12]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 13, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 13, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 13]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 14, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 14, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 14]})]][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):
    x=d['x']; g=d['g']; p=d['p']; descend=g<x; correction=descend and x>p
    root=g if descend else x; gc=(p if correction else x) if descend else g; parent=x if correction else p
    return {'root_key': root,
    'grandchild_key': gc,
    'parent_key': x if descend else p,
    'correction': correction,
    'trace': (["grandchild"]+["parent"] if correction else ["grandchild"]) if descend else [],
    'multiset': sorted([root,gc,parent])}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 10, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 10, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 10]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 11, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 11, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 11]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 12, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 12, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 12]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 13, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 13, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 13]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 14, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 14, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 14]})]][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 minmax grandchild step certificate reports an incorrect parent key.

A minimum-level trickle step receives current key x, chosen grandchild key g, its parent key p, and ids. After swapping x with smaller g, x at the grandchild must also be no greater than its maximum-level parent; if x>p exchange those two. Return root key, grandchild key, parent key, cross-level correction flag, two-step trace, and preserved multiset.

split: open-access


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

N = 1
observations = []
def solve(d):
    x=d['x']; g=d['g']; p=d['p']; descend=g<x; correction=descend and x>p
    root=g if descend else x; gc=(p if correction else x) if descend else g; parent=x if correction else p
    return {'root_key': root,
    'grandchild_key': gc,
    'parent_key': parent,
    'correction': descend,
    'trace': (["grandchild"]+["parent"] if correction else ["grandchild"]) if descend else [],
    'multiset': sorted([root,gc,parent])}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 10, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 10, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 10]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 11, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 11, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 11]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 12, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 12, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 12]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 13, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 13, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 13]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 14, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 14, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 14]})]][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):
    x=d['x']; g=d['g']; p=d['p']; descend=g<x; correction=descend and x>p
    root=g if descend else x; gc=(p if correction else x) if descend else g; parent=x if correction else p
    return {'root_key': root,
    'grandchild_key': gc,
    'parent_key': parent,
    'correction': descend and x<p,
    'trace': (["grandchild"]+["parent"] if correction else ["grandchild"]) if descend else [],
    'multiset': sorted([root,gc,parent])}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 10, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 10, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 10]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 11, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 11, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 11]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 12, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 12, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 12]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 13, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 13, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 13]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 14, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 14, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 14]})]][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 minmax grandchild step certificate reports an incorrect correction.

A minimum-level trickle step receives current key x, chosen grandchild key g, its parent key p, and ids. After swapping x with smaller g, x at the grandchild must also be no greater than its maximum-level parent; if x>p exchange those two. Return root key, grandchild key, parent key, cross-level correction flag, two-step trace, and preserved multiset.

split: open-access


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

N = 1
observations = []
def solve(d):
    x=d['x']; g=d['g']; p=d['p']; descend=g<x; correction=descend and x>p
    root=g if descend else x; gc=(p if correction else x) if descend else g; parent=x if correction else p
    return {'root_key': root,
    'grandchild_key': gc,
    'parent_key': parent,
    'correction': correction,
    'trace': ["grandchild"] if descend else [],
    'multiset': sorted([root,gc,parent])}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 10, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 10, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 10]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 11, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 11, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 11]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 12, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 12, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 12]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 13, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 13, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 13]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 14, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 14, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 14]})]][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):
    x=d['x']; g=d['g']; p=d['p']; descend=g<x; correction=descend and x>p
    root=g if descend else x; gc=(p if correction else x) if descend else g; parent=x if correction else p
    return {'root_key': root,
    'grandchild_key': gc,
    'parent_key': parent,
    'correction': correction,
    'trace': ["parent","grandchild"] if correction else ["grandchild"] if descend else [],
    'multiset': sorted([root,gc,parent])}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 10, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 10, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 10]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 11, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 11, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 11]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 12, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 12, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 12]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 13, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 13, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 13]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 14, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 14, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 14]})]][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 minmax grandchild step certificate reports an incorrect trace.

A minimum-level trickle step receives current key x, chosen grandchild key g, its parent key p, and ids. After swapping x with smaller g, x at the grandchild must also be no greater than its maximum-level parent; if x>p exchange those two. Return root key, grandchild key, parent key, cross-level correction flag, two-step trace, and preserved multiset.

split: open-access


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

N = 1
observations = []
def solve(d):
    x=d['x']; g=d['g']; p=d['p']; descend=g<x; correction=descend and x>p
    root=g if descend else x; gc=(p if correction else x) if descend else g; parent=x if correction else p
    return {'root_key': root,
    'grandchild_key': gc,
    'parent_key': parent,
    'correction': correction,
    'trace': (["grandchild"]+["parent"] if correction else ["grandchild"]) if descend else [],
    'multiset': sorted([root,x,p])}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 10, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 10, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 10]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 11, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 11, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 11]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 12, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 12, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 12]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 13, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 13, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 13]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 14, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 14, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 14]})]][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):
    x=d['x']; g=d['g']; p=d['p']; descend=g<x; correction=descend and x>p
    root=g if descend else x; gc=(p if correction else x) if descend else g; parent=x if correction else p
    return {'root_key': root,
    'grandchild_key': gc,
    'parent_key': parent,
    'correction': correction,
    'trace': (["grandchild"]+["parent"] if correction else ["grandchild"]) if descend else [],
    'multiset': sorted(set([root,gc,parent]))}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 10, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 10, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 10]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 11, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 11, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 11]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 12, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 12, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 12]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 13, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 13, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 13]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 14, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 14, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 14]})]][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 minmax grandchild step certificate reports an incorrect multiset.

A minimum-level trickle step receives current key x, chosen grandchild key g, its parent key p, and ids. After swapping x with smaller g, x at the grandchild must also be no greater than its maximum-level parent; if x>p exchange those two. Return root key, grandchild key, parent key, cross-level correction flag, two-step trace, and preserved multiset.

split: open-access


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

N = 1
observations = []
def solve(d):
    a=d['intervals']; side=d['side']; tail=a[-1] if a else []; k=0 if side=='low' else -1; v=tail[k] if tail else None; rest=tail[1:] if side=='low' else tail[:-1]; out=a[:-1]+([rest] if rest else []) if a else []
    return {'replacement': tail[-1] if tail else None,
    'remaining': out,
    'size': sum(map(len,out)),
    'singleton': bool(out) and len(out[-1])==1,
    'survivor': rest[0] if rest else None,
    'nodes': len(out)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'intervals': [], 'side': 'low'}, {'replacement': None, 'remaining': [], 'size': 0, 'singleton': False, 'survivor': None, 'nodes': 0}), ({'intervals': [[4]], 'side': 'high'}, {'replacement': 4, 'remaining': [], 'size': 0, 'singleton': False, 'survivor': None, 'nodes': 0}), ({'intervals': [[1, 9]], 'side': 'low'}, {'replacement': 1, 'remaining': [[9]], 'size': 1, 'singleton': True, 'survivor': 9, 'nodes': 1}), ({'intervals': [[1, 9], [3, 7]], 'side': 'high'}, {'replacement': 7, 'remaining': [[1, 9], [3]], 'size': 3, 'singleton': True, 'survivor': 3, 'nodes': 2}), ({'intervals': [[1, 9], [3]], 'side': 'low'}, {'replacement': 3, 'remaining': [[1, 9]], 'size': 2, 'singleton': False, 'survivor': None, 'nodes': 1}), ({'intervals': [[1, 9], [2, 8], [4, 6]], 'side': 'low'}, {'replacement': 4, 'remaining': [[1, 9], [2, 8], [6]], 'size': 5, 'singleton': True, 'survivor': 6, 'nodes': 3}), ({'intervals': [[1, 9], [2, 8], [4, 7]], 'side': 'low'}, {'replacement': 4, 'remaining': [[1, 9], [2, 8], [7]], 'size': 5, 'singleton': True, 'survivor': 7, 'nodes': 3})], [({'intervals': [], 'side': 'low'}, {'replacement': None, 'remaining': [], 'size': 0, 'singleton': False, 'survivor': None, 'nodes': 0}), ({'intervals': [[4]], 'side': 'high'}, {'replacement': 4, 'remaining': [], 'size': 0, 'singleton': False, 'survivor': None, 'nodes': 0}), ({'intervals': [[1, 9]], 'side': 'low'}, {'replacement': 1, 'remaining': [[9]], 'size': 1, 'singleton': True, 'survivor': 9, 'nodes': 1}), ({'intervals': [[1, 9], [3, 7]], 'side': 'high'}, {'replacement': 7, 'remaining': [[1, 9], [3]], 'size': 3, 'singleton': True, 'survivor': 3, 'nodes': 2}), ({'intervals': [[1, 9], [3]], 'side': 'low'}, {'replacement': 3, 'remaining': [[1, 9]], 'size': 2, 'singleton': False, 'survivor': None, 'nodes': 1}), ({'intervals': [[1, 9], [2, 8], [4, 6]], 'side': 'low'}, {'replacement': 4, 'remaining': [[1, 9], [2, 8], [6]], 'size': 5, 'singleton': True, 'survivor': 6, 'nodes': 3}), ({'intervals': [[1, 9], [2, 8], [4, 8]], 'side': 'low'}, {'replacement': 4, 'remaining': [[1, 9], [2, 8], [8]], 'size': 5, 'singleton': True, 'survivor': 8, 'nodes': 3})], [({'intervals': [], 'side': 'low'}, {'replacement': None, 'remaining': [], 'size': 0, 'singleton': False, 'survivor': None, 'nodes': 0}), ({'intervals': [[4]], 'side': 'high'}, {'replacement': 4, 'remaining': [], 'size': 0, 'singleton': False, 'survivor': None, 'nodes': 0}), ({'intervals': [[1, 9]], 'side': 'low'}, {'replacement': 1, 'remaining': [[9]], 'size': 1, 'singleton': True, 'survivor': 9, 'nodes': 1}), ({'intervals': [[1, 9], [3, 7]], 'side': 'high'}, {'replacement': 7, 'remaining': [[1, 9], [3]], 'size': 3, 'singleton': True, 'survivor': 3, 'nodes': 2}), ({'intervals': [[1, 9], [3]], 'side': 'low'}, {'replacement': 3, 'remaining': [[1, 9]], 'size': 2, 'singleton': False, 'survivor': None, 'nodes': 1}), ({'intervals': [[1, 9], [2, 8], [4, 6]], 'side': 'low'}, {'replacement': 4, 'remaining': [[1, 9], [2, 8], [6]], 'size': 5, 'singleton': True, 'survivor': 6, 'nodes': 3}), ({'intervals': [[1, 9], [2, 8], [4, 9]], 'side': 'low'}, {'replacement': 4, 'remaining': [[1, 9], [2, 8], [9]], 'size': 5, 'singleton': True, 'survivor': 9, 'nodes': 3})], [({'intervals': [], 'side': 'low'}, {'replacement': None, 'remaining': [], 'size': 0, 'singleton': False, 'survivor': None, 'nodes': 0}), ({'intervals': [[4]], 'side': 'high'}, {'replacement': 4, 'remaining': [], 'size': 0, 'singleton': False, 'survivor': None, 'nodes': 0}), ({'intervals': [[1, 9]], 'side': 'low'}, {'replacement': 1, 'remaining': [[9]], 'size': 1, 'singleton': True, 'survivor': 9, 'nodes': 1}), ({'intervals': [[1, 9], [3, 7]], 'side': 'high'}, {'replacement': 7, 'remaining': [[1, 9], [3]], 'size': 3, 'singleton': True, 'survivor': 3, 'nodes': 2}), ({'intervals': [[1, 9], [3]], 'side': 'low'}, {'replacement': 3, 'remaining': [[1, 9]], 'size': 2, 'singleton': False, 'survivor': None, 'nodes': 1}), ({'intervals': [[1, 9], [2, 8], [4, 6]], 'side': 'low'}, {'replacement': 4, 'remaining': [[1, 9], [2, 8], [6]], 'size': 5, 'singleton': True, 'survivor': 6, 'nodes': 3}), ({'intervals': [[1, 9], [2, 8], [4, 10]], 'side': 'low'}, {'replacement': 4, 'remaining': [[1, 9], [2, 8], [10]], 'size': 5, 'singleton': True, 'survivor': 10, 'nodes': 3})], [({'intervals': [], 'side': 'low'}, {'replacement': None, 'remaining': [], 'size': 0, 'singleton': False, 'survivor': None, 'nodes': 0}), ({'intervals': [[4]], 'side': 'high'}, {'replacement': 4, 'remaining': [], 'size': 0, 'singleton': False, 'survivor': None, 'nodes': 0}), ({'intervals': [[1, 9]], 'side': 'low'}, {'replacement': 1, 'remaining': [[9]], 'size': 1, 'singleton': True, 'survivor': 9, 'nodes': 1}), ({'intervals': [[1, 9], [3, 7]], 'side': 'high'}, {'replacement': 7, 'remaining': [[1, 9], [3]], 'size': 3, 'singleton': True, 'survivor': 3, 'nodes': 2}), ({'intervals': [[1, 9], [3]], 'side': 'low'}, {'replacement': 3, 'remaining': [[1, 9]], 'size': 2, 'singleton': False, 'survivor': None, 'nodes': 1}), ({'intervals': [[1, 9], [2, 8], [4, 6]], 'side': 'low'}, {'replacement': 4, 'remaining': [[1, 9], [2, 8], [6]], 'size': 5, 'singleton': True, 'survivor': 6, 'nodes': 3}), ({'intervals': [[1, 9], [2, 8], [4, 11]], 'side': 'low'}, {'replacement': 4, 'remaining': [[1, 9], [2, 8], [11]], 'size': 5, 'singleton': True, 'survivor': 11, 'nodes': 3})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

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

N = 1
observations = []
def solve(d):
    a=d['intervals']; side=d['side']; tail=a[-1] if a else []; k=0 if side=='low' else -1; v=tail[k] if tail else None; rest=tail[1:] if side=='low' else tail[:-1]; out=a[:-1]+([rest] if rest else []) if a else []
    return {'replacement': tail[0] if tail else None,
    'remaining': out,
    'size': sum(map(len,out)),
    'singleton': bool(out) and len(out[-1])==1,
    'survivor': rest[0] if rest else None,
    'nodes': len(out)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'intervals': [], 'side': 'low'}, {'replacement': None, 'remaining': [], 'size': 0, 'singleton': False, 'survivor': None, 'nodes': 0}), ({'intervals': [[4]], 'side': 'high'}, {'replacement': 4, 'remaining': [], 'size': 0, 'singleton': False, 'survivor': None, 'nodes': 0}), ({'intervals': [[1, 9]], 'side': 'low'}, {'replacement': 1, 'remaining': [[9]], 'size': 1, 'singleton': True, 'survivor': 9, 'nodes': 1}), ({'intervals': [[1, 9], [3, 7]], 'side': 'high'}, {'replacement': 7, 'remaining': [[1, 9], [3]], 'size': 3, 'singleton': True, 'survivor': 3, 'nodes': 2}), ({'intervals': [[1, 9], [3]], 'side': 'low'}, {'replacement': 3, 'remaining': [[1, 9]], 'size': 2, 'singleton': False, 'survivor': None, 'nodes': 1}), ({'intervals': [[1, 9], [2, 8], [4, 6]], 'side': 'low'}, {'replacement': 4, 'remaining': [[1, 9], [2, 8], [6]], 'size': 5, 'singleton': True, 'survivor': 6, 'nodes': 3}), ({'intervals': [[1, 9], [2, 8], [4, 7]], 'side': 'low'}, {'replacement': 4, 'remaining': [[1, 9], [2, 8], [7]], 'size': 5, 'singleton': True, 'survivor': 7, 'nodes': 3})], [({'intervals': [], 'side': 'low'}, {'replacement': None, 'remaining': [], 'size': 0, 'singleton': False, 'survivor': None, 'nodes': 0}), ({'intervals': [[4]], 'side': 'high'}, {'replacement': 4, 'remaining': [], 'size': 0, 'singleton': False, 'survivor': None, 'nodes': 0}), ({'intervals': [[1, 9]], 'side': 'low'}, {'replacement': 1, 'remaining': [[9]], 'size': 1, 'singleton': True, 'survivor': 9, 'nodes': 1}), ({'intervals': [[1, 9], [3, 7]], 'side': 'high'}, {'replacement': 7, 'remaining': [[1, 9], [3]], 'size': 3, 'singleton': True, 'survivor': 3, 'nodes': 2}), ({'intervals': [[1, 9], [3]], 'side': 'low'}, {'replacement': 3, 'remaining': [[1, 9]], 'size': 2, 'singleton': False, 'survivor': None, 'nodes': 1}), ({'intervals': [[1, 9], [2, 8], [4, 6]], 'side': 'low'}, {'replacement': 4, 'remaining': [[1, 9], [2, 8], [6]], 'size': 5, 'singleton': True, 'survivor': 6, 'nodes': 3}), ({'intervals': [[1, 9], [2, 8], [4, 8]], 'side': 'low'}, {'replacement': 4, 'remaining': [[1, 9], [2, 8], [8]], 'size': 5, 'singleton': True, 'survivor': 8, 'nodes': 3})], [({'intervals': [], 'side': 'low'}, {'replacement': None, 'remaining': [], 'size': 0, 'singleton': False, 'survivor': None, 'nodes': 0}), ({'intervals': [[4]], 'side': 'high'}, {'replacement': 4, 'remaining': [], 'size': 0, 'singleton': False, 'survivor': None, 'nodes': 0}), ({'intervals': [[1, 9]], 'side': 'low'}, {'replacement': 1, 'remaining': [[9]], 'size': 1, 'singleton': True, 'survivor': 9, 'nodes': 1}), ({'intervals': [[1, 9], [3, 7]], 'side': 'high'}, {'replacement': 7, 'remaining': [[1, 9], [3]], 'size': 3, 'singleton': True, 'survivor': 3, 'nodes': 2}), ({'intervals': [[1, 9], [3]], 'side': 'low'}, {'replacement': 3, 'remaining': [[1, 9]], 'size': 2, 'singleton': False, 'survivor': None, 'nodes': 1}), ({'intervals': [[1, 9], [2, 8], [4, 6]], 'side': 'low'}, {'replacement': 4, 'remaining': [[1, 9], [2, 8], [6]], 'size': 5, 'singleton': True, 'survivor': 6, 'nodes': 3}), ({'intervals': [[1, 9], [2, 8], [4, 9]], 'side': 'low'}, {'replacement': 4, 'remaining': [[1, 9], [2, 8], [9]], 'size': 5, 'singleton': True, 'survivor': 9, 'nodes': 3})], [({'intervals': [], 'side': 'low'}, {'replacement': None, 'remaining': [], 'size': 0, 'singleton': False, 'survivor': None, 'nodes': 0}), ({'intervals': [[4]], 'side': 'high'}, {'replacement': 4, 'remaining': [], 'size': 0, 'singleton': False, 'survivor': None, 'nodes': 0}), ({'intervals': [[1, 9]], 'side': 'low'}, {'replacement': 1, 'remaining': [[9]], 'size': 1, 'singleton': True, 'survivor': 9, 'nodes': 1}), ({'intervals': [[1, 9], [3, 7]], 'side': 'high'}, {'replacement': 7, 'remaining': [[1, 9], [3]], 'size': 3, 'singleton': True, 'survivor': 3, 'nodes': 2}), ({'intervals': [[1, 9], [3]], 'side': 'low'}, {'replacement': 3, 'remaining': [[1, 9]], 'size': 2, 'singleton': False, 'survivor': None, 'nodes': 1}), ({'intervals': [[1, 9], [2, 8], [4, 6]], 'side': 'low'}, {'replacement': 4, 'remaining': [[1, 9], [2, 8], [6]], 'size': 5, 'singleton': True, 'survivor': 6, 'nodes': 3}), ({'intervals': [[1, 9], [2, 8], [4, 10]], 'side': 'low'}, {'replacement': 4, 'remaining': [[1, 9], [2, 8], [10]], 'size': 5, 'singleton': True, 'survivor': 10, 'nodes': 3})], [({'intervals': [], 'side': 'low'}, {'replacement': None, 'remaining': [], 'size': 0, 'singleton': False, 'survivor': None, 'nodes': 0}), ({'intervals': [[4]], 'side': 'high'}, {'replacement': 4, 'remaining': [], 'size': 0, 'singleton': False, 'survivor': None, 'nodes': 0}), ({'intervals': [[1, 9]], 'side': 'low'}, {'replacement': 1, 'remaining': [[9]], 'size': 1, 'singleton': True, 'survivor': 9, 'nodes': 1}), ({'intervals': [[1, 9], [3, 7]], 'side': 'high'}, {'replacement': 7, 'remaining': [[1, 9], [3]], 'size': 3, 'singleton': True, 'survivor': 3, 'nodes': 2}), ({'intervals': [[1, 9], [3]], 'side': 'low'}, {'replacement': 3, 'remaining': [[1, 9]], 'size': 2, 'singleton': False, 'survivor': None, 'nodes': 1}), ({'intervals': [[1, 9], [2, 8], [4, 6]], 'side': 'low'}, {'replacement': 4, 'remaining': [[1, 9], [2, 8], [6]], 'size': 5, 'singleton': True, 'survivor': 6, 'nodes': 3}), ({'intervals': [[1, 9], [2, 8], [4, 11]], 'side': 'low'}, {'replacement': 4, 'remaining': [[1, 9], [2, 8], [11]], 'size': 5, 'singleton': True, 'survivor': 11, 'nodes': 3})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
The bounded interval pop end certificate reports an incorrect replacement.

A bounded interval-tail removal receives intervals, and side low or high. Remove the requested endpoint from the final interval (singleton removed wholly), returning extracted tail replacement, remaining interval list, new logical size, singleton status, surviving endpoint, and array-node count. This isolates tail extraction before global bubbling.

split: open-access