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

N = 1
observations = []
def solve(d):
    path=d['path']; siblings=d['siblings']; old=d['old_generation']; new=d['new_generation']; copies=[[x,new] for x in path]
    return {'allocations': [[path[-1],new]] if path else [],
    'edges': [[[path[i],new],[path[i+1],new]] for i in range(len(path)-1)],
    'shared': [[x,old] for x in siblings],
    'old_refs': [[x,old] for x in path],
    'root': [path[0],new] if path else None,
    'target': [path[-1],new] if path else None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 10}, {'allocations': [[5, 10], [3, 10], [100, 10]], 'edges': [[[5, 10], [3, 10]], [[3, 10], [100, 10]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2]], 'root': [5, 10], 'target': [100, 10]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 11}, {'allocations': [[5, 11], [3, 11], [100, 11], [101, 11]], 'edges': [[[5, 11], [3, 11]], [[3, 11], [100, 11]], [[100, 11], [101, 11]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2]], 'root': [5, 11], 'target': [101, 11]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101, 102], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 12}, {'allocations': [[5, 12], [3, 12], [100, 12], [101, 12], [102, 12]], 'edges': [[[5, 12], [3, 12]], [[3, 12], [100, 12]], [[100, 12], [101, 12]], [[101, 12], [102, 12]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2], [102, 2]], 'root': [5, 12], 'target': [102, 12]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101, 102, 103], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 13}, {'allocations': [[5, 13], [3, 13], [100, 13], [101, 13], [102, 13], [103, 13]], 'edges': [[[5, 13], [3, 13]], [[3, 13], [100, 13]], [[100, 13], [101, 13]], [[101, 13], [102, 13]], [[102, 13], [103, 13]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2], [102, 2], [103, 2]], 'root': [5, 13], 'target': [103, 13]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101, 102, 103, 104], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 14}, {'allocations': [[5, 14], [3, 14], [100, 14], [101, 14], [102, 14], [103, 14], [104, 14]], 'edges': [[[5, 14], [3, 14]], [[3, 14], [100, 14]], [[100, 14], [101, 14]], [[101, 14], [102, 14]], [[102, 14], [103, 14]], [[103, 14], [104, 14]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2], [102, 2], [103, 2], [104, 2]], 'root': [5, 14], 'target': [104, 14]})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

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

