FA-87381 / Collision detection broadphase / Open access

Grid row range uses the maximum x as maximum y · case 01

Tall boxes are inserted into too few rows, wide boxes into too many.

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

ROOT CAUSE

j1 is computed from maxx.

VERIFIED REPAIR

Rows run from floor(miny/cs) to floor(maxy/cs).

Unsuccessful approach: Using minx for the first row mixes axes the other way.

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 = math.floor(b[1] / cs), math.floor(b[3] / cs)
        j0, j1 = math.floor(b[2] / cs), math.floor(b[3] / 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 = [[[[[[14, -1.0, -6.0, 1.0, -4.0], [11, 5.0, -3.0, 7.0, 1.0], [36, 1.0, 4.0, 1.0, 9.0]], 2.5], [[], 10, 1]], [[[[4, 5.0, 3.0, 5.0, 3.0], [32, -4.0, 4.0, -4.0, 7.0], [19, -2.0, 4.0, -1.0, 7.0], [23, -6.0, -6.0, -3.0, -2.0], [16, -1.0, 2.0, 1.0, 2.0]], 2.5], [[], 13, 1]], [[[[14, -2.5, 0.5, -2.5, 3.0], [38, 0.0, 2.0, 1.0, 3.0]], 1.0], [[], 8, 1]], [[[[31, -1.5, 0.0, 0.5, 0.0], [39, -2.5, 1.5, 0.0, 3.5]], 3.0], [[[31, 39]], 6, 2]], [[[[38, -0.5, 3.0, 0.0, 4.5], [37, -1.0, -3.0, -1.0, -2.5], [14, -1.5, -1.0, -1.0, -1.0], [18, 1.5, -1.0, 2.5, 0.5], [32, -3.0, 2.0, -0.5, 2.5], [16, 1.0, 3.0, 1.5, 3.0]], 2.0], [[[16, 38], [32, 38]], 13, 2]], [[[[13, 2.0, 3.0, 2.5, 5.5], [36, -3.0, 1.0, -3.0, 3.0]], 2.0], [[], 4, 1]], [[[[12, -2.5, -2.0, -2.0, -2.0], [8, -3.0, -2.5, -0.5, -1.5]], 3.0], [[[8, 12]], 2, 2]], [[[[7, 5.0, 1.0, 5.0, 4.0], [6, 0.0, -6.0, 5.0, -1.0], [22, 6.0, 6.0, 9.0, 10.0], [34, -1.0, 2.0, -1.0, 6.0], [1, 4.0, -5.0, 4.0, -2.0]], 2.5], [[[1, 6]], 22, 2]]], [[[[[20, 0.0, 1.0, 1.0, 1.0], [7, -1.0, -3.0, 2.0, -1.0], [10, 0.0, -2.0, 3.0, 0.0], [35, 5.0, 6.0, 7.0, 7.0], [32, 2.0, -4.0, 5.0, -2.0], [4, -6.0, 1.0, -6.0, 6.0]], 1.0], [[[7, 10], [7, 32], [10, 32]], 50, 3]], [[[[31, 1.0, -4.0, 2.0, -3.0], [34, 3.0, 0.0, 3.0, 2.0], [39, 3.0, 2.0, 3.0, 7.0], [18, 1.0, 3.0, 2.0, 4.0]], 3.0], [[[34, 39]], 7, 2]], [[[[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]], [[[[6, -2.5, 2.5, -1.5, 4.0], [32, -2.5, 0.5, -0.5, 1.0], [29, 2.5, 0.0, 4.0, 1.5], [18, -2.5, -0.5, -1.0, 2.0]], 1.0], [[[6, 18], [18, 32]], 30, 2]], [[[[19, 3.0, 3.0, 4.5, 5.5], [18, 1.5, -2.0, 3.0, -1.0], [2, -1.5, 0.5, -1.0, 3.0], [27, 3.0, 1.5, 5.0, 3.5], [32, -3.0, 0.0, -2.5, 1.5], [34, -0.5, 2.5, 2.0, 2.5], [14, -1.0, 2.5, -0.5, 2.5]], 3.0], [[[2, 14], [2, 32], [2, 34], [14, 32], [14, 34], [19, 27], [32, 34]], 11, 4]], [[[[24, -4.0, 3.0, -4.0, 5.0], [19, 5.0, 1.0, 8.0, 6.0]], 2.5], [[], 8, 1]], [[[[1, 1.0, -6.0, 4.0, -1.0], [35, -5.0, 6.0, 0.0, 11.0], [13, 5.0, 4.0, 5.0, 7.0], [17, 4.0, 3.0, 4.0, 7.0]], 2.0], [[[13, 17]], 26, 2]], [[[[9, 1.0, 0.5, 3.5, 1.0], [16, -2.5, -3.0, -1.0, -0.5], [8, -3.0, 1.5, -1.0, 3.5], [28, -2.5, -2.5, -1.5, -1.5]], 3.0], [[[16, 28]], 6, 2]]], [[[[[21, 1.0, -1.0, 5.0, 2.0], [18, -6.0, 3.0, -3.0, 8.0], [29, 6.0, -1.0, 6.0, 2.0], [10, 5.0, 0.0, 7.0, 1.0], [30, 0.0, -4.0, 3.0, -3.0], [16, 2.0, 1.0, 7.0, 2.0]], 2.5], [[[10, 16], [10, 21], [10, 29], [16, 21], [16, 29], [21, 29]], 20, 4]], [[[[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]], [[[[7, 0.0, 1.0, 5.0, 2.0], [2, -4.0, -1.0, -1.0, 2.0]], 3.0], [[], 6, 1]], [[[[22, 1.0, -5.0, 3.0, -1.0], [35, -5.0, -6.0, -1.0, -1.0], [16, -1.0, -2.0, -1.0, 2.0], [1, 4.0, 2.0, 9.0, 3.0], [24, 5.0, -3.0, 7.0, 0.0], [5, 4.0, 1.0, 5.0, 1.0]], 2.5], [[[1, 5], [1, 24], [5, 24], [16, 35]], 23, 3]], [[[[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]], [[[[23, -2.0, 3.0, -0.5, 3.5], [26, 3.0, 2.0, 5.5, 3.0], [38, -1.5, 0.0, 0.0, 0.0], [4, 1.5, 2.5, 4.0, 5.0]], 1.0], [[[4, 26]], 27, 2]], [[[[34, 2.0, 4.0, 7.0, 8.0], [3, 5.0, -3.0, 9.0, 1.0], [15, -3.0, 1.0, 2.0, 2.0], [24, -5.0, -1.0, -1.0, -1.0]], 3.0], [[], 16, 1]], [[[[1, 4.0, -2.0, 8.0, 3.0], [19, -6.0, 3.0, -4.0, 6.0]], 3.0], [[], 8, 1]]], [[[[[32, 3.0, -5.0, 4.0, -3.0], [30, 2.0, 4.0, 6.0, 9.0], [11, 0.0, -4.0, 0.0, -1.0]], 2.5], [[], 12, 1]], [[[[33, 2.0, 0.0, 5.0, 1.0], [26, 1.0, -1.0, 1.0, 0.0], [29, -5.0, 2.0, -4.0, 5.0]], 2.0], [[], 8, 1]], [[[[22, -0.5, -2.5, 1.0, -1.0], [14, 2.0, -2.0, 2.0, -2.0], [24, 2.5, 0.5, 3.0, 1.5], [5, -1.5, 3.0, 1.0, 5.0], [19, -1.0, -1.5, 1.0, -1.0], [17, -0.5, -2.5, 1.5, -0.5], [33, 3.0, 3.0, 5.5, 5.5]], 1.0], [[[17, 19], [17, 22], [19, 22]], 50, 3]], [[[[33, 5.0, 4.0, 6.0, 9.0], [23, -6.0, 0.0, -6.0, 5.0]], 3.0], [[], 8, 1]], [[[[23, -4.0, 4.0, -4.0, 7.0], [25, 5.0, 4.0, 9.0, 6.0]], 2.5], [[], 6, 1]], [[[[32, 2.0, -1.0, 2.0, 0.0], [15, 2.5, 1.0, 4.0, 2.5], [34, -2.0, 2.5, 0.0, 5.0], [1, 2.0, 1.5, 2.5, 2.5]], 3.0], [[[1, 15], [1, 32], [1, 34], [15, 32], [15, 34], [32, 34]], 9, 4]], [[[[28, -2.0, 3.0, -2.0, 3.5], [14, 1.0, 3.0, 1.5, 4.5], [12, 2.5, -1.5, 4.0, -0.5], [33, 0.0, 2.5, 1.0, 2.5], [6, -2.0, 1.0, -0.5, 1.5], [17, 1.0, 0.5, 2.5, 2.5]], 3.0], [[[17, 33]], 7, 2]], [[[[22, 1.0, 3.0, 3.0, 6.0], [10, -6.0, 1.0, -2.0, 5.0], [2, 5.0, 5.0, 10.0, 6.0], [20, 1.0, -4.0, 4.0, -2.0]], 1.0], [[], 61, 1]]], [[[[[18, 3.0, 3.0, 4.0, 4.0], [25, 3.0, 0.5, 5.0, 3.0], [15, -2.0, -0.5, -1.5, 1.0], [21, 0.0, 2.5, 0.5, 4.0], [6, 3.0, 0.5, 5.5, 3.0], [29, -3.0, 1.0, -0.5, 1.5], [11, -1.5, 2.0, 0.5, 3.0], [10, 0.5, -0.5, 2.5, 0.0]], 1.0], [[[6, 18], [6, 25], [11, 21], [15, 29], [18, 25]], 49, 3]], [[[[27, 0.0, 4.0, 2.0, 6.0], [26, -2.0, 5.0, -1.0, 5.0], [14, 1.0, 6.0, 1.0, 7.0]], 1.0], [[[14, 27]], 13, 2]], [[[[9, -6.0, 2.0, -3.0, 3.0], [13, -6.0, 3.0, -3.0, 5.0], [11, 1.0, -6.0, 4.0, -5.0], [35, 2.0, 1.0, 4.0, 3.0], [24, -1.0, -3.0, 4.0, 0.0], [39, 3.0, 1.0, 4.0, 6.0]], 2.5], [[[9, 13], [11, 24], [24, 35], [24, 39], [35, 39]], 28, 3]], [[[[12, 6.0, -3.0, 8.0, -2.0], [23, 2.0, 6.0, 5.0, 8.0], [11, -3.0, 0.0, 1.0, 4.0], [10, -3.0, -1.0, -1.0, 2.0], [29, -5.0, -4.0, 0.0, -4.0], [6, 1.0, -1.0, 1.0, 2.0], [38, 5.0, 1.0, 10.0, 3.0]], 2.5], [[[6, 11], [10, 11]], 31, 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]], [[[[4, -1.0, -2.0, 0.5, -0.5], [34, -3.0, -2.0, -1.5, 0.0], [26, 2.0, 2.5, 2.5, 3.0], [5, 1.5, -0.5, 3.5, 1.5]], 3.0], [[[4, 5], [4, 34], [5, 26]], 10, 2]], [[[[37, 0.0, 2.5, 1.5, 2.5], [14, 2.0, -0.5, 3.0, 0.5]], 2.0], [[], 3, 1]], [[[[27, 3.0, -6.0, 6.0, -1.0], [29, 1.0, 3.0, 4.0, 3.0], [10, -3.0, 1.0, 0.0, 1.0]], 2.0], [[], 15, 1]]]]
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	`[[], 13, 1]`	`[[], 10, 1]`	Failed
case 1	`[[], 8, 1]`	`[[], 13, 1]`	Failed
case 2	`[[], 0, 0]`	`[[], 8, 1]`	Failed
case 3	`[[[31, 39]], 4, 2]`	`[[[31, 39]], 6, 2]`	Failed
case 4	`[[[14, 37]], 9, 2]`	`[[[16, 38], [32, 38]], 13, 2]`	Failed
case 5	`[[], 1, 1]`	`[[], 4, 1]`	Failed
case 6	`[[[8, 12]], 2, 2]`	`[[[8, 12]], 2, 2]`	Passed
case 7	`[[[1, 6], [6, 7], [6, 22], [7, 22]], 29, 3]`	`[[[1, 6]], 22, 2]`	Failed

SHA-256 / ba91ff9672466a5293dd6722fa981f48d3517dcf66d5513d8b92c92245ecd2cd

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

SHA-256 / 0c10af3d8c94a7892c2237e704f84ee0e027784ede49263b6def4ce1148c4532

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

SHA-256 / 84374a5d3ca965c6e9ac94ae752e6a05f6a0088e4e65f3295c54228e1ddcf2e9

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

Case digest / d75eea2f3d1e7799c5fb961e7354f6c17b339a7fdfefcb7d3fdb4df980c5c9bf