{"abstract":"Narrowphase runs the same pair once per shared cell.","category":"Collision detection broadphase","checks":8,"contract":"solve(boxes, cs): insert each box [id,minx,miny,maxx,maxy] into every grid cell floor(min/cs)..floor(max/cs) inclusive on both axes. Return [sorted unique canonical candidate pairs sharing a cell, total cell insertions, largest bucket size].","contract_signature":"boxes, cs","evaluation_group":"w2-collision_detection_broadphase-uniform-grid-candidates","failed_approach":"A set of unordered tuples still keeps (a,b) and (b,a) separately.","family":"w2-collision_detection_broadphase-uniform-grid-candidates-cross-cell-deduplication","id":"FA-87376","implementations":{"attempt":{"sha256":"7ec25b010e387dc39e8c301b215200b2cfe5d3ede9082130ca638d57c281a4ea","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nimport math\nN = 1\nobservations = []\ndef solve(boxes, cs):\n    grid = {}\n    inserts = 0\n    for b in boxes:\n        i0, i1 = math.floor(b[1] / cs), math.floor(b[3] / cs)\n        j0, j1 = math.floor(b[2] / cs), math.floor(b[4] / cs)\n        for i in range(i0, i1 + 1):\n            for j in range(j0, j1 + 1):\n                grid.setdefault((i, j), []).append(b[0])\n                inserts += 1\n    pairs = set()\n    for cell in grid.values():\n        for p in range(len(cell)):\n            for q in range(p + 1, len(cell)):\n                a, c = cell[p], cell[q]\n                pairs.add((a, c))\n    return [sorted([list(p) for p in pairs]), inserts, max((len(v) for v in grid.values()), default=0)]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\nfixtures = [[[[[[9, -2.0, -2.0, -2.0, -1.0], [17, 1.5, -1.5, 3.5, 0.0], [25, -2.5, 3.0, 0.0, 3.5], [6, 2.5, 2.5, 5.0, 2.5], [12, 0.5, 1.5, 2.5, 3.0]], 1.0], [[[6, 12], [12, 25]], 28, 2]], [[[[12, -2.5, -2.0, -2.0, -2.0], [8, -3.0, -2.5, -0.5, -1.5]], 3.0], [[[8, 12]], 2, 2]], [[[[38, 4.0, -1.0, 5.0, 0.0], [39, -4.0, -3.0, 0.0, 1.0]], 2.5], [[], 13, 1]], [[[[7, 5.0, 1.0, 5.0, 4.0], [6, 0.0, -6.0, 5.0, -1.0], [22, 6.0, 6.0, 9.0, 10.0], [34, -1.0, 2.0, -1.0, 6.0], [1, 4.0, -5.0, 4.0, -2.0]], 2.5], [[[1, 6]], 22, 2]], [[[[34, -5.0, -6.0, -2.0, -2.0], [20, 3.0, 4.0, 7.0, 7.0], [23, 2.0, 3.0, 7.0, 6.0], [14, -4.0, 6.0, -4.0, 10.0], [6, 1.0, 0.0, 2.0, 5.0], [17, -3.0, -4.0, -1.0, -2.0]], 2.5], [[[6, 23], [17, 34], [20, 23]], 26, 2]], [[[[30, -5.0, 2.0, -2.0, 3.0], [27, 3.0, 3.0, 3.0, 3.0], [26, 5.0, -4.0, 9.0, -4.0]], 3.0], [[], 8, 1]], [[[[29, -3.0, 1.5, -0.5, 3.0], [14, -1.0, -1.5, 0.0, 0.5]], 3.0], [[[14, 29]], 6, 2]], [[[[21, -2.5, 1.5, -2.0, 2.5], [19, 1.5, 0.0, 2.0, 1.0], [10, -1.0, 1.5, 1.0, 3.5], [18, -1.5, 0.0, -1.0, 2.5], [24, -3.0, -1.5, -1.0, -1.0], [28, 3.0, 0.5, 4.0, 1.5]], 2.5], [[[10, 18], [10, 19], [10, 21], [18, 21]], 12, 3]]], [[[[[23, 4.0, -2.0, 7.0, 1.0], [38, -5.0, 3.0, 0.0, 7.0], [24, -6.0, 1.0, -1.0, 2.0], [34, -3.0, -1.0, 1.0, 0.0], [35, 3.0, 0.0, 3.0, 4.0]], 1.0], [[], 73, 1]], [[[[37, 3.0, 0.5, 3.5, 3.0], [13, 2.0, -0.5, 3.5, 0.5], [21, 1.0, 2.0, 2.5, 2.5], [34, 0.0, 2.0, 1.5, 4.5], [29, -0.5, -2.0, 1.5, -1.0], [33, -0.5, 0.5, 0.0, 3.0], [27, 0.5, 0.5, 2.0, 0.5]], 1.0], [[[13, 27], [13, 37], [21, 34], [27, 33], [33, 34]], 33, 2]], [[[[13, -1.0, 6.0, 2.0, 9.0], [17, 5.0, -1.0, 10.0, 1.0], [8, 4.0, -4.0, 6.0, -2.0], [14, 3.0, 2.0, 6.0, 3.0], [18, 2.0, -1.0, 3.0, 2.0]], 2.5], [[[8, 17], [8, 18], [14, 17], [14, 18]], 22, 2]], [[[[1, -2.0, 2.0, -1.5, 4.5], [38, -3.0, 3.0, -1.0, 5.0], [39, -1.5, -3.0, 0.5, -1.5], [25, 1.5, -0.5, 3.5, 2.0], [9, -2.0, 1.0, -1.0, 3.0]], 3.0], [[[1, 9], [1, 38], [9, 38], [25, 39]], 11, 3]], [[[[8, -4.0, 6.0, 1.0, 6.0], [31, -5.0, 3.0, -5.0, 7.0], [24, 6.0, -3.0, 7.0, 1.0], [5, -5.0, 5.0, -4.0, 9.0]], 1.0], [[[5, 8], [5, 31]], 31, 2]], [[[[25, -6.0, 5.0, -6.0, 9.0], [28, 4.0, 3.0, 8.0, 3.0], [36, -2.0, 3.0, 2.0, 8.0], [29, 2.0, -5.0, 5.0, -1.0], [20, -2.0, 4.0, 3.0, 9.0], [12, -2.0, -3.0, 1.0, -3.0]], 1.0], [[[20, 36]], 100, 2]], [[[[30, 3.0, 3.0, 4.0, 8.0], [14, 3.0, -6.0, 6.0, -5.0], [28, -1.0, -5.0, -1.0, -3.0]], 1.0], [[], 23, 1]], [[[[6, -2.5, 2.5, -1.5, 4.0], [32, -2.5, 0.5, -0.5, 1.0], [29, 2.5, 0.0, 4.0, 1.5], [18, -2.5, -0.5, -1.0, 2.0]], 1.0], [[[6, 18], [18, 32]], 30, 2]]], [[[[[16, 2.0, 1.5, 3.0, 2.5], [25, -2.5, -1.0, -0.5, 1.0], [9, -2.5, 2.0, -0.5, 3.5], [11, -2.0, -1.0, 0.0, -1.0], [37, -0.5, 2.0, 0.0, 2.5], [26, -2.0, -2.0, 0.5, -2.0], [8, 2.5, -3.0, 5.0, -1.5], [30, -2.5, -0.5, -2.5, 1.0]], 2.0], [[[9, 37], [11, 25], [11, 26], [25, 26], [25, 30]], 20, 3]], [[[[37, -1.0, -2.0, -1.0, -1.0], [10, 3.0, -1.0, 4.0, 4.0], [34, -6.0, -3.0, -5.0, 0.0], [28, -2.0, 3.0, 0.0, 8.0], [20, 4.0, -3.0, 5.0, 1.0], [22, 1.0, -4.0, 5.0, -3.0]], 2.0], [[[10, 20], [20, 22]], 26, 2]], [[[[23, -2.0, 3.0, -0.5, 3.5], [26, 3.0, 2.0, 5.5, 3.0], [38, -1.5, 0.0, 0.0, 0.0], [4, 1.5, 2.5, 4.0, 5.0]], 1.0], [[[4, 26]], 27, 2]], [[[[22, 0.5, 2.0, 2.0, 2.5], [8, 1.5, -0.5, 2.0, -0.5], [2, 3.0, -0.5, 3.0, 0.0], [27, -1.0, 1.5, 0.5, 2.0], [36, 1.5, 1.5, 2.5, 1.5], [14, -2.5, -1.5, -2.0, -1.5], [31, 0.0, -1.5, 1.0, -0.5]], 2.5], [[[2, 36], [8, 31], [22, 27], [22, 36], [27, 36]], 11, 3]], [[[[22, 3.0, 4.0, 6.0, 6.0], [36, 0.0, -6.0, 4.0, -1.0], [38, -5.0, 0.0, 0.0, 0.0], [25, -4.0, 1.0, 0.0, 3.0]], 2.5], [[[25, 38]], 19, 2]], [[[[28, 1.5, 0.5, 3.0, 3.0], [22, -1.5, -0.5, -0.5, -0.5], [15, -1.5, 2.5, -1.0, 3.5], [19, -1.0, -2.5, 1.0, -1.0], [30, -2.5, 0.0, -1.0, 0.5], [2, 0.5, -2.5, 2.0, -0.5], [23, -2.0, 0.0, -1.0, 0.5]], 2.5], [[[2, 19], [19, 22], [23, 30]], 11, 2]], [[[[16, -5.0, 5.0, -4.0, 6.0], [37, -2.0, 5.0, -1.0, 10.0], [10, 5.0, -2.0, 9.0, 1.0]], 1.0], [[], 36, 1]], [[[[21, 1.0, -1.0, 5.0, 2.0], [18, -6.0, 3.0, -3.0, 8.0], [29, 6.0, -1.0, 6.0, 2.0], [10, 5.0, 0.0, 7.0, 1.0], [30, 0.0, -4.0, 3.0, -3.0], [16, 2.0, 1.0, 7.0, 2.0]], 2.5], [[[10, 16], [10, 21], [10, 29], [16, 21], [16, 29], [21, 29]], 20, 4]]], [[[[[8, 5.0, 4.0, 9.0, 8.0], [21, 5.0, -3.0, 5.0, -2.0], [14, 3.0, 6.0, 3.0, 11.0], [32, 4.0, -5.0, 5.0, 0.0], [29, -1.0, 3.0, 2.0, 5.0], [3, -4.0, 4.0, -1.0, 8.0], [39, -1.0, 1.0, 4.0, 3.0]], 2.0], [[[3, 29], [21, 32], [29, 39], [32, 39]], 38, 2]], [[[[5, -3.0, 2.0, -2.5, 3.5], [4, 2.5, 2.0, 5.0, 4.5], [27, 3.0, 0.5, 4.5, 0.5], [12, 0.0, -1.5, 1.5, -1.5], [22, 2.5, 1.5, 2.5, 2.5], [20, 1.5, 1.0, 2.0, 2.0]], 1.0], [[[4, 20], [4, 22], [20, 22]], 24, 3]], [[[[17, 4.0, 0.0, 9.0, 5.0], [10, 3.0, -6.0, 5.0, -1.0], [11, 0.0, -4.0, 2.0, 0.0]], 2.5], [[], 18, 1]], [[[[14, 4.0, -5.0, 4.0, -5.0], [25, -2.0, -4.0, 0.0, -4.0], [30, -4.0, 0.0, -1.0, 0.0], [8, -4.0, -4.0, -3.0, -4.0], [28, -4.0, 5.0, 0.0, 7.0], [19, -5.0, -2.0, -2.0, 2.0], [37, 4.0, -1.0, 9.0, 4.0], [9, -5.0, 4.0, -3.0, 8.0]], 3.0], [[[8, 25], [9, 28], [19, 30]], 30, 2]], [[[[30, -2.5, -1.0, -0.5, 1.0], [16, 0.5, 3.0, 3.0, 5.5], [17, 1.0, -2.5, 1.0, -1.0], [32, 1.5, 0.0, 4.0, 0.0], [36, -1.5, 2.0, -0.5, 3.5]], 2.5], [[[30, 36]], 11, 2]], [[[[15, 0.0, 2.0, 2.0, 2.5], [2, -3.0, 2.0, -3.0, 4.5], [29, -1.5, 1.5, 0.0, 4.0], [37, -2.0, 1.0, -2.0, 3.0], [27, 2.5, 1.0, 4.0, 3.5], [30, -0.5, 2.5, -0.5, 4.5]], 1.0], [[[15, 27], [15, 29], [29, 30], [29, 37]], 33, 2]], [[[[19, -3.0, 2.0, -1.0, 2.0], [3, 6.0, 0.0, 9.0, 4.0], [32, 3.0, -6.0, 3.0, -2.0], [38, 0.0, 3.0, 5.0, 3.0], [8, -4.0, 6.0, -3.0, 11.0], [13, -3.0, 5.0, 2.0, 10.0], [2, 3.0, 3.0, 7.0, 3.0], [30, 2.0, 0.0, 5.0, 5.0]], 3.0], [[[2, 3], [2, 30], [2, 38], [8, 13], [13, 30], [13, 38], [30, 38]], 25, 3]], [[[[33, 2.0, 0.0, 5.0, 1.0], [26, 1.0, -1.0, 1.0, 0.0], [29, -5.0, 2.0, -4.0, 5.0]], 2.0], [[], 8, 1]]], [[[[[2, 0.0, -4.0, 1.0, 0.0], [33, 4.0, -4.0, 4.0, -3.0], [9, 4.0, 5.0, 9.0, 5.0], [37, 6.0, 5.0, 6.0, 6.0], [32, -3.0, -5.0, 2.0, -5.0], [26, 5.0, 0.0, 5.0, 1.0]], 2.5], [[[2, 32], [9, 37]], 12, 2]], [[[[2, 0.0, -2.0, 1.0, 2.0], [38, -4.0, -3.0, 1.0, -2.0], [8, 5.0, -2.0, 10.0, 3.0], [10, 4.0, -2.0, 9.0, 0.0], [4, -1.0, 6.0, 1.0, 10.0], [20, -3.0, -2.0, -2.0, 3.0], [31, -5.0, -4.0, -5.0, -3.0], [16, -4.0, -1.0, -2.0, 4.0], [1, -1.0, -5.0, 3.0, 0.0], [23, -6.0, 4.0, -4.0, 6.0]], 2.5], [[[1, 2], [1, 10], [1, 16], [1, 20], [1, 38], [2, 38], [8, 10], [16, 20], [16, 23], [16, 38], [20, 23], [20, 38], [31, 38]], 55, 4]], [[[[35, 0.0, 0.0, 0.0, 4.0], [18, -1.0, -6.0, 3.0, -6.0], [6, 3.0, 4.0, 5.0, 8.0], [25, 4.0, -4.0, 6.0, -2.0], [36, 2.0, -6.0, 7.0, -5.0], [21, 0.0, 4.0, 4.0, 6.0], [29, 4.0, -2.0, 9.0, 3.0], [34, 3.0, -2.0, 7.0, 0.0], [33, 5.0, -4.0, 5.0, -3.0], [15, 4.0, 0.0, 4.0, 5.0]], 2.5], [[[6, 15], [6, 21], [6, 29], [15, 21], [15, 29], [15, 34], [18, 36], [21, 29], [21, 35], [25, 29], [25, 33], [25, 34], [25, 36], [29, 34], [33, 36]], 42, 4]], [[[[29, 1.0, -2.0, 2.5, 0.0], [30, -2.5, 0.0, -2.0, 0.0]], 2.5], [[], 5, 1]], [[[[33, -2.0, -5.0, -1.0, -1.0], [32, -4.0, -3.0, -4.0, -2.0]], 2.5], [[], 4, 1]], [[[[1, -0.5, -3.0, 1.0, -0.5], [31, 1.0, -3.0, 2.0, -3.0], [30, -1.0, 2.5, -1.0, 3.0], [23, -2.0, -2.5, -2.0, 0.0], [35, 3.0, -2.0, 3.0, -1.5], [5, -2.0, -2.5, 0.5, -1.5], [7, 0.0, -1.0, 1.0, 1.5], [12, 1.5, 0.0, 3.0, 0.0], [28, 0.5, -2.5, 0.5, -0.5], [37, -2.5, 0.0, -1.0, 0.0]], 2.0], [[[1, 5], [1, 7], [1, 23], [1, 28], [1, 31], [5, 7], [5, 23], [5, 28], [5, 31], [7, 12], [7, 28], [23, 37], [28, 31]], 23, 4]], [[[[30, -5.0, -5.0, 0.0, -2.0], [37, 6.0, -2.0, 10.0, 3.0], [3, -3.0, 4.0, 2.0, 5.0], [7, 0.0, -5.0, 4.0, 0.0], [20, -2.0, 1.0, 2.0, 4.0], [16, -3.0, -4.0, 0.0, 0.0], [24, 0.0, 6.0, 0.0, 9.0]], 2.0], [[[3, 20], [7, 16], [7, 20], [7, 30], [16, 20], [16, 30]], 57, 3]], [[[[37, 0.5, 2.5, 3.0, 5.0], [31, -2.0, 2.0, 0.5, 3.5], [6, -1.5, -2.0, -0.5, 0.0], [14, -2.5, 1.0, -1.5, 3.5]], 3.0], [[[6, 14], [6, 31], [14, 31], [31, 37]], 12, 3]]]]\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":"bee2617f81feb60d55edd1ac49dc971894896e2158e0cfef69255dac612d8978","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nimport math\nN = 1\nobservations = []\ndef solve(boxes, cs):\n    grid = {}\n    inserts = 0\n    for b in boxes:\n        i0, i1 = math.floor(b[1] / cs), math.floor(b[3] / cs)\n        j0, j1 = math.floor(b[2] / cs), math.floor(b[4] / cs)\n        for i in range(i0, i1 + 1):\n            for j in range(j0, j1 + 1):\n                grid.setdefault((i, j), []).append(b[0])\n                inserts += 1\n    pairs = []\n    for cell in grid.values():\n        for p in range(len(cell)):\n            for q in range(p + 1, len(cell)):\n                a, c = cell[p], cell[q]\n                pairs.append((min(a, c), max(a, c)))\n    return [sorted([list(p) for p in pairs]), inserts, max((len(v) for v in grid.values()), default=0)]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\nfixtures = [[[[[[9, -2.0, -2.0, -2.0, -1.0], [17, 1.5, -1.5, 3.5, 0.0], [25, -2.5, 3.0, 0.0, 3.5], [6, 2.5, 2.5, 5.0, 2.5], [12, 0.5, 1.5, 2.5, 3.0]], 1.0], [[[6, 12], [12, 25]], 28, 2]], [[[[12, -2.5, -2.0, -2.0, -2.0], [8, -3.0, -2.5, -0.5, -1.5]], 3.0], [[[8, 12]], 2, 2]], [[[[38, 4.0, -1.0, 5.0, 0.0], [39, -4.0, -3.0, 0.0, 1.0]], 2.5], [[], 13, 1]], [[[[7, 5.0, 1.0, 5.0, 4.0], [6, 0.0, -6.0, 5.0, -1.0], [22, 6.0, 6.0, 9.0, 10.0], [34, -1.0, 2.0, -1.0, 6.0], [1, 4.0, -5.0, 4.0, -2.0]], 2.5], [[[1, 6]], 22, 2]], [[[[34, -5.0, -6.0, -2.0, -2.0], [20, 3.0, 4.0, 7.0, 7.0], [23, 2.0, 3.0, 7.0, 6.0], [14, -4.0, 6.0, -4.0, 10.0], [6, 1.0, 0.0, 2.0, 5.0], [17, -3.0, -4.0, -1.0, -2.0]], 2.5], [[[6, 23], [17, 34], [20, 23]], 26, 2]], [[[[30, -5.0, 2.0, -2.0, 3.0], [27, 3.0, 3.0, 3.0, 3.0], [26, 5.0, -4.0, 9.0, -4.0]], 3.0], [[], 8, 1]], [[[[29, -3.0, 1.5, -0.5, 3.0], [14, -1.0, -1.5, 0.0, 0.5]], 3.0], [[[14, 29]], 6, 2]], [[[[21, -2.5, 1.5, -2.0, 2.5], [19, 1.5, 0.0, 2.0, 1.0], [10, -1.0, 1.5, 1.0, 3.5], [18, -1.5, 0.0, -1.0, 2.5], [24, -3.0, -1.5, -1.0, -1.0], [28, 3.0, 0.5, 4.0, 1.5]], 2.5], [[[10, 18], [10, 19], [10, 21], [18, 21]], 12, 3]]], [[[[[23, 4.0, -2.0, 7.0, 1.0], [38, -5.0, 3.0, 0.0, 7.0], [24, -6.0, 1.0, -1.0, 2.0], [34, -3.0, -1.0, 1.0, 0.0], [35, 3.0, 0.0, 3.0, 4.0]], 1.0], [[], 73, 1]], [[[[37, 3.0, 0.5, 3.5, 3.0], [13, 2.0, -0.5, 3.5, 0.5], [21, 1.0, 2.0, 2.5, 2.5], [34, 0.0, 2.0, 1.5, 4.5], [29, -0.5, -2.0, 1.5, -1.0], [33, -0.5, 0.5, 0.0, 3.0], [27, 0.5, 0.5, 2.0, 0.5]], 1.0], [[[13, 27], [13, 37], [21, 34], [27, 33], [33, 34]], 33, 2]], [[[[13, -1.0, 6.0, 2.0, 9.0], [17, 5.0, -1.0, 10.0, 1.0], [8, 4.0, -4.0, 6.0, -2.0], [14, 3.0, 2.0, 6.0, 3.0], [18, 2.0, -1.0, 3.0, 2.0]], 2.5], [[[8, 17], [8, 18], [14, 17], [14, 18]], 22, 2]], [[[[1, -2.0, 2.0, -1.5, 4.5], [38, -3.0, 3.0, -1.0, 5.0], [39, -1.5, -3.0, 0.5, -1.5], [25, 1.5, -0.5, 3.5, 2.0], [9, -2.0, 1.0, -1.0, 3.0]], 3.0], [[[1, 9], [1, 38], [9, 38], [25, 39]], 11, 3]], [[[[8, -4.0, 6.0, 1.0, 6.0], [31, -5.0, 3.0, -5.0, 7.0], [24, 6.0, -3.0, 7.0, 1.0], [5, -5.0, 5.0, -4.0, 9.0]], 1.0], [[[5, 8], [5, 31]], 31, 2]], [[[[25, -6.0, 5.0, -6.0, 9.0], [28, 4.0, 3.0, 8.0, 3.0], [36, -2.0, 3.0, 2.0, 8.0], [29, 2.0, -5.0, 5.0, -1.0], [20, -2.0, 4.0, 3.0, 9.0], [12, -2.0, -3.0, 1.0, -3.0]], 1.0], [[[20, 36]], 100, 2]], [[[[30, 3.0, 3.0, 4.0, 8.0], [14, 3.0, -6.0, 6.0, -5.0], [28, -1.0, -5.0, -1.0, -3.0]], 1.0], [[], 23, 1]], [[[[6, -2.5, 2.5, -1.5, 4.0], [32, -2.5, 0.5, -0.5, 1.0], [29, 2.5, 0.0, 4.0, 1.5], [18, -2.5, -0.5, -1.0, 2.0]], 1.0], [[[6, 18], [18, 32]], 30, 2]]], [[[[[16, 2.0, 1.5, 3.0, 2.5], [25, -2.5, -1.0, -0.5, 1.0], [9, -2.5, 2.0, -0.5, 3.5], [11, -2.0, -1.0, 0.0, -1.0], [37, -0.5, 2.0, 0.0, 2.5], [26, -2.0, -2.0, 0.5, -2.0], [8, 2.5, -3.0, 5.0, -1.5], [30, -2.5, -0.5, -2.5, 1.0]], 2.0], [[[9, 37], [11, 25], [11, 26], [25, 26], [25, 30]], 20, 3]], [[[[37, -1.0, -2.0, -1.0, -1.0], [10, 3.0, -1.0, 4.0, 4.0], [34, -6.0, -3.0, -5.0, 0.0], [28, -2.0, 3.0, 0.0, 8.0], [20, 4.0, -3.0, 5.0, 1.0], [22, 1.0, -4.0, 5.0, -3.0]], 2.0], [[[10, 20], [20, 22]], 26, 2]], [[[[23, -2.0, 3.0, -0.5, 3.5], [26, 3.0, 2.0, 5.5, 3.0], [38, -1.5, 0.0, 0.0, 0.0], [4, 1.5, 2.5, 4.0, 5.0]], 1.0], [[[4, 26]], 27, 2]], [[[[22, 0.5, 2.0, 2.0, 2.5], [8, 1.5, -0.5, 2.0, -0.5], [2, 3.0, -0.5, 3.0, 0.0], [27, -1.0, 1.5, 0.5, 2.0], [36, 1.5, 1.5, 2.5, 1.5], [14, -2.5, -1.5, -2.0, -1.5], [31, 0.0, -1.5, 1.0, -0.5]], 2.5], [[[2, 36], [8, 31], [22, 27], [22, 36], [27, 36]], 11, 3]], [[[[22, 3.0, 4.0, 6.0, 6.0], [36, 0.0, -6.0, 4.0, -1.0], [38, -5.0, 0.0, 0.0, 0.0], [25, -4.0, 1.0, 0.0, 3.0]], 2.5], [[[25, 38]], 19, 2]], [[[[28, 1.5, 0.5, 3.0, 3.0], [22, -1.5, -0.5, -0.5, -0.5], [15, -1.5, 2.5, -1.0, 3.5], [19, -1.0, -2.5, 1.0, -1.0], [30, -2.5, 0.0, -1.0, 0.5], [2, 0.5, -2.5, 2.0, -0.5], [23, -2.0, 0.0, -1.0, 0.5]], 2.5], [[[2, 19], [19, 22], [23, 30]], 11, 2]], [[[[16, -5.0, 5.0, -4.0, 6.0], [37, -2.0, 5.0, -1.0, 10.0], [10, 5.0, -2.0, 9.0, 1.0]], 1.0], [[], 36, 1]], [[[[21, 1.0, -1.0, 5.0, 2.0], [18, -6.0, 3.0, -3.0, 8.0], [29, 6.0, -1.0, 6.0, 2.0], [10, 5.0, 0.0, 7.0, 1.0], [30, 0.0, -4.0, 3.0, -3.0], [16, 2.0, 1.0, 7.0, 2.0]], 2.5], [[[10, 16], [10, 21], [10, 29], [16, 21], [16, 29], [21, 29]], 20, 4]]], [[[[[8, 5.0, 4.0, 9.0, 8.0], [21, 5.0, -3.0, 5.0, -2.0], [14, 3.0, 6.0, 3.0, 11.0], [32, 4.0, -5.0, 5.0, 0.0], [29, -1.0, 3.0, 2.0, 5.0], [3, -4.0, 4.0, -1.0, 8.0], [39, -1.0, 1.0, 4.0, 3.0]], 2.0], [[[3, 29], [21, 32], [29, 39], [32, 39]], 38, 2]], [[[[5, -3.0, 2.0, -2.5, 3.5], [4, 2.5, 2.0, 5.0, 4.5], [27, 3.0, 0.5, 4.5, 0.5], [12, 0.0, -1.5, 1.5, -1.5], [22, 2.5, 1.5, 2.5, 2.5], [20, 1.5, 1.0, 2.0, 2.0]], 1.0], [[[4, 20], [4, 22], [20, 22]], 24, 3]], [[[[17, 4.0, 0.0, 9.0, 5.0], [10, 3.0, -6.0, 5.0, -1.0], [11, 0.0, -4.0, 2.0, 0.0]], 2.5], [[], 18, 1]], [[[[14, 4.0, -5.0, 4.0, -5.0], [25, -2.0, -4.0, 0.0, -4.0], [30, -4.0, 0.0, -1.0, 0.0], [8, -4.0, -4.0, -3.0, -4.0], [28, -4.0, 5.0, 0.0, 7.0], [19, -5.0, -2.0, -2.0, 2.0], [37, 4.0, -1.0, 9.0, 4.0], [9, -5.0, 4.0, -3.0, 8.0]], 3.0], [[[8, 25], [9, 28], [19, 30]], 30, 2]], [[[[30, -2.5, -1.0, -0.5, 1.0], [16, 0.5, 3.0, 3.0, 5.5], [17, 1.0, -2.5, 1.0, -1.0], [32, 1.5, 0.0, 4.0, 0.0], [36, -1.5, 2.0, -0.5, 3.5]], 2.5], [[[30, 36]], 11, 2]], [[[[15, 0.0, 2.0, 2.0, 2.5], [2, -3.0, 2.0, -3.0, 4.5], [29, -1.5, 1.5, 0.0, 4.0], [37, -2.0, 1.0, -2.0, 3.0], [27, 2.5, 1.0, 4.0, 3.5], [30, -0.5, 2.5, -0.5, 4.5]], 1.0], [[[15, 27], [15, 29], [29, 30], [29, 37]], 33, 2]], [[[[19, -3.0, 2.0, -1.0, 2.0], [3, 6.0, 0.0, 9.0, 4.0], [32, 3.0, -6.0, 3.0, -2.0], [38, 0.0, 3.0, 5.0, 3.0], [8, -4.0, 6.0, -3.0, 11.0], [13, -3.0, 5.0, 2.0, 10.0], [2, 3.0, 3.0, 7.0, 3.0], [30, 2.0, 0.0, 5.0, 5.0]], 3.0], [[[2, 3], [2, 30], [2, 38], [8, 13], [13, 30], [13, 38], [30, 38]], 25, 3]], [[[[33, 2.0, 0.0, 5.0, 1.0], [26, 1.0, -1.0, 1.0, 0.0], [29, -5.0, 2.0, -4.0, 5.0]], 2.0], [[], 8, 1]]], [[[[[2, 0.0, -4.0, 1.0, 0.0], [33, 4.0, -4.0, 4.0, -3.0], [9, 4.0, 5.0, 9.0, 5.0], [37, 6.0, 5.0, 6.0, 6.0], [32, -3.0, -5.0, 2.0, -5.0], [26, 5.0, 0.0, 5.0, 1.0]], 2.5], [[[2, 32], [9, 37]], 12, 2]], [[[[2, 0.0, -2.0, 1.0, 2.0], [38, -4.0, -3.0, 1.0, -2.0], [8, 5.0, -2.0, 10.0, 3.0], [10, 4.0, -2.0, 9.0, 0.0], [4, -1.0, 6.0, 1.0, 10.0], [20, -3.0, -2.0, -2.0, 3.0], [31, -5.0, -4.0, -5.0, -3.0], [16, -4.0, -1.0, -2.0, 4.0], [1, -1.0, -5.0, 3.0, 0.0], [23, -6.0, 4.0, -4.0, 6.0]], 2.5], [[[1, 2], [1, 10], [1, 16], [1, 20], [1, 38], [2, 38], [8, 10], [16, 20], [16, 23], [16, 38], [20, 23], [20, 38], [31, 38]], 55, 4]], [[[[35, 0.0, 0.0, 0.0, 4.0], [18, -1.0, -6.0, 3.0, -6.0], [6, 3.0, 4.0, 5.0, 8.0], [25, 4.0, -4.0, 6.0, -2.0], [36, 2.0, -6.0, 7.0, -5.0], [21, 0.0, 4.0, 4.0, 6.0], [29, 4.0, -2.0, 9.0, 3.0], [34, 3.0, -2.0, 7.0, 0.0], [33, 5.0, -4.0, 5.0, -3.0], [15, 4.0, 0.0, 4.0, 5.0]], 2.5], [[[6, 15], [6, 21], [6, 29], [15, 21], [15, 29], [15, 34], [18, 36], [21, 29], [21, 35], [25, 29], [25, 33], [25, 34], [25, 36], [29, 34], [33, 36]], 42, 4]], [[[[29, 1.0, -2.0, 2.5, 0.0], [30, -2.5, 0.0, -2.0, 0.0]], 2.5], [[], 5, 1]], [[[[33, -2.0, -5.0, -1.0, -1.0], [32, -4.0, -3.0, -4.0, -2.0]], 2.5], [[], 4, 1]], [[[[1, -0.5, -3.0, 1.0, -0.5], [31, 1.0, -3.0, 2.0, -3.0], [30, -1.0, 2.5, -1.0, 3.0], [23, -2.0, -2.5, -2.0, 0.0], [35, 3.0, -2.0, 3.0, -1.5], [5, -2.0, -2.5, 0.5, -1.5], [7, 0.0, -1.0, 1.0, 1.5], [12, 1.5, 0.0, 3.0, 0.0], [28, 0.5, -2.5, 0.5, -0.5], [37, -2.5, 0.0, -1.0, 0.0]], 2.0], [[[1, 5], [1, 7], [1, 23], [1, 28], [1, 31], [5, 7], [5, 23], [5, 28], [5, 31], [7, 12], [7, 28], [23, 37], [28, 31]], 23, 4]], [[[[30, -5.0, -5.0, 0.0, -2.0], [37, 6.0, -2.0, 10.0, 3.0], [3, -3.0, 4.0, 2.0, 5.0], [7, 0.0, -5.0, 4.0, 0.0], [20, -2.0, 1.0, 2.0, 4.0], [16, -3.0, -4.0, 0.0, 0.0], [24, 0.0, 6.0, 0.0, 9.0]], 2.0], [[[3, 20], [7, 16], [7, 20], [7, 30], [16, 20], [16, 30]], 57, 3]], [[[[37, 0.5, 2.5, 3.0, 5.0], [31, -2.0, 2.0, 0.5, 3.5], [6, -1.5, -2.0, -0.5, 0.0], [14, -2.5, 1.0, -1.5, 3.5]], 3.0], [[[6, 14], [6, 31], [14, 31], [31, 37]], 12, 3]]]]\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-uniform-grid-candidates-cross-cell-deduplication","generated_at":"2026-09-29T14:50:58.299662+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.","root_cause":"Pairs are collected in a list rather than a set.","sha256":"67041644033a0fa497974dad82483044309d0232d4b19ba72f8099835c2dbde6","title":"Candidate pairs found in several cells are reported repeatedly · 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":41.351,"exit_code":1,"observations":[{"actual":[[[6,12],[25,12]],28,2],"check":"case 0","expected":[[[6,12],[12,25]],28,2],"passed":false},{"actual":[[[12,8]],2,2],"check":"case 1","expected":[[[8,12]],2,2],"passed":false},{"actual":[[],13,1],"check":"case 2","expected":[[],13,1],"passed":true},{"actual":[[[6,1]],22,2],"check":"case 3","expected":[[[1,6]],22,2],"passed":false},{"actual":[[[20,23],[23,6],[34,17]],26,2],"check":"case 4","expected":[[[6,23],[17,34],[20,23]],26,2],"passed":false},{"actual":[[],8,1],"check":"case 5","expected":[[],8,1],"passed":true},{"actual":[[[29,14]],6,2],"check":"case 6","expected":[[[14,29]],6,2],"passed":false},{"actual":[[[10,18],[19,10],[21,10],[21,18]],12,3],"check":"case 7","expected":[[[10,18],[10,19],[10,21],[18,21]],12,3],"passed":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"case 0\", \"actual\": [[[6, 12], [25, 12]], 28, 2], \"expected\": [[[6, 12], [12, 25]], 28, 2], \"passed\": false}, {\"check\": \"case 1\", \"actual\": [[[12, 8]], 2, 2], \"expected\": [[[8, 12]], 2, 2], \"passed\": false}, {\"check\": \"case 2\", \"actual\": [[], 13, 1], \"expected\": [[], 13, 1], \"passed\": true}, {\"check\": \"case 3\", \"actual\": [[[6, 1]], 22, 2], \"expected\": [[[1, 6]], 22, 2], \"passed\": false}, {\"check\": \"case 4\", \"actual\": [[[20, 23], [23, 6], [34, 17]], 26, 2], \"expected\": [[[6, 23], [17, 34], [20, 23]], 26, 2], \"passed\": false}, {\"check\": \"case 5\", \"actual\": [[], 8, 1], \"expected\": [[], 8, 1], \"passed\": true}, {\"check\": \"case 6\", \"actual\": [[[29, 14]], 6, 2], \"expected\": [[[14, 29]], 6, 2], \"passed\": false}, {\"check\": \"case 7\", \"actual\": [[[10, 18], [19, 10], [21, 10], [21, 18]], 12, 3], \"expected\": [[[10, 18], [10, 19], [10, 21], [18, 21]], 12, 3], \"passed\": false}], \"passed\": false}\n"},"broken":{"elapsed_ms":38.826,"exit_code":1,"observations":[{"actual":[[[6,12],[12,25]],28,2],"check":"case 0","expected":[[[6,12],[12,25]],28,2],"passed":true},{"actual":[[[8,12]],2,2],"check":"case 1","expected":[[[8,12]],2,2],"passed":true},{"actual":[[],13,1],"check":"case 2","expected":[[],13,1],"passed":true},{"actual":[[[1,6],[1,6]],22,2],"check":"case 3","expected":[[[1,6]],22,2],"passed":false},{"actual":[[[6,23],[6,23],[17,34],[17,34],[17,34],[17,34],[20,23],[20,23],[20,23],[20,23]],26,2],"check":"case 4","expected":[[[6,23],[17,34],[20,23]],26,2],"passed":false},{"actual":[[],8,1],"check":"case 5","expected":[[],8,1],"passed":true},{"actual":[[[14,29]],6,2],"check":"case 6","expected":[[[14,29]],6,2],"passed":true},{"actual":[[[10,18],[10,18],[10,19],[10,21],[10,21],[18,21],[18,21]],12,3],"check":"case 7","expected":[[[10,18],[10,19],[10,21],[18,21]],12,3],"passed":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"case 0\", \"actual\": [[[6, 12], [12, 25]], 28, 2], \"expected\": [[[6, 12], [12, 25]], 28, 2], \"passed\": true}, {\"check\": \"case 1\", \"actual\": [[[8, 12]], 2, 2], \"expected\": [[[8, 12]], 2, 2], \"passed\": true}, {\"check\": \"case 2\", \"actual\": [[], 13, 1], \"expected\": [[], 13, 1], \"passed\": true}, {\"check\": \"case 3\", \"actual\": [[[1, 6], [1, 6]], 22, 2], \"expected\": [[[1, 6]], 22, 2], \"passed\": false}, {\"check\": \"case 4\", \"actual\": [[[6, 23], [6, 23], [17, 34], [17, 34], [17, 34], [17, 34], [20, 23], [20, 23], [20, 23], [20, 23]], 26, 2], \"expected\": [[[6, 23], [17, 34], [20, 23]], 26, 2], \"passed\": false}, {\"check\": \"case 5\", \"actual\": [[], 8, 1], \"expected\": [[], 8, 1], \"passed\": true}, {\"check\": \"case 6\", \"actual\": [[[14, 29]], 6, 2], \"expected\": [[[14, 29]], 6, 2], \"passed\": true}, {\"check\": \"case 7\", \"actual\": [[[10, 18], [10, 18], [10, 19], [10, 21], [10, 21], [18, 21], [18, 21]], 12, 3], \"expected\": [[[10, 18], [10, 19], [10, 21], [18, 21]], 12, 3], \"passed\": false}], \"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."}}