{"abstract":"The bounded minmax grandchild step certificate reports an incorrect grandchild key.","category":"Heap invariants","checks":7,"contract":"A minimum-level trickle step receives current key x, chosen grandchild key g, its parent key p, and ids. After swapping x with smaller g, x at the grandchild must also be no greater than its maximum-level parent; if x>p exchange those two. Return root key, grandchild key, parent key, cross-level correction flag, two-step trace, and preserved multiset.","evaluation_group":"s3-heap-model-minmax-grandchild-step","failed_approach":"The local patch uses g and still violates the stated relation.","family":"s3-heap-minmax-grandchild-step-grandchild_key","id":"FA-40746","implementations":{"attempt":{"sha256":"7b227fb89a43e33c6eedad1bce389d016beea65287f33eb0882513130df1e458","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(d):\n    x=d['x']; g=d['g']; p=d['p']; descend=g<x; correction=descend and x>p\n    root=g if descend else x; gc=(p if correction else x) if descend else g; parent=x if correction else p\n    return {'root_key': root,\n    'grandchild_key': g,\n    'parent_key': parent,\n    'correction': correction,\n    'trace': ([\"grandchild\"]+[\"parent\"] if correction else [\"grandchild\"]) if descend else [],\n    'multiset': sorted([root,gc,parent])}\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 10, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 10, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 10]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 11, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 11, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 11]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 12, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 12, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 12]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 13, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 13, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 13]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 14, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 14, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 14]})]][N-1]\ncheck('regression certificate 1', solve(cases[0][0]), cases[0][1])\ncheck('regression certificate 2', solve(cases[1][0]), cases[1][1])\ncheck('regression certificate 3', solve(cases[2][0]), cases[2][1])\ncheck('regression certificate 4', solve(cases[3][0]), cases[3][1])\ncheck('regression certificate 5', solve(cases[4][0]), cases[4][1])\ncheck('regression certificate 6', solve(cases[5][0]), cases[5][1])\ncheck('variant-dependent certificate', solve(cases[6][0]), cases[6][1])\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"broken":{"sha256":"ff256d430fb9e852ae36a28f61ac0b6a3e791b39e0e09e8b27b39e436c79c3e5","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(d):\n    x=d['x']; g=d['g']; p=d['p']; descend=g<x; correction=descend and x>p\n    root=g if descend else x; gc=(p if correction else x) if descend else g; parent=x if correction else p\n    return {'root_key': root,\n    'grandchild_key': x if descend else g,\n    'parent_key': parent,\n    'correction': correction,\n    'trace': ([\"grandchild\"]+[\"parent\"] if correction else [\"grandchild\"]) if descend else [],\n    'multiset': sorted([root,gc,parent])}\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 10, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 10, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 10]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 11, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 11, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 11]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 12, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 12, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 12]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 13, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 13, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 13]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 14, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 14, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 14]})]][N-1]\ncheck('regression certificate 1', solve(cases[0][0]), cases[0][1])\ncheck('regression certificate 2', solve(cases[1][0]), cases[1][1])\ncheck('regression certificate 3', solve(cases[2][0]), cases[2][1])\ncheck('regression certificate 4', solve(cases[3][0]), cases[3][1])\ncheck('regression certificate 5', solve(cases[4][0]), cases[4][1])\ncheck('regression certificate 6', solve(cases[5][0]), cases[5][1])\ncheck('variant-dependent certificate', solve(cases[6][0]), cases[6][1])\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"fixed":{"sha256":"c7ef9a607a1b957a6bbfa7c13afb7b24afdfc823e4fbebb7882279aaac41e1c0","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(d):\n    x=d['x']; g=d['g']; p=d['p']; descend=g<x; correction=descend and x>p\n    root=g if descend else x; gc=(p if correction else x) if descend else g; parent=x if correction else p\n    return {'root_key': root,\n    'grandchild_key': gc,\n    'parent_key': parent,\n    'correction': correction,\n    'trace': ([\"grandchild\"]+[\"parent\"] if correction else [\"grandchild\"]) if descend else [],\n    'multiset': sorted([root,gc,parent])}\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 10, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 10, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 10]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 11, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 11, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 11]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 12, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 12, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 12]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 13, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 13, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 13]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 14, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 14, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 14]})]][N-1]\ncheck('regression certificate 1', solve(cases[0][0]), cases[0][1])\ncheck('regression certificate 2', solve(cases[1][0]), cases[1][1])\ncheck('regression certificate 3', solve(cases[2][0]), cases[2][1])\ncheck('regression certificate 4', solve(cases[3][0]), cases[3][1])\ncheck('regression certificate 5', solve(cases[4][0]), cases[4][1])\ncheck('regression certificate 6', solve(cases[5][0]), cases[5][1])\ncheck('variant-dependent certificate', solve(cases[6][0]), cases[6][1])\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"}},"limitations":"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.","method":"Deterministic executable model with adversarial boundary fixtures.","provenance":{"created_by":"Failure Map","dependencies":"Python standard library","family":"s3-heap-minmax-grandchild-step-grandchild_key","generated_at":"2026-09-29T14:43:34.081408+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"This isolates an internal heap representation or priority-structure invariant using deterministic finite records.","repair":"Derive grandchild key using gc under the stated bounded certificate contract.","root_cause":"Min-max trickle repairs the displaced key against the intervening max-level parent.","sha256":"2177d1933e68bc9f000b529a4d29386d9b2870331598dead6cf9d0c32807d8ad","title":"Min-max trickle repairs the displaced key against the intervening max-level parent · case 01","variant":1,"variant_policy":"Six explicit regression certificates are retained; a seventh changes structural size, position, priority, or bounds with N.","verification":{"attempt":{"elapsed_ms":40.076,"exit_code":1,"observations":[{"actual":{"correction":true,"grandchild_key":2,"multiset":[2,7,9],"parent_key":9,"root_key":2,"trace":["grandchild","parent"]},"check":"regression certificate 1","expected":{"correction":true,"grandchild_key":7,"multiset":[2,7,9],"parent_key":9,"root_key":2,"trace":["grandchild","parent"]},"passed":false},{"actual":{"correction":false,"grandchild_key":1,"multiset":[1,5,8],"parent_key":8,"root_key":1,"trace":["grandchild"]},"check":"regression certificate 2","expected":{"correction":false,"grandchild_key":5,"multiset":[1,5,8],"parent_key":8,"root_key":1,"trace":["grandchild"]},"passed":false},{"actual":{"correction":false,"grandchild_key":4,"multiset":[3,4,8],"parent_key":8,"root_key":3,"trace":[]},"check":"regression certificate 3","expected":{"correction":false,"grandchild_key":4,"multiset":[3,4,8],"parent_key":8,"root_key":3,"trace":[]},"passed":true},{"actual":{"correction":false,"grandchild_key":2,"multiset":[2,7,7],"parent_key":7,"root_key":2,"trace":["grandchild"]},"check":"regression certificate 4","expected":{"correction":false,"grandchild_key":7,"multiset":[2,7,7],"parent_key":7,"root_key":2,"trace":["grandchild"]},"passed":false},{"actual":{"correction":false,"grandchild_key":4,"multiset":[4,4,9],"parent_key":9,"root_key":4,"trace":[]},"check":"regression certificate 5","expected":{"correction":false,"grandchild_key":4,"multiset":[4,4,9],"parent_key":9,"root_key":4,"trace":[]},"passed":true},{"actual":{"correction":true,"grandchild_key":2,"multiset":[2,2,9],"parent_key":9,"root_key":2,"trace":["grandchild","parent"]},"check":"regression certificate 6","expected":{"correction":true,"grandchild_key":2,"multiset":[2,2,9],"parent_key":9,"root_key":2,"trace":["grandchild","parent"]},"passed":true},{"actual":{"correction":true,"grandchild_key":2,"multiset":[2,2,10],"parent_key":10,"root_key":2,"trace":["grandchild","parent"]},"check":"variant-dependent certificate","expected":{"correction":true,"grandchild_key":2,"multiset":[2,2,10],"parent_key":10,"root_key":2,"trace":["grandchild","parent"]},"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"regression certificate 1\", \"actual\": {\"root_key\": 2, \"grandchild_key\": 2, \"parent_key\": 9, \"correction\": true, \"trace\": [\"grandchild\", \"parent\"], \"multiset\": [2, 7, 9]}, \"expected\": {\"root_key\": 2, \"grandchild_key\": 7, \"parent_key\": 9, \"correction\": true, \"trace\": [\"grandchild\", \"parent\"], \"multiset\": [2, 7, 9]}, \"passed\": false}, {\"check\": \"regression certificate 2\", \"actual\": {\"root_key\": 1, \"grandchild_key\": 1, \"parent_key\": 8, \"correction\": false, \"trace\": [\"grandchild\"], \"multiset\": [1, 5, 8]}, \"expected\": {\"root_key\": 1, \"grandchild_key\": 5, \"parent_key\": 8, \"correction\": false, \"trace\": [\"grandchild\"], \"multiset\": [1, 5, 8]}, \"passed\": false}, {\"check\": \"regression certificate 3\", \"actual\": {\"root_key\": 3, \"grandchild_key\": 4, \"parent_key\": 8, \"correction\": false, \"trace\": [], \"multiset\": [3, 4, 8]}, \"expected\": {\"root_key\": 3, \"grandchild_key\": 4, \"parent_key\": 8, \"correction\": false, \"trace\": [], \"multiset\": [3, 4, 8]}, \"passed\": true}, {\"check\": \"regression certificate 4\", \"actual\": {\"root_key\": 2, \"grandchild_key\": 2, \"parent_key\": 7, \"correction\": false, \"trace\": [\"grandchild\"], \"multiset\": [2, 7, 7]}, \"expected\": {\"root_key\": 2, \"grandchild_key\": 7, \"parent_key\": 7, \"correction\": false, \"trace\": [\"grandchild\"], \"multiset\": [2, 7, 7]}, \"passed\": false}, {\"check\": \"regression certificate 5\", \"actual\": {\"root_key\": 4, \"grandchild_key\": 4, \"parent_key\": 9, \"correction\": false, \"trace\": [], \"multiset\": [4, 4, 9]}, \"expected\": {\"root_key\": 4, \"grandchild_key\": 4, \"parent_key\": 9, \"correction\": false, \"trace\": [], \"multiset\": [4, 4, 9]}, \"passed\": true}, {\"check\": \"regression certificate 6\", \"actual\": {\"root_key\": 2, \"grandchild_key\": 2, \"parent_key\": 9, \"correction\": true, \"trace\": [\"grandchild\", \"parent\"], \"multiset\": [2, 2, 9]}, \"expected\": {\"root_key\": 2, \"grandchild_key\": 2, \"parent_key\": 9, \"correction\": true, \"trace\": [\"grandchild\", \"parent\"], \"multiset\": [2, 2, 9]}, \"passed\": true}, {\"check\": \"variant-dependent certificate\", \"actual\": {\"root_key\": 2, \"grandchild_key\": 2, \"parent_key\": 10, \"correction\": true, \"trace\": [\"grandchild\", \"parent\"], \"multiset\": [2, 2, 10]}, \"expected\": {\"root_key\": 2, \"grandchild_key\": 2, \"parent_key\": 10, \"correction\": true, \"trace\": [\"grandchild\", \"parent\"], \"multiset\": [2, 2, 10]}, \"passed\": true}], \"passed\": false}\n"},"broken":{"elapsed_ms":44.74,"exit_code":1,"observations":[{"actual":{"correction":true,"grandchild_key":9,"multiset":[2,7,9],"parent_key":9,"root_key":2,"trace":["grandchild","parent"]},"check":"regression certificate 1","expected":{"correction":true,"grandchild_key":7,"multiset":[2,7,9],"parent_key":9,"root_key":2,"trace":["grandchild","parent"]},"passed":false},{"actual":{"correction":false,"grandchild_key":5,"multiset":[1,5,8],"parent_key":8,"root_key":1,"trace":["grandchild"]},"check":"regression certificate 2","expected":{"correction":false,"grandchild_key":5,"multiset":[1,5,8],"parent_key":8,"root_key":1,"trace":["grandchild"]},"passed":true},{"actual":{"correction":false,"grandchild_key":4,"multiset":[3,4,8],"parent_key":8,"root_key":3,"trace":[]},"check":"regression certificate 3","expected":{"correction":false,"grandchild_key":4,"multiset":[3,4,8],"parent_key":8,"root_key":3,"trace":[]},"passed":true},{"actual":{"correction":false,"grandchild_key":7,"multiset":[2,7,7],"parent_key":7,"root_key":2,"trace":["grandchild"]},"check":"regression certificate 4","expected":{"correction":false,"grandchild_key":7,"multiset":[2,7,7],"parent_key":7,"root_key":2,"trace":["grandchild"]},"passed":true},{"actual":{"correction":false,"grandchild_key":4,"multiset":[4,4,9],"parent_key":9,"root_key":4,"trace":[]},"check":"regression certificate 5","expected":{"correction":false,"grandchild_key":4,"multiset":[4,4,9],"parent_key":9,"root_key":4,"trace":[]},"passed":true},{"actual":{"correction":true,"grandchild_key":9,"multiset":[2,2,9],"parent_key":9,"root_key":2,"trace":["grandchild","parent"]},"check":"regression certificate 6","expected":{"correction":true,"grandchild_key":2,"multiset":[2,2,9],"parent_key":9,"root_key":2,"trace":["grandchild","parent"]},"passed":false},{"actual":{"correction":true,"grandchild_key":10,"multiset":[2,2,10],"parent_key":10,"root_key":2,"trace":["grandchild","parent"]},"check":"variant-dependent certificate","expected":{"correction":true,"grandchild_key":2,"multiset":[2,2,10],"parent_key":10,"root_key":2,"trace":["grandchild","parent"]},"passed":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"regression certificate 1\", \"actual\": {\"root_key\": 2, \"grandchild_key\": 9, \"parent_key\": 9, \"correction\": true, \"trace\": [\"grandchild\", \"parent\"], \"multiset\": [2, 7, 9]}, \"expected\": {\"root_key\": 2, \"grandchild_key\": 7, \"parent_key\": 9, \"correction\": true, \"trace\": [\"grandchild\", \"parent\"], \"multiset\": [2, 7, 9]}, \"passed\": false}, {\"check\": \"regression certificate 2\", \"actual\": {\"root_key\": 1, \"grandchild_key\": 5, \"parent_key\": 8, \"correction\": false, \"trace\": [\"grandchild\"], \"multiset\": [1, 5, 8]}, \"expected\": {\"root_key\": 1, \"grandchild_key\": 5, \"parent_key\": 8, \"correction\": false, \"trace\": [\"grandchild\"], \"multiset\": [1, 5, 8]}, \"passed\": true}, {\"check\": \"regression certificate 3\", \"actual\": {\"root_key\": 3, \"grandchild_key\": 4, \"parent_key\": 8, \"correction\": false, \"trace\": [], \"multiset\": [3, 4, 8]}, \"expected\": {\"root_key\": 3, \"grandchild_key\": 4, \"parent_key\": 8, \"correction\": false, \"trace\": [], \"multiset\": [3, 4, 8]}, \"passed\": true}, {\"check\": \"regression certificate 4\", \"actual\": {\"root_key\": 2, \"grandchild_key\": 7, \"parent_key\": 7, \"correction\": false, \"trace\": [\"grandchild\"], \"multiset\": [2, 7, 7]}, \"expected\": {\"root_key\": 2, \"grandchild_key\": 7, \"parent_key\": 7, \"correction\": false, \"trace\": [\"grandchild\"], \"multiset\": [2, 7, 7]}, \"passed\": true}, {\"check\": \"regression certificate 5\", \"actual\": {\"root_key\": 4, \"grandchild_key\": 4, \"parent_key\": 9, \"correction\": false, \"trace\": [], \"multiset\": [4, 4, 9]}, \"expected\": {\"root_key\": 4, \"grandchild_key\": 4, \"parent_key\": 9, \"correction\": false, \"trace\": [], \"multiset\": [4, 4, 9]}, \"passed\": true}, {\"check\": \"regression certificate 6\", \"actual\": {\"root_key\": 2, \"grandchild_key\": 9, \"parent_key\": 9, \"correction\": true, \"trace\": [\"grandchild\", \"parent\"], \"multiset\": [2, 2, 9]}, \"expected\": {\"root_key\": 2, \"grandchild_key\": 2, \"parent_key\": 9, \"correction\": true, \"trace\": [\"grandchild\", \"parent\"], \"multiset\": [2, 2, 9]}, \"passed\": false}, {\"check\": \"variant-dependent certificate\", \"actual\": {\"root_key\": 2, \"grandchild_key\": 10, \"parent_key\": 10, \"correction\": true, \"trace\": [\"grandchild\", \"parent\"], \"multiset\": [2, 2, 10]}, \"expected\": {\"root_key\": 2, \"grandchild_key\": 2, \"parent_key\": 10, \"correction\": true, \"trace\": [\"grandchild\", \"parent\"], \"multiset\": [2, 2, 10]}, \"passed\": false}], \"passed\": false}\n"},"fixed":{"elapsed_ms":40.169,"exit_code":0,"observations":[{"actual":{"correction":true,"grandchild_key":7,"multiset":[2,7,9],"parent_key":9,"root_key":2,"trace":["grandchild","parent"]},"check":"regression certificate 1","expected":{"correction":true,"grandchild_key":7,"multiset":[2,7,9],"parent_key":9,"root_key":2,"trace":["grandchild","parent"]},"passed":true},{"actual":{"correction":false,"grandchild_key":5,"multiset":[1,5,8],"parent_key":8,"root_key":1,"trace":["grandchild"]},"check":"regression certificate 2","expected":{"correction":false,"grandchild_key":5,"multiset":[1,5,8],"parent_key":8,"root_key":1,"trace":["grandchild"]},"passed":true},{"actual":{"correction":false,"grandchild_key":4,"multiset":[3,4,8],"parent_key":8,"root_key":3,"trace":[]},"check":"regression certificate 3","expected":{"correction":false,"grandchild_key":4,"multiset":[3,4,8],"parent_key":8,"root_key":3,"trace":[]},"passed":true},{"actual":{"correction":false,"grandchild_key":7,"multiset":[2,7,7],"parent_key":7,"root_key":2,"trace":["grandchild"]},"check":"regression certificate 4","expected":{"correction":false,"grandchild_key":7,"multiset":[2,7,7],"parent_key":7,"root_key":2,"trace":["grandchild"]},"passed":true},{"actual":{"correction":false,"grandchild_key":4,"multiset":[4,4,9],"parent_key":9,"root_key":4,"trace":[]},"check":"regression certificate 5","expected":{"correction":false,"grandchild_key":4,"multiset":[4,4,9],"parent_key":9,"root_key":4,"trace":[]},"passed":true},{"actual":{"correction":true,"grandchild_key":2,"multiset":[2,2,9],"parent_key":9,"root_key":2,"trace":["grandchild","parent"]},"check":"regression certificate 6","expected":{"correction":true,"grandchild_key":2,"multiset":[2,2,9],"parent_key":9,"root_key":2,"trace":["grandchild","parent"]},"passed":true},{"actual":{"correction":true,"grandchild_key":2,"multiset":[2,2,10],"parent_key":10,"root_key":2,"trace":["grandchild","parent"]},"check":"variant-dependent certificate","expected":{"correction":true,"grandchild_key":2,"multiset":[2,2,10],"parent_key":10,"root_key":2,"trace":["grandchild","parent"]},"passed":true}],"passed":true,"stderr":"","stdout":"{\"observations\": [{\"check\": \"regression certificate 1\", \"actual\": {\"root_key\": 2, \"grandchild_key\": 7, \"parent_key\": 9, \"correction\": true, \"trace\": [\"grandchild\", \"parent\"], \"multiset\": [2, 7, 9]}, \"expected\": {\"root_key\": 2, \"grandchild_key\": 7, \"parent_key\": 9, \"correction\": true, \"trace\": [\"grandchild\", \"parent\"], \"multiset\": [2, 7, 9]}, \"passed\": true}, {\"check\": \"regression certificate 2\", \"actual\": {\"root_key\": 1, \"grandchild_key\": 5, \"parent_key\": 8, \"correction\": false, \"trace\": [\"grandchild\"], \"multiset\": [1, 5, 8]}, \"expected\": {\"root_key\": 1, \"grandchild_key\": 5, \"parent_key\": 8, \"correction\": false, \"trace\": [\"grandchild\"], \"multiset\": [1, 5, 8]}, \"passed\": true}, {\"check\": \"regression certificate 3\", \"actual\": {\"root_key\": 3, \"grandchild_key\": 4, \"parent_key\": 8, \"correction\": false, \"trace\": [], \"multiset\": [3, 4, 8]}, \"expected\": {\"root_key\": 3, \"grandchild_key\": 4, \"parent_key\": 8, \"correction\": false, \"trace\": [], \"multiset\": [3, 4, 8]}, \"passed\": true}, {\"check\": \"regression certificate 4\", \"actual\": {\"root_key\": 2, \"grandchild_key\": 7, \"parent_key\": 7, \"correction\": false, \"trace\": [\"grandchild\"], \"multiset\": [2, 7, 7]}, \"expected\": {\"root_key\": 2, \"grandchild_key\": 7, \"parent_key\": 7, \"correction\": false, \"trace\": [\"grandchild\"], \"multiset\": [2, 7, 7]}, \"passed\": true}, {\"check\": \"regression certificate 5\", \"actual\": {\"root_key\": 4, \"grandchild_key\": 4, \"parent_key\": 9, \"correction\": false, \"trace\": [], \"multiset\": [4, 4, 9]}, \"expected\": {\"root_key\": 4, \"grandchild_key\": 4, \"parent_key\": 9, \"correction\": false, \"trace\": [], \"multiset\": [4, 4, 9]}, \"passed\": true}, {\"check\": \"regression certificate 6\", \"actual\": {\"root_key\": 2, \"grandchild_key\": 2, \"parent_key\": 9, \"correction\": true, \"trace\": [\"grandchild\", \"parent\"], \"multiset\": [2, 2, 9]}, \"expected\": {\"root_key\": 2, \"grandchild_key\": 2, \"parent_key\": 9, \"correction\": true, \"trace\": [\"grandchild\", \"parent\"], \"multiset\": [2, 2, 9]}, \"passed\": true}, {\"check\": \"variant-dependent certificate\", \"actual\": {\"root_key\": 2, \"grandchild_key\": 2, \"parent_key\": 10, \"correction\": true, \"trace\": [\"grandchild\", \"parent\"], \"multiset\": [2, 2, 10]}, \"expected\": {\"root_key\": 2, \"grandchild_key\": 2, \"parent_key\": 10, \"correction\": true, \"trace\": [\"grandchild\", \"parent\"], \"multiset\": [2, 2, 10]}, \"passed\": true}], \"passed\": true}\n"}},"verified":true,"visibility":"public"}