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

N = 1
observations = []
def solve(d):
    runs=d['runs']; offsets=d['offsets']; r=d['pop_run']; out=list(offsets); value=runs[r][out[r]]; out[r]+=1; heads=sorted([[runs[i][k],i] for i,k in enumerate(out) if k<len(runs[i])])
    return {'emitted': value,
    'offsets': out,
    'heads': heads,
    'exhausted': [i for i,k in enumerate(out) if k==len(runs[i])],
    'remaining': sum(len(x)-k for x,k in zip(runs,out)),
    'next_run': r if out[r]<len(runs[r]) else None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 4], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 4, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 5], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 5, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 6], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 6, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 7], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 7, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 8], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 8, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})]][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):
    runs=d['runs']; offsets=d['offsets']; r=d['pop_run']; out=list(offsets); value=runs[r][out[r]]; out[r]+=1; heads=sorted([[runs[i][k],i] for i,k in enumerate(out) if k<len(runs[i])])
    return {'emitted': value,
    'offsets': out,
    'heads': heads,
    'exhausted': [i for i,k in enumerate(out) if k==len(runs[i])],
    'remaining': sum(len(x)-k for x,k in zip(runs,out)),
    'next_run': heads[0][0] if heads else None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 4], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 4, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 5], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 5, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 6], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 6, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 7], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 7, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 8], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 8, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})]][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 run frontier certificate reports an incorrect next run.

A k-way heap merge frontier stores one cursor per sorted run. A frontier item identifies run r and its current offset. Pop run r current item, advance only its offset, omit exhausted runs, and report next head candidates sorted by (value,run). Return emitted value, cursor vector, heads, exhausted runs, remaining item count, and next run.

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': v,
    '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': 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)

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': v+[terminal] if terminal is not None else v,
    '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': 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 alloc order.

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,g],
    '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': 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,
    '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': 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 terminal.

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],terminal] for i in range(len(v))],
    'root': v[0] if v else terminal,
    'allocation_count': len(v),
    '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 else terminal] for i in range(len(v))],
    'root': v[0] if v else terminal,
    'allocation_count': len(v),
    '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 links.

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[-1] if v else terminal,
    'allocation_count': len(v),
    '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': None if not v else v[0],
    'allocation_count': len(v),
    '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 root.

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