N = 1
observations = []
def solve(d):
    path=d['path']; siblings=d['siblings']; old=d['old_generation']; new=d['new_generation']; copies=[[x,new] for x in path]
    return {'allocations': [[x,new] for x in path+siblings],
    'edges': [[[path[i],new],[path[i+1],new]] for i in range(len(path)-1)],
    'shared': [[x,old] for x in siblings],
    'old_refs': [[x,old] for x in path],
    'root': [path[0],new] if path else None,
    'target': [path[-1],new] if path else None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 10}, {'allocations': [[5, 10], [3, 10], [100, 10]], 'edges': [[[5, 10], [3, 10]], [[3, 10], [100, 10]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2]], 'root': [5, 10], 'target': [100, 10]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 11}, {'allocations': [[5, 11], [3, 11], [100, 11], [101, 11]], 'edges': [[[5, 11], [3, 11]], [[3, 11], [100, 11]], [[100, 11], [101, 11]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2]], 'root': [5, 11], 'target': [101, 11]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101, 102], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 12}, {'allocations': [[5, 12], [3, 12], [100, 12], [101, 12], [102, 12]], 'edges': [[[5, 12], [3, 12]], [[3, 12], [100, 12]], [[100, 12], [101, 12]], [[101, 12], [102, 12]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2], [102, 2]], 'root': [5, 12], 'target': [102, 12]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101, 102, 103], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 13}, {'allocations': [[5, 13], [3, 13], [100, 13], [101, 13], [102, 13], [103, 13]], 'edges': [[[5, 13], [3, 13]], [[3, 13], [100, 13]], [[100, 13], [101, 13]], [[101, 13], [102, 13]], [[102, 13], [103, 13]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2], [102, 2], [103, 2]], 'root': [5, 13], 'target': [103, 13]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101, 102, 103, 104], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 14}, {'allocations': [[5, 14], [3, 14], [100, 14], [101, 14], [102, 14], [103, 14], [104, 14]], 'edges': [[[5, 14], [3, 14]], [[3, 14], [100, 14]], [[100, 14], [101, 14]], [[101, 14], [102, 14]], [[102, 14], [103, 14]], [[103, 14], [104, 14]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2], [102, 2], [103, 2], [104, 2]], 'root': [5, 14], 'target': [104, 14]})]][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 path copy certificate reports an incorrect allocations.

A persistent array-backed heap update supplies a root-to-target node-id path, off-path sibling ids, old node generations, and a new generation. Allocate one copy per path node, reconnect copied edges, share every sibling, and preserve old node references. Report allocated pairs, copied edges, shared ids, old generation list, new root reference, and target reference.

split: open-access


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

N = 1
observations = []
def solve(d):
    path=d['path']; siblings=d['siblings']; old=d['old_generation']; new=d['new_generation']; copies=[[x,new] for x in path]
    return {'allocations': copies,
    'edges': [[[path[i],new],[path[i+1],old]] for i in range(len(path)-1)],
    'shared': [[x,old] for x in siblings],
    'old_refs': [[x,old] for x in path],
    'root': [path[0],new] if path else None,
    'target': [path[-1],new] if path else None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 10}, {'allocations': [[5, 10], [3, 10], [100, 10]], 'edges': [[[5, 10], [3, 10]], [[3, 10], [100, 10]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2]], 'root': [5, 10], 'target': [100, 10]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 11}, {'allocations': [[5, 11], [3, 11], [100, 11], [101, 11]], 'edges': [[[5, 11], [3, 11]], [[3, 11], [100, 11]], [[100, 11], [101, 11]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2]], 'root': [5, 11], 'target': [101, 11]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101, 102], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 12}, {'allocations': [[5, 12], [3, 12], [100, 12], [101, 12], [102, 12]], 'edges': [[[5, 12], [3, 12]], [[3, 12], [100, 12]], [[100, 12], [101, 12]], [[101, 12], [102, 12]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2], [102, 2]], 'root': [5, 12], 'target': [102, 12]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101, 102, 103], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 13}, {'allocations': [[5, 13], [3, 13], [100, 13], [101, 13], [102, 13], [103, 13]], 'edges': [[[5, 13], [3, 13]], [[3, 13], [100, 13]], [[100, 13], [101, 13]], [[101, 13], [102, 13]], [[102, 13], [103, 13]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2], [102, 2], [103, 2]], 'root': [5, 13], 'target': [103, 13]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101, 102, 103, 104], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 14}, {'allocations': [[5, 14], [3, 14], [100, 14], [101, 14], [102, 14], [103, 14], [104, 14]], 'edges': [[[5, 14], [3, 14]], [[3, 14], [100, 14]], [[100, 14], [101, 14]], [[101, 14], [102, 14]], [[102, 14], [103, 14]], [[103, 14], [104, 14]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2], [102, 2], [103, 2], [104, 2]], 'root': [5, 14], 'target': [104, 14]})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

meaning: Fixture-count band, not measured model difficulty

deps: stdlib

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

