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

N = 1
observations = []
def solve(d):
    v=d['visited']; terminal=d['terminal']; g=d['generation']; order=list(reversed(v))
    return {'alloc_order': order,
    'terminal': None if terminal is None else [terminal,"shared"],
    'links': [[v[i],v[i+1] if i+1<len(v) else terminal] for i in range(len(v))],
    'root': v[0] if v else terminal,
    'allocation_count': len(v)+int(terminal is not None),
    'old_snapshot': d["old_ids"]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'visited': [], 'terminal': None, 'generation': 7, 'old_ids': []}, {'alloc_order': [], 'terminal': None, 'links': [], 'root': None, 'allocation_count': 0, 'old_snapshot': []}), ({'visited': [], 'terminal': 3, 'generation': 7, 'old_ids': [3, 4]}, {'alloc_order': [], 'terminal': [3, 'shared'], 'links': [], 'root': 3, 'allocation_count': 0, 'old_snapshot': [3, 4]}), ({'visited': [1], 'terminal': 2, 'generation': 7, 'old_ids': [1, 2, 3]}, {'alloc_order': [1], 'terminal': [2, 'shared'], 'links': [[1, 2]], 'root': 1, 'allocation_count': 1, 'old_snapshot': [1, 2, 3]}), ({'visited': [1, 4, 7], 'terminal': 9, 'generation': 7, 'old_ids': [1, 2, 4, 7, 9]}, {'alloc_order': [7, 4, 1], 'terminal': [9, 'shared'], 'links': [[1, 4], [4, 7], [7, 9]], 'root': 1, 'allocation_count': 3, 'old_snapshot': [1, 2, 4, 7, 9]}), ({'visited': [8, 3], 'terminal': None, 'generation': 7, 'old_ids': [8, 3]}, {'alloc_order': [3, 8], 'terminal': None, 'links': [[8, 3], [3, None]], 'root': 8, 'allocation_count': 2, 'old_snapshot': [8, 3]}), ({'visited': [2, 5, 9, 6], 'terminal': 10, 'generation': 7, 'old_ids': [2, 5, 9, 6, 10, 11]}, {'alloc_order': [6, 9, 5, 2], 'terminal': [10, 'shared'], 'links': [[2, 5], [5, 9], [9, 6], [6, 10]], 'root': 2, 'allocation_count': 4, 'old_snapshot': [2, 5, 9, 6, 10, 11]}), ({'visited': [2, 5, 9, 6, 100], 'terminal': 10, 'generation': 7, 'old_ids': [2, 5, 9, 6, 10, 11, 100]}, {'alloc_order': [100, 6, 9, 5, 2], 'terminal': [10, 'shared'], 'links': [[2, 5], [5, 9], [9, 6], [6, 100], [100, 10]], 'root': 2, 'allocation_count': 5, 'old_snapshot': [2, 5, 9, 6, 10, 11, 100]})], [({'visited': [], 'terminal': None, 'generation': 7, 'old_ids': []}, {'alloc_order': [], 'terminal': None, 'links': [], 'root': None, 'allocation_count': 0, 'old_snapshot': []}), ({'visited': [], 'terminal': 3, 'generation': 7, 'old_ids': [3, 4]}, {'alloc_order': [], 'terminal': [3, 'shared'], 'links': [], 'root': 3, 'allocation_count': 0, 'old_snapshot': [3, 4]}), ({'visited': [1], 'terminal': 2, 'generation': 7, 'old_ids': [1, 2, 3]}, {'alloc_order': [1], 'terminal': [2, 'shared'], 'links': [[1, 2]], 'root': 1, 'allocation_count': 1, 'old_snapshot': [1, 2, 3]}), ({'visited': [1, 4, 7], 'terminal': 9, 'generation': 7, 'old_ids': [1, 2, 4, 7, 9]}, {'alloc_order': [7, 4, 1], 'terminal': [9, 'shared'], 'links': [[1, 4], [4, 7], [7, 9]], 'root': 1, 'allocation_count': 3, 'old_snapshot': [1, 2, 4, 7, 9]}), ({'visited': [8, 3], 'terminal': None, 'generation': 7, 'old_ids': [8, 3]}, {'alloc_order': [3, 8], 'terminal': None, 'links': [[8, 3], [3, None]], 'root': 8, 'allocation_count': 2, 'old_snapshot': [8, 3]}), ({'visited': [2, 5, 9, 6], 'terminal': 10, 'generation': 7, 'old_ids': [2, 5, 9, 6, 10, 11]}, {'alloc_order': [6, 9, 5, 2], 'terminal': [10, 'shared'], 'links': [[2, 5], [5, 9], [9, 6], [6, 10]], 'root': 2, 'allocation_count': 4, 'old_snapshot': [2, 5, 9, 6, 10, 11]}), ({'visited': [2, 5, 9, 6, 100, 101], 'terminal': 10, 'generation': 7, 'old_ids': [2, 5, 9, 6, 10, 11, 100, 101]}, {'alloc_order': [101, 100, 6, 9, 5, 2], 'terminal': [10, 'shared'], 'links': [[2, 5], [5, 9], [9, 6], [6, 100], [100, 101], [101, 10]], 'root': 2, 'allocation_count': 6, 'old_snapshot': [2, 5, 9, 6, 10, 11, 100, 101]})], [({'visited': [], 'terminal': None, 'generation': 7, 'old_ids': []}, {'alloc_order': [], 'terminal': None, 'links': [], 'root': None, 'allocation_count': 0, 'old_snapshot': []}), ({'visited': [], 'terminal': 3, 'generation': 7, 'old_ids': [3, 4]}, {'alloc_order': [], 'terminal': [3, 'shared'], 'links': [], 'root': 3, 'allocation_count': 0, 'old_snapshot': [3, 4]}), ({'visited': [1], 'terminal': 2, 'generation': 7, 'old_ids': [1, 2, 3]}, {'alloc_order': [1], 'terminal': [2, 'shared'], 'links': [[1, 2]], 'root': 1, 'allocation_count': 1, 'old_snapshot': [1, 2, 3]}), ({'visited': [1, 4, 7], 'terminal': 9, 'generation': 7, 'old_ids': [1, 2, 4, 7, 9]}, {'alloc_order': [7, 4, 1], 'terminal': [9, 'shared'], 'links': [[1, 4], [4, 7], [7, 9]], 'root': 1, 'allocation_count': 3, 'old_snapshot': [1, 2, 4, 7, 9]}), ({'visited': [8, 3], 'terminal': None, 'generation': 7, 'old_ids': [8, 3]}, {'alloc_order': [3, 8], 'terminal': None, 'links': [[8, 3], [3, None]], 'root': 8, 'allocation_count': 2, 'old_snapshot': [8, 3]}), ({'visited': [2, 5, 9, 6], 'terminal': 10, 'generation': 7, 'old_ids': [2, 5, 9, 6, 10, 11]}, {'alloc_order': [6, 9, 5, 2], 'terminal': [10, 'shared'], 'links': [[2, 5], [5, 9], [9, 6], [6, 10]], 'root': 2, 'allocation_count': 4, 'old_snapshot': [2, 5, 9, 6, 10, 11]}), ({'visited': [2, 5, 9, 6, 100, 101, 102], 'terminal': 10, 'generation': 7, 'old_ids': [2, 5, 9, 6, 10, 11, 100, 101, 102]}, {'alloc_order': [102, 101, 100, 6, 9, 5, 2], 'terminal': [10, 'shared'], 'links': [[2, 5], [5, 9], [9, 6], [6, 100], [100, 101], [101, 102], [102, 10]], 'root': 2, 'allocation_count': 7, 'old_snapshot': [2, 5, 9, 6, 10, 11, 100, 101, 102]})], [({'visited': [], 'terminal': None, 'generation': 7, 'old_ids': []}, {'alloc_order': [], 'terminal': None, 'links': [], 'root': None, 'allocation_count': 0, 'old_snapshot': []}), ({'visited': [], 'terminal': 3, 'generation': 7, 'old_ids': [3, 4]}, {'alloc_order': [], 'terminal': [3, 'shared'], 'links': [], 'root': 3, 'allocation_count': 0, 'old_snapshot': [3, 4]}), ({'visited': [1], 'terminal': 2, 'generation': 7, 'old_ids': [1, 2, 3]}, {'alloc_order': [1], 'terminal': [2, 'shared'], 'links': [[1, 2]], 'root': 1, 'allocation_count': 1, 'old_snapshot': [1, 2, 3]}), ({'visited': [1, 4, 7], 'terminal': 9, 'generation': 7, 'old_ids': [1, 2, 4, 7, 9]}, {'alloc_order': [7, 4, 1], 'terminal': [9, 'shared'], 'links': [[1, 4], [4, 7], [7, 9]], 'root': 1, 'allocation_count': 3, 'old_snapshot': [1, 2, 4, 7, 9]}), ({'visited': [8, 3], 'terminal': None, 'generation': 7, 'old_ids': [8, 3]}, {'alloc_order': [3, 8], 'terminal': None, 'links': [[8, 3], [3, None]], 'root': 8, 'allocation_count': 2, 'old_snapshot': [8, 3]}), ({'visited': [2, 5, 9, 6], 'terminal': 10, 'generation': 7, 'old_ids': [2, 5, 9, 6, 10, 11]}, {'alloc_order': [6, 9, 5, 2], 'terminal': [10, 'shared'], 'links': [[2, 5], [5, 9], [9, 6], [6, 10]], 'root': 2, 'allocation_count': 4, 'old_snapshot': [2, 5, 9, 6, 10, 11]}), ({'visited': [2, 5, 9, 6, 100, 101, 102, 103], 'terminal': 10, 'generation': 7, 'old_ids': [2, 5, 9, 6, 10, 11, 100, 101, 102, 103]}, {'alloc_order': [103, 102, 101, 100, 6, 9, 5, 2], 'terminal': [10, 'shared'], 'links': [[2, 5], [5, 9], [9, 6], [6, 100], [100, 101], [101, 102], [102, 103], [103, 10]], 'root': 2, 'allocation_count': 8, 'old_snapshot': [2, 5, 9, 6, 10, 11, 100, 101, 102, 103]})], [({'visited': [], 'terminal': None, 'generation': 7, 'old_ids': []}, {'alloc_order': [], 'terminal': None, 'links': [], 'root': None, 'allocation_count': 0, 'old_snapshot': []}), ({'visited': [], 'terminal': 3, 'generation': 7, 'old_ids': [3, 4]}, {'alloc_order': [], 'terminal': [3, 'shared'], 'links': [], 'root': 3, 'allocation_count': 0, 'old_snapshot': [3, 4]}), ({'visited': [1], 'terminal': 2, 'generation': 7, 'old_ids': [1, 2, 3]}, {'alloc_order': [1], 'terminal': [2, 'shared'], 'links': [[1, 2]], 'root': 1, 'allocation_count': 1, 'old_snapshot': [1, 2, 3]}), ({'visited': [1, 4, 7], 'terminal': 9, 'generation': 7, 'old_ids': [1, 2, 4, 7, 9]}, {'alloc_order': [7, 4, 1], 'terminal': [9, 'shared'], 'links': [[1, 4], [4, 7], [7, 9]], 'root': 1, 'allocation_count': 3, 'old_snapshot': [1, 2, 4, 7, 9]}), ({'visited': [8, 3], 'terminal': None, 'generation': 7, 'old_ids': [8, 3]}, {'alloc_order': [3, 8], 'terminal': None, 'links': [[8, 3], [3, None]], 'root': 8, 'allocation_count': 2, 'old_snapshot': [8, 3]}), ({'visited': [2, 5, 9, 6], 'terminal': 10, 'generation': 7, 'old_ids': [2, 5, 9, 6, 10, 11]}, {'alloc_order': [6, 9, 5, 2], 'terminal': [10, 'shared'], 'links': [[2, 5], [5, 9], [9, 6], [6, 10]], 'root': 2, 'allocation_count': 4, 'old_snapshot': [2, 5, 9, 6, 10, 11]}), ({'visited': [2, 5, 9, 6, 100, 101, 102, 103, 104], 'terminal': 10, 'generation': 7, 'old_ids': [2, 5, 9, 6, 10, 11, 100, 101, 102, 103, 104]}, {'alloc_order': [104, 103, 102, 101, 100, 6, 9, 5, 2], 'terminal': [10, 'shared'], 'links': [[2, 5], [5, 9], [9, 6], [6, 100], [100, 101], [101, 102], [102, 103], [103, 104], [104, 10]], 'root': 2, 'allocation_count': 9, 'old_snapshot': [2, 5, 9, 6, 10, 11, 100, 101, 102, 103, 104]})]][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):
    v=d['visited']; terminal=d['terminal']; g=d['generation']; order=list(reversed(v))
    return {'alloc_order': order,
    'terminal': None if terminal is None else [terminal,"shared"],
    'links': [[v[i],v[i+1] if i+1<len(v) else terminal] for i in range(len(v))],
    'root': v[0] if v else terminal,
    'allocation_count': max(0,len(v)-1),
    'old_snapshot': d["old_ids"]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'visited': [], 'terminal': None, 'generation': 7, 'old_ids': []}, {'alloc_order': [], 'terminal': None, 'links': [], 'root': None, 'allocation_count': 0, 'old_snapshot': []}), ({'visited': [], 'terminal': 3, 'generation': 7, 'old_ids': [3, 4]}, {'alloc_order': [], 'terminal': [3, 'shared'], 'links': [], 'root': 3, 'allocation_count': 0, 'old_snapshot': [3, 4]}), ({'visited': [1], 'terminal': 2, 'generation': 7, 'old_ids': [1, 2, 3]}, {'alloc_order': [1], 'terminal': [2, 'shared'], 'links': [[1, 2]], 'root': 1, 'allocation_count': 1, 'old_snapshot': [1, 2, 3]}), ({'visited': [1, 4, 7], 'terminal': 9, 'generation': 7, 'old_ids': [1, 2, 4, 7, 9]}, {'alloc_order': [7, 4, 1], 'terminal': [9, 'shared'], 'links': [[1, 4], [4, 7], [7, 9]], 'root': 1, 'allocation_count': 3, 'old_snapshot': [1, 2, 4, 7, 9]}), ({'visited': [8, 3], 'terminal': None, 'generation': 7, 'old_ids': [8, 3]}, {'alloc_order': [3, 8], 'terminal': None, 'links': [[8, 3], [3, None]], 'root': 8, 'allocation_count': 2, 'old_snapshot': [8, 3]}), ({'visited': [2, 5, 9, 6], 'terminal': 10, 'generation': 7, 'old_ids': [2, 5, 9, 6, 10, 11]}, {'alloc_order': [6, 9, 5, 2], 'terminal': [10, 'shared'], 'links': [[2, 5], [5, 9], [9, 6], [6, 10]], 'root': 2, 'allocation_count': 4, 'old_snapshot': [2, 5, 9, 6, 10, 11]}), ({'visited': [2, 5, 9, 6, 100], 'terminal': 10, 'generation': 7, 'old_ids': [2, 5, 9, 6, 10, 11, 100]}, {'alloc_order': [100, 6, 9, 5, 2], 'terminal': [10, 'shared'], 'links': [[2, 5], [5, 9], [9, 6], [6, 100], [100, 10]], 'root': 2, 'allocation_count': 5, 'old_snapshot': [2, 5, 9, 6, 10, 11, 100]})], [({'visited': [], 'terminal': None, 'generation': 7, 'old_ids': []}, {'alloc_order': [], 'terminal': None, 'links': [], 'root': None, 'allocation_count': 0, 'old_snapshot': []}), ({'visited': [], 'terminal': 3, 'generation': 7, 'old_ids': [3, 4]}, {'alloc_order': [], 'terminal': [3, 'shared'], 'links': [], 'root': 3, 'allocation_count': 0, 'old_snapshot': [3, 4]}), ({'visited': [1], 'terminal': 2, 'generation': 7, 'old_ids': [1, 2, 3]}, {'alloc_order': [1], 'terminal': [2, 'shared'], 'links': [[1, 2]], 'root': 1, 'allocation_count': 1, 'old_snapshot': [1, 2, 3]}), ({'visited': [1, 4, 7], 'terminal': 9, 'generation': 7, 'old_ids': [1, 2, 4, 7, 9]}, {'alloc_order': [7, 4, 1], 'terminal': [9, 'shared'], 'links': [[1, 4], [4, 7], [7, 9]], 'root': 1, 'allocation_count': 3, 'old_snapshot': [1, 2, 4, 7, 9]}), ({'visited': [8, 3], 'terminal': None, 'generation': 7, 'old_ids': [8, 3]}, {'alloc_order': [3, 8], 'terminal': None, 'links': [[8, 3], [3, None]], 'root': 8, 'allocation_count': 2, 'old_snapshot': [8, 3]}), ({'visited': [2, 5, 9, 6], 'terminal': 10, 'generation': 7, 'old_ids': [2, 5, 9, 6, 10, 11]}, {'alloc_order': [6, 9, 5, 2], 'terminal': [10, 'shared'], 'links': [[2, 5], [5, 9], [9, 6], [6, 10]], 'root': 2, 'allocation_count': 4, 'old_snapshot': [2, 5, 9, 6, 10, 11]}), ({'visited': [2, 5, 9, 6, 100, 101], 'terminal': 10, 'generation': 7, 'old_ids': [2, 5, 9, 6, 10, 11, 100, 101]}, {'alloc_order': [101, 100, 6, 9, 5, 2], 'terminal': [10, 'shared'], 'links': [[2, 5], [5, 9], [9, 6], [6, 100], [100, 101], [101, 10]], 'root': 2, 'allocation_count': 6, 'old_snapshot': [2, 5, 9, 6, 10, 11, 100, 101]})], [({'visited': [], 'terminal': None, 'generation': 7, 'old_ids': []}, {'alloc_order': [], 'terminal': None, 'links': [], 'root': None, 'allocation_count': 0, 'old_snapshot': []}), ({'visited': [], 'terminal': 3, 'generation': 7, 'old_ids': [3, 4]}, {'alloc_order': [], 'terminal': [3, 'shared'], 'links': [], 'root': 3, 'allocation_count': 0, 'old_snapshot': [3, 4]}), ({'visited': [1], 'terminal': 2, 'generation': 7, 'old_ids': [1, 2, 3]}, {'alloc_order': [1], 'terminal': [2, 'shared'], 'links': [[1, 2]], 'root': 1, 'allocation_count': 1, 'old_snapshot': [1, 2, 3]}), ({'visited': [1, 4, 7], 'terminal': 9, 'generation': 7, 'old_ids': [1, 2, 4, 7, 9]}, {'alloc_order': [7, 4, 1], 'terminal': [9, 'shared'], 'links': [[1, 4], [4, 7], [7, 9]], 'root': 1, 'allocation_count': 3, 'old_snapshot': [1, 2, 4, 7, 9]}), ({'visited': [8, 3], 'terminal': None, 'generation': 7, 'old_ids': [8, 3]}, {'alloc_order': [3, 8], 'terminal': None, 'links': [[8, 3], [3, None]], 'root': 8, 'allocation_count': 2, 'old_snapshot': [8, 3]}), ({'visited': [2, 5, 9, 6], 'terminal': 10, 'generation': 7, 'old_ids': [2, 5, 9, 6, 10, 11]}, {'alloc_order': [6, 9, 5, 2], 'terminal': [10, 'shared'], 'links': [[2, 5], [5, 9], [9, 6], [6, 10]], 'root': 2, 'allocation_count': 4, 'old_snapshot': [2, 5, 9, 6, 10, 11]}), ({'visited': [2, 5, 9, 6, 100, 101, 102], 'terminal': 10, 'generation': 7, 'old_ids': [2, 5, 9, 6, 10, 11, 100, 101, 102]}, {'alloc_order': [102, 101, 100, 6, 9, 5, 2], 'terminal': [10, 'shared'], 'links': [[2, 5], [5, 9], [9, 6], [6, 100], [100, 101], [101, 102], [102, 10]], 'root': 2, 'allocation_count': 7, 'old_snapshot': [2, 5, 9, 6, 10, 11, 100, 101, 102]})], [({'visited': [], 'terminal': None, 'generation': 7, 'old_ids': []}, {'alloc_order': [], 'terminal': None, 'links': [], 'root': None, 'allocation_count': 0, 'old_snapshot': []}), ({'visited': [], 'terminal': 3, 'generation': 7, 'old_ids': [3, 4]}, {'alloc_order': [], 'terminal': [3, 'shared'], 'links': [], 'root': 3, 'allocation_count': 0, 'old_snapshot': [3, 4]}), ({'visited': [1], 'terminal': 2, 'generation': 7, 'old_ids': [1, 2, 3]}, {'alloc_order': [1], 'terminal': [2, 'shared'], 'links': [[1, 2]], 'root': 1, 'allocation_count': 1, 'old_snapshot': [1, 2, 3]}), ({'visited': [1, 4, 7], 'terminal': 9, 'generation': 7, 'old_ids': [1, 2, 4, 7, 9]}, {'alloc_order': [7, 4, 1], 'terminal': [9, 'shared'], 'links': [[1, 4], [4, 7], [7, 9]], 'root': 1, 'allocation_count': 3, 'old_snapshot': [1, 2, 4, 7, 9]}), ({'visited': [8, 3], 'terminal': None, 'generation': 7, 'old_ids': [8, 3]}, {'alloc_order': [3, 8], 'terminal': None, 'links': [[8, 3], [3, None]], 'root': 8, 'allocation_count': 2, 'old_snapshot': [8, 3]}), ({'visited': [2, 5, 9, 6], 'terminal': 10, 'generation': 7, 'old_ids': [2, 5, 9, 6, 10, 11]}, {'alloc_order': [6, 9, 5, 2], 'terminal': [10, 'shared'], 'links': [[2, 5], [5, 9], [9, 6], [6, 10]], 'root': 2, 'allocation_count': 4, 'old_snapshot': [2, 5, 9, 6, 10, 11]}), ({'visited': [2, 5, 9, 6, 100, 101, 102, 103], 'terminal': 10, 'generation': 7, 'old_ids': [2, 5, 9, 6, 10, 11, 100, 101, 102, 103]}, {'alloc_order': [103, 102, 101, 100, 6, 9, 5, 2], 'terminal': [10, 'shared'], 'links': [[2, 5], [5, 9], [9, 6], [6, 100], [100, 101], [101, 102], [102, 103], [103, 10]], 'root': 2, 'allocation_count': 8, 'old_snapshot': [2, 5, 9, 6, 10, 11, 100, 101, 102, 103]})], [({'visited': [], 'terminal': None, 'generation': 7, 'old_ids': []}, {'alloc_order': [], 'terminal': None, 'links': [], 'root': None, 'allocation_count': 0, 'old_snapshot': []}), ({'visited': [], 'terminal': 3, 'generation': 7, 'old_ids': [3, 4]}, {'alloc_order': [], 'terminal': [3, 'shared'], 'links': [], 'root': 3, 'allocation_count': 0, 'old_snapshot': [3, 4]}), ({'visited': [1], 'terminal': 2, 'generation': 7, 'old_ids': [1, 2, 3]}, {'alloc_order': [1], 'terminal': [2, 'shared'], 'links': [[1, 2]], 'root': 1, 'allocation_count': 1, 'old_snapshot': [1, 2, 3]}), ({'visited': [1, 4, 7], 'terminal': 9, 'generation': 7, 'old_ids': [1, 2, 4, 7, 9]}, {'alloc_order': [7, 4, 1], 'terminal': [9, 'shared'], 'links': [[1, 4], [4, 7], [7, 9]], 'root': 1, 'allocation_count': 3, 'old_snapshot': [1, 2, 4, 7, 9]}), ({'visited': [8, 3], 'terminal': None, 'generation': 7, 'old_ids': [8, 3]}, {'alloc_order': [3, 8], 'terminal': None, 'links': [[8, 3], [3, None]], 'root': 8, 'allocation_count': 2, 'old_snapshot': [8, 3]}), ({'visited': [2, 5, 9, 6], 'terminal': 10, 'generation': 7, 'old_ids': [2, 5, 9, 6, 10, 11]}, {'alloc_order': [6, 9, 5, 2], 'terminal': [10, 'shared'], 'links': [[2, 5], [5, 9], [9, 6], [6, 10]], 'root': 2, 'allocation_count': 4, 'old_snapshot': [2, 5, 9, 6, 10, 11]}), ({'visited': [2, 5, 9, 6, 100, 101, 102, 103, 104], 'terminal': 10, 'generation': 7, 'old_ids': [2, 5, 9, 6, 10, 11, 100, 101, 102, 103, 104]}, {'alloc_order': [104, 103, 102, 101, 100, 6, 9, 5, 2], 'terminal': [10, 'shared'], 'links': [[2, 5], [5, 9], [9, 6], [6, 100], [100, 101], [101, 102], [102, 103], [103, 104], [104, 10]], 'root': 2, 'allocation_count': 9, 'old_snapshot': [2, 5, 9, 6, 10, 11, 100, 101, 102, 103, 104]})]][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 persistent meld reuse certificate reports an incorrect allocation count.

A persistent meld recursion trace lists winner nodes visited and one terminal untouched subtree id (or None), with fresh generation g. Rebuild only visited winners during unwind in reverse visitation order and share the terminal subtree. Return allocation order, shared terminal reference, reconstructed links, new root, allocation count, and original snapshot ids unchanged. This is a path-copy trace, not a complete heap algorithm.

split: open-access


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

N = 1
observations = []
def solve(d):
    v=d['visited']; terminal=d['terminal']; g=d['generation']; order=list(reversed(v))
    return {'alloc_order': order,
    'terminal': None if terminal is None else [terminal,"shared"],
    'links': [[v[i],v[i+1] if i+1<len(v) else terminal] for i in range(len(v))],
    'root': v[0] if v else terminal,
    'allocation_count': len(v),
    'old_snapshot': [x for x in d["old_ids"] if x not in v]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'visited': [], 'terminal': None, 'generation': 7, 'old_ids': []}, {'alloc_order': [], 'terminal': None, 'links': [], 'root': None, 'allocation_count': 0, 'old_snapshot': []}), ({'visited': [], 'terminal': 3, 'generation': 7, 'old_ids': [3, 4]}, {'alloc_order': [], 'terminal': [3, 'shared'], 'links': [], 'root': 3, 'allocation_count': 0, 'old_snapshot': [3, 4]}), ({'visited': [1], 'terminal': 2, 'generation': 7, 'old_ids': [1, 2, 3]}, {'alloc_order': [1], 'terminal': [2, 'shared'], 'links': [[1, 2]], 'root': 1, 'allocation_count': 1, 'old_snapshot': [1, 2, 3]}), ({'visited': [1, 4, 7], 'terminal': 9, 'generation': 7, 'old_ids': [1, 2, 4, 7, 9]}, {'alloc_order': [7, 4, 1], 'terminal': [9, 'shared'], 'links': [[1, 4], [4, 7], [7, 9]], 'root': 1, 'allocation_count': 3, 'old_snapshot': [1, 2, 4, 7, 9]}), ({'visited': [8, 3], 'terminal': None, 'generation': 7, 'old_ids': [8, 3]}, {'alloc_order': [3, 8], 'terminal': None, 'links': [[8, 3], [3, None]], 'root': 8, 'allocation_count': 2, 'old_snapshot': [8, 3]}), ({'visited': [2, 5, 9, 6], 'terminal': 10, 'generation': 7, 'old_ids': [2, 5, 9, 6, 10, 11]}, {'alloc_order': [6, 9, 5, 2], 'terminal': [10, 'shared'], 'links': [[2, 5], [5, 9], [9, 6], [6, 10]], 'root': 2, 'allocation_count': 4, 'old_snapshot': [2, 5, 9, 6, 10, 11]}), ({'visited': [2, 5, 9, 6, 100], 'terminal': 10, 'generation': 7, 'old_ids': [2, 5, 9, 6, 10, 11, 100]}, {'alloc_order': [100, 6, 9, 5, 2], 'terminal': [10, 'shared'], 'links': [[2, 5], [5, 9], [9, 6], [6, 100], [100, 10]], 'root': 2, 'allocation_count': 5, 'old_snapshot': [2, 5, 9, 6, 10, 11, 100]})], [({'visited': [], 'terminal': None, 'generation': 7, 'old_ids': []}, {'alloc_order': [], 'terminal': None, 'links': [], 'root': None, 'allocation_count': 0, 'old_snapshot': []}), ({'visited': [], 'terminal': 3, 'generation': 7, 'old_ids': [3, 4]}, {'alloc_order': [], 'terminal': [3, 'shared'], 'links': [], 'root': 3, 'allocation_count': 0, 'old_snapshot': [3, 4]}), ({'visited': [1], 'terminal': 2, 'generation': 7, 'old_ids': [1, 2, 3]}, {'alloc_order': [1], 'terminal': [2, 'shared'], 'links': [[1, 2]], 'root': 1, 'allocation_count': 1, 'old_snapshot': [1, 2, 3]}), ({'visited': [1, 4, 7], 'terminal': 9, 'generation': 7, 'old_ids': [1, 2, 4, 7, 9]}, {'alloc_order': [7, 4, 1], 'terminal': [9, 'shared'], 'links': [[1, 4], [4, 7], [7, 9]], 'root': 1, 'allocation_count': 3, 'old_snapshot': [1, 2, 4, 7, 9]}), ({'visited': [8, 3], 'terminal': None, 'generation': 7, 'old_ids': [8, 3]}, {'alloc_order': [3, 8], 'terminal': None, 'links': [[8, 3], [3, None]], 'root': 8, 'allocation_count': 2, 'old_snapshot': [8, 3]}), ({'visited': [2, 5, 9, 6], 'terminal': 10, 'generation': 7, 'old_ids': [2, 5, 9, 6, 10, 11]}, {'alloc_order': [6, 9, 5, 2], 'terminal': [10, 'shared'], 'links': [[2, 5], [5, 9], [9, 6], [6, 10]], 'root': 2, 'allocation_count': 4, 'old_snapshot': [2, 5, 9, 6, 10, 11]}), ({'visited': [2, 5, 9, 6, 100, 101], 'terminal': 10, 'generation': 7, 'old_ids': [2, 5, 9, 6, 10, 11, 100, 101]}, {'alloc_order': [101, 100, 6, 9, 5, 2], 'terminal': [10, 'shared'], 'links': [[2, 5], [5, 9], [9, 6], [6, 100], [100, 101], [101, 10]], 'root': 2, 'allocation_count': 6, 'old_snapshot': [2, 5, 9, 6, 10, 11, 100, 101]})], [({'visited': [], 'terminal': None, 'generation': 7, 'old_ids': []}, {'alloc_order': [], 'terminal': None, 'links': [], 'root': None, 'allocation_count': 0, 'old_snapshot': []}), ({'visited': [], 'terminal': 3, 'generation': 7, 'old_ids': [3, 4]}, {'alloc_order': [], 'terminal': [3, 'shared'], 'links': [], 'root': 3, 'allocation_count': 0, 'old_snapshot': [3, 4]}), ({'visited': [1], 'terminal': 2, 'generation': 7, 'old_ids': [1, 2, 3]}, {'alloc_order': [1], 'terminal': [2, 'shared'], 'links': [[1, 2]], 'root': 1, 'allocation_count': 1, 'old_snapshot': [1, 2, 3]}), ({'visited': [1, 4, 7], 'terminal': 9, 'generation': 7, 'old_ids': [1, 2, 4, 7, 9]}, {'alloc_order': [7, 4, 1], 'terminal': [9, 'shared'], 'links': [[1, 4], [4, 7], [7, 9]], 'root': 1, 'allocation_count': 3, 'old_snapshot': [1, 2, 4, 7, 9]}), ({'visited': [8, 3], 'terminal': None, 'generation': 7, 'old_ids': [8, 3]}, {'alloc_order': [3, 8], 'terminal': None, 'links': [[8, 3], [3, None]], 'root': 8, 'allocation_count': 2, 'old_snapshot': [8, 3]}), ({'visited': [2, 5, 9, 6], 'terminal': 10, 'generation': 7, 'old_ids': [2, 5, 9, 6, 10, 11]}, {'alloc_order': [6, 9, 5, 2], 'terminal': [10, 'shared'], 'links': [[2, 5], [5, 9], [9, 6], [6, 10]], 'root': 2, 'allocation_count': 4, 'old_snapshot': [2, 5, 9, 6, 10, 11]}), ({'visited': [2, 5, 9, 6, 100, 101, 102], 'terminal': 10, 'generation': 7, 'old_ids': [2, 5, 9, 6, 10, 11, 100, 101, 102]}, {'alloc_order': [102, 101, 100, 6, 9, 5, 2], 'terminal': [10, 'shared'], 'links': [[2, 5], [5, 9], [9, 6], [6, 100], [100, 101], [101, 102], [102, 10]], 'root': 2, 'allocation_count': 7, 'old_snapshot': [2, 5, 9, 6, 10, 11, 100, 101, 102]})], [({'visited': [], 'terminal': None, 'generation': 7, 'old_ids': []}, {'alloc_order': [], 'terminal': None, 'links': [], 'root': None, 'allocation_count': 0, 'old_snapshot': []}), ({'visited': [], 'terminal': 3, 'generation': 7, 'old_ids': [3, 4]}, {'alloc_order': [], 'terminal': [3, 'shared'], 'links': [], 'root': 3, 'allocation_count': 0, 'old_snapshot': [3, 4]}), ({'visited': [1], 'terminal': 2, 'generation': 7, 'old_ids': [1, 2, 3]}, {'alloc_order': [1], 'terminal': [2, 'shared'], 'links': [[1, 2]], 'root': 1, 'allocation_count': 1, 'old_snapshot': [1, 2, 3]}), ({'visited': [1, 4, 7], 'terminal': 9, 'generation': 7, 'old_ids': [1, 2, 4, 7, 9]}, {'alloc_order': [7, 4, 1], 'terminal': [9, 'shared'], 'links': [[1, 4], [4, 7], [7, 9]], 'root': 1, 'allocation_count': 3, 'old_snapshot': [1, 2, 4, 7, 9]}), ({'visited': [8, 3], 'terminal': None, 'generation': 7, 'old_ids': [8, 3]}, {'alloc_order': [3, 8], 'terminal': None, 'links': [[8, 3], [3, None]], 'root': 8, 'allocation_count': 2, 'old_snapshot': [8, 3]}), ({'visited': [2, 5, 9, 6], 'terminal': 10, 'generation': 7, 'old_ids': [2, 5, 9, 6, 10, 11]}, {'alloc_order': [6, 9, 5, 2], 'terminal': [10, 'shared'], 'links': [[2, 5], [5, 9], [9, 6], [6, 10]], 'root': 2, 'allocation_count': 4, 'old_snapshot': [2, 5, 9, 6, 10, 11]}), ({'visited': [2, 5, 9, 6, 100, 101, 102, 103], 'terminal': 10, 'generation': 7, 'old_ids': [2, 5, 9, 6, 10, 11, 100, 101, 102, 103]}, {'alloc_order': [103, 102, 101, 100, 6, 9, 5, 2], 'terminal': [10, 'shared'], 'links': [[2, 5], [5, 9], [9, 6], [6, 100], [100, 101], [101, 102], [102, 103], [103, 10]], 'root': 2, 'allocation_count': 8, 'old_snapshot': [2, 5, 9, 6, 10, 11, 100, 101, 102, 103]})], [({'visited': [], 'terminal': None, 'generation': 7, 'old_ids': []}, {'alloc_order': [], 'terminal': None, 'links': [], 'root': None, 'allocation_count': 0, 'old_snapshot': []}), ({'visited': [], 'terminal': 3, 'generation': 7, 'old_ids': [3, 4]}, {'alloc_order': [], 'terminal': [3, 'shared'], 'links': [], 'root': 3, 'allocation_count': 0, 'old_snapshot': [3, 4]}), ({'visited': [1], 'terminal': 2, 'generation': 7, 'old_ids': [1, 2, 3]}, {'alloc_order': [1], 'terminal': [2, 'shared'], 'links': [[1, 2]], 'root': 1, 'allocation_count': 1, 'old_snapshot': [1, 2, 3]}), ({'visited': [1, 4, 7], 'terminal': 9, 'generation': 7, 'old_ids': [1, 2, 4, 7, 9]}, {'alloc_order': [7, 4, 1], 'terminal': [9, 'shared'], 'links': [[1, 4], [4, 7], [7, 9]], 'root': 1, 'allocation_count': 3, 'old_snapshot': [1, 2, 4, 7, 9]}), ({'visited': [8, 3], 'terminal': None, 'generation': 7, 'old_ids': [8, 3]}, {'alloc_order': [3, 8], 'terminal': None, 'links': [[8, 3], [3, None]], 'root': 8, 'allocation_count': 2, 'old_snapshot': [8, 3]}), ({'visited': [2, 5, 9, 6], 'terminal': 10, 'generation': 7, 'old_ids': [2, 5, 9, 6, 10, 11]}, {'alloc_order': [6, 9, 5, 2], 'terminal': [10, 'shared'], 'links': [[2, 5], [5, 9], [9, 6], [6, 10]], 'root': 2, 'allocation_count': 4, 'old_snapshot': [2, 5, 9, 6, 10, 11]}), ({'visited': [2, 5, 9, 6, 100, 101, 102, 103, 104], 'terminal': 10, 'generation': 7, 'old_ids': [2, 5, 9, 6, 10, 11, 100, 101, 102, 103, 104]}, {'alloc_order': [104, 103, 102, 101, 100, 6, 9, 5, 2], 'terminal': [10, 'shared'], 'links': [[2, 5], [5, 9], [9, 6], [6, 100], [100, 101], [101, 102], [102, 103], [103, 104], [104, 10]], 'root': 2, 'allocation_count': 9, 'old_snapshot': [2, 5, 9, 6, 10, 11, 100, 101, 102, 103, 104]})]][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):
    v=d['visited']; terminal=d['terminal']; g=d['generation']; order=list(reversed(v))
    return {'alloc_order': order,
    'terminal': None if terminal is None else [terminal,"shared"],
    'links': [[v[i],v[i+1] if i+1<len(v) else terminal] for i in range(len(v))],
    'root': v[0] if v else terminal,
    'allocation_count': len(v),
    'old_snapshot': []}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'visited': [], 'terminal': None, 'generation': 7, 'old_ids': []}, {'alloc_order': [], 'terminal': None, 'links': [], 'root': None, 'allocation_count': 0, 'old_snapshot': []}), ({'visited': [], 'terminal': 3, 'generation': 7, 'old_ids': [3, 4]}, {'alloc_order': [], 'terminal': [3, 'shared'], 'links': [], 'root': 3, 'allocation_count': 0, 'old_snapshot': [3, 4]}), ({'visited': [1], 'terminal': 2, 'generation': 7, 'old_ids': [1, 2, 3]}, {'alloc_order': [1], 'terminal': [2, 'shared'], 'links': [[1, 2]], 'root': 1, 'allocation_count': 1, 'old_snapshot': [1, 2, 3]}), ({'visited': [1, 4, 7], 'terminal': 9, 'generation': 7, 'old_ids': [1, 2, 4, 7, 9]}, {'alloc_order': [7, 4, 1], 'terminal': [9, 'shared'], 'links': [[1, 4], [4, 7], [7, 9]], 'root': 1, 'allocation_count': 3, 'old_snapshot': [1, 2, 4, 7, 9]}), ({'visited': [8, 3], 'terminal': None, 'generation': 7, 'old_ids': [8, 3]}, {'alloc_order': [3, 8], 'terminal': None, 'links': [[8, 3], [3, None]], 'root': 8, 'allocation_count': 2, 'old_snapshot': [8, 3]}), ({'visited': [2, 5, 9, 6], 'terminal': 10, 'generation': 7, 'old_ids': [2, 5, 9, 6, 10, 11]}, {'alloc_order': [6, 9, 5, 2], 'terminal': [10, 'shared'], 'links': [[2, 5], [5, 9], [9, 6], [6, 10]], 'root': 2, 'allocation_count': 4, 'old_snapshot': [2, 5, 9, 6, 10, 11]}), ({'visited': [2, 5, 9, 6, 100], 'terminal': 10, 'generation': 7, 'old_ids': [2, 5, 9, 6, 10, 11, 100]}, {'alloc_order': [100, 6, 9, 5, 2], 'terminal': [10, 'shared'], 'links': [[2, 5], [5, 9], [9, 6], [6, 100], [100, 10]], 'root': 2, 'allocation_count': 5, 'old_snapshot': [2, 5, 9, 6, 10, 11, 100]})], [({'visited': [], 'terminal': None, 'generation': 7, 'old_ids': []}, {'alloc_order': [], 'terminal': None, 'links': [], 'root': None, 'allocation_count': 0, 'old_snapshot': []}), ({'visited': [], 'terminal': 3, 'generation': 7, 'old_ids': [3, 4]}, {'alloc_order': [], 'terminal': [3, 'shared'], 'links': [], 'root': 3, 'allocation_count': 0, 'old_snapshot': [3, 4]}), ({'visited': [1], 'terminal': 2, 'generation': 7, 'old_ids': [1, 2, 3]}, {'alloc_order': [1], 'terminal': [2, 'shared'], 'links': [[1, 2]], 'root': 1, 'allocation_count': 1, 'old_snapshot': [1, 2, 3]}), ({'visited': [1, 4, 7], 'terminal': 9, 'generation': 7, 'old_ids': [1, 2, 4, 7, 9]}, {'alloc_order': [7, 4, 1], 'terminal': [9, 'shared'], 'links': [[1, 4], [4, 7], [7, 9]], 'root': 1, 'allocation_count': 3, 'old_snapshot': [1, 2, 4, 7, 9]}), ({'visited': [8, 3], 'terminal': None, 'generation': 7, 'old_ids': [8, 3]}, {'alloc_order': [3, 8], 'terminal': None, 'links': [[8, 3], [3, None]], 'root': 8, 'allocation_count': 2, 'old_snapshot': [8, 3]}), ({'visited': [2, 5, 9, 6], 'terminal': 10, 'generation': 7, 'old_ids': [2, 5, 9, 6, 10, 11]}, {'alloc_order': [6, 9, 5, 2], 'terminal': [10, 'shared'], 'links': [[2, 5], [5, 9], [9, 6], [6, 10]], 'root': 2, 'allocation_count': 4, 'old_snapshot': [2, 5, 9, 6, 10, 11]}), ({'visited': [2, 5, 9, 6, 100, 101], 'terminal': 10, 'generation': 7, 'old_ids': [2, 5, 9, 6, 10, 11, 100, 101]}, {'alloc_order': [101, 100, 6, 9, 5, 2], 'terminal': [10, 'shared'], 'links': [[2, 5], [5, 9], [9, 6], [6, 100], [100, 101], [101, 10]], 'root': 2, 'allocation_count': 6, 'old_snapshot': [2, 5, 9, 6, 10, 11, 100, 101]})], [({'visited': [], 'terminal': None, 'generation': 7, 'old_ids': []}, {'alloc_order': [], 'terminal': None, 'links': [], 'root': None, 'allocation_count': 0, 'old_snapshot': []}), ({'visited': [], 'terminal': 3, 'generation': 7, 'old_ids': [3, 4]}, {'alloc_order': [], 'terminal': [3, 'shared'], 'links': [], 'root': 3, 'allocation_count': 0, 'old_snapshot': [3, 4]}), ({'visited': [1], 'terminal': 2, 'generation': 7, 'old_ids': [1, 2, 3]}, {'alloc_order': [1], 'terminal': [2, 'shared'], 'links': [[1, 2]], 'root': 1, 'allocation_count': 1, 'old_snapshot': [1, 2, 3]}), ({'visited': [1, 4, 7], 'terminal': 9, 'generation': 7, 'old_ids': [1, 2, 4, 7, 9]}, {'alloc_order': [7, 4, 1], 'terminal': [9, 'shared'], 'links': [[1, 4], [4, 7], [7, 9]], 'root': 1, 'allocation_count': 3, 'old_snapshot': [1, 2, 4, 7, 9]}), ({'visited': [8, 3], 'terminal': None, 'generation': 7, 'old_ids': [8, 3]}, {'alloc_order': [3, 8], 'terminal': None, 'links': [[8, 3], [3, None]], 'root': 8, 'allocation_count': 2, 'old_snapshot': [8, 3]}), ({'visited': [2, 5, 9, 6], 'terminal': 10, 'generation': 7, 'old_ids': [2, 5, 9, 6, 10, 11]}, {'alloc_order': [6, 9, 5, 2], 'terminal': [10, 'shared'], 'links': [[2, 5], [5, 9], [9, 6], [6, 10]], 'root': 2, 'allocation_count': 4, 'old_snapshot': [2, 5, 9, 6, 10, 11]}), ({'visited': [2, 5, 9, 6, 100, 101, 102], 'terminal': 10, 'generation': 7, 'old_ids': [2, 5, 9, 6, 10, 11, 100, 101, 102]}, {'alloc_order': [102, 101, 100, 6, 9, 5, 2], 'terminal': [10, 'shared'], 'links': [[2, 5], [5, 9], [9, 6], [6, 100], [100, 101], [101, 102], [102, 10]], 'root': 2, 'allocation_count': 7, 'old_snapshot': [2, 5, 9, 6, 10, 11, 100, 101, 102]})], [({'visited': [], 'terminal': None, 'generation': 7, 'old_ids': []}, {'alloc_order': [], 'terminal': None, 'links': [], 'root': None, 'allocation_count': 0, 'old_snapshot': []}), ({'visited': [], 'terminal': 3, 'generation': 7, 'old_ids': [3, 4]}, {'alloc_order': [], 'terminal': [3, 'shared'], 'links': [], 'root': 3, 'allocation_count': 0, 'old_snapshot': [3, 4]}), ({'visited': [1], 'terminal': 2, 'generation': 7, 'old_ids': [1, 2, 3]}, {'alloc_order': [1], 'terminal': [2, 'shared'], 'links': [[1, 2]], 'root': 1, 'allocation_count': 1, 'old_snapshot': [1, 2, 3]}), ({'visited': [1, 4, 7], 'terminal': 9, 'generation': 7, 'old_ids': [1, 2, 4, 7, 9]}, {'alloc_order': [7, 4, 1], 'terminal': [9, 'shared'], 'links': [[1, 4], [4, 7], [7, 9]], 'root': 1, 'allocation_count': 3, 'old_snapshot': [1, 2, 4, 7, 9]}), ({'visited': [8, 3], 'terminal': None, 'generation': 7, 'old_ids': [8, 3]}, {'alloc_order': [3, 8], 'terminal': None, 'links': [[8, 3], [3, None]], 'root': 8, 'allocation_count': 2, 'old_snapshot': [8, 3]}), ({'visited': [2, 5, 9, 6], 'terminal': 10, 'generation': 7, 'old_ids': [2, 5, 9, 6, 10, 11]}, {'alloc_order': [6, 9, 5, 2], 'terminal': [10, 'shared'], 'links': [[2, 5], [5, 9], [9, 6], [6, 10]], 'root': 2, 'allocation_count': 4, 'old_snapshot': [2, 5, 9, 6, 10, 11]}), ({'visited': [2, 5, 9, 6, 100, 101, 102, 103], 'terminal': 10, 'generation': 7, 'old_ids': [2, 5, 9, 6, 10, 11, 100, 101, 102, 103]}, {'alloc_order': [103, 102, 101, 100, 6, 9, 5, 2], 'terminal': [10, 'shared'], 'links': [[2, 5], [5, 9], [9, 6], [6, 100], [100, 101], [101, 102], [102, 103], [103, 10]], 'root': 2, 'allocation_count': 8, 'old_snapshot': [2, 5, 9, 6, 10, 11, 100, 101, 102, 103]})], [({'visited': [], 'terminal': None, 'generation': 7, 'old_ids': []}, {'alloc_order': [], 'terminal': None, 'links': [], 'root': None, 'allocation_count': 0, 'old_snapshot': []}), ({'visited': [], 'terminal': 3, 'generation': 7, 'old_ids': [3, 4]}, {'alloc_order': [], 'terminal': [3, 'shared'], 'links': [], 'root': 3, 'allocation_count': 0, 'old_snapshot': [3, 4]}), ({'visited': [1], 'terminal': 2, 'generation': 7, 'old_ids': [1, 2, 3]}, {'alloc_order': [1], 'terminal': [2, 'shared'], 'links': [[1, 2]], 'root': 1, 'allocation_count': 1, 'old_snapshot': [1, 2, 3]}), ({'visited': [1, 4, 7], 'terminal': 9, 'generation': 7, 'old_ids': [1, 2, 4, 7, 9]}, {'alloc_order': [7, 4, 1], 'terminal': [9, 'shared'], 'links': [[1, 4], [4, 7], [7, 9]], 'root': 1, 'allocation_count': 3, 'old_snapshot': [1, 2, 4, 7, 9]}), ({'visited': [8, 3], 'terminal': None, 'generation': 7, 'old_ids': [8, 3]}, {'alloc_order': [3, 8], 'terminal': None, 'links': [[8, 3], [3, None]], 'root': 8, 'allocation_count': 2, 'old_snapshot': [8, 3]}), ({'visited': [2, 5, 9, 6], 'terminal': 10, 'generation': 7, 'old_ids': [2, 5, 9, 6, 10, 11]}, {'alloc_order': [6, 9, 5, 2], 'terminal': [10, 'shared'], 'links': [[2, 5], [5, 9], [9, 6], [6, 10]], 'root': 2, 'allocation_count': 4, 'old_snapshot': [2, 5, 9, 6, 10, 11]}), ({'visited': [2, 5, 9, 6, 100, 101, 102, 103, 104], 'terminal': 10, 'generation': 7, 'old_ids': [2, 5, 9, 6, 10, 11, 100, 101, 102, 103, 104]}, {'alloc_order': [104, 103, 102, 101, 100, 6, 9, 5, 2], 'terminal': [10, 'shared'], 'links': [[2, 5], [5, 9], [9, 6], [6, 100], [100, 101], [101, 102], [102, 103], [103, 104], [104, 10]], 'root': 2, 'allocation_count': 9, 'old_snapshot': [2, 5, 9, 6, 10, 11, 100, 101, 102, 103, 104]})]][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 persistent meld reuse certificate reports an incorrect old snapshot.

A persistent meld recursion trace lists winner nodes visited and one terminal untouched subtree id (or None), with fresh generation g. Rebuild only visited winners during unwind in reverse visitation order and share the terminal subtree. Return allocation order, shared terminal reference, reconstructed links, new root, allocation count, and original snapshot ids unchanged. This is a path-copy trace, not a complete heap algorithm.

split: open-access


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

N = 1
observations = []
def solve(d):
    n=d['size']; b=d['page_size']; i=d['index']; children=[j for j in (2*i+1,2*i+2) if j<n]
    def address(j): return [j//b,j%b]
    return {'address': [i%b,i//b],
    'parent': None if i==0 else address((i-1)//2),
    'children': [address(j) for j in children],
    'pages': (n+b-1)//b,
    'tail_occupancy': (n-1)%b+1,
    'touched': sorted({j//b for j in [i]+children})}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 11, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 4, 'tail_occupancy': 2, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 12, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 4, 'tail_occupancy': 3, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 13, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 5, 'tail_occupancy': 1, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 14, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 5, 'tail_occupancy': 2, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 15, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 5, 'tail_occupancy': 3, 'touched': [1, 3]})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

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

N = 1
observations = []
def solve(d):
    n=d['size']; b=d['page_size']; i=d['index']; children=[j for j in (2*i+1,2*i+2) if j<n]
    def address(j): return [j//b,j%b]
    return {'address': [(i+1)//b,(i+1)%b],
    'parent': None if i==0 else address((i-1)//2),
    'children': [address(j) for j in children],
    'pages': (n+b-1)//b,
    'tail_occupancy': (n-1)%b+1,
    'touched': sorted({j//b for j in [i]+children})}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 11, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 4, 'tail_occupancy': 2, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 12, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 4, 'tail_occupancy': 3, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 13, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 5, 'tail_occupancy': 1, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 14, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 5, 'tail_occupancy': 2, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 15, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 5, 'tail_occupancy': 3, 'touched': [1, 3]})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
The bounded paged heap layout certificate reports an incorrect address.

A binary heap is stored in fixed-size pages of B slots using zero-based global indices. For n logical members and selected live index i report its page/offset, parent address or None, child addresses, allocated page count, last-page live occupancy, and pages touched by reading i and its existing children. B>=1 and 0<=i<n.

split: open-access


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

N = 1
observations = []
def solve(d):
    n=d['size']; b=d['page_size']; i=d['index']; children=[j for j in (2*i+1,2*i+2) if j<n]
    def address(j): return [j//b,j%b]
    return {'address': address(i),
    'parent': None if i==0 else address(i//2),
    'children': [address(j) for j in children],
    'pages': (n+b-1)//b,
    'tail_occupancy': (n-1)%b+1,
    'touched': sorted({j//b for j in [i]+children})}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 11, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 4, 'tail_occupancy': 2, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 12, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 4, 'tail_occupancy': 3, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 13, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 5, 'tail_occupancy': 1, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 14, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 5, 'tail_occupancy': 2, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 15, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 5, 'tail_occupancy': 3, 'touched': [1, 3]})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

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

N = 1
observations = []
def solve(d):
    n=d['size']; b=d['page_size']; i=d['index']; children=[j for j in (2*i+1,2*i+2) if j<n]
    def address(j): return [j//b,j%b]
    return {'address': address(i),
    'parent': None if i==0 else [i//b,(i%b-1)//2],
    'children': [address(j) for j in children],
    'pages': (n+b-1)//b,
    'tail_occupancy': (n-1)%b+1,
    'touched': sorted({j//b for j in [i]+children})}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 11, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 4, 'tail_occupancy': 2, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 12, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 4, 'tail_occupancy': 3, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 13, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 5, 'tail_occupancy': 1, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 14, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 5, 'tail_occupancy': 2, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 15, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 5, 'tail_occupancy': 3, 'touched': [1, 3]})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
The bounded paged heap layout certificate reports an incorrect parent.

A binary heap is stored in fixed-size pages of B slots using zero-based global indices. For n logical members and selected live index i report its page/offset, parent address or None, child addresses, allocated page count, last-page live occupancy, and pages touched by reading i and its existing children. B>=1 and 0<=i<n.

split: open-access


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

N = 1
observations = []
def solve(d):
    n=d['size']; b=d['page_size']; i=d['index']; children=[j for j in (2*i+1,2*i+2) if j<n]
    def address(j): return [j//b,j%b]
    return {'address': address(i),
    'parent': None if i==0 else address((i-1)//2),
    'children': [[i//b,2*(i%b)+k] for k in (1,2) if 2*i+k<n],
    'pages': (n+b-1)//b,
    'tail_occupancy': (n-1)%b+1,
    'touched': sorted({j//b for j in [i]+children})}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 11, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 4, 'tail_occupancy': 2, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 12, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 4, 'tail_occupancy': 3, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 13, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 5, 'tail_occupancy': 1, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 14, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 5, 'tail_occupancy': 2, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 15, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 5, 'tail_occupancy': 3, 'touched': [1, 3]})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

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

N = 1
observations = []
def solve(d):
    n=d['size']; b=d['page_size']; i=d['index']; children=[j for j in (2*i+1,2*i+2) if j<n]
    def address(j): return [j//b,j%b]
    return {'address': address(i),
    'parent': None if i==0 else address((i-1)//2),
    'children': [address(2*i)] if 2*i<n else [],
    'pages': (n+b-1)//b,
    'tail_occupancy': (n-1)%b+1,
    'touched': sorted({j//b for j in [i]+children})}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 11, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 4, 'tail_occupancy': 2, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 12, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 4, 'tail_occupancy': 3, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 13, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 5, 'tail_occupancy': 1, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 14, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 5, 'tail_occupancy': 2, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 15, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 5, 'tail_occupancy': 3, 'touched': [1, 3]})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
The bounded paged heap layout certificate reports an incorrect children.

A binary heap is stored in fixed-size pages of B slots using zero-based global indices. For n logical members and selected live index i report its page/offset, parent address or None, child addresses, allocated page count, last-page live occupancy, and pages touched by reading i and its existing children. B>=1 and 0<=i<n.

split: open-access


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

N = 1
observations = []
def solve(d):
    n=d['size']; b=d['page_size']; i=d['index']; children=[j for j in (2*i+1,2*i+2) if j<n]
    def address(j): return [j//b,j%b]
    return {'address': address(i),
    'parent': None if i==0 else address((i-1)//2),
    'children': [address(j) for j in children],
    'pages': n//b,
    'tail_occupancy': (n-1)%b+1,
    'touched': sorted({j//b for j in [i]+children})}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 11, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 4, 'tail_occupancy': 2, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 12, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 4, 'tail_occupancy': 3, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 13, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 5, 'tail_occupancy': 1, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 14, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 5, 'tail_occupancy': 2, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 15, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 5, 'tail_occupancy': 3, 'touched': [1, 3]})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

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

N = 1
observations = []
def solve(d):
    n=d['size']; b=d['page_size']; i=d['index']; children=[j for j in (2*i+1,2*i+2) if j<n]
    def address(j): return [j//b,j%b]
    return {'address': address(i),
    'parent': None if i==0 else address((i-1)//2),
    'children': [address(j) for j in children],
    'pages': n//b+1,
    'tail_occupancy': (n-1)%b+1,
    'touched': sorted({j//b for j in [i]+children})}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 11, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 4, 'tail_occupancy': 2, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 12, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 4, 'tail_occupancy': 3, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 13, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 5, 'tail_occupancy': 1, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 14, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 5, 'tail_occupancy': 2, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 15, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 5, 'tail_occupancy': 3, 'touched': [1, 3]})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
The bounded paged heap layout certificate reports an incorrect pages.

A binary heap is stored in fixed-size pages of B slots using zero-based global indices. For n logical members and selected live index i report its page/offset, parent address or None, child addresses, allocated page count, last-page live occupancy, and pages touched by reading i and its existing children. B>=1 and 0<=i<n.

split: open-access