{"abstract":"Files whose distance equals max_d are treated as too different.","category":"Text diff and three-way merge","checks":10,"contract":"Compute the minimum number of line insertions plus deletions between a and b using the greedy furthest-reaching diagonal method: for d = 0..min(max_d, n+m), for k = -d..d step 2 choose the start x from diagonal k+1 when k == -d or (k != d and V[k-1] < V[k+1]), else V[k-1]+1; follow the snake of equal elements; return d once x >= n and y >= m. Return None when the distance exceeds max_d.","contract_signature":"a, b, max_d","evaluation_group":"w2-text-diff-merge-myers-edit-distance","failed_approach":"Capping at n+m-1 fails when every line differs and the distance is exactly n+m.","family":"w2-text-diff-merge-myers-edit-distance-distance-cap","id":"FA-75381","implementations":{"attempt":{"sha256":"bbcd45bff097431bf5f9f17b363c56d49dd317f688c1ed2bc63c17b1e6afa33e","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(a, b, max_d):\n    n, m = len(a), len(b)\n    off = n + m + 1\n    v = [0] * (2 * off + 2)\n    for d in range(0, min(max_d, n + m - 1) + 1):\n        for k in range(-d, d + 1, 2):\n            if k == -d or (k != d and v[off + k - 1] < v[off + k + 1]):\n                x = v[off + k + 1]\n            else:\n                x = v[off + k - 1] + 1\n            y = x - k\n            while x < n and y < m and a[x] == b[y]:\n                x += 1\n                y += 1\n            v[off + k] = x\n            if x >= n and y >= m:\n                return d\n    return None\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = {\n    1: [('classic example', [['a', 'b', 'c', 'a', 'b', 'b', 'a'], ['c', 'b', 'a', 'b', 'a', 'c'], 20], 5), ('identical', [['x'], ['x'], 5], 0), ('all different', [['a', 'b'], ['c', 'd'], 10], 4), ('cap equal to distance', [['a', 'b', 'c'], ['a', 'b', 'd'], 2], 2), ('cap below distance', [['a', 'b', 'c', 'd'], ['w', 'x', 'y', 'z'], 4], None), ('one side empty', [[], ['q'], 2], 1), ('insert in the middle', [['a', 'a', 'a', 'a'], ['a', 'a', 'b', 'a', 'a'], 4], 1), ('long snakes', [['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'], ['a', 'b', 'c', 'X', 'd', 'e', 'f', 'g'], 9], 2), ('distance exactly the total length', [['a', 'b'], ['c', 'd', 'e'], 5], 5), ('single edits scattered', [['a', 'b', 'c', 'd', 'e', 'f', 'g'], ['b', 'c', 'd', 'x', 'e', 'f', 'g', 'y'], 12], 3)],\n    2: [('classic example', [['a', 'b', 'c', 'a', 'b', 'b', 'a'], ['c', 'b', 'a', 'b', 'a', 'c'], 20], 5), ('identical', [['x', 'x'], ['x', 'x'], 5], 0), ('all different', [['a', 'b'], ['c', 'd'], 10], 4), ('cap equal to distance', [['a', 'b', 'c'], ['a', 'b', 'd'], 2], 2), ('cap below distance', [['a', 'b', 'c', 'd'], ['w', 'x', 'y', 'z'], 3], None), ('one side empty', [[], ['q', 'q'], 3], 2), ('insert in the middle', [['a', 'a', 'a', 'a'], ['a', 'a', 'b', 'a', 'a'], 4], 1), ('long snakes', [['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'], ['a', 'b', 'c', 'X', 'd', 'e', 'f', 'g', 'h'], 9], 1), ('distance exactly the total length', [['a', 'b'], ['c', 'd', 'e'], 5], 5), ('single edits scattered', [['a', 'b', 'c', 'd', 'e', 'f', 'g'], ['b', 'c', 'd', 'x', 'e', 'f', 'g', 'y'], 12], 3)],\n    3: [('classic example', [['a', 'b', 'c', 'a', 'b', 'b', 'a'], ['c', 'b', 'a', 'b', 'a', 'c'], 20], 5), ('identical', [['x', 'x', 'x'], ['x', 'x', 'x'], 5], 0), ('all different', [['a', 'b'], ['c', 'd'], 10], 4), ('cap equal to distance', [['a', 'b', 'c'], ['a', 'b', 'd'], 2], 2), ('cap below distance', [['a', 'b', 'c', 'd'], ['w', 'x', 'y', 'z'], 4], None), ('one side empty', [[], ['q', 'q', 'q'], 4], 3), ('insert in the middle', [['a', 'a', 'a', 'a'], ['a', 'a', 'b', 'a', 'a'], 4], 1), ('long snakes', [['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'], ['a', 'b', 'c', 'X', 'd', 'e', 'f', 'g'], 9], 2), ('distance exactly the total length', [['a', 'b'], ['c', 'd', 'e'], 5], 5), ('single edits scattered', [['a', 'b', 'c', 'd', 'e', 'f', 'g'], ['b', 'c', 'd', 'x', 'e', 'f', 'g', 'y'], 12], 3)],\n    4: [('classic example', [['a', 'b', 'c', 'a', 'b', 'b', 'a'], ['c', 'b', 'a', 'b', 'a', 'c'], 20], 5), ('identical', [['x', 'x', 'x', 'x'], ['x', 'x', 'x', 'x'], 5], 0), ('all different', [['a', 'b'], ['c', 'd'], 10], 4), ('cap equal to distance', [['a', 'b', 'c'], ['a', 'b', 'd'], 2], 2), ('cap below distance', [['a', 'b', 'c', 'd'], ['w', 'x', 'y', 'z'], 3], None), ('one side empty', [[], ['q', 'q', 'q', 'q'], 5], 4), ('insert in the middle', [['a', 'a', 'a', 'a'], ['a', 'a', 'b', 'a', 'a'], 4], 1), ('long snakes', [['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'], ['a', 'b', 'c', 'X', 'd', 'e', 'f', 'g', 'h'], 9], 1), ('distance exactly the total length', [['a', 'b'], ['c', 'd', 'e'], 5], 5), ('single edits scattered', [['a', 'b', 'c', 'd', 'e', 'f', 'g'], ['b', 'c', 'd', 'x', 'e', 'f', 'g', 'y'], 12], 3)],\n    5: [('classic example', [['a', 'b', 'c', 'a', 'b', 'b', 'a'], ['c', 'b', 'a', 'b', 'a', 'c'], 20], 5), ('identical', [['x', 'x', 'x', 'x', 'x'], ['x', 'x', 'x', 'x', 'x'], 5], 0), ('all different', [['a', 'b'], ['c', 'd'], 10], 4), ('cap equal to distance', [['a', 'b', 'c'], ['a', 'b', 'd'], 2], 2), ('cap below distance', [['a', 'b', 'c', 'd'], ['w', 'x', 'y', 'z'], 4], None), ('one side empty', [[], ['q', 'q', 'q', 'q', 'q'], 6], 5), ('insert in the middle', [['a', 'a', 'a', 'a'], ['a', 'a', 'b', 'a', 'a'], 4], 1), ('long snakes', [['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'], ['a', 'b', 'c', 'X', 'd', 'e', 'f', 'g'], 9], 2), ('distance exactly the total length', [['a', 'b'], ['c', 'd', 'e'], 5], 5), ('single edits scattered', [['a', 'b', 'c', 'd', 'e', 'f', 'g'], ['b', 'c', 'd', 'x', 'e', 'f', 'g', 'y'], 12], 3)],\n}[N]\nfor label, args, expected in cases:\n    check(label, solve(*args), expected)\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":"47506fc013870dfd5ddddffa1c42859c2a9ba3dd44ba5704ea947e4d01e37bbf","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(a, b, max_d):\n    n, m = len(a), len(b)\n    off = n + m + 1\n    v = [0] * (2 * off + 2)\n    for d in range(0, min(max_d, n + m)):\n        for k in range(-d, d + 1, 2):\n            if k == -d or (k != d and v[off + k - 1] < v[off + k + 1]):\n                x = v[off + k + 1]\n            else:\n                x = v[off + k - 1] + 1\n            y = x - k\n            while x < n and y < m and a[x] == b[y]:\n                x += 1\n                y += 1\n            v[off + k] = x\n            if x >= n and y >= m:\n                return d\n    return None\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = {\n    1: [('classic example', [['a', 'b', 'c', 'a', 'b', 'b', 'a'], ['c', 'b', 'a', 'b', 'a', 'c'], 20], 5), ('identical', [['x'], ['x'], 5], 0), ('all different', [['a', 'b'], ['c', 'd'], 10], 4), ('cap equal to distance', [['a', 'b', 'c'], ['a', 'b', 'd'], 2], 2), ('cap below distance', [['a', 'b', 'c', 'd'], ['w', 'x', 'y', 'z'], 4], None), ('one side empty', [[], ['q'], 2], 1), ('insert in the middle', [['a', 'a', 'a', 'a'], ['a', 'a', 'b', 'a', 'a'], 4], 1), ('long snakes', [['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'], ['a', 'b', 'c', 'X', 'd', 'e', 'f', 'g'], 9], 2), ('distance exactly the total length', [['a', 'b'], ['c', 'd', 'e'], 5], 5), ('single edits scattered', [['a', 'b', 'c', 'd', 'e', 'f', 'g'], ['b', 'c', 'd', 'x', 'e', 'f', 'g', 'y'], 12], 3)],\n    2: [('classic example', [['a', 'b', 'c', 'a', 'b', 'b', 'a'], ['c', 'b', 'a', 'b', 'a', 'c'], 20], 5), ('identical', [['x', 'x'], ['x', 'x'], 5], 0), ('all different', [['a', 'b'], ['c', 'd'], 10], 4), ('cap equal to distance', [['a', 'b', 'c'], ['a', 'b', 'd'], 2], 2), ('cap below distance', [['a', 'b', 'c', 'd'], ['w', 'x', 'y', 'z'], 3], None), ('one side empty', [[], ['q', 'q'], 3], 2), ('insert in the middle', [['a', 'a', 'a', 'a'], ['a', 'a', 'b', 'a', 'a'], 4], 1), ('long snakes', [['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'], ['a', 'b', 'c', 'X', 'd', 'e', 'f', 'g', 'h'], 9], 1), ('distance exactly the total length', [['a', 'b'], ['c', 'd', 'e'], 5], 5), ('single edits scattered', [['a', 'b', 'c', 'd', 'e', 'f', 'g'], ['b', 'c', 'd', 'x', 'e', 'f', 'g', 'y'], 12], 3)],\n    3: [('classic example', [['a', 'b', 'c', 'a', 'b', 'b', 'a'], ['c', 'b', 'a', 'b', 'a', 'c'], 20], 5), ('identical', [['x', 'x', 'x'], ['x', 'x', 'x'], 5], 0), ('all different', [['a', 'b'], ['c', 'd'], 10], 4), ('cap equal to distance', [['a', 'b', 'c'], ['a', 'b', 'd'], 2], 2), ('cap below distance', [['a', 'b', 'c', 'd'], ['w', 'x', 'y', 'z'], 4], None), ('one side empty', [[], ['q', 'q', 'q'], 4], 3), ('insert in the middle', [['a', 'a', 'a', 'a'], ['a', 'a', 'b', 'a', 'a'], 4], 1), ('long snakes', [['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'], ['a', 'b', 'c', 'X', 'd', 'e', 'f', 'g'], 9], 2), ('distance exactly the total length', [['a', 'b'], ['c', 'd', 'e'], 5], 5), ('single edits scattered', [['a', 'b', 'c', 'd', 'e', 'f', 'g'], ['b', 'c', 'd', 'x', 'e', 'f', 'g', 'y'], 12], 3)],\n    4: [('classic example', [['a', 'b', 'c', 'a', 'b', 'b', 'a'], ['c', 'b', 'a', 'b', 'a', 'c'], 20], 5), ('identical', [['x', 'x', 'x', 'x'], ['x', 'x', 'x', 'x'], 5], 0), ('all different', [['a', 'b'], ['c', 'd'], 10], 4), ('cap equal to distance', [['a', 'b', 'c'], ['a', 'b', 'd'], 2], 2), ('cap below distance', [['a', 'b', 'c', 'd'], ['w', 'x', 'y', 'z'], 3], None), ('one side empty', [[], ['q', 'q', 'q', 'q'], 5], 4), ('insert in the middle', [['a', 'a', 'a', 'a'], ['a', 'a', 'b', 'a', 'a'], 4], 1), ('long snakes', [['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'], ['a', 'b', 'c', 'X', 'd', 'e', 'f', 'g', 'h'], 9], 1), ('distance exactly the total length', [['a', 'b'], ['c', 'd', 'e'], 5], 5), ('single edits scattered', [['a', 'b', 'c', 'd', 'e', 'f', 'g'], ['b', 'c', 'd', 'x', 'e', 'f', 'g', 'y'], 12], 3)],\n    5: [('classic example', [['a', 'b', 'c', 'a', 'b', 'b', 'a'], ['c', 'b', 'a', 'b', 'a', 'c'], 20], 5), ('identical', [['x', 'x', 'x', 'x', 'x'], ['x', 'x', 'x', 'x', 'x'], 5], 0), ('all different', [['a', 'b'], ['c', 'd'], 10], 4), ('cap equal to distance', [['a', 'b', 'c'], ['a', 'b', 'd'], 2], 2), ('cap below distance', [['a', 'b', 'c', 'd'], ['w', 'x', 'y', 'z'], 4], None), ('one side empty', [[], ['q', 'q', 'q', 'q', 'q'], 6], 5), ('insert in the middle', [['a', 'a', 'a', 'a'], ['a', 'a', 'b', 'a', 'a'], 4], 1), ('long snakes', [['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'], ['a', 'b', 'c', 'X', 'd', 'e', 'f', 'g'], 9], 2), ('distance exactly the total length', [['a', 'b'], ['c', 'd', 'e'], 5], 5), ('single edits scattered', [['a', 'b', 'c', 'd', 'e', 'f', 'g'], ['b', 'c', 'd', 'x', 'e', 'f', 'g', 'y'], 12], 3)],\n}[N]\nfor label, args, expected in cases:\n    check(label, solve(*args), expected)\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 deterministic, bounded teaching model of one diff, patch or merge rule with stipulated conventions; it is not a production diff or version-control implementation and makes no claim of conformance to any specific tool. 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":"w2-text-diff-merge-myers-edit-distance-distance-cap","generated_at":"2026-09-29T14:49:05.967483+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"Diff engines use Myers' O(ND) algorithm with a cap on D to bound work on very different files.","root_cause":"The d loop stops one short of the cap.","sha256":"fa4ae7e9e7f2f8e75bdb23e0d7aa956423dbe87e9a2f84c02910a1c1eb98c798","title":"Myers greedy edit distance: a distance equal to the cap is reported as exceeded · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verified":true,"visibility":"public","verification":{"attempt":{"elapsed_ms":42.541,"exit_code":1,"observations":[{"actual":5,"check":"classic example","expected":5,"passed":true},{"actual":0,"check":"identical","expected":0,"passed":true},{"actual":null,"check":"all different","expected":4,"passed":false},{"actual":2,"check":"cap equal to distance","expected":2,"passed":true},{"actual":null,"check":"cap below distance","expected":null,"passed":true},{"actual":null,"check":"one side empty","expected":1,"passed":false},{"actual":1,"check":"insert in the middle","expected":1,"passed":true},{"actual":2,"check":"long snakes","expected":2,"passed":true},{"actual":null,"check":"distance exactly the total length","expected":5,"passed":false},{"actual":3,"check":"single edits scattered","expected":3,"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"classic example\", \"actual\": 5, \"expected\": 5, \"passed\": true}, {\"check\": \"identical\", \"actual\": 0, \"expected\": 0, \"passed\": true}, {\"check\": \"all different\", \"actual\": null, \"expected\": 4, \"passed\": false}, {\"check\": \"cap equal to distance\", \"actual\": 2, \"expected\": 2, \"passed\": true}, {\"check\": \"cap below distance\", \"actual\": null, \"expected\": null, \"passed\": true}, {\"check\": \"one side empty\", \"actual\": null, \"expected\": 1, \"passed\": false}, {\"check\": \"insert in the middle\", \"actual\": 1, \"expected\": 1, \"passed\": true}, {\"check\": \"long snakes\", \"actual\": 2, \"expected\": 2, \"passed\": true}, {\"check\": \"distance exactly the total length\", \"actual\": null, \"expected\": 5, \"passed\": false}, {\"check\": \"single edits scattered\", \"actual\": 3, \"expected\": 3, \"passed\": true}], \"passed\": false}\n"},"broken":{"elapsed_ms":41.073,"exit_code":1,"observations":[{"actual":5,"check":"classic example","expected":5,"passed":true},{"actual":0,"check":"identical","expected":0,"passed":true},{"actual":null,"check":"all different","expected":4,"passed":false},{"actual":null,"check":"cap equal to distance","expected":2,"passed":false},{"actual":null,"check":"cap below distance","expected":null,"passed":true},{"actual":null,"check":"one side empty","expected":1,"passed":false},{"actual":1,"check":"insert in the middle","expected":1,"passed":true},{"actual":2,"check":"long snakes","expected":2,"passed":true},{"actual":null,"check":"distance exactly the total length","expected":5,"passed":false},{"actual":3,"check":"single edits scattered","expected":3,"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"classic example\", \"actual\": 5, \"expected\": 5, \"passed\": true}, {\"check\": \"identical\", \"actual\": 0, \"expected\": 0, \"passed\": true}, {\"check\": \"all different\", \"actual\": null, \"expected\": 4, \"passed\": false}, {\"check\": \"cap equal to distance\", \"actual\": null, \"expected\": 2, \"passed\": false}, {\"check\": \"cap below distance\", \"actual\": null, \"expected\": null, \"passed\": true}, {\"check\": \"one side empty\", \"actual\": null, \"expected\": 1, \"passed\": false}, {\"check\": \"insert in the middle\", \"actual\": 1, \"expected\": 1, \"passed\": true}, {\"check\": \"long snakes\", \"actual\": 2, \"expected\": 2, \"passed\": true}, {\"check\": \"distance exactly the total length\", \"actual\": null, \"expected\": 5, \"passed\": false}, {\"check\": \"single edits scattered\", \"actual\": 3, \"expected\": 3, \"passed\": true}], \"passed\": false}\n"}},"member_only":{"stages":["fixed"],"fields":["implementations.fixed","verification.fixed","harness","repair"],"note":"The verified repair, its recorded checks, the repair description, and the scoring harness are available to members."}}