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

N = 1
observations = []
def solve(d):
    a=d['challenger']; b=d['defender']; active=[x for x in (a,b) if x[2]]; win=min(active,key=lambda x:(x[1],x[0])) if active else None; lose=None if win is None else (b if win is a else a)
    return {'winner': None if win is None else win[0],
    'stored_loser': None if lose is None else lose[0],
    'comparisons': int(len(active)==2),
    'exhausted': [x[0] for x in (a,b) if x[1] is None],
    'key': None if win is None else win[1],
    'continuation': None if win is None else win[0]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'challenger': [1, 0, False], 'defender': [2, 5, True]}, {'winner': 2, 'stored_loser': 1, 'comparisons': 0, 'exhausted': [1], 'key': 5, 'continuation': 2}), ({'challenger': [7, 3, True], 'defender': [2, 3, True]}, {'winner': 2, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 3, 'continuation': 2}), ({'challenger': [4, 8, True], 'defender': [3, 2, True]}, {'winner': 3, 'stored_loser': 4, 'comparisons': 1, 'exhausted': [], 'key': 2, 'continuation': 3}), ({'challenger': [1, 0, True], 'defender': [2, 9, False]}, {'winner': 1, 'stored_loser': 2, 'comparisons': 0, 'exhausted': [2], 'key': 0, 'continuation': 1}), ({'challenger': [1, -9, False], 'defender': [2, 4, False]}, {'winner': None, 'stored_loser': None, 'comparisons': 0, 'exhausted': [1, 2], 'key': None, 'continuation': None}), ({'challenger': [3, 1, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 1, 'continuation': 3}), ({'challenger': [3, 2, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 2, 'continuation': 3})], [({'challenger': [1, 0, False], 'defender': [2, 5, True]}, {'winner': 2, 'stored_loser': 1, 'comparisons': 0, 'exhausted': [1], 'key': 5, 'continuation': 2}), ({'challenger': [7, 3, True], 'defender': [2, 3, True]}, {'winner': 2, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 3, 'continuation': 2}), ({'challenger': [4, 8, True], 'defender': [3, 2, True]}, {'winner': 3, 'stored_loser': 4, 'comparisons': 1, 'exhausted': [], 'key': 2, 'continuation': 3}), ({'challenger': [1, 0, True], 'defender': [2, 9, False]}, {'winner': 1, 'stored_loser': 2, 'comparisons': 0, 'exhausted': [2], 'key': 0, 'continuation': 1}), ({'challenger': [1, -9, False], 'defender': [2, 4, False]}, {'winner': None, 'stored_loser': None, 'comparisons': 0, 'exhausted': [1, 2], 'key': None, 'continuation': None}), ({'challenger': [3, 1, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 1, 'continuation': 3}), ({'challenger': [3, 3, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 3, 'continuation': 3})], [({'challenger': [1, 0, False], 'defender': [2, 5, True]}, {'winner': 2, 'stored_loser': 1, 'comparisons': 0, 'exhausted': [1], 'key': 5, 'continuation': 2}), ({'challenger': [7, 3, True], 'defender': [2, 3, True]}, {'winner': 2, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 3, 'continuation': 2}), ({'challenger': [4, 8, True], 'defender': [3, 2, True]}, {'winner': 3, 'stored_loser': 4, 'comparisons': 1, 'exhausted': [], 'key': 2, 'continuation': 3}), ({'challenger': [1, 0, True], 'defender': [2, 9, False]}, {'winner': 1, 'stored_loser': 2, 'comparisons': 0, 'exhausted': [2], 'key': 0, 'continuation': 1}), ({'challenger': [1, -9, False], 'defender': [2, 4, False]}, {'winner': None, 'stored_loser': None, 'comparisons': 0, 'exhausted': [1, 2], 'key': None, 'continuation': None}), ({'challenger': [3, 1, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 1, 'continuation': 3}), ({'challenger': [3, 4, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 4, 'continuation': 3})], [({'challenger': [1, 0, False], 'defender': [2, 5, True]}, {'winner': 2, 'stored_loser': 1, 'comparisons': 0, 'exhausted': [1], 'key': 5, 'continuation': 2}), ({'challenger': [7, 3, True], 'defender': [2, 3, True]}, {'winner': 2, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 3, 'continuation': 2}), ({'challenger': [4, 8, True], 'defender': [3, 2, True]}, {'winner': 3, 'stored_loser': 4, 'comparisons': 1, 'exhausted': [], 'key': 2, 'continuation': 3}), ({'challenger': [1, 0, True], 'defender': [2, 9, False]}, {'winner': 1, 'stored_loser': 2, 'comparisons': 0, 'exhausted': [2], 'key': 0, 'continuation': 1}), ({'challenger': [1, -9, False], 'defender': [2, 4, False]}, {'winner': None, 'stored_loser': None, 'comparisons': 0, 'exhausted': [1, 2], 'key': None, 'continuation': None}), ({'challenger': [3, 1, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 1, 'continuation': 3}), ({'challenger': [3, 5, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 5, 'continuation': 3})], [({'challenger': [1, 0, False], 'defender': [2, 5, True]}, {'winner': 2, 'stored_loser': 1, 'comparisons': 0, 'exhausted': [1], 'key': 5, 'continuation': 2}), ({'challenger': [7, 3, True], 'defender': [2, 3, True]}, {'winner': 2, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 3, 'continuation': 2}), ({'challenger': [4, 8, True], 'defender': [3, 2, True]}, {'winner': 3, 'stored_loser': 4, 'comparisons': 1, 'exhausted': [], 'key': 2, 'continuation': 3}), ({'challenger': [1, 0, True], 'defender': [2, 9, False]}, {'winner': 1, 'stored_loser': 2, 'comparisons': 0, 'exhausted': [2], 'key': 0, 'continuation': 1}), ({'challenger': [1, -9, False], 'defender': [2, 4, False]}, {'winner': None, 'stored_loser': None, 'comparisons': 0, 'exhausted': [1, 2], 'key': None, 'continuation': None}), ({'challenger': [3, 1, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 1, 'continuation': 3}), ({'challenger': [3, 6, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 6, 'continuation': 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['challenger']; b=d['defender']; active=[x for x in (a,b) if x[2]]; win=min(active,key=lambda x:(x[1],x[0])) if active else None; lose=None if win is None else (b if win is a else a)
    return {'winner': None if win is None else win[0],
    'stored_loser': None if lose is None else lose[0],
    'comparisons': int(len(active)==2),
    'exhausted': [x[0] for x in (a,b) if x[1]==0],
    'key': None if win is None else win[1],
    'continuation': None if win is None else win[0]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'challenger': [1, 0, False], 'defender': [2, 5, True]}, {'winner': 2, 'stored_loser': 1, 'comparisons': 0, 'exhausted': [1], 'key': 5, 'continuation': 2}), ({'challenger': [7, 3, True], 'defender': [2, 3, True]}, {'winner': 2, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 3, 'continuation': 2}), ({'challenger': [4, 8, True], 'defender': [3, 2, True]}, {'winner': 3, 'stored_loser': 4, 'comparisons': 1, 'exhausted': [], 'key': 2, 'continuation': 3}), ({'challenger': [1, 0, True], 'defender': [2, 9, False]}, {'winner': 1, 'stored_loser': 2, 'comparisons': 0, 'exhausted': [2], 'key': 0, 'continuation': 1}), ({'challenger': [1, -9, False], 'defender': [2, 4, False]}, {'winner': None, 'stored_loser': None, 'comparisons': 0, 'exhausted': [1, 2], 'key': None, 'continuation': None}), ({'challenger': [3, 1, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 1, 'continuation': 3}), ({'challenger': [3, 2, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 2, 'continuation': 3})], [({'challenger': [1, 0, False], 'defender': [2, 5, True]}, {'winner': 2, 'stored_loser': 1, 'comparisons': 0, 'exhausted': [1], 'key': 5, 'continuation': 2}), ({'challenger': [7, 3, True], 'defender': [2, 3, True]}, {'winner': 2, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 3, 'continuation': 2}), ({'challenger': [4, 8, True], 'defender': [3, 2, True]}, {'winner': 3, 'stored_loser': 4, 'comparisons': 1, 'exhausted': [], 'key': 2, 'continuation': 3}), ({'challenger': [1, 0, True], 'defender': [2, 9, False]}, {'winner': 1, 'stored_loser': 2, 'comparisons': 0, 'exhausted': [2], 'key': 0, 'continuation': 1}), ({'challenger': [1, -9, False], 'defender': [2, 4, False]}, {'winner': None, 'stored_loser': None, 'comparisons': 0, 'exhausted': [1, 2], 'key': None, 'continuation': None}), ({'challenger': [3, 1, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 1, 'continuation': 3}), ({'challenger': [3, 3, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 3, 'continuation': 3})], [({'challenger': [1, 0, False], 'defender': [2, 5, True]}, {'winner': 2, 'stored_loser': 1, 'comparisons': 0, 'exhausted': [1], 'key': 5, 'continuation': 2}), ({'challenger': [7, 3, True], 'defender': [2, 3, True]}, {'winner': 2, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 3, 'continuation': 2}), ({'challenger': [4, 8, True], 'defender': [3, 2, True]}, {'winner': 3, 'stored_loser': 4, 'comparisons': 1, 'exhausted': [], 'key': 2, 'continuation': 3}), ({'challenger': [1, 0, True], 'defender': [2, 9, False]}, {'winner': 1, 'stored_loser': 2, 'comparisons': 0, 'exhausted': [2], 'key': 0, 'continuation': 1}), ({'challenger': [1, -9, False], 'defender': [2, 4, False]}, {'winner': None, 'stored_loser': None, 'comparisons': 0, 'exhausted': [1, 2], 'key': None, 'continuation': None}), ({'challenger': [3, 1, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 1, 'continuation': 3}), ({'challenger': [3, 4, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 4, 'continuation': 3})], [({'challenger': [1, 0, False], 'defender': [2, 5, True]}, {'winner': 2, 'stored_loser': 1, 'comparisons': 0, 'exhausted': [1], 'key': 5, 'continuation': 2}), ({'challenger': [7, 3, True], 'defender': [2, 3, True]}, {'winner': 2, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 3, 'continuation': 2}), ({'challenger': [4, 8, True], 'defender': [3, 2, True]}, {'winner': 3, 'stored_loser': 4, 'comparisons': 1, 'exhausted': [], 'key': 2, 'continuation': 3}), ({'challenger': [1, 0, True], 'defender': [2, 9, False]}, {'winner': 1, 'stored_loser': 2, 'comparisons': 0, 'exhausted': [2], 'key': 0, 'continuation': 1}), ({'challenger': [1, -9, False], 'defender': [2, 4, False]}, {'winner': None, 'stored_loser': None, 'comparisons': 0, 'exhausted': [1, 2], 'key': None, 'continuation': None}), ({'challenger': [3, 1, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 1, 'continuation': 3}), ({'challenger': [3, 5, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 5, 'continuation': 3})], [({'challenger': [1, 0, False], 'defender': [2, 5, True]}, {'winner': 2, 'stored_loser': 1, 'comparisons': 0, 'exhausted': [1], 'key': 5, 'continuation': 2}), ({'challenger': [7, 3, True], 'defender': [2, 3, True]}, {'winner': 2, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 3, 'continuation': 2}), ({'challenger': [4, 8, True], 'defender': [3, 2, True]}, {'winner': 3, 'stored_loser': 4, 'comparisons': 1, 'exhausted': [], 'key': 2, 'continuation': 3}), ({'challenger': [1, 0, True], 'defender': [2, 9, False]}, {'winner': 1, 'stored_loser': 2, 'comparisons': 0, 'exhausted': [2], 'key': 0, 'continuation': 1}), ({'challenger': [1, -9, False], 'defender': [2, 4, False]}, {'winner': None, 'stored_loser': None, 'comparisons': 0, 'exhausted': [1, 2], 'key': None, 'continuation': None}), ({'challenger': [3, 1, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 1, 'continuation': 3}), ({'challenger': [3, 6, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 6, 'continuation': 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 loser match certificate reports an incorrect exhausted.

A loser-tree match compares challenger [run,key,active] and defender likewise. Exhausted entries lose to active entries, ties prefer lower run id, both exhausted produce no winner. Return winner run, stored loser run, active match cost, exhausted runs, winning key, and replay continuation run.

split: open-access


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

N = 1
observations = []
def solve(d):
    a=d['challenger']; b=d['defender']; active=[x for x in (a,b) if x[2]]; win=min(active,key=lambda x:(x[1],x[0])) if active else None; lose=None if win is None else (b if win is a else a)
    return {'winner': None if win is None else win[0],
    'stored_loser': None if lose is None else lose[0],
    'comparisons': int(len(active)==2),
    'exhausted': [x[0] for x in (a,b) if not x[2]],
    'key': min(a[1],b[1]),
    'continuation': None if win is None else win[0]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'challenger': [1, 0, False], 'defender': [2, 5, True]}, {'winner': 2, 'stored_loser': 1, 'comparisons': 0, 'exhausted': [1], 'key': 5, 'continuation': 2}), ({'challenger': [7, 3, True], 'defender': [2, 3, True]}, {'winner': 2, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 3, 'continuation': 2}), ({'challenger': [4, 8, True], 'defender': [3, 2, True]}, {'winner': 3, 'stored_loser': 4, 'comparisons': 1, 'exhausted': [], 'key': 2, 'continuation': 3}), ({'challenger': [1, 0, True], 'defender': [2, 9, False]}, {'winner': 1, 'stored_loser': 2, 'comparisons': 0, 'exhausted': [2], 'key': 0, 'continuation': 1}), ({'challenger': [1, -9, False], 'defender': [2, 4, False]}, {'winner': None, 'stored_loser': None, 'comparisons': 0, 'exhausted': [1, 2], 'key': None, 'continuation': None}), ({'challenger': [3, 1, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 1, 'continuation': 3}), ({'challenger': [3, 2, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 2, 'continuation': 3})], [({'challenger': [1, 0, False], 'defender': [2, 5, True]}, {'winner': 2, 'stored_loser': 1, 'comparisons': 0, 'exhausted': [1], 'key': 5, 'continuation': 2}), ({'challenger': [7, 3, True], 'defender': [2, 3, True]}, {'winner': 2, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 3, 'continuation': 2}), ({'challenger': [4, 8, True], 'defender': [3, 2, True]}, {'winner': 3, 'stored_loser': 4, 'comparisons': 1, 'exhausted': [], 'key': 2, 'continuation': 3}), ({'challenger': [1, 0, True], 'defender': [2, 9, False]}, {'winner': 1, 'stored_loser': 2, 'comparisons': 0, 'exhausted': [2], 'key': 0, 'continuation': 1}), ({'challenger': [1, -9, False], 'defender': [2, 4, False]}, {'winner': None, 'stored_loser': None, 'comparisons': 0, 'exhausted': [1, 2], 'key': None, 'continuation': None}), ({'challenger': [3, 1, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 1, 'continuation': 3}), ({'challenger': [3, 3, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 3, 'continuation': 3})], [({'challenger': [1, 0, False], 'defender': [2, 5, True]}, {'winner': 2, 'stored_loser': 1, 'comparisons': 0, 'exhausted': [1], 'key': 5, 'continuation': 2}), ({'challenger': [7, 3, True], 'defender': [2, 3, True]}, {'winner': 2, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 3, 'continuation': 2}), ({'challenger': [4, 8, True], 'defender': [3, 2, True]}, {'winner': 3, 'stored_loser': 4, 'comparisons': 1, 'exhausted': [], 'key': 2, 'continuation': 3}), ({'challenger': [1, 0, True], 'defender': [2, 9, False]}, {'winner': 1, 'stored_loser': 2, 'comparisons': 0, 'exhausted': [2], 'key': 0, 'continuation': 1}), ({'challenger': [1, -9, False], 'defender': [2, 4, False]}, {'winner': None, 'stored_loser': None, 'comparisons': 0, 'exhausted': [1, 2], 'key': None, 'continuation': None}), ({'challenger': [3, 1, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 1, 'continuation': 3}), ({'challenger': [3, 4, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 4, 'continuation': 3})], [({'challenger': [1, 0, False], 'defender': [2, 5, True]}, {'winner': 2, 'stored_loser': 1, 'comparisons': 0, 'exhausted': [1], 'key': 5, 'continuation': 2}), ({'challenger': [7, 3, True], 'defender': [2, 3, True]}, {'winner': 2, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 3, 'continuation': 2}), ({'challenger': [4, 8, True], 'defender': [3, 2, True]}, {'winner': 3, 'stored_loser': 4, 'comparisons': 1, 'exhausted': [], 'key': 2, 'continuation': 3}), ({'challenger': [1, 0, True], 'defender': [2, 9, False]}, {'winner': 1, 'stored_loser': 2, 'comparisons': 0, 'exhausted': [2], 'key': 0, 'continuation': 1}), ({'challenger': [1, -9, False], 'defender': [2, 4, False]}, {'winner': None, 'stored_loser': None, 'comparisons': 0, 'exhausted': [1, 2], 'key': None, 'continuation': None}), ({'challenger': [3, 1, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 1, 'continuation': 3}), ({'challenger': [3, 5, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 5, 'continuation': 3})], [({'challenger': [1, 0, False], 'defender': [2, 5, True]}, {'winner': 2, 'stored_loser': 1, 'comparisons': 0, 'exhausted': [1], 'key': 5, 'continuation': 2}), ({'challenger': [7, 3, True], 'defender': [2, 3, True]}, {'winner': 2, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 3, 'continuation': 2}), ({'challenger': [4, 8, True], 'defender': [3, 2, True]}, {'winner': 3, 'stored_loser': 4, 'comparisons': 1, 'exhausted': [], 'key': 2, 'continuation': 3}), ({'challenger': [1, 0, True], 'defender': [2, 9, False]}, {'winner': 1, 'stored_loser': 2, 'comparisons': 0, 'exhausted': [2], 'key': 0, 'continuation': 1}), ({'challenger': [1, -9, False], 'defender': [2, 4, False]}, {'winner': None, 'stored_loser': None, 'comparisons': 0, 'exhausted': [1, 2], 'key': None, 'continuation': None}), ({'challenger': [3, 1, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 1, 'continuation': 3}), ({'challenger': [3, 6, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 6, 'continuation': 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)

meaning: Fixture-count band, not measured model difficulty

deps: stdlib

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

N = 1
observations = []
def solve(d):
    a=d['challenger']; b=d['defender']; active=[x for x in (a,b) if x[2]]; win=min(active,key=lambda x:(x[1],x[0])) if active else None; lose=None if win is None else (b if win is a else a)
    return {'winner': None if win is None else win[0],
    'stored_loser': None if lose is None else lose[0],
    'comparisons': int(len(active)==2),
    'exhausted': [x[0] for x in (a,b) if not x[2]],
    'key': None if win is None else win[0],
    'continuation': None if win is None else win[0]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'challenger': [1, 0, False], 'defender': [2, 5, True]}, {'winner': 2, 'stored_loser': 1, 'comparisons': 0, 'exhausted': [1], 'key': 5, 'continuation': 2}), ({'challenger': [7, 3, True], 'defender': [2, 3, True]}, {'winner': 2, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 3, 'continuation': 2}), ({'challenger': [4, 8, True], 'defender': [3, 2, True]}, {'winner': 3, 'stored_loser': 4, 'comparisons': 1, 'exhausted': [], 'key': 2, 'continuation': 3}), ({'challenger': [1, 0, True], 'defender': [2, 9, False]}, {'winner': 1, 'stored_loser': 2, 'comparisons': 0, 'exhausted': [2], 'key': 0, 'continuation': 1}), ({'challenger': [1, -9, False], 'defender': [2, 4, False]}, {'winner': None, 'stored_loser': None, 'comparisons': 0, 'exhausted': [1, 2], 'key': None, 'continuation': None}), ({'challenger': [3, 1, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 1, 'continuation': 3}), ({'challenger': [3, 2, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 2, 'continuation': 3})], [({'challenger': [1, 0, False], 'defender': [2, 5, True]}, {'winner': 2, 'stored_loser': 1, 'comparisons': 0, 'exhausted': [1], 'key': 5, 'continuation': 2}), ({'challenger': [7, 3, True], 'defender': [2, 3, True]}, {'winner': 2, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 3, 'continuation': 2}), ({'challenger': [4, 8, True], 'defender': [3, 2, True]}, {'winner': 3, 'stored_loser': 4, 'comparisons': 1, 'exhausted': [], 'key': 2, 'continuation': 3}), ({'challenger': [1, 0, True], 'defender': [2, 9, False]}, {'winner': 1, 'stored_loser': 2, 'comparisons': 0, 'exhausted': [2], 'key': 0, 'continuation': 1}), ({'challenger': [1, -9, False], 'defender': [2, 4, False]}, {'winner': None, 'stored_loser': None, 'comparisons': 0, 'exhausted': [1, 2], 'key': None, 'continuation': None}), ({'challenger': [3, 1, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 1, 'continuation': 3}), ({'challenger': [3, 3, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 3, 'continuation': 3})], [({'challenger': [1, 0, False], 'defender': [2, 5, True]}, {'winner': 2, 'stored_loser': 1, 'comparisons': 0, 'exhausted': [1], 'key': 5, 'continuation': 2}), ({'challenger': [7, 3, True], 'defender': [2, 3, True]}, {'winner': 2, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 3, 'continuation': 2}), ({'challenger': [4, 8, True], 'defender': [3, 2, True]}, {'winner': 3, 'stored_loser': 4, 'comparisons': 1, 'exhausted': [], 'key': 2, 'continuation': 3}), ({'challenger': [1, 0, True], 'defender': [2, 9, False]}, {'winner': 1, 'stored_loser': 2, 'comparisons': 0, 'exhausted': [2], 'key': 0, 'continuation': 1}), ({'challenger': [1, -9, False], 'defender': [2, 4, False]}, {'winner': None, 'stored_loser': None, 'comparisons': 0, 'exhausted': [1, 2], 'key': None, 'continuation': None}), ({'challenger': [3, 1, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 1, 'continuation': 3}), ({'challenger': [3, 4, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 4, 'continuation': 3})], [({'challenger': [1, 0, False], 'defender': [2, 5, True]}, {'winner': 2, 'stored_loser': 1, 'comparisons': 0, 'exhausted': [1], 'key': 5, 'continuation': 2}), ({'challenger': [7, 3, True], 'defender': [2, 3, True]}, {'winner': 2, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 3, 'continuation': 2}), ({'challenger': [4, 8, True], 'defender': [3, 2, True]}, {'winner': 3, 'stored_loser': 4, 'comparisons': 1, 'exhausted': [], 'key': 2, 'continuation': 3}), ({'challenger': [1, 0, True], 'defender': [2, 9, False]}, {'winner': 1, 'stored_loser': 2, 'comparisons': 0, 'exhausted': [2], 'key': 0, 'continuation': 1}), ({'challenger': [1, -9, False], 'defender': [2, 4, False]}, {'winner': None, 'stored_loser': None, 'comparisons': 0, 'exhausted': [1, 2], 'key': None, 'continuation': None}), ({'challenger': [3, 1, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 1, 'continuation': 3}), ({'challenger': [3, 5, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 5, 'continuation': 3})], [({'challenger': [1, 0, False], 'defender': [2, 5, True]}, {'winner': 2, 'stored_loser': 1, 'comparisons': 0, 'exhausted': [1], 'key': 5, 'continuation': 2}), ({'challenger': [7, 3, True], 'defender': [2, 3, True]}, {'winner': 2, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 3, 'continuation': 2}), ({'challenger': [4, 8, True], 'defender': [3, 2, True]}, {'winner': 3, 'stored_loser': 4, 'comparisons': 1, 'exhausted': [], 'key': 2, 'continuation': 3}), ({'challenger': [1, 0, True], 'defender': [2, 9, False]}, {'winner': 1, 'stored_loser': 2, 'comparisons': 0, 'exhausted': [2], 'key': 0, 'continuation': 1}), ({'challenger': [1, -9, False], 'defender': [2, 4, False]}, {'winner': None, 'stored_loser': None, 'comparisons': 0, 'exhausted': [1, 2], 'key': None, 'continuation': None}), ({'challenger': [3, 1, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 1, 'continuation': 3}), ({'challenger': [3, 6, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 6, 'continuation': 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 loser match certificate reports an incorrect key.

A loser-tree match compares challenger [run,key,active] and defender likewise. Exhausted entries lose to active entries, ties prefer lower run id, both exhausted produce no winner. Return winner run, stored loser run, active match cost, exhausted runs, winning key, and replay continuation run.

split: open-access


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

N = 1
observations = []
def solve(d):
    a=d['challenger']; b=d['defender']; active=[x for x in (a,b) if x[2]]; win=min(active,key=lambda x:(x[1],x[0])) if active else None; lose=None if win is None else (b if win is a else a)
    return {'winner': None if win is None else win[0],
    'stored_loser': None if lose is None else lose[0],
    'comparisons': int(len(active)==2),
    'exhausted': [x[0] for x in (a,b) if not x[2]],
    'key': None if win is None else win[1],
    'continuation': None if lose is None else lose[0]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'challenger': [1, 0, False], 'defender': [2, 5, True]}, {'winner': 2, 'stored_loser': 1, 'comparisons': 0, 'exhausted': [1], 'key': 5, 'continuation': 2}), ({'challenger': [7, 3, True], 'defender': [2, 3, True]}, {'winner': 2, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 3, 'continuation': 2}), ({'challenger': [4, 8, True], 'defender': [3, 2, True]}, {'winner': 3, 'stored_loser': 4, 'comparisons': 1, 'exhausted': [], 'key': 2, 'continuation': 3}), ({'challenger': [1, 0, True], 'defender': [2, 9, False]}, {'winner': 1, 'stored_loser': 2, 'comparisons': 0, 'exhausted': [2], 'key': 0, 'continuation': 1}), ({'challenger': [1, -9, False], 'defender': [2, 4, False]}, {'winner': None, 'stored_loser': None, 'comparisons': 0, 'exhausted': [1, 2], 'key': None, 'continuation': None}), ({'challenger': [3, 1, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 1, 'continuation': 3}), ({'challenger': [3, 2, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 2, 'continuation': 3})], [({'challenger': [1, 0, False], 'defender': [2, 5, True]}, {'winner': 2, 'stored_loser': 1, 'comparisons': 0, 'exhausted': [1], 'key': 5, 'continuation': 2}), ({'challenger': [7, 3, True], 'defender': [2, 3, True]}, {'winner': 2, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 3, 'continuation': 2}), ({'challenger': [4, 8, True], 'defender': [3, 2, True]}, {'winner': 3, 'stored_loser': 4, 'comparisons': 1, 'exhausted': [], 'key': 2, 'continuation': 3}), ({'challenger': [1, 0, True], 'defender': [2, 9, False]}, {'winner': 1, 'stored_loser': 2, 'comparisons': 0, 'exhausted': [2], 'key': 0, 'continuation': 1}), ({'challenger': [1, -9, False], 'defender': [2, 4, False]}, {'winner': None, 'stored_loser': None, 'comparisons': 0, 'exhausted': [1, 2], 'key': None, 'continuation': None}), ({'challenger': [3, 1, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 1, 'continuation': 3}), ({'challenger': [3, 3, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 3, 'continuation': 3})], [({'challenger': [1, 0, False], 'defender': [2, 5, True]}, {'winner': 2, 'stored_loser': 1, 'comparisons': 0, 'exhausted': [1], 'key': 5, 'continuation': 2}), ({'challenger': [7, 3, True], 'defender': [2, 3, True]}, {'winner': 2, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 3, 'continuation': 2}), ({'challenger': [4, 8, True], 'defender': [3, 2, True]}, {'winner': 3, 'stored_loser': 4, 'comparisons': 1, 'exhausted': [], 'key': 2, 'continuation': 3}), ({'challenger': [1, 0, True], 'defender': [2, 9, False]}, {'winner': 1, 'stored_loser': 2, 'comparisons': 0, 'exhausted': [2], 'key': 0, 'continuation': 1}), ({'challenger': [1, -9, False], 'defender': [2, 4, False]}, {'winner': None, 'stored_loser': None, 'comparisons': 0, 'exhausted': [1, 2], 'key': None, 'continuation': None}), ({'challenger': [3, 1, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 1, 'continuation': 3}), ({'challenger': [3, 4, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 4, 'continuation': 3})], [({'challenger': [1, 0, False], 'defender': [2, 5, True]}, {'winner': 2, 'stored_loser': 1, 'comparisons': 0, 'exhausted': [1], 'key': 5, 'continuation': 2}), ({'challenger': [7, 3, True], 'defender': [2, 3, True]}, {'winner': 2, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 3, 'continuation': 2}), ({'challenger': [4, 8, True], 'defender': [3, 2, True]}, {'winner': 3, 'stored_loser': 4, 'comparisons': 1, 'exhausted': [], 'key': 2, 'continuation': 3}), ({'challenger': [1, 0, True], 'defender': [2, 9, False]}, {'winner': 1, 'stored_loser': 2, 'comparisons': 0, 'exhausted': [2], 'key': 0, 'continuation': 1}), ({'challenger': [1, -9, False], 'defender': [2, 4, False]}, {'winner': None, 'stored_loser': None, 'comparisons': 0, 'exhausted': [1, 2], 'key': None, 'continuation': None}), ({'challenger': [3, 1, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 1, 'continuation': 3}), ({'challenger': [3, 5, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 5, 'continuation': 3})], [({'challenger': [1, 0, False], 'defender': [2, 5, True]}, {'winner': 2, 'stored_loser': 1, 'comparisons': 0, 'exhausted': [1], 'key': 5, 'continuation': 2}), ({'challenger': [7, 3, True], 'defender': [2, 3, True]}, {'winner': 2, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 3, 'continuation': 2}), ({'challenger': [4, 8, True], 'defender': [3, 2, True]}, {'winner': 3, 'stored_loser': 4, 'comparisons': 1, 'exhausted': [], 'key': 2, 'continuation': 3}), ({'challenger': [1, 0, True], 'defender': [2, 9, False]}, {'winner': 1, 'stored_loser': 2, 'comparisons': 0, 'exhausted': [2], 'key': 0, 'continuation': 1}), ({'challenger': [1, -9, False], 'defender': [2, 4, False]}, {'winner': None, 'stored_loser': None, 'comparisons': 0, 'exhausted': [1, 2], 'key': None, 'continuation': None}), ({'challenger': [3, 1, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 1, 'continuation': 3}), ({'challenger': [3, 6, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 6, 'continuation': 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['challenger']; b=d['defender']; active=[x for x in (a,b) if x[2]]; win=min(active,key=lambda x:(x[1],x[0])) if active else None; lose=None if win is None else (b if win is a else a)
    return {'winner': None if win is None else win[0],
    'stored_loser': None if lose is None else lose[0],
    'comparisons': int(len(active)==2),
    'exhausted': [x[0] for x in (a,b) if not x[2]],
    'key': None if win is None else win[1],
    'continuation': a[0]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'challenger': [1, 0, False], 'defender': [2, 5, True]}, {'winner': 2, 'stored_loser': 1, 'comparisons': 0, 'exhausted': [1], 'key': 5, 'continuation': 2}), ({'challenger': [7, 3, True], 'defender': [2, 3, True]}, {'winner': 2, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 3, 'continuation': 2}), ({'challenger': [4, 8, True], 'defender': [3, 2, True]}, {'winner': 3, 'stored_loser': 4, 'comparisons': 1, 'exhausted': [], 'key': 2, 'continuation': 3}), ({'challenger': [1, 0, True], 'defender': [2, 9, False]}, {'winner': 1, 'stored_loser': 2, 'comparisons': 0, 'exhausted': [2], 'key': 0, 'continuation': 1}), ({'challenger': [1, -9, False], 'defender': [2, 4, False]}, {'winner': None, 'stored_loser': None, 'comparisons': 0, 'exhausted': [1, 2], 'key': None, 'continuation': None}), ({'challenger': [3, 1, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 1, 'continuation': 3}), ({'challenger': [3, 2, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 2, 'continuation': 3})], [({'challenger': [1, 0, False], 'defender': [2, 5, True]}, {'winner': 2, 'stored_loser': 1, 'comparisons': 0, 'exhausted': [1], 'key': 5, 'continuation': 2}), ({'challenger': [7, 3, True], 'defender': [2, 3, True]}, {'winner': 2, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 3, 'continuation': 2}), ({'challenger': [4, 8, True], 'defender': [3, 2, True]}, {'winner': 3, 'stored_loser': 4, 'comparisons': 1, 'exhausted': [], 'key': 2, 'continuation': 3}), ({'challenger': [1, 0, True], 'defender': [2, 9, False]}, {'winner': 1, 'stored_loser': 2, 'comparisons': 0, 'exhausted': [2], 'key': 0, 'continuation': 1}), ({'challenger': [1, -9, False], 'defender': [2, 4, False]}, {'winner': None, 'stored_loser': None, 'comparisons': 0, 'exhausted': [1, 2], 'key': None, 'continuation': None}), ({'challenger': [3, 1, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 1, 'continuation': 3}), ({'challenger': [3, 3, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 3, 'continuation': 3})], [({'challenger': [1, 0, False], 'defender': [2, 5, True]}, {'winner': 2, 'stored_loser': 1, 'comparisons': 0, 'exhausted': [1], 'key': 5, 'continuation': 2}), ({'challenger': [7, 3, True], 'defender': [2, 3, True]}, {'winner': 2, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 3, 'continuation': 2}), ({'challenger': [4, 8, True], 'defender': [3, 2, True]}, {'winner': 3, 'stored_loser': 4, 'comparisons': 1, 'exhausted': [], 'key': 2, 'continuation': 3}), ({'challenger': [1, 0, True], 'defender': [2, 9, False]}, {'winner': 1, 'stored_loser': 2, 'comparisons': 0, 'exhausted': [2], 'key': 0, 'continuation': 1}), ({'challenger': [1, -9, False], 'defender': [2, 4, False]}, {'winner': None, 'stored_loser': None, 'comparisons': 0, 'exhausted': [1, 2], 'key': None, 'continuation': None}), ({'challenger': [3, 1, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 1, 'continuation': 3}), ({'challenger': [3, 4, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 4, 'continuation': 3})], [({'challenger': [1, 0, False], 'defender': [2, 5, True]}, {'winner': 2, 'stored_loser': 1, 'comparisons': 0, 'exhausted': [1], 'key': 5, 'continuation': 2}), ({'challenger': [7, 3, True], 'defender': [2, 3, True]}, {'winner': 2, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 3, 'continuation': 2}), ({'challenger': [4, 8, True], 'defender': [3, 2, True]}, {'winner': 3, 'stored_loser': 4, 'comparisons': 1, 'exhausted': [], 'key': 2, 'continuation': 3}), ({'challenger': [1, 0, True], 'defender': [2, 9, False]}, {'winner': 1, 'stored_loser': 2, 'comparisons': 0, 'exhausted': [2], 'key': 0, 'continuation': 1}), ({'challenger': [1, -9, False], 'defender': [2, 4, False]}, {'winner': None, 'stored_loser': None, 'comparisons': 0, 'exhausted': [1, 2], 'key': None, 'continuation': None}), ({'challenger': [3, 1, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 1, 'continuation': 3}), ({'challenger': [3, 5, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 5, 'continuation': 3})], [({'challenger': [1, 0, False], 'defender': [2, 5, True]}, {'winner': 2, 'stored_loser': 1, 'comparisons': 0, 'exhausted': [1], 'key': 5, 'continuation': 2}), ({'challenger': [7, 3, True], 'defender': [2, 3, True]}, {'winner': 2, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 3, 'continuation': 2}), ({'challenger': [4, 8, True], 'defender': [3, 2, True]}, {'winner': 3, 'stored_loser': 4, 'comparisons': 1, 'exhausted': [], 'key': 2, 'continuation': 3}), ({'challenger': [1, 0, True], 'defender': [2, 9, False]}, {'winner': 1, 'stored_loser': 2, 'comparisons': 0, 'exhausted': [2], 'key': 0, 'continuation': 1}), ({'challenger': [1, -9, False], 'defender': [2, 4, False]}, {'winner': None, 'stored_loser': None, 'comparisons': 0, 'exhausted': [1, 2], 'key': None, 'continuation': None}), ({'challenger': [3, 1, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 1, 'continuation': 3}), ({'challenger': [3, 6, True], 'defender': [7, 9, True]}, {'winner': 3, 'stored_loser': 7, 'comparisons': 1, 'exhausted': [], 'key': 6, 'continuation': 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 loser match certificate reports an incorrect continuation.

A loser-tree match compares challenger [run,key,active] and defender likewise. Exhausted entries lose to active entries, ties prefer lower run id, both exhausted produce no winner. Return winner run, stored loser run, active match cost, exhausted runs, winning key, and replay continuation run.

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': None if start==0 else start//2,
    'path': path,
    'cost': len(path),
    'stop': j,
    'orientation': None if start==0 else r[j//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': None if start==0 else (start-1)//2,
    'path': path,
    'cost': len(path),
    'stop': j,
    'orientation': None if start==0 else r[j//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)

prompt:
The bounded weak ancestor certificate reports an incorrect ancestor.

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': list(reversed(path)),
    'cost': len(path),
    'stop': j,
    'orientation': None if start==0 else r[j//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[1:],
    'cost': len(path),
    'stop': j,
    'orientation': None if start==0 else r[j//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)

prompt:
The bounded weak ancestor certificate reports an incorrect path.

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': 0 if start==0 else 1,
    'stop': j,
    'orientation': None if start==0 else r[j//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)+1,
    'stop': j,
    'orientation': None if start==0 else r[j//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)

prompt:
The bounded weak ancestor certificate reports an incorrect cost.

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': start,
    'orientation': None if start==0 else r[j//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//2,
    'orientation': None if start==0 else r[j//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)

prompt:
The bounded weak ancestor certificate reports an incorrect stop.

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