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

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

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

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

prompt:
The bounded weak join certificate reports an incorrect flipped.

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

split: open-access


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

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

meaning: Fixture-count band, not measured model difficulty

deps: stdlib

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

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

prompt:
The bounded weak join certificate reports an incorrect comparisons.

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

split: open-access


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

N = 1
observations = []
def solve(d):
    n=d['size']; internal=list(range(n//2-1,-1,-1)); levels=[]; start=0; width=1
    while start<n:
        levels.append([start,min(n-1,start+width-1)]); start+=width; width*=2
    return {'schedule': list(reversed(internal)),
    'leaves': list(range(n//2,n)),
    'levels': levels,
    'unpaired_parent': n//2-1 if n>0 and n%2==0 else None,
    'dependencies': [[i,(i-1)//2] for i in range(1,n//2)],
    'internal_count': n//2}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 16}, {'schedule': [7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [8, 9, 10, 11, 12, 13, 14, 15], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 15]], 'unpaired_parent': 7, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3]], 'internal_count': 8})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 17}, {'schedule': [7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [8, 9, 10, 11, 12, 13, 14, 15, 16], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 16]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3]], 'internal_count': 8})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 18}, {'schedule': [8, 7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [9, 10, 11, 12, 13, 14, 15, 16, 17], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 17]], 'unpaired_parent': 8, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3], [8, 3]], 'internal_count': 9})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 19}, {'schedule': [8, 7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [9, 10, 11, 12, 13, 14, 15, 16, 17, 18], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 18]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3], [8, 3]], 'internal_count': 9})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 20}, {'schedule': [9, 8, 7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [10, 11, 12, 13, 14, 15, 16, 17, 18, 19], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 19]], 'unpaired_parent': 9, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3], [8, 3], [9, 4]], 'internal_count': 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):
    n=d['size']; internal=list(range(n//2-1,-1,-1)); levels=[]; start=0; width=1
    while start<n:
        levels.append([start,min(n-1,start+width-1)]); start+=width; width*=2
    return {'schedule': list(range(n//2,-1,-1)),
    'leaves': list(range(n//2,n)),
    'levels': levels,
    'unpaired_parent': n//2-1 if n>0 and n%2==0 else None,
    'dependencies': [[i,(i-1)//2] for i in range(1,n//2)],
    'internal_count': n//2}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 16}, {'schedule': [7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [8, 9, 10, 11, 12, 13, 14, 15], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 15]], 'unpaired_parent': 7, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3]], 'internal_count': 8})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 17}, {'schedule': [7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [8, 9, 10, 11, 12, 13, 14, 15, 16], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 16]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3]], 'internal_count': 8})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 18}, {'schedule': [8, 7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [9, 10, 11, 12, 13, 14, 15, 16, 17], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 17]], 'unpaired_parent': 8, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3], [8, 3]], 'internal_count': 9})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 19}, {'schedule': [8, 7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [9, 10, 11, 12, 13, 14, 15, 16, 17, 18], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 18]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3], [8, 3]], 'internal_count': 9})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 20}, {'schedule': [9, 8, 7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [10, 11, 12, 13, 14, 15, 16, 17, 18, 19], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 19]], 'unpaired_parent': 9, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3], [8, 3], [9, 4]], 'internal_count': 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 bottomup schedule certificate reports an incorrect schedule.

For building a complete zero-based binary heap of n nodes, report descending internal-node repair schedule, leaf indices, level spans as inclusive [start,end], right-child-less internal node, parent dependency edges [child,parent], and number of internal nodes. This describes the build work graph, not sorted output.

split: open-access


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

N = 1
observations = []
def solve(d):
    n=d['size']; internal=list(range(n//2-1,-1,-1)); levels=[]; start=0; width=1
    while start<n:
        levels.append([start,min(n-1,start+width-1)]); start+=width; width*=2
    return {'schedule': internal,
    'leaves': list(range(n//2+1,n)),
    'levels': levels,
    'unpaired_parent': n//2-1 if n>0 and n%2==0 else None,
    'dependencies': [[i,(i-1)//2] for i in range(1,n//2)],
    'internal_count': n//2}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 16}, {'schedule': [7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [8, 9, 10, 11, 12, 13, 14, 15], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 15]], 'unpaired_parent': 7, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3]], 'internal_count': 8})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 17}, {'schedule': [7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [8, 9, 10, 11, 12, 13, 14, 15, 16], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 16]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3]], 'internal_count': 8})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 18}, {'schedule': [8, 7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [9, 10, 11, 12, 13, 14, 15, 16, 17], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 17]], 'unpaired_parent': 8, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3], [8, 3]], 'internal_count': 9})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 19}, {'schedule': [8, 7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [9, 10, 11, 12, 13, 14, 15, 16, 17, 18], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 18]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3], [8, 3]], 'internal_count': 9})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 20}, {'schedule': [9, 8, 7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [10, 11, 12, 13, 14, 15, 16, 17, 18, 19], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 19]], 'unpaired_parent': 9, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3], [8, 3], [9, 4]], 'internal_count': 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):
    n=d['size']; internal=list(range(n//2-1,-1,-1)); levels=[]; start=0; width=1
    while start<n:
        levels.append([start,min(n-1,start+width-1)]); start+=width; width*=2
    return {'schedule': internal,
    'leaves': list(range((n+1)//2,n)),
    'levels': levels,
    'unpaired_parent': n//2-1 if n>0 and n%2==0 else None,
    'dependencies': [[i,(i-1)//2] for i in range(1,n//2)],
    'internal_count': n//2}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 16}, {'schedule': [7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [8, 9, 10, 11, 12, 13, 14, 15], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 15]], 'unpaired_parent': 7, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3]], 'internal_count': 8})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 17}, {'schedule': [7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [8, 9, 10, 11, 12, 13, 14, 15, 16], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 16]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3]], 'internal_count': 8})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 18}, {'schedule': [8, 7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [9, 10, 11, 12, 13, 14, 15, 16, 17], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 17]], 'unpaired_parent': 8, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3], [8, 3]], 'internal_count': 9})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 19}, {'schedule': [8, 7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [9, 10, 11, 12, 13, 14, 15, 16, 17, 18], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 18]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3], [8, 3]], 'internal_count': 9})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 20}, {'schedule': [9, 8, 7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [10, 11, 12, 13, 14, 15, 16, 17, 18, 19], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 19]], 'unpaired_parent': 9, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3], [8, 3], [9, 4]], 'internal_count': 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 bottomup schedule certificate reports an incorrect leaves.

For building a complete zero-based binary heap of n nodes, report descending internal-node repair schedule, leaf indices, level spans as inclusive [start,end], right-child-less internal node, parent dependency edges [child,parent], and number of internal nodes. This describes the build work graph, not sorted output.

split: open-access


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

N = 1
observations = []
def solve(d):
    n=d['size']; internal=list(range(n//2-1,-1,-1)); levels=[]; start=0; width=1
    while start<n:
        levels.append([start,min(n-1,start+width-1)]); start+=width; width*=2
    return {'schedule': internal,
    'leaves': list(range(n//2,n)),
    'levels': [[x,y+1] for x,y in levels],
    'unpaired_parent': n//2-1 if n>0 and n%2==0 else None,
    'dependencies': [[i,(i-1)//2] for i in range(1,n//2)],
    'internal_count': n//2}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 16}, {'schedule': [7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [8, 9, 10, 11, 12, 13, 14, 15], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 15]], 'unpaired_parent': 7, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3]], 'internal_count': 8})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 17}, {'schedule': [7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [8, 9, 10, 11, 12, 13, 14, 15, 16], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 16]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3]], 'internal_count': 8})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 18}, {'schedule': [8, 7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [9, 10, 11, 12, 13, 14, 15, 16, 17], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 17]], 'unpaired_parent': 8, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3], [8, 3]], 'internal_count': 9})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 19}, {'schedule': [8, 7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [9, 10, 11, 12, 13, 14, 15, 16, 17, 18], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 18]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3], [8, 3]], 'internal_count': 9})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 20}, {'schedule': [9, 8, 7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [10, 11, 12, 13, 14, 15, 16, 17, 18, 19], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 19]], 'unpaired_parent': 9, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3], [8, 3], [9, 4]], 'internal_count': 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):
    n=d['size']; internal=list(range(n//2-1,-1,-1)); levels=[]; start=0; width=1
    while start<n:
        levels.append([start,min(n-1,start+width-1)]); start+=width; width*=2
    return {'schedule': internal,
    'leaves': list(range(n//2,n)),
    'levels': [[x+1,y] for x,y in levels],
    'unpaired_parent': n//2-1 if n>0 and n%2==0 else None,
    'dependencies': [[i,(i-1)//2] for i in range(1,n//2)],
    'internal_count': n//2}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 16}, {'schedule': [7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [8, 9, 10, 11, 12, 13, 14, 15], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 15]], 'unpaired_parent': 7, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3]], 'internal_count': 8})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 17}, {'schedule': [7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [8, 9, 10, 11, 12, 13, 14, 15, 16], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 16]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3]], 'internal_count': 8})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 18}, {'schedule': [8, 7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [9, 10, 11, 12, 13, 14, 15, 16, 17], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 17]], 'unpaired_parent': 8, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3], [8, 3]], 'internal_count': 9})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 19}, {'schedule': [8, 7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [9, 10, 11, 12, 13, 14, 15, 16, 17, 18], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 18]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3], [8, 3]], 'internal_count': 9})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 20}, {'schedule': [9, 8, 7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [10, 11, 12, 13, 14, 15, 16, 17, 18, 19], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 19]], 'unpaired_parent': 9, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3], [8, 3], [9, 4]], 'internal_count': 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 bottomup schedule certificate reports an incorrect levels.

For building a complete zero-based binary heap of n nodes, report descending internal-node repair schedule, leaf indices, level spans as inclusive [start,end], right-child-less internal node, parent dependency edges [child,parent], and number of internal nodes. This describes the build work graph, not sorted output.

split: open-access


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

N = 1
observations = []
def solve(d):
    n=d['size']; internal=list(range(n//2-1,-1,-1)); levels=[]; start=0; width=1
    while start<n:
        levels.append([start,min(n-1,start+width-1)]); start+=width; width*=2
    return {'schedule': internal,
    'leaves': list(range(n//2,n)),
    'levels': levels,
    'unpaired_parent': n//2 if n>0 and n%2==0 else None,
    'dependencies': [[i,(i-1)//2] for i in range(1,n//2)],
    'internal_count': n//2}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 16}, {'schedule': [7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [8, 9, 10, 11, 12, 13, 14, 15], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 15]], 'unpaired_parent': 7, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3]], 'internal_count': 8})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 17}, {'schedule': [7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [8, 9, 10, 11, 12, 13, 14, 15, 16], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 16]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3]], 'internal_count': 8})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 18}, {'schedule': [8, 7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [9, 10, 11, 12, 13, 14, 15, 16, 17], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 17]], 'unpaired_parent': 8, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3], [8, 3]], 'internal_count': 9})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 19}, {'schedule': [8, 7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [9, 10, 11, 12, 13, 14, 15, 16, 17, 18], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 18]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3], [8, 3]], 'internal_count': 9})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 20}, {'schedule': [9, 8, 7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [10, 11, 12, 13, 14, 15, 16, 17, 18, 19], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 19]], 'unpaired_parent': 9, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3], [8, 3], [9, 4]], 'internal_count': 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):
    n=d['size']; internal=list(range(n//2-1,-1,-1)); levels=[]; start=0; width=1
    while start<n:
        levels.append([start,min(n-1,start+width-1)]); start+=width; width*=2
    return {'schedule': internal,
    'leaves': list(range(n//2,n)),
    'levels': levels,
    'unpaired_parent': n//2-1 if n>1 else None,
    'dependencies': [[i,(i-1)//2] for i in range(1,n//2)],
    'internal_count': n//2}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 16}, {'schedule': [7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [8, 9, 10, 11, 12, 13, 14, 15], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 15]], 'unpaired_parent': 7, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3]], 'internal_count': 8})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 17}, {'schedule': [7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [8, 9, 10, 11, 12, 13, 14, 15, 16], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 16]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3]], 'internal_count': 8})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 18}, {'schedule': [8, 7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [9, 10, 11, 12, 13, 14, 15, 16, 17], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 17]], 'unpaired_parent': 8, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3], [8, 3]], 'internal_count': 9})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 19}, {'schedule': [8, 7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [9, 10, 11, 12, 13, 14, 15, 16, 17, 18], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 18]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3], [8, 3]], 'internal_count': 9})], [({'size': 0}, {'schedule': [], 'leaves': [], 'levels': [], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 1}, {'schedule': [], 'leaves': [0], 'levels': [[0, 0]], 'unpaired_parent': None, 'dependencies': [], 'internal_count': 0}), ({'size': 2}, {'schedule': [0], 'leaves': [1], 'levels': [[0, 0], [1, 1]], 'unpaired_parent': 0, 'dependencies': [], 'internal_count': 1}), ({'size': 5}, {'schedule': [1, 0], 'leaves': [2, 3, 4], 'levels': [[0, 0], [1, 2], [3, 4]], 'unpaired_parent': None, 'dependencies': [[1, 0]], 'internal_count': 2}), ({'size': 8}, {'schedule': [3, 2, 1, 0], 'leaves': [4, 5, 6, 7], 'levels': [[0, 0], [1, 2], [3, 6], [7, 7]], 'unpaired_parent': 3, 'dependencies': [[1, 0], [2, 0], [3, 1]], 'internal_count': 4}), ({'size': 15}, {'schedule': [6, 5, 4, 3, 2, 1, 0], 'leaves': [7, 8, 9, 10, 11, 12, 13, 14], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14]], 'unpaired_parent': None, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2]], 'internal_count': 7}), ({'size': 20}, {'schedule': [9, 8, 7, 6, 5, 4, 3, 2, 1, 0], 'leaves': [10, 11, 12, 13, 14, 15, 16, 17, 18, 19], 'levels': [[0, 0], [1, 2], [3, 6], [7, 14], [15, 19]], 'unpaired_parent': 9, 'dependencies': [[1, 0], [2, 0], [3, 1], [4, 1], [5, 2], [6, 2], [7, 3], [8, 3], [9, 4]], 'internal_count': 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 bottomup schedule certificate reports an incorrect unpaired parent.

For building a complete zero-based binary heap of n nodes, report descending internal-node repair schedule, leaf indices, level spans as inclusive [start,end], right-child-less internal node, parent dependency edges [child,parent], and number of internal nodes. This describes the build work graph, not sorted output.

split: open-access