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

N = 1
observations = []
def solve(d):
    c=d['capacity']; s=d['slot']; leaf=c+s; path=[]; siblings=[]; v=leaf
    while v>1:
        siblings.append(v^1); v//=2; path.append(v)
    return {'replay': path,
    'siblings': siblings,
    'root': 0,
    'comparisons': len(path),
    'leaf': leaf,
    'untouched': [i for i in range(c) if i!=s]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 1}, {'replay': [8, 4, 2, 1], 'siblings': [16, 9, 5, 3], 'root': 1, 'comparisons': 4, 'leaf': 17, 'untouched': [0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 2}, {'replay': [9, 4, 2, 1], 'siblings': [19, 8, 5, 3], 'root': 1, 'comparisons': 4, 'leaf': 18, 'untouched': [0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 3}, {'replay': [9, 4, 2, 1], 'siblings': [18, 8, 5, 3], 'root': 1, 'comparisons': 4, 'leaf': 19, 'untouched': [0, 1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 4}, {'replay': [10, 5, 2, 1], 'siblings': [21, 11, 4, 3], 'root': 1, 'comparisons': 4, 'leaf': 20, 'untouched': [0, 1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 5}, {'replay': [10, 5, 2, 1], 'siblings': [20, 11, 4, 3], 'root': 1, 'comparisons': 4, 'leaf': 21, 'untouched': [0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})]][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):
    c=d['capacity']; s=d['slot']; leaf=c+s; path=[]; siblings=[]; v=leaf
    while v>1:
        siblings.append(v^1); v//=2; path.append(v)
    return {'replay': path,
    'siblings': siblings,
    'root': c,
    'comparisons': len(path),
    'leaf': leaf,
    'untouched': [i for i in range(c) if i!=s]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 1}, {'replay': [8, 4, 2, 1], 'siblings': [16, 9, 5, 3], 'root': 1, 'comparisons': 4, 'leaf': 17, 'untouched': [0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 2}, {'replay': [9, 4, 2, 1], 'siblings': [19, 8, 5, 3], 'root': 1, 'comparisons': 4, 'leaf': 18, 'untouched': [0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 3}, {'replay': [9, 4, 2, 1], 'siblings': [18, 8, 5, 3], 'root': 1, 'comparisons': 4, 'leaf': 19, 'untouched': [0, 1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 4}, {'replay': [10, 5, 2, 1], 'siblings': [21, 11, 4, 3], 'root': 1, 'comparisons': 4, 'leaf': 20, 'untouched': [0, 1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 5}, {'replay': [10, 5, 2, 1], 'siblings': [20, 11, 4, 3], 'root': 1, 'comparisons': 4, 'leaf': 21, 'untouched': [0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})]][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 tournament path certificate reports an incorrect root.

A complete winner tournament has power-of-two leaf capacity c and updated leaf slot s. Tree leaves occupy c+s. Report ancestors in bottom-up replay order, sibling indices along that path, root index, comparison count, leaf index, and unaffected leaf slots. Capacity at least one; slot is in range.

split: open-access


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

N = 1
observations = []
def solve(d):
    c=d['capacity']; s=d['slot']; leaf=c+s; path=[]; siblings=[]; v=leaf
    while v>1:
        siblings.append(v^1); v//=2; path.append(v)
    return {'replay': path,
    'siblings': siblings,
    'root': 1,
    'comparisons': c-1,
    'leaf': leaf,
    'untouched': [i for i in range(c) if i!=s]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 1}, {'replay': [8, 4, 2, 1], 'siblings': [16, 9, 5, 3], 'root': 1, 'comparisons': 4, 'leaf': 17, 'untouched': [0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 2}, {'replay': [9, 4, 2, 1], 'siblings': [19, 8, 5, 3], 'root': 1, 'comparisons': 4, 'leaf': 18, 'untouched': [0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 3}, {'replay': [9, 4, 2, 1], 'siblings': [18, 8, 5, 3], 'root': 1, 'comparisons': 4, 'leaf': 19, 'untouched': [0, 1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 4}, {'replay': [10, 5, 2, 1], 'siblings': [21, 11, 4, 3], 'root': 1, 'comparisons': 4, 'leaf': 20, 'untouched': [0, 1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 5}, {'replay': [10, 5, 2, 1], 'siblings': [20, 11, 4, 3], 'root': 1, 'comparisons': 4, 'leaf': 21, 'untouched': [0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})]][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):
    c=d['capacity']; s=d['slot']; leaf=c+s; path=[]; siblings=[]; v=leaf
    while v>1:
        siblings.append(v^1); v//=2; path.append(v)
    return {'replay': path,
    'siblings': siblings,
    'root': 1,
    'comparisons': max(0,len(path)-1),
    'leaf': leaf,
    'untouched': [i for i in range(c) if i!=s]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 1}, {'replay': [8, 4, 2, 1], 'siblings': [16, 9, 5, 3], 'root': 1, 'comparisons': 4, 'leaf': 17, 'untouched': [0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 2}, {'replay': [9, 4, 2, 1], 'siblings': [19, 8, 5, 3], 'root': 1, 'comparisons': 4, 'leaf': 18, 'untouched': [0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 3}, {'replay': [9, 4, 2, 1], 'siblings': [18, 8, 5, 3], 'root': 1, 'comparisons': 4, 'leaf': 19, 'untouched': [0, 1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 4}, {'replay': [10, 5, 2, 1], 'siblings': [21, 11, 4, 3], 'root': 1, 'comparisons': 4, 'leaf': 20, 'untouched': [0, 1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 5}, {'replay': [10, 5, 2, 1], 'siblings': [20, 11, 4, 3], 'root': 1, 'comparisons': 4, 'leaf': 21, 'untouched': [0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})]][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 tournament path certificate reports an incorrect comparisons.

A complete winner tournament has power-of-two leaf capacity c and updated leaf slot s. Tree leaves occupy c+s. Report ancestors in bottom-up replay order, sibling indices along that path, root index, comparison count, leaf index, and unaffected leaf slots. Capacity at least one; slot is in range.

split: open-access


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

N = 1
observations = []
def solve(d):
    c=d['capacity']; s=d['slot']; leaf=c+s; path=[]; siblings=[]; v=leaf
    while v>1:
        siblings.append(v^1); v//=2; path.append(v)
    return {'replay': path,
    'siblings': siblings,
    'root': 1,
    'comparisons': len(path),
    'leaf': s,
    'untouched': [i for i in range(c) if i!=s]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 1}, {'replay': [8, 4, 2, 1], 'siblings': [16, 9, 5, 3], 'root': 1, 'comparisons': 4, 'leaf': 17, 'untouched': [0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 2}, {'replay': [9, 4, 2, 1], 'siblings': [19, 8, 5, 3], 'root': 1, 'comparisons': 4, 'leaf': 18, 'untouched': [0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 3}, {'replay': [9, 4, 2, 1], 'siblings': [18, 8, 5, 3], 'root': 1, 'comparisons': 4, 'leaf': 19, 'untouched': [0, 1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 4}, {'replay': [10, 5, 2, 1], 'siblings': [21, 11, 4, 3], 'root': 1, 'comparisons': 4, 'leaf': 20, 'untouched': [0, 1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 5}, {'replay': [10, 5, 2, 1], 'siblings': [20, 11, 4, 3], 'root': 1, 'comparisons': 4, 'leaf': 21, 'untouched': [0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})]][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):
    c=d['capacity']; s=d['slot']; leaf=c+s; path=[]; siblings=[]; v=leaf
    while v>1:
        siblings.append(v^1); v//=2; path.append(v)
    return {'replay': path,
    'siblings': siblings,
    'root': 1,
    'comparisons': len(path),
    'leaf': c+s-1,
    'untouched': [i for i in range(c) if i!=s]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 1}, {'replay': [8, 4, 2, 1], 'siblings': [16, 9, 5, 3], 'root': 1, 'comparisons': 4, 'leaf': 17, 'untouched': [0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 2}, {'replay': [9, 4, 2, 1], 'siblings': [19, 8, 5, 3], 'root': 1, 'comparisons': 4, 'leaf': 18, 'untouched': [0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 3}, {'replay': [9, 4, 2, 1], 'siblings': [18, 8, 5, 3], 'root': 1, 'comparisons': 4, 'leaf': 19, 'untouched': [0, 1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 4}, {'replay': [10, 5, 2, 1], 'siblings': [21, 11, 4, 3], 'root': 1, 'comparisons': 4, 'leaf': 20, 'untouched': [0, 1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 5}, {'replay': [10, 5, 2, 1], 'siblings': [20, 11, 4, 3], 'root': 1, 'comparisons': 4, 'leaf': 21, 'untouched': [0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})]][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 tournament path certificate reports an incorrect leaf.

A complete winner tournament has power-of-two leaf capacity c and updated leaf slot s. Tree leaves occupy c+s. Report ancestors in bottom-up replay order, sibling indices along that path, root index, comparison count, leaf index, and unaffected leaf slots. Capacity at least one; slot is in range.

split: open-access


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

N = 1
observations = []
def solve(d):
    c=d['capacity']; s=d['slot']; leaf=c+s; path=[]; siblings=[]; v=leaf
    while v>1:
        siblings.append(v^1); v//=2; path.append(v)
    return {'replay': path,
    'siblings': siblings,
    'root': 1,
    'comparisons': len(path),
    'leaf': leaf,
    'untouched': [i for i in range(c) if i!=leaf]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 1}, {'replay': [8, 4, 2, 1], 'siblings': [16, 9, 5, 3], 'root': 1, 'comparisons': 4, 'leaf': 17, 'untouched': [0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 2}, {'replay': [9, 4, 2, 1], 'siblings': [19, 8, 5, 3], 'root': 1, 'comparisons': 4, 'leaf': 18, 'untouched': [0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 3}, {'replay': [9, 4, 2, 1], 'siblings': [18, 8, 5, 3], 'root': 1, 'comparisons': 4, 'leaf': 19, 'untouched': [0, 1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 4}, {'replay': [10, 5, 2, 1], 'siblings': [21, 11, 4, 3], 'root': 1, 'comparisons': 4, 'leaf': 20, 'untouched': [0, 1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 5}, {'replay': [10, 5, 2, 1], 'siblings': [20, 11, 4, 3], 'root': 1, 'comparisons': 4, 'leaf': 21, 'untouched': [0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})]][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):
    c=d['capacity']; s=d['slot']; leaf=c+s; path=[]; siblings=[]; v=leaf
    while v>1:
        siblings.append(v^1); v//=2; path.append(v)
    return {'replay': path,
    'siblings': siblings,
    'root': 1,
    'comparisons': len(path),
    'leaf': leaf,
    'untouched': []}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 1}, {'replay': [8, 4, 2, 1], 'siblings': [16, 9, 5, 3], 'root': 1, 'comparisons': 4, 'leaf': 17, 'untouched': [0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 2}, {'replay': [9, 4, 2, 1], 'siblings': [19, 8, 5, 3], 'root': 1, 'comparisons': 4, 'leaf': 18, 'untouched': [0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 3}, {'replay': [9, 4, 2, 1], 'siblings': [18, 8, 5, 3], 'root': 1, 'comparisons': 4, 'leaf': 19, 'untouched': [0, 1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 4}, {'replay': [10, 5, 2, 1], 'siblings': [21, 11, 4, 3], 'root': 1, 'comparisons': 4, 'leaf': 20, 'untouched': [0, 1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})], [({'capacity': 1, 'slot': 0}, {'replay': [], 'siblings': [], 'root': 1, 'comparisons': 0, 'leaf': 1, 'untouched': []}), ({'capacity': 2, 'slot': 1}, {'replay': [1], 'siblings': [2], 'root': 1, 'comparisons': 1, 'leaf': 3, 'untouched': [0]}), ({'capacity': 4, 'slot': 0}, {'replay': [2, 1], 'siblings': [5, 3], 'root': 1, 'comparisons': 2, 'leaf': 4, 'untouched': [1, 2, 3]}), ({'capacity': 4, 'slot': 3}, {'replay': [3, 1], 'siblings': [6, 2], 'root': 1, 'comparisons': 2, 'leaf': 7, 'untouched': [0, 1, 2]}), ({'capacity': 8, 'slot': 5}, {'replay': [6, 3, 1], 'siblings': [12, 7, 2], 'root': 1, 'comparisons': 3, 'leaf': 13, 'untouched': [0, 1, 2, 3, 4, 6, 7]}), ({'capacity': 16, 'slot': 10}, {'replay': [13, 6, 3, 1], 'siblings': [27, 12, 7, 2], 'root': 1, 'comparisons': 4, 'leaf': 26, 'untouched': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15]}), ({'capacity': 16, 'slot': 5}, {'replay': [10, 5, 2, 1], 'siblings': [20, 11, 4, 3], 'root': 1, 'comparisons': 4, 'leaf': 21, 'untouched': [0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]})]][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 tournament path certificate reports an incorrect untouched.

A complete winner tournament has power-of-two leaf capacity c and updated leaf slot s. Tree leaves occupy c+s. Report ancestors in bottom-up replay order, sibling indices along that path, root index, comparison count, leaf index, and unaffected leaf slots. Capacity at least one; slot is in range.

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': min((a,b),key=lambda x:(x[1],x[0]))[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 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': a[0] if a[2] else b[0] if b[2] else None,
    '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 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 winner.

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 win is None else win[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 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': b[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 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 stored loser.

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': 1,
    'exhausted': [x[0] for x in (a,b) if not x[2]],
    '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': len(active),
    'exhausted': [x[0] for x in (a,b) if not x[2]],
    '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 comparisons.

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