N = 1
observations = []
def solve(d):
    path=d['path']; siblings=d['siblings']; old=d['old_generation']; new=d['new_generation']; copies=[[x,new] for x in path]
    return {'allocations': copies,
    'edges': [[[path[i],old],[path[i+1],new]] for i in range(len(path)-1)],
    'shared': [[x,old] for x in siblings],
    'old_refs': [[x,old] for x in path],
    'root': [path[0],new] if path else None,
    'target': [path[-1],new] if path else None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 10}, {'allocations': [[5, 10], [3, 10], [100, 10]], 'edges': [[[5, 10], [3, 10]], [[3, 10], [100, 10]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2]], 'root': [5, 10], 'target': [100, 10]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 11}, {'allocations': [[5, 11], [3, 11], [100, 11], [101, 11]], 'edges': [[[5, 11], [3, 11]], [[3, 11], [100, 11]], [[100, 11], [101, 11]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2]], 'root': [5, 11], 'target': [101, 11]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101, 102], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 12}, {'allocations': [[5, 12], [3, 12], [100, 12], [101, 12], [102, 12]], 'edges': [[[5, 12], [3, 12]], [[3, 12], [100, 12]], [[100, 12], [101, 12]], [[101, 12], [102, 12]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2], [102, 2]], 'root': [5, 12], 'target': [102, 12]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101, 102, 103], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 13}, {'allocations': [[5, 13], [3, 13], [100, 13], [101, 13], [102, 13], [103, 13]], 'edges': [[[5, 13], [3, 13]], [[3, 13], [100, 13]], [[100, 13], [101, 13]], [[101, 13], [102, 13]], [[102, 13], [103, 13]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2], [102, 2], [103, 2]], 'root': [5, 13], 'target': [103, 13]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101, 102, 103, 104], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 14}, {'allocations': [[5, 14], [3, 14], [100, 14], [101, 14], [102, 14], [103, 14], [104, 14]], 'edges': [[[5, 14], [3, 14]], [[3, 14], [100, 14]], [[100, 14], [101, 14]], [[101, 14], [102, 14]], [[102, 14], [103, 14]], [[103, 14], [104, 14]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2], [102, 2], [103, 2], [104, 2]], 'root': [5, 14], 'target': [104, 14]})]][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 path copy certificate reports an incorrect edges.

A persistent array-backed heap update supplies a root-to-target node-id path, off-path sibling ids, old node generations, and a new generation. Allocate one copy per path node, reconnect copied edges, share every sibling, and preserve old node references. Report allocated pairs, copied edges, shared ids, old generation list, new root reference, and target reference.

split: open-access


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

N = 1
observations = []
def solve(d):
    path=d['path']; siblings=d['siblings']; old=d['old_generation']; new=d['new_generation']; copies=[[x,new] for x in path]
    return {'allocations': copies,
    'edges': [[[path[i],new],[path[i+1],new]] for i in range(len(path)-1)],
    'shared': [[x,new] for x in siblings],
    'old_refs': [[x,old] for x in path],
    'root': [path[0],new] if path else None,
    'target': [path[-1],new] if path else None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 10}, {'allocations': [[5, 10], [3, 10], [100, 10]], 'edges': [[[5, 10], [3, 10]], [[3, 10], [100, 10]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2]], 'root': [5, 10], 'target': [100, 10]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 11}, {'allocations': [[5, 11], [3, 11], [100, 11], [101, 11]], 'edges': [[[5, 11], [3, 11]], [[3, 11], [100, 11]], [[100, 11], [101, 11]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2]], 'root': [5, 11], 'target': [101, 11]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101, 102], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 12}, {'allocations': [[5, 12], [3, 12], [100, 12], [101, 12], [102, 12]], 'edges': [[[5, 12], [3, 12]], [[3, 12], [100, 12]], [[100, 12], [101, 12]], [[101, 12], [102, 12]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2], [102, 2]], 'root': [5, 12], 'target': [102, 12]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101, 102, 103], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 13}, {'allocations': [[5, 13], [3, 13], [100, 13], [101, 13], [102, 13], [103, 13]], 'edges': [[[5, 13], [3, 13]], [[3, 13], [100, 13]], [[100, 13], [101, 13]], [[101, 13], [102, 13]], [[102, 13], [103, 13]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2], [102, 2], [103, 2]], 'root': [5, 13], 'target': [103, 13]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101, 102, 103, 104], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 14}, {'allocations': [[5, 14], [3, 14], [100, 14], [101, 14], [102, 14], [103, 14], [104, 14]], 'edges': [[[5, 14], [3, 14]], [[3, 14], [100, 14]], [[100, 14], [101, 14]], [[101, 14], [102, 14]], [[102, 14], [103, 14]], [[103, 14], [104, 14]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2], [102, 2], [103, 2], [104, 2]], 'root': [5, 14], 'target': [104, 14]})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

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

