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

N = 1
observations = []
def solve(d):
    r=d['reverse']; start=d['node']; j=start; path=[]
    while j>0 and j%2==r[j//2]:
        path.append(j); j//=2
    ancestor=None if start==0 else j//2
    return {'ancestor': ancestor,
    'path': path,
    'cost': len(path),
    'stop': j,
    'orientation': None if start==0 else r[start//2],
    'direct': start!=0 and ancestor==start//2}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'reverse': [0], 'node': 0}, {'ancestor': None, 'path': [], 'cost': 0, 'stop': 0, 'orientation': None, 'direct': False}), ({'reverse': [0, 0], 'node': 1}, {'ancestor': 0, 'path': [], 'cost': 0, 'stop': 1, 'orientation': 0, 'direct': True}), ({'reverse': [0, 0, 0, 0, 0, 0, 0, 0], 'node': 4}, {'ancestor': 0, 'path': [4, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 0, 1, 0, 0, 0, 0], 'node': 7}, {'ancestor': 0, 'path': [7, 3], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 0, 1, 0, 0, 0, 0, 0], 'node': 5}, {'ancestor': 0, 'path': [5, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 6}, {'ancestor': 3, 'path': [], 'cost': 0, 'stop': 6, 'orientation': 1, 'direct': True}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 2}, {'ancestor': 1, 'path': [], 'cost': 0, 'stop': 2, 'orientation': 1, 'direct': True})], [({'reverse': [0], 'node': 0}, {'ancestor': None, 'path': [], 'cost': 0, 'stop': 0, 'orientation': None, 'direct': False}), ({'reverse': [0, 0], 'node': 1}, {'ancestor': 0, 'path': [], 'cost': 0, 'stop': 1, 'orientation': 0, 'direct': True}), ({'reverse': [0, 0, 0, 0, 0, 0, 0, 0], 'node': 4}, {'ancestor': 0, 'path': [4, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 0, 1, 0, 0, 0, 0], 'node': 7}, {'ancestor': 0, 'path': [7, 3], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 0, 1, 0, 0, 0, 0, 0], 'node': 5}, {'ancestor': 0, 'path': [5, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 6}, {'ancestor': 3, 'path': [], 'cost': 0, 'stop': 6, 'orientation': 1, 'direct': True}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 3}, {'ancestor': 0, 'path': [3], 'cost': 1, 'stop': 1, 'orientation': 0, 'direct': False})], [({'reverse': [0], 'node': 0}, {'ancestor': None, 'path': [], 'cost': 0, 'stop': 0, 'orientation': None, 'direct': False}), ({'reverse': [0, 0], 'node': 1}, {'ancestor': 0, 'path': [], 'cost': 0, 'stop': 1, 'orientation': 0, 'direct': True}), ({'reverse': [0, 0, 0, 0, 0, 0, 0, 0], 'node': 4}, {'ancestor': 0, 'path': [4, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 0, 1, 0, 0, 0, 0], 'node': 7}, {'ancestor': 0, 'path': [7, 3], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 0, 1, 0, 0, 0, 0, 0], 'node': 5}, {'ancestor': 0, 'path': [5, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 6}, {'ancestor': 3, 'path': [], 'cost': 0, 'stop': 6, 'orientation': 1, 'direct': True}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 4}, {'ancestor': 2, 'path': [], 'cost': 0, 'stop': 4, 'orientation': 1, 'direct': True})], [({'reverse': [0], 'node': 0}, {'ancestor': None, 'path': [], 'cost': 0, 'stop': 0, 'orientation': None, 'direct': False}), ({'reverse': [0, 0], 'node': 1}, {'ancestor': 0, 'path': [], 'cost': 0, 'stop': 1, 'orientation': 0, 'direct': True}), ({'reverse': [0, 0, 0, 0, 0, 0, 0, 0], 'node': 4}, {'ancestor': 0, 'path': [4, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 0, 1, 0, 0, 0, 0], 'node': 7}, {'ancestor': 0, 'path': [7, 3], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 0, 1, 0, 0, 0, 0, 0], 'node': 5}, {'ancestor': 0, 'path': [5, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 6}, {'ancestor': 3, 'path': [], 'cost': 0, 'stop': 6, 'orientation': 1, 'direct': True}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 5}, {'ancestor': 1, 'path': [5], 'cost': 1, 'stop': 2, 'orientation': 1, 'direct': False})], [({'reverse': [0], 'node': 0}, {'ancestor': None, 'path': [], 'cost': 0, 'stop': 0, 'orientation': None, 'direct': False}), ({'reverse': [0, 0], 'node': 1}, {'ancestor': 0, 'path': [], 'cost': 0, 'stop': 1, 'orientation': 0, 'direct': True}), ({'reverse': [0, 0, 0, 0, 0, 0, 0, 0], 'node': 4}, {'ancestor': 0, 'path': [4, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 0, 1, 0, 0, 0, 0], 'node': 7}, {'ancestor': 0, 'path': [7, 3], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 0, 1, 0, 0, 0, 0, 0], 'node': 5}, {'ancestor': 0, 'path': [5, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 6}, {'ancestor': 3, 'path': [], 'cost': 0, 'stop': 6, 'orientation': 1, 'direct': True}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 6}, {'ancestor': 3, 'path': [], 'cost': 0, 'stop': 6, 'orientation': 1, 'direct': True})]][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):
    r=d['reverse']; start=d['node']; j=start; path=[]
    while j>0 and j%2==r[j//2]:
        path.append(j); j//=2
    ancestor=None if start==0 else j//2
    return {'ancestor': ancestor,
    'path': path,
    'cost': len(path),
    'stop': j,
    'orientation': None if start==0 else r[j],
    'direct': start!=0 and ancestor==start//2}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'reverse': [0], 'node': 0}, {'ancestor': None, 'path': [], 'cost': 0, 'stop': 0, 'orientation': None, 'direct': False}), ({'reverse': [0, 0], 'node': 1}, {'ancestor': 0, 'path': [], 'cost': 0, 'stop': 1, 'orientation': 0, 'direct': True}), ({'reverse': [0, 0, 0, 0, 0, 0, 0, 0], 'node': 4}, {'ancestor': 0, 'path': [4, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 0, 1, 0, 0, 0, 0], 'node': 7}, {'ancestor': 0, 'path': [7, 3], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 0, 1, 0, 0, 0, 0, 0], 'node': 5}, {'ancestor': 0, 'path': [5, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 6}, {'ancestor': 3, 'path': [], 'cost': 0, 'stop': 6, 'orientation': 1, 'direct': True}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 2}, {'ancestor': 1, 'path': [], 'cost': 0, 'stop': 2, 'orientation': 1, 'direct': True})], [({'reverse': [0], 'node': 0}, {'ancestor': None, 'path': [], 'cost': 0, 'stop': 0, 'orientation': None, 'direct': False}), ({'reverse': [0, 0], 'node': 1}, {'ancestor': 0, 'path': [], 'cost': 0, 'stop': 1, 'orientation': 0, 'direct': True}), ({'reverse': [0, 0, 0, 0, 0, 0, 0, 0], 'node': 4}, {'ancestor': 0, 'path': [4, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 0, 1, 0, 0, 0, 0], 'node': 7}, {'ancestor': 0, 'path': [7, 3], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 0, 1, 0, 0, 0, 0, 0], 'node': 5}, {'ancestor': 0, 'path': [5, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 6}, {'ancestor': 3, 'path': [], 'cost': 0, 'stop': 6, 'orientation': 1, 'direct': True}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 3}, {'ancestor': 0, 'path': [3], 'cost': 1, 'stop': 1, 'orientation': 0, 'direct': False})], [({'reverse': [0], 'node': 0}, {'ancestor': None, 'path': [], 'cost': 0, 'stop': 0, 'orientation': None, 'direct': False}), ({'reverse': [0, 0], 'node': 1}, {'ancestor': 0, 'path': [], 'cost': 0, 'stop': 1, 'orientation': 0, 'direct': True}), ({'reverse': [0, 0, 0, 0, 0, 0, 0, 0], 'node': 4}, {'ancestor': 0, 'path': [4, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 0, 1, 0, 0, 0, 0], 'node': 7}, {'ancestor': 0, 'path': [7, 3], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 0, 1, 0, 0, 0, 0, 0], 'node': 5}, {'ancestor': 0, 'path': [5, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 6}, {'ancestor': 3, 'path': [], 'cost': 0, 'stop': 6, 'orientation': 1, 'direct': True}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 4}, {'ancestor': 2, 'path': [], 'cost': 0, 'stop': 4, 'orientation': 1, 'direct': True})], [({'reverse': [0], 'node': 0}, {'ancestor': None, 'path': [], 'cost': 0, 'stop': 0, 'orientation': None, 'direct': False}), ({'reverse': [0, 0], 'node': 1}, {'ancestor': 0, 'path': [], 'cost': 0, 'stop': 1, 'orientation': 0, 'direct': True}), ({'reverse': [0, 0, 0, 0, 0, 0, 0, 0], 'node': 4}, {'ancestor': 0, 'path': [4, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 0, 1, 0, 0, 0, 0], 'node': 7}, {'ancestor': 0, 'path': [7, 3], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 0, 1, 0, 0, 0, 0, 0], 'node': 5}, {'ancestor': 0, 'path': [5, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 6}, {'ancestor': 3, 'path': [], 'cost': 0, 'stop': 6, 'orientation': 1, 'direct': True}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 5}, {'ancestor': 1, 'path': [5], 'cost': 1, 'stop': 2, 'orientation': 1, 'direct': False})], [({'reverse': [0], 'node': 0}, {'ancestor': None, 'path': [], 'cost': 0, 'stop': 0, 'orientation': None, 'direct': False}), ({'reverse': [0, 0], 'node': 1}, {'ancestor': 0, 'path': [], 'cost': 0, 'stop': 1, 'orientation': 0, 'direct': True}), ({'reverse': [0, 0, 0, 0, 0, 0, 0, 0], 'node': 4}, {'ancestor': 0, 'path': [4, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 0, 1, 0, 0, 0, 0], 'node': 7}, {'ancestor': 0, 'path': [7, 3], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 0, 1, 0, 0, 0, 0, 0], 'node': 5}, {'ancestor': 0, 'path': [5, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 6}, {'ancestor': 3, 'path': [], 'cost': 0, 'stop': 6, 'orientation': 1, 'direct': True}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 6}, {'ancestor': 3, 'path': [], 'cost': 0, 'stop': 6, 'orientation': 1, 'direct': True})]][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 weak ancestor certificate reports an incorrect orientation.

A weak heap stores reverse bits r in a zero-based array. For nonroot node j, climb while j is a left child under its parent reverse bit: (j mod 2)==r[j//2]. Its distinguished ancestor is j//2 after climbing; zero has none. Report ancestor, climb path, climb count, stopping child, orientation bit, and whether direct parent suffices.

split: open-access


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

N = 1
observations = []
def solve(d):
    r=d['reverse']; start=d['node']; j=start; path=[]
    while j>0 and j%2==r[j//2]:
        path.append(j); j//=2
    ancestor=None if start==0 else j//2
    return {'ancestor': ancestor,
    'path': path,
    'cost': len(path),
    'stop': j,
    'orientation': None if start==0 else r[j//2],
    'direct': bool(start)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'reverse': [0], 'node': 0}, {'ancestor': None, 'path': [], 'cost': 0, 'stop': 0, 'orientation': None, 'direct': False}), ({'reverse': [0, 0], 'node': 1}, {'ancestor': 0, 'path': [], 'cost': 0, 'stop': 1, 'orientation': 0, 'direct': True}), ({'reverse': [0, 0, 0, 0, 0, 0, 0, 0], 'node': 4}, {'ancestor': 0, 'path': [4, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 0, 1, 0, 0, 0, 0], 'node': 7}, {'ancestor': 0, 'path': [7, 3], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 0, 1, 0, 0, 0, 0, 0], 'node': 5}, {'ancestor': 0, 'path': [5, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 6}, {'ancestor': 3, 'path': [], 'cost': 0, 'stop': 6, 'orientation': 1, 'direct': True}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 2}, {'ancestor': 1, 'path': [], 'cost': 0, 'stop': 2, 'orientation': 1, 'direct': True})], [({'reverse': [0], 'node': 0}, {'ancestor': None, 'path': [], 'cost': 0, 'stop': 0, 'orientation': None, 'direct': False}), ({'reverse': [0, 0], 'node': 1}, {'ancestor': 0, 'path': [], 'cost': 0, 'stop': 1, 'orientation': 0, 'direct': True}), ({'reverse': [0, 0, 0, 0, 0, 0, 0, 0], 'node': 4}, {'ancestor': 0, 'path': [4, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 0, 1, 0, 0, 0, 0], 'node': 7}, {'ancestor': 0, 'path': [7, 3], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 0, 1, 0, 0, 0, 0, 0], 'node': 5}, {'ancestor': 0, 'path': [5, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 6}, {'ancestor': 3, 'path': [], 'cost': 0, 'stop': 6, 'orientation': 1, 'direct': True}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 3}, {'ancestor': 0, 'path': [3], 'cost': 1, 'stop': 1, 'orientation': 0, 'direct': False})], [({'reverse': [0], 'node': 0}, {'ancestor': None, 'path': [], 'cost': 0, 'stop': 0, 'orientation': None, 'direct': False}), ({'reverse': [0, 0], 'node': 1}, {'ancestor': 0, 'path': [], 'cost': 0, 'stop': 1, 'orientation': 0, 'direct': True}), ({'reverse': [0, 0, 0, 0, 0, 0, 0, 0], 'node': 4}, {'ancestor': 0, 'path': [4, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 0, 1, 0, 0, 0, 0], 'node': 7}, {'ancestor': 0, 'path': [7, 3], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 0, 1, 0, 0, 0, 0, 0], 'node': 5}, {'ancestor': 0, 'path': [5, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 6}, {'ancestor': 3, 'path': [], 'cost': 0, 'stop': 6, 'orientation': 1, 'direct': True}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 4}, {'ancestor': 2, 'path': [], 'cost': 0, 'stop': 4, 'orientation': 1, 'direct': True})], [({'reverse': [0], 'node': 0}, {'ancestor': None, 'path': [], 'cost': 0, 'stop': 0, 'orientation': None, 'direct': False}), ({'reverse': [0, 0], 'node': 1}, {'ancestor': 0, 'path': [], 'cost': 0, 'stop': 1, 'orientation': 0, 'direct': True}), ({'reverse': [0, 0, 0, 0, 0, 0, 0, 0], 'node': 4}, {'ancestor': 0, 'path': [4, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 0, 1, 0, 0, 0, 0], 'node': 7}, {'ancestor': 0, 'path': [7, 3], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 0, 1, 0, 0, 0, 0, 0], 'node': 5}, {'ancestor': 0, 'path': [5, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 6}, {'ancestor': 3, 'path': [], 'cost': 0, 'stop': 6, 'orientation': 1, 'direct': True}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 5}, {'ancestor': 1, 'path': [5], 'cost': 1, 'stop': 2, 'orientation': 1, 'direct': False})], [({'reverse': [0], 'node': 0}, {'ancestor': None, 'path': [], 'cost': 0, 'stop': 0, 'orientation': None, 'direct': False}), ({'reverse': [0, 0], 'node': 1}, {'ancestor': 0, 'path': [], 'cost': 0, 'stop': 1, 'orientation': 0, 'direct': True}), ({'reverse': [0, 0, 0, 0, 0, 0, 0, 0], 'node': 4}, {'ancestor': 0, 'path': [4, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 0, 1, 0, 0, 0, 0], 'node': 7}, {'ancestor': 0, 'path': [7, 3], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 0, 1, 0, 0, 0, 0, 0], 'node': 5}, {'ancestor': 0, 'path': [5, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 6}, {'ancestor': 3, 'path': [], 'cost': 0, 'stop': 6, 'orientation': 1, 'direct': True}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 6}, {'ancestor': 3, 'path': [], 'cost': 0, 'stop': 6, 'orientation': 1, 'direct': True})]][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):
    r=d['reverse']; start=d['node']; j=start; path=[]
    while j>0 and j%2==r[j//2]:
        path.append(j); j//=2
    ancestor=None if start==0 else j//2
    return {'ancestor': ancestor,
    'path': path,
    'cost': len(path),
    'stop': j,
    'orientation': None if start==0 else r[j//2],
    'direct': start!=0 and start%2==1}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'reverse': [0], 'node': 0}, {'ancestor': None, 'path': [], 'cost': 0, 'stop': 0, 'orientation': None, 'direct': False}), ({'reverse': [0, 0], 'node': 1}, {'ancestor': 0, 'path': [], 'cost': 0, 'stop': 1, 'orientation': 0, 'direct': True}), ({'reverse': [0, 0, 0, 0, 0, 0, 0, 0], 'node': 4}, {'ancestor': 0, 'path': [4, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 0, 1, 0, 0, 0, 0], 'node': 7}, {'ancestor': 0, 'path': [7, 3], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 0, 1, 0, 0, 0, 0, 0], 'node': 5}, {'ancestor': 0, 'path': [5, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 6}, {'ancestor': 3, 'path': [], 'cost': 0, 'stop': 6, 'orientation': 1, 'direct': True}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 2}, {'ancestor': 1, 'path': [], 'cost': 0, 'stop': 2, 'orientation': 1, 'direct': True})], [({'reverse': [0], 'node': 0}, {'ancestor': None, 'path': [], 'cost': 0, 'stop': 0, 'orientation': None, 'direct': False}), ({'reverse': [0, 0], 'node': 1}, {'ancestor': 0, 'path': [], 'cost': 0, 'stop': 1, 'orientation': 0, 'direct': True}), ({'reverse': [0, 0, 0, 0, 0, 0, 0, 0], 'node': 4}, {'ancestor': 0, 'path': [4, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 0, 1, 0, 0, 0, 0], 'node': 7}, {'ancestor': 0, 'path': [7, 3], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 0, 1, 0, 0, 0, 0, 0], 'node': 5}, {'ancestor': 0, 'path': [5, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 6}, {'ancestor': 3, 'path': [], 'cost': 0, 'stop': 6, 'orientation': 1, 'direct': True}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 3}, {'ancestor': 0, 'path': [3], 'cost': 1, 'stop': 1, 'orientation': 0, 'direct': False})], [({'reverse': [0], 'node': 0}, {'ancestor': None, 'path': [], 'cost': 0, 'stop': 0, 'orientation': None, 'direct': False}), ({'reverse': [0, 0], 'node': 1}, {'ancestor': 0, 'path': [], 'cost': 0, 'stop': 1, 'orientation': 0, 'direct': True}), ({'reverse': [0, 0, 0, 0, 0, 0, 0, 0], 'node': 4}, {'ancestor': 0, 'path': [4, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 0, 1, 0, 0, 0, 0], 'node': 7}, {'ancestor': 0, 'path': [7, 3], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 0, 1, 0, 0, 0, 0, 0], 'node': 5}, {'ancestor': 0, 'path': [5, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 6}, {'ancestor': 3, 'path': [], 'cost': 0, 'stop': 6, 'orientation': 1, 'direct': True}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 4}, {'ancestor': 2, 'path': [], 'cost': 0, 'stop': 4, 'orientation': 1, 'direct': True})], [({'reverse': [0], 'node': 0}, {'ancestor': None, 'path': [], 'cost': 0, 'stop': 0, 'orientation': None, 'direct': False}), ({'reverse': [0, 0], 'node': 1}, {'ancestor': 0, 'path': [], 'cost': 0, 'stop': 1, 'orientation': 0, 'direct': True}), ({'reverse': [0, 0, 0, 0, 0, 0, 0, 0], 'node': 4}, {'ancestor': 0, 'path': [4, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 0, 1, 0, 0, 0, 0], 'node': 7}, {'ancestor': 0, 'path': [7, 3], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 0, 1, 0, 0, 0, 0, 0], 'node': 5}, {'ancestor': 0, 'path': [5, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 6}, {'ancestor': 3, 'path': [], 'cost': 0, 'stop': 6, 'orientation': 1, 'direct': True}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 5}, {'ancestor': 1, 'path': [5], 'cost': 1, 'stop': 2, 'orientation': 1, 'direct': False})], [({'reverse': [0], 'node': 0}, {'ancestor': None, 'path': [], 'cost': 0, 'stop': 0, 'orientation': None, 'direct': False}), ({'reverse': [0, 0], 'node': 1}, {'ancestor': 0, 'path': [], 'cost': 0, 'stop': 1, 'orientation': 0, 'direct': True}), ({'reverse': [0, 0, 0, 0, 0, 0, 0, 0], 'node': 4}, {'ancestor': 0, 'path': [4, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 0, 1, 0, 0, 0, 0], 'node': 7}, {'ancestor': 0, 'path': [7, 3], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 0, 1, 0, 0, 0, 0, 0], 'node': 5}, {'ancestor': 0, 'path': [5, 2], 'cost': 2, 'stop': 1, 'orientation': 0, 'direct': False}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 6}, {'ancestor': 3, 'path': [], 'cost': 0, 'stop': 6, 'orientation': 1, 'direct': True}), ({'reverse': [0, 1, 1, 1, 0, 0, 0, 0], 'node': 6}, {'ancestor': 3, 'path': [], 'cost': 0, 'stop': 6, 'orientation': 1, 'direct': True})]][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 weak ancestor certificate reports an incorrect direct.

A weak heap stores reverse bits r in a zero-based array. For nonroot node j, climb while j is a left child under its parent reverse bit: (j mod 2)==r[j//2]. Its distinguished ancestor is j//2 after climbing; zero has none. Report ancestor, climb path, climb count, stopping child, orientation bit, and whether direct parent suffices.

split: open-access


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

N = 1
observations = []
def solve(d):
    a=d['keys']; r=d['reverse']; i=d['i']; j=d['j']; swap=a[j]<a[i]; out=list(a); bits=list(r)
    if swap: out[i],out[j]=out[j],out[i]; bits[j]^=1
    return {'keys': a,
    'bits': bits,
    'swapped': swap,
    'winner_key': out[i],
    'flipped': j if swap else None,
    'comparisons': 1}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 4], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 4], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 3], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 3], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 2], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 2], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 1], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 1, 3, 4, 2], 'bits': [0, 1, 0, 1, 1], 'swapped': True, 'winner_key': 1, 'flipped': 4, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 0], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 0, 3, 4, 2], 'bits': [0, 1, 0, 1, 1], 'swapped': True, 'winner_key': 0, 'flipped': 4, 'comparisons': 1})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

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

