FA-87341 / Collision detection broadphase / Open access
Sweep processes end events before begin events at equal x · case 01
Boxes whose x extents only touch never become a pair.
ROOT CAUSE
The endpoint sort puts end markers first on coordinate ties.
VERIFIED REPAIR
Sort by (coordinate, begin before end) so touching intervals overlap.
Unsuccessful approach: Sorting by coordinate alone keeps insertion order on ties and still drops touching pairs.
Case contract
solve(boxes): boxes [id,minx,miny,maxx,maxy] with closed intervals (touching overlaps). Sweep x endpoints sorted by (coord, begin-before-end); on each begin, test y against every active box. Return sorted [min id, max id] pairs overlapping on both axes.
Why this case matters
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.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(boxes):
ev = []
for b in boxes:
ev.append((b[1], 0, b[0]))
ev.append((b[3], 1, b[0]))
ev.sort(key=lambda e: (e[0], -e[1]))
byid = {b[0]: b for b in boxes}
active = []
pairs = []
for x, kind, i in ev:
if kind == 0:
bi = byid[i]
for j in active:
bj = byid[j]
if bi[2] <= bj[4] and bj[2] <= bi[4]:
pairs.append([min(i, j), max(i, j)])
active.append(i)
else:
active.remove(i)
pairs.sort()
return pairs
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[[[[[5, -5.0, -4.0, -4.0, -2.0], [37, -5.0, -1.0, -1.0, -1.0], [26, 0.0, 1.0, 3.0, 2.0]]], []], [[[[20, 4.0, -5.0, 6.0, -3.0], [38, 0.0, 4.0, 1.0, 4.0], [22, 3.0, -6.0, 5.0, -5.0], [3, -1.0, -5.0, 0.0, -4.0], [35, -6.0, 3.0, -2.0, 7.0], [7, 2.0, -6.0, 5.0, -6.0], [28, -2.0, 1.0, 2.0, 3.0]]], [[7, 22], [20, 22], [28, 35]]], [[[[28, 6.0, -4.0, 7.0, -3.0], [32, 6.0, -4.0, 9.0, -1.0], [8, 1.0, 4.0, 3.0, 7.0], [9, 3.0, -6.0, 7.0, -4.0], [37, -6.0, 3.0, -2.0, 6.0]]], [[9, 28], [9, 32], [28, 32]]], [[[[22, -2.0, 2.0, 2.0, 3.0], [29, -5.0, 1.0, -4.0, 2.0], [4, -5.0, -2.0, -2.0, 1.0]]], [[4, 29]]], [[[[14, -3.0, 4.0, 1.0, 6.0], [11, -4.0, -6.0, 0.0, -2.0], [24, -1.0, 4.0, 3.0, 6.0], [37, 2.0, -4.0, 6.0, -3.0]]], [[14, 24]]], [[[[7, -4.0, -2.0, -3.0, 2.0], [38, -1.0, -4.0, 0.0, -4.0]]], []], [[[[16, -6.0, 6.0, -5.0, 6.0], [20, 6.0, 1.0, 10.0, 4.0], [32, 4.0, -6.0, 7.0, -5.0], [11, 4.0, -6.0, 6.0, -6.0], [39, -6.0, 5.0, -2.0, 7.0], [19, -2.0, 5.0, 0.0, 6.0], [21, 1.0, -1.0, 4.0, 3.0]]], [[11, 32], [16, 39], [19, 39]]], [[[[32, 4.0, -1.0, 6.0, -1.0], [11, 6.0, -5.0, 7.0, -1.0], [28, 2.0, 1.0, 4.0, 4.0], [2, 0.0, 5.0, 1.0, 6.0], [39, 6.0, 0.0, 10.0, 2.0]]], [[11, 32]]]], [[[[[28, -6.0, 3.0, -5.0, 6.0], [21, -5.0, 1.0, -3.0, 4.0], [19, 5.0, 2.0, 9.0, 2.0]]], [[21, 28]]], [[[[12, 3.0, -2.0, 5.0, -2.0], [32, 2.0, 1.0, 4.0, 5.0]]], []], [[[[12, 6.0, -6.0, 10.0, -2.0], [21, -3.0, -5.0, 1.0, -5.0], [1, 1.0, -6.0, 4.0, -6.0], [8, -1.0, 0.0, 2.0, 4.0], [25, 2.0, -1.0, 3.0, 2.0], [35, 1.0, -1.0, 5.0, -1.0], [32, -4.0, -3.0, -1.0, -3.0]]], [[8, 25], [25, 35]]], [[[[1, 2.0, -5.0, 4.0, -4.0], [34, 6.0, -3.0, 9.0, -3.0]]], []], [[[[11, -1.0, 2.0, 3.0, 2.0], [9, 3.0, -1.0, 4.0, 0.0], [20, 5.0, -4.0, 9.0, -2.0]]], []], [[[[38, -4.0, 2.0, 0.0, 3.0], [39, -3.0, 4.0, 0.0, 4.0], [1, -5.0, 6.0, -2.0, 9.0], [6, 1.0, 4.0, 5.0, 8.0], [35, 4.0, -1.0, 5.0, 2.0]]], []], [[[[6, 6.0, -1.0, 8.0, 0.0], [35, -2.0, 2.0, -1.0, 3.0], [24, 1.0, 0.0, 4.0, 0.0]]], []], [[[[13, 4.0, -1.0, 5.0, 2.0], [8, 5.0, -4.0, 6.0, -1.0], [34, -2.0, 3.0, 0.0, 7.0], [5, 4.0, 6.0, 6.0, 9.0], [1, -4.0, 4.0, -2.0, 8.0]]], [[1, 34], [8, 13]]]], [[[[[2, 0.0, 6.0, 1.0, 7.0], [8, 2.0, 4.0, 4.0, 6.0], [10, 2.0, 2.0, 5.0, 5.0], [6, -5.0, -6.0, -1.0, -2.0], [24, -1.0, 3.0, 0.0, 3.0]]], [[8, 10]]], [[[[34, 6.0, 0.0, 9.0, 1.0], [24, -2.0, -3.0, 2.0, -3.0]]], []], [[[[38, -1.0, 2.0, 1.0, 6.0], [11, 5.0, -3.0, 8.0, -3.0], [21, 1.0, -5.0, 2.0, -4.0]]], []], [[[[3, -6.0, 0.0, -2.0, 3.0], [8, 2.0, -5.0, 5.0, -4.0], [25, -4.0, -4.0, -3.0, -3.0], [24, 5.0, -5.0, 7.0, -4.0], [28, 5.0, 3.0, 9.0, 3.0], [35, -3.0, 4.0, 0.0, 4.0]]], [[8, 24]]], [[[[7, -4.0, -6.0, -2.0, -2.0], [4, 6.0, 4.0, 9.0, 4.0], [38, 1.0, 5.0, 2.0, 8.0], [33, -5.0, -2.0, -2.0, 1.0], [5, 5.0, 4.0, 6.0, 6.0], [2, 2.0, 4.0, 4.0, 8.0], [34, 5.0, -2.0, 6.0, -1.0]]], [[2, 38], [4, 5], [7, 33]]], [[[[24, 1.0, -4.0, 4.0, -1.0], [32, -2.0, 4.0, 2.0, 6.0], [18, -5.0, -5.0, -2.0, -2.0]]], []], [[[[35, -5.0, -1.0, -4.0, 0.0], [10, 2.0, 3.0, 5.0, 5.0], [13, -4.0, -1.0, -1.0, 0.0], [11, -1.0, -3.0, 1.0, -1.0], [14, -2.0, -3.0, 0.0, -3.0]]], [[11, 13], [11, 14], [13, 35]]], [[[[2, -2.0, -5.0, 2.0, -3.0], [39, -5.0, -6.0, -3.0, -2.0], [27, -2.0, -6.0, -1.0, -6.0], [14, -3.0, -3.0, 1.0, -3.0]]], [[2, 14], [14, 39]]]], [[[[[27, 1.0, -4.0, 2.0, -3.0], [22, -3.0, 5.0, 0.0, 7.0], [36, 0.0, -2.0, 4.0, -1.0]]], []], [[[[25, -6.0, -6.0, -3.0, -5.0], [23, 5.0, -2.0, 7.0, -1.0], [3, 1.0, -3.0, 5.0, 1.0]]], [[3, 23]]], [[[[21, -6.0, -4.0, -3.0, -4.0], [30, 0.0, -4.0, 4.0, 0.0], [33, 4.0, 0.0, 5.0, 0.0], [7, 4.0, -4.0, 6.0, -1.0]]], [[7, 30], [30, 33]]], [[[[18, 6.0, -5.0, 9.0, -2.0], [13, 1.0, 1.0, 2.0, 3.0]]], []], [[[[16, -3.0, -5.0, -1.0, -4.0], [13, 3.0, 3.0, 7.0, 6.0], [7, -6.0, -1.0, -2.0, 3.0], [12, -4.0, 2.0, -3.0, 3.0], [24, 3.0, 3.0, 6.0, 3.0], [17, -6.0, 3.0, -4.0, 5.0]]], [[7, 12], [7, 17], [12, 17], [13, 24]]], [[[[10, 1.0, 3.0, 5.0, 4.0], [21, 5.0, 0.0, 7.0, 2.0], [27, 5.0, 1.0, 6.0, 5.0], [34, -1.0, -4.0, 2.0, -3.0]]], [[10, 27], [21, 27]]], [[[[17, 6.0, 6.0, 7.0, 10.0], [25, -3.0, 4.0, -2.0, 5.0]]], []], [[[[8, 3.0, 2.0, 4.0, 3.0], [6, 1.0, -6.0, 3.0, -5.0]]], []]], [[[[[10, -5.0, 1.0, -4.0, 2.0], [24, -6.0, -5.0, -3.0, -3.0], [32, -5.0, 2.0, -3.0, 5.0], [7, -2.0, -6.0, 2.0, -2.0], [18, -3.0, -6.0, 0.0, -3.0], [3, 5.0, 1.0, 6.0, 5.0], [19, 3.0, 1.0, 7.0, 3.0], [26, -5.0, 4.0, -2.0, 4.0], [8, -6.0, 4.0, -2.0, 8.0]]], [[3, 19], [7, 18], [8, 26], [8, 32], [10, 32], [18, 24], [26, 32]]], [[[[4, 1.0, -1.0, 5.0, -1.0], [36, -4.0, -5.0, -1.0, -5.0], [10, 3.0, 6.0, 5.0, 6.0], [11, 0.0, -1.0, 4.0, 0.0], [22, -1.0, 0.0, 1.0, 4.0], [14, 1.0, -4.0, 4.0, -2.0], [3, -1.0, 0.0, 1.0, 0.0]]], [[3, 11], [3, 22], [4, 11], [11, 22]]], [[[[24, 5.0, -5.0, 8.0, -3.0], [23, -4.0, 1.0, 0.0, 4.0], [4, -6.0, -6.0, -2.0, -6.0], [2, -4.0, 2.0, -3.0, 2.0], [7, 0.0, 3.0, 2.0, 4.0], [19, 0.0, -5.0, 4.0, -1.0]]], [[2, 23], [7, 23]]], [[[[29, -1.0, 3.0, 0.0, 7.0], [37, 0.0, -5.0, 3.0, -1.0], [28, 3.0, 3.0, 5.0, 3.0], [22, 6.0, -2.0, 9.0, 0.0], [18, -5.0, -1.0, -3.0, 0.0], [14, 3.0, 3.0, 7.0, 6.0], [3, -3.0, -1.0, -1.0, 1.0]]], [[3, 18], [14, 28]]], [[[[38, 0.0, -6.0, 2.0, -5.0], [25, -6.0, 5.0, -3.0, 6.0], [23, 2.0, 6.0, 6.0, 9.0], [34, -6.0, 2.0, -2.0, 4.0]]], []], [[[[3, 4.0, 0.0, 7.0, 4.0], [24, 4.0, -3.0, 6.0, -2.0], [33, -4.0, 4.0, -3.0, 8.0]]], []], [[[[20, 3.0, -6.0, 7.0, -4.0], [23, 6.0, 0.0, 8.0, 2.0]]], []], [[[[35, 3.0, 1.0, 7.0, 2.0], [3, 1.0, -6.0, 5.0, -6.0], [23, -4.0, -4.0, -1.0, 0.0], [22, -1.0, 0.0, 0.0, 3.0]]], [[22, 23]]]]]
for i, (args, expected) in enumerate(fixtures[N-1]):
check("case %d" % i, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| case 0 | [] | [] | Passed |
| case 1 | [[7, 22], [20, 22]] | [[7, 22], [20, 22], [28, 35]] | Failed |
| case 2 | [[9, 28], [9, 32], [28, 32]] | [[9, 28], [9, 32], [28, 32]] | Passed |
| case 3 | [[4, 29]] | [[4, 29]] | Passed |
| case 4 | [[14, 24]] | [[14, 24]] | Passed |
| case 5 | [] | [] | Passed |
| case 6 | [[11, 32], [16, 39]] | [[11, 32], [16, 39], [19, 39]] | Failed |
| case 7 | [] | [[11, 32]] | Failed |
SHA-256 / 8097961e327947ae5c254b939228322d380cf8de2e0d5c93240494d6bf57c2ca
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(boxes):
ev = []
for b in boxes:
ev.append((b[1], 0, b[0]))
ev.append((b[3], 1, b[0]))
ev.sort(key=lambda e: e[0])
byid = {b[0]: b for b in boxes}
active = []
pairs = []
for x, kind, i in ev:
if kind == 0:
bi = byid[i]
for j in active:
bj = byid[j]
if bi[2] <= bj[4] and bj[2] <= bi[4]:
pairs.append([min(i, j), max(i, j)])
active.append(i)
else:
active.remove(i)
pairs.sort()
return pairs
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[[[[[5, -5.0, -4.0, -4.0, -2.0], [37, -5.0, -1.0, -1.0, -1.0], [26, 0.0, 1.0, 3.0, 2.0]]], []], [[[[20, 4.0, -5.0, 6.0, -3.0], [38, 0.0, 4.0, 1.0, 4.0], [22, 3.0, -6.0, 5.0, -5.0], [3, -1.0, -5.0, 0.0, -4.0], [35, -6.0, 3.0, -2.0, 7.0], [7, 2.0, -6.0, 5.0, -6.0], [28, -2.0, 1.0, 2.0, 3.0]]], [[7, 22], [20, 22], [28, 35]]], [[[[28, 6.0, -4.0, 7.0, -3.0], [32, 6.0, -4.0, 9.0, -1.0], [8, 1.0, 4.0, 3.0, 7.0], [9, 3.0, -6.0, 7.0, -4.0], [37, -6.0, 3.0, -2.0, 6.0]]], [[9, 28], [9, 32], [28, 32]]], [[[[22, -2.0, 2.0, 2.0, 3.0], [29, -5.0, 1.0, -4.0, 2.0], [4, -5.0, -2.0, -2.0, 1.0]]], [[4, 29]]], [[[[14, -3.0, 4.0, 1.0, 6.0], [11, -4.0, -6.0, 0.0, -2.0], [24, -1.0, 4.0, 3.0, 6.0], [37, 2.0, -4.0, 6.0, -3.0]]], [[14, 24]]], [[[[7, -4.0, -2.0, -3.0, 2.0], [38, -1.0, -4.0, 0.0, -4.0]]], []], [[[[16, -6.0, 6.0, -5.0, 6.0], [20, 6.0, 1.0, 10.0, 4.0], [32, 4.0, -6.0, 7.0, -5.0], [11, 4.0, -6.0, 6.0, -6.0], [39, -6.0, 5.0, -2.0, 7.0], [19, -2.0, 5.0, 0.0, 6.0], [21, 1.0, -1.0, 4.0, 3.0]]], [[11, 32], [16, 39], [19, 39]]], [[[[32, 4.0, -1.0, 6.0, -1.0], [11, 6.0, -5.0, 7.0, -1.0], [28, 2.0, 1.0, 4.0, 4.0], [2, 0.0, 5.0, 1.0, 6.0], [39, 6.0, 0.0, 10.0, 2.0]]], [[11, 32]]]], [[[[[28, -6.0, 3.0, -5.0, 6.0], [21, -5.0, 1.0, -3.0, 4.0], [19, 5.0, 2.0, 9.0, 2.0]]], [[21, 28]]], [[[[12, 3.0, -2.0, 5.0, -2.0], [32, 2.0, 1.0, 4.0, 5.0]]], []], [[[[12, 6.0, -6.0, 10.0, -2.0], [21, -3.0, -5.0, 1.0, -5.0], [1, 1.0, -6.0, 4.0, -6.0], [8, -1.0, 0.0, 2.0, 4.0], [25, 2.0, -1.0, 3.0, 2.0], [35, 1.0, -1.0, 5.0, -1.0], [32, -4.0, -3.0, -1.0, -3.0]]], [[8, 25], [25, 35]]], [[[[1, 2.0, -5.0, 4.0, -4.0], [34, 6.0, -3.0, 9.0, -3.0]]], []], [[[[11, -1.0, 2.0, 3.0, 2.0], [9, 3.0, -1.0, 4.0, 0.0], [20, 5.0, -4.0, 9.0, -2.0]]], []], [[[[38, -4.0, 2.0, 0.0, 3.0], [39, -3.0, 4.0, 0.0, 4.0], [1, -5.0, 6.0, -2.0, 9.0], [6, 1.0, 4.0, 5.0, 8.0], [35, 4.0, -1.0, 5.0, 2.0]]], []], [[[[6, 6.0, -1.0, 8.0, 0.0], [35, -2.0, 2.0, -1.0, 3.0], [24, 1.0, 0.0, 4.0, 0.0]]], []], [[[[13, 4.0, -1.0, 5.0, 2.0], [8, 5.0, -4.0, 6.0, -1.0], [34, -2.0, 3.0, 0.0, 7.0], [5, 4.0, 6.0, 6.0, 9.0], [1, -4.0, 4.0, -2.0, 8.0]]], [[1, 34], [8, 13]]]], [[[[[2, 0.0, 6.0, 1.0, 7.0], [8, 2.0, 4.0, 4.0, 6.0], [10, 2.0, 2.0, 5.0, 5.0], [6, -5.0, -6.0, -1.0, -2.0], [24, -1.0, 3.0, 0.0, 3.0]]], [[8, 10]]], [[[[34, 6.0, 0.0, 9.0, 1.0], [24, -2.0, -3.0, 2.0, -3.0]]], []], [[[[38, -1.0, 2.0, 1.0, 6.0], [11, 5.0, -3.0, 8.0, -3.0], [21, 1.0, -5.0, 2.0, -4.0]]], []], [[[[3, -6.0, 0.0, -2.0, 3.0], [8, 2.0, -5.0, 5.0, -4.0], [25, -4.0, -4.0, -3.0, -3.0], [24, 5.0, -5.0, 7.0, -4.0], [28, 5.0, 3.0, 9.0, 3.0], [35, -3.0, 4.0, 0.0, 4.0]]], [[8, 24]]], [[[[7, -4.0, -6.0, -2.0, -2.0], [4, 6.0, 4.0, 9.0, 4.0], [38, 1.0, 5.0, 2.0, 8.0], [33, -5.0, -2.0, -2.0, 1.0], [5, 5.0, 4.0, 6.0, 6.0], [2, 2.0, 4.0, 4.0, 8.0], [34, 5.0, -2.0, 6.0, -1.0]]], [[2, 38], [4, 5], [7, 33]]], [[[[24, 1.0, -4.0, 4.0, -1.0], [32, -2.0, 4.0, 2.0, 6.0], [18, -5.0, -5.0, -2.0, -2.0]]], []], [[[[35, -5.0, -1.0, -4.0, 0.0], [10, 2.0, 3.0, 5.0, 5.0], [13, -4.0, -1.0, -1.0, 0.0], [11, -1.0, -3.0, 1.0, -1.0], [14, -2.0, -3.0, 0.0, -3.0]]], [[11, 13], [11, 14], [13, 35]]], [[[[2, -2.0, -5.0, 2.0, -3.0], [39, -5.0, -6.0, -3.0, -2.0], [27, -2.0, -6.0, -1.0, -6.0], [14, -3.0, -3.0, 1.0, -3.0]]], [[2, 14], [14, 39]]]], [[[[[27, 1.0, -4.0, 2.0, -3.0], [22, -3.0, 5.0, 0.0, 7.0], [36, 0.0, -2.0, 4.0, -1.0]]], []], [[[[25, -6.0, -6.0, -3.0, -5.0], [23, 5.0, -2.0, 7.0, -1.0], [3, 1.0, -3.0, 5.0, 1.0]]], [[3, 23]]], [[[[21, -6.0, -4.0, -3.0, -4.0], [30, 0.0, -4.0, 4.0, 0.0], [33, 4.0, 0.0, 5.0, 0.0], [7, 4.0, -4.0, 6.0, -1.0]]], [[7, 30], [30, 33]]], [[[[18, 6.0, -5.0, 9.0, -2.0], [13, 1.0, 1.0, 2.0, 3.0]]], []], [[[[16, -3.0, -5.0, -1.0, -4.0], [13, 3.0, 3.0, 7.0, 6.0], [7, -6.0, -1.0, -2.0, 3.0], [12, -4.0, 2.0, -3.0, 3.0], [24, 3.0, 3.0, 6.0, 3.0], [17, -6.0, 3.0, -4.0, 5.0]]], [[7, 12], [7, 17], [12, 17], [13, 24]]], [[[[10, 1.0, 3.0, 5.0, 4.0], [21, 5.0, 0.0, 7.0, 2.0], [27, 5.0, 1.0, 6.0, 5.0], [34, -1.0, -4.0, 2.0, -3.0]]], [[10, 27], [21, 27]]], [[[[17, 6.0, 6.0, 7.0, 10.0], [25, -3.0, 4.0, -2.0, 5.0]]], []], [[[[8, 3.0, 2.0, 4.0, 3.0], [6, 1.0, -6.0, 3.0, -5.0]]], []]], [[[[[10, -5.0, 1.0, -4.0, 2.0], [24, -6.0, -5.0, -3.0, -3.0], [32, -5.0, 2.0, -3.0, 5.0], [7, -2.0, -6.0, 2.0, -2.0], [18, -3.0, -6.0, 0.0, -3.0], [3, 5.0, 1.0, 6.0, 5.0], [19, 3.0, 1.0, 7.0, 3.0], [26, -5.0, 4.0, -2.0, 4.0], [8, -6.0, 4.0, -2.0, 8.0]]], [[3, 19], [7, 18], [8, 26], [8, 32], [10, 32], [18, 24], [26, 32]]], [[[[4, 1.0, -1.0, 5.0, -1.0], [36, -4.0, -5.0, -1.0, -5.0], [10, 3.0, 6.0, 5.0, 6.0], [11, 0.0, -1.0, 4.0, 0.0], [22, -1.0, 0.0, 1.0, 4.0], [14, 1.0, -4.0, 4.0, -2.0], [3, -1.0, 0.0, 1.0, 0.0]]], [[3, 11], [3, 22], [4, 11], [11, 22]]], [[[[24, 5.0, -5.0, 8.0, -3.0], [23, -4.0, 1.0, 0.0, 4.0], [4, -6.0, -6.0, -2.0, -6.0], [2, -4.0, 2.0, -3.0, 2.0], [7, 0.0, 3.0, 2.0, 4.0], [19, 0.0, -5.0, 4.0, -1.0]]], [[2, 23], [7, 23]]], [[[[29, -1.0, 3.0, 0.0, 7.0], [37, 0.0, -5.0, 3.0, -1.0], [28, 3.0, 3.0, 5.0, 3.0], [22, 6.0, -2.0, 9.0, 0.0], [18, -5.0, -1.0, -3.0, 0.0], [14, 3.0, 3.0, 7.0, 6.0], [3, -3.0, -1.0, -1.0, 1.0]]], [[3, 18], [14, 28]]], [[[[38, 0.0, -6.0, 2.0, -5.0], [25, -6.0, 5.0, -3.0, 6.0], [23, 2.0, 6.0, 6.0, 9.0], [34, -6.0, 2.0, -2.0, 4.0]]], []], [[[[3, 4.0, 0.0, 7.0, 4.0], [24, 4.0, -3.0, 6.0, -2.0], [33, -4.0, 4.0, -3.0, 8.0]]], []], [[[[20, 3.0, -6.0, 7.0, -4.0], [23, 6.0, 0.0, 8.0, 2.0]]], []], [[[[35, 3.0, 1.0, 7.0, 2.0], [3, 1.0, -6.0, 5.0, -6.0], [23, -4.0, -4.0, -1.0, 0.0], [22, -1.0, 0.0, 0.0, 3.0]]], [[22, 23]]]]]
for i, (args, expected) in enumerate(fixtures[N-1]):
check("case %d" % i, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| case 0 | [] | [] | Passed |
| case 1 | [[7, 22], [20, 22]] | [[7, 22], [20, 22], [28, 35]] | Failed |
| case 2 | [[9, 28], [9, 32], [28, 32]] | [[9, 28], [9, 32], [28, 32]] | Passed |
| case 3 | [[4, 29]] | [[4, 29]] | Passed |
| case 4 | [[14, 24]] | [[14, 24]] | Passed |
| case 5 | [] | [] | Passed |
| case 6 | [[11, 32], [16, 39]] | [[11, 32], [16, 39], [19, 39]] | Failed |
| case 7 | [] | [[11, 32]] | Failed |
SHA-256 / 86285cbc1c60348bff05404f0ad3330f347d8a68e8b4ebddbee5e55652e2ec30
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(boxes):
ev = []
for b in boxes:
ev.append((b[1], 0, b[0]))
ev.append((b[3], 1, b[0]))
ev.sort()
byid = {b[0]: b for b in boxes}
active = []
pairs = []
for x, kind, i in ev:
if kind == 0:
bi = byid[i]
for j in active:
bj = byid[j]
if bi[2] <= bj[4] and bj[2] <= bi[4]:
pairs.append([min(i, j), max(i, j)])
active.append(i)
else:
active.remove(i)
pairs.sort()
return pairs
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[[[[[5, -5.0, -4.0, -4.0, -2.0], [37, -5.0, -1.0, -1.0, -1.0], [26, 0.0, 1.0, 3.0, 2.0]]], []], [[[[20, 4.0, -5.0, 6.0, -3.0], [38, 0.0, 4.0, 1.0, 4.0], [22, 3.0, -6.0, 5.0, -5.0], [3, -1.0, -5.0, 0.0, -4.0], [35, -6.0, 3.0, -2.0, 7.0], [7, 2.0, -6.0, 5.0, -6.0], [28, -2.0, 1.0, 2.0, 3.0]]], [[7, 22], [20, 22], [28, 35]]], [[[[28, 6.0, -4.0, 7.0, -3.0], [32, 6.0, -4.0, 9.0, -1.0], [8, 1.0, 4.0, 3.0, 7.0], [9, 3.0, -6.0, 7.0, -4.0], [37, -6.0, 3.0, -2.0, 6.0]]], [[9, 28], [9, 32], [28, 32]]], [[[[22, -2.0, 2.0, 2.0, 3.0], [29, -5.0, 1.0, -4.0, 2.0], [4, -5.0, -2.0, -2.0, 1.0]]], [[4, 29]]], [[[[14, -3.0, 4.0, 1.0, 6.0], [11, -4.0, -6.0, 0.0, -2.0], [24, -1.0, 4.0, 3.0, 6.0], [37, 2.0, -4.0, 6.0, -3.0]]], [[14, 24]]], [[[[7, -4.0, -2.0, -3.0, 2.0], [38, -1.0, -4.0, 0.0, -4.0]]], []], [[[[16, -6.0, 6.0, -5.0, 6.0], [20, 6.0, 1.0, 10.0, 4.0], [32, 4.0, -6.0, 7.0, -5.0], [11, 4.0, -6.0, 6.0, -6.0], [39, -6.0, 5.0, -2.0, 7.0], [19, -2.0, 5.0, 0.0, 6.0], [21, 1.0, -1.0, 4.0, 3.0]]], [[11, 32], [16, 39], [19, 39]]], [[[[32, 4.0, -1.0, 6.0, -1.0], [11, 6.0, -5.0, 7.0, -1.0], [28, 2.0, 1.0, 4.0, 4.0], [2, 0.0, 5.0, 1.0, 6.0], [39, 6.0, 0.0, 10.0, 2.0]]], [[11, 32]]]], [[[[[28, -6.0, 3.0, -5.0, 6.0], [21, -5.0, 1.0, -3.0, 4.0], [19, 5.0, 2.0, 9.0, 2.0]]], [[21, 28]]], [[[[12, 3.0, -2.0, 5.0, -2.0], [32, 2.0, 1.0, 4.0, 5.0]]], []], [[[[12, 6.0, -6.0, 10.0, -2.0], [21, -3.0, -5.0, 1.0, -5.0], [1, 1.0, -6.0, 4.0, -6.0], [8, -1.0, 0.0, 2.0, 4.0], [25, 2.0, -1.0, 3.0, 2.0], [35, 1.0, -1.0, 5.0, -1.0], [32, -4.0, -3.0, -1.0, -3.0]]], [[8, 25], [25, 35]]], [[[[1, 2.0, -5.0, 4.0, -4.0], [34, 6.0, -3.0, 9.0, -3.0]]], []], [[[[11, -1.0, 2.0, 3.0, 2.0], [9, 3.0, -1.0, 4.0, 0.0], [20, 5.0, -4.0, 9.0, -2.0]]], []], [[[[38, -4.0, 2.0, 0.0, 3.0], [39, -3.0, 4.0, 0.0, 4.0], [1, -5.0, 6.0, -2.0, 9.0], [6, 1.0, 4.0, 5.0, 8.0], [35, 4.0, -1.0, 5.0, 2.0]]], []], [[[[6, 6.0, -1.0, 8.0, 0.0], [35, -2.0, 2.0, -1.0, 3.0], [24, 1.0, 0.0, 4.0, 0.0]]], []], [[[[13, 4.0, -1.0, 5.0, 2.0], [8, 5.0, -4.0, 6.0, -1.0], [34, -2.0, 3.0, 0.0, 7.0], [5, 4.0, 6.0, 6.0, 9.0], [1, -4.0, 4.0, -2.0, 8.0]]], [[1, 34], [8, 13]]]], [[[[[2, 0.0, 6.0, 1.0, 7.0], [8, 2.0, 4.0, 4.0, 6.0], [10, 2.0, 2.0, 5.0, 5.0], [6, -5.0, -6.0, -1.0, -2.0], [24, -1.0, 3.0, 0.0, 3.0]]], [[8, 10]]], [[[[34, 6.0, 0.0, 9.0, 1.0], [24, -2.0, -3.0, 2.0, -3.0]]], []], [[[[38, -1.0, 2.0, 1.0, 6.0], [11, 5.0, -3.0, 8.0, -3.0], [21, 1.0, -5.0, 2.0, -4.0]]], []], [[[[3, -6.0, 0.0, -2.0, 3.0], [8, 2.0, -5.0, 5.0, -4.0], [25, -4.0, -4.0, -3.0, -3.0], [24, 5.0, -5.0, 7.0, -4.0], [28, 5.0, 3.0, 9.0, 3.0], [35, -3.0, 4.0, 0.0, 4.0]]], [[8, 24]]], [[[[7, -4.0, -6.0, -2.0, -2.0], [4, 6.0, 4.0, 9.0, 4.0], [38, 1.0, 5.0, 2.0, 8.0], [33, -5.0, -2.0, -2.0, 1.0], [5, 5.0, 4.0, 6.0, 6.0], [2, 2.0, 4.0, 4.0, 8.0], [34, 5.0, -2.0, 6.0, -1.0]]], [[2, 38], [4, 5], [7, 33]]], [[[[24, 1.0, -4.0, 4.0, -1.0], [32, -2.0, 4.0, 2.0, 6.0], [18, -5.0, -5.0, -2.0, -2.0]]], []], [[[[35, -5.0, -1.0, -4.0, 0.0], [10, 2.0, 3.0, 5.0, 5.0], [13, -4.0, -1.0, -1.0, 0.0], [11, -1.0, -3.0, 1.0, -1.0], [14, -2.0, -3.0, 0.0, -3.0]]], [[11, 13], [11, 14], [13, 35]]], [[[[2, -2.0, -5.0, 2.0, -3.0], [39, -5.0, -6.0, -3.0, -2.0], [27, -2.0, -6.0, -1.0, -6.0], [14, -3.0, -3.0, 1.0, -3.0]]], [[2, 14], [14, 39]]]], [[[[[27, 1.0, -4.0, 2.0, -3.0], [22, -3.0, 5.0, 0.0, 7.0], [36, 0.0, -2.0, 4.0, -1.0]]], []], [[[[25, -6.0, -6.0, -3.0, -5.0], [23, 5.0, -2.0, 7.0, -1.0], [3, 1.0, -3.0, 5.0, 1.0]]], [[3, 23]]], [[[[21, -6.0, -4.0, -3.0, -4.0], [30, 0.0, -4.0, 4.0, 0.0], [33, 4.0, 0.0, 5.0, 0.0], [7, 4.0, -4.0, 6.0, -1.0]]], [[7, 30], [30, 33]]], [[[[18, 6.0, -5.0, 9.0, -2.0], [13, 1.0, 1.0, 2.0, 3.0]]], []], [[[[16, -3.0, -5.0, -1.0, -4.0], [13, 3.0, 3.0, 7.0, 6.0], [7, -6.0, -1.0, -2.0, 3.0], [12, -4.0, 2.0, -3.0, 3.0], [24, 3.0, 3.0, 6.0, 3.0], [17, -6.0, 3.0, -4.0, 5.0]]], [[7, 12], [7, 17], [12, 17], [13, 24]]], [[[[10, 1.0, 3.0, 5.0, 4.0], [21, 5.0, 0.0, 7.0, 2.0], [27, 5.0, 1.0, 6.0, 5.0], [34, -1.0, -4.0, 2.0, -3.0]]], [[10, 27], [21, 27]]], [[[[17, 6.0, 6.0, 7.0, 10.0], [25, -3.0, 4.0, -2.0, 5.0]]], []], [[[[8, 3.0, 2.0, 4.0, 3.0], [6, 1.0, -6.0, 3.0, -5.0]]], []]], [[[[[10, -5.0, 1.0, -4.0, 2.0], [24, -6.0, -5.0, -3.0, -3.0], [32, -5.0, 2.0, -3.0, 5.0], [7, -2.0, -6.0, 2.0, -2.0], [18, -3.0, -6.0, 0.0, -3.0], [3, 5.0, 1.0, 6.0, 5.0], [19, 3.0, 1.0, 7.0, 3.0], [26, -5.0, 4.0, -2.0, 4.0], [8, -6.0, 4.0, -2.0, 8.0]]], [[3, 19], [7, 18], [8, 26], [8, 32], [10, 32], [18, 24], [26, 32]]], [[[[4, 1.0, -1.0, 5.0, -1.0], [36, -4.0, -5.0, -1.0, -5.0], [10, 3.0, 6.0, 5.0, 6.0], [11, 0.0, -1.0, 4.0, 0.0], [22, -1.0, 0.0, 1.0, 4.0], [14, 1.0, -4.0, 4.0, -2.0], [3, -1.0, 0.0, 1.0, 0.0]]], [[3, 11], [3, 22], [4, 11], [11, 22]]], [[[[24, 5.0, -5.0, 8.0, -3.0], [23, -4.0, 1.0, 0.0, 4.0], [4, -6.0, -6.0, -2.0, -6.0], [2, -4.0, 2.0, -3.0, 2.0], [7, 0.0, 3.0, 2.0, 4.0], [19, 0.0, -5.0, 4.0, -1.0]]], [[2, 23], [7, 23]]], [[[[29, -1.0, 3.0, 0.0, 7.0], [37, 0.0, -5.0, 3.0, -1.0], [28, 3.0, 3.0, 5.0, 3.0], [22, 6.0, -2.0, 9.0, 0.0], [18, -5.0, -1.0, -3.0, 0.0], [14, 3.0, 3.0, 7.0, 6.0], [3, -3.0, -1.0, -1.0, 1.0]]], [[3, 18], [14, 28]]], [[[[38, 0.0, -6.0, 2.0, -5.0], [25, -6.0, 5.0, -3.0, 6.0], [23, 2.0, 6.0, 6.0, 9.0], [34, -6.0, 2.0, -2.0, 4.0]]], []], [[[[3, 4.0, 0.0, 7.0, 4.0], [24, 4.0, -3.0, 6.0, -2.0], [33, -4.0, 4.0, -3.0, 8.0]]], []], [[[[20, 3.0, -6.0, 7.0, -4.0], [23, 6.0, 0.0, 8.0, 2.0]]], []], [[[[35, 3.0, 1.0, 7.0, 2.0], [3, 1.0, -6.0, 5.0, -6.0], [23, -4.0, -4.0, -1.0, 0.0], [22, -1.0, 0.0, 0.0, 3.0]]], [[22, 23]]]]]
for i, (args, expected) in enumerate(fixtures[N-1]):
check("case %d" % i, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| case 0 | [] | [] | Passed |
| case 1 | [[7, 22], [20, 22], [28, 35]] | [[7, 22], [20, 22], [28, 35]] | Passed |
| case 2 | [[9, 28], [9, 32], [28, 32]] | [[9, 28], [9, 32], [28, 32]] | Passed |
| case 3 | [[4, 29]] | [[4, 29]] | Passed |
| case 4 | [[14, 24]] | [[14, 24]] | Passed |
| case 5 | [] | [] | Passed |
| case 6 | [[11, 32], [16, 39], [19, 39]] | [[11, 32], [16, 39], [19, 39]] | Passed |
| case 7 | [[11, 32]] | [[11, 32]] | Passed |
SHA-256 / fe87014eb0b8cbdab96f0b35cfae6b257d538b9f42dccbf22301a024fc08c325
Verification & scope
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.
Observations recorded using Python 3.12.14 at 2026-09-29T14:50:57.890469+00:00.
Case digest / 7c3c7dd6511461fd317ba85822d431ea743aaaa4aaebc9215eec72f2476708d1