N = 1
observations = []
def solve(d):
    path=d['path']; siblings=d['siblings']; old=d['old_generation']; new=d['new_generation']; copies=[[x,new] for x in path]
    return {'allocations': copies,
    'edges': [[[path[i],new],[path[i+1],new]] for i in range(len(path)-1)],
    'shared': [],
    'old_refs': [[x,old] for x in path],
    'root': [path[0],new] if path else None,
    'target': [path[-1],new] if path else None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 10}, {'allocations': [[5, 10], [3, 10], [100, 10]], 'edges': [[[5, 10], [3, 10]], [[3, 10], [100, 10]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2]], 'root': [5, 10], 'target': [100, 10]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 11}, {'allocations': [[5, 11], [3, 11], [100, 11], [101, 11]], 'edges': [[[5, 11], [3, 11]], [[3, 11], [100, 11]], [[100, 11], [101, 11]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2]], 'root': [5, 11], 'target': [101, 11]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101, 102], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 12}, {'allocations': [[5, 12], [3, 12], [100, 12], [101, 12], [102, 12]], 'edges': [[[5, 12], [3, 12]], [[3, 12], [100, 12]], [[100, 12], [101, 12]], [[101, 12], [102, 12]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2], [102, 2]], 'root': [5, 12], 'target': [102, 12]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101, 102, 103], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 13}, {'allocations': [[5, 13], [3, 13], [100, 13], [101, 13], [102, 13], [103, 13]], 'edges': [[[5, 13], [3, 13]], [[3, 13], [100, 13]], [[100, 13], [101, 13]], [[101, 13], [102, 13]], [[102, 13], [103, 13]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2], [102, 2], [103, 2]], 'root': [5, 13], 'target': [103, 13]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101, 102, 103, 104], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 14}, {'allocations': [[5, 14], [3, 14], [100, 14], [101, 14], [102, 14], [103, 14], [104, 14]], 'edges': [[[5, 14], [3, 14]], [[3, 14], [100, 14]], [[100, 14], [101, 14]], [[101, 14], [102, 14]], [[102, 14], [103, 14]], [[103, 14], [104, 14]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2], [102, 2], [103, 2], [104, 2]], 'root': [5, 14], 'target': [104, 14]})]][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 path copy certificate reports an incorrect shared.

A persistent array-backed heap update supplies a root-to-target node-id path, off-path sibling ids, old node generations, and a new generation. Allocate one copy per path node, reconnect copied edges, share every sibling, and preserve old node references. Report allocated pairs, copied edges, shared ids, old generation list, new root reference, and target reference.

split: open-access


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

N = 1
observations = []
def solve(d):
    path=d['path']; siblings=d['siblings']; old=d['old_generation']; new=d['new_generation']; copies=[[x,new] for x in path]
    return {'allocations': copies,
    'edges': [[[path[i],new],[path[i+1],new]] for i in range(len(path)-1)],
    'shared': [[x,old] for x in siblings],
    'old_refs': [[x,new] for x in path],
    'root': [path[0],new] if path else None,
    'target': [path[-1],new] if path else None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 10}, {'allocations': [[5, 10], [3, 10], [100, 10]], 'edges': [[[5, 10], [3, 10]], [[3, 10], [100, 10]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2]], 'root': [5, 10], 'target': [100, 10]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 11}, {'allocations': [[5, 11], [3, 11], [100, 11], [101, 11]], 'edges': [[[5, 11], [3, 11]], [[3, 11], [100, 11]], [[100, 11], [101, 11]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2]], 'root': [5, 11], 'target': [101, 11]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101, 102], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 12}, {'allocations': [[5, 12], [3, 12], [100, 12], [101, 12], [102, 12]], 'edges': [[[5, 12], [3, 12]], [[3, 12], [100, 12]], [[100, 12], [101, 12]], [[101, 12], [102, 12]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2], [102, 2]], 'root': [5, 12], 'target': [102, 12]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101, 102, 103], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 13}, {'allocations': [[5, 13], [3, 13], [100, 13], [101, 13], [102, 13], [103, 13]], 'edges': [[[5, 13], [3, 13]], [[3, 13], [100, 13]], [[100, 13], [101, 13]], [[101, 13], [102, 13]], [[102, 13], [103, 13]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2], [102, 2], [103, 2]], 'root': [5, 13], 'target': [103, 13]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101, 102, 103, 104], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 14}, {'allocations': [[5, 14], [3, 14], [100, 14], [101, 14], [102, 14], [103, 14], [104, 14]], 'edges': [[[5, 14], [3, 14]], [[3, 14], [100, 14]], [[100, 14], [101, 14]], [[101, 14], [102, 14]], [[102, 14], [103, 14]], [[103, 14], [104, 14]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2], [102, 2], [103, 2], [104, 2]], 'root': [5, 14], 'target': [104, 14]})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

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