N = 1
observations = []
def solve(d):
    a=d['keys']; r=d['reverse']; i=d['i']; j=d['j']; swap=a[j]<a[i]; out=list(a); bits=list(r)
    if swap: out[i],out[j]=out[j],out[i]; bits[j]^=1
    return {'keys': [min(x,a[j]) if k==i else x for k,x in enumerate(a)],
    'bits': bits,
    'swapped': swap,
    'winner_key': out[i],
    'flipped': j if swap else None,
    'comparisons': 1}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 4], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 4], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 3], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 3], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 2], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 2], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 1], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 1, 3, 4, 2], 'bits': [0, 1, 0, 1, 1], 'swapped': True, 'winner_key': 1, 'flipped': 4, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 0], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 0, 3, 4, 2], 'bits': [0, 1, 0, 1, 1], 'swapped': True, 'winner_key': 0, 'flipped': 4, 'comparisons': 1})]][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 weak join certificate reports an incorrect keys.

A weak-heap join receives keys, reverse bits, ancestor i and distinct descendant j. When keys[j]<keys[i], swap these keys and flip only reverse[j]; on equality do nothing. Return resulting keys, reversal bits, swapped status, winning key, changed reversal index, and comparison count.

split: open-access


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

N = 1
observations = []
def solve(d):
    a=d['keys']; r=d['reverse']; i=d['i']; j=d['j']; swap=a[j]<a[i]; out=list(a); bits=list(r)
    if swap: out[i],out[j]=out[j],out[i]; bits[j]^=1
    return {'keys': out,
    'bits': [x^(1 if k==i and swap else 0) for k,x in enumerate(r)],
    'swapped': swap,
    'winner_key': out[i],
    'flipped': j if swap else None,
    'comparisons': 1}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 4], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 4], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 3], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 3], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 2], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 2], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 1], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 1, 3, 4, 2], 'bits': [0, 1, 0, 1, 1], 'swapped': True, 'winner_key': 1, 'flipped': 4, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 0], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 0, 3, 4, 2], 'bits': [0, 1, 0, 1, 1], 'swapped': True, 'winner_key': 0, 'flipped': 4, 'comparisons': 1})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

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

