{"abstract":"Large primitives are placed on the wrong side of the split.","category":"Collision detection broadphase","checks":8,"contract":"solve(prims): top-down BVH build step. Split axis = larger centroid extent (x on ties). Primitives sorted by centroid on that axis (index tiebreak). Cost of split k = 1 + (P(L)*k + P(R)*(n-k))/P(parent) with P the box perimeter of the primitives' bounds; leaf cost n. Return [best k or 0 for leaf, axis, cost rounded to 6, sorted left indices].","evaluation_group":"w2-collision_detection_broadphase-sah-split-selection","failed_approach":"Sorting by the max edge fails for the mirrored reason.","family":"w2-collision_detection_broadphase-sah-split-selection-partition-sort-key","id":"FA-87431","implementations":{"attempt":{"sha256":"33801e48c794576f2cfba28bc5f2c91b15b03a8512cd9b3e1a9442761508d1d9","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nimport math\nN = 1\nobservations = []\ndef solve(prims):\n    n = len(prims)\n    cent = [((p[0] + p[2]) / 2, (p[1] + p[3]) / 2) for p in prims]\n    ex = max(c[0] for c in cent) - min(c[0] for c in cent)\n    ey = max(c[1] for c in cent) - min(c[1] for c in cent)\n    axis = 0 if ex >= ey else 1\n    order = sorted(range(n), key=lambda i: (prims[i][axis + 2], i))\n    def box(ids):\n        return [min(prims[i][0] for i in ids), min(prims[i][1] for i in ids), max(prims[i][2] for i in ids), max(prims[i][3] for i in ids)]\n    def perim(b):\n        return 2 * ((b[2] - b[0]) + (b[3] - b[1]))\n    pa = perim(box(order))\n    best_k, best = 0, float(n)\n    for k in range(1, n):\n        cost = 1 + (perim(box(order[:k])) * k + perim(box(order[k:])) * (n - k)) / pa\n        if cost < best:\n            best_k, best = k, cost\n    return [best_k, axis, round(best, 6), sorted(order[:best_k])]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\nfixtures = [[[[[[6, 0, 9, 2], [9, 9, 11, 12], [1, 8, 3, 10], [1, 2, 3, 7], [5, 2, 11, 4]]], [3, 1, 4.590909, [0, 3, 4]]], [[[[9, 3, 15, 6], [2, 1, 3, 6], [10, 4, 11, 9]]], [1, 0, 2.428571, [1]]], [[[[4, 4, 11, 5], [6, 0, 10, 5], [10, 6, 16, 11], [2, 2, 4, 9], [7, 8, 11, 15], [6, 10, 13, 11], [7, 7, 8, 12]]], [4, 0, 5.862069, [0, 1, 3, 6]]], [[[[9, 9, 14, 15], [3, 8, 7, 14], [7, 4, 11, 9], [9, 0, 13, 1], [10, 0, 16, 7], [1, 2, 8, 6]]], [2, 1, 5.4, [3, 4]]], [[[[0, 5, 5, 7], [8, 4, 14, 11], [8, 3, 11, 4]]], [1, 0, 2.590909, [0]]], [[[[4, 10, 10, 15], [7, 8, 13, 15], [4, 2, 8, 8], [9, 9, 11, 12], [0, 8, 5, 15]]], [2, 0, 4.461538, [2, 4]]], [[[[6, 2, 10, 9], [10, 2, 13, 6], [4, 6, 10, 7], [6, 8, 13, 10], [5, 4, 7, 9], [10, 4, 11, 6]]], [2, 0, 5.823529, [2, 4]]], [[[[6, 1, 10, 5], [5, 6, 10, 7], [6, 5, 9, 11], [8, 6, 14, 12]]], [2, 1, 3.6, [0, 1]]]], [[[[[2, 9, 5, 11], [5, 10, 8, 13]]], [0, 0, 2.0, []]], [[[[10, 6, 11, 9], [2, 1, 8, 4], [9, 10, 11, 17], [3, 8, 9, 9], [7, 7, 11, 11]]], [3, 1, 4.16, [0, 1, 3]]], [[[[9, 3, 13, 6], [4, 9, 6, 15]]], [1, 1, 1.714286, [0]]], [[[[2, 6, 9, 7], [9, 0, 13, 6], [10, 9, 16, 10], [7, 1, 9, 5], [5, 9, 11, 10], [4, 1, 8, 4]]], [3, 0, 5.25, [0, 3, 5]]], [[[[5, 9, 9, 12], [6, 4, 11, 11], [0, 4, 5, 7], [10, 4, 16, 7], [6, 4, 7, 10], [7, 9, 13, 15], [9, 8, 11, 9]]], [3, 0, 6.0, [0, 2, 4]]], [[[[10, 7, 14, 14], [5, 1, 8, 8], [10, 8, 15, 11], [2, 7, 9, 12], [0, 1, 3, 5], [5, 8, 12, 9], [1, 2, 4, 3]]], [4, 0, 5.678571, [1, 3, 4, 6]]], [[[[6, 10, 9, 11], [0, 9, 5, 14], [2, 8, 7, 12], [5, 10, 7, 13], [6, 3, 12, 10], [5, 5, 8, 12], [3, 4, 7, 10]]], [4, 0, 6.043478, [1, 2, 3, 6]]], [[[[4, 10, 10, 16], [3, 8, 6, 14], [4, 10, 8, 16], [8, 3, 10, 8]]], [1, 1, 3.6, [3]]]], [[[[[2, 1, 7, 3], [2, 3, 3, 9], [2, 1, 8, 8], [7, 4, 10, 5], [1, 9, 5, 16], [2, 2, 9, 8]]], [5, 1, 4.791667, [0, 1, 2, 3, 5]]], [[[[8, 1, 13, 5], [10, 10, 16, 17], [6, 4, 7, 6], [3, 10, 10, 17], [0, 1, 3, 3]]], [2, 0, 4.46875, [2, 4]]], [[[[6, 3, 8, 6], [7, 7, 8, 14], [5, 6, 7, 7], [9, 0, 16, 3], [6, 10, 13, 11], [3, 3, 4, 9]]], [3, 0, 4.888889, [0, 2, 5]]], [[[[0, 0, 3, 2], [10, 3, 14, 6], [3, 2, 10, 7], [10, 9, 17, 13], [5, 0, 10, 5], [5, 10, 11, 12]]], [3, 0, 4.9, [0, 2, 4]]], [[[[6, 9, 11, 16], [3, 2, 8, 7], [9, 4, 15, 8], [0, 0, 2, 3], [10, 5, 17, 12], [7, 6, 8, 9]]], [3, 0, 4.636364, [1, 3, 5]]], [[[[1, 7, 7, 13], [5, 0, 12, 3], [0, 9, 4, 12], [8, 6, 9, 7], [0, 4, 7, 7], [3, 8, 5, 10]]], [3, 1, 4.84, [1, 3, 4]]], [[[[4, 2, 11, 8], [3, 2, 6, 5], [5, 8, 11, 9], [9, 8, 15, 14], [6, 7, 9, 13]]], [2, 0, 4.291667, [0, 1]]], [[[[5, 2, 11, 3], [5, 9, 8, 16], [0, 7, 5, 12], [6, 7, 11, 10], [4, 9, 7, 11]]], [2, 1, 4.16, [0, 3]]]], [[[[[1, 3, 3, 9], [3, 9, 10, 14], [9, 7, 15, 9], [10, 10, 11, 12], [0, 5, 4, 12], [10, 3, 13, 5]]], [3, 0, 5.153846, [0, 1, 4]]], [[[[6, 5, 10, 11], [1, 1, 8, 4], [6, 2, 7, 8], [0, 10, 6, 12], [6, 10, 10, 11], [6, 2, 11, 9], [9, 5, 12, 7]]], [4, 1, 6.521739, [1, 2, 5, 6]]], [[[[6, 10, 7, 12], [5, 4, 12, 9], [3, 5, 7, 12], [8, 1, 11, 4], [1, 4, 6, 7]]], [3, 1, 4.590909, [1, 3, 4]]], [[[[8, 2, 10, 3], [6, 1, 9, 7], [6, 10, 10, 15], [5, 0, 9, 5], [2, 10, 9, 11], [2, 1, 6, 6], [5, 9, 9, 10]]], [4, 1, 5.434783, [0, 1, 3, 5]]], [[[[6, 10, 7, 17], [10, 9, 15, 12], [2, 10, 8, 14], [1, 4, 5, 6]]], [2, 0, 3.518519, [2, 3]]], [[[[10, 1, 15, 7], [3, 5, 9, 11], [4, 10, 7, 14], [3, 7, 7, 9], [3, 6, 8, 9], [5, 8, 9, 10], [7, 3, 9, 5]]], [2, 1, 5.12, [0, 6]]], [[[[10, 4, 11, 7], [3, 6, 10, 10], [4, 8, 7, 14], [1, 3, 8, 9]]], [0, 0, 4.0, []]], [[[[7, 1, 8, 4], [10, 0, 12, 4], [9, 3, 15, 8]]], [2, 0, 2.8125, [0, 1]]]], [[[[[7, 6, 12, 12], [7, 10, 9, 15], [3, 6, 4, 7], [1, 2, 5, 5], [9, 7, 14, 9]]], [2, 1, 3.538462, [2, 3]]], [[[[7, 0, 10, 7], [7, 8, 14, 15], [0, 9, 4, 14], [6, 10, 12, 17], [0, 10, 7, 14], [6, 9, 10, 15], [2, 9, 4, 15]]], [2, 1, 5.645161, [0, 1]]], [[[[1, 6, 3, 12], [8, 6, 12, 9]]], [1, 0, 1.882353, [0]]], [[[[2, 6, 5, 11], [1, 9, 8, 14]]], [0, 1, 2.0, []]], [[[[1, 6, 6, 7], [10, 4, 13, 9], [0, 9, 7, 13], [0, 1, 3, 2], [3, 2, 9, 5], [0, 2, 2, 4]]], [2, 0, 5.32, [3, 5]]], [[[[5, 9, 10, 10], [8, 3, 13, 7], [8, 10, 10, 17], [3, 2, 10, 4], [2, 5, 9, 10]]], [3, 1, 4.192308, [1, 3, 4]]], [[[[0, 0, 4, 5], [7, 8, 12, 12], [7, 0, 11, 3], [10, 8, 12, 12]]], [2, 0, 3.083333, [0, 2]]], [[[[6, 7, 11, 9], [9, 4, 16, 6]]], [0, 0, 2.0, []]]]]\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":"408a47e3d881c0947e9322c425e1a965b7f638767bf2b5d09c355073510d6729","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nimport math\nN = 1\nobservations = []\ndef solve(prims):\n    n = len(prims)\n    cent = [((p[0] + p[2]) / 2, (p[1] + p[3]) / 2) for p in prims]\n    ex = max(c[0] for c in cent) - min(c[0] for c in cent)\n    ey = max(c[1] for c in cent) - min(c[1] for c in cent)\n    axis = 0 if ex >= ey else 1\n    order = sorted(range(n), key=lambda i: (prims[i][axis], i))\n    def box(ids):\n        return [min(prims[i][0] for i in ids), min(prims[i][1] for i in ids), max(prims[i][2] for i in ids), max(prims[i][3] for i in ids)]\n    def perim(b):\n        return 2 * ((b[2] - b[0]) + (b[3] - b[1]))\n    pa = perim(box(order))\n    best_k, best = 0, float(n)\n    for k in range(1, n):\n        cost = 1 + (perim(box(order[:k])) * k + perim(box(order[k:])) * (n - k)) / pa\n        if cost < best:\n            best_k, best = k, cost\n    return [best_k, axis, round(best, 6), sorted(order[:best_k])]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\nfixtures = [[[[[[6, 0, 9, 2], [9, 9, 11, 12], [1, 8, 3, 10], [1, 2, 3, 7], [5, 2, 11, 4]]], [3, 1, 4.590909, [0, 3, 4]]], [[[[9, 3, 15, 6], [2, 1, 3, 6], [10, 4, 11, 9]]], [1, 0, 2.428571, [1]]], [[[[4, 4, 11, 5], [6, 0, 10, 5], [10, 6, 16, 11], [2, 2, 4, 9], [7, 8, 11, 15], [6, 10, 13, 11], [7, 7, 8, 12]]], [4, 0, 5.862069, [0, 1, 3, 6]]], [[[[9, 9, 14, 15], [3, 8, 7, 14], [7, 4, 11, 9], [9, 0, 13, 1], [10, 0, 16, 7], [1, 2, 8, 6]]], [2, 1, 5.4, [3, 4]]], [[[[0, 5, 5, 7], [8, 4, 14, 11], [8, 3, 11, 4]]], [1, 0, 2.590909, [0]]], [[[[4, 10, 10, 15], [7, 8, 13, 15], [4, 2, 8, 8], [9, 9, 11, 12], [0, 8, 5, 15]]], [2, 0, 4.461538, [2, 4]]], [[[[6, 2, 10, 9], [10, 2, 13, 6], [4, 6, 10, 7], [6, 8, 13, 10], [5, 4, 7, 9], [10, 4, 11, 6]]], [2, 0, 5.823529, [2, 4]]], [[[[6, 1, 10, 5], [5, 6, 10, 7], [6, 5, 9, 11], [8, 6, 14, 12]]], [2, 1, 3.6, [0, 1]]]], [[[[[2, 9, 5, 11], [5, 10, 8, 13]]], [0, 0, 2.0, []]], [[[[10, 6, 11, 9], [2, 1, 8, 4], [9, 10, 11, 17], [3, 8, 9, 9], [7, 7, 11, 11]]], [3, 1, 4.16, [0, 1, 3]]], [[[[9, 3, 13, 6], [4, 9, 6, 15]]], [1, 1, 1.714286, [0]]], [[[[2, 6, 9, 7], [9, 0, 13, 6], [10, 9, 16, 10], [7, 1, 9, 5], [5, 9, 11, 10], [4, 1, 8, 4]]], [3, 0, 5.25, [0, 3, 5]]], [[[[5, 9, 9, 12], [6, 4, 11, 11], [0, 4, 5, 7], [10, 4, 16, 7], [6, 4, 7, 10], [7, 9, 13, 15], [9, 8, 11, 9]]], [3, 0, 6.0, [0, 2, 4]]], [[[[10, 7, 14, 14], [5, 1, 8, 8], [10, 8, 15, 11], [2, 7, 9, 12], [0, 1, 3, 5], [5, 8, 12, 9], [1, 2, 4, 3]]], [4, 0, 5.678571, [1, 3, 4, 6]]], [[[[6, 10, 9, 11], [0, 9, 5, 14], [2, 8, 7, 12], [5, 10, 7, 13], [6, 3, 12, 10], [5, 5, 8, 12], [3, 4, 7, 10]]], [4, 0, 6.043478, [1, 2, 3, 6]]], [[[[4, 10, 10, 16], [3, 8, 6, 14], [4, 10, 8, 16], [8, 3, 10, 8]]], [1, 1, 3.6, [3]]]], [[[[[2, 1, 7, 3], [2, 3, 3, 9], [2, 1, 8, 8], [7, 4, 10, 5], [1, 9, 5, 16], [2, 2, 9, 8]]], [5, 1, 4.791667, [0, 1, 2, 3, 5]]], [[[[8, 1, 13, 5], [10, 10, 16, 17], [6, 4, 7, 6], [3, 10, 10, 17], [0, 1, 3, 3]]], [2, 0, 4.46875, [2, 4]]], [[[[6, 3, 8, 6], [7, 7, 8, 14], [5, 6, 7, 7], [9, 0, 16, 3], [6, 10, 13, 11], [3, 3, 4, 9]]], [3, 0, 4.888889, [0, 2, 5]]], [[[[0, 0, 3, 2], [10, 3, 14, 6], [3, 2, 10, 7], [10, 9, 17, 13], [5, 0, 10, 5], [5, 10, 11, 12]]], [3, 0, 4.9, [0, 2, 4]]], [[[[6, 9, 11, 16], [3, 2, 8, 7], [9, 4, 15, 8], [0, 0, 2, 3], [10, 5, 17, 12], [7, 6, 8, 9]]], [3, 0, 4.636364, [1, 3, 5]]], [[[[1, 7, 7, 13], [5, 0, 12, 3], [0, 9, 4, 12], [8, 6, 9, 7], [0, 4, 7, 7], [3, 8, 5, 10]]], [3, 1, 4.84, [1, 3, 4]]], [[[[4, 2, 11, 8], [3, 2, 6, 5], [5, 8, 11, 9], [9, 8, 15, 14], [6, 7, 9, 13]]], [2, 0, 4.291667, [0, 1]]], [[[[5, 2, 11, 3], [5, 9, 8, 16], [0, 7, 5, 12], [6, 7, 11, 10], [4, 9, 7, 11]]], [2, 1, 4.16, [0, 3]]]], [[[[[1, 3, 3, 9], [3, 9, 10, 14], [9, 7, 15, 9], [10, 10, 11, 12], [0, 5, 4, 12], [10, 3, 13, 5]]], [3, 0, 5.153846, [0, 1, 4]]], [[[[6, 5, 10, 11], [1, 1, 8, 4], [6, 2, 7, 8], [0, 10, 6, 12], [6, 10, 10, 11], [6, 2, 11, 9], [9, 5, 12, 7]]], [4, 1, 6.521739, [1, 2, 5, 6]]], [[[[6, 10, 7, 12], [5, 4, 12, 9], [3, 5, 7, 12], [8, 1, 11, 4], [1, 4, 6, 7]]], [3, 1, 4.590909, [1, 3, 4]]], [[[[8, 2, 10, 3], [6, 1, 9, 7], [6, 10, 10, 15], [5, 0, 9, 5], [2, 10, 9, 11], [2, 1, 6, 6], [5, 9, 9, 10]]], [4, 1, 5.434783, [0, 1, 3, 5]]], [[[[6, 10, 7, 17], [10, 9, 15, 12], [2, 10, 8, 14], [1, 4, 5, 6]]], [2, 0, 3.518519, [2, 3]]], [[[[10, 1, 15, 7], [3, 5, 9, 11], [4, 10, 7, 14], [3, 7, 7, 9], [3, 6, 8, 9], [5, 8, 9, 10], [7, 3, 9, 5]]], [2, 1, 5.12, [0, 6]]], [[[[10, 4, 11, 7], [3, 6, 10, 10], [4, 8, 7, 14], [1, 3, 8, 9]]], [0, 0, 4.0, []]], [[[[7, 1, 8, 4], [10, 0, 12, 4], [9, 3, 15, 8]]], [2, 0, 2.8125, [0, 1]]]], [[[[[7, 6, 12, 12], [7, 10, 9, 15], [3, 6, 4, 7], [1, 2, 5, 5], [9, 7, 14, 9]]], [2, 1, 3.538462, [2, 3]]], [[[[7, 0, 10, 7], [7, 8, 14, 15], [0, 9, 4, 14], [6, 10, 12, 17], [0, 10, 7, 14], [6, 9, 10, 15], [2, 9, 4, 15]]], [2, 1, 5.645161, [0, 1]]], [[[[1, 6, 3, 12], [8, 6, 12, 9]]], [1, 0, 1.882353, [0]]], [[[[2, 6, 5, 11], [1, 9, 8, 14]]], [0, 1, 2.0, []]], [[[[1, 6, 6, 7], [10, 4, 13, 9], [0, 9, 7, 13], [0, 1, 3, 2], [3, 2, 9, 5], [0, 2, 2, 4]]], [2, 0, 5.32, [3, 5]]], [[[[5, 9, 10, 10], [8, 3, 13, 7], [8, 10, 10, 17], [3, 2, 10, 4], [2, 5, 9, 10]]], [3, 1, 4.192308, [1, 3, 4]]], [[[[0, 0, 4, 5], [7, 8, 12, 12], [7, 0, 11, 3], [10, 8, 12, 12]]], [2, 0, 3.083333, [0, 2]]], [[[[6, 7, 11, 9], [9, 4, 16, 6]]], [0, 0, 2.0, []]]]]\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":"dd31804c056b9cc3684df3f97f0a32ee7f61b9c0983b7b1e4639efc7464cc8c4","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nimport math\nN = 1\nobservations = []\ndef solve(prims):\n    n = len(prims)\n    cent = [((p[0] + p[2]) / 2, (p[1] + p[3]) / 2) for p in prims]\n    ex = max(c[0] for c in cent) - min(c[0] for c in cent)\n    ey = max(c[1] for c in cent) - min(c[1] for c in cent)\n    axis = 0 if ex >= ey else 1\n    order = sorted(range(n), key=lambda i: (cent[i][axis], i))\n    def box(ids):\n        return [min(prims[i][0] for i in ids), min(prims[i][1] for i in ids), max(prims[i][2] for i in ids), max(prims[i][3] for i in ids)]\n    def perim(b):\n        return 2 * ((b[2] - b[0]) + (b[3] - b[1]))\n    pa = perim(box(order))\n    best_k, best = 0, float(n)\n    for k in range(1, n):\n        cost = 1 + (perim(box(order[:k])) * k + perim(box(order[k:])) * (n - k)) / pa\n        if cost < best:\n            best_k, best = k, cost\n    return [best_k, axis, round(best, 6), sorted(order[:best_k])]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\nfixtures = [[[[[[6, 0, 9, 2], [9, 9, 11, 12], [1, 8, 3, 10], [1, 2, 3, 7], [5, 2, 11, 4]]], [3, 1, 4.590909, [0, 3, 4]]], [[[[9, 3, 15, 6], [2, 1, 3, 6], [10, 4, 11, 9]]], [1, 0, 2.428571, [1]]], [[[[4, 4, 11, 5], [6, 0, 10, 5], [10, 6, 16, 11], [2, 2, 4, 9], [7, 8, 11, 15], [6, 10, 13, 11], [7, 7, 8, 12]]], [4, 0, 5.862069, [0, 1, 3, 6]]], [[[[9, 9, 14, 15], [3, 8, 7, 14], [7, 4, 11, 9], [9, 0, 13, 1], [10, 0, 16, 7], [1, 2, 8, 6]]], [2, 1, 5.4, [3, 4]]], [[[[0, 5, 5, 7], [8, 4, 14, 11], [8, 3, 11, 4]]], [1, 0, 2.590909, [0]]], [[[[4, 10, 10, 15], [7, 8, 13, 15], [4, 2, 8, 8], [9, 9, 11, 12], [0, 8, 5, 15]]], [2, 0, 4.461538, [2, 4]]], [[[[6, 2, 10, 9], [10, 2, 13, 6], [4, 6, 10, 7], [6, 8, 13, 10], [5, 4, 7, 9], [10, 4, 11, 6]]], [2, 0, 5.823529, [2, 4]]], [[[[6, 1, 10, 5], [5, 6, 10, 7], [6, 5, 9, 11], [8, 6, 14, 12]]], [2, 1, 3.6, [0, 1]]]], [[[[[2, 9, 5, 11], [5, 10, 8, 13]]], [0, 0, 2.0, []]], [[[[10, 6, 11, 9], [2, 1, 8, 4], [9, 10, 11, 17], [3, 8, 9, 9], [7, 7, 11, 11]]], [3, 1, 4.16, [0, 1, 3]]], [[[[9, 3, 13, 6], [4, 9, 6, 15]]], [1, 1, 1.714286, [0]]], [[[[2, 6, 9, 7], [9, 0, 13, 6], [10, 9, 16, 10], [7, 1, 9, 5], [5, 9, 11, 10], [4, 1, 8, 4]]], [3, 0, 5.25, [0, 3, 5]]], [[[[5, 9, 9, 12], [6, 4, 11, 11], [0, 4, 5, 7], [10, 4, 16, 7], [6, 4, 7, 10], [7, 9, 13, 15], [9, 8, 11, 9]]], [3, 0, 6.0, [0, 2, 4]]], [[[[10, 7, 14, 14], [5, 1, 8, 8], [10, 8, 15, 11], [2, 7, 9, 12], [0, 1, 3, 5], [5, 8, 12, 9], [1, 2, 4, 3]]], [4, 0, 5.678571, [1, 3, 4, 6]]], [[[[6, 10, 9, 11], [0, 9, 5, 14], [2, 8, 7, 12], [5, 10, 7, 13], [6, 3, 12, 10], [5, 5, 8, 12], [3, 4, 7, 10]]], [4, 0, 6.043478, [1, 2, 3, 6]]], [[[[4, 10, 10, 16], [3, 8, 6, 14], [4, 10, 8, 16], [8, 3, 10, 8]]], [1, 1, 3.6, [3]]]], [[[[[2, 1, 7, 3], [2, 3, 3, 9], [2, 1, 8, 8], [7, 4, 10, 5], [1, 9, 5, 16], [2, 2, 9, 8]]], [5, 1, 4.791667, [0, 1, 2, 3, 5]]], [[[[8, 1, 13, 5], [10, 10, 16, 17], [6, 4, 7, 6], [3, 10, 10, 17], [0, 1, 3, 3]]], [2, 0, 4.46875, [2, 4]]], [[[[6, 3, 8, 6], [7, 7, 8, 14], [5, 6, 7, 7], [9, 0, 16, 3], [6, 10, 13, 11], [3, 3, 4, 9]]], [3, 0, 4.888889, [0, 2, 5]]], [[[[0, 0, 3, 2], [10, 3, 14, 6], [3, 2, 10, 7], [10, 9, 17, 13], [5, 0, 10, 5], [5, 10, 11, 12]]], [3, 0, 4.9, [0, 2, 4]]], [[[[6, 9, 11, 16], [3, 2, 8, 7], [9, 4, 15, 8], [0, 0, 2, 3], [10, 5, 17, 12], [7, 6, 8, 9]]], [3, 0, 4.636364, [1, 3, 5]]], [[[[1, 7, 7, 13], [5, 0, 12, 3], [0, 9, 4, 12], [8, 6, 9, 7], [0, 4, 7, 7], [3, 8, 5, 10]]], [3, 1, 4.84, [1, 3, 4]]], [[[[4, 2, 11, 8], [3, 2, 6, 5], [5, 8, 11, 9], [9, 8, 15, 14], [6, 7, 9, 13]]], [2, 0, 4.291667, [0, 1]]], [[[[5, 2, 11, 3], [5, 9, 8, 16], [0, 7, 5, 12], [6, 7, 11, 10], [4, 9, 7, 11]]], [2, 1, 4.16, [0, 3]]]], [[[[[1, 3, 3, 9], [3, 9, 10, 14], [9, 7, 15, 9], [10, 10, 11, 12], [0, 5, 4, 12], [10, 3, 13, 5]]], [3, 0, 5.153846, [0, 1, 4]]], [[[[6, 5, 10, 11], [1, 1, 8, 4], [6, 2, 7, 8], [0, 10, 6, 12], [6, 10, 10, 11], [6, 2, 11, 9], [9, 5, 12, 7]]], [4, 1, 6.521739, [1, 2, 5, 6]]], [[[[6, 10, 7, 12], [5, 4, 12, 9], [3, 5, 7, 12], [8, 1, 11, 4], [1, 4, 6, 7]]], [3, 1, 4.590909, [1, 3, 4]]], [[[[8, 2, 10, 3], [6, 1, 9, 7], [6, 10, 10, 15], [5, 0, 9, 5], [2, 10, 9, 11], [2, 1, 6, 6], [5, 9, 9, 10]]], [4, 1, 5.434783, [0, 1, 3, 5]]], [[[[6, 10, 7, 17], [10, 9, 15, 12], [2, 10, 8, 14], [1, 4, 5, 6]]], [2, 0, 3.518519, [2, 3]]], [[[[10, 1, 15, 7], [3, 5, 9, 11], [4, 10, 7, 14], [3, 7, 7, 9], [3, 6, 8, 9], [5, 8, 9, 10], [7, 3, 9, 5]]], [2, 1, 5.12, [0, 6]]], [[[[10, 4, 11, 7], [3, 6, 10, 10], [4, 8, 7, 14], [1, 3, 8, 9]]], [0, 0, 4.0, []]], [[[[7, 1, 8, 4], [10, 0, 12, 4], [9, 3, 15, 8]]], [2, 0, 2.8125, [0, 1]]]], [[[[[7, 6, 12, 12], [7, 10, 9, 15], [3, 6, 4, 7], [1, 2, 5, 5], [9, 7, 14, 9]]], [2, 1, 3.538462, [2, 3]]], [[[[7, 0, 10, 7], [7, 8, 14, 15], [0, 9, 4, 14], [6, 10, 12, 17], [0, 10, 7, 14], [6, 9, 10, 15], [2, 9, 4, 15]]], [2, 1, 5.645161, [0, 1]]], [[[[1, 6, 3, 12], [8, 6, 12, 9]]], [1, 0, 1.882353, [0]]], [[[[2, 6, 5, 11], [1, 9, 8, 14]]], [0, 1, 2.0, []]], [[[[1, 6, 6, 7], [10, 4, 13, 9], [0, 9, 7, 13], [0, 1, 3, 2], [3, 2, 9, 5], [0, 2, 2, 4]]], [2, 0, 5.32, [3, 5]]], [[[[5, 9, 10, 10], [8, 3, 13, 7], [8, 10, 10, 17], [3, 2, 10, 4], [2, 5, 9, 10]]], [3, 1, 4.192308, [1, 3, 4]]], [[[[0, 0, 4, 5], [7, 8, 12, 12], [7, 0, 11, 3], [10, 8, 12, 12]]], [2, 0, 3.083333, [0, 2]]], [[[[6, 7, 11, 9], [9, 4, 16, 6]]], [0, 0, 2.0, []]]]]\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-sah-split-selection-partition-sort-key","generated_at":"2026-09-29T14:50:58.617329+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":"Sort by centroid coordinate.","root_cause":"The sort key reads the min coordinate on the axis.","sha256":"b913fc1f4de45413d221974929ba7bd629e8bf420550f164dfe562694221413f","title":"Primitives are ordered by their minimum edge instead of centroid · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verification":{"attempt":{"elapsed_ms":40.158,"exit_code":1,"observations":[{"actual":[3,1,4.590909,[0,3,4]],"check":"case 0","expected":[3,1,4.590909,[0,3,4]],"passed":true},{"actual":[1,0,2.428571,[1]],"check":"case 1","expected":[1,0,2.428571,[1]],"passed":true},{"actual":[4,0,5.862069,[0,1,3,6]],"check":"case 2","expected":[4,0,5.862069,[0,1,3,6]],"passed":true},{"actual":[3,1,5.4,[3,4,5]],"check":"case 3","expected":[2,1,5.4,[3,4]],"passed":false},{"actual":[1,0,2.590909,[0]],"check":"case 4","expected":[1,0,2.590909,[0]],"passed":true},{"actual":[2,0,4.461538,[2,4]],"check":"case 5","expected":[2,0,4.461538,[2,4]],"passed":true},{"actual":[3,0,5.941176,[0,2,4]],"check":"case 6","expected":[2,0,5.823529,[2,4]],"passed":false},{"actual":[2,1,3.6,[0,1]],"check":"case 7","expected":[2,1,3.6,[0,1]],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"case 0\", \"actual\": [3, 1, 4.590909, [0, 3, 4]], \"expected\": [3, 1, 4.590909, [0, 3, 4]], \"passed\": true}, {\"check\": \"case 1\", \"actual\": [1, 0, 2.428571, [1]], \"expected\": [1, 0, 2.428571, [1]], \"passed\": true}, {\"check\": \"case 2\", \"actual\": [4, 0, 5.862069, [0, 1, 3, 6]], \"expected\": [4, 0, 5.862069, [0, 1, 3, 6]], \"passed\": true}, {\"check\": \"case 3\", \"actual\": [3, 1, 5.4, [3, 4, 5]], \"expected\": [2, 1, 5.4, [3, 4]], \"passed\": false}, {\"check\": \"case 4\", \"actual\": [1, 0, 2.590909, [0]], \"expected\": [1, 0, 2.590909, [0]], \"passed\": true}, {\"check\": \"case 5\", \"actual\": [2, 0, 4.461538, [2, 4]], \"expected\": [2, 0, 4.461538, [2, 4]], \"passed\": true}, {\"check\": \"case 6\", \"actual\": [3, 0, 5.941176, [0, 2, 4]], \"expected\": [2, 0, 5.823529, [2, 4]], \"passed\": false}, {\"check\": \"case 7\", \"actual\": [2, 1, 3.6, [0, 1]], \"expected\": [2, 1, 3.6, [0, 1]], \"passed\": true}], \"passed\": false}\n"},"broken":{"elapsed_ms":40.865,"exit_code":1,"observations":[{"actual":[3,1,4.590909,[0,3,4]],"check":"case 0","expected":[3,1,4.590909,[0,3,4]],"passed":true},{"actual":[1,0,2.428571,[1]],"check":"case 1","expected":[1,0,2.428571,[1]],"passed":true},{"actual":[3,0,5.482759,[0,1,3]],"check":"case 2","expected":[4,0,5.862069,[0,1,3,6]],"passed":false},{"actual":[2,1,5.4,[3,4]],"check":"case 3","expected":[2,1,5.4,[3,4]],"passed":true},{"actual":[1,0,2.590909,[0]],"check":"case 4","expected":[1,0,2.590909,[0]],"passed":true},{"actual":[3,0,4.653846,[0,2,4]],"check":"case 5","expected":[2,0,4.461538,[2,4]],"passed":false},{"actual":[2,0,5.823529,[2,4]],"check":"case 6","expected":[2,0,5.823529,[2,4]],"passed":true},{"actual":[1,1,3.8,[0]],"check":"case 7","expected":[2,1,3.6,[0,1]],"passed":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"case 0\", \"actual\": [3, 1, 4.590909, [0, 3, 4]], \"expected\": [3, 1, 4.590909, [0, 3, 4]], \"passed\": true}, {\"check\": \"case 1\", \"actual\": [1, 0, 2.428571, [1]], \"expected\": [1, 0, 2.428571, [1]], \"passed\": true}, {\"check\": \"case 2\", \"actual\": [3, 0, 5.482759, [0, 1, 3]], \"expected\": [4, 0, 5.862069, [0, 1, 3, 6]], \"passed\": false}, {\"check\": \"case 3\", \"actual\": [2, 1, 5.4, [3, 4]], \"expected\": [2, 1, 5.4, [3, 4]], \"passed\": true}, {\"check\": \"case 4\", \"actual\": [1, 0, 2.590909, [0]], \"expected\": [1, 0, 2.590909, [0]], \"passed\": true}, {\"check\": \"case 5\", \"actual\": [3, 0, 4.653846, [0, 2, 4]], \"expected\": [2, 0, 4.461538, [2, 4]], \"passed\": false}, {\"check\": \"case 6\", \"actual\": [2, 0, 5.823529, [2, 4]], \"expected\": [2, 0, 5.823529, [2, 4]], \"passed\": true}, {\"check\": \"case 7\", \"actual\": [1, 1, 3.8, [0]], \"expected\": [2, 1, 3.6, [0, 1]], \"passed\": false}], \"passed\": false}\n"},"fixed":{"elapsed_ms":41.383,"exit_code":0,"observations":[{"actual":[3,1,4.590909,[0,3,4]],"check":"case 0","expected":[3,1,4.590909,[0,3,4]],"passed":true},{"actual":[1,0,2.428571,[1]],"check":"case 1","expected":[1,0,2.428571,[1]],"passed":true},{"actual":[4,0,5.862069,[0,1,3,6]],"check":"case 2","expected":[4,0,5.862069,[0,1,3,6]],"passed":true},{"actual":[2,1,5.4,[3,4]],"check":"case 3","expected":[2,1,5.4,[3,4]],"passed":true},{"actual":[1,0,2.590909,[0]],"check":"case 4","expected":[1,0,2.590909,[0]],"passed":true},{"actual":[2,0,4.461538,[2,4]],"check":"case 5","expected":[2,0,4.461538,[2,4]],"passed":true},{"actual":[2,0,5.823529,[2,4]],"check":"case 6","expected":[2,0,5.823529,[2,4]],"passed":true},{"actual":[2,1,3.6,[0,1]],"check":"case 7","expected":[2,1,3.6,[0,1]],"passed":true}],"passed":true,"stderr":"","stdout":"{\"observations\": [{\"check\": \"case 0\", \"actual\": [3, 1, 4.590909, [0, 3, 4]], \"expected\": [3, 1, 4.590909, [0, 3, 4]], \"passed\": true}, {\"check\": \"case 1\", \"actual\": [1, 0, 2.428571, [1]], \"expected\": [1, 0, 2.428571, [1]], \"passed\": true}, {\"check\": \"case 2\", \"actual\": [4, 0, 5.862069, [0, 1, 3, 6]], \"expected\": [4, 0, 5.862069, [0, 1, 3, 6]], \"passed\": true}, {\"check\": \"case 3\", \"actual\": [2, 1, 5.4, [3, 4]], \"expected\": [2, 1, 5.4, [3, 4]], \"passed\": true}, {\"check\": \"case 4\", \"actual\": [1, 0, 2.590909, [0]], \"expected\": [1, 0, 2.590909, [0]], \"passed\": true}, {\"check\": \"case 5\", \"actual\": [2, 0, 4.461538, [2, 4]], \"expected\": [2, 0, 4.461538, [2, 4]], \"passed\": true}, {\"check\": \"case 6\", \"actual\": [2, 0, 5.823529, [2, 4]], \"expected\": [2, 0, 5.823529, [2, 4]], \"passed\": true}, {\"check\": \"case 7\", \"actual\": [2, 1, 3.6, [0, 1]], \"expected\": [2, 1, 3.6, [0, 1]], \"passed\": true}], \"passed\": true}\n"}},"verified":true,"visibility":"public"}