FA-87366 / Collision detection broadphase / Open access

Grid cell index truncates toward zero for negative coordinates · case 01

Boxes straddling the origin share cell 0 with boxes one cell away.

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

ROOT CAUSE

int() is used for cell indices, so -0.5 maps to cell 0.

VERIFIED REPAIR

Use floor division semantics for negative coordinates.

Unsuccessful approach: Flooring only the minimum corner still truncates the maximum corner.

Case 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].

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, cs):
    grid = {}
    inserts = 0
    for b in boxes:
        i0, i1 = int(b[1] / cs), int(b[3] / cs)
        j0, j1 = math.floor(b[2] / cs), math.floor(b[4] / cs)
        for i in range(i0, i1 + 1):
            for j in range(j0, j1 + 1):
                grid.setdefault((i, j), []).append(b[0])
                inserts += 1
    pairs = set()
    for cell in grid.values():
        for p in range(len(cell)):
            for q in range(p + 1, len(cell)):
                a, c = cell[p], cell[q]
                pairs.add((min(a, c), max(a, c)))
    return [sorted([list(p) for p in pairs]), inserts, max((len(v) for v in grid.values()), default=0)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[[[[[28, 1.0, -1.0, 5.0, 1.0], [39, 5.0, -4.0, 6.0, -4.0], [25, 6.0, -3.0, 6.0, -3.0], [24, 3.0, 1.0, 7.0, 5.0], [22, -4.0, -3.0, 0.0, -2.0]], 2.5], [[[22, 28], [24, 28], [25, 39]], 20, 2]], [[[[39, -3.0, 0.0, -2.0, 3.0], [1, 2.0, -5.0, 6.0, -4.0]], 3.0], [[], 5, 1]], [[[[37, -6.0, 1.0, -3.0, 2.0], [20, -4.0, 5.0, 1.0, 7.0]], 2.0], [[], 10, 1]], [[[[12, -6.0, -5.0, -6.0, -2.0], [6, 1.0, 2.0, 1.0, 4.0], [28, -1.0, 6.0, 3.0, 9.0]], 3.0], [[], 10, 1]], [[[[12, 0.5, -0.5, 1.0, -0.5], [39, 0.0, -2.5, 0.0, -2.5], [3, -3.0, -1.5, -2.5, 1.0], [20, -1.0, 2.5, -0.5, 3.5], [7, -2.5, -0.5, -0.5, -0.5], [10, 1.5, 1.0, 3.5, 3.0]], 1.0], [[[3, 7]], 21, 2]], [[[[14, -2.5, 0.5, -2.5, 3.0], [38, 0.0, 2.0, 1.0, 3.0]], 1.0], [[], 8, 1]], [[[[13, 4.0, 1.0, 4.0, 3.0], [10, 3.0, 0.0, 3.0, 5.0], [3, 2.0, 1.0, 3.0, 4.0], [7, 5.0, 1.0, 8.0, 5.0]], 2.0], [[[3, 10], [7, 13]], 17, 2]], [[[[27, 3.0, 5.0, 6.0, 8.0], [8, 6.0, 2.0, 11.0, 6.0], [10, 5.0, -2.0, 8.0, 2.0], [11, -6.0, 3.0, -2.0, 6.0], [6, 5.0, 5.0, 6.0, 7.0]], 1.0], [[[6, 8], [6, 27], [8, 10], [8, 27]], 92, 3]]], [[[[[35, -6.0, -2.0, -2.0, 1.0], [23, 0.0, -1.0, 0.0, 3.0], [36, 3.0, -6.0, 3.0, -6.0], [34, 3.0, 0.0, 5.0, 1.0]], 3.0], [[], 9, 1]], [[[[29, 4.0, -5.0, 5.0, -1.0], [33, -3.0, 1.0, -1.0, 4.0], [3, -3.0, -1.0, -1.0, 3.0], [37, -6.0, 6.0, -1.0, 11.0], [27, 4.0, 0.0, 7.0, 5.0]], 2.0], [[[3, 33]], 30, 2]], [[[[1, -4.0, -2.0, -4.0, 3.0], [10, 1.0, 1.0, 5.0, 5.0], [19, -4.0, -6.0, 0.0, -1.0]], 1.0], [[[1, 19]], 61, 2]], [[[[29, 4.0, 5.0, 8.0, 10.0], [16, -1.0, -3.0, 4.0, -1.0]], 2.5], [[], 15, 1]], [[[[2, -3.0, -0.5, -2.5, 2.0], [10, 1.0, -3.0, 2.0, -3.0], [36, 0.0, 0.5, 2.0, 0.5]], 2.0], [[], 7, 1]], [[[[9, -2.0, -2.0, -1.0, -1.5], [20, 0.0, 1.0, 0.0, 1.0], [1, 2.0, 1.5, 3.5, 1.5], [33, -1.0, -3.0, 0.0, -1.5], [11, -0.5, 0.0, -0.5, 1.0], [39, 1.5, -1.0, 2.5, 1.0]], 1.0], [[[1, 39], [9, 33]], 17, 2]], [[[[32, -3.0, 3.0, 1.0, 5.0], [16, 5.0, 2.0, 7.0, 2.0], [6, 6.0, 1.0, 10.0, 4.0], [26, 2.0, 0.0, 6.0, 3.0], [5, 3.0, -3.0, 4.0, 2.0]], 1.0], [[[5, 26], [6, 16], [6, 26], [16, 26]], 70, 3]], [[[[8, 3.0, 1.0, 5.0, 3.0], [17, 0.0, 4.0, 1.0, 6.0], [23, -5.0, -3.0, -1.0, -1.0], [20, -3.0, -6.0, 1.0, -1.0], [33, 6.0, 5.0, 8.0, 9.0]], 3.0], [[[20, 23]], 13, 2]]], [[[[[13, 5.0, -1.0, 7.0, 4.0], [17, 4.0, -6.0, 8.0, -3.0]], 1.0], [[], 38, 1]], [[[[5, 1.0, -1.0, 3.0, 1.0], [4, 3.0, 2.5, 3.5, 3.5], [2, 1.5, -0.5, 1.5, 2.0]], 2.5], [[[2, 5]], 7, 2]], [[[[13, -0.5, 1.0, 0.0, 2.0], [22, -1.0, -1.5, -0.5, -0.5], [32, 3.0, -2.0, 3.0, -0.5]], 2.0], [[], 6, 1]], [[[[8, 3.0, 3.0, 5.0, 5.5], [27, -2.0, 1.5, -2.0, 3.0], [5, 0.0, 2.5, 1.5, 3.5], [2, -1.0, -1.0, -1.0, 1.0], [37, 3.0, 3.0, 4.5, 4.0], [4, 1.0, 0.5, 3.0, 2.5], [13, 2.0, 3.0, 2.0, 5.0]], 3.0], [[[2, 27], [4, 5], [5, 13], [8, 37]], 11, 2]], [[[[11, -2.5, 1.5, 0.0, 2.0], [39, -2.5, 0.5, -1.0, 2.0], [34, -3.0, -2.0, -1.5, -1.0], [31, -0.5, -1.5, 2.0, -1.0], [23, 0.5, -1.0, 2.0, -0.5], [27, 1.5, 2.0, 1.5, 2.0]], 2.5], [[[11, 27], [11, 39], [23, 31], [31, 34]], 9, 2]], [[[[18, -0.5, -3.0, 1.5, -1.0], [16, 2.5, -3.0, 4.0, -1.5]], 2.5], [[], 6, 1]], [[[[33, -3.0, -3.0, -1.0, -1.0], [24, -3.0, -1.0, -3.0, 0.5], [19, 1.5, -1.0, 2.5, -0.5], [13, 1.5, -1.5, 3.5, 0.0]], 1.0], [[[13, 19], [24, 33]], 22, 2]], [[[[13, 1.0, 4.0, 4.0, 8.0], [39, 4.0, -4.0, 6.0, 1.0], [11, 0.0, 6.0, 0.0, 8.0], [15, -3.0, -3.0, 0.0, -1.0], [30, 2.0, -1.0, 2.0, 1.0], [31, -1.0, 0.0, -1.0, 5.0], [37, 6.0, 5.0, 6.0, 10.0], [7, 6.0, 3.0, 6.0, 8.0]], 3.0], [[[7, 37], [11, 13], [15, 30]], 22, 2]]], [[[[[19, 3.0, -5.0, 4.0, -3.0], [29, 6.0, -4.0, 7.0, -4.0], [33, 6.0, -5.0, 6.0, -2.0], [34, -2.0, -3.0, -1.0, -1.0], [4, 1.0, 6.0, 2.0, 8.0], [1, -4.0, -2.0, -4.0, -2.0], [7, -1.0, -4.0, -1.0, -1.0], [8, 0.0, -4.0, 1.0, 1.0]], 3.0], [[[7, 34], [29, 33]], 13, 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]], [[[[30, 2.0, -2.0, 2.5, -1.0], [27, 0.5, 1.0, 2.0, 2.5], [32, 1.5, 1.0, 1.5, 1.0], [8, -0.5, 1.5, 0.0, 2.5], [6, 2.0, 2.0, 3.5, 4.5], [25, 0.5, 2.5, 1.0, 3.5]], 1.0], [[[6, 27], [8, 25], [8, 27], [25, 27], [27, 32]], 23, 3]], [[[[2, 1.0, -3.0, 3.0, -1.0], [8, 0.0, 5.0, 3.0, 9.0], [27, -4.0, -2.0, -2.0, -1.0], [24, 2.0, 5.0, 4.0, 10.0], [7, 6.0, -1.0, 9.0, 1.0], [32, -3.0, 0.0, 0.0, 2.0]], 3.0], [[[8, 24]], 22, 2]], [[[[10, 1.0, 1.0, 5.0, 1.0], [12, 1.0, 4.0, 6.0, 4.0], [38, 4.0, 6.0, 5.0, 6.0], [31, -4.0, -4.0, -4.0, -3.0], [5, -5.0, 4.0, -4.0, 7.0], [29, -1.0, 3.0, -1.0, 5.0], [39, 5.0, -1.0, 8.0, 0.0], [14, -1.0, -2.0, 3.0, 1.0], [17, 5.0, 5.0, 9.0, 7.0]], 1.0], [[[10, 14], [17, 38]], 69, 2]], [[[[16, 1.0, -1.5, 1.0, -1.0], [7, 0.5, 0.5, 0.5, 0.5], [36, -3.0, 0.0, -3.0, 1.5]], 2.5], [[], 3, 1]], [[[[33, 5.0, 4.0, 6.0, 9.0], [23, -6.0, 0.0, -6.0, 5.0]], 3.0], [[], 8, 1]], [[[[38, 1.0, 2.5, 3.0, 3.0], [17, 0.5, 2.0, 2.5, 4.5]], 3.0], [[[17, 38]], 6, 2]]], [[[[[17, 5.0, 0.0, 6.0, 5.0], [34, -4.0, 5.0, -2.0, 9.0], [19, 1.0, -4.0, 1.0, 0.0], [27, -4.0, -1.0, 0.0, -1.0], [22, -1.0, 2.0, 3.0, 5.0], [26, 1.0, -5.0, 1.0, -2.0], [25, 1.0, -4.0, 4.0, -4.0]], 1.0], [[[19, 25], [19, 26], [25, 26]], 65, 3]], [[[[33, 3.0, 4.0, 5.0, 8.0], [14, -1.0, -6.0, 4.0, -1.0], [20, -4.0, -5.0, -4.0, -4.0], [5, 4.0, 4.0, 4.0, 4.0], [32, 1.0, 3.0, 5.0, 5.0], [31, 2.0, 3.0, 6.0, 7.0]], 2.5], [[[5, 31], [5, 32], [5, 33], [31, 32], [31, 33], [32, 33]], 29, 4]], [[[[7, -2.5, -3.0, 0.0, -2.0], [4, 1.5, -2.5, 3.5, -1.5]], 2.5], [[[4, 7]], 6, 2]], [[[[7, 1.5, 2.0, 3.0, 4.5], [13, -1.0, 0.5, 0.5, 0.5], [26, 1.5, 3.0, 4.0, 4.0], [23, 3.0, -1.0, 3.5, 1.0], [28, -3.0, -2.5, -1.5, -0.5], [33, 0.5, -3.0, 2.5, -3.0]], 2.5], [[[7, 13], [7, 23], [7, 26]], 14, 2]], [[[[36, 2.0, 0.0, 6.0, 3.0], [32, -1.0, 6.0, -1.0, 9.0], [7, 4.0, -3.0, 9.0, 2.0]], 3.0], [[[7, 36]], 14, 2]], [[[[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]], [[[[14, -1.5, 1.5, 0.0, 2.5], [36, 0.5, 3.0, 0.5, 4.5], [4, 0.5, 3.0, 2.0, 5.0], [33, -3.0, -1.0, -2.5, 0.5], [21, -2.5, 2.5, -0.5, 3.0], [10, 1.5, 1.0, 1.5, 1.0], [7, -0.5, 0.0, 2.0, 2.0], [23, 2.0, -1.0, 2.0, 1.0], [30, 3.0, 0.0, 3.5, 0.5]], 2.0], [[[4, 7], [4, 14], [4, 36], [7, 10], [7, 14], [7, 21], [7, 23], [7, 30], [7, 36], [10, 14], [14, 21], [14, 36], [23, 30]], 24, 4]], [[[[29, -1.5, -0.5, 0.5, 1.0], [33, 0.0, 2.5, 2.0, 4.5], [11, -2.0, -2.0, 0.5, -2.0], [28, -0.5, 3.0, 0.0, 3.5]], 2.0], [[[11, 29], [28, 33]], 12, 2]]]]
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	`[[[22, 28], [24, 28], [25, 39]], 18, 2]`	`[[[22, 28], [24, 28], [25, 39]], 20, 2]`	Failed
case 1	`[[], 7, 1]`	`[[], 5, 1]`	Failed
case 2	`[[], 12, 1]`	`[[], 10, 1]`	Failed
case 3	`[[], 8, 1]`	`[[], 10, 1]`	Failed
case 4	`[[[3, 7], [7, 12]], 27, 2]`	`[[[3, 7]], 21, 2]`	Failed
case 5	`[[], 8, 1]`	`[[], 8, 1]`	Passed
case 6	`[[[3, 10], [7, 13]], 17, 2]`	`[[[3, 10], [7, 13]], 17, 2]`	Passed
case 7	`[[[6, 8], [6, 27], [8, 10], [8, 27]], 92, 3]`	`[[[6, 8], [6, 27], [8, 10], [8, 27]], 92, 3]`	Passed

SHA-256 / 0960b26990fb3f3e24da47c653ce0864cc4b7f3ae441921a666f2a2c1fef98f3

2 / The unsuccessful fix

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(boxes, cs):
    grid = {}
    inserts = 0
    for b in boxes:
        i0, i1 = math.floor(b[1] / cs), int(b[3] / cs)
        j0, j1 = math.floor(b[2] / cs), math.floor(b[4] / cs)
        for i in range(i0, i1 + 1):
            for j in range(j0, j1 + 1):
                grid.setdefault((i, j), []).append(b[0])
                inserts += 1
    pairs = set()
    for cell in grid.values():
        for p in range(len(cell)):
            for q in range(p + 1, len(cell)):
                a, c = cell[p], cell[q]
                pairs.add((min(a, c), max(a, c)))
    return [sorted([list(p) for p in pairs]), inserts, max((len(v) for v in grid.values()), default=0)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[[[[[28, 1.0, -1.0, 5.0, 1.0], [39, 5.0, -4.0, 6.0, -4.0], [25, 6.0, -3.0, 6.0, -3.0], [24, 3.0, 1.0, 7.0, 5.0], [22, -4.0, -3.0, 0.0, -2.0]], 2.5], [[[22, 28], [24, 28], [25, 39]], 20, 2]], [[[[39, -3.0, 0.0, -2.0, 3.0], [1, 2.0, -5.0, 6.0, -4.0]], 3.0], [[], 5, 1]], [[[[37, -6.0, 1.0, -3.0, 2.0], [20, -4.0, 5.0, 1.0, 7.0]], 2.0], [[], 10, 1]], [[[[12, -6.0, -5.0, -6.0, -2.0], [6, 1.0, 2.0, 1.0, 4.0], [28, -1.0, 6.0, 3.0, 9.0]], 3.0], [[], 10, 1]], [[[[12, 0.5, -0.5, 1.0, -0.5], [39, 0.0, -2.5, 0.0, -2.5], [3, -3.0, -1.5, -2.5, 1.0], [20, -1.0, 2.5, -0.5, 3.5], [7, -2.5, -0.5, -0.5, -0.5], [10, 1.5, 1.0, 3.5, 3.0]], 1.0], [[[3, 7]], 21, 2]], [[[[14, -2.5, 0.5, -2.5, 3.0], [38, 0.0, 2.0, 1.0, 3.0]], 1.0], [[], 8, 1]], [[[[13, 4.0, 1.0, 4.0, 3.0], [10, 3.0, 0.0, 3.0, 5.0], [3, 2.0, 1.0, 3.0, 4.0], [7, 5.0, 1.0, 8.0, 5.0]], 2.0], [[[3, 10], [7, 13]], 17, 2]], [[[[27, 3.0, 5.0, 6.0, 8.0], [8, 6.0, 2.0, 11.0, 6.0], [10, 5.0, -2.0, 8.0, 2.0], [11, -6.0, 3.0, -2.0, 6.0], [6, 5.0, 5.0, 6.0, 7.0]], 1.0], [[[6, 8], [6, 27], [8, 10], [8, 27]], 92, 3]]], [[[[[35, -6.0, -2.0, -2.0, 1.0], [23, 0.0, -1.0, 0.0, 3.0], [36, 3.0, -6.0, 3.0, -6.0], [34, 3.0, 0.0, 5.0, 1.0]], 3.0], [[], 9, 1]], [[[[29, 4.0, -5.0, 5.0, -1.0], [33, -3.0, 1.0, -1.0, 4.0], [3, -3.0, -1.0, -1.0, 3.0], [37, -6.0, 6.0, -1.0, 11.0], [27, 4.0, 0.0, 7.0, 5.0]], 2.0], [[[3, 33]], 30, 2]], [[[[1, -4.0, -2.0, -4.0, 3.0], [10, 1.0, 1.0, 5.0, 5.0], [19, -4.0, -6.0, 0.0, -1.0]], 1.0], [[[1, 19]], 61, 2]], [[[[29, 4.0, 5.0, 8.0, 10.0], [16, -1.0, -3.0, 4.0, -1.0]], 2.5], [[], 15, 1]], [[[[2, -3.0, -0.5, -2.5, 2.0], [10, 1.0, -3.0, 2.0, -3.0], [36, 0.0, 0.5, 2.0, 0.5]], 2.0], [[], 7, 1]], [[[[9, -2.0, -2.0, -1.0, -1.5], [20, 0.0, 1.0, 0.0, 1.0], [1, 2.0, 1.5, 3.5, 1.5], [33, -1.0, -3.0, 0.0, -1.5], [11, -0.5, 0.0, -0.5, 1.0], [39, 1.5, -1.0, 2.5, 1.0]], 1.0], [[[1, 39], [9, 33]], 17, 2]], [[[[32, -3.0, 3.0, 1.0, 5.0], [16, 5.0, 2.0, 7.0, 2.0], [6, 6.0, 1.0, 10.0, 4.0], [26, 2.0, 0.0, 6.0, 3.0], [5, 3.0, -3.0, 4.0, 2.0]], 1.0], [[[5, 26], [6, 16], [6, 26], [16, 26]], 70, 3]], [[[[8, 3.0, 1.0, 5.0, 3.0], [17, 0.0, 4.0, 1.0, 6.0], [23, -5.0, -3.0, -1.0, -1.0], [20, -3.0, -6.0, 1.0, -1.0], [33, 6.0, 5.0, 8.0, 9.0]], 3.0], [[[20, 23]], 13, 2]]], [[[[[13, 5.0, -1.0, 7.0, 4.0], [17, 4.0, -6.0, 8.0, -3.0]], 1.0], [[], 38, 1]], [[[[5, 1.0, -1.0, 3.0, 1.0], [4, 3.0, 2.5, 3.5, 3.5], [2, 1.5, -0.5, 1.5, 2.0]], 2.5], [[[2, 5]], 7, 2]], [[[[13, -0.5, 1.0, 0.0, 2.0], [22, -1.0, -1.5, -0.5, -0.5], [32, 3.0, -2.0, 3.0, -0.5]], 2.0], [[], 6, 1]], [[[[8, 3.0, 3.0, 5.0, 5.5], [27, -2.0, 1.5, -2.0, 3.0], [5, 0.0, 2.5, 1.5, 3.5], [2, -1.0, -1.0, -1.0, 1.0], [37, 3.0, 3.0, 4.5, 4.0], [4, 1.0, 0.5, 3.0, 2.5], [13, 2.0, 3.0, 2.0, 5.0]], 3.0], [[[2, 27], [4, 5], [5, 13], [8, 37]], 11, 2]], [[[[11, -2.5, 1.5, 0.0, 2.0], [39, -2.5, 0.5, -1.0, 2.0], [34, -3.0, -2.0, -1.5, -1.0], [31, -0.5, -1.5, 2.0, -1.0], [23, 0.5, -1.0, 2.0, -0.5], [27, 1.5, 2.0, 1.5, 2.0]], 2.5], [[[11, 27], [11, 39], [23, 31], [31, 34]], 9, 2]], [[[[18, -0.5, -3.0, 1.5, -1.0], [16, 2.5, -3.0, 4.0, -1.5]], 2.5], [[], 6, 1]], [[[[33, -3.0, -3.0, -1.0, -1.0], [24, -3.0, -1.0, -3.0, 0.5], [19, 1.5, -1.0, 2.5, -0.5], [13, 1.5, -1.5, 3.5, 0.0]], 1.0], [[[13, 19], [24, 33]], 22, 2]], [[[[13, 1.0, 4.0, 4.0, 8.0], [39, 4.0, -4.0, 6.0, 1.0], [11, 0.0, 6.0, 0.0, 8.0], [15, -3.0, -3.0, 0.0, -1.0], [30, 2.0, -1.0, 2.0, 1.0], [31, -1.0, 0.0, -1.0, 5.0], [37, 6.0, 5.0, 6.0, 10.0], [7, 6.0, 3.0, 6.0, 8.0]], 3.0], [[[7, 37], [11, 13], [15, 30]], 22, 2]]], [[[[[19, 3.0, -5.0, 4.0, -3.0], [29, 6.0, -4.0, 7.0, -4.0], [33, 6.0, -5.0, 6.0, -2.0], [34, -2.0, -3.0, -1.0, -1.0], [4, 1.0, 6.0, 2.0, 8.0], [1, -4.0, -2.0, -4.0, -2.0], [7, -1.0, -4.0, -1.0, -1.0], [8, 0.0, -4.0, 1.0, 1.0]], 3.0], [[[7, 34], [29, 33]], 13, 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]], [[[[30, 2.0, -2.0, 2.5, -1.0], [27, 0.5, 1.0, 2.0, 2.5], [32, 1.5, 1.0, 1.5, 1.0], [8, -0.5, 1.5, 0.0, 2.5], [6, 2.0, 2.0, 3.5, 4.5], [25, 0.5, 2.5, 1.0, 3.5]], 1.0], [[[6, 27], [8, 25], [8, 27], [25, 27], [27, 32]], 23, 3]], [[[[2, 1.0, -3.0, 3.0, -1.0], [8, 0.0, 5.0, 3.0, 9.0], [27, -4.0, -2.0, -2.0, -1.0], [24, 2.0, 5.0, 4.0, 10.0], [7, 6.0, -1.0, 9.0, 1.0], [32, -3.0, 0.0, 0.0, 2.0]], 3.0], [[[8, 24]], 22, 2]], [[[[10, 1.0, 1.0, 5.0, 1.0], [12, 1.0, 4.0, 6.0, 4.0], [38, 4.0, 6.0, 5.0, 6.0], [31, -4.0, -4.0, -4.0, -3.0], [5, -5.0, 4.0, -4.0, 7.0], [29, -1.0, 3.0, -1.0, 5.0], [39, 5.0, -1.0, 8.0, 0.0], [14, -1.0, -2.0, 3.0, 1.0], [17, 5.0, 5.0, 9.0, 7.0]], 1.0], [[[10, 14], [17, 38]], 69, 2]], [[[[16, 1.0, -1.5, 1.0, -1.0], [7, 0.5, 0.5, 0.5, 0.5], [36, -3.0, 0.0, -3.0, 1.5]], 2.5], [[], 3, 1]], [[[[33, 5.0, 4.0, 6.0, 9.0], [23, -6.0, 0.0, -6.0, 5.0]], 3.0], [[], 8, 1]], [[[[38, 1.0, 2.5, 3.0, 3.0], [17, 0.5, 2.0, 2.5, 4.5]], 3.0], [[[17, 38]], 6, 2]]], [[[[[17, 5.0, 0.0, 6.0, 5.0], [34, -4.0, 5.0, -2.0, 9.0], [19, 1.0, -4.0, 1.0, 0.0], [27, -4.0, -1.0, 0.0, -1.0], [22, -1.0, 2.0, 3.0, 5.0], [26, 1.0, -5.0, 1.0, -2.0], [25, 1.0, -4.0, 4.0, -4.0]], 1.0], [[[19, 25], [19, 26], [25, 26]], 65, 3]], [[[[33, 3.0, 4.0, 5.0, 8.0], [14, -1.0, -6.0, 4.0, -1.0], [20, -4.0, -5.0, -4.0, -4.0], [5, 4.0, 4.0, 4.0, 4.0], [32, 1.0, 3.0, 5.0, 5.0], [31, 2.0, 3.0, 6.0, 7.0]], 2.5], [[[5, 31], [5, 32], [5, 33], [31, 32], [31, 33], [32, 33]], 29, 4]], [[[[7, -2.5, -3.0, 0.0, -2.0], [4, 1.5, -2.5, 3.5, -1.5]], 2.5], [[[4, 7]], 6, 2]], [[[[7, 1.5, 2.0, 3.0, 4.5], [13, -1.0, 0.5, 0.5, 0.5], [26, 1.5, 3.0, 4.0, 4.0], [23, 3.0, -1.0, 3.5, 1.0], [28, -3.0, -2.5, -1.5, -0.5], [33, 0.5, -3.0, 2.5, -3.0]], 2.5], [[[7, 13], [7, 23], [7, 26]], 14, 2]], [[[[36, 2.0, 0.0, 6.0, 3.0], [32, -1.0, 6.0, -1.0, 9.0], [7, 4.0, -3.0, 9.0, 2.0]], 3.0], [[[7, 36]], 14, 2]], [[[[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]], [[[[14, -1.5, 1.5, 0.0, 2.5], [36, 0.5, 3.0, 0.5, 4.5], [4, 0.5, 3.0, 2.0, 5.0], [33, -3.0, -1.0, -2.5, 0.5], [21, -2.5, 2.5, -0.5, 3.0], [10, 1.5, 1.0, 1.5, 1.0], [7, -0.5, 0.0, 2.0, 2.0], [23, 2.0, -1.0, 2.0, 1.0], [30, 3.0, 0.0, 3.5, 0.5]], 2.0], [[[4, 7], [4, 14], [4, 36], [7, 10], [7, 14], [7, 21], [7, 23], [7, 30], [7, 36], [10, 14], [14, 21], [14, 36], [23, 30]], 24, 4]], [[[[29, -1.5, -0.5, 0.5, 1.0], [33, 0.0, 2.5, 2.0, 4.5], [11, -2.0, -2.0, 0.5, -2.0], [28, -0.5, 3.0, 0.0, 3.5]], 2.0], [[[11, 29], [28, 33]], 12, 2]]]]
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	`[[[22, 28], [24, 28], [25, 39]], 20, 2]`	`[[[22, 28], [24, 28], [25, 39]], 20, 2]`	Passed
case 1	`[[], 7, 1]`	`[[], 5, 1]`	Failed
case 2	`[[], 12, 1]`	`[[], 10, 1]`	Failed
case 3	`[[], 10, 1]`	`[[], 10, 1]`	Passed
case 4	`[[[3, 7], [7, 12]], 28, 2]`	`[[[3, 7]], 21, 2]`	Failed
case 5	`[[], 12, 1]`	`[[], 8, 1]`	Failed
case 6	`[[[3, 10], [7, 13]], 17, 2]`	`[[[3, 10], [7, 13]], 17, 2]`	Passed
case 7	`[[[6, 8], [6, 27], [8, 10], [8, 27]], 92, 3]`	`[[[6, 8], [6, 27], [8, 10], [8, 27]], 92, 3]`	Passed

SHA-256 / b96d2988572e9cfb8cef65324c9fd9db6624f72d1f3ffce643940bb5996ff751

3 / The verified repair

Exit 0

"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(boxes, cs):
    grid = {}
    inserts = 0
    for b in boxes:
        i0, i1 = math.floor(b[1] / cs), math.floor(b[3] / cs)
        j0, j1 = math.floor(b[2] / cs), math.floor(b[4] / cs)
        for i in range(i0, i1 + 1):
            for j in range(j0, j1 + 1):
                grid.setdefault((i, j), []).append(b[0])
                inserts += 1
    pairs = set()
    for cell in grid.values():
        for p in range(len(cell)):
            for q in range(p + 1, len(cell)):
                a, c = cell[p], cell[q]
                pairs.add((min(a, c), max(a, c)))
    return [sorted([list(p) for p in pairs]), inserts, max((len(v) for v in grid.values()), default=0)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[[[[[28, 1.0, -1.0, 5.0, 1.0], [39, 5.0, -4.0, 6.0, -4.0], [25, 6.0, -3.0, 6.0, -3.0], [24, 3.0, 1.0, 7.0, 5.0], [22, -4.0, -3.0, 0.0, -2.0]], 2.5], [[[22, 28], [24, 28], [25, 39]], 20, 2]], [[[[39, -3.0, 0.0, -2.0, 3.0], [1, 2.0, -5.0, 6.0, -4.0]], 3.0], [[], 5, 1]], [[[[37, -6.0, 1.0, -3.0, 2.0], [20, -4.0, 5.0, 1.0, 7.0]], 2.0], [[], 10, 1]], [[[[12, -6.0, -5.0, -6.0, -2.0], [6, 1.0, 2.0, 1.0, 4.0], [28, -1.0, 6.0, 3.0, 9.0]], 3.0], [[], 10, 1]], [[[[12, 0.5, -0.5, 1.0, -0.5], [39, 0.0, -2.5, 0.0, -2.5], [3, -3.0, -1.5, -2.5, 1.0], [20, -1.0, 2.5, -0.5, 3.5], [7, -2.5, -0.5, -0.5, -0.5], [10, 1.5, 1.0, 3.5, 3.0]], 1.0], [[[3, 7]], 21, 2]], [[[[14, -2.5, 0.5, -2.5, 3.0], [38, 0.0, 2.0, 1.0, 3.0]], 1.0], [[], 8, 1]], [[[[13, 4.0, 1.0, 4.0, 3.0], [10, 3.0, 0.0, 3.0, 5.0], [3, 2.0, 1.0, 3.0, 4.0], [7, 5.0, 1.0, 8.0, 5.0]], 2.0], [[[3, 10], [7, 13]], 17, 2]], [[[[27, 3.0, 5.0, 6.0, 8.0], [8, 6.0, 2.0, 11.0, 6.0], [10, 5.0, -2.0, 8.0, 2.0], [11, -6.0, 3.0, -2.0, 6.0], [6, 5.0, 5.0, 6.0, 7.0]], 1.0], [[[6, 8], [6, 27], [8, 10], [8, 27]], 92, 3]]], [[[[[35, -6.0, -2.0, -2.0, 1.0], [23, 0.0, -1.0, 0.0, 3.0], [36, 3.0, -6.0, 3.0, -6.0], [34, 3.0, 0.0, 5.0, 1.0]], 3.0], [[], 9, 1]], [[[[29, 4.0, -5.0, 5.0, -1.0], [33, -3.0, 1.0, -1.0, 4.0], [3, -3.0, -1.0, -1.0, 3.0], [37, -6.0, 6.0, -1.0, 11.0], [27, 4.0, 0.0, 7.0, 5.0]], 2.0], [[[3, 33]], 30, 2]], [[[[1, -4.0, -2.0, -4.0, 3.0], [10, 1.0, 1.0, 5.0, 5.0], [19, -4.0, -6.0, 0.0, -1.0]], 1.0], [[[1, 19]], 61, 2]], [[[[29, 4.0, 5.0, 8.0, 10.0], [16, -1.0, -3.0, 4.0, -1.0]], 2.5], [[], 15, 1]], [[[[2, -3.0, -0.5, -2.5, 2.0], [10, 1.0, -3.0, 2.0, -3.0], [36, 0.0, 0.5, 2.0, 0.5]], 2.0], [[], 7, 1]], [[[[9, -2.0, -2.0, -1.0, -1.5], [20, 0.0, 1.0, 0.0, 1.0], [1, 2.0, 1.5, 3.5, 1.5], [33, -1.0, -3.0, 0.0, -1.5], [11, -0.5, 0.0, -0.5, 1.0], [39, 1.5, -1.0, 2.5, 1.0]], 1.0], [[[1, 39], [9, 33]], 17, 2]], [[[[32, -3.0, 3.0, 1.0, 5.0], [16, 5.0, 2.0, 7.0, 2.0], [6, 6.0, 1.0, 10.0, 4.0], [26, 2.0, 0.0, 6.0, 3.0], [5, 3.0, -3.0, 4.0, 2.0]], 1.0], [[[5, 26], [6, 16], [6, 26], [16, 26]], 70, 3]], [[[[8, 3.0, 1.0, 5.0, 3.0], [17, 0.0, 4.0, 1.0, 6.0], [23, -5.0, -3.0, -1.0, -1.0], [20, -3.0, -6.0, 1.0, -1.0], [33, 6.0, 5.0, 8.0, 9.0]], 3.0], [[[20, 23]], 13, 2]]], [[[[[13, 5.0, -1.0, 7.0, 4.0], [17, 4.0, -6.0, 8.0, -3.0]], 1.0], [[], 38, 1]], [[[[5, 1.0, -1.0, 3.0, 1.0], [4, 3.0, 2.5, 3.5, 3.5], [2, 1.5, -0.5, 1.5, 2.0]], 2.5], [[[2, 5]], 7, 2]], [[[[13, -0.5, 1.0, 0.0, 2.0], [22, -1.0, -1.5, -0.5, -0.5], [32, 3.0, -2.0, 3.0, -0.5]], 2.0], [[], 6, 1]], [[[[8, 3.0, 3.0, 5.0, 5.5], [27, -2.0, 1.5, -2.0, 3.0], [5, 0.0, 2.5, 1.5, 3.5], [2, -1.0, -1.0, -1.0, 1.0], [37, 3.0, 3.0, 4.5, 4.0], [4, 1.0, 0.5, 3.0, 2.5], [13, 2.0, 3.0, 2.0, 5.0]], 3.0], [[[2, 27], [4, 5], [5, 13], [8, 37]], 11, 2]], [[[[11, -2.5, 1.5, 0.0, 2.0], [39, -2.5, 0.5, -1.0, 2.0], [34, -3.0, -2.0, -1.5, -1.0], [31, -0.5, -1.5, 2.0, -1.0], [23, 0.5, -1.0, 2.0, -0.5], [27, 1.5, 2.0, 1.5, 2.0]], 2.5], [[[11, 27], [11, 39], [23, 31], [31, 34]], 9, 2]], [[[[18, -0.5, -3.0, 1.5, -1.0], [16, 2.5, -3.0, 4.0, -1.5]], 2.5], [[], 6, 1]], [[[[33, -3.0, -3.0, -1.0, -1.0], [24, -3.0, -1.0, -3.0, 0.5], [19, 1.5, -1.0, 2.5, -0.5], [13, 1.5, -1.5, 3.5, 0.0]], 1.0], [[[13, 19], [24, 33]], 22, 2]], [[[[13, 1.0, 4.0, 4.0, 8.0], [39, 4.0, -4.0, 6.0, 1.0], [11, 0.0, 6.0, 0.0, 8.0], [15, -3.0, -3.0, 0.0, -1.0], [30, 2.0, -1.0, 2.0, 1.0], [31, -1.0, 0.0, -1.0, 5.0], [37, 6.0, 5.0, 6.0, 10.0], [7, 6.0, 3.0, 6.0, 8.0]], 3.0], [[[7, 37], [11, 13], [15, 30]], 22, 2]]], [[[[[19, 3.0, -5.0, 4.0, -3.0], [29, 6.0, -4.0, 7.0, -4.0], [33, 6.0, -5.0, 6.0, -2.0], [34, -2.0, -3.0, -1.0, -1.0], [4, 1.0, 6.0, 2.0, 8.0], [1, -4.0, -2.0, -4.0, -2.0], [7, -1.0, -4.0, -1.0, -1.0], [8, 0.0, -4.0, 1.0, 1.0]], 3.0], [[[7, 34], [29, 33]], 13, 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]], [[[[30, 2.0, -2.0, 2.5, -1.0], [27, 0.5, 1.0, 2.0, 2.5], [32, 1.5, 1.0, 1.5, 1.0], [8, -0.5, 1.5, 0.0, 2.5], [6, 2.0, 2.0, 3.5, 4.5], [25, 0.5, 2.5, 1.0, 3.5]], 1.0], [[[6, 27], [8, 25], [8, 27], [25, 27], [27, 32]], 23, 3]], [[[[2, 1.0, -3.0, 3.0, -1.0], [8, 0.0, 5.0, 3.0, 9.0], [27, -4.0, -2.0, -2.0, -1.0], [24, 2.0, 5.0, 4.0, 10.0], [7, 6.0, -1.0, 9.0, 1.0], [32, -3.0, 0.0, 0.0, 2.0]], 3.0], [[[8, 24]], 22, 2]], [[[[10, 1.0, 1.0, 5.0, 1.0], [12, 1.0, 4.0, 6.0, 4.0], [38, 4.0, 6.0, 5.0, 6.0], [31, -4.0, -4.0, -4.0, -3.0], [5, -5.0, 4.0, -4.0, 7.0], [29, -1.0, 3.0, -1.0, 5.0], [39, 5.0, -1.0, 8.0, 0.0], [14, -1.0, -2.0, 3.0, 1.0], [17, 5.0, 5.0, 9.0, 7.0]], 1.0], [[[10, 14], [17, 38]], 69, 2]], [[[[16, 1.0, -1.5, 1.0, -1.0], [7, 0.5, 0.5, 0.5, 0.5], [36, -3.0, 0.0, -3.0, 1.5]], 2.5], [[], 3, 1]], [[[[33, 5.0, 4.0, 6.0, 9.0], [23, -6.0, 0.0, -6.0, 5.0]], 3.0], [[], 8, 1]], [[[[38, 1.0, 2.5, 3.0, 3.0], [17, 0.5, 2.0, 2.5, 4.5]], 3.0], [[[17, 38]], 6, 2]]], [[[[[17, 5.0, 0.0, 6.0, 5.0], [34, -4.0, 5.0, -2.0, 9.0], [19, 1.0, -4.0, 1.0, 0.0], [27, -4.0, -1.0, 0.0, -1.0], [22, -1.0, 2.0, 3.0, 5.0], [26, 1.0, -5.0, 1.0, -2.0], [25, 1.0, -4.0, 4.0, -4.0]], 1.0], [[[19, 25], [19, 26], [25, 26]], 65, 3]], [[[[33, 3.0, 4.0, 5.0, 8.0], [14, -1.0, -6.0, 4.0, -1.0], [20, -4.0, -5.0, -4.0, -4.0], [5, 4.0, 4.0, 4.0, 4.0], [32, 1.0, 3.0, 5.0, 5.0], [31, 2.0, 3.0, 6.0, 7.0]], 2.5], [[[5, 31], [5, 32], [5, 33], [31, 32], [31, 33], [32, 33]], 29, 4]], [[[[7, -2.5, -3.0, 0.0, -2.0], [4, 1.5, -2.5, 3.5, -1.5]], 2.5], [[[4, 7]], 6, 2]], [[[[7, 1.5, 2.0, 3.0, 4.5], [13, -1.0, 0.5, 0.5, 0.5], [26, 1.5, 3.0, 4.0, 4.0], [23, 3.0, -1.0, 3.5, 1.0], [28, -3.0, -2.5, -1.5, -0.5], [33, 0.5, -3.0, 2.5, -3.0]], 2.5], [[[7, 13], [7, 23], [7, 26]], 14, 2]], [[[[36, 2.0, 0.0, 6.0, 3.0], [32, -1.0, 6.0, -1.0, 9.0], [7, 4.0, -3.0, 9.0, 2.0]], 3.0], [[[7, 36]], 14, 2]], [[[[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]], [[[[14, -1.5, 1.5, 0.0, 2.5], [36, 0.5, 3.0, 0.5, 4.5], [4, 0.5, 3.0, 2.0, 5.0], [33, -3.0, -1.0, -2.5, 0.5], [21, -2.5, 2.5, -0.5, 3.0], [10, 1.5, 1.0, 1.5, 1.0], [7, -0.5, 0.0, 2.0, 2.0], [23, 2.0, -1.0, 2.0, 1.0], [30, 3.0, 0.0, 3.5, 0.5]], 2.0], [[[4, 7], [4, 14], [4, 36], [7, 10], [7, 14], [7, 21], [7, 23], [7, 30], [7, 36], [10, 14], [14, 21], [14, 36], [23, 30]], 24, 4]], [[[[29, -1.5, -0.5, 0.5, 1.0], [33, 0.0, 2.5, 2.0, 4.5], [11, -2.0, -2.0, 0.5, -2.0], [28, -0.5, 3.0, 0.0, 3.5]], 2.0], [[[11, 29], [28, 33]], 12, 2]]]]
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	`[[[22, 28], [24, 28], [25, 39]], 20, 2]`	`[[[22, 28], [24, 28], [25, 39]], 20, 2]`	Passed
case 1	`[[], 5, 1]`	`[[], 5, 1]`	Passed
case 2	`[[], 10, 1]`	`[[], 10, 1]`	Passed
case 3	`[[], 10, 1]`	`[[], 10, 1]`	Passed
case 4	`[[[3, 7]], 21, 2]`	`[[[3, 7]], 21, 2]`	Passed
case 5	`[[], 8, 1]`	`[[], 8, 1]`	Passed
case 6	`[[[3, 10], [7, 13]], 17, 2]`	`[[[3, 10], [7, 13]], 17, 2]`	Passed
case 7	`[[[6, 8], [6, 27], [8, 10], [8, 27]], 92, 3]`	`[[[6, 8], [6, 27], [8, 10], [8, 27]], 92, 3]`	Passed

SHA-256 / 633e724d055f29cbd870c99fa781b9857d225b27edf461b8d85f74eefd5eda9b

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

Case digest / bcd88ec5bafea8a236df6697e12375384c7aba28d67401f1fe869168b4db41d5