N = 1
observations = []
def solve(d):
    a=d['keys']; r=d['reverse']; i=d['i']; j=d['j']; swap=a[j]<a[i]; out=list(a); bits=list(r)
    if swap: out[i],out[j]=out[j],out[i]; bits[j]^=1
    return {'keys': out,
    'bits': [x^(1 if swap else 0) for x in r],
    'swapped': swap,
    'winner_key': out[i],
    'flipped': j if swap else None,
    'comparisons': 1}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 4], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 4], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 3], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 3], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 2], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 2], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 1], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 1, 3, 4, 2], 'bits': [0, 1, 0, 1, 1], 'swapped': True, 'winner_key': 1, 'flipped': 4, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 0], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 0, 3, 4, 2], 'bits': [0, 1, 0, 1, 1], 'swapped': True, 'winner_key': 0, 'flipped': 4, 'comparisons': 1})]][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 weak join certificate reports an incorrect bits.

A weak-heap join receives keys, reverse bits, ancestor i and distinct descendant j. When keys[j]<keys[i], swap these keys and flip only reverse[j]; on equality do nothing. Return resulting keys, reversal bits, swapped status, winning key, changed reversal index, and comparison count.

split: open-access


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

N = 1
observations = []
def solve(d):
    a=d['keys']; r=d['reverse']; i=d['i']; j=d['j']; swap=a[j]<a[i]; out=list(a); bits=list(r)
    if swap: out[i],out[j]=out[j],out[i]; bits[j]^=1
    return {'keys': out,
    'bits': bits,
    'swapped': a[j]<=a[i],
    'winner_key': out[i],
    'flipped': j if swap else None,
    'comparisons': 1}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 4], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 4], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 3], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 3], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 2], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 2], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 1], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 1, 3, 4, 2], 'bits': [0, 1, 0, 1, 1], 'swapped': True, 'winner_key': 1, 'flipped': 4, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 0], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 0, 3, 4, 2], 'bits': [0, 1, 0, 1, 1], 'swapped': True, 'winner_key': 0, 'flipped': 4, 'comparisons': 1})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

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