N = 1
observations = []
def solve(d):
    path=d['path']; siblings=d['siblings']; old=d['old_generation']; new=d['new_generation']; copies=[[x,new] for x in path]
    return {'allocations': copies,
    'edges': [[[path[i],new],[path[i+1],new]] for i in range(len(path)-1)],
    'shared': [[x,old] for x in siblings],
    'old_refs': [[x,old] for x in path[:-1]],
    'root': [path[0],new] if path else None,
    'target': [path[-1],new] if path else None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 10}, {'allocations': [[5, 10], [3, 10], [100, 10]], 'edges': [[[5, 10], [3, 10]], [[3, 10], [100, 10]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2]], 'root': [5, 10], 'target': [100, 10]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 11}, {'allocations': [[5, 11], [3, 11], [100, 11], [101, 11]], 'edges': [[[5, 11], [3, 11]], [[3, 11], [100, 11]], [[100, 11], [101, 11]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2]], 'root': [5, 11], 'target': [101, 11]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101, 102], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 12}, {'allocations': [[5, 12], [3, 12], [100, 12], [101, 12], [102, 12]], 'edges': [[[5, 12], [3, 12]], [[3, 12], [100, 12]], [[100, 12], [101, 12]], [[101, 12], [102, 12]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2], [102, 2]], 'root': [5, 12], 'target': [102, 12]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101, 102, 103], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 13}, {'allocations': [[5, 13], [3, 13], [100, 13], [101, 13], [102, 13], [103, 13]], 'edges': [[[5, 13], [3, 13]], [[3, 13], [100, 13]], [[100, 13], [101, 13]], [[101, 13], [102, 13]], [[102, 13], [103, 13]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2], [102, 2], [103, 2]], 'root': [5, 13], 'target': [103, 13]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101, 102, 103, 104], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 14}, {'allocations': [[5, 14], [3, 14], [100, 14], [101, 14], [102, 14], [103, 14], [104, 14]], 'edges': [[[5, 14], [3, 14]], [[3, 14], [100, 14]], [[100, 14], [101, 14]], [[101, 14], [102, 14]], [[102, 14], [103, 14]], [[103, 14], [104, 14]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2], [102, 2], [103, 2], [104, 2]], 'root': [5, 14], 'target': [104, 14]})]][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 path copy certificate reports an incorrect old refs.

A persistent array-backed heap update supplies a root-to-target node-id path, off-path sibling ids, old node generations, and a new generation. Allocate one copy per path node, reconnect copied edges, share every sibling, and preserve old node references. Report allocated pairs, copied edges, shared ids, old generation list, new root reference, and target reference.

split: open-access