FA-87346 / Collision detection broadphase / Open access

Secondary axis test is exclusive at the boundary · case 01

Stacked boxes resting exactly on each other lose their pair.

Verified by executionVariant 1 · 8 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

The y overlap uses strict inequalities.

VERIFIED REPAIR

Closed intervals: minA <= maxB and minB <= maxA.

Unsuccessful approach: Testing only one side of the y interval admits boxes stacked far apart.

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()
    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 = [[[[[[8, 2.0, 1.0, 3.0, 5.0], [5, -5.0, 3.0, -2.0, 5.0], [38, 2.0, -5.0, 3.0, -5.0], [3, -1.0, 3.0, -1.0, 7.0], [16, -4.0, 0.0, -1.0, 3.0]]], [[3, 16], [5, 16]]], [[[[25, -6.0, -3.0, -6.0, -3.0], [23, -1.0, 6.0, 2.0, 8.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]]], [[[[7, -4.0, -2.0, -3.0, 2.0], [38, -1.0, -4.0, 0.0, -4.0]]], []], [[[[3, -2.0, 3.0, -1.0, 7.0], [20, -2.0, 3.0, 1.0, 4.0], [31, -6.0, -2.0, -5.0, -2.0], [5, -6.0, 0.0, -5.0, 1.0], [2, -2.0, 3.0, -1.0, 3.0]]], [[2, 3], [2, 20], [3, 20]]], [[[[3, 2.0, -5.0, 2.0, -2.0], [24, -2.0, -4.0, 2.0, -4.0], [26, 6.0, 4.0, 10.0, 8.0], [4, -2.0, 2.0, -1.0, 3.0], [29, -5.0, -2.0, -2.0, 2.0], [11, 4.0, 3.0, 4.0, 6.0]]], [[3, 24], [4, 29]]], [[[[22, -6.0, 5.0, -3.0, 7.0], [30, 1.0, 3.0, 4.0, 5.0], [23, -4.0, 2.0, -2.0, 4.0], [8, 4.0, -5.0, 4.0, -1.0], [7, -2.0, -6.0, 2.0, -6.0], [32, 6.0, -3.0, 10.0, -2.0]]], []], [[[[19, 2.0, 2.0, 2.0, 2.0], [13, -6.0, -1.0, -5.0, 3.0], [5, -2.0, 6.0, 2.0, 8.0]]], []]], [[[[[1, 3.0, 1.0, 3.0, 1.0], [31, -4.0, -4.0, -4.0, -2.0], [4, 2.0, -6.0, 5.0, -3.0], [21, 4.0, 3.0, 6.0, 3.0], [17, 2.0, 5.0, 4.0, 9.0], [33, 3.0, 1.0, 4.0, 1.0], [7, -6.0, -5.0, -5.0, -2.0]]], [[1, 33]]], [[[[22, 3.0, 2.0, 3.0, 2.0], [25, 0.0, 3.0, 4.0, 3.0], [3, -6.0, -3.0, -3.0, -1.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]]], [[[[9, 6.0, -6.0, 10.0, -3.0], [5, 2.0, 2.0, 6.0, 3.0], [2, 5.0, -4.0, 6.0, -2.0], [15, 2.0, 3.0, 2.0, 7.0], [29, 4.0, 0.0, 7.0, 3.0]]], [[2, 9], [5, 15], [5, 29]]], [[[[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]]], []], [[[[1, 2.0, -5.0, 4.0, -4.0], [34, 6.0, -3.0, 9.0, -3.0]]], []], [[[[1, -2.0, 3.0, 2.0, 5.0], [3, 2.0, 0.0, 2.0, 0.0], [15, 4.0, 2.0, 7.0, 4.0], [31, 5.0, 0.0, 7.0, 3.0], [21, 6.0, -1.0, 8.0, 3.0], [7, -5.0, -4.0, -5.0, -2.0]]], [[15, 21], [15, 31], [21, 31]]], [[[[23, -6.0, -1.0, -4.0, 0.0], [5, 1.0, 1.0, 5.0, 4.0], [13, 2.0, -3.0, 4.0, -1.0], [26, 2.0, 4.0, 4.0, 7.0], [21, -2.0, 6.0, -2.0, 6.0], [8, 0.0, -4.0, 2.0, -1.0], [35, -1.0, -2.0, 0.0, -1.0]]], [[5, 26], [8, 13], [8, 35]]]], [[[[[22, -3.0, -4.0, 0.0, -4.0], [30, -3.0, 3.0, 1.0, 6.0], [37, -6.0, 5.0, -5.0, 5.0], [36, 5.0, 5.0, 8.0, 8.0], [21, -1.0, 1.0, -1.0, 2.0], [33, -4.0, -4.0, 0.0, -3.0], [2, -4.0, -1.0, -1.0, -1.0]]], [[22, 33]]], [[[[3, -4.0, -3.0, 0.0, -1.0], [12, 3.0, 5.0, 7.0, 6.0], [35, -2.0, 3.0, 2.0, 5.0], [11, 6.0, 2.0, 9.0, 2.0]]], []], [[[[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]]], [[[[3, 2.0, -1.0, 3.0, 2.0], [30, -5.0, 3.0, -4.0, 7.0], [34, 1.0, -5.0, 4.0, -3.0]]], []], [[[[29, 1.0, 3.0, 1.0, 5.0], [19, -2.0, 4.0, 2.0, 5.0], [21, -4.0, 4.0, -4.0, 6.0], [6, -6.0, -3.0, -4.0, 0.0], [11, 5.0, 2.0, 8.0, 2.0], [24, -3.0, 5.0, -3.0, 5.0], [15, -1.0, 5.0, 3.0, 9.0], [35, -5.0, 0.0, -5.0, 4.0]]], [[6, 35], [15, 19], [15, 29], [19, 29]]], [[[[36, -1.0, -5.0, 3.0, -4.0], [32, 5.0, 6.0, 8.0, 6.0], [26, 5.0, -4.0, 7.0, -4.0], [11, -1.0, 6.0, -1.0, 6.0], [20, -3.0, -5.0, -2.0, -3.0], [31, 6.0, 3.0, 6.0, 6.0], [9, 1.0, -6.0, 2.0, -4.0]]], [[9, 36], [31, 32]]], [[[[18, -6.0, -3.0, -5.0, -2.0], [29, 4.0, 1.0, 7.0, 4.0], [13, -6.0, -6.0, -2.0, -3.0], [25, 4.0, 2.0, 8.0, 6.0], [9, 2.0, -6.0, 6.0, -3.0], [2, -5.0, -6.0, -5.0, -3.0], [27, 6.0, -6.0, 6.0, -4.0]]], [[2, 13], [2, 18], [9, 27], [13, 18], [25, 29]]], [[[[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]]]], [[[[[18, -5.0, -4.0, -4.0, -1.0], [32, -1.0, -5.0, 2.0, -3.0], [22, -6.0, 2.0, -2.0, 6.0], [28, 6.0, 5.0, 7.0, 8.0], [12, -5.0, 4.0, -5.0, 7.0], [33, 5.0, 5.0, 9.0, 7.0], [39, -3.0, 3.0, -2.0, 4.0], [11, -5.0, -4.0, -4.0, 0.0]]], [[11, 18], [12, 22], [22, 39], [28, 33]]], [[[[37, -6.0, -4.0, -5.0, -3.0], [35, -1.0, 4.0, 3.0, 8.0]]], []], [[[[34, -2.0, -6.0, -1.0, -6.0], [39, 5.0, -4.0, 7.0, -3.0], [9, 1.0, -3.0, 2.0, -2.0], [38, 2.0, 5.0, 4.0, 6.0], [8, -5.0, 1.0, -3.0, 4.0], [26, -2.0, -2.0, 2.0, 0.0], [4, 5.0, -5.0, 6.0, -3.0], [35, 3.0, 1.0, 6.0, 2.0], [10, -4.0, 6.0, -2.0, 6.0], [31, 2.0, 1.0, 5.0, 3.0]]], [[4, 39], [9, 26], [31, 35]]], [[[[17, 1.0, -4.0, 5.0, -1.0], [15, -6.0, 3.0, -3.0, 6.0], [39, -6.0, 2.0, -4.0, 4.0], [13, 5.0, 0.0, 9.0, 0.0], [29, 6.0, -4.0, 10.0, 0.0], [34, -4.0, -1.0, -1.0, -1.0], [33, -2.0, -2.0, -2.0, 2.0], [16, 2.0, -4.0, 4.0, -4.0]]], [[13, 29], [15, 39], [16, 17], [33, 34]]], [[[[5, 0.0, -2.0, 3.0, -1.0], [4, -6.0, -3.0, -4.0, 1.0], [20, 6.0, -4.0, 10.0, 0.0]]], []], [[[[17, 0.0, -3.0, 0.0, -1.0], [5, 0.0, 1.0, 1.0, 2.0]]], []], [[[[35, 3.0, -6.0, 4.0, -2.0], [13, 0.0, -2.0, 1.0, 2.0], [20, -3.0, 0.0, -1.0, 4.0], [23, -3.0, 6.0, -1.0, 10.0], [33, 2.0, -3.0, 5.0, -2.0], [38, 5.0, -2.0, 8.0, 2.0], [26, -2.0, 5.0, -2.0, 6.0]]], [[23, 26], [33, 35], [33, 38]]], [[[[16, -2.0, -1.0, 2.0, 3.0], [27, -3.0, -3.0, -1.0, 0.0], [30, -2.0, -4.0, -2.0, 0.0], [7, -5.0, -4.0, -2.0, -4.0], [14, -3.0, 1.0, 0.0, 2.0], [33, 4.0, 4.0, 4.0, 8.0], [29, 5.0, 5.0, 9.0, 5.0], [21, 1.0, -3.0, 3.0, 1.0]]], [[7, 30], [14, 16], [16, 21], [16, 27], [16, 30], [27, 30]]]], [[[[[2, 6.0, -4.0, 10.0, -1.0], [30, -1.0, -4.0, 2.0, -4.0], [3, -3.0, -1.0, -1.0, -1.0], [16, 3.0, -2.0, 7.0, -2.0]]], [[2, 16]]], [[[[18, -5.0, 6.0, -5.0, 9.0], [21, 2.0, -4.0, 4.0, -1.0], [9, 3.0, 1.0, 3.0, 1.0]]], []], [[[[11, 4.0, 2.0, 8.0, 2.0], [25, 4.0, -2.0, 8.0, 2.0], [8, -1.0, 6.0, 0.0, 9.0], [37, -3.0, 4.0, -2.0, 5.0], [39, -6.0, -3.0, -4.0, 1.0], [21, -1.0, 1.0, 0.0, 2.0], [32, -1.0, 1.0, 3.0, 3.0], [12, -4.0, 3.0, 0.0, 3.0], [4, 4.0, -1.0, 7.0, 1.0]]], [[4, 25], [11, 25], [12, 32], [21, 32]]], [[[[19, 4.0, 1.0, 4.0, 2.0], [1, 2.0, -6.0, 3.0, -2.0], [35, -6.0, -4.0, -2.0, -3.0], [32, -6.0, 3.0, -3.0, 3.0], [22, -1.0, -5.0, 1.0, -1.0], [34, -1.0, 3.0, 1.0, 3.0], [24, -4.0, -5.0, -4.0, -5.0], [20, 6.0, 3.0, 8.0, 3.0], [7, -2.0, 6.0, -1.0, 6.0], [30, 3.0, -4.0, 7.0, -1.0], [15, 1.0, -5.0, 5.0, -4.0]]], [[1, 15], [1, 30], [15, 22], [15, 30]]], [[[[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]]], []], [[[[26, 2.0, 6.0, 3.0, 9.0], [3, -5.0, -1.0, -1.0, 3.0], [28, 2.0, 1.0, 4.0, 3.0], [8, -2.0, -3.0, 1.0, 1.0], [34, 3.0, 0.0, 4.0, 3.0], [27, -4.0, 1.0, 0.0, 1.0], [5, 4.0, 5.0, 5.0, 7.0], [24, -2.0, 4.0, -1.0, 7.0], [21, 5.0, -1.0, 6.0, 1.0], [2, 3.0, 0.0, 4.0, 0.0]]], [[2, 34], [3, 8], [3, 27], [8, 27], [28, 34]]], [[[[20, 3.0, -6.0, 7.0, -4.0], [23, 6.0, 0.0, 8.0, 2.0]]], []], [[[[39, -3.0, 2.0, -3.0, 5.0], [29, 1.0, 1.0, 3.0, 5.0], [12, 6.0, -1.0, 10.0, 1.0], [11, 5.0, 3.0, 9.0, 3.0], [30, -6.0, 6.0, -6.0, 6.0], [14, 1.0, -1.0, 5.0, 2.0], [21, -1.0, 4.0, -1.0, 6.0], [13, -2.0, 0.0, 0.0, 4.0]]], [[13, 21], [14, 29]]]]]
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	`[]`	`[[3, 16], [5, 16]]`	Failed
case 1	`[]`	`[]`	Passed
case 2	`[[16, 39], [19, 39]]`	`[[11, 32], [16, 39], [19, 39]]`	Failed
case 3	`[]`	`[]`	Passed
case 4	`[[3, 20]]`	`[[2, 3], [2, 20], [3, 20]]`	Failed
case 5	`[[3, 24]]`	`[[3, 24], [4, 29]]`	Failed
case 6	`[]`	`[]`	Passed
case 7	`[]`	`[]`	Passed

SHA-256 / 40c658169a673ff67cc243765f5874c6432892504dd7f99956d2760ea4bd417e

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()
    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]:
                    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 = [[[[[[8, 2.0, 1.0, 3.0, 5.0], [5, -5.0, 3.0, -2.0, 5.0], [38, 2.0, -5.0, 3.0, -5.0], [3, -1.0, 3.0, -1.0, 7.0], [16, -4.0, 0.0, -1.0, 3.0]]], [[3, 16], [5, 16]]], [[[[25, -6.0, -3.0, -6.0, -3.0], [23, -1.0, 6.0, 2.0, 8.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]]], [[[[7, -4.0, -2.0, -3.0, 2.0], [38, -1.0, -4.0, 0.0, -4.0]]], []], [[[[3, -2.0, 3.0, -1.0, 7.0], [20, -2.0, 3.0, 1.0, 4.0], [31, -6.0, -2.0, -5.0, -2.0], [5, -6.0, 0.0, -5.0, 1.0], [2, -2.0, 3.0, -1.0, 3.0]]], [[2, 3], [2, 20], [3, 20]]], [[[[3, 2.0, -5.0, 2.0, -2.0], [24, -2.0, -4.0, 2.0, -4.0], [26, 6.0, 4.0, 10.0, 8.0], [4, -2.0, 2.0, -1.0, 3.0], [29, -5.0, -2.0, -2.0, 2.0], [11, 4.0, 3.0, 4.0, 6.0]]], [[3, 24], [4, 29]]], [[[[22, -6.0, 5.0, -3.0, 7.0], [30, 1.0, 3.0, 4.0, 5.0], [23, -4.0, 2.0, -2.0, 4.0], [8, 4.0, -5.0, 4.0, -1.0], [7, -2.0, -6.0, 2.0, -6.0], [32, 6.0, -3.0, 10.0, -2.0]]], []], [[[[19, 2.0, 2.0, 2.0, 2.0], [13, -6.0, -1.0, -5.0, 3.0], [5, -2.0, 6.0, 2.0, 8.0]]], []]], [[[[[1, 3.0, 1.0, 3.0, 1.0], [31, -4.0, -4.0, -4.0, -2.0], [4, 2.0, -6.0, 5.0, -3.0], [21, 4.0, 3.0, 6.0, 3.0], [17, 2.0, 5.0, 4.0, 9.0], [33, 3.0, 1.0, 4.0, 1.0], [7, -6.0, -5.0, -5.0, -2.0]]], [[1, 33]]], [[[[22, 3.0, 2.0, 3.0, 2.0], [25, 0.0, 3.0, 4.0, 3.0], [3, -6.0, -3.0, -3.0, -1.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]]], [[[[9, 6.0, -6.0, 10.0, -3.0], [5, 2.0, 2.0, 6.0, 3.0], [2, 5.0, -4.0, 6.0, -2.0], [15, 2.0, 3.0, 2.0, 7.0], [29, 4.0, 0.0, 7.0, 3.0]]], [[2, 9], [5, 15], [5, 29]]], [[[[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]]], []], [[[[1, 2.0, -5.0, 4.0, -4.0], [34, 6.0, -3.0, 9.0, -3.0]]], []], [[[[1, -2.0, 3.0, 2.0, 5.0], [3, 2.0, 0.0, 2.0, 0.0], [15, 4.0, 2.0, 7.0, 4.0], [31, 5.0, 0.0, 7.0, 3.0], [21, 6.0, -1.0, 8.0, 3.0], [7, -5.0, -4.0, -5.0, -2.0]]], [[15, 21], [15, 31], [21, 31]]], [[[[23, -6.0, -1.0, -4.0, 0.0], [5, 1.0, 1.0, 5.0, 4.0], [13, 2.0, -3.0, 4.0, -1.0], [26, 2.0, 4.0, 4.0, 7.0], [21, -2.0, 6.0, -2.0, 6.0], [8, 0.0, -4.0, 2.0, -1.0], [35, -1.0, -2.0, 0.0, -1.0]]], [[5, 26], [8, 13], [8, 35]]]], [[[[[22, -3.0, -4.0, 0.0, -4.0], [30, -3.0, 3.0, 1.0, 6.0], [37, -6.0, 5.0, -5.0, 5.0], [36, 5.0, 5.0, 8.0, 8.0], [21, -1.0, 1.0, -1.0, 2.0], [33, -4.0, -4.0, 0.0, -3.0], [2, -4.0, -1.0, -1.0, -1.0]]], [[22, 33]]], [[[[3, -4.0, -3.0, 0.0, -1.0], [12, 3.0, 5.0, 7.0, 6.0], [35, -2.0, 3.0, 2.0, 5.0], [11, 6.0, 2.0, 9.0, 2.0]]], []], [[[[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]]], [[[[3, 2.0, -1.0, 3.0, 2.0], [30, -5.0, 3.0, -4.0, 7.0], [34, 1.0, -5.0, 4.0, -3.0]]], []], [[[[29, 1.0, 3.0, 1.0, 5.0], [19, -2.0, 4.0, 2.0, 5.0], [21, -4.0, 4.0, -4.0, 6.0], [6, -6.0, -3.0, -4.0, 0.0], [11, 5.0, 2.0, 8.0, 2.0], [24, -3.0, 5.0, -3.0, 5.0], [15, -1.0, 5.0, 3.0, 9.0], [35, -5.0, 0.0, -5.0, 4.0]]], [[6, 35], [15, 19], [15, 29], [19, 29]]], [[[[36, -1.0, -5.0, 3.0, -4.0], [32, 5.0, 6.0, 8.0, 6.0], [26, 5.0, -4.0, 7.0, -4.0], [11, -1.0, 6.0, -1.0, 6.0], [20, -3.0, -5.0, -2.0, -3.0], [31, 6.0, 3.0, 6.0, 6.0], [9, 1.0, -6.0, 2.0, -4.0]]], [[9, 36], [31, 32]]], [[[[18, -6.0, -3.0, -5.0, -2.0], [29, 4.0, 1.0, 7.0, 4.0], [13, -6.0, -6.0, -2.0, -3.0], [25, 4.0, 2.0, 8.0, 6.0], [9, 2.0, -6.0, 6.0, -3.0], [2, -5.0, -6.0, -5.0, -3.0], [27, 6.0, -6.0, 6.0, -4.0]]], [[2, 13], [2, 18], [9, 27], [13, 18], [25, 29]]], [[[[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]]]], [[[[[18, -5.0, -4.0, -4.0, -1.0], [32, -1.0, -5.0, 2.0, -3.0], [22, -6.0, 2.0, -2.0, 6.0], [28, 6.0, 5.0, 7.0, 8.0], [12, -5.0, 4.0, -5.0, 7.0], [33, 5.0, 5.0, 9.0, 7.0], [39, -3.0, 3.0, -2.0, 4.0], [11, -5.0, -4.0, -4.0, 0.0]]], [[11, 18], [12, 22], [22, 39], [28, 33]]], [[[[37, -6.0, -4.0, -5.0, -3.0], [35, -1.0, 4.0, 3.0, 8.0]]], []], [[[[34, -2.0, -6.0, -1.0, -6.0], [39, 5.0, -4.0, 7.0, -3.0], [9, 1.0, -3.0, 2.0, -2.0], [38, 2.0, 5.0, 4.0, 6.0], [8, -5.0, 1.0, -3.0, 4.0], [26, -2.0, -2.0, 2.0, 0.0], [4, 5.0, -5.0, 6.0, -3.0], [35, 3.0, 1.0, 6.0, 2.0], [10, -4.0, 6.0, -2.0, 6.0], [31, 2.0, 1.0, 5.0, 3.0]]], [[4, 39], [9, 26], [31, 35]]], [[[[17, 1.0, -4.0, 5.0, -1.0], [15, -6.0, 3.0, -3.0, 6.0], [39, -6.0, 2.0, -4.0, 4.0], [13, 5.0, 0.0, 9.0, 0.0], [29, 6.0, -4.0, 10.0, 0.0], [34, -4.0, -1.0, -1.0, -1.0], [33, -2.0, -2.0, -2.0, 2.0], [16, 2.0, -4.0, 4.0, -4.0]]], [[13, 29], [15, 39], [16, 17], [33, 34]]], [[[[5, 0.0, -2.0, 3.0, -1.0], [4, -6.0, -3.0, -4.0, 1.0], [20, 6.0, -4.0, 10.0, 0.0]]], []], [[[[17, 0.0, -3.0, 0.0, -1.0], [5, 0.0, 1.0, 1.0, 2.0]]], []], [[[[35, 3.0, -6.0, 4.0, -2.0], [13, 0.0, -2.0, 1.0, 2.0], [20, -3.0, 0.0, -1.0, 4.0], [23, -3.0, 6.0, -1.0, 10.0], [33, 2.0, -3.0, 5.0, -2.0], [38, 5.0, -2.0, 8.0, 2.0], [26, -2.0, 5.0, -2.0, 6.0]]], [[23, 26], [33, 35], [33, 38]]], [[[[16, -2.0, -1.0, 2.0, 3.0], [27, -3.0, -3.0, -1.0, 0.0], [30, -2.0, -4.0, -2.0, 0.0], [7, -5.0, -4.0, -2.0, -4.0], [14, -3.0, 1.0, 0.0, 2.0], [33, 4.0, 4.0, 4.0, 8.0], [29, 5.0, 5.0, 9.0, 5.0], [21, 1.0, -3.0, 3.0, 1.0]]], [[7, 30], [14, 16], [16, 21], [16, 27], [16, 30], [27, 30]]]], [[[[[2, 6.0, -4.0, 10.0, -1.0], [30, -1.0, -4.0, 2.0, -4.0], [3, -3.0, -1.0, -1.0, -1.0], [16, 3.0, -2.0, 7.0, -2.0]]], [[2, 16]]], [[[[18, -5.0, 6.0, -5.0, 9.0], [21, 2.0, -4.0, 4.0, -1.0], [9, 3.0, 1.0, 3.0, 1.0]]], []], [[[[11, 4.0, 2.0, 8.0, 2.0], [25, 4.0, -2.0, 8.0, 2.0], [8, -1.0, 6.0, 0.0, 9.0], [37, -3.0, 4.0, -2.0, 5.0], [39, -6.0, -3.0, -4.0, 1.0], [21, -1.0, 1.0, 0.0, 2.0], [32, -1.0, 1.0, 3.0, 3.0], [12, -4.0, 3.0, 0.0, 3.0], [4, 4.0, -1.0, 7.0, 1.0]]], [[4, 25], [11, 25], [12, 32], [21, 32]]], [[[[19, 4.0, 1.0, 4.0, 2.0], [1, 2.0, -6.0, 3.0, -2.0], [35, -6.0, -4.0, -2.0, -3.0], [32, -6.0, 3.0, -3.0, 3.0], [22, -1.0, -5.0, 1.0, -1.0], [34, -1.0, 3.0, 1.0, 3.0], [24, -4.0, -5.0, -4.0, -5.0], [20, 6.0, 3.0, 8.0, 3.0], [7, -2.0, 6.0, -1.0, 6.0], [30, 3.0, -4.0, 7.0, -1.0], [15, 1.0, -5.0, 5.0, -4.0]]], [[1, 15], [1, 30], [15, 22], [15, 30]]], [[[[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]]], []], [[[[26, 2.0, 6.0, 3.0, 9.0], [3, -5.0, -1.0, -1.0, 3.0], [28, 2.0, 1.0, 4.0, 3.0], [8, -2.0, -3.0, 1.0, 1.0], [34, 3.0, 0.0, 4.0, 3.0], [27, -4.0, 1.0, 0.0, 1.0], [5, 4.0, 5.0, 5.0, 7.0], [24, -2.0, 4.0, -1.0, 7.0], [21, 5.0, -1.0, 6.0, 1.0], [2, 3.0, 0.0, 4.0, 0.0]]], [[2, 34], [3, 8], [3, 27], [8, 27], [28, 34]]], [[[[20, 3.0, -6.0, 7.0, -4.0], [23, 6.0, 0.0, 8.0, 2.0]]], []], [[[[39, -3.0, 2.0, -3.0, 5.0], [29, 1.0, 1.0, 3.0, 5.0], [12, 6.0, -1.0, 10.0, 1.0], [11, 5.0, 3.0, 9.0, 3.0], [30, -6.0, 6.0, -6.0, 6.0], [14, 1.0, -1.0, 5.0, 2.0], [21, -1.0, 4.0, -1.0, 6.0], [13, -2.0, 0.0, 0.0, 4.0]]], [[13, 21], [14, 29]]]]]
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	`[[3, 16], [5, 16], [8, 38]]`	`[[3, 16], [5, 16]]`	Failed
case 1	`[]`	`[]`	Passed
case 2	`[[11, 21], [11, 32], [16, 39], [19, 39], [21, 32]]`	`[[11, 32], [16, 39], [19, 39]]`	Failed
case 3	`[]`	`[]`	Passed
case 4	`[[2, 3], [2, 20], [3, 20], [5, 31]]`	`[[2, 3], [2, 20], [3, 20]]`	Failed
case 5	`[[3, 24], [4, 24], [4, 29], [24, 29]]`	`[[3, 24], [4, 29]]`	Failed
case 6	`[[7, 23], [8, 30], [22, 23]]`	`[]`	Failed
case 7	`[[5, 19]]`	`[]`	Failed

SHA-256 / 4bf143255e04fbca783177a7a0779eb1de931383c0d7aa3ee6e7385de2a388b9

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 = [[[[[[8, 2.0, 1.0, 3.0, 5.0], [5, -5.0, 3.0, -2.0, 5.0], [38, 2.0, -5.0, 3.0, -5.0], [3, -1.0, 3.0, -1.0, 7.0], [16, -4.0, 0.0, -1.0, 3.0]]], [[3, 16], [5, 16]]], [[[[25, -6.0, -3.0, -6.0, -3.0], [23, -1.0, 6.0, 2.0, 8.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]]], [[[[7, -4.0, -2.0, -3.0, 2.0], [38, -1.0, -4.0, 0.0, -4.0]]], []], [[[[3, -2.0, 3.0, -1.0, 7.0], [20, -2.0, 3.0, 1.0, 4.0], [31, -6.0, -2.0, -5.0, -2.0], [5, -6.0, 0.0, -5.0, 1.0], [2, -2.0, 3.0, -1.0, 3.0]]], [[2, 3], [2, 20], [3, 20]]], [[[[3, 2.0, -5.0, 2.0, -2.0], [24, -2.0, -4.0, 2.0, -4.0], [26, 6.0, 4.0, 10.0, 8.0], [4, -2.0, 2.0, -1.0, 3.0], [29, -5.0, -2.0, -2.0, 2.0], [11, 4.0, 3.0, 4.0, 6.0]]], [[3, 24], [4, 29]]], [[[[22, -6.0, 5.0, -3.0, 7.0], [30, 1.0, 3.0, 4.0, 5.0], [23, -4.0, 2.0, -2.0, 4.0], [8, 4.0, -5.0, 4.0, -1.0], [7, -2.0, -6.0, 2.0, -6.0], [32, 6.0, -3.0, 10.0, -2.0]]], []], [[[[19, 2.0, 2.0, 2.0, 2.0], [13, -6.0, -1.0, -5.0, 3.0], [5, -2.0, 6.0, 2.0, 8.0]]], []]], [[[[[1, 3.0, 1.0, 3.0, 1.0], [31, -4.0, -4.0, -4.0, -2.0], [4, 2.0, -6.0, 5.0, -3.0], [21, 4.0, 3.0, 6.0, 3.0], [17, 2.0, 5.0, 4.0, 9.0], [33, 3.0, 1.0, 4.0, 1.0], [7, -6.0, -5.0, -5.0, -2.0]]], [[1, 33]]], [[[[22, 3.0, 2.0, 3.0, 2.0], [25, 0.0, 3.0, 4.0, 3.0], [3, -6.0, -3.0, -3.0, -1.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]]], [[[[9, 6.0, -6.0, 10.0, -3.0], [5, 2.0, 2.0, 6.0, 3.0], [2, 5.0, -4.0, 6.0, -2.0], [15, 2.0, 3.0, 2.0, 7.0], [29, 4.0, 0.0, 7.0, 3.0]]], [[2, 9], [5, 15], [5, 29]]], [[[[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]]], []], [[[[1, 2.0, -5.0, 4.0, -4.0], [34, 6.0, -3.0, 9.0, -3.0]]], []], [[[[1, -2.0, 3.0, 2.0, 5.0], [3, 2.0, 0.0, 2.0, 0.0], [15, 4.0, 2.0, 7.0, 4.0], [31, 5.0, 0.0, 7.0, 3.0], [21, 6.0, -1.0, 8.0, 3.0], [7, -5.0, -4.0, -5.0, -2.0]]], [[15, 21], [15, 31], [21, 31]]], [[[[23, -6.0, -1.0, -4.0, 0.0], [5, 1.0, 1.0, 5.0, 4.0], [13, 2.0, -3.0, 4.0, -1.0], [26, 2.0, 4.0, 4.0, 7.0], [21, -2.0, 6.0, -2.0, 6.0], [8, 0.0, -4.0, 2.0, -1.0], [35, -1.0, -2.0, 0.0, -1.0]]], [[5, 26], [8, 13], [8, 35]]]], [[[[[22, -3.0, -4.0, 0.0, -4.0], [30, -3.0, 3.0, 1.0, 6.0], [37, -6.0, 5.0, -5.0, 5.0], [36, 5.0, 5.0, 8.0, 8.0], [21, -1.0, 1.0, -1.0, 2.0], [33, -4.0, -4.0, 0.0, -3.0], [2, -4.0, -1.0, -1.0, -1.0]]], [[22, 33]]], [[[[3, -4.0, -3.0, 0.0, -1.0], [12, 3.0, 5.0, 7.0, 6.0], [35, -2.0, 3.0, 2.0, 5.0], [11, 6.0, 2.0, 9.0, 2.0]]], []], [[[[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]]], [[[[3, 2.0, -1.0, 3.0, 2.0], [30, -5.0, 3.0, -4.0, 7.0], [34, 1.0, -5.0, 4.0, -3.0]]], []], [[[[29, 1.0, 3.0, 1.0, 5.0], [19, -2.0, 4.0, 2.0, 5.0], [21, -4.0, 4.0, -4.0, 6.0], [6, -6.0, -3.0, -4.0, 0.0], [11, 5.0, 2.0, 8.0, 2.0], [24, -3.0, 5.0, -3.0, 5.0], [15, -1.0, 5.0, 3.0, 9.0], [35, -5.0, 0.0, -5.0, 4.0]]], [[6, 35], [15, 19], [15, 29], [19, 29]]], [[[[36, -1.0, -5.0, 3.0, -4.0], [32, 5.0, 6.0, 8.0, 6.0], [26, 5.0, -4.0, 7.0, -4.0], [11, -1.0, 6.0, -1.0, 6.0], [20, -3.0, -5.0, -2.0, -3.0], [31, 6.0, 3.0, 6.0, 6.0], [9, 1.0, -6.0, 2.0, -4.0]]], [[9, 36], [31, 32]]], [[[[18, -6.0, -3.0, -5.0, -2.0], [29, 4.0, 1.0, 7.0, 4.0], [13, -6.0, -6.0, -2.0, -3.0], [25, 4.0, 2.0, 8.0, 6.0], [9, 2.0, -6.0, 6.0, -3.0], [2, -5.0, -6.0, -5.0, -3.0], [27, 6.0, -6.0, 6.0, -4.0]]], [[2, 13], [2, 18], [9, 27], [13, 18], [25, 29]]], [[[[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]]]], [[[[[18, -5.0, -4.0, -4.0, -1.0], [32, -1.0, -5.0, 2.0, -3.0], [22, -6.0, 2.0, -2.0, 6.0], [28, 6.0, 5.0, 7.0, 8.0], [12, -5.0, 4.0, -5.0, 7.0], [33, 5.0, 5.0, 9.0, 7.0], [39, -3.0, 3.0, -2.0, 4.0], [11, -5.0, -4.0, -4.0, 0.0]]], [[11, 18], [12, 22], [22, 39], [28, 33]]], [[[[37, -6.0, -4.0, -5.0, -3.0], [35, -1.0, 4.0, 3.0, 8.0]]], []], [[[[34, -2.0, -6.0, -1.0, -6.0], [39, 5.0, -4.0, 7.0, -3.0], [9, 1.0, -3.0, 2.0, -2.0], [38, 2.0, 5.0, 4.0, 6.0], [8, -5.0, 1.0, -3.0, 4.0], [26, -2.0, -2.0, 2.0, 0.0], [4, 5.0, -5.0, 6.0, -3.0], [35, 3.0, 1.0, 6.0, 2.0], [10, -4.0, 6.0, -2.0, 6.0], [31, 2.0, 1.0, 5.0, 3.0]]], [[4, 39], [9, 26], [31, 35]]], [[[[17, 1.0, -4.0, 5.0, -1.0], [15, -6.0, 3.0, -3.0, 6.0], [39, -6.0, 2.0, -4.0, 4.0], [13, 5.0, 0.0, 9.0, 0.0], [29, 6.0, -4.0, 10.0, 0.0], [34, -4.0, -1.0, -1.0, -1.0], [33, -2.0, -2.0, -2.0, 2.0], [16, 2.0, -4.0, 4.0, -4.0]]], [[13, 29], [15, 39], [16, 17], [33, 34]]], [[[[5, 0.0, -2.0, 3.0, -1.0], [4, -6.0, -3.0, -4.0, 1.0], [20, 6.0, -4.0, 10.0, 0.0]]], []], [[[[17, 0.0, -3.0, 0.0, -1.0], [5, 0.0, 1.0, 1.0, 2.0]]], []], [[[[35, 3.0, -6.0, 4.0, -2.0], [13, 0.0, -2.0, 1.0, 2.0], [20, -3.0, 0.0, -1.0, 4.0], [23, -3.0, 6.0, -1.0, 10.0], [33, 2.0, -3.0, 5.0, -2.0], [38, 5.0, -2.0, 8.0, 2.0], [26, -2.0, 5.0, -2.0, 6.0]]], [[23, 26], [33, 35], [33, 38]]], [[[[16, -2.0, -1.0, 2.0, 3.0], [27, -3.0, -3.0, -1.0, 0.0], [30, -2.0, -4.0, -2.0, 0.0], [7, -5.0, -4.0, -2.0, -4.0], [14, -3.0, 1.0, 0.0, 2.0], [33, 4.0, 4.0, 4.0, 8.0], [29, 5.0, 5.0, 9.0, 5.0], [21, 1.0, -3.0, 3.0, 1.0]]], [[7, 30], [14, 16], [16, 21], [16, 27], [16, 30], [27, 30]]]], [[[[[2, 6.0, -4.0, 10.0, -1.0], [30, -1.0, -4.0, 2.0, -4.0], [3, -3.0, -1.0, -1.0, -1.0], [16, 3.0, -2.0, 7.0, -2.0]]], [[2, 16]]], [[[[18, -5.0, 6.0, -5.0, 9.0], [21, 2.0, -4.0, 4.0, -1.0], [9, 3.0, 1.0, 3.0, 1.0]]], []], [[[[11, 4.0, 2.0, 8.0, 2.0], [25, 4.0, -2.0, 8.0, 2.0], [8, -1.0, 6.0, 0.0, 9.0], [37, -3.0, 4.0, -2.0, 5.0], [39, -6.0, -3.0, -4.0, 1.0], [21, -1.0, 1.0, 0.0, 2.0], [32, -1.0, 1.0, 3.0, 3.0], [12, -4.0, 3.0, 0.0, 3.0], [4, 4.0, -1.0, 7.0, 1.0]]], [[4, 25], [11, 25], [12, 32], [21, 32]]], [[[[19, 4.0, 1.0, 4.0, 2.0], [1, 2.0, -6.0, 3.0, -2.0], [35, -6.0, -4.0, -2.0, -3.0], [32, -6.0, 3.0, -3.0, 3.0], [22, -1.0, -5.0, 1.0, -1.0], [34, -1.0, 3.0, 1.0, 3.0], [24, -4.0, -5.0, -4.0, -5.0], [20, 6.0, 3.0, 8.0, 3.0], [7, -2.0, 6.0, -1.0, 6.0], [30, 3.0, -4.0, 7.0, -1.0], [15, 1.0, -5.0, 5.0, -4.0]]], [[1, 15], [1, 30], [15, 22], [15, 30]]], [[[[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]]], []], [[[[26, 2.0, 6.0, 3.0, 9.0], [3, -5.0, -1.0, -1.0, 3.0], [28, 2.0, 1.0, 4.0, 3.0], [8, -2.0, -3.0, 1.0, 1.0], [34, 3.0, 0.0, 4.0, 3.0], [27, -4.0, 1.0, 0.0, 1.0], [5, 4.0, 5.0, 5.0, 7.0], [24, -2.0, 4.0, -1.0, 7.0], [21, 5.0, -1.0, 6.0, 1.0], [2, 3.0, 0.0, 4.0, 0.0]]], [[2, 34], [3, 8], [3, 27], [8, 27], [28, 34]]], [[[[20, 3.0, -6.0, 7.0, -4.0], [23, 6.0, 0.0, 8.0, 2.0]]], []], [[[[39, -3.0, 2.0, -3.0, 5.0], [29, 1.0, 1.0, 3.0, 5.0], [12, 6.0, -1.0, 10.0, 1.0], [11, 5.0, 3.0, 9.0, 3.0], [30, -6.0, 6.0, -6.0, 6.0], [14, 1.0, -1.0, 5.0, 2.0], [21, -1.0, 4.0, -1.0, 6.0], [13, -2.0, 0.0, 0.0, 4.0]]], [[13, 21], [14, 29]]]]]
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	`[[3, 16], [5, 16]]`	`[[3, 16], [5, 16]]`	Passed
case 1	`[]`	`[]`	Passed
case 2	`[[11, 32], [16, 39], [19, 39]]`	`[[11, 32], [16, 39], [19, 39]]`	Passed
case 3	`[]`	`[]`	Passed
case 4	`[[2, 3], [2, 20], [3, 20]]`	`[[2, 3], [2, 20], [3, 20]]`	Passed
case 5	`[[3, 24], [4, 29]]`	`[[3, 24], [4, 29]]`	Passed
case 6	`[]`	`[]`	Passed
case 7	`[]`	`[]`	Passed

SHA-256 / 2825a65712ec249b51673abb9cfbeb8a78fab922a04c3c176c8a240ef4ff6e8b

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.963831+00:00.

Case digest / 5b0dfe81e3245fa1763c633abd2edf0a2e7ca9f4a068d11c74ce33961d645071