FA-87371 / Collision detection broadphase / Open access

Grid insertion excludes the cell containing the maximum corner · case 01

Boxes are missing from their last row and column of cells and contacts there are lost.

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

ROOT CAUSE

The x cell range is range(i0, i1).

VERIFIED REPAIR

Cover i0..i1 inclusive.

Unsuccessful approach: Forcing at least one column still drops the last column of wide boxes.

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[4] / cs)
        for i in range(i0, i1):
            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 = [[[[[[7, 1.0, -3.0, 6.0, -3.0], [28, 1.0, 0.0, 1.0, 1.0], [26, 4.0, 1.0, 6.0, 6.0], [29, -5.0, 0.0, -2.0, 4.0]], 1.0], [[], 46, 1]], [[[[22, -1.0, 0.5, -0.5, 2.5], [36, 3.0, 1.5, 4.5, 3.5], [6, 0.5, 0.0, 3.0, 1.0], [30, -2.0, 1.5, -1.5, 3.0], [27, 0.5, 2.0, 0.5, 2.5], [8, -1.0, -0.5, 0.5, -0.5]], 3.0], [[[6, 27], [6, 36], [22, 30]], 10, 2]], [[[[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]], [[[[31, -1.5, 0.0, 0.5, 0.0], [39, -2.5, 1.5, 0.0, 3.5]], 3.0], [[[31, 39]], 6, 2]], [[[[28, 3.0, -0.5, 5.0, -0.5], [8, 0.5, 0.5, 2.5, 1.5], [17, -3.0, 1.0, -1.0, 1.5]], 2.5], [[], 6, 1]], [[[[30, 4.0, -2.0, 7.0, -1.0], [28, 6.0, 3.0, 11.0, 6.0]], 2.0], [[], 11, 1]], [[[[14, -2.5, 0.5, -2.5, 3.0], [38, 0.0, 2.0, 1.0, 3.0]], 1.0], [[], 8, 1]], [[[[25, 3.0, 4.0, 3.0, 4.0], [23, 3.0, 6.0, 8.0, 8.0], [6, 0.0, 5.0, 3.0, 5.0], [19, 3.0, 1.0, 6.0, 4.0], [4, -6.0, 1.0, -5.0, 2.0]], 2.5], [[[6, 23], [19, 25]], 15, 2]]], [[[[[23, 4.0, -2.0, 7.0, 1.0], [38, -5.0, 3.0, 0.0, 7.0], [24, -6.0, 1.0, -1.0, 2.0], [34, -3.0, -1.0, 1.0, 0.0], [35, 3.0, 0.0, 3.0, 4.0]], 1.0], [[], 73, 1]], [[[[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]], [[[[26, 1.0, -1.5, 3.0, -1.0], [11, -2.0, -1.5, -1.0, 1.0]], 2.5], [[], 4, 1]], [[[[29, 1.0, 4.0, 2.0, 6.0], [9, -5.0, 5.0, -1.0, 9.0], [12, 6.0, -1.0, 6.0, -1.0], [22, 4.0, -5.0, 8.0, -4.0], [21, -4.0, -5.0, 0.0, 0.0], [28, 0.0, 2.0, 5.0, 6.0]], 2.0], [[[28, 29]], 41, 2]], [[[[25, 3.0, 0.5, 4.0, 1.5], [12, -1.0, 2.0, 1.5, 2.5], [39, 2.0, 1.0, 3.5, 2.0], [37, 1.5, 0.5, 4.0, 1.5], [8, -3.0, -1.0, -1.5, -1.0]], 1.0], [[[25, 37], [25, 39], [37, 39]], 21, 3]], [[[[35, 1.5, -0.5, 2.5, 1.5], [5, 1.0, -2.0, 2.5, -1.0], [31, 0.5, -3.0, 0.5, -1.5], [24, 3.0, -1.5, 3.5, 0.5]], 1.0], [[[5, 35]], 15, 2]], [[[[25, -6.0, 5.0, -6.0, 9.0], [28, 4.0, 3.0, 8.0, 3.0], [36, -2.0, 3.0, 2.0, 8.0], [29, 2.0, -5.0, 5.0, -1.0], [20, -2.0, 4.0, 3.0, 9.0], [12, -2.0, -3.0, 1.0, -3.0]], 1.0], [[[20, 36]], 100, 2]], [[[[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]]], [[[[[3, -4.0, -4.0, -2.0, -4.0], [32, 2.0, 0.0, 2.0, 3.0], [37, -4.0, 0.0, 1.0, 1.0], [15, -1.0, -2.0, 0.0, -2.0], [12, 6.0, -2.0, 7.0, 1.0], [39, -1.0, -5.0, 0.0, -2.0]], 3.0], [[[3, 39], [15, 39], [32, 37]], 15, 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]], [[[[33, 5.0, -4.0, 7.0, -4.0], [31, 2.0, 1.0, 3.0, 2.0], [37, 6.0, 5.0, 10.0, 5.0], [38, 3.0, -1.0, 6.0, 3.0]], 2.5], [[[31, 38]], 12, 2]], [[[[30, -1.0, 0.0, 1.0, 2.0], [17, 1.0, -3.0, 1.0, -3.0], [28, 2.0, 2.0, 2.0, 4.0], [11, -5.0, -3.0, -1.0, -2.0], [21, -5.0, -1.0, -2.0, 4.0]], 3.0], [[[11, 21], [21, 30], [28, 30]], 13, 2]], [[[[13, 5.0, -1.0, 7.0, 4.0], [17, 4.0, -6.0, 8.0, -3.0]], 1.0], [[], 38, 1]], [[[[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]], [[[[14, -0.5, 2.0, 0.0, 4.5], [12, 1.5, 1.0, 2.0, 3.5], [1, -1.5, 3.0, -0.5, 4.0], [21, -2.0, -2.0, -1.5, 0.0], [32, -0.5, -0.5, 1.0, -0.5], [39, 1.0, -2.5, 2.5, -0.5], [18, 1.0, 1.5, 2.5, 3.5]], 2.5], [[[1, 14], [12, 14], [12, 18], [14, 18], [14, 21], [21, 32], [32, 39]], 17, 3]]], [[[[[27, 5.0, -3.0, 6.0, 0.0], [1, 4.0, -4.0, 5.0, 0.0], [38, 6.0, 4.0, 10.0, 9.0], [34, -2.0, -2.0, -1.0, 1.0], [23, -1.0, -3.0, 0.0, -3.0], [10, -1.0, 6.0, 4.0, 11.0], [3, -4.0, 4.0, 0.0, 7.0], [20, 1.0, 0.0, 1.0, 3.0], [21, -6.0, -1.0, -4.0, -1.0]], 2.5], [[[1, 27], [3, 10], [3, 20]], 41, 2]], [[[[3, 2.0, 3.0, 3.5, 3.0], [6, 2.0, 1.0, 3.0, 1.0], [37, -1.5, -1.5, 0.0, 1.0], [19, 1.0, 1.0, 2.5, 2.0], [32, -1.5, -2.5, -1.5, -1.0], [26, 0.0, 0.5, 2.0, 2.0], [31, 1.0, 2.5, 2.5, 3.5]], 1.0], [[[3, 31], [6, 19], [6, 26], [19, 26], [19, 31], [26, 31], [26, 37], [32, 37]], 36, 3]], [[[[35, 2.5, 2.5, 4.5, 4.0], [13, 1.5, -3.0, 4.0, -2.5]], 3.0], [[], 6, 1]], [[[[5, -2.5, 2.5, -1.0, 5.0], [25, 0.5, 0.0, 1.0, 2.5], [22, 1.5, -2.0, 2.0, -1.0], [10, -1.5, -1.0, -1.0, 0.0]], 2.0], [[], 10, 1]], [[[[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]], [[[[36, -0.5, -2.0, 1.0, -0.5], [8, 3.0, 2.5, 4.0, 3.5]], 3.0], [[], 4, 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]], [[[[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]]], [[[[[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]], [[[[3, -6.0, -2.0, -5.0, 1.0], [13, -3.0, 3.0, 2.0, 5.0], [31, 4.0, 5.0, 8.0, 6.0], [33, 2.0, 1.0, 5.0, 1.0], [32, 3.0, 2.0, 8.0, 3.0]], 3.0], [[[31, 32], [32, 33]], 14, 2]], [[[[7, -2.5, 0.0, 0.0, 0.5], [30, -3.0, 0.5, -0.5, 3.0], [4, -2.5, -3.0, -0.5, -1.0], [8, 3.0, 3.0, 3.0, 4.0], [26, -0.5, -2.0, -0.5, -0.5], [28, -2.5, 2.5, 0.0, 3.5], [33, 0.5, -3.0, 1.0, -3.0], [24, 3.0, -0.5, 4.0, 2.0]], 2.5], [[[4, 26], [7, 30], [28, 30]], 15, 2]], [[[[13, -2.0, 0.0, 0.0, 1.5], [15, 2.0, -3.0, 3.5, -2.5]], 2.5], [[], 6, 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]], [[[[8, 3.0, -0.5, 5.0, 1.5], [38, -1.0, -2.0, -0.5, -1.0], [9, 2.5, 1.0, 3.5, 2.5], [6, 2.0, 0.0, 2.5, 2.0]], 2.5], [[[6, 8], [6, 9], [8, 9]], 9, 3]], [[[[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]], [[[[37, -1.5, 0.0, 0.0, 1.0], [20, 0.0, 0.0, 0.5, 2.5], [8, -2.0, 0.0, 0.5, 0.0]], 2.5], [[[8, 20], [8, 37], [20, 37]], 6, 3]]]]
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	`[[], 32, 1]`	`[[], 46, 1]`	Failed
case 1	`[[], 2, 1]`	`[[[6, 27], [6, 36], [22, 30]], 10, 2]`	Failed
case 2	`[[], 4, 1]`	`[[], 10, 1]`	Failed
case 3	`[[[31, 39]], 3, 2]`	`[[[31, 39]], 6, 2]`	Failed
case 4	`[[], 3, 1]`	`[[], 6, 1]`	Failed
case 5	`[[], 7, 1]`	`[[], 11, 1]`	Failed
case 6	`[[], 2, 1]`	`[[], 8, 1]`	Failed
case 7	`[[], 8, 1]`	`[[[6, 23], [19, 25]], 15, 2]`	Failed

SHA-256 / 1d02fc540d1fbc8899d5f2b631e3cf85549a15c97e09456bf5bbd5ee2d0306a2

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[2] / cs), math.floor(b[4] / cs)
        for i in range(i0, max(i1, i0 + 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 = [[[[[[7, 1.0, -3.0, 6.0, -3.0], [28, 1.0, 0.0, 1.0, 1.0], [26, 4.0, 1.0, 6.0, 6.0], [29, -5.0, 0.0, -2.0, 4.0]], 1.0], [[], 46, 1]], [[[[22, -1.0, 0.5, -0.5, 2.5], [36, 3.0, 1.5, 4.5, 3.5], [6, 0.5, 0.0, 3.0, 1.0], [30, -2.0, 1.5, -1.5, 3.0], [27, 0.5, 2.0, 0.5, 2.5], [8, -1.0, -0.5, 0.5, -0.5]], 3.0], [[[6, 27], [6, 36], [22, 30]], 10, 2]], [[[[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]], [[[[31, -1.5, 0.0, 0.5, 0.0], [39, -2.5, 1.5, 0.0, 3.5]], 3.0], [[[31, 39]], 6, 2]], [[[[28, 3.0, -0.5, 5.0, -0.5], [8, 0.5, 0.5, 2.5, 1.5], [17, -3.0, 1.0, -1.0, 1.5]], 2.5], [[], 6, 1]], [[[[30, 4.0, -2.0, 7.0, -1.0], [28, 6.0, 3.0, 11.0, 6.0]], 2.0], [[], 11, 1]], [[[[14, -2.5, 0.5, -2.5, 3.0], [38, 0.0, 2.0, 1.0, 3.0]], 1.0], [[], 8, 1]], [[[[25, 3.0, 4.0, 3.0, 4.0], [23, 3.0, 6.0, 8.0, 8.0], [6, 0.0, 5.0, 3.0, 5.0], [19, 3.0, 1.0, 6.0, 4.0], [4, -6.0, 1.0, -5.0, 2.0]], 2.5], [[[6, 23], [19, 25]], 15, 2]]], [[[[[23, 4.0, -2.0, 7.0, 1.0], [38, -5.0, 3.0, 0.0, 7.0], [24, -6.0, 1.0, -1.0, 2.0], [34, -3.0, -1.0, 1.0, 0.0], [35, 3.0, 0.0, 3.0, 4.0]], 1.0], [[], 73, 1]], [[[[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]], [[[[26, 1.0, -1.5, 3.0, -1.0], [11, -2.0, -1.5, -1.0, 1.0]], 2.5], [[], 4, 1]], [[[[29, 1.0, 4.0, 2.0, 6.0], [9, -5.0, 5.0, -1.0, 9.0], [12, 6.0, -1.0, 6.0, -1.0], [22, 4.0, -5.0, 8.0, -4.0], [21, -4.0, -5.0, 0.0, 0.0], [28, 0.0, 2.0, 5.0, 6.0]], 2.0], [[[28, 29]], 41, 2]], [[[[25, 3.0, 0.5, 4.0, 1.5], [12, -1.0, 2.0, 1.5, 2.5], [39, 2.0, 1.0, 3.5, 2.0], [37, 1.5, 0.5, 4.0, 1.5], [8, -3.0, -1.0, -1.5, -1.0]], 1.0], [[[25, 37], [25, 39], [37, 39]], 21, 3]], [[[[35, 1.5, -0.5, 2.5, 1.5], [5, 1.0, -2.0, 2.5, -1.0], [31, 0.5, -3.0, 0.5, -1.5], [24, 3.0, -1.5, 3.5, 0.5]], 1.0], [[[5, 35]], 15, 2]], [[[[25, -6.0, 5.0, -6.0, 9.0], [28, 4.0, 3.0, 8.0, 3.0], [36, -2.0, 3.0, 2.0, 8.0], [29, 2.0, -5.0, 5.0, -1.0], [20, -2.0, 4.0, 3.0, 9.0], [12, -2.0, -3.0, 1.0, -3.0]], 1.0], [[[20, 36]], 100, 2]], [[[[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]]], [[[[[3, -4.0, -4.0, -2.0, -4.0], [32, 2.0, 0.0, 2.0, 3.0], [37, -4.0, 0.0, 1.0, 1.0], [15, -1.0, -2.0, 0.0, -2.0], [12, 6.0, -2.0, 7.0, 1.0], [39, -1.0, -5.0, 0.0, -2.0]], 3.0], [[[3, 39], [15, 39], [32, 37]], 15, 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]], [[[[33, 5.0, -4.0, 7.0, -4.0], [31, 2.0, 1.0, 3.0, 2.0], [37, 6.0, 5.0, 10.0, 5.0], [38, 3.0, -1.0, 6.0, 3.0]], 2.5], [[[31, 38]], 12, 2]], [[[[30, -1.0, 0.0, 1.0, 2.0], [17, 1.0, -3.0, 1.0, -3.0], [28, 2.0, 2.0, 2.0, 4.0], [11, -5.0, -3.0, -1.0, -2.0], [21, -5.0, -1.0, -2.0, 4.0]], 3.0], [[[11, 21], [21, 30], [28, 30]], 13, 2]], [[[[13, 5.0, -1.0, 7.0, 4.0], [17, 4.0, -6.0, 8.0, -3.0]], 1.0], [[], 38, 1]], [[[[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]], [[[[14, -0.5, 2.0, 0.0, 4.5], [12, 1.5, 1.0, 2.0, 3.5], [1, -1.5, 3.0, -0.5, 4.0], [21, -2.0, -2.0, -1.5, 0.0], [32, -0.5, -0.5, 1.0, -0.5], [39, 1.0, -2.5, 2.5, -0.5], [18, 1.0, 1.5, 2.5, 3.5]], 2.5], [[[1, 14], [12, 14], [12, 18], [14, 18], [14, 21], [21, 32], [32, 39]], 17, 3]]], [[[[[27, 5.0, -3.0, 6.0, 0.0], [1, 4.0, -4.0, 5.0, 0.0], [38, 6.0, 4.0, 10.0, 9.0], [34, -2.0, -2.0, -1.0, 1.0], [23, -1.0, -3.0, 0.0, -3.0], [10, -1.0, 6.0, 4.0, 11.0], [3, -4.0, 4.0, 0.0, 7.0], [20, 1.0, 0.0, 1.0, 3.0], [21, -6.0, -1.0, -4.0, -1.0]], 2.5], [[[1, 27], [3, 10], [3, 20]], 41, 2]], [[[[3, 2.0, 3.0, 3.5, 3.0], [6, 2.0, 1.0, 3.0, 1.0], [37, -1.5, -1.5, 0.0, 1.0], [19, 1.0, 1.0, 2.5, 2.0], [32, -1.5, -2.5, -1.5, -1.0], [26, 0.0, 0.5, 2.0, 2.0], [31, 1.0, 2.5, 2.5, 3.5]], 1.0], [[[3, 31], [6, 19], [6, 26], [19, 26], [19, 31], [26, 31], [26, 37], [32, 37]], 36, 3]], [[[[35, 2.5, 2.5, 4.5, 4.0], [13, 1.5, -3.0, 4.0, -2.5]], 3.0], [[], 6, 1]], [[[[5, -2.5, 2.5, -1.0, 5.0], [25, 0.5, 0.0, 1.0, 2.5], [22, 1.5, -2.0, 2.0, -1.0], [10, -1.5, -1.0, -1.0, 0.0]], 2.0], [[], 10, 1]], [[[[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]], [[[[36, -0.5, -2.0, 1.0, -0.5], [8, 3.0, 2.5, 4.0, 3.5]], 3.0], [[], 4, 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]], [[[[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]]], [[[[[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]], [[[[3, -6.0, -2.0, -5.0, 1.0], [13, -3.0, 3.0, 2.0, 5.0], [31, 4.0, 5.0, 8.0, 6.0], [33, 2.0, 1.0, 5.0, 1.0], [32, 3.0, 2.0, 8.0, 3.0]], 3.0], [[[31, 32], [32, 33]], 14, 2]], [[[[7, -2.5, 0.0, 0.0, 0.5], [30, -3.0, 0.5, -0.5, 3.0], [4, -2.5, -3.0, -0.5, -1.0], [8, 3.0, 3.0, 3.0, 4.0], [26, -0.5, -2.0, -0.5, -0.5], [28, -2.5, 2.5, 0.0, 3.5], [33, 0.5, -3.0, 1.0, -3.0], [24, 3.0, -0.5, 4.0, 2.0]], 2.5], [[[4, 26], [7, 30], [28, 30]], 15, 2]], [[[[13, -2.0, 0.0, 0.0, 1.5], [15, 2.0, -3.0, 3.5, -2.5]], 2.5], [[], 6, 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]], [[[[8, 3.0, -0.5, 5.0, 1.5], [38, -1.0, -2.0, -0.5, -1.0], [9, 2.5, 1.0, 3.5, 2.5], [6, 2.0, 0.0, 2.5, 2.0]], 2.5], [[[6, 8], [6, 9], [8, 9]], 9, 3]], [[[[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]], [[[[37, -1.5, 0.0, 0.0, 1.0], [20, 0.0, 0.0, 0.5, 2.5], [8, -2.0, 0.0, 0.5, 0.0]], 2.5], [[[8, 20], [8, 37], [20, 37]], 6, 3]]]]
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	`[[], 34, 1]`	`[[], 46, 1]`	Failed
case 1	`[[[6, 27], [22, 30]], 8, 2]`	`[[[6, 27], [6, 36], [22, 30]], 10, 2]`	Failed
case 2	`[[], 8, 1]`	`[[], 10, 1]`	Failed
case 3	`[[[31, 39]], 3, 2]`	`[[[31, 39]], 6, 2]`	Failed
case 4	`[[], 3, 1]`	`[[], 6, 1]`	Failed
case 5	`[[], 7, 1]`	`[[], 11, 1]`	Failed
case 6	`[[], 6, 1]`	`[[], 8, 1]`	Failed
case 7	`[[[19, 25]], 9, 2]`	`[[[6, 23], [19, 25]], 15, 2]`	Failed

SHA-256 / 4382fede7604eb8825739565c3a0600b8800424266dce5450548090c959c4028

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

SHA-256 / 2b5d66037d475c7ef3e2ea91a488f1a28d8fe63dd863e380b972d3252a4d407f

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

Case digest / fca21886bcafb11afbd4d25c9423663fde5fe08e712346cf051b57b74dcd9ff7