{"abstract":"Deque merge drops the unmerged left suffix.","category":"Bounded deques","checks":6,"contract":"Merge sorted deque runs by key, placing equal keys from the left run first and preserving each run order. Split the merged stream at output capacity.","evaluation_group":"s3-bounded-deques-merge-runs","failed_approach":"The partial repair still applies the incorrect transition to an admitted boundary or multi-element case.","family":"s3-bounded-deques-merge-runs-left-tail","id":"FA-46246","implementations":{"attempt":{"sha256":"777ced77e7e4c9bb4a8cf5154a583512509b2478a711b8fb9535c690fbd5ed0d","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    a,b,cap=x\n    out=[]\n    i=j=0\n    while i<len(a) and j<len(b):\n        if a[i][0]<=b[j][0]:\n            out.append(a[i]);i+=1\n        else:\n            out.append(b[j]);j+=1\n    out.extend(a[i:] if j==0 else [])\n    out.extend(b[j:])\n    return [out[:cap],out[cap:]]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncheck('0', solve([[[1,N],[2,N+1]],[[1,N+2],[3,N+3]],3]), {1: [[[1, 1], [1, 3], [2, 2]], [[3, 4]]], 2: [[[1, 2], [1, 4], [2, 3]], [[3, 5]]], 3: [[[1, 3], [1, 5], [2, 4]], [[3, 6]]], 4: [[[1, 4], [1, 6], [2, 5]], [[3, 7]]], 5: [[[1, 5], [1, 7], [2, 6]], [[3, 8]]]}[N])\ncheck('1', solve([[[1,N]],[],2]), {1: [[[1, 1]], []], 2: [[[1, 2]], []], 3: [[[1, 3]], []], 4: [[[1, 4]], []], 5: [[[1, 5]], []]}[N])\ncheck('2', solve([[],[[1,N]],0]), {1: [[], [[1, 1]]], 2: [[], [[1, 2]]], 3: [[], [[1, 3]]], 4: [[], [[1, 4]]], 5: [[], [[1, 5]]]}[N])\ncheck('3', solve([[[1,N],[1,N+1]],[[1,N+2]],3]), {1: [[[1, 1], [1, 2], [1, 3]], []], 2: [[[1, 2], [1, 3], [1, 4]], []], 3: [[[1, 3], [1, 4], [1, 5]], []], 4: [[[1, 4], [1, 5], [1, 6]], []], 5: [[[1, 5], [1, 6], [1, 7]], []]}[N])\ncheck('4', solve([[[4,N]],[[1,N+1],[2,N+2]],4]), {1: [[[1, 2], [2, 3], [4, 1]], []], 2: [[[1, 3], [2, 4], [4, 2]], []], 3: [[[1, 4], [2, 5], [4, 3]], []], 4: [[[1, 5], [2, 6], [4, 4]], []], 5: [[[1, 6], [2, 7], [4, 5]], []]}[N])\ncheck('5', solve([[],[],2]), {1: [[], []], 2: [[], []], 3: [[], []], 4: [[], []], 5: [[], []]}[N])\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":"0694305b73834ea46100dd0aacc70f8ad4aca2bcbbc08c78b0abb9b90f4d51eb","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    a,b,cap=x\n    out=[]\n    i=j=0\n    while i<len(a) and j<len(b):\n        if a[i][0]<=b[j][0]:\n            out.append(a[i]);i+=1\n        else:\n            out.append(b[j]);j+=1\n    out.extend([])\n    out.extend(b[j:])\n    return [out[:cap],out[cap:]]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncheck('0', solve([[[1,N],[2,N+1]],[[1,N+2],[3,N+3]],3]), {1: [[[1, 1], [1, 3], [2, 2]], [[3, 4]]], 2: [[[1, 2], [1, 4], [2, 3]], [[3, 5]]], 3: [[[1, 3], [1, 5], [2, 4]], [[3, 6]]], 4: [[[1, 4], [1, 6], [2, 5]], [[3, 7]]], 5: [[[1, 5], [1, 7], [2, 6]], [[3, 8]]]}[N])\ncheck('1', solve([[[1,N]],[],2]), {1: [[[1, 1]], []], 2: [[[1, 2]], []], 3: [[[1, 3]], []], 4: [[[1, 4]], []], 5: [[[1, 5]], []]}[N])\ncheck('2', solve([[],[[1,N]],0]), {1: [[], [[1, 1]]], 2: [[], [[1, 2]]], 3: [[], [[1, 3]]], 4: [[], [[1, 4]]], 5: [[], [[1, 5]]]}[N])\ncheck('3', solve([[[1,N],[1,N+1]],[[1,N+2]],3]), {1: [[[1, 1], [1, 2], [1, 3]], []], 2: [[[1, 2], [1, 3], [1, 4]], []], 3: [[[1, 3], [1, 4], [1, 5]], []], 4: [[[1, 4], [1, 5], [1, 6]], []], 5: [[[1, 5], [1, 6], [1, 7]], []]}[N])\ncheck('4', solve([[[4,N]],[[1,N+1],[2,N+2]],4]), {1: [[[1, 2], [2, 3], [4, 1]], []], 2: [[[1, 3], [2, 4], [4, 2]], []], 3: [[[1, 4], [2, 5], [4, 3]], []], 4: [[[1, 5], [2, 6], [4, 4]], []], 5: [[[1, 6], [2, 7], [4, 5]], []]}[N])\ncheck('5', solve([[],[],2]), {1: [[], []], 2: [[], []], 3: [[], []], 4: [[], []], 5: [[], []]}[N])\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":"29c5f698168933d5a694c57753f86162759032454083f9ea1c95002fa7e116db","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    a,b,cap=x\n    out=[]\n    i=j=0\n    while i<len(a) and j<len(b):\n        if a[i][0]<=b[j][0]:\n            out.append(a[i]);i+=1\n        else:\n            out.append(b[j]);j+=1\n    out.extend(a[i:])\n    out.extend(b[j:])\n    return [out[:cap],out[cap:]]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncheck('0', solve([[[1,N],[2,N+1]],[[1,N+2],[3,N+3]],3]), {1: [[[1, 1], [1, 3], [2, 2]], [[3, 4]]], 2: [[[1, 2], [1, 4], [2, 3]], [[3, 5]]], 3: [[[1, 3], [1, 5], [2, 4]], [[3, 6]]], 4: [[[1, 4], [1, 6], [2, 5]], [[3, 7]]], 5: [[[1, 5], [1, 7], [2, 6]], [[3, 8]]]}[N])\ncheck('1', solve([[[1,N]],[],2]), {1: [[[1, 1]], []], 2: [[[1, 2]], []], 3: [[[1, 3]], []], 4: [[[1, 4]], []], 5: [[[1, 5]], []]}[N])\ncheck('2', solve([[],[[1,N]],0]), {1: [[], [[1, 1]]], 2: [[], [[1, 2]]], 3: [[], [[1, 3]]], 4: [[], [[1, 4]]], 5: [[], [[1, 5]]]}[N])\ncheck('3', solve([[[1,N],[1,N+1]],[[1,N+2]],3]), {1: [[[1, 1], [1, 2], [1, 3]], []], 2: [[[1, 2], [1, 3], [1, 4]], []], 3: [[[1, 3], [1, 4], [1, 5]], []], 4: [[[1, 4], [1, 5], [1, 6]], []], 5: [[[1, 5], [1, 6], [1, 7]], []]}[N])\ncheck('4', solve([[[4,N]],[[1,N+1],[2,N+2]],4]), {1: [[[1, 2], [2, 3], [4, 1]], []], 2: [[[1, 3], [2, 4], [4, 2]], []], 3: [[[1, 4], [2, 5], [4, 3]], []], 4: [[[1, 5], [2, 6], [4, 4]], []], 5: [[[1, 6], [2, 7], [4, 5]], []]}[N])\ncheck('5', solve([[],[],2]), {1: [[], []], 2: [[], []], 3: [[], []], 4: [[], []], 5: [[], []]}[N])\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":"Offline finite deterministic model; no claim of production implementation or concurrent memory-model conformance. 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-bounded-deques-merge-runs-left-tail","generated_at":"2026-09-29T14:44:30.287752+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"Controlled bounded deque implementation model with explicit storage and lifecycle observations.","repair":"Restore the documented left tail invariant in merge-runs.","root_cause":"Deque merge drops the unmerged left suffix.","sha256":"f505c55160fdbac2e418c3b157d8b517f818271c7b2116568ef3c8f2150b367d","title":"Deque merge drops the unmerged left suffix · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verification":{"attempt":{"elapsed_ms":41.18,"exit_code":1,"observations":[{"actual":[[[1,1],[1,3],[2,2]],[[3,4]]],"check":"0","expected":[[[1,1],[1,3],[2,2]],[[3,4]]],"passed":true},{"actual":[[[1,1]],[]],"check":"1","expected":[[[1,1]],[]],"passed":true},{"actual":[[],[[1,1]]],"check":"2","expected":[[],[[1,1]]],"passed":true},{"actual":[[[1,1],[1,2],[1,3]],[]],"check":"3","expected":[[[1,1],[1,2],[1,3]],[]],"passed":true},{"actual":[[[1,2],[2,3]],[]],"check":"4","expected":[[[1,2],[2,3],[4,1]],[]],"passed":false},{"actual":[[],[]],"check":"5","expected":[[],[]],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"0\", \"actual\": [[[1, 1], [1, 3], [2, 2]], [[3, 4]]], \"expected\": [[[1, 1], [1, 3], [2, 2]], [[3, 4]]], \"passed\": true}, {\"check\": \"1\", \"actual\": [[[1, 1]], []], \"expected\": [[[1, 1]], []], \"passed\": true}, {\"check\": \"2\", \"actual\": [[], [[1, 1]]], \"expected\": [[], [[1, 1]]], \"passed\": true}, {\"check\": \"3\", \"actual\": [[[1, 1], [1, 2], [1, 3]], []], \"expected\": [[[1, 1], [1, 2], [1, 3]], []], \"passed\": true}, {\"check\": \"4\", \"actual\": [[[1, 2], [2, 3]], []], \"expected\": [[[1, 2], [2, 3], [4, 1]], []], \"passed\": false}, {\"check\": \"5\", \"actual\": [[], []], \"expected\": [[], []], \"passed\": true}], \"passed\": false}\n"},"broken":{"elapsed_ms":41.38,"exit_code":1,"observations":[{"actual":[[[1,1],[1,3],[2,2]],[[3,4]]],"check":"0","expected":[[[1,1],[1,3],[2,2]],[[3,4]]],"passed":true},{"actual":[[],[]],"check":"1","expected":[[[1,1]],[]],"passed":false},{"actual":[[],[[1,1]]],"check":"2","expected":[[],[[1,1]]],"passed":true},{"actual":[[[1,1],[1,2],[1,3]],[]],"check":"3","expected":[[[1,1],[1,2],[1,3]],[]],"passed":true},{"actual":[[[1,2],[2,3]],[]],"check":"4","expected":[[[1,2],[2,3],[4,1]],[]],"passed":false},{"actual":[[],[]],"check":"5","expected":[[],[]],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"0\", \"actual\": [[[1, 1], [1, 3], [2, 2]], [[3, 4]]], \"expected\": [[[1, 1], [1, 3], [2, 2]], [[3, 4]]], \"passed\": true}, {\"check\": \"1\", \"actual\": [[], []], \"expected\": [[[1, 1]], []], \"passed\": false}, {\"check\": \"2\", \"actual\": [[], [[1, 1]]], \"expected\": [[], [[1, 1]]], \"passed\": true}, {\"check\": \"3\", \"actual\": [[[1, 1], [1, 2], [1, 3]], []], \"expected\": [[[1, 1], [1, 2], [1, 3]], []], \"passed\": true}, {\"check\": \"4\", \"actual\": [[[1, 2], [2, 3]], []], \"expected\": [[[1, 2], [2, 3], [4, 1]], []], \"passed\": false}, {\"check\": \"5\", \"actual\": [[], []], \"expected\": [[], []], \"passed\": true}], \"passed\": false}\n"},"fixed":{"elapsed_ms":43.899,"exit_code":0,"observations":[{"actual":[[[1,1],[1,3],[2,2]],[[3,4]]],"check":"0","expected":[[[1,1],[1,3],[2,2]],[[3,4]]],"passed":true},{"actual":[[[1,1]],[]],"check":"1","expected":[[[1,1]],[]],"passed":true},{"actual":[[],[[1,1]]],"check":"2","expected":[[],[[1,1]]],"passed":true},{"actual":[[[1,1],[1,2],[1,3]],[]],"check":"3","expected":[[[1,1],[1,2],[1,3]],[]],"passed":true},{"actual":[[[1,2],[2,3],[4,1]],[]],"check":"4","expected":[[[1,2],[2,3],[4,1]],[]],"passed":true},{"actual":[[],[]],"check":"5","expected":[[],[]],"passed":true}],"passed":true,"stderr":"","stdout":"{\"observations\": [{\"check\": \"0\", \"actual\": [[[1, 1], [1, 3], [2, 2]], [[3, 4]]], \"expected\": [[[1, 1], [1, 3], [2, 2]], [[3, 4]]], \"passed\": true}, {\"check\": \"1\", \"actual\": [[[1, 1]], []], \"expected\": [[[1, 1]], []], \"passed\": true}, {\"check\": \"2\", \"actual\": [[], [[1, 1]]], \"expected\": [[], [[1, 1]]], \"passed\": true}, {\"check\": \"3\", \"actual\": [[[1, 1], [1, 2], [1, 3]], []], \"expected\": [[[1, 1], [1, 2], [1, 3]], []], \"passed\": true}, {\"check\": \"4\", \"actual\": [[[1, 2], [2, 3], [4, 1]], []], \"expected\": [[[1, 2], [2, 3], [4, 1]], []], \"passed\": true}, {\"check\": \"5\", \"actual\": [[], []], \"expected\": [[], []], \"passed\": true}], \"passed\": true}\n"}},"verified":true,"visibility":"public"}