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

N = 1
observations = []
def solve(d):
    path=d['path']; cut=[]; marked=None; visited=0
    for ident,root,mark in path:
        visited+=1
        if root: break
        if not mark:
            marked=ident; break
        cut.append(ident)
    return {'cuts': cut,
    'new_mark': marked,
    'cleared': cut,
    'visits': visited,
    'promoted_count': visited,
    'potential_delta': -len(cut)+(2 if marked is not None else 0)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'path': []}, {'cuts': [], 'new_mark': None, 'cleared': [], 'visits': 0, 'promoted_count': 0, 'potential_delta': 0}), ({'path': [[1, True, False]]}, {'cuts': [], 'new_mark': None, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 0}), ({'path': [[1, False, False], [2, True, False]]}, {'cuts': [], 'new_mark': 1, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 2}), ({'path': [[1, False, True], [2, False, False], [3, True, False]]}, {'cuts': [1], 'new_mark': 2, 'cleared': [1], 'visits': 2, 'promoted_count': 1, 'potential_delta': 1}), ({'path': [[1, False, True], [2, False, True], [3, True, True]]}, {'cuts': [1, 2], 'new_mark': None, 'cleared': [1, 2], 'visits': 3, 'promoted_count': 2, 'potential_delta': -2}), ({'path': [[1, False, False], [2, False, True], [3, True, False]]}, {'cuts': [], 'new_mark': 1, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 2}), ({'path': [[100, False, True], [1, False, False], [2, False, True], [3, True, False]]}, {'cuts': [100], 'new_mark': 1, 'cleared': [100], 'visits': 2, 'promoted_count': 1, 'potential_delta': 1})], [({'path': []}, {'cuts': [], 'new_mark': None, 'cleared': [], 'visits': 0, 'promoted_count': 0, 'potential_delta': 0}), ({'path': [[1, True, False]]}, {'cuts': [], 'new_mark': None, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 0}), ({'path': [[1, False, False], [2, True, False]]}, {'cuts': [], 'new_mark': 1, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 2}), ({'path': [[1, False, True], [2, False, False], [3, True, False]]}, {'cuts': [1], 'new_mark': 2, 'cleared': [1], 'visits': 2, 'promoted_count': 1, 'potential_delta': 1}), ({'path': [[1, False, True], [2, False, True], [3, True, True]]}, {'cuts': [1, 2], 'new_mark': None, 'cleared': [1, 2], 'visits': 3, 'promoted_count': 2, 'potential_delta': -2}), ({'path': [[1, False, False], [2, False, True], [3, True, False]]}, {'cuts': [], 'new_mark': 1, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 2}), ({'path': [[100, False, True], [101, False, True], [1, False, False], [2, False, True], [3, True, False]]}, {'cuts': [100, 101], 'new_mark': 1, 'cleared': [100, 101], 'visits': 3, 'promoted_count': 2, 'potential_delta': 0})], [({'path': []}, {'cuts': [], 'new_mark': None, 'cleared': [], 'visits': 0, 'promoted_count': 0, 'potential_delta': 0}), ({'path': [[1, True, False]]}, {'cuts': [], 'new_mark': None, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 0}), ({'path': [[1, False, False], [2, True, False]]}, {'cuts': [], 'new_mark': 1, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 2}), ({'path': [[1, False, True], [2, False, False], [3, True, False]]}, {'cuts': [1], 'new_mark': 2, 'cleared': [1], 'visits': 2, 'promoted_count': 1, 'potential_delta': 1}), ({'path': [[1, False, True], [2, False, True], [3, True, True]]}, {'cuts': [1, 2], 'new_mark': None, 'cleared': [1, 2], 'visits': 3, 'promoted_count': 2, 'potential_delta': -2}), ({'path': [[1, False, False], [2, False, True], [3, True, False]]}, {'cuts': [], 'new_mark': 1, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 2}), ({'path': [[100, False, True], [101, False, True], [102, False, True], [1, False, False], [2, False, True], [3, True, False]]}, {'cuts': [100, 101, 102], 'new_mark': 1, 'cleared': [100, 101, 102], 'visits': 4, 'promoted_count': 3, 'potential_delta': -1})], [({'path': []}, {'cuts': [], 'new_mark': None, 'cleared': [], 'visits': 0, 'promoted_count': 0, 'potential_delta': 0}), ({'path': [[1, True, False]]}, {'cuts': [], 'new_mark': None, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 0}), ({'path': [[1, False, False], [2, True, False]]}, {'cuts': [], 'new_mark': 1, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 2}), ({'path': [[1, False, True], [2, False, False], [3, True, False]]}, {'cuts': [1], 'new_mark': 2, 'cleared': [1], 'visits': 2, 'promoted_count': 1, 'potential_delta': 1}), ({'path': [[1, False, True], [2, False, True], [3, True, True]]}, {'cuts': [1, 2], 'new_mark': None, 'cleared': [1, 2], 'visits': 3, 'promoted_count': 2, 'potential_delta': -2}), ({'path': [[1, False, False], [2, False, True], [3, True, False]]}, {'cuts': [], 'new_mark': 1, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 2}), ({'path': [[100, False, True], [101, False, True], [102, False, True], [103, False, True], [1, False, False], [2, False, True], [3, True, False]]}, {'cuts': [100, 101, 102, 103], 'new_mark': 1, 'cleared': [100, 101, 102, 103], 'visits': 5, 'promoted_count': 4, 'potential_delta': -2})], [({'path': []}, {'cuts': [], 'new_mark': None, 'cleared': [], 'visits': 0, 'promoted_count': 0, 'potential_delta': 0}), ({'path': [[1, True, False]]}, {'cuts': [], 'new_mark': None, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 0}), ({'path': [[1, False, False], [2, True, False]]}, {'cuts': [], 'new_mark': 1, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 2}), ({'path': [[1, False, True], [2, False, False], [3, True, False]]}, {'cuts': [1], 'new_mark': 2, 'cleared': [1], 'visits': 2, 'promoted_count': 1, 'potential_delta': 1}), ({'path': [[1, False, True], [2, False, True], [3, True, True]]}, {'cuts': [1, 2], 'new_mark': None, 'cleared': [1, 2], 'visits': 3, 'promoted_count': 2, 'potential_delta': -2}), ({'path': [[1, False, False], [2, False, True], [3, True, False]]}, {'cuts': [], 'new_mark': 1, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 2}), ({'path': [[100, False, True], [101, False, True], [102, False, True], [103, False, True], [104, False, True], [1, False, False], [2, False, True], [3, True, False]]}, {'cuts': [100, 101, 102, 103, 104], 'new_mark': 1, 'cleared': [100, 101, 102, 103, 104], 'visits': 6, 'promoted_count': 5, 'potential_delta': -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):
    path=d['path']; cut=[]; marked=None; visited=0
    for ident,root,mark in path:
        visited+=1
        if root: break
        if not mark:
            marked=ident; break
        cut.append(ident)
    return {'cuts': cut,
    'new_mark': marked,
    'cleared': cut,
    'visits': visited,
    'promoted_count': max(0,len(cut)-1),
    'potential_delta': -len(cut)+(2 if marked is not None else 0)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'path': []}, {'cuts': [], 'new_mark': None, 'cleared': [], 'visits': 0, 'promoted_count': 0, 'potential_delta': 0}), ({'path': [[1, True, False]]}, {'cuts': [], 'new_mark': None, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 0}), ({'path': [[1, False, False], [2, True, False]]}, {'cuts': [], 'new_mark': 1, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 2}), ({'path': [[1, False, True], [2, False, False], [3, True, False]]}, {'cuts': [1], 'new_mark': 2, 'cleared': [1], 'visits': 2, 'promoted_count': 1, 'potential_delta': 1}), ({'path': [[1, False, True], [2, False, True], [3, True, True]]}, {'cuts': [1, 2], 'new_mark': None, 'cleared': [1, 2], 'visits': 3, 'promoted_count': 2, 'potential_delta': -2}), ({'path': [[1, False, False], [2, False, True], [3, True, False]]}, {'cuts': [], 'new_mark': 1, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 2}), ({'path': [[100, False, True], [1, False, False], [2, False, True], [3, True, False]]}, {'cuts': [100], 'new_mark': 1, 'cleared': [100], 'visits': 2, 'promoted_count': 1, 'potential_delta': 1})], [({'path': []}, {'cuts': [], 'new_mark': None, 'cleared': [], 'visits': 0, 'promoted_count': 0, 'potential_delta': 0}), ({'path': [[1, True, False]]}, {'cuts': [], 'new_mark': None, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 0}), ({'path': [[1, False, False], [2, True, False]]}, {'cuts': [], 'new_mark': 1, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 2}), ({'path': [[1, False, True], [2, False, False], [3, True, False]]}, {'cuts': [1], 'new_mark': 2, 'cleared': [1], 'visits': 2, 'promoted_count': 1, 'potential_delta': 1}), ({'path': [[1, False, True], [2, False, True], [3, True, True]]}, {'cuts': [1, 2], 'new_mark': None, 'cleared': [1, 2], 'visits': 3, 'promoted_count': 2, 'potential_delta': -2}), ({'path': [[1, False, False], [2, False, True], [3, True, False]]}, {'cuts': [], 'new_mark': 1, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 2}), ({'path': [[100, False, True], [101, False, True], [1, False, False], [2, False, True], [3, True, False]]}, {'cuts': [100, 101], 'new_mark': 1, 'cleared': [100, 101], 'visits': 3, 'promoted_count': 2, 'potential_delta': 0})], [({'path': []}, {'cuts': [], 'new_mark': None, 'cleared': [], 'visits': 0, 'promoted_count': 0, 'potential_delta': 0}), ({'path': [[1, True, False]]}, {'cuts': [], 'new_mark': None, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 0}), ({'path': [[1, False, False], [2, True, False]]}, {'cuts': [], 'new_mark': 1, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 2}), ({'path': [[1, False, True], [2, False, False], [3, True, False]]}, {'cuts': [1], 'new_mark': 2, 'cleared': [1], 'visits': 2, 'promoted_count': 1, 'potential_delta': 1}), ({'path': [[1, False, True], [2, False, True], [3, True, True]]}, {'cuts': [1, 2], 'new_mark': None, 'cleared': [1, 2], 'visits': 3, 'promoted_count': 2, 'potential_delta': -2}), ({'path': [[1, False, False], [2, False, True], [3, True, False]]}, {'cuts': [], 'new_mark': 1, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 2}), ({'path': [[100, False, True], [101, False, True], [102, False, True], [1, False, False], [2, False, True], [3, True, False]]}, {'cuts': [100, 101, 102], 'new_mark': 1, 'cleared': [100, 101, 102], 'visits': 4, 'promoted_count': 3, 'potential_delta': -1})], [({'path': []}, {'cuts': [], 'new_mark': None, 'cleared': [], 'visits': 0, 'promoted_count': 0, 'potential_delta': 0}), ({'path': [[1, True, False]]}, {'cuts': [], 'new_mark': None, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 0}), ({'path': [[1, False, False], [2, True, False]]}, {'cuts': [], 'new_mark': 1, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 2}), ({'path': [[1, False, True], [2, False, False], [3, True, False]]}, {'cuts': [1], 'new_mark': 2, 'cleared': [1], 'visits': 2, 'promoted_count': 1, 'potential_delta': 1}), ({'path': [[1, False, True], [2, False, True], [3, True, True]]}, {'cuts': [1, 2], 'new_mark': None, 'cleared': [1, 2], 'visits': 3, 'promoted_count': 2, 'potential_delta': -2}), ({'path': [[1, False, False], [2, False, True], [3, True, False]]}, {'cuts': [], 'new_mark': 1, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 2}), ({'path': [[100, False, True], [101, False, True], [102, False, True], [103, False, True], [1, False, False], [2, False, True], [3, True, False]]}, {'cuts': [100, 101, 102, 103], 'new_mark': 1, 'cleared': [100, 101, 102, 103], 'visits': 5, 'promoted_count': 4, 'potential_delta': -2})], [({'path': []}, {'cuts': [], 'new_mark': None, 'cleared': [], 'visits': 0, 'promoted_count': 0, 'potential_delta': 0}), ({'path': [[1, True, False]]}, {'cuts': [], 'new_mark': None, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 0}), ({'path': [[1, False, False], [2, True, False]]}, {'cuts': [], 'new_mark': 1, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 2}), ({'path': [[1, False, True], [2, False, False], [3, True, False]]}, {'cuts': [1], 'new_mark': 2, 'cleared': [1], 'visits': 2, 'promoted_count': 1, 'potential_delta': 1}), ({'path': [[1, False, True], [2, False, True], [3, True, True]]}, {'cuts': [1, 2], 'new_mark': None, 'cleared': [1, 2], 'visits': 3, 'promoted_count': 2, 'potential_delta': -2}), ({'path': [[1, False, False], [2, False, True], [3, True, False]]}, {'cuts': [], 'new_mark': 1, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 2}), ({'path': [[100, False, True], [101, False, True], [102, False, True], [103, False, True], [104, False, True], [1, False, False], [2, False, True], [3, True, False]]}, {'cuts': [100, 101, 102, 103, 104], 'new_mark': 1, 'cleared': [100, 101, 102, 103, 104], 'visits': 6, 'promoted_count': 5, 'potential_delta': -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 fibonacci cascade certificate reports an incorrect promoted count.

A cascading-cut path runs from the parent of an initially cut node upward as [id,is_root,marked]. Stop at a root or first unmarked nonroot; mark that first unmarked node. Previously marked nonroots are cut and unmarked. Report cut ids, marked stop, cleared ids, visited count, promoted count, and potential change roots+2*marks.

split: open-access


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

N = 1
observations = []
def solve(d):
    path=d['path']; cut=[]; marked=None; visited=0
    for ident,root,mark in path:
        visited+=1
        if root: break
        if not mark:
            marked=ident; break
        cut.append(ident)
    return {'cuts': cut,
    'new_mark': marked,
    'cleared': cut,
    'visits': visited,
    'promoted_count': len(cut),
    'potential_delta': len(cut)+(2 if marked is not None else 0)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'path': []}, {'cuts': [], 'new_mark': None, 'cleared': [], 'visits': 0, 'promoted_count': 0, 'potential_delta': 0}), ({'path': [[1, True, False]]}, {'cuts': [], 'new_mark': None, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 0}), ({'path': [[1, False, False], [2, True, False]]}, {'cuts': [], 'new_mark': 1, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 2}), ({'path': [[1, False, True], [2, False, False], [3, True, False]]}, {'cuts': [1], 'new_mark': 2, 'cleared': [1], 'visits': 2, 'promoted_count': 1, 'potential_delta': 1}), ({'path': [[1, False, True], [2, False, True], [3, True, True]]}, {'cuts': [1, 2], 'new_mark': None, 'cleared': [1, 2], 'visits': 3, 'promoted_count': 2, 'potential_delta': -2}), ({'path': [[1, False, False], [2, False, True], [3, True, False]]}, {'cuts': [], 'new_mark': 1, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 2}), ({'path': [[100, False, True], [1, False, False], [2, False, True], [3, True, False]]}, {'cuts': [100], 'new_mark': 1, 'cleared': [100], 'visits': 2, 'promoted_count': 1, 'potential_delta': 1})], [({'path': []}, {'cuts': [], 'new_mark': None, 'cleared': [], 'visits': 0, 'promoted_count': 0, 'potential_delta': 0}), ({'path': [[1, True, False]]}, {'cuts': [], 'new_mark': None, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 0}), ({'path': [[1, False, False], [2, True, False]]}, {'cuts': [], 'new_mark': 1, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 2}), ({'path': [[1, False, True], [2, False, False], [3, True, False]]}, {'cuts': [1], 'new_mark': 2, 'cleared': [1], 'visits': 2, 'promoted_count': 1, 'potential_delta': 1}), ({'path': [[1, False, True], [2, False, True], [3, True, True]]}, {'cuts': [1, 2], 'new_mark': None, 'cleared': [1, 2], 'visits': 3, 'promoted_count': 2, 'potential_delta': -2}), ({'path': [[1, False, False], [2, False, True], [3, True, False]]}, {'cuts': [], 'new_mark': 1, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 2}), ({'path': [[100, False, True], [101, False, True], [1, False, False], [2, False, True], [3, True, False]]}, {'cuts': [100, 101], 'new_mark': 1, 'cleared': [100, 101], 'visits': 3, 'promoted_count': 2, 'potential_delta': 0})], [({'path': []}, {'cuts': [], 'new_mark': None, 'cleared': [], 'visits': 0, 'promoted_count': 0, 'potential_delta': 0}), ({'path': [[1, True, False]]}, {'cuts': [], 'new_mark': None, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 0}), ({'path': [[1, False, False], [2, True, False]]}, {'cuts': [], 'new_mark': 1, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 2}), ({'path': [[1, False, True], [2, False, False], [3, True, False]]}, {'cuts': [1], 'new_mark': 2, 'cleared': [1], 'visits': 2, 'promoted_count': 1, 'potential_delta': 1}), ({'path': [[1, False, True], [2, False, True], [3, True, True]]}, {'cuts': [1, 2], 'new_mark': None, 'cleared': [1, 2], 'visits': 3, 'promoted_count': 2, 'potential_delta': -2}), ({'path': [[1, False, False], [2, False, True], [3, True, False]]}, {'cuts': [], 'new_mark': 1, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 2}), ({'path': [[100, False, True], [101, False, True], [102, False, True], [1, False, False], [2, False, True], [3, True, False]]}, {'cuts': [100, 101, 102], 'new_mark': 1, 'cleared': [100, 101, 102], 'visits': 4, 'promoted_count': 3, 'potential_delta': -1})], [({'path': []}, {'cuts': [], 'new_mark': None, 'cleared': [], 'visits': 0, 'promoted_count': 0, 'potential_delta': 0}), ({'path': [[1, True, False]]}, {'cuts': [], 'new_mark': None, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 0}), ({'path': [[1, False, False], [2, True, False]]}, {'cuts': [], 'new_mark': 1, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 2}), ({'path': [[1, False, True], [2, False, False], [3, True, False]]}, {'cuts': [1], 'new_mark': 2, 'cleared': [1], 'visits': 2, 'promoted_count': 1, 'potential_delta': 1}), ({'path': [[1, False, True], [2, False, True], [3, True, True]]}, {'cuts': [1, 2], 'new_mark': None, 'cleared': [1, 2], 'visits': 3, 'promoted_count': 2, 'potential_delta': -2}), ({'path': [[1, False, False], [2, False, True], [3, True, False]]}, {'cuts': [], 'new_mark': 1, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 2}), ({'path': [[100, False, True], [101, False, True], [102, False, True], [103, False, True], [1, False, False], [2, False, True], [3, True, False]]}, {'cuts': [100, 101, 102, 103], 'new_mark': 1, 'cleared': [100, 101, 102, 103], 'visits': 5, 'promoted_count': 4, 'potential_delta': -2})], [({'path': []}, {'cuts': [], 'new_mark': None, 'cleared': [], 'visits': 0, 'promoted_count': 0, 'potential_delta': 0}), ({'path': [[1, True, False]]}, {'cuts': [], 'new_mark': None, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 0}), ({'path': [[1, False, False], [2, True, False]]}, {'cuts': [], 'new_mark': 1, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 2}), ({'path': [[1, False, True], [2, False, False], [3, True, False]]}, {'cuts': [1], 'new_mark': 2, 'cleared': [1], 'visits': 2, 'promoted_count': 1, 'potential_delta': 1}), ({'path': [[1, False, True], [2, False, True], [3, True, True]]}, {'cuts': [1, 2], 'new_mark': None, 'cleared': [1, 2], 'visits': 3, 'promoted_count': 2, 'potential_delta': -2}), ({'path': [[1, False, False], [2, False, True], [3, True, False]]}, {'cuts': [], 'new_mark': 1, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 2}), ({'path': [[100, False, True], [101, False, True], [102, False, True], [103, False, True], [104, False, True], [1, False, False], [2, False, True], [3, True, False]]}, {'cuts': [100, 101, 102, 103, 104], 'new_mark': 1, 'cleared': [100, 101, 102, 103, 104], 'visits': 6, 'promoted_count': 5, 'potential_delta': -3})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

meaning: Fixture-count band, not measured model difficulty

deps: stdlib

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

N = 1
observations = []
def solve(d):
    path=d['path']; cut=[]; marked=None; visited=0
    for ident,root,mark in path:
        visited+=1
        if root: break
        if not mark:
            marked=ident; break
        cut.append(ident)
    return {'cuts': cut,
    'new_mark': marked,
    'cleared': cut,
    'visits': visited,
    'promoted_count': len(cut),
    'potential_delta': -2*len(cut)+(2 if marked is not None else 0)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'path': []}, {'cuts': [], 'new_mark': None, 'cleared': [], 'visits': 0, 'promoted_count': 0, 'potential_delta': 0}), ({'path': [[1, True, False]]}, {'cuts': [], 'new_mark': None, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 0}), ({'path': [[1, False, False], [2, True, False]]}, {'cuts': [], 'new_mark': 1, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 2}), ({'path': [[1, False, True], [2, False, False], [3, True, False]]}, {'cuts': [1], 'new_mark': 2, 'cleared': [1], 'visits': 2, 'promoted_count': 1, 'potential_delta': 1}), ({'path': [[1, False, True], [2, False, True], [3, True, True]]}, {'cuts': [1, 2], 'new_mark': None, 'cleared': [1, 2], 'visits': 3, 'promoted_count': 2, 'potential_delta': -2}), ({'path': [[1, False, False], [2, False, True], [3, True, False]]}, {'cuts': [], 'new_mark': 1, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 2}), ({'path': [[100, False, True], [1, False, False], [2, False, True], [3, True, False]]}, {'cuts': [100], 'new_mark': 1, 'cleared': [100], 'visits': 2, 'promoted_count': 1, 'potential_delta': 1})], [({'path': []}, {'cuts': [], 'new_mark': None, 'cleared': [], 'visits': 0, 'promoted_count': 0, 'potential_delta': 0}), ({'path': [[1, True, False]]}, {'cuts': [], 'new_mark': None, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 0}), ({'path': [[1, False, False], [2, True, False]]}, {'cuts': [], 'new_mark': 1, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 2}), ({'path': [[1, False, True], [2, False, False], [3, True, False]]}, {'cuts': [1], 'new_mark': 2, 'cleared': [1], 'visits': 2, 'promoted_count': 1, 'potential_delta': 1}), ({'path': [[1, False, True], [2, False, True], [3, True, True]]}, {'cuts': [1, 2], 'new_mark': None, 'cleared': [1, 2], 'visits': 3, 'promoted_count': 2, 'potential_delta': -2}), ({'path': [[1, False, False], [2, False, True], [3, True, False]]}, {'cuts': [], 'new_mark': 1, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 2}), ({'path': [[100, False, True], [101, False, True], [1, False, False], [2, False, True], [3, True, False]]}, {'cuts': [100, 101], 'new_mark': 1, 'cleared': [100, 101], 'visits': 3, 'promoted_count': 2, 'potential_delta': 0})], [({'path': []}, {'cuts': [], 'new_mark': None, 'cleared': [], 'visits': 0, 'promoted_count': 0, 'potential_delta': 0}), ({'path': [[1, True, False]]}, {'cuts': [], 'new_mark': None, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 0}), ({'path': [[1, False, False], [2, True, False]]}, {'cuts': [], 'new_mark': 1, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 2}), ({'path': [[1, False, True], [2, False, False], [3, True, False]]}, {'cuts': [1], 'new_mark': 2, 'cleared': [1], 'visits': 2, 'promoted_count': 1, 'potential_delta': 1}), ({'path': [[1, False, True], [2, False, True], [3, True, True]]}, {'cuts': [1, 2], 'new_mark': None, 'cleared': [1, 2], 'visits': 3, 'promoted_count': 2, 'potential_delta': -2}), ({'path': [[1, False, False], [2, False, True], [3, True, False]]}, {'cuts': [], 'new_mark': 1, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 2}), ({'path': [[100, False, True], [101, False, True], [102, False, True], [1, False, False], [2, False, True], [3, True, False]]}, {'cuts': [100, 101, 102], 'new_mark': 1, 'cleared': [100, 101, 102], 'visits': 4, 'promoted_count': 3, 'potential_delta': -1})], [({'path': []}, {'cuts': [], 'new_mark': None, 'cleared': [], 'visits': 0, 'promoted_count': 0, 'potential_delta': 0}), ({'path': [[1, True, False]]}, {'cuts': [], 'new_mark': None, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 0}), ({'path': [[1, False, False], [2, True, False]]}, {'cuts': [], 'new_mark': 1, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 2}), ({'path': [[1, False, True], [2, False, False], [3, True, False]]}, {'cuts': [1], 'new_mark': 2, 'cleared': [1], 'visits': 2, 'promoted_count': 1, 'potential_delta': 1}), ({'path': [[1, False, True], [2, False, True], [3, True, True]]}, {'cuts': [1, 2], 'new_mark': None, 'cleared': [1, 2], 'visits': 3, 'promoted_count': 2, 'potential_delta': -2}), ({'path': [[1, False, False], [2, False, True], [3, True, False]]}, {'cuts': [], 'new_mark': 1, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 2}), ({'path': [[100, False, True], [101, False, True], [102, False, True], [103, False, True], [1, False, False], [2, False, True], [3, True, False]]}, {'cuts': [100, 101, 102, 103], 'new_mark': 1, 'cleared': [100, 101, 102, 103], 'visits': 5, 'promoted_count': 4, 'potential_delta': -2})], [({'path': []}, {'cuts': [], 'new_mark': None, 'cleared': [], 'visits': 0, 'promoted_count': 0, 'potential_delta': 0}), ({'path': [[1, True, False]]}, {'cuts': [], 'new_mark': None, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 0}), ({'path': [[1, False, False], [2, True, False]]}, {'cuts': [], 'new_mark': 1, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 2}), ({'path': [[1, False, True], [2, False, False], [3, True, False]]}, {'cuts': [1], 'new_mark': 2, 'cleared': [1], 'visits': 2, 'promoted_count': 1, 'potential_delta': 1}), ({'path': [[1, False, True], [2, False, True], [3, True, True]]}, {'cuts': [1, 2], 'new_mark': None, 'cleared': [1, 2], 'visits': 3, 'promoted_count': 2, 'potential_delta': -2}), ({'path': [[1, False, False], [2, False, True], [3, True, False]]}, {'cuts': [], 'new_mark': 1, 'cleared': [], 'visits': 1, 'promoted_count': 0, 'potential_delta': 2}), ({'path': [[100, False, True], [101, False, True], [102, False, True], [103, False, True], [104, False, True], [1, False, False], [2, False, True], [3, True, False]]}, {'cuts': [100, 101, 102, 103, 104], 'new_mark': 1, 'cleared': [100, 101, 102, 103, 104], 'visits': 6, 'promoted_count': 5, 'potential_delta': -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 fibonacci cascade certificate reports an incorrect potential delta.

A cascading-cut path runs from the parent of an initially cut node upward as [id,is_root,marked]. Stop at a root or first unmarked nonroot; mark that first unmarked node. Previously marked nonroots are cut and unmarked. Report cut ids, marked stop, cleared ids, visited count, promoted count, and potential change roots+2*marks.

split: open-access


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

N = 1
observations = []
def solve(d):
    a=d['children']; pairs=[(a[i],a[i+1]) for i in range(0,len(a)-1,2)]
    wins=[x if x[1]<=y[1] else y for x,y in pairs]
    loses=[y if x[1]<=y[1] else x for x,y in pairs]
    first=wins+([a[-1]] if len(a)%2 else [])
    return {'pairs': [[i,i+1] for i in range(len(a)-1)],
    'winners': [x[0] for x in wins],
    'losers': [x[0] for x in loses],
    'carry': a[-1][0] if len(a)%2 else None,
    'fold_order': [x[0] for x in reversed(first)],
    'comparisons': len(pairs)+max(0,len(first)-1)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': 100, 'fold_order': [100, 5, 6, 8], 'comparisons': 6})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 2], [101, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7]], 'winners': [8, 6, 5, 101], 'losers': [9, 7, 4, 100], 'carry': None, 'fold_order': [101, 5, 6, 8], 'comparisons': 7})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 3], [101, 2], [102, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7]], 'winners': [8, 6, 5, 101], 'losers': [9, 7, 4, 100], 'carry': 102, 'fold_order': [102, 101, 5, 6, 8], 'comparisons': 8})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 4], [101, 3], [102, 2], [103, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7], [8, 9]], 'winners': [8, 6, 5, 101, 103], 'losers': [9, 7, 4, 100, 102], 'carry': None, 'fold_order': [103, 101, 5, 6, 8], 'comparisons': 9})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 5], [101, 4], [102, 3], [103, 2], [104, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7], [8, 9]], 'winners': [8, 6, 5, 101, 103], 'losers': [9, 7, 4, 100, 102], 'carry': 104, 'fold_order': [104, 103, 101, 5, 6, 8], 'comparisons': 10})]][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['children']; pairs=[(a[i],a[i+1]) for i in range(0,len(a)-1,2)]
    wins=[x if x[1]<=y[1] else y for x,y in pairs]
    loses=[y if x[1]<=y[1] else x for x,y in pairs]
    first=wins+([a[-1]] if len(a)%2 else [])
    return {'pairs': [[i,i+1] for i in range(1,len(a)-1,2)],
    'winners': [x[0] for x in wins],
    'losers': [x[0] for x in loses],
    'carry': a[-1][0] if len(a)%2 else None,
    'fold_order': [x[0] for x in reversed(first)],
    'comparisons': len(pairs)+max(0,len(first)-1)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': 100, 'fold_order': [100, 5, 6, 8], 'comparisons': 6})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 2], [101, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7]], 'winners': [8, 6, 5, 101], 'losers': [9, 7, 4, 100], 'carry': None, 'fold_order': [101, 5, 6, 8], 'comparisons': 7})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 3], [101, 2], [102, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7]], 'winners': [8, 6, 5, 101], 'losers': [9, 7, 4, 100], 'carry': 102, 'fold_order': [102, 101, 5, 6, 8], 'comparisons': 8})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 4], [101, 3], [102, 2], [103, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7], [8, 9]], 'winners': [8, 6, 5, 101, 103], 'losers': [9, 7, 4, 100, 102], 'carry': None, 'fold_order': [103, 101, 5, 6, 8], 'comparisons': 9})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 5], [101, 4], [102, 3], [103, 2], [104, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7], [8, 9]], 'winners': [8, 6, 5, 101, 103], 'losers': [9, 7, 4, 100, 102], 'carry': 104, 'fold_order': [104, 103, 101, 5, 6, 8], 'comparisons': 10})]][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 pairing pass certificate reports an incorrect pairs.

For delete-min pairing pass, children are [id,key]. Pair adjacent children left-to-right, keeping the left on equal keys. An odd last child survives. Return pair indices, winning ids, losing ids, odd carry id, second-pass traversal order, and comparison count. The second pass folds from right to left.

split: open-access


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

N = 1
observations = []
def solve(d):
    a=d['children']; pairs=[(a[i],a[i+1]) for i in range(0,len(a)-1,2)]
    wins=[x if x[1]<=y[1] else y for x,y in pairs]
    loses=[y if x[1]<=y[1] else x for x,y in pairs]
    first=wins+([a[-1]] if len(a)%2 else [])
    return {'pairs': [[i,i+1] for i in range(0,len(a)-1,2)],
    'winners': [min(x[0],y[0]) for x,y in pairs],
    'losers': [x[0] for x in loses],
    'carry': a[-1][0] if len(a)%2 else None,
    'fold_order': [x[0] for x in reversed(first)],
    'comparisons': len(pairs)+max(0,len(first)-1)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': 100, 'fold_order': [100, 5, 6, 8], 'comparisons': 6})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 2], [101, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7]], 'winners': [8, 6, 5, 101], 'losers': [9, 7, 4, 100], 'carry': None, 'fold_order': [101, 5, 6, 8], 'comparisons': 7})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 3], [101, 2], [102, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7]], 'winners': [8, 6, 5, 101], 'losers': [9, 7, 4, 100], 'carry': 102, 'fold_order': [102, 101, 5, 6, 8], 'comparisons': 8})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 4], [101, 3], [102, 2], [103, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7], [8, 9]], 'winners': [8, 6, 5, 101, 103], 'losers': [9, 7, 4, 100, 102], 'carry': None, 'fold_order': [103, 101, 5, 6, 8], 'comparisons': 9})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 5], [101, 4], [102, 3], [103, 2], [104, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7], [8, 9]], 'winners': [8, 6, 5, 101, 103], 'losers': [9, 7, 4, 100, 102], 'carry': 104, 'fold_order': [104, 103, 101, 5, 6, 8], 'comparisons': 10})]][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['children']; pairs=[(a[i],a[i+1]) for i in range(0,len(a)-1,2)]
    wins=[x if x[1]<=y[1] else y for x,y in pairs]
    loses=[y if x[1]<=y[1] else x for x,y in pairs]
    first=wins+([a[-1]] if len(a)%2 else [])
    return {'pairs': [[i,i+1] for i in range(0,len(a)-1,2)],
    'winners': [x[0] for x,y in pairs],
    'losers': [x[0] for x in loses],
    'carry': a[-1][0] if len(a)%2 else None,
    'fold_order': [x[0] for x in reversed(first)],
    'comparisons': len(pairs)+max(0,len(first)-1)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': 100, 'fold_order': [100, 5, 6, 8], 'comparisons': 6})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 2], [101, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7]], 'winners': [8, 6, 5, 101], 'losers': [9, 7, 4, 100], 'carry': None, 'fold_order': [101, 5, 6, 8], 'comparisons': 7})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 3], [101, 2], [102, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7]], 'winners': [8, 6, 5, 101], 'losers': [9, 7, 4, 100], 'carry': 102, 'fold_order': [102, 101, 5, 6, 8], 'comparisons': 8})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 4], [101, 3], [102, 2], [103, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7], [8, 9]], 'winners': [8, 6, 5, 101, 103], 'losers': [9, 7, 4, 100, 102], 'carry': None, 'fold_order': [103, 101, 5, 6, 8], 'comparisons': 9})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 5], [101, 4], [102, 3], [103, 2], [104, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7], [8, 9]], 'winners': [8, 6, 5, 101, 103], 'losers': [9, 7, 4, 100, 102], 'carry': 104, 'fold_order': [104, 103, 101, 5, 6, 8], 'comparisons': 10})]][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 pairing pass certificate reports an incorrect winners.

For delete-min pairing pass, children are [id,key]. Pair adjacent children left-to-right, keeping the left on equal keys. An odd last child survives. Return pair indices, winning ids, losing ids, odd carry id, second-pass traversal order, and comparison count. The second pass folds from right to left.

split: open-access


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

N = 1
observations = []
def solve(d):
    a=d['children']; pairs=[(a[i],a[i+1]) for i in range(0,len(a)-1,2)]
    wins=[x if x[1]<=y[1] else y for x,y in pairs]
    loses=[y if x[1]<=y[1] else x for x,y in pairs]
    first=wins+([a[-1]] if len(a)%2 else [])
    return {'pairs': [[i,i+1] for i in range(0,len(a)-1,2)],
    'winners': [x[0] for x in wins],
    'losers': [x[0] for x in wins],
    'carry': a[-1][0] if len(a)%2 else None,
    'fold_order': [x[0] for x in reversed(first)],
    'comparisons': len(pairs)+max(0,len(first)-1)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': 100, 'fold_order': [100, 5, 6, 8], 'comparisons': 6})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 2], [101, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7]], 'winners': [8, 6, 5, 101], 'losers': [9, 7, 4, 100], 'carry': None, 'fold_order': [101, 5, 6, 8], 'comparisons': 7})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 3], [101, 2], [102, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7]], 'winners': [8, 6, 5, 101], 'losers': [9, 7, 4, 100], 'carry': 102, 'fold_order': [102, 101, 5, 6, 8], 'comparisons': 8})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 4], [101, 3], [102, 2], [103, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7], [8, 9]], 'winners': [8, 6, 5, 101, 103], 'losers': [9, 7, 4, 100, 102], 'carry': None, 'fold_order': [103, 101, 5, 6, 8], 'comparisons': 9})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 5], [101, 4], [102, 3], [103, 2], [104, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7], [8, 9]], 'winners': [8, 6, 5, 101, 103], 'losers': [9, 7, 4, 100, 102], 'carry': 104, 'fold_order': [104, 103, 101, 5, 6, 8], 'comparisons': 10})]][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['children']; pairs=[(a[i],a[i+1]) for i in range(0,len(a)-1,2)]
    wins=[x if x[1]<=y[1] else y for x,y in pairs]
    loses=[y if x[1]<=y[1] else x for x,y in pairs]
    first=wins+([a[-1]] if len(a)%2 else [])
    return {'pairs': [[i,i+1] for i in range(0,len(a)-1,2)],
    'winners': [x[0] for x in wins],
    'losers': [y[0] for x,y in pairs],
    'carry': a[-1][0] if len(a)%2 else None,
    'fold_order': [x[0] for x in reversed(first)],
    'comparisons': len(pairs)+max(0,len(first)-1)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': 100, 'fold_order': [100, 5, 6, 8], 'comparisons': 6})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 2], [101, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7]], 'winners': [8, 6, 5, 101], 'losers': [9, 7, 4, 100], 'carry': None, 'fold_order': [101, 5, 6, 8], 'comparisons': 7})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 3], [101, 2], [102, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7]], 'winners': [8, 6, 5, 101], 'losers': [9, 7, 4, 100], 'carry': 102, 'fold_order': [102, 101, 5, 6, 8], 'comparisons': 8})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 4], [101, 3], [102, 2], [103, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7], [8, 9]], 'winners': [8, 6, 5, 101, 103], 'losers': [9, 7, 4, 100, 102], 'carry': None, 'fold_order': [103, 101, 5, 6, 8], 'comparisons': 9})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 5], [101, 4], [102, 3], [103, 2], [104, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7], [8, 9]], 'winners': [8, 6, 5, 101, 103], 'losers': [9, 7, 4, 100, 102], 'carry': 104, 'fold_order': [104, 103, 101, 5, 6, 8], 'comparisons': 10})]][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 pairing pass certificate reports an incorrect losers.

For delete-min pairing pass, children are [id,key]. Pair adjacent children left-to-right, keeping the left on equal keys. An odd last child survives. Return pair indices, winning ids, losing ids, odd carry id, second-pass traversal order, and comparison count. The second pass folds from right to left.

split: open-access


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

N = 1
observations = []
def solve(d):
    a=d['children']; pairs=[(a[i],a[i+1]) for i in range(0,len(a)-1,2)]
    wins=[x if x[1]<=y[1] else y for x,y in pairs]
    loses=[y if x[1]<=y[1] else x for x,y in pairs]
    first=wins+([a[-1]] if len(a)%2 else [])
    return {'pairs': [[i,i+1] for i in range(0,len(a)-1,2)],
    'winners': [x[0] for x in wins],
    'losers': [x[0] for x in loses],
    'carry': a[-1][0] if a else None,
    'fold_order': [x[0] for x in reversed(first)],
    'comparisons': len(pairs)+max(0,len(first)-1)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': 100, 'fold_order': [100, 5, 6, 8], 'comparisons': 6})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 2], [101, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7]], 'winners': [8, 6, 5, 101], 'losers': [9, 7, 4, 100], 'carry': None, 'fold_order': [101, 5, 6, 8], 'comparisons': 7})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 3], [101, 2], [102, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7]], 'winners': [8, 6, 5, 101], 'losers': [9, 7, 4, 100], 'carry': 102, 'fold_order': [102, 101, 5, 6, 8], 'comparisons': 8})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 4], [101, 3], [102, 2], [103, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7], [8, 9]], 'winners': [8, 6, 5, 101, 103], 'losers': [9, 7, 4, 100, 102], 'carry': None, 'fold_order': [103, 101, 5, 6, 8], 'comparisons': 9})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 5], [101, 4], [102, 3], [103, 2], [104, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7], [8, 9]], 'winners': [8, 6, 5, 101, 103], 'losers': [9, 7, 4, 100, 102], 'carry': 104, 'fold_order': [104, 103, 101, 5, 6, 8], 'comparisons': 10})]][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['children']; pairs=[(a[i],a[i+1]) for i in range(0,len(a)-1,2)]
    wins=[x if x[1]<=y[1] else y for x,y in pairs]
    loses=[y if x[1]<=y[1] else x for x,y in pairs]
    first=wins+([a[-1]] if len(a)%2 else [])
    return {'pairs': [[i,i+1] for i in range(0,len(a)-1,2)],
    'winners': [x[0] for x in wins],
    'losers': [x[0] for x in loses],
    'carry': a[0][0] if len(a)%2 else None,
    'fold_order': [x[0] for x in reversed(first)],
    'comparisons': len(pairs)+max(0,len(first)-1)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': 100, 'fold_order': [100, 5, 6, 8], 'comparisons': 6})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 2], [101, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7]], 'winners': [8, 6, 5, 101], 'losers': [9, 7, 4, 100], 'carry': None, 'fold_order': [101, 5, 6, 8], 'comparisons': 7})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 3], [101, 2], [102, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7]], 'winners': [8, 6, 5, 101], 'losers': [9, 7, 4, 100], 'carry': 102, 'fold_order': [102, 101, 5, 6, 8], 'comparisons': 8})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 4], [101, 3], [102, 2], [103, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7], [8, 9]], 'winners': [8, 6, 5, 101, 103], 'losers': [9, 7, 4, 100, 102], 'carry': None, 'fold_order': [103, 101, 5, 6, 8], 'comparisons': 9})], [({'children': []}, {'pairs': [], 'winners': [], 'losers': [], 'carry': None, 'fold_order': [], 'comparisons': 0}), ({'children': [[8, 3]]}, {'pairs': [], 'winners': [], 'losers': [], 'carry': 8, 'fold_order': [8], 'comparisons': 0}), ({'children': [[8, 9], [2, 1]]}, {'pairs': [[0, 1]], 'winners': [2], 'losers': [8], 'carry': None, 'fold_order': [2], 'comparisons': 1}), ({'children': [[4, 5], [7, 2], [1, 9]]}, {'pairs': [[0, 1]], 'winners': [7], 'losers': [4], 'carry': 1, 'fold_order': [1, 7], 'comparisons': 2}), ({'children': [[4, 2], [7, 2], [1, 6], [9, 3]]}, {'pairs': [[0, 1], [2, 3]], 'winners': [4, 9], 'losers': [7, 1], 'carry': None, 'fold_order': [9, 4], 'comparisons': 3}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6]]}, {'pairs': [[0, 1], [2, 3], [4, 5]], 'winners': [8, 6, 5], 'losers': [9, 7, 4], 'carry': None, 'fold_order': [5, 6, 8], 'comparisons': 5}), ({'children': [[9, 8], [8, 2], [7, 7], [6, 1], [5, 3], [4, 6], [100, 5], [101, 4], [102, 3], [103, 2], [104, 1]]}, {'pairs': [[0, 1], [2, 3], [4, 5], [6, 7], [8, 9]], 'winners': [8, 6, 5, 101, 103], 'losers': [9, 7, 4, 100, 102], 'carry': 104, 'fold_order': [104, 103, 101, 5, 6, 8], 'comparisons': 10})]][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 pairing pass certificate reports an incorrect carry.

For delete-min pairing pass, children are [id,key]. Pair adjacent children left-to-right, keeping the left on equal keys. An odd last child survives. Return pair indices, winning ids, losing ids, odd carry id, second-pass traversal order, and comparison count. The second pass folds from right to left.

split: open-access