FA-40406 / Heap invariants / Open access
Min-max complete-tree level alternation includes both zero-based child positions · case 01
The bounded minmax levels certificate reports an incorrect edges.
ROOT CAUSE
Min-max complete-tree level alternation includes both zero-based child positions.
VERIFIED REPAIR
Derive edges using [[i,j] for i in range(n) for j in (2*i+1,2*i+2) if j<n] under the stated bounded certificate contract.
Unsuccessful approach: The local patch uses [[i,2*i+1] for i in range(n) if 2*i+1<n] and still violates the stated relation.
Case contract
A min-max heap certificate is a complete zero-based binary array. Even depth is a minimum level, odd depth a maximum level. Report level parities, grandparent indices, minimum-level grandchild violations, maximum-level grandchild violations, maximum endpoint, and immediate-child level alternation pairs. Empty maximum is None.
Why this case matters
This isolates an internal heap representation or priority-structure invariant using deterministic finite records.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(d):
a=d['keys']; n=len(a)
def depth(i): return (i+1).bit_length()-1
def grandchildren(i): return [j for j in range(4*i+3,4*i+7) if j<n]
return {'parity': [depth(i)%2 for i in range(n)],
'grandparents': [None if i<3 else (i-3)//4 for i in range(n)],
'min_violations': [[i,j] for i in range(n) if depth(i)%2==0 for j in grandchildren(i) if a[j]<a[i]],
'max_violations': [[i,j] for i in range(n) if depth(i)%2==1 for j in grandchildren(i) if a[j]>a[i]],
'maximum': None if not a else max(a[1:3] or a),
'edges': [[i,j] for i in range(n) for j in (2*i,2*i+1) if j<n]}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'keys': []}, {'parity': [], 'grandparents': [], 'min_violations': [], 'max_violations': [], 'maximum': None, 'edges': []}), ({'keys': [4]}, {'parity': [0], 'grandparents': [None], 'min_violations': [], 'max_violations': [], 'maximum': 4, 'edges': []}), ({'keys': [1, 8, 9]}, {'parity': [0, 1, 1], 'grandparents': [None, None, None], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2]]}), ({'keys': [2, 9, 8, 3, 2, 4, 7]}, {'parity': [0, 1, 1, 0, 0, 0, 0], 'grandparents': [None, None, None, 0, 0, 0, 0], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]]}), ({'keys': [5, 4, 9, 1, 8, 2, 6, 10, 3, 8, 7, 6, 5, 4, 3]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [[0, 3], [0, 5]], 'max_violations': [[1, 7], [1, 9], [1, 10]], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 7, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [[1, 10]], 'maximum': 8, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 8, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [[1, 10]], 'maximum': 8, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]})], [({'keys': []}, {'parity': [], 'grandparents': [], 'min_violations': [], 'max_violations': [], 'maximum': None, 'edges': []}), ({'keys': [4]}, {'parity': [0], 'grandparents': [None], 'min_violations': [], 'max_violations': [], 'maximum': 4, 'edges': []}), ({'keys': [1, 8, 9]}, {'parity': [0, 1, 1], 'grandparents': [None, None, None], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2]]}), ({'keys': [2, 9, 8, 3, 2, 4, 7]}, {'parity': [0, 1, 1, 0, 0, 0, 0], 'grandparents': [None, None, None, 0, 0, 0, 0], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]]}), ({'keys': [5, 4, 9, 1, 8, 2, 6, 10, 3, 8, 7, 6, 5, 4, 3]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [[0, 3], [0, 5]], 'max_violations': [[1, 7], [1, 9], [1, 10]], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 7, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [[1, 10]], 'maximum': 8, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 9, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]})], [({'keys': []}, {'parity': [], 'grandparents': [], 'min_violations': [], 'max_violations': [], 'maximum': None, 'edges': []}), ({'keys': [4]}, {'parity': [0], 'grandparents': [None], 'min_violations': [], 'max_violations': [], 'maximum': 4, 'edges': []}), ({'keys': [1, 8, 9]}, {'parity': [0, 1, 1], 'grandparents': [None, None, None], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2]]}), ({'keys': [2, 9, 8, 3, 2, 4, 7]}, {'parity': [0, 1, 1, 0, 0, 0, 0], 'grandparents': [None, None, None, 0, 0, 0, 0], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]]}), ({'keys': [5, 4, 9, 1, 8, 2, 6, 10, 3, 8, 7, 6, 5, 4, 3]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [[0, 3], [0, 5]], 'max_violations': [[1, 7], [1, 9], [1, 10]], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 7, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [[1, 10]], 'maximum': 8, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 10, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [], 'maximum': 10, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]})], [({'keys': []}, {'parity': [], 'grandparents': [], 'min_violations': [], 'max_violations': [], 'maximum': None, 'edges': []}), ({'keys': [4]}, {'parity': [0], 'grandparents': [None], 'min_violations': [], 'max_violations': [], 'maximum': 4, 'edges': []}), ({'keys': [1, 8, 9]}, {'parity': [0, 1, 1], 'grandparents': [None, None, None], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2]]}), ({'keys': [2, 9, 8, 3, 2, 4, 7]}, {'parity': [0, 1, 1, 0, 0, 0, 0], 'grandparents': [None, None, None, 0, 0, 0, 0], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]]}), ({'keys': [5, 4, 9, 1, 8, 2, 6, 10, 3, 8, 7, 6, 5, 4, 3]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [[0, 3], [0, 5]], 'max_violations': [[1, 7], [1, 9], [1, 10]], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 7, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [[1, 10]], 'maximum': 8, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 11, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [], 'maximum': 11, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]})], [({'keys': []}, {'parity': [], 'grandparents': [], 'min_violations': [], 'max_violations': [], 'maximum': None, 'edges': []}), ({'keys': [4]}, {'parity': [0], 'grandparents': [None], 'min_violations': [], 'max_violations': [], 'maximum': 4, 'edges': []}), ({'keys': [1, 8, 9]}, {'parity': [0, 1, 1], 'grandparents': [None, None, None], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2]]}), ({'keys': [2, 9, 8, 3, 2, 4, 7]}, {'parity': [0, 1, 1, 0, 0, 0, 0], 'grandparents': [None, None, None, 0, 0, 0, 0], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]]}), ({'keys': [5, 4, 9, 1, 8, 2, 6, 10, 3, 8, 7, 6, 5, 4, 3]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [[0, 3], [0, 5]], 'max_violations': [[1, 7], [1, 9], [1, 10]], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 7, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [[1, 10]], 'maximum': 8, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 12, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [], 'maximum': 12, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 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)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| regression certificate 1 | {'edges': [], 'grandparents': [], 'max_violations': [], 'maximum': None, 'min_violations': [], 'parity': []} | {'edges': [], 'grandparents': [], 'max_violations': [], 'maximum': None, 'min_violations': [], 'parity': []} | Passed |
| regression certificate 2 | {'edges': [[0, 0]], 'grandparents': [None], 'max_violations': [], 'maximum': 4, 'min_violations': [], 'parity': [0]} | {'edges': [], 'grandparents': [None], 'max_violations': [], 'maximum': 4, 'min_violations': [], 'parity': [0]} | Failed |
| regression certificate 3 | {'edges': [[0, 0], [0, 1], [1, 2]], 'grandparents': [None, None, None], 'max_violations': [], 'maximum': 9, 'min_violations': [], 'parity': [0, 1, 1]} | {'edges': [[0, 1], [0, 2]], 'grandparents': [None, None, None], 'max_violations': [], 'maximum': 9, 'min_violations': [], 'parity': [0, 1, 1]} | Failed |
| regression certificate 4 | {'edges': [[0, 0], [0, 1], [1, 2], [1, 3], [2, 4], [2, 5], [3, 6]], 'grandparents': [None, None, None, 0, 0, 0, 0], 'max_violations': [], 'maximum': 9, 'min_violations': [], 'parity': [0, 1, 1, 0, 0, 0, 0]} | {'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]], 'grandparents': [None, None, None, 0, 0, 0, 0], 'max_violations': [], 'maximum': 9, 'min_violations': [], 'parity': [0, 1, 1, 0, 0, 0, 0]} | Failed |
| regression certificate 5 | {'edges': [[0, 0], [0, 1], [1, 2], [1, 3], [2, 4], [2, 5], [3, 6], [3, 7], [4, 8], [4, 9], [5, 10], [5, 11], [6, 12], [6, 13], [7, 14]], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'max_violations': [[1, 7], [1, 9], [1, 10]], 'maximum': 9, 'min_violations': [[0, 3], [0, 5]], 'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]} | {'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'max_violations': [[1, 7], [1, 9], [1, 10]], 'maximum': 9, 'min_violations': [[0, 3], [0, 5]], 'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]} | Failed |
| regression certificate 6 | {'edges': [[0, 0], [0, 1], [1, 2], [1, 3], [2, 4], [2, 5], [3, 6], [3, 7], [4, 8], [4, 9], [5, 10], [5, 11], [6, 12], [6, 13], [7, 14]], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'max_violations': [[1, 10]], 'maximum': 8, 'min_violations': [], 'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]} | {'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'max_violations': [[1, 10]], 'maximum': 8, 'min_violations': [], 'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]} | Failed |
| variant-dependent certificate | {'edges': [[0, 0], [0, 1], [1, 2], [1, 3], [2, 4], [2, 5], [3, 6], [3, 7], [4, 8], [4, 9], [5, 10], [5, 11], [6, 12], [6, 13], [7, 14]], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'max_violations': [[1, 10]], 'maximum': 8, 'min_violations': [], 'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]} | {'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'max_violations': [[1, 10]], 'maximum': 8, 'min_violations': [], 'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]} | Failed |
SHA-256 / af78700f484bee0f3b8a5e039bff7ccf808388844e9578eb0b1eb93632e9376a
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(d):
a=d['keys']; n=len(a)
def depth(i): return (i+1).bit_length()-1
def grandchildren(i): return [j for j in range(4*i+3,4*i+7) if j<n]
return {'parity': [depth(i)%2 for i in range(n)],
'grandparents': [None if i<3 else (i-3)//4 for i in range(n)],
'min_violations': [[i,j] for i in range(n) if depth(i)%2==0 for j in grandchildren(i) if a[j]<a[i]],
'max_violations': [[i,j] for i in range(n) if depth(i)%2==1 for j in grandchildren(i) if a[j]>a[i]],
'maximum': None if not a else max(a[1:3] or a),
'edges': [[i,2*i+1] for i in range(n) if 2*i+1<n]}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'keys': []}, {'parity': [], 'grandparents': [], 'min_violations': [], 'max_violations': [], 'maximum': None, 'edges': []}), ({'keys': [4]}, {'parity': [0], 'grandparents': [None], 'min_violations': [], 'max_violations': [], 'maximum': 4, 'edges': []}), ({'keys': [1, 8, 9]}, {'parity': [0, 1, 1], 'grandparents': [None, None, None], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2]]}), ({'keys': [2, 9, 8, 3, 2, 4, 7]}, {'parity': [0, 1, 1, 0, 0, 0, 0], 'grandparents': [None, None, None, 0, 0, 0, 0], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]]}), ({'keys': [5, 4, 9, 1, 8, 2, 6, 10, 3, 8, 7, 6, 5, 4, 3]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [[0, 3], [0, 5]], 'max_violations': [[1, 7], [1, 9], [1, 10]], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 7, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [[1, 10]], 'maximum': 8, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 8, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [[1, 10]], 'maximum': 8, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]})], [({'keys': []}, {'parity': [], 'grandparents': [], 'min_violations': [], 'max_violations': [], 'maximum': None, 'edges': []}), ({'keys': [4]}, {'parity': [0], 'grandparents': [None], 'min_violations': [], 'max_violations': [], 'maximum': 4, 'edges': []}), ({'keys': [1, 8, 9]}, {'parity': [0, 1, 1], 'grandparents': [None, None, None], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2]]}), ({'keys': [2, 9, 8, 3, 2, 4, 7]}, {'parity': [0, 1, 1, 0, 0, 0, 0], 'grandparents': [None, None, None, 0, 0, 0, 0], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]]}), ({'keys': [5, 4, 9, 1, 8, 2, 6, 10, 3, 8, 7, 6, 5, 4, 3]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [[0, 3], [0, 5]], 'max_violations': [[1, 7], [1, 9], [1, 10]], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 7, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [[1, 10]], 'maximum': 8, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 9, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]})], [({'keys': []}, {'parity': [], 'grandparents': [], 'min_violations': [], 'max_violations': [], 'maximum': None, 'edges': []}), ({'keys': [4]}, {'parity': [0], 'grandparents': [None], 'min_violations': [], 'max_violations': [], 'maximum': 4, 'edges': []}), ({'keys': [1, 8, 9]}, {'parity': [0, 1, 1], 'grandparents': [None, None, None], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2]]}), ({'keys': [2, 9, 8, 3, 2, 4, 7]}, {'parity': [0, 1, 1, 0, 0, 0, 0], 'grandparents': [None, None, None, 0, 0, 0, 0], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]]}), ({'keys': [5, 4, 9, 1, 8, 2, 6, 10, 3, 8, 7, 6, 5, 4, 3]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [[0, 3], [0, 5]], 'max_violations': [[1, 7], [1, 9], [1, 10]], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 7, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [[1, 10]], 'maximum': 8, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 10, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [], 'maximum': 10, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]})], [({'keys': []}, {'parity': [], 'grandparents': [], 'min_violations': [], 'max_violations': [], 'maximum': None, 'edges': []}), ({'keys': [4]}, {'parity': [0], 'grandparents': [None], 'min_violations': [], 'max_violations': [], 'maximum': 4, 'edges': []}), ({'keys': [1, 8, 9]}, {'parity': [0, 1, 1], 'grandparents': [None, None, None], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2]]}), ({'keys': [2, 9, 8, 3, 2, 4, 7]}, {'parity': [0, 1, 1, 0, 0, 0, 0], 'grandparents': [None, None, None, 0, 0, 0, 0], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]]}), ({'keys': [5, 4, 9, 1, 8, 2, 6, 10, 3, 8, 7, 6, 5, 4, 3]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [[0, 3], [0, 5]], 'max_violations': [[1, 7], [1, 9], [1, 10]], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 7, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [[1, 10]], 'maximum': 8, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 11, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [], 'maximum': 11, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]})], [({'keys': []}, {'parity': [], 'grandparents': [], 'min_violations': [], 'max_violations': [], 'maximum': None, 'edges': []}), ({'keys': [4]}, {'parity': [0], 'grandparents': [None], 'min_violations': [], 'max_violations': [], 'maximum': 4, 'edges': []}), ({'keys': [1, 8, 9]}, {'parity': [0, 1, 1], 'grandparents': [None, None, None], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2]]}), ({'keys': [2, 9, 8, 3, 2, 4, 7]}, {'parity': [0, 1, 1, 0, 0, 0, 0], 'grandparents': [None, None, None, 0, 0, 0, 0], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]]}), ({'keys': [5, 4, 9, 1, 8, 2, 6, 10, 3, 8, 7, 6, 5, 4, 3]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [[0, 3], [0, 5]], 'max_violations': [[1, 7], [1, 9], [1, 10]], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 7, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [[1, 10]], 'maximum': 8, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 12, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [], 'maximum': 12, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 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)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| regression certificate 1 | {'edges': [], 'grandparents': [], 'max_violations': [], 'maximum': None, 'min_violations': [], 'parity': []} | {'edges': [], 'grandparents': [], 'max_violations': [], 'maximum': None, 'min_violations': [], 'parity': []} | Passed |
| regression certificate 2 | {'edges': [], 'grandparents': [None], 'max_violations': [], 'maximum': 4, 'min_violations': [], 'parity': [0]} | {'edges': [], 'grandparents': [None], 'max_violations': [], 'maximum': 4, 'min_violations': [], 'parity': [0]} | Passed |
| regression certificate 3 | {'edges': [[0, 1]], 'grandparents': [None, None, None], 'max_violations': [], 'maximum': 9, 'min_violations': [], 'parity': [0, 1, 1]} | {'edges': [[0, 1], [0, 2]], 'grandparents': [None, None, None], 'max_violations': [], 'maximum': 9, 'min_violations': [], 'parity': [0, 1, 1]} | Failed |
| regression certificate 4 | {'edges': [[0, 1], [1, 3], [2, 5]], 'grandparents': [None, None, None, 0, 0, 0, 0], 'max_violations': [], 'maximum': 9, 'min_violations': [], 'parity': [0, 1, 1, 0, 0, 0, 0]} | {'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]], 'grandparents': [None, None, None, 0, 0, 0, 0], 'max_violations': [], 'maximum': 9, 'min_violations': [], 'parity': [0, 1, 1, 0, 0, 0, 0]} | Failed |
| regression certificate 5 | {'edges': [[0, 1], [1, 3], [2, 5], [3, 7], [4, 9], [5, 11], [6, 13]], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'max_violations': [[1, 7], [1, 9], [1, 10]], 'maximum': 9, 'min_violations': [[0, 3], [0, 5]], 'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]} | {'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'max_violations': [[1, 7], [1, 9], [1, 10]], 'maximum': 9, 'min_violations': [[0, 3], [0, 5]], 'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]} | Failed |
| regression certificate 6 | {'edges': [[0, 1], [1, 3], [2, 5], [3, 7], [4, 9], [5, 11], [6, 13]], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'max_violations': [[1, 10]], 'maximum': 8, 'min_violations': [], 'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]} | {'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'max_violations': [[1, 10]], 'maximum': 8, 'min_violations': [], 'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]} | Failed |
| variant-dependent certificate | {'edges': [[0, 1], [1, 3], [2, 5], [3, 7], [4, 9], [5, 11], [6, 13]], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'max_violations': [[1, 10]], 'maximum': 8, 'min_violations': [], 'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]} | {'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'max_violations': [[1, 10]], 'maximum': 8, 'min_violations': [], 'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]} | Failed |
SHA-256 / 9ea78ffa0f74374031123a354c637de6cefc6f3e0d2f6c41f21716f1f046bce4
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(d):
a=d['keys']; n=len(a)
def depth(i): return (i+1).bit_length()-1
def grandchildren(i): return [j for j in range(4*i+3,4*i+7) if j<n]
return {'parity': [depth(i)%2 for i in range(n)],
'grandparents': [None if i<3 else (i-3)//4 for i in range(n)],
'min_violations': [[i,j] for i in range(n) if depth(i)%2==0 for j in grandchildren(i) if a[j]<a[i]],
'max_violations': [[i,j] for i in range(n) if depth(i)%2==1 for j in grandchildren(i) if a[j]>a[i]],
'maximum': None if not a else max(a[1:3] or a),
'edges': [[i,j] for i in range(n) for j in (2*i+1,2*i+2) if j<n]}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'keys': []}, {'parity': [], 'grandparents': [], 'min_violations': [], 'max_violations': [], 'maximum': None, 'edges': []}), ({'keys': [4]}, {'parity': [0], 'grandparents': [None], 'min_violations': [], 'max_violations': [], 'maximum': 4, 'edges': []}), ({'keys': [1, 8, 9]}, {'parity': [0, 1, 1], 'grandparents': [None, None, None], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2]]}), ({'keys': [2, 9, 8, 3, 2, 4, 7]}, {'parity': [0, 1, 1, 0, 0, 0, 0], 'grandparents': [None, None, None, 0, 0, 0, 0], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]]}), ({'keys': [5, 4, 9, 1, 8, 2, 6, 10, 3, 8, 7, 6, 5, 4, 3]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [[0, 3], [0, 5]], 'max_violations': [[1, 7], [1, 9], [1, 10]], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 7, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [[1, 10]], 'maximum': 8, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 8, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [[1, 10]], 'maximum': 8, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]})], [({'keys': []}, {'parity': [], 'grandparents': [], 'min_violations': [], 'max_violations': [], 'maximum': None, 'edges': []}), ({'keys': [4]}, {'parity': [0], 'grandparents': [None], 'min_violations': [], 'max_violations': [], 'maximum': 4, 'edges': []}), ({'keys': [1, 8, 9]}, {'parity': [0, 1, 1], 'grandparents': [None, None, None], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2]]}), ({'keys': [2, 9, 8, 3, 2, 4, 7]}, {'parity': [0, 1, 1, 0, 0, 0, 0], 'grandparents': [None, None, None, 0, 0, 0, 0], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]]}), ({'keys': [5, 4, 9, 1, 8, 2, 6, 10, 3, 8, 7, 6, 5, 4, 3]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [[0, 3], [0, 5]], 'max_violations': [[1, 7], [1, 9], [1, 10]], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 7, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [[1, 10]], 'maximum': 8, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 9, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]})], [({'keys': []}, {'parity': [], 'grandparents': [], 'min_violations': [], 'max_violations': [], 'maximum': None, 'edges': []}), ({'keys': [4]}, {'parity': [0], 'grandparents': [None], 'min_violations': [], 'max_violations': [], 'maximum': 4, 'edges': []}), ({'keys': [1, 8, 9]}, {'parity': [0, 1, 1], 'grandparents': [None, None, None], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2]]}), ({'keys': [2, 9, 8, 3, 2, 4, 7]}, {'parity': [0, 1, 1, 0, 0, 0, 0], 'grandparents': [None, None, None, 0, 0, 0, 0], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]]}), ({'keys': [5, 4, 9, 1, 8, 2, 6, 10, 3, 8, 7, 6, 5, 4, 3]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [[0, 3], [0, 5]], 'max_violations': [[1, 7], [1, 9], [1, 10]], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 7, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [[1, 10]], 'maximum': 8, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 10, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [], 'maximum': 10, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]})], [({'keys': []}, {'parity': [], 'grandparents': [], 'min_violations': [], 'max_violations': [], 'maximum': None, 'edges': []}), ({'keys': [4]}, {'parity': [0], 'grandparents': [None], 'min_violations': [], 'max_violations': [], 'maximum': 4, 'edges': []}), ({'keys': [1, 8, 9]}, {'parity': [0, 1, 1], 'grandparents': [None, None, None], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2]]}), ({'keys': [2, 9, 8, 3, 2, 4, 7]}, {'parity': [0, 1, 1, 0, 0, 0, 0], 'grandparents': [None, None, None, 0, 0, 0, 0], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]]}), ({'keys': [5, 4, 9, 1, 8, 2, 6, 10, 3, 8, 7, 6, 5, 4, 3]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [[0, 3], [0, 5]], 'max_violations': [[1, 7], [1, 9], [1, 10]], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 7, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [[1, 10]], 'maximum': 8, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 11, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [], 'maximum': 11, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]})], [({'keys': []}, {'parity': [], 'grandparents': [], 'min_violations': [], 'max_violations': [], 'maximum': None, 'edges': []}), ({'keys': [4]}, {'parity': [0], 'grandparents': [None], 'min_violations': [], 'max_violations': [], 'maximum': 4, 'edges': []}), ({'keys': [1, 8, 9]}, {'parity': [0, 1, 1], 'grandparents': [None, None, None], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2]]}), ({'keys': [2, 9, 8, 3, 2, 4, 7]}, {'parity': [0, 1, 1, 0, 0, 0, 0], 'grandparents': [None, None, None, 0, 0, 0, 0], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]]}), ({'keys': [5, 4, 9, 1, 8, 2, 6, 10, 3, 8, 7, 6, 5, 4, 3]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [[0, 3], [0, 5]], 'max_violations': [[1, 7], [1, 9], [1, 10]], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 7, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [[1, 10]], 'maximum': 8, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 12, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [], 'maximum': 12, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 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)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| regression certificate 1 | {'edges': [], 'grandparents': [], 'max_violations': [], 'maximum': None, 'min_violations': [], 'parity': []} | {'edges': [], 'grandparents': [], 'max_violations': [], 'maximum': None, 'min_violations': [], 'parity': []} | Passed |
| regression certificate 2 | {'edges': [], 'grandparents': [None], 'max_violations': [], 'maximum': 4, 'min_violations': [], 'parity': [0]} | {'edges': [], 'grandparents': [None], 'max_violations': [], 'maximum': 4, 'min_violations': [], 'parity': [0]} | Passed |
| regression certificate 3 | {'edges': [[0, 1], [0, 2]], 'grandparents': [None, None, None], 'max_violations': [], 'maximum': 9, 'min_violations': [], 'parity': [0, 1, 1]} | {'edges': [[0, 1], [0, 2]], 'grandparents': [None, None, None], 'max_violations': [], 'maximum': 9, 'min_violations': [], 'parity': [0, 1, 1]} | Passed |
| regression certificate 4 | {'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]], 'grandparents': [None, None, None, 0, 0, 0, 0], 'max_violations': [], 'maximum': 9, 'min_violations': [], 'parity': [0, 1, 1, 0, 0, 0, 0]} | {'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]], 'grandparents': [None, None, None, 0, 0, 0, 0], 'max_violations': [], 'maximum': 9, 'min_violations': [], 'parity': [0, 1, 1, 0, 0, 0, 0]} | Passed |
| regression certificate 5 | {'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'max_violations': [[1, 7], [1, 9], [1, 10]], 'maximum': 9, 'min_violations': [[0, 3], [0, 5]], 'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]} | {'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'max_violations': [[1, 7], [1, 9], [1, 10]], 'maximum': 9, 'min_violations': [[0, 3], [0, 5]], 'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]} | Passed |
| regression certificate 6 | {'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'max_violations': [[1, 10]], 'maximum': 8, 'min_violations': [], 'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]} | {'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'max_violations': [[1, 10]], 'maximum': 8, 'min_violations': [], 'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]} | Passed |
| variant-dependent certificate | {'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'max_violations': [[1, 10]], 'maximum': 8, 'min_violations': [], 'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]} | {'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'max_violations': [[1, 10]], 'maximum': 8, 'min_violations': [], 'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]} | Passed |
SHA-256 / 6cdf3075ba45f3441d9cc01e779db03bdb44f414ee457672e010befa88b92b90
Verification & scope
A stipulated offline diagnostic model; it does not implement a production allocator, concurrency protocol, or complete heap library. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.
Observations recorded using Python 3.12.14 at 2026-09-29T14:43:30.827037+00:00.
Case digest / 038c25b7016d3588d2959487486d81cbc9ac7a0f3cdc6126114079dae27cc72a