N = 1
observations = []
def solve(d):
    a=d['keys']; r=d['reverse']; i=d['i']; j=d['j']; swap=a[j]<a[i]; out=list(a); bits=list(r)
    if swap: out[i],out[j]=out[j],out[i]; bits[j]^=1
    return {'keys': out,
    'bits': bits,
    'swapped': a[j]>a[i],
    'winner_key': out[i],
    'flipped': j if swap else None,
    'comparisons': 1}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 4], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 4], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 3], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 3], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 2], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 2], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 1], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 1, 3, 4, 2], 'bits': [0, 1, 0, 1, 1], 'swapped': True, 'winner_key': 1, 'flipped': 4, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 0], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 0, 3, 4, 2], 'bits': [0, 1, 0, 1, 1], 'swapped': True, 'winner_key': 0, 'flipped': 4, 'comparisons': 1})]][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 weak join certificate reports an incorrect swapped.

A weak-heap join receives keys, reverse bits, ancestor i and distinct descendant j. When keys[j]<keys[i], swap these keys and flip only reverse[j]; on equality do nothing. Return resulting keys, reversal bits, swapped status, winning key, changed reversal index, and comparison count.

split: open-access


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

N = 1
observations = []
def solve(d):
    a=d['keys']; r=d['reverse']; i=d['i']; j=d['j']; swap=a[j]<a[i]; out=list(a); bits=list(r)
    if swap: out[i],out[j]=out[j],out[i]; bits[j]^=1
    return {'keys': out,
    'bits': bits,
    'swapped': swap,
    'winner_key': out[j],
    'flipped': j if swap else None,
    'comparisons': 1}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 4], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 4], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 3], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 3], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 2], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 2], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 1], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 1, 3, 4, 2], 'bits': [0, 1, 0, 1, 1], 'swapped': True, 'winner_key': 1, 'flipped': 4, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 0], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 0, 3, 4, 2], 'bits': [0, 1, 0, 1, 1], 'swapped': True, 'winner_key': 0, 'flipped': 4, 'comparisons': 1})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

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

N = 1
observations = []
def solve(d):
    a=d['keys']; r=d['reverse']; i=d['i']; j=d['j']; swap=a[j]<a[i]; out=list(a); bits=list(r)
    if swap: out[i],out[j]=out[j],out[i]; bits[j]^=1
    return {'keys': out,
    'bits': bits,
    'swapped': swap,
    'winner_key': min(a),
    'flipped': j if swap else None,
    'comparisons': 1}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 4], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 4], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 3], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 3], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 2], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 2], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 1], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 1, 3, 4, 2], 'bits': [0, 1, 0, 1, 1], 'swapped': True, 'winner_key': 1, 'flipped': 4, 'comparisons': 1})], [({'keys': [4, 2], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [2, 4], 'bits': [0, 1], 'swapped': True, 'winner_key': 2, 'flipped': 1, 'comparisons': 1}), ({'keys': [1, 7], 'reverse': [0, 1], 'i': 0, 'j': 1}, {'keys': [1, 7], 'bits': [0, 1], 'swapped': False, 'winner_key': 1, 'flipped': None, 'comparisons': 1}), ({'keys': [3, 3], 'reverse': [0, 0], 'i': 0, 'j': 1}, {'keys': [3, 3], 'bits': [0, 0], 'swapped': False, 'winner_key': 3, 'flipped': None, 'comparisons': 1}), ({'keys': [0, 8, 5, 2], 'reverse': [0, 1, 0, 1], 'i': 1, 'j': 3}, {'keys': [0, 2, 5, 8], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 2, 'flipped': 3, 'comparisons': 1}), ({'keys': [9, 1, 7, 3], 'reverse': [0, 1, 1, 0], 'i': 0, 'j': 2}, {'keys': [7, 1, 9, 3], 'bits': [0, 1, 0, 0], 'swapped': True, 'winner_key': 7, 'flipped': 2, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 5], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 2, 3, 4, 5], 'bits': [0, 1, 0, 1, 0], 'swapped': False, 'winner_key': 2, 'flipped': None, 'comparisons': 1}), ({'keys': [1, 2, 3, 4, 0], 'reverse': [0, 1, 0, 1, 0], 'i': 1, 'j': 4}, {'keys': [1, 0, 3, 4, 2], 'bits': [0, 1, 0, 1, 1], 'swapped': True, 'winner_key': 0, 'flipped': 4, 'comparisons': 1})]][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 weak join certificate reports an incorrect winner key.

A weak-heap join receives keys, reverse bits, ancestor i and distinct descendant j. When keys[j]<keys[i], swap these keys and flip only reverse[j]; on equality do nothing. Return resulting keys, reversal bits, swapped status, winning key, changed reversal index, and comparison count.

split: open-access