{"abstract":"Pairs with equal minimum x are reported twice.","category":"Collision detection broadphase","checks":8,"contract":"solve(A, B): bipartite box pruning (dynamic set A vs static set B), boxes [id,minx,miny,maxx,maxy], closed intervals. Sort both by (minx,id). Pass 1: for each a, B boxes with minx in [a.minx, a.maxx]; pass 2: for each b, A boxes with minx in (b.minx, b.maxx]; y overlap required. Return sorted [a id, b id] pairs.","evaluation_group":"w2-collision_detection_broadphase-bipartite-box-pruning","failed_approach":"Making pass 1 skip ties as well loses equal-start pairs entirely.","family":"w2-collision_detection_broadphase-bipartite-box-pruning-equal-start-ownership","id":"FA-87761","implementations":{"attempt":{"sha256":"8e4ed7b2b30056913009e65e09ac76121da3d2f0acd9256a9a5511f9f2e0ec64","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nimport math\nN = 1\nobservations = []\ndef solve(A, B):\n    As = sorted(A, key=lambda r: (r[1], r[0]))\n    Bs = sorted(B, key=lambda r: (r[1], r[0]))\n    def yover(p, q):\n        return p[2] <= q[4] and q[2] <= p[4]\n    pairs = []\n    j = 0\n    for a in As:\n        while j < len(Bs) and Bs[j][1] <= a[1]:\n            j += 1\n        k = j\n        while k < len(Bs) and Bs[k][1] <= a[3]:\n            if yover(a, Bs[k]):\n                pairs.append([a[0], Bs[k][0]])\n            k += 1\n    j2 = 0\n    for b in Bs:\n        while j2 < len(As) and As[j2][1] <= b[1]:\n            j2 += 1\n        k = j2\n        while k < len(As) and As[k][1] <= b[3]:\n            if yover(As[k], b):\n                pairs.append([As[k][0], b[0]])\n            k += 1\n    pairs.sort()\n    return pairs\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\nfixtures = [[[[[[22, 5.0, -3.0, 7.0, -3.0]], [[6, 5.0, 1.0, 5.0, 2.0], [4, 1.0, 0.0, 4.0, 0.0]]], []], [[[[33, 0.0, 3.0, 0.0, 5.0], [32, 2.0, 3.0, 4.0, 5.0], [11, -5.0, -4.0, -5.0, -4.0]], [[8, 0.0, -2.0, 5.0, -2.0]]], []], [[[[39, 2.0, 0.0, 5.0, 2.0], [24, 3.0, -3.0, 4.0, -2.0]], [[9, 2.0, 2.0, 2.0, 3.0], [17, 3.0, 3.0, 5.0, 3.0]]], [[39, 9]]], [[[[29, -3.0, -4.0, -3.0, -1.0], [37, 5.0, 0.0, 5.0, 0.0], [14, -1.0, 2.0, 0.0, 3.0]], [[1, -3.0, -1.0, 3.0, -1.0], [20, 4.0, 0.0, 5.0, 3.0]]], [[29, 1], [37, 20]]], [[[[14, -3.0, 4.0, 0.0, 5.0], [11, -5.0, -1.0, -5.0, -1.0], [7, 5.0, 5.0, 6.0, 8.0]], [[9, -3.0, 2.0, 6.0, 2.0]]], []], [[[[33, 3.0, 3.0, 6.0, 6.0], [9, -4.0, 4.0, -2.0, 6.0], [26, -1.0, -5.0, -1.0, -4.0], [12, 1.0, 4.0, 2.0, 4.0]], [[19, 3.0, 0.0, 7.0, 3.0], [5, -3.0, 5.0, -1.0, 5.0], [18, 1.0, -3.0, 4.0, 0.0], [30, 5.0, -3.0, 7.0, 0.0]]], [[9, 5], [33, 19]]], [[[[4, -5.0, -1.0, -2.0, 1.0], [2, 5.0, -3.0, 5.0, -2.0], [29, -5.0, 2.0, -2.0, 5.0]], [[27, -5.0, 2.0, -1.0, 2.0], [18, 0.0, -5.0, 1.0, -5.0], [37, 3.0, -3.0, 4.0, -3.0], [11, -4.0, -5.0, -2.0, -3.0]]], [[29, 27]]], [[[[4, -3.0, -5.0, -3.0, -5.0], [11, 5.0, -4.0, 6.0, -3.0]], [[26, 5.0, -3.0, 5.0, 0.0]]], [[11, 26]]]], [[[[[35, 5.0, -2.0, 7.0, -2.0], [22, -2.0, 0.0, 0.0, 0.0], [29, 4.0, -2.0, 6.0, 1.0]], [[30, 5.0, -2.0, 5.0, 1.0], [9, 2.0, 2.0, 2.0, 3.0], [19, -1.0, 1.0, -1.0, 3.0]]], [[29, 30], [35, 30]]], [[[[24, -3.0, 5.0, 0.0, 7.0], [22, 2.0, 0.0, 5.0, 2.0]], [[19, -3.0, -2.0, 5.0, -2.0]]], []], [[[[26, 1.0, -5.0, 4.0, -4.0], [15, -3.0, -2.0, -3.0, -2.0], [35, -4.0, 2.0, -2.0, 4.0]], [[22, -2.0, -5.0, -1.0, -3.0], [29, -3.0, -5.0, -1.0, -5.0], [37, 2.0, 4.0, 5.0, 4.0]]], []], [[[[17, -5.0, -3.0, -4.0, 0.0], [22, -5.0, 4.0, -5.0, 5.0]], [[23, -5.0, 1.0, 0.0, 1.0], [3, 5.0, -4.0, 5.0, -4.0], [6, -1.0, 4.0, 0.0, 7.0], [1, 5.0, -5.0, 7.0, -5.0]]], []], [[[[20, -4.0, -5.0, -4.0, -2.0], [9, 5.0, 2.0, 6.0, 5.0]], [[18, 2.0, 5.0, 4.0, 5.0], [5, 4.0, 3.0, 7.0, 5.0]]], [[9, 5]]], [[[[29, 0.0, 4.0, 0.0, 5.0], [13, -2.0, 0.0, 1.0, 0.0], [26, 5.0, -2.0, 8.0, -2.0]], [[4, 0.0, 5.0, 0.0, 6.0], [32, 3.0, 0.0, 6.0, 1.0]]], [[29, 4]]], [[[[34, 3.0, 2.0, 4.0, 4.0], [11, -2.0, -1.0, -2.0, -1.0], [19, -2.0, -5.0, -1.0, -3.0], [39, 1.0, -2.0, 1.0, 0.0]], [[13, 5.0, -5.0, 8.0, -3.0], [14, -4.0, 1.0, -4.0, 1.0], [8, 1.0, -2.0, 1.0, -1.0], [32, 2.0, -4.0, 2.0, -4.0]]], [[39, 8]]], [[[[23, 0.0, -3.0, 1.0, -1.0]], [[9, 0.0, -1.0, 0.0, 0.0], [30, 4.0, 1.0, 4.0, 4.0], [27, -4.0, -3.0, -1.0, 0.0]]], [[23, 9]]]], [[[[[26, -3.0, 3.0, -1.0, 3.0], [12, 3.0, -2.0, 6.0, 1.0], [38, 1.0, -2.0, 4.0, -1.0], [31, 5.0, -5.0, 8.0, -4.0]], [[9, -5.0, -2.0, -2.0, 1.0]]], []], [[[[13, -2.0, 5.0, -2.0, 5.0]], [[19, -1.0, -3.0, -1.0, -1.0]]], []], [[[[26, -1.0, 1.0, 0.0, 1.0]], [[15, 1.0, -1.0, 2.0, -1.0], [10, 4.0, 5.0, 7.0, 6.0], [34, -5.0, -1.0, -4.0, -1.0]]], []], [[[[26, -3.0, 0.0, -3.0, 3.0]], [[28, -2.0, -3.0, -2.0, -2.0], [20, 1.0, 3.0, 1.0, 3.0], [29, 2.0, 4.0, 2.0, 5.0], [19, -3.0, 0.0, -2.0, 3.0]]], [[26, 19]]], [[[[36, 2.0, 4.0, 4.0, 4.0], [32, -3.0, -4.0, -3.0, -2.0], [37, -3.0, -4.0, -2.0, -4.0], [12, 5.0, -2.0, 5.0, 1.0]], [[22, 2.0, 4.0, 2.0, 4.0], [5, 4.0, 2.0, 7.0, 5.0]]], [[36, 5], [36, 22]]], [[[[1, -4.0, -5.0, -2.0, -2.0], [28, -5.0, -2.0, -5.0, 0.0], [3, 2.0, -3.0, 4.0, 0.0], [11, -5.0, -1.0, -3.0, 1.0]], [[9, 2.0, 3.0, 2.0, 5.0], [21, 5.0, -5.0, 6.0, -4.0]]], []], [[[[27, 0.0, 3.0, 0.0, 6.0], [12, -4.0, 4.0, -3.0, 7.0], [8, -3.0, -1.0, -1.0, -1.0]], [[4, -1.0, -4.0, -1.0, -1.0], [16, -5.0, -4.0, -4.0, -3.0], [28, -4.0, 5.0, -2.0, 5.0], [5, -1.0, 4.0, 2.0, 5.0]]], [[8, 4], [12, 28], [27, 5]]], [[[[5, 4.0, 1.0, 5.0, 4.0]], [[15, 4.0, 4.0, 4.0, 4.0]]], [[5, 15]]]], [[[[[8, -2.0, 0.0, 1.0, 1.0], [9, -2.0, -1.0, 1.0, 2.0], [1, 1.0, -3.0, 3.0, -2.0]], [[35, -2.0, 0.0, 3.0, 2.0], [14, 2.0, -1.0, 3.0, 1.0]]], [[8, 35], [9, 35]]], [[[[25, 0.0, -5.0, 0.0, -2.0], [24, 3.0, 5.0, 3.0, 7.0], [1, -3.0, 5.0, -3.0, 8.0], [30, -2.0, -1.0, -1.0, 2.0]], [[13, 0.0, -2.0, 2.0, 1.0], [39, -5.0, 3.0, -4.0, 5.0], [2, 4.0, 5.0, 4.0, 7.0], [7, 0.0, 3.0, 0.0, 5.0]]], [[25, 13]]], [[[[29, 5.0, -4.0, 6.0, -4.0], [7, 5.0, 4.0, 6.0, 7.0]], [[36, 1.0, -4.0, 4.0, -1.0], [27, 1.0, 2.0, 3.0, 3.0], [19, 2.0, 2.0, 3.0, 3.0]]], []], [[[[18, -5.0, 2.0, -2.0, 2.0], [34, -5.0, -3.0, -3.0, -3.0], [13, -5.0, 4.0, -2.0, 6.0]], [[32, -5.0, 5.0, 8.0, 6.0]]], [[13, 32]]], [[[[15, 3.0, -1.0, 3.0, -1.0]], [[35, 3.0, -4.0, 4.0, -1.0], [16, -2.0, 0.0, -2.0, 2.0], [9, 1.0, 4.0, 4.0, 4.0], [27, -4.0, -5.0, -4.0, -4.0]]], [[15, 35]]], [[[[15, 5.0, 2.0, 6.0, 3.0], [27, -3.0, 5.0, -3.0, 6.0]], [[38, 5.0, 2.0, 5.0, 2.0]]], [[15, 38]]], [[[[35, 4.0, 5.0, 6.0, 8.0], [5, -4.0, 4.0, -3.0, 4.0], [33, 1.0, 5.0, 2.0, 5.0]], [[1, 4.0, 4.0, 4.0, 4.0], [10, -3.0, 4.0, -2.0, 6.0], [17, -1.0, 1.0, 0.0, 3.0], [7, 5.0, -5.0, 7.0, -5.0]]], [[5, 10]]], [[[[35, -3.0, 2.0, -3.0, 4.0], [16, 0.0, 1.0, 1.0, 1.0], [15, -2.0, 4.0, 0.0, 6.0]], [[22, -3.0, -3.0, 2.0, 0.0], [7, 2.0, 1.0, 3.0, 4.0], [6, 5.0, -5.0, 6.0, -4.0]]], []]], [[[[[2, -1.0, 0.0, -1.0, 1.0], [10, -5.0, 2.0, -3.0, 5.0], [19, -4.0, 1.0, -4.0, 4.0]], [[11, 4.0, 3.0, 4.0, 5.0], [14, -2.0, 1.0, 1.0, 2.0]]], [[2, 14]]], [[[[32, 2.0, 1.0, 4.0, 4.0], [10, 2.0, -3.0, 3.0, -2.0]], [[5, -2.0, 5.0, -1.0, 5.0]]], []], [[[[16, -1.0, -4.0, 1.0, -1.0], [31, -5.0, -2.0, -5.0, -1.0]], [[6, -1.0, -4.0, 2.0, -4.0], [9, -2.0, -4.0, -2.0, -1.0], [8, -5.0, -5.0, -4.0, -3.0], [34, 5.0, 1.0, 8.0, 4.0]]], [[16, 6]]], [[[[14, -4.0, -1.0, -2.0, 1.0]], [[20, 3.0, 0.0, 5.0, 2.0], [12, 0.0, -2.0, 1.0, 1.0], [19, 4.0, -2.0, 5.0, -1.0]]], []], [[[[14, -5.0, -5.0, -5.0, -5.0], [26, -3.0, -1.0, -1.0, 1.0], [20, 1.0, 3.0, 3.0, 4.0]], [[10, -5.0, -5.0, 2.0, -4.0]]], [[14, 10]]], [[[[29, -2.0, 0.0, 0.0, 3.0]], [[36, -4.0, 5.0, -2.0, 6.0], [1, -2.0, -1.0, -1.0, 2.0]]], [[29, 1]]], [[[[7, -2.0, 0.0, -1.0, 0.0], [15, 5.0, -5.0, 5.0, -5.0], [16, -1.0, -2.0, 2.0, -2.0], [39, 0.0, -1.0, 0.0, 0.0]], [[13, -2.0, 2.0, 3.0, 5.0]]], []], [[[[14, -4.0, 5.0, -2.0, 8.0]], [[8, -4.0, 3.0, -1.0, 6.0], [17, 3.0, -4.0, 6.0, -1.0]]], [[14, 8]]]]]\nfor i, (args, expected) in enumerate(fixtures[N-1]):\n    check(\"case %d\" % i, 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":"59a13299ca60b94a14edd28ed2ec0388b70b175ac0fa114b827934796b66c75d","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nimport math\nN = 1\nobservations = []\ndef solve(A, B):\n    As = sorted(A, key=lambda r: (r[1], r[0]))\n    Bs = sorted(B, key=lambda r: (r[1], r[0]))\n    def yover(p, q):\n        return p[2] <= q[4] and q[2] <= p[4]\n    pairs = []\n    j = 0\n    for a in As:\n        while j < len(Bs) and Bs[j][1] < a[1]:\n            j += 1\n        k = j\n        while k < len(Bs) and Bs[k][1] <= a[3]:\n            if yover(a, Bs[k]):\n                pairs.append([a[0], Bs[k][0]])\n            k += 1\n    j2 = 0\n    for b in Bs:\n        while j2 < len(As) and As[j2][1] < b[1]:\n            j2 += 1\n        k = j2\n        while k < len(As) and As[k][1] <= b[3]:\n            if yover(As[k], b):\n                pairs.append([As[k][0], b[0]])\n            k += 1\n    pairs.sort()\n    return pairs\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\nfixtures = [[[[[[22, 5.0, -3.0, 7.0, -3.0]], [[6, 5.0, 1.0, 5.0, 2.0], [4, 1.0, 0.0, 4.0, 0.0]]], []], [[[[33, 0.0, 3.0, 0.0, 5.0], [32, 2.0, 3.0, 4.0, 5.0], [11, -5.0, -4.0, -5.0, -4.0]], [[8, 0.0, -2.0, 5.0, -2.0]]], []], [[[[39, 2.0, 0.0, 5.0, 2.0], [24, 3.0, -3.0, 4.0, -2.0]], [[9, 2.0, 2.0, 2.0, 3.0], [17, 3.0, 3.0, 5.0, 3.0]]], [[39, 9]]], [[[[29, -3.0, -4.0, -3.0, -1.0], [37, 5.0, 0.0, 5.0, 0.0], [14, -1.0, 2.0, 0.0, 3.0]], [[1, -3.0, -1.0, 3.0, -1.0], [20, 4.0, 0.0, 5.0, 3.0]]], [[29, 1], [37, 20]]], [[[[14, -3.0, 4.0, 0.0, 5.0], [11, -5.0, -1.0, -5.0, -1.0], [7, 5.0, 5.0, 6.0, 8.0]], [[9, -3.0, 2.0, 6.0, 2.0]]], []], [[[[33, 3.0, 3.0, 6.0, 6.0], [9, -4.0, 4.0, -2.0, 6.0], [26, -1.0, -5.0, -1.0, -4.0], [12, 1.0, 4.0, 2.0, 4.0]], [[19, 3.0, 0.0, 7.0, 3.0], [5, -3.0, 5.0, -1.0, 5.0], [18, 1.0, -3.0, 4.0, 0.0], [30, 5.0, -3.0, 7.0, 0.0]]], [[9, 5], [33, 19]]], [[[[4, -5.0, -1.0, -2.0, 1.0], [2, 5.0, -3.0, 5.0, -2.0], [29, -5.0, 2.0, -2.0, 5.0]], [[27, -5.0, 2.0, -1.0, 2.0], [18, 0.0, -5.0, 1.0, -5.0], [37, 3.0, -3.0, 4.0, -3.0], [11, -4.0, -5.0, -2.0, -3.0]]], [[29, 27]]], [[[[4, -3.0, -5.0, -3.0, -5.0], [11, 5.0, -4.0, 6.0, -3.0]], [[26, 5.0, -3.0, 5.0, 0.0]]], [[11, 26]]]], [[[[[35, 5.0, -2.0, 7.0, -2.0], [22, -2.0, 0.0, 0.0, 0.0], [29, 4.0, -2.0, 6.0, 1.0]], [[30, 5.0, -2.0, 5.0, 1.0], [9, 2.0, 2.0, 2.0, 3.0], [19, -1.0, 1.0, -1.0, 3.0]]], [[29, 30], [35, 30]]], [[[[24, -3.0, 5.0, 0.0, 7.0], [22, 2.0, 0.0, 5.0, 2.0]], [[19, -3.0, -2.0, 5.0, -2.0]]], []], [[[[26, 1.0, -5.0, 4.0, -4.0], [15, -3.0, -2.0, -3.0, -2.0], [35, -4.0, 2.0, -2.0, 4.0]], [[22, -2.0, -5.0, -1.0, -3.0], [29, -3.0, -5.0, -1.0, -5.0], [37, 2.0, 4.0, 5.0, 4.0]]], []], [[[[17, -5.0, -3.0, -4.0, 0.0], [22, -5.0, 4.0, -5.0, 5.0]], [[23, -5.0, 1.0, 0.0, 1.0], [3, 5.0, -4.0, 5.0, -4.0], [6, -1.0, 4.0, 0.0, 7.0], [1, 5.0, -5.0, 7.0, -5.0]]], []], [[[[20, -4.0, -5.0, -4.0, -2.0], [9, 5.0, 2.0, 6.0, 5.0]], [[18, 2.0, 5.0, 4.0, 5.0], [5, 4.0, 3.0, 7.0, 5.0]]], [[9, 5]]], [[[[29, 0.0, 4.0, 0.0, 5.0], [13, -2.0, 0.0, 1.0, 0.0], [26, 5.0, -2.0, 8.0, -2.0]], [[4, 0.0, 5.0, 0.0, 6.0], [32, 3.0, 0.0, 6.0, 1.0]]], [[29, 4]]], [[[[34, 3.0, 2.0, 4.0, 4.0], [11, -2.0, -1.0, -2.0, -1.0], [19, -2.0, -5.0, -1.0, -3.0], [39, 1.0, -2.0, 1.0, 0.0]], [[13, 5.0, -5.0, 8.0, -3.0], [14, -4.0, 1.0, -4.0, 1.0], [8, 1.0, -2.0, 1.0, -1.0], [32, 2.0, -4.0, 2.0, -4.0]]], [[39, 8]]], [[[[23, 0.0, -3.0, 1.0, -1.0]], [[9, 0.0, -1.0, 0.0, 0.0], [30, 4.0, 1.0, 4.0, 4.0], [27, -4.0, -3.0, -1.0, 0.0]]], [[23, 9]]]], [[[[[26, -3.0, 3.0, -1.0, 3.0], [12, 3.0, -2.0, 6.0, 1.0], [38, 1.0, -2.0, 4.0, -1.0], [31, 5.0, -5.0, 8.0, -4.0]], [[9, -5.0, -2.0, -2.0, 1.0]]], []], [[[[13, -2.0, 5.0, -2.0, 5.0]], [[19, -1.0, -3.0, -1.0, -1.0]]], []], [[[[26, -1.0, 1.0, 0.0, 1.0]], [[15, 1.0, -1.0, 2.0, -1.0], [10, 4.0, 5.0, 7.0, 6.0], [34, -5.0, -1.0, -4.0, -1.0]]], []], [[[[26, -3.0, 0.0, -3.0, 3.0]], [[28, -2.0, -3.0, -2.0, -2.0], [20, 1.0, 3.0, 1.0, 3.0], [29, 2.0, 4.0, 2.0, 5.0], [19, -3.0, 0.0, -2.0, 3.0]]], [[26, 19]]], [[[[36, 2.0, 4.0, 4.0, 4.0], [32, -3.0, -4.0, -3.0, -2.0], [37, -3.0, -4.0, -2.0, -4.0], [12, 5.0, -2.0, 5.0, 1.0]], [[22, 2.0, 4.0, 2.0, 4.0], [5, 4.0, 2.0, 7.0, 5.0]]], [[36, 5], [36, 22]]], [[[[1, -4.0, -5.0, -2.0, -2.0], [28, -5.0, -2.0, -5.0, 0.0], [3, 2.0, -3.0, 4.0, 0.0], [11, -5.0, -1.0, -3.0, 1.0]], [[9, 2.0, 3.0, 2.0, 5.0], [21, 5.0, -5.0, 6.0, -4.0]]], []], [[[[27, 0.0, 3.0, 0.0, 6.0], [12, -4.0, 4.0, -3.0, 7.0], [8, -3.0, -1.0, -1.0, -1.0]], [[4, -1.0, -4.0, -1.0, -1.0], [16, -5.0, -4.0, -4.0, -3.0], [28, -4.0, 5.0, -2.0, 5.0], [5, -1.0, 4.0, 2.0, 5.0]]], [[8, 4], [12, 28], [27, 5]]], [[[[5, 4.0, 1.0, 5.0, 4.0]], [[15, 4.0, 4.0, 4.0, 4.0]]], [[5, 15]]]], [[[[[8, -2.0, 0.0, 1.0, 1.0], [9, -2.0, -1.0, 1.0, 2.0], [1, 1.0, -3.0, 3.0, -2.0]], [[35, -2.0, 0.0, 3.0, 2.0], [14, 2.0, -1.0, 3.0, 1.0]]], [[8, 35], [9, 35]]], [[[[25, 0.0, -5.0, 0.0, -2.0], [24, 3.0, 5.0, 3.0, 7.0], [1, -3.0, 5.0, -3.0, 8.0], [30, -2.0, -1.0, -1.0, 2.0]], [[13, 0.0, -2.0, 2.0, 1.0], [39, -5.0, 3.0, -4.0, 5.0], [2, 4.0, 5.0, 4.0, 7.0], [7, 0.0, 3.0, 0.0, 5.0]]], [[25, 13]]], [[[[29, 5.0, -4.0, 6.0, -4.0], [7, 5.0, 4.0, 6.0, 7.0]], [[36, 1.0, -4.0, 4.0, -1.0], [27, 1.0, 2.0, 3.0, 3.0], [19, 2.0, 2.0, 3.0, 3.0]]], []], [[[[18, -5.0, 2.0, -2.0, 2.0], [34, -5.0, -3.0, -3.0, -3.0], [13, -5.0, 4.0, -2.0, 6.0]], [[32, -5.0, 5.0, 8.0, 6.0]]], [[13, 32]]], [[[[15, 3.0, -1.0, 3.0, -1.0]], [[35, 3.0, -4.0, 4.0, -1.0], [16, -2.0, 0.0, -2.0, 2.0], [9, 1.0, 4.0, 4.0, 4.0], [27, -4.0, -5.0, -4.0, -4.0]]], [[15, 35]]], [[[[15, 5.0, 2.0, 6.0, 3.0], [27, -3.0, 5.0, -3.0, 6.0]], [[38, 5.0, 2.0, 5.0, 2.0]]], [[15, 38]]], [[[[35, 4.0, 5.0, 6.0, 8.0], [5, -4.0, 4.0, -3.0, 4.0], [33, 1.0, 5.0, 2.0, 5.0]], [[1, 4.0, 4.0, 4.0, 4.0], [10, -3.0, 4.0, -2.0, 6.0], [17, -1.0, 1.0, 0.0, 3.0], [7, 5.0, -5.0, 7.0, -5.0]]], [[5, 10]]], [[[[35, -3.0, 2.0, -3.0, 4.0], [16, 0.0, 1.0, 1.0, 1.0], [15, -2.0, 4.0, 0.0, 6.0]], [[22, -3.0, -3.0, 2.0, 0.0], [7, 2.0, 1.0, 3.0, 4.0], [6, 5.0, -5.0, 6.0, -4.0]]], []]], [[[[[2, -1.0, 0.0, -1.0, 1.0], [10, -5.0, 2.0, -3.0, 5.0], [19, -4.0, 1.0, -4.0, 4.0]], [[11, 4.0, 3.0, 4.0, 5.0], [14, -2.0, 1.0, 1.0, 2.0]]], [[2, 14]]], [[[[32, 2.0, 1.0, 4.0, 4.0], [10, 2.0, -3.0, 3.0, -2.0]], [[5, -2.0, 5.0, -1.0, 5.0]]], []], [[[[16, -1.0, -4.0, 1.0, -1.0], [31, -5.0, -2.0, -5.0, -1.0]], [[6, -1.0, -4.0, 2.0, -4.0], [9, -2.0, -4.0, -2.0, -1.0], [8, -5.0, -5.0, -4.0, -3.0], [34, 5.0, 1.0, 8.0, 4.0]]], [[16, 6]]], [[[[14, -4.0, -1.0, -2.0, 1.0]], [[20, 3.0, 0.0, 5.0, 2.0], [12, 0.0, -2.0, 1.0, 1.0], [19, 4.0, -2.0, 5.0, -1.0]]], []], [[[[14, -5.0, -5.0, -5.0, -5.0], [26, -3.0, -1.0, -1.0, 1.0], [20, 1.0, 3.0, 3.0, 4.0]], [[10, -5.0, -5.0, 2.0, -4.0]]], [[14, 10]]], [[[[29, -2.0, 0.0, 0.0, 3.0]], [[36, -4.0, 5.0, -2.0, 6.0], [1, -2.0, -1.0, -1.0, 2.0]]], [[29, 1]]], [[[[7, -2.0, 0.0, -1.0, 0.0], [15, 5.0, -5.0, 5.0, -5.0], [16, -1.0, -2.0, 2.0, -2.0], [39, 0.0, -1.0, 0.0, 0.0]], [[13, -2.0, 2.0, 3.0, 5.0]]], []], [[[[14, -4.0, 5.0, -2.0, 8.0]], [[8, -4.0, 3.0, -1.0, 6.0], [17, 3.0, -4.0, 6.0, -1.0]]], [[14, 8]]]]]\nfor i, (args, expected) in enumerate(fixtures[N-1]):\n    check(\"case %d\" % i, 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"},"fixed":{"sha256":"a661ea5a7b7113fa06daa7a361ba3c513f817e9635d685ef055e33fc929f9b26","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nimport math\nN = 1\nobservations = []\ndef solve(A, B):\n    As = sorted(A, key=lambda r: (r[1], r[0]))\n    Bs = sorted(B, key=lambda r: (r[1], r[0]))\n    def yover(p, q):\n        return p[2] <= q[4] and q[2] <= p[4]\n    pairs = []\n    j = 0\n    for a in As:\n        while j < len(Bs) and Bs[j][1] < a[1]:\n            j += 1\n        k = j\n        while k < len(Bs) and Bs[k][1] <= a[3]:\n            if yover(a, Bs[k]):\n                pairs.append([a[0], Bs[k][0]])\n            k += 1\n    j2 = 0\n    for b in Bs:\n        while j2 < len(As) and As[j2][1] <= b[1]:\n            j2 += 1\n        k = j2\n        while k < len(As) and As[k][1] <= b[3]:\n            if yover(As[k], b):\n                pairs.append([As[k][0], b[0]])\n            k += 1\n    pairs.sort()\n    return pairs\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\nfixtures = [[[[[[22, 5.0, -3.0, 7.0, -3.0]], [[6, 5.0, 1.0, 5.0, 2.0], [4, 1.0, 0.0, 4.0, 0.0]]], []], [[[[33, 0.0, 3.0, 0.0, 5.0], [32, 2.0, 3.0, 4.0, 5.0], [11, -5.0, -4.0, -5.0, -4.0]], [[8, 0.0, -2.0, 5.0, -2.0]]], []], [[[[39, 2.0, 0.0, 5.0, 2.0], [24, 3.0, -3.0, 4.0, -2.0]], [[9, 2.0, 2.0, 2.0, 3.0], [17, 3.0, 3.0, 5.0, 3.0]]], [[39, 9]]], [[[[29, -3.0, -4.0, -3.0, -1.0], [37, 5.0, 0.0, 5.0, 0.0], [14, -1.0, 2.0, 0.0, 3.0]], [[1, -3.0, -1.0, 3.0, -1.0], [20, 4.0, 0.0, 5.0, 3.0]]], [[29, 1], [37, 20]]], [[[[14, -3.0, 4.0, 0.0, 5.0], [11, -5.0, -1.0, -5.0, -1.0], [7, 5.0, 5.0, 6.0, 8.0]], [[9, -3.0, 2.0, 6.0, 2.0]]], []], [[[[33, 3.0, 3.0, 6.0, 6.0], [9, -4.0, 4.0, -2.0, 6.0], [26, -1.0, -5.0, -1.0, -4.0], [12, 1.0, 4.0, 2.0, 4.0]], [[19, 3.0, 0.0, 7.0, 3.0], [5, -3.0, 5.0, -1.0, 5.0], [18, 1.0, -3.0, 4.0, 0.0], [30, 5.0, -3.0, 7.0, 0.0]]], [[9, 5], [33, 19]]], [[[[4, -5.0, -1.0, -2.0, 1.0], [2, 5.0, -3.0, 5.0, -2.0], [29, -5.0, 2.0, -2.0, 5.0]], [[27, -5.0, 2.0, -1.0, 2.0], [18, 0.0, -5.0, 1.0, -5.0], [37, 3.0, -3.0, 4.0, -3.0], [11, -4.0, -5.0, -2.0, -3.0]]], [[29, 27]]], [[[[4, -3.0, -5.0, -3.0, -5.0], [11, 5.0, -4.0, 6.0, -3.0]], [[26, 5.0, -3.0, 5.0, 0.0]]], [[11, 26]]]], [[[[[35, 5.0, -2.0, 7.0, -2.0], [22, -2.0, 0.0, 0.0, 0.0], [29, 4.0, -2.0, 6.0, 1.0]], [[30, 5.0, -2.0, 5.0, 1.0], [9, 2.0, 2.0, 2.0, 3.0], [19, -1.0, 1.0, -1.0, 3.0]]], [[29, 30], [35, 30]]], [[[[24, -3.0, 5.0, 0.0, 7.0], [22, 2.0, 0.0, 5.0, 2.0]], [[19, -3.0, -2.0, 5.0, -2.0]]], []], [[[[26, 1.0, -5.0, 4.0, -4.0], [15, -3.0, -2.0, -3.0, -2.0], [35, -4.0, 2.0, -2.0, 4.0]], [[22, -2.0, -5.0, -1.0, -3.0], [29, -3.0, -5.0, -1.0, -5.0], [37, 2.0, 4.0, 5.0, 4.0]]], []], [[[[17, -5.0, -3.0, -4.0, 0.0], [22, -5.0, 4.0, -5.0, 5.0]], [[23, -5.0, 1.0, 0.0, 1.0], [3, 5.0, -4.0, 5.0, -4.0], [6, -1.0, 4.0, 0.0, 7.0], [1, 5.0, -5.0, 7.0, -5.0]]], []], [[[[20, -4.0, -5.0, -4.0, -2.0], [9, 5.0, 2.0, 6.0, 5.0]], [[18, 2.0, 5.0, 4.0, 5.0], [5, 4.0, 3.0, 7.0, 5.0]]], [[9, 5]]], [[[[29, 0.0, 4.0, 0.0, 5.0], [13, -2.0, 0.0, 1.0, 0.0], [26, 5.0, -2.0, 8.0, -2.0]], [[4, 0.0, 5.0, 0.0, 6.0], [32, 3.0, 0.0, 6.0, 1.0]]], [[29, 4]]], [[[[34, 3.0, 2.0, 4.0, 4.0], [11, -2.0, -1.0, -2.0, -1.0], [19, -2.0, -5.0, -1.0, -3.0], [39, 1.0, -2.0, 1.0, 0.0]], [[13, 5.0, -5.0, 8.0, -3.0], [14, -4.0, 1.0, -4.0, 1.0], [8, 1.0, -2.0, 1.0, -1.0], [32, 2.0, -4.0, 2.0, -4.0]]], [[39, 8]]], [[[[23, 0.0, -3.0, 1.0, -1.0]], [[9, 0.0, -1.0, 0.0, 0.0], [30, 4.0, 1.0, 4.0, 4.0], [27, -4.0, -3.0, -1.0, 0.0]]], [[23, 9]]]], [[[[[26, -3.0, 3.0, -1.0, 3.0], [12, 3.0, -2.0, 6.0, 1.0], [38, 1.0, -2.0, 4.0, -1.0], [31, 5.0, -5.0, 8.0, -4.0]], [[9, -5.0, -2.0, -2.0, 1.0]]], []], [[[[13, -2.0, 5.0, -2.0, 5.0]], [[19, -1.0, -3.0, -1.0, -1.0]]], []], [[[[26, -1.0, 1.0, 0.0, 1.0]], [[15, 1.0, -1.0, 2.0, -1.0], [10, 4.0, 5.0, 7.0, 6.0], [34, -5.0, -1.0, -4.0, -1.0]]], []], [[[[26, -3.0, 0.0, -3.0, 3.0]], [[28, -2.0, -3.0, -2.0, -2.0], [20, 1.0, 3.0, 1.0, 3.0], [29, 2.0, 4.0, 2.0, 5.0], [19, -3.0, 0.0, -2.0, 3.0]]], [[26, 19]]], [[[[36, 2.0, 4.0, 4.0, 4.0], [32, -3.0, -4.0, -3.0, -2.0], [37, -3.0, -4.0, -2.0, -4.0], [12, 5.0, -2.0, 5.0, 1.0]], [[22, 2.0, 4.0, 2.0, 4.0], [5, 4.0, 2.0, 7.0, 5.0]]], [[36, 5], [36, 22]]], [[[[1, -4.0, -5.0, -2.0, -2.0], [28, -5.0, -2.0, -5.0, 0.0], [3, 2.0, -3.0, 4.0, 0.0], [11, -5.0, -1.0, -3.0, 1.0]], [[9, 2.0, 3.0, 2.0, 5.0], [21, 5.0, -5.0, 6.0, -4.0]]], []], [[[[27, 0.0, 3.0, 0.0, 6.0], [12, -4.0, 4.0, -3.0, 7.0], [8, -3.0, -1.0, -1.0, -1.0]], [[4, -1.0, -4.0, -1.0, -1.0], [16, -5.0, -4.0, -4.0, -3.0], [28, -4.0, 5.0, -2.0, 5.0], [5, -1.0, 4.0, 2.0, 5.0]]], [[8, 4], [12, 28], [27, 5]]], [[[[5, 4.0, 1.0, 5.0, 4.0]], [[15, 4.0, 4.0, 4.0, 4.0]]], [[5, 15]]]], [[[[[8, -2.0, 0.0, 1.0, 1.0], [9, -2.0, -1.0, 1.0, 2.0], [1, 1.0, -3.0, 3.0, -2.0]], [[35, -2.0, 0.0, 3.0, 2.0], [14, 2.0, -1.0, 3.0, 1.0]]], [[8, 35], [9, 35]]], [[[[25, 0.0, -5.0, 0.0, -2.0], [24, 3.0, 5.0, 3.0, 7.0], [1, -3.0, 5.0, -3.0, 8.0], [30, -2.0, -1.0, -1.0, 2.0]], [[13, 0.0, -2.0, 2.0, 1.0], [39, -5.0, 3.0, -4.0, 5.0], [2, 4.0, 5.0, 4.0, 7.0], [7, 0.0, 3.0, 0.0, 5.0]]], [[25, 13]]], [[[[29, 5.0, -4.0, 6.0, -4.0], [7, 5.0, 4.0, 6.0, 7.0]], [[36, 1.0, -4.0, 4.0, -1.0], [27, 1.0, 2.0, 3.0, 3.0], [19, 2.0, 2.0, 3.0, 3.0]]], []], [[[[18, -5.0, 2.0, -2.0, 2.0], [34, -5.0, -3.0, -3.0, -3.0], [13, -5.0, 4.0, -2.0, 6.0]], [[32, -5.0, 5.0, 8.0, 6.0]]], [[13, 32]]], [[[[15, 3.0, -1.0, 3.0, -1.0]], [[35, 3.0, -4.0, 4.0, -1.0], [16, -2.0, 0.0, -2.0, 2.0], [9, 1.0, 4.0, 4.0, 4.0], [27, -4.0, -5.0, -4.0, -4.0]]], [[15, 35]]], [[[[15, 5.0, 2.0, 6.0, 3.0], [27, -3.0, 5.0, -3.0, 6.0]], [[38, 5.0, 2.0, 5.0, 2.0]]], [[15, 38]]], [[[[35, 4.0, 5.0, 6.0, 8.0], [5, -4.0, 4.0, -3.0, 4.0], [33, 1.0, 5.0, 2.0, 5.0]], [[1, 4.0, 4.0, 4.0, 4.0], [10, -3.0, 4.0, -2.0, 6.0], [17, -1.0, 1.0, 0.0, 3.0], [7, 5.0, -5.0, 7.0, -5.0]]], [[5, 10]]], [[[[35, -3.0, 2.0, -3.0, 4.0], [16, 0.0, 1.0, 1.0, 1.0], [15, -2.0, 4.0, 0.0, 6.0]], [[22, -3.0, -3.0, 2.0, 0.0], [7, 2.0, 1.0, 3.0, 4.0], [6, 5.0, -5.0, 6.0, -4.0]]], []]], [[[[[2, -1.0, 0.0, -1.0, 1.0], [10, -5.0, 2.0, -3.0, 5.0], [19, -4.0, 1.0, -4.0, 4.0]], [[11, 4.0, 3.0, 4.0, 5.0], [14, -2.0, 1.0, 1.0, 2.0]]], [[2, 14]]], [[[[32, 2.0, 1.0, 4.0, 4.0], [10, 2.0, -3.0, 3.0, -2.0]], [[5, -2.0, 5.0, -1.0, 5.0]]], []], [[[[16, -1.0, -4.0, 1.0, -1.0], [31, -5.0, -2.0, -5.0, -1.0]], [[6, -1.0, -4.0, 2.0, -4.0], [9, -2.0, -4.0, -2.0, -1.0], [8, -5.0, -5.0, -4.0, -3.0], [34, 5.0, 1.0, 8.0, 4.0]]], [[16, 6]]], [[[[14, -4.0, -1.0, -2.0, 1.0]], [[20, 3.0, 0.0, 5.0, 2.0], [12, 0.0, -2.0, 1.0, 1.0], [19, 4.0, -2.0, 5.0, -1.0]]], []], [[[[14, -5.0, -5.0, -5.0, -5.0], [26, -3.0, -1.0, -1.0, 1.0], [20, 1.0, 3.0, 3.0, 4.0]], [[10, -5.0, -5.0, 2.0, -4.0]]], [[14, 10]]], [[[[29, -2.0, 0.0, 0.0, 3.0]], [[36, -4.0, 5.0, -2.0, 6.0], [1, -2.0, -1.0, -1.0, 2.0]]], [[29, 1]]], [[[[7, -2.0, 0.0, -1.0, 0.0], [15, 5.0, -5.0, 5.0, -5.0], [16, -1.0, -2.0, 2.0, -2.0], [39, 0.0, -1.0, 0.0, 0.0]], [[13, -2.0, 2.0, 3.0, 5.0]]], []], [[[[14, -4.0, 5.0, -2.0, 8.0]], [[8, -4.0, 3.0, -1.0, 6.0], [17, 3.0, -4.0, 6.0, -1.0]]], [[14, 8]]]]]\nfor i, (args, expected) in enumerate(fixtures[N-1]):\n    check(\"case %d\" % i, 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 with stipulated toy conventions; not a production physics engine or spatial index. 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-collision_detection_broadphase-bipartite-box-pruning-equal-start-ownership","generated_at":"2026-09-29T14:51:01.818733+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"Broadphase stages decide which object pairs ever reach narrowphase; a wrong boundary, ordering or bookkeeping rule silently drops real contacts or floods the solver with false candidates.","repair":"Pass 2 must skip A boxes with minx <= b.minx (pass 1 owns ties).","root_cause":"Pass 2 skips only A boxes with minx < b.minx.","sha256":"7248733ca8dd4c1667c92c08e79cf57ad44d2df9babb6636766c045d41020160","title":"Boxes starting at the same x are paired by both passes · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verification":{"attempt":{"elapsed_ms":41.408,"exit_code":1,"observations":[{"actual":[],"check":"case 0","expected":[],"passed":true},{"actual":[],"check":"case 1","expected":[],"passed":true},{"actual":[],"check":"case 2","expected":[[39,9]],"passed":false},{"actual":[[37,20]],"check":"case 3","expected":[[29,1],[37,20]],"passed":false},{"actual":[],"check":"case 4","expected":[],"passed":true},{"actual":[[9,5]],"check":"case 5","expected":[[9,5],[33,19]],"passed":false},{"actual":[],"check":"case 6","expected":[[29,27]],"passed":false},{"actual":[],"check":"case 7","expected":[[11,26]],"passed":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"case 0\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"case 1\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"case 2\", \"actual\": [], \"expected\": [[39, 9]], \"passed\": false}, {\"check\": \"case 3\", \"actual\": [[37, 20]], \"expected\": [[29, 1], [37, 20]], \"passed\": false}, {\"check\": \"case 4\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"case 5\", \"actual\": [[9, 5]], \"expected\": [[9, 5], [33, 19]], \"passed\": false}, {\"check\": \"case 6\", \"actual\": [], \"expected\": [[29, 27]], \"passed\": false}, {\"check\": \"case 7\", \"actual\": [], \"expected\": [[11, 26]], \"passed\": false}], \"passed\": false}\n"},"broken":{"elapsed_ms":41.02,"exit_code":1,"observations":[{"actual":[],"check":"case 0","expected":[],"passed":true},{"actual":[],"check":"case 1","expected":[],"passed":true},{"actual":[[39,9],[39,9]],"check":"case 2","expected":[[39,9]],"passed":false},{"actual":[[29,1],[29,1],[37,20]],"check":"case 3","expected":[[29,1],[37,20]],"passed":false},{"actual":[],"check":"case 4","expected":[],"passed":true},{"actual":[[9,5],[33,19],[33,19]],"check":"case 5","expected":[[9,5],[33,19]],"passed":false},{"actual":[[29,27],[29,27]],"check":"case 6","expected":[[29,27]],"passed":false},{"actual":[[11,26],[11,26]],"check":"case 7","expected":[[11,26]],"passed":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"case 0\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"case 1\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"case 2\", \"actual\": [[39, 9], [39, 9]], \"expected\": [[39, 9]], \"passed\": false}, {\"check\": \"case 3\", \"actual\": [[29, 1], [29, 1], [37, 20]], \"expected\": [[29, 1], [37, 20]], \"passed\": false}, {\"check\": \"case 4\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"case 5\", \"actual\": [[9, 5], [33, 19], [33, 19]], \"expected\": [[9, 5], [33, 19]], \"passed\": false}, {\"check\": \"case 6\", \"actual\": [[29, 27], [29, 27]], \"expected\": [[29, 27]], \"passed\": false}, {\"check\": \"case 7\", \"actual\": [[11, 26], [11, 26]], \"expected\": [[11, 26]], \"passed\": false}], \"passed\": false}\n"},"fixed":{"elapsed_ms":41.017,"exit_code":0,"observations":[{"actual":[],"check":"case 0","expected":[],"passed":true},{"actual":[],"check":"case 1","expected":[],"passed":true},{"actual":[[39,9]],"check":"case 2","expected":[[39,9]],"passed":true},{"actual":[[29,1],[37,20]],"check":"case 3","expected":[[29,1],[37,20]],"passed":true},{"actual":[],"check":"case 4","expected":[],"passed":true},{"actual":[[9,5],[33,19]],"check":"case 5","expected":[[9,5],[33,19]],"passed":true},{"actual":[[29,27]],"check":"case 6","expected":[[29,27]],"passed":true},{"actual":[[11,26]],"check":"case 7","expected":[[11,26]],"passed":true}],"passed":true,"stderr":"","stdout":"{\"observations\": [{\"check\": \"case 0\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"case 1\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"case 2\", \"actual\": [[39, 9]], \"expected\": [[39, 9]], \"passed\": true}, {\"check\": \"case 3\", \"actual\": [[29, 1], [37, 20]], \"expected\": [[29, 1], [37, 20]], \"passed\": true}, {\"check\": \"case 4\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"case 5\", \"actual\": [[9, 5], [33, 19]], \"expected\": [[9, 5], [33, 19]], \"passed\": true}, {\"check\": \"case 6\", \"actual\": [[29, 27]], \"expected\": [[29, 27]], \"passed\": true}, {\"check\": \"case 7\", \"actual\": [[11, 26]], \"expected\": [[11, 26]], \"passed\": true}], \"passed\": true}\n"}},"verified":true,"visibility":"public"}