FA-87776 / Collision detection broadphase / Open access

Box sets are sorted by id instead of minimum x · case 01

The running index skips boxes and pairs are lost.

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

ROOT CAUSE

Both lists use the default sort on ids.

VERIFIED REPAIR

Sort by (minx, id).

Unsuccessful approach: Sorting by max x breaks the start-point sweep too.

Case contract

solve(A, B): bipartite box pruning (dynamic set A vs static set B), boxes [id,minx,miny,maxx,maxy], closed intervals. Sort both by (minx,id). Pass 1: for each a, B boxes with minx in [a.minx, a.maxx]; pass 2: for each b, A boxes with minx in (b.minx, b.maxx]; y overlap required. Return sorted [a id, b id] pairs.

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(A, B):
    As = sorted(A)
    Bs = sorted(B)
    def yover(p, q):
        return p[2] <= q[4] and q[2] <= p[4]
    pairs = []
    j = 0
    for a in As:
        while j < len(Bs) and Bs[j][1] < a[1]:
            j += 1
        k = j
        while k < len(Bs) and Bs[k][1] <= a[3]:
            if yover(a, Bs[k]):
                pairs.append([a[0], Bs[k][0]])
            k += 1
    j2 = 0
    for b in Bs:
        while j2 < len(As) and As[j2][1] <= b[1]:
            j2 += 1
        k = j2
        while k < len(As) and As[k][1] <= b[3]:
            if yover(As[k], b):
                pairs.append([As[k][0], b[0]])
            k += 1
    pairs.sort()
    return pairs
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[[[[[39, 2.0, 0.0, 5.0, 2.0], [24, 3.0, -3.0, 4.0, -2.0]], [[9, 2.0, 2.0, 2.0, 3.0], [17, 3.0, 3.0, 5.0, 3.0]]], [[39, 9]]], [[[[21, 4.0, 0.0, 6.0, 3.0]], [[20, 4.0, 0.0, 4.0, 1.0], [19, -3.0, 1.0, -2.0, 1.0]]], [[21, 20]]], [[[[11, -3.0, 4.0, -1.0, 7.0], [26, -5.0, 5.0, -4.0, 8.0], [4, -3.0, -2.0, -1.0, 1.0], [34, -2.0, -2.0, -2.0, -1.0]], [[28, -3.0, -3.0, 3.0, 0.0], [5, 0.0, -3.0, 2.0, -1.0], [7, -2.0, 1.0, -2.0, 3.0]]], [[4, 7], [4, 28], [34, 28]]], [[[[9, 1.0, 0.0, 4.0, 0.0]], [[10, 1.0, 0.0, 1.0, 1.0], [35, -4.0, 4.0, -3.0, 4.0], [17, 0.0, 3.0, 3.0, 3.0], [14, -1.0, 3.0, 1.0, 4.0]]], [[9, 10]]], [[[[27, 3.0, 0.0, 5.0, 1.0], [3, -1.0, -4.0, 1.0, -2.0], [32, -2.0, -3.0, 1.0, -3.0], [5, -4.0, -2.0, -1.0, -1.0]], [[15, -5.0, -4.0, -2.0, -1.0], [34, -5.0, 5.0, -3.0, 5.0], [13, 4.0, -3.0, 7.0, -1.0]]], [[5, 15], [32, 15]]], [[[[5, 3.0, 3.0, 4.0, 4.0]], [[8, 3.0, -5.0, 3.0, -5.0]]], []], [[[[4, -5.0, -2.0, -5.0, -1.0], [36, 5.0, -4.0, 6.0, -3.0], [16, -3.0, -2.0, 0.0, 0.0]], [[39, -5.0, -2.0, -1.0, -1.0], [20, 0.0, 0.0, 3.0, 2.0], [26, -1.0, -5.0, -1.0, -4.0], [5, 2.0, 5.0, 2.0, 7.0]]], [[4, 39], [16, 20], [16, 39]]], [[[[15, -2.0, -1.0, -1.0, 2.0], [7, 2.0, -2.0, 2.0, 1.0]], [[20, -2.0, -5.0, 0.0, -3.0], [38, 1.0, -5.0, 1.0, -4.0]]], []]], [[[[[23, 1.0, 3.0, 1.0, 5.0], [15, 0.0, -5.0, 3.0, -4.0]], [[1, 1.0, 2.0, 1.0, 3.0], [35, 3.0, -3.0, 5.0, 0.0]]], [[23, 1]]], [[[[30, 3.0, -4.0, 5.0, -1.0]], [[2, 3.0, -2.0, 3.0, 1.0], [28, 5.0, -5.0, 5.0, -2.0], [22, 3.0, 3.0, 5.0, 6.0]]], [[30, 2], [30, 28]]], [[[[32, 2.0, 2.0, 5.0, 4.0], [15, -2.0, -3.0, -1.0, 0.0], [23, 4.0, -3.0, 4.0, -2.0], [14, 3.0, 3.0, 4.0, 5.0]], [[18, -2.0, -1.0, 1.0, 1.0], [20, 3.0, 1.0, 6.0, 1.0], [30, 1.0, -2.0, 4.0, 0.0], [35, 3.0, 4.0, 5.0, 4.0]]], [[14, 35], [15, 18], [23, 30], [32, 35]]], [[[[23, 0.0, -3.0, 1.0, -1.0]], [[9, 0.0, -1.0, 0.0, 0.0], [30, 4.0, 1.0, 4.0, 4.0], [27, -4.0, -3.0, -1.0, 0.0]]], [[23, 9]]], [[[[31, 1.0, 4.0, 1.0, 4.0], [3, -1.0, -3.0, 2.0, 0.0], [2, 2.0, -3.0, 2.0, -2.0]], [[29, 1.0, 4.0, 2.0, 7.0], [1, -4.0, 0.0, -1.0, 1.0], [18, 2.0, 1.0, 2.0, 1.0], [36, 0.0, 3.0, 2.0, 4.0]]], [[3, 1], [31, 29], [31, 36]]], [[[[31, -3.0, 2.0, -2.0, 4.0], [18, -3.0, 3.0, -3.0, 6.0], [11, -3.0, -4.0, 0.0, -3.0]], [[29, -3.0, 5.0, -2.0, 7.0], [30, 0.0, -3.0, 1.0, -3.0], [38, -3.0, 5.0, -3.0, 5.0]]], [[11, 30], [18, 29], [18, 38]]], [[[[23, -5.0, -4.0, -4.0, -2.0]], [[15, 4.0, 4.0, 6.0, 5.0], [8, 2.0, 2.0, 2.0, 4.0], [2, -3.0, -1.0, 0.0, -1.0]]], []], [[[[32, -4.0, -3.0, -2.0, -2.0], [22, 3.0, 3.0, 4.0, 6.0], [9, -4.0, 3.0, -4.0, 6.0]], [[1, 5.0, -4.0, 5.0, -1.0], [29, 3.0, 4.0, 5.0, 5.0], [37, -3.0, 1.0, -1.0, 1.0]]], [[22, 29]]]], [[[[[26, -1.0, 1.0, 0.0, 1.0]], [[15, 1.0, -1.0, 2.0, -1.0], [10, 4.0, 5.0, 7.0, 6.0], [34, -5.0, -1.0, -4.0, -1.0]]], []], [[[[14, 2.0, -1.0, 2.0, 2.0], [6, 2.0, 1.0, 3.0, 1.0], [9, 5.0, -4.0, 8.0, -2.0], [2, 0.0, -2.0, 1.0, -2.0]], [[20, 2.0, -3.0, 5.0, -2.0], [1, -5.0, -2.0, -4.0, 1.0], [34, 0.0, 1.0, 3.0, 1.0]]], [[6, 34], [9, 20], [14, 34]]], [[[[19, 3.0, 5.0, 4.0, 7.0]], [[8, 5.0, -5.0, 8.0, -5.0]]], []], [[[[1, -2.0, -2.0, 0.0, 1.0], [34, -2.0, 3.0, -2.0, 5.0], [17, 4.0, 0.0, 4.0, 3.0]], [[8, -2.0, 2.0, 1.0, 4.0], [36, -3.0, 5.0, -3.0, 7.0], [21, -1.0, -4.0, -1.0, -4.0]]], [[34, 8]]], [[[[37, -5.0, -2.0, -5.0, -1.0], [35, -3.0, 5.0, -2.0, 8.0], [10, -4.0, -1.0, -1.0, 0.0]], [[24, -5.0, -1.0, -2.0, 1.0], [19, 5.0, 3.0, 7.0, 4.0]]], [[10, 24], [37, 24]]], [[[[23, -2.0, -1.0, -2.0, 0.0], [39, 0.0, 0.0, 3.0, 0.0], [34, 3.0, -1.0, 3.0, -1.0]], [[7, 3.0, 4.0, 6.0, 5.0], [3, 0.0, 5.0, 3.0, 5.0], [1, -1.0, 0.0, 1.0, 0.0]]], [[39, 1]]], [[[[37, 5.0, -2.0, 5.0, -1.0], [13, -1.0, 0.0, 2.0, 1.0]], [[32, 5.0, -4.0, 5.0, -2.0], [9, 1.0, 1.0, 2.0, 4.0]]], [[13, 9], [37, 32]]], [[[[13, -5.0, 5.0, -4.0, 6.0], [36, 4.0, -5.0, 4.0, -3.0]], [[29, 4.0, -5.0, 7.0, -2.0], [34, -5.0, 4.0, -5.0, 7.0]]], [[13, 34], [36, 29]]]], [[[[[3, -5.0, -2.0, -4.0, 1.0], [32, -1.0, 0.0, 2.0, 0.0], [25, 4.0, -2.0, 7.0, 1.0]], [[6, 1.0, -1.0, 4.0, 2.0]]], [[25, 6], [32, 6]]], [[[[12, 4.0, 0.0, 6.0, 1.0], [37, -5.0, 1.0, -4.0, 2.0], [2, -2.0, -1.0, -1.0, 0.0], [38, -4.0, 2.0, -2.0, 4.0]], [[7, 4.0, 2.0, 6.0, 5.0]]], []], [[[[16, -2.0, -4.0, 1.0, -3.0], [25, 0.0, 1.0, 3.0, 1.0], [23, -2.0, -5.0, 0.0, -4.0], [33, 4.0, 5.0, 6.0, 8.0]], [[27, -2.0, 4.0, 0.0, 4.0], [14, 3.0, -1.0, 3.0, 2.0], [8, -4.0, -3.0, -4.0, -1.0], [37, 4.0, 2.0, 7.0, 4.0]]], [[25, 14]]], [[[[38, -1.0, 5.0, 0.0, 5.0], [31, 3.0, 0.0, 4.0, 0.0], [2, 2.0, -4.0, 3.0, -2.0], [6, -3.0, -1.0, -3.0, 0.0]], [[11, -1.0, 0.0, 5.0, 1.0], [24, 4.0, -5.0, 7.0, -4.0]]], [[31, 11]]], [[[[26, -4.0, -3.0, -2.0, -3.0]], [[28, -4.0, -4.0, 2.0, -2.0], [23, 5.0, -3.0, 8.0, 0.0]]], [[26, 28]]], [[[[21, 0.0, -2.0, 0.0, -1.0], [9, 4.0, -4.0, 5.0, -4.0]], [[13, 0.0, -1.0, 5.0, -1.0], [33, 2.0, 0.0, 3.0, 3.0], [28, -1.0, -3.0, -1.0, -2.0]]], [[21, 13]]], [[[[36, 4.0, -3.0, 4.0, 0.0], [6, -3.0, 1.0, -3.0, 1.0], [37, -3.0, -3.0, -1.0, -2.0]], [[33, 3.0, -2.0, 4.0, -2.0], [18, -1.0, 5.0, -1.0, 7.0], [25, -3.0, -1.0, -1.0, 1.0], [2, -3.0, 5.0, 0.0, 6.0]]], [[6, 25], [36, 33]]], [[[[28, -1.0, -5.0, 0.0, -4.0], [34, 5.0, 4.0, 7.0, 7.0], [14, 4.0, 4.0, 5.0, 6.0], [36, 0.0, -3.0, 2.0, -2.0]], [[7, -1.0, -4.0, -1.0, -3.0]]], [[28, 7]]]], [[[[[23, 1.0, 4.0, 3.0, 5.0], [4, 4.0, -4.0, 5.0, -3.0]], [[27, 5.0, -1.0, 7.0, 0.0], [18, -2.0, 2.0, 1.0, 4.0]]], [[23, 18]]], [[[[39, 4.0, 5.0, 7.0, 5.0], [32, 0.0, -4.0, 0.0, -2.0], [11, 5.0, 1.0, 5.0, 4.0]], [[28, 4.0, 3.0, 4.0, 5.0], [10, 0.0, 0.0, 0.0, 2.0], [13, 5.0, -3.0, 8.0, -2.0], [35, -3.0, -1.0, 0.0, 0.0]]], [[39, 28]]], [[[[16, -1.0, -4.0, 1.0, -1.0], [31, -5.0, -2.0, -5.0, -1.0]], [[6, -1.0, -4.0, 2.0, -4.0], [9, -2.0, -4.0, -2.0, -1.0], [8, -5.0, -5.0, -4.0, -3.0], [34, 5.0, 1.0, 8.0, 4.0]]], [[16, 6]]], [[[[36, -4.0, -1.0, -1.0, 2.0], [13, 5.0, 5.0, 7.0, 7.0], [30, -2.0, 4.0, 1.0, 4.0], [15, 2.0, 2.0, 2.0, 5.0]], [[22, -4.0, -1.0, 7.0, 2.0], [8, 3.0, 0.0, 6.0, 1.0], [9, 1.0, 2.0, 2.0, 3.0]]], [[15, 9], [15, 22], [36, 22]]], [[[[30, -4.0, 4.0, -3.0, 7.0], [7, -3.0, 1.0, -2.0, 1.0]], [[34, -3.0, 3.0, -2.0, 3.0], [9, 0.0, -3.0, 0.0, -2.0]]], []], [[[[38, -1.0, 5.0, 1.0, 6.0], [39, -2.0, -4.0, 1.0, -4.0], [9, 3.0, 0.0, 6.0, 0.0], [23, 1.0, 4.0, 2.0, 5.0]], [[16, 5.0, -5.0, 6.0, -3.0], [30, 4.0, -5.0, 6.0, -5.0], [6, 5.0, -5.0, 8.0, -3.0]]], []], [[[[37, -1.0, -2.0, 2.0, -2.0], [1, -2.0, -2.0, 1.0, 0.0], [23, 1.0, -5.0, 3.0, -5.0]], [[4, -1.0, 0.0, 7.0, 2.0], [28, 2.0, 1.0, 2.0, 2.0]]], [[1, 4]]], [[[[28, -5.0, 4.0, -5.0, 7.0], [9, -2.0, -1.0, 1.0, 2.0]], [[24, -5.0, 0.0, -4.0, 2.0], [25, 5.0, -2.0, 8.0, 0.0], [30, -2.0, 3.0, 0.0, 4.0]]], []]]]
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	`[]`	`[[39, 9]]`	Failed
case 1	`[[21, 20]]`	`[[21, 20]]`	Passed
case 2	`[]`	`[[4, 7], [4, 28], [34, 28]]`	Failed
case 3	`[[9, 10]]`	`[[9, 10]]`	Passed
case 4	`[]`	`[[5, 15], [32, 15]]`	Failed
case 5	`[]`	`[]`	Passed
case 6	`[]`	`[[4, 39], [16, 20], [16, 39]]`	Failed
case 7	`[]`	`[]`	Passed

SHA-256 / cf8f3686d6b89e1673d224d35e7d3057560cd1978a422d994e24fc1bc54afd16

2 / The unsuccessful fix

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(A, B):
    As = sorted(A, key=lambda r: (r[3], r[0]))
    Bs = sorted(B, key=lambda r: (r[3], r[0]))
    def yover(p, q):
        return p[2] <= q[4] and q[2] <= p[4]
    pairs = []
    j = 0
    for a in As:
        while j < len(Bs) and Bs[j][1] < a[1]:
            j += 1
        k = j
        while k < len(Bs) and Bs[k][1] <= a[3]:
            if yover(a, Bs[k]):
                pairs.append([a[0], Bs[k][0]])
            k += 1
    j2 = 0
    for b in Bs:
        while j2 < len(As) and As[j2][1] <= b[1]:
            j2 += 1
        k = j2
        while k < len(As) and As[k][1] <= b[3]:
            if yover(As[k], b):
                pairs.append([As[k][0], b[0]])
            k += 1
    pairs.sort()
    return pairs
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[[[[[39, 2.0, 0.0, 5.0, 2.0], [24, 3.0, -3.0, 4.0, -2.0]], [[9, 2.0, 2.0, 2.0, 3.0], [17, 3.0, 3.0, 5.0, 3.0]]], [[39, 9]]], [[[[21, 4.0, 0.0, 6.0, 3.0]], [[20, 4.0, 0.0, 4.0, 1.0], [19, -3.0, 1.0, -2.0, 1.0]]], [[21, 20]]], [[[[11, -3.0, 4.0, -1.0, 7.0], [26, -5.0, 5.0, -4.0, 8.0], [4, -3.0, -2.0, -1.0, 1.0], [34, -2.0, -2.0, -2.0, -1.0]], [[28, -3.0, -3.0, 3.0, 0.0], [5, 0.0, -3.0, 2.0, -1.0], [7, -2.0, 1.0, -2.0, 3.0]]], [[4, 7], [4, 28], [34, 28]]], [[[[9, 1.0, 0.0, 4.0, 0.0]], [[10, 1.0, 0.0, 1.0, 1.0], [35, -4.0, 4.0, -3.0, 4.0], [17, 0.0, 3.0, 3.0, 3.0], [14, -1.0, 3.0, 1.0, 4.0]]], [[9, 10]]], [[[[27, 3.0, 0.0, 5.0, 1.0], [3, -1.0, -4.0, 1.0, -2.0], [32, -2.0, -3.0, 1.0, -3.0], [5, -4.0, -2.0, -1.0, -1.0]], [[15, -5.0, -4.0, -2.0, -1.0], [34, -5.0, 5.0, -3.0, 5.0], [13, 4.0, -3.0, 7.0, -1.0]]], [[5, 15], [32, 15]]], [[[[5, 3.0, 3.0, 4.0, 4.0]], [[8, 3.0, -5.0, 3.0, -5.0]]], []], [[[[4, -5.0, -2.0, -5.0, -1.0], [36, 5.0, -4.0, 6.0, -3.0], [16, -3.0, -2.0, 0.0, 0.0]], [[39, -5.0, -2.0, -1.0, -1.0], [20, 0.0, 0.0, 3.0, 2.0], [26, -1.0, -5.0, -1.0, -4.0], [5, 2.0, 5.0, 2.0, 7.0]]], [[4, 39], [16, 20], [16, 39]]], [[[[15, -2.0, -1.0, -1.0, 2.0], [7, 2.0, -2.0, 2.0, 1.0]], [[20, -2.0, -5.0, 0.0, -3.0], [38, 1.0, -5.0, 1.0, -4.0]]], []]], [[[[[23, 1.0, 3.0, 1.0, 5.0], [15, 0.0, -5.0, 3.0, -4.0]], [[1, 1.0, 2.0, 1.0, 3.0], [35, 3.0, -3.0, 5.0, 0.0]]], [[23, 1]]], [[[[30, 3.0, -4.0, 5.0, -1.0]], [[2, 3.0, -2.0, 3.0, 1.0], [28, 5.0, -5.0, 5.0, -2.0], [22, 3.0, 3.0, 5.0, 6.0]]], [[30, 2], [30, 28]]], [[[[32, 2.0, 2.0, 5.0, 4.0], [15, -2.0, -3.0, -1.0, 0.0], [23, 4.0, -3.0, 4.0, -2.0], [14, 3.0, 3.0, 4.0, 5.0]], [[18, -2.0, -1.0, 1.0, 1.0], [20, 3.0, 1.0, 6.0, 1.0], [30, 1.0, -2.0, 4.0, 0.0], [35, 3.0, 4.0, 5.0, 4.0]]], [[14, 35], [15, 18], [23, 30], [32, 35]]], [[[[23, 0.0, -3.0, 1.0, -1.0]], [[9, 0.0, -1.0, 0.0, 0.0], [30, 4.0, 1.0, 4.0, 4.0], [27, -4.0, -3.0, -1.0, 0.0]]], [[23, 9]]], [[[[31, 1.0, 4.0, 1.0, 4.0], [3, -1.0, -3.0, 2.0, 0.0], [2, 2.0, -3.0, 2.0, -2.0]], [[29, 1.0, 4.0, 2.0, 7.0], [1, -4.0, 0.0, -1.0, 1.0], [18, 2.0, 1.0, 2.0, 1.0], [36, 0.0, 3.0, 2.0, 4.0]]], [[3, 1], [31, 29], [31, 36]]], [[[[31, -3.0, 2.0, -2.0, 4.0], [18, -3.0, 3.0, -3.0, 6.0], [11, -3.0, -4.0, 0.0, -3.0]], [[29, -3.0, 5.0, -2.0, 7.0], [30, 0.0, -3.0, 1.0, -3.0], [38, -3.0, 5.0, -3.0, 5.0]]], [[11, 30], [18, 29], [18, 38]]], [[[[23, -5.0, -4.0, -4.0, -2.0]], [[15, 4.0, 4.0, 6.0, 5.0], [8, 2.0, 2.0, 2.0, 4.0], [2, -3.0, -1.0, 0.0, -1.0]]], []], [[[[32, -4.0, -3.0, -2.0, -2.0], [22, 3.0, 3.0, 4.0, 6.0], [9, -4.0, 3.0, -4.0, 6.0]], [[1, 5.0, -4.0, 5.0, -1.0], [29, 3.0, 4.0, 5.0, 5.0], [37, -3.0, 1.0, -1.0, 1.0]]], [[22, 29]]]], [[[[[26, -1.0, 1.0, 0.0, 1.0]], [[15, 1.0, -1.0, 2.0, -1.0], [10, 4.0, 5.0, 7.0, 6.0], [34, -5.0, -1.0, -4.0, -1.0]]], []], [[[[14, 2.0, -1.0, 2.0, 2.0], [6, 2.0, 1.0, 3.0, 1.0], [9, 5.0, -4.0, 8.0, -2.0], [2, 0.0, -2.0, 1.0, -2.0]], [[20, 2.0, -3.0, 5.0, -2.0], [1, -5.0, -2.0, -4.0, 1.0], [34, 0.0, 1.0, 3.0, 1.0]]], [[6, 34], [9, 20], [14, 34]]], [[[[19, 3.0, 5.0, 4.0, 7.0]], [[8, 5.0, -5.0, 8.0, -5.0]]], []], [[[[1, -2.0, -2.0, 0.0, 1.0], [34, -2.0, 3.0, -2.0, 5.0], [17, 4.0, 0.0, 4.0, 3.0]], [[8, -2.0, 2.0, 1.0, 4.0], [36, -3.0, 5.0, -3.0, 7.0], [21, -1.0, -4.0, -1.0, -4.0]]], [[34, 8]]], [[[[37, -5.0, -2.0, -5.0, -1.0], [35, -3.0, 5.0, -2.0, 8.0], [10, -4.0, -1.0, -1.0, 0.0]], [[24, -5.0, -1.0, -2.0, 1.0], [19, 5.0, 3.0, 7.0, 4.0]]], [[10, 24], [37, 24]]], [[[[23, -2.0, -1.0, -2.0, 0.0], [39, 0.0, 0.0, 3.0, 0.0], [34, 3.0, -1.0, 3.0, -1.0]], [[7, 3.0, 4.0, 6.0, 5.0], [3, 0.0, 5.0, 3.0, 5.0], [1, -1.0, 0.0, 1.0, 0.0]]], [[39, 1]]], [[[[37, 5.0, -2.0, 5.0, -1.0], [13, -1.0, 0.0, 2.0, 1.0]], [[32, 5.0, -4.0, 5.0, -2.0], [9, 1.0, 1.0, 2.0, 4.0]]], [[13, 9], [37, 32]]], [[[[13, -5.0, 5.0, -4.0, 6.0], [36, 4.0, -5.0, 4.0, -3.0]], [[29, 4.0, -5.0, 7.0, -2.0], [34, -5.0, 4.0, -5.0, 7.0]]], [[13, 34], [36, 29]]]], [[[[[3, -5.0, -2.0, -4.0, 1.0], [32, -1.0, 0.0, 2.0, 0.0], [25, 4.0, -2.0, 7.0, 1.0]], [[6, 1.0, -1.0, 4.0, 2.0]]], [[25, 6], [32, 6]]], [[[[12, 4.0, 0.0, 6.0, 1.0], [37, -5.0, 1.0, -4.0, 2.0], [2, -2.0, -1.0, -1.0, 0.0], [38, -4.0, 2.0, -2.0, 4.0]], [[7, 4.0, 2.0, 6.0, 5.0]]], []], [[[[16, -2.0, -4.0, 1.0, -3.0], [25, 0.0, 1.0, 3.0, 1.0], [23, -2.0, -5.0, 0.0, -4.0], [33, 4.0, 5.0, 6.0, 8.0]], [[27, -2.0, 4.0, 0.0, 4.0], [14, 3.0, -1.0, 3.0, 2.0], [8, -4.0, -3.0, -4.0, -1.0], [37, 4.0, 2.0, 7.0, 4.0]]], [[25, 14]]], [[[[38, -1.0, 5.0, 0.0, 5.0], [31, 3.0, 0.0, 4.0, 0.0], [2, 2.0, -4.0, 3.0, -2.0], [6, -3.0, -1.0, -3.0, 0.0]], [[11, -1.0, 0.0, 5.0, 1.0], [24, 4.0, -5.0, 7.0, -4.0]]], [[31, 11]]], [[[[26, -4.0, -3.0, -2.0, -3.0]], [[28, -4.0, -4.0, 2.0, -2.0], [23, 5.0, -3.0, 8.0, 0.0]]], [[26, 28]]], [[[[21, 0.0, -2.0, 0.0, -1.0], [9, 4.0, -4.0, 5.0, -4.0]], [[13, 0.0, -1.0, 5.0, -1.0], [33, 2.0, 0.0, 3.0, 3.0], [28, -1.0, -3.0, -1.0, -2.0]]], [[21, 13]]], [[[[36, 4.0, -3.0, 4.0, 0.0], [6, -3.0, 1.0, -3.0, 1.0], [37, -3.0, -3.0, -1.0, -2.0]], [[33, 3.0, -2.0, 4.0, -2.0], [18, -1.0, 5.0, -1.0, 7.0], [25, -3.0, -1.0, -1.0, 1.0], [2, -3.0, 5.0, 0.0, 6.0]]], [[6, 25], [36, 33]]], [[[[28, -1.0, -5.0, 0.0, -4.0], [34, 5.0, 4.0, 7.0, 7.0], [14, 4.0, 4.0, 5.0, 6.0], [36, 0.0, -3.0, 2.0, -2.0]], [[7, -1.0, -4.0, -1.0, -3.0]]], [[28, 7]]]], [[[[[23, 1.0, 4.0, 3.0, 5.0], [4, 4.0, -4.0, 5.0, -3.0]], [[27, 5.0, -1.0, 7.0, 0.0], [18, -2.0, 2.0, 1.0, 4.0]]], [[23, 18]]], [[[[39, 4.0, 5.0, 7.0, 5.0], [32, 0.0, -4.0, 0.0, -2.0], [11, 5.0, 1.0, 5.0, 4.0]], [[28, 4.0, 3.0, 4.0, 5.0], [10, 0.0, 0.0, 0.0, 2.0], [13, 5.0, -3.0, 8.0, -2.0], [35, -3.0, -1.0, 0.0, 0.0]]], [[39, 28]]], [[[[16, -1.0, -4.0, 1.0, -1.0], [31, -5.0, -2.0, -5.0, -1.0]], [[6, -1.0, -4.0, 2.0, -4.0], [9, -2.0, -4.0, -2.0, -1.0], [8, -5.0, -5.0, -4.0, -3.0], [34, 5.0, 1.0, 8.0, 4.0]]], [[16, 6]]], [[[[36, -4.0, -1.0, -1.0, 2.0], [13, 5.0, 5.0, 7.0, 7.0], [30, -2.0, 4.0, 1.0, 4.0], [15, 2.0, 2.0, 2.0, 5.0]], [[22, -4.0, -1.0, 7.0, 2.0], [8, 3.0, 0.0, 6.0, 1.0], [9, 1.0, 2.0, 2.0, 3.0]]], [[15, 9], [15, 22], [36, 22]]], [[[[30, -4.0, 4.0, -3.0, 7.0], [7, -3.0, 1.0, -2.0, 1.0]], [[34, -3.0, 3.0, -2.0, 3.0], [9, 0.0, -3.0, 0.0, -2.0]]], []], [[[[38, -1.0, 5.0, 1.0, 6.0], [39, -2.0, -4.0, 1.0, -4.0], [9, 3.0, 0.0, 6.0, 0.0], [23, 1.0, 4.0, 2.0, 5.0]], [[16, 5.0, -5.0, 6.0, -3.0], [30, 4.0, -5.0, 6.0, -5.0], [6, 5.0, -5.0, 8.0, -3.0]]], []], [[[[37, -1.0, -2.0, 2.0, -2.0], [1, -2.0, -2.0, 1.0, 0.0], [23, 1.0, -5.0, 3.0, -5.0]], [[4, -1.0, 0.0, 7.0, 2.0], [28, 2.0, 1.0, 2.0, 2.0]]], [[1, 4]]], [[[[28, -5.0, 4.0, -5.0, 7.0], [9, -2.0, -1.0, 1.0, 2.0]], [[24, -5.0, 0.0, -4.0, 2.0], [25, 5.0, -2.0, 8.0, 0.0], [30, -2.0, 3.0, 0.0, 4.0]]], []]]]
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	`[]`	`[[39, 9]]`	Failed
case 1	`[[21, 20]]`	`[[21, 20]]`	Passed
case 2	`[[4, 7]]`	`[[4, 7], [4, 28], [34, 28]]`	Failed
case 3	`[[9, 10]]`	`[[9, 10]]`	Passed
case 4	`[[5, 15]]`	`[[5, 15], [32, 15]]`	Failed
case 5	`[]`	`[]`	Passed
case 6	`[[16, 39]]`	`[[4, 39], [16, 20], [16, 39]]`	Failed
case 7	`[]`	`[]`	Passed

SHA-256 / 0f4fb8c703d0fddc062f639405e12194d58bf71e00bdaf45413c15ce2a8223ff

3 / The verified repair

Exit 0

"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(A, B):
    As = sorted(A, key=lambda r: (r[1], r[0]))
    Bs = sorted(B, key=lambda r: (r[1], r[0]))
    def yover(p, q):
        return p[2] <= q[4] and q[2] <= p[4]
    pairs = []
    j = 0
    for a in As:
        while j < len(Bs) and Bs[j][1] < a[1]:
            j += 1
        k = j
        while k < len(Bs) and Bs[k][1] <= a[3]:
            if yover(a, Bs[k]):
                pairs.append([a[0], Bs[k][0]])
            k += 1
    j2 = 0
    for b in Bs:
        while j2 < len(As) and As[j2][1] <= b[1]:
            j2 += 1
        k = j2
        while k < len(As) and As[k][1] <= b[3]:
            if yover(As[k], b):
                pairs.append([As[k][0], b[0]])
            k += 1
    pairs.sort()
    return pairs
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[[[[[39, 2.0, 0.0, 5.0, 2.0], [24, 3.0, -3.0, 4.0, -2.0]], [[9, 2.0, 2.0, 2.0, 3.0], [17, 3.0, 3.0, 5.0, 3.0]]], [[39, 9]]], [[[[21, 4.0, 0.0, 6.0, 3.0]], [[20, 4.0, 0.0, 4.0, 1.0], [19, -3.0, 1.0, -2.0, 1.0]]], [[21, 20]]], [[[[11, -3.0, 4.0, -1.0, 7.0], [26, -5.0, 5.0, -4.0, 8.0], [4, -3.0, -2.0, -1.0, 1.0], [34, -2.0, -2.0, -2.0, -1.0]], [[28, -3.0, -3.0, 3.0, 0.0], [5, 0.0, -3.0, 2.0, -1.0], [7, -2.0, 1.0, -2.0, 3.0]]], [[4, 7], [4, 28], [34, 28]]], [[[[9, 1.0, 0.0, 4.0, 0.0]], [[10, 1.0, 0.0, 1.0, 1.0], [35, -4.0, 4.0, -3.0, 4.0], [17, 0.0, 3.0, 3.0, 3.0], [14, -1.0, 3.0, 1.0, 4.0]]], [[9, 10]]], [[[[27, 3.0, 0.0, 5.0, 1.0], [3, -1.0, -4.0, 1.0, -2.0], [32, -2.0, -3.0, 1.0, -3.0], [5, -4.0, -2.0, -1.0, -1.0]], [[15, -5.0, -4.0, -2.0, -1.0], [34, -5.0, 5.0, -3.0, 5.0], [13, 4.0, -3.0, 7.0, -1.0]]], [[5, 15], [32, 15]]], [[[[5, 3.0, 3.0, 4.0, 4.0]], [[8, 3.0, -5.0, 3.0, -5.0]]], []], [[[[4, -5.0, -2.0, -5.0, -1.0], [36, 5.0, -4.0, 6.0, -3.0], [16, -3.0, -2.0, 0.0, 0.0]], [[39, -5.0, -2.0, -1.0, -1.0], [20, 0.0, 0.0, 3.0, 2.0], [26, -1.0, -5.0, -1.0, -4.0], [5, 2.0, 5.0, 2.0, 7.0]]], [[4, 39], [16, 20], [16, 39]]], [[[[15, -2.0, -1.0, -1.0, 2.0], [7, 2.0, -2.0, 2.0, 1.0]], [[20, -2.0, -5.0, 0.0, -3.0], [38, 1.0, -5.0, 1.0, -4.0]]], []]], [[[[[23, 1.0, 3.0, 1.0, 5.0], [15, 0.0, -5.0, 3.0, -4.0]], [[1, 1.0, 2.0, 1.0, 3.0], [35, 3.0, -3.0, 5.0, 0.0]]], [[23, 1]]], [[[[30, 3.0, -4.0, 5.0, -1.0]], [[2, 3.0, -2.0, 3.0, 1.0], [28, 5.0, -5.0, 5.0, -2.0], [22, 3.0, 3.0, 5.0, 6.0]]], [[30, 2], [30, 28]]], [[[[32, 2.0, 2.0, 5.0, 4.0], [15, -2.0, -3.0, -1.0, 0.0], [23, 4.0, -3.0, 4.0, -2.0], [14, 3.0, 3.0, 4.0, 5.0]], [[18, -2.0, -1.0, 1.0, 1.0], [20, 3.0, 1.0, 6.0, 1.0], [30, 1.0, -2.0, 4.0, 0.0], [35, 3.0, 4.0, 5.0, 4.0]]], [[14, 35], [15, 18], [23, 30], [32, 35]]], [[[[23, 0.0, -3.0, 1.0, -1.0]], [[9, 0.0, -1.0, 0.0, 0.0], [30, 4.0, 1.0, 4.0, 4.0], [27, -4.0, -3.0, -1.0, 0.0]]], [[23, 9]]], [[[[31, 1.0, 4.0, 1.0, 4.0], [3, -1.0, -3.0, 2.0, 0.0], [2, 2.0, -3.0, 2.0, -2.0]], [[29, 1.0, 4.0, 2.0, 7.0], [1, -4.0, 0.0, -1.0, 1.0], [18, 2.0, 1.0, 2.0, 1.0], [36, 0.0, 3.0, 2.0, 4.0]]], [[3, 1], [31, 29], [31, 36]]], [[[[31, -3.0, 2.0, -2.0, 4.0], [18, -3.0, 3.0, -3.0, 6.0], [11, -3.0, -4.0, 0.0, -3.0]], [[29, -3.0, 5.0, -2.0, 7.0], [30, 0.0, -3.0, 1.0, -3.0], [38, -3.0, 5.0, -3.0, 5.0]]], [[11, 30], [18, 29], [18, 38]]], [[[[23, -5.0, -4.0, -4.0, -2.0]], [[15, 4.0, 4.0, 6.0, 5.0], [8, 2.0, 2.0, 2.0, 4.0], [2, -3.0, -1.0, 0.0, -1.0]]], []], [[[[32, -4.0, -3.0, -2.0, -2.0], [22, 3.0, 3.0, 4.0, 6.0], [9, -4.0, 3.0, -4.0, 6.0]], [[1, 5.0, -4.0, 5.0, -1.0], [29, 3.0, 4.0, 5.0, 5.0], [37, -3.0, 1.0, -1.0, 1.0]]], [[22, 29]]]], [[[[[26, -1.0, 1.0, 0.0, 1.0]], [[15, 1.0, -1.0, 2.0, -1.0], [10, 4.0, 5.0, 7.0, 6.0], [34, -5.0, -1.0, -4.0, -1.0]]], []], [[[[14, 2.0, -1.0, 2.0, 2.0], [6, 2.0, 1.0, 3.0, 1.0], [9, 5.0, -4.0, 8.0, -2.0], [2, 0.0, -2.0, 1.0, -2.0]], [[20, 2.0, -3.0, 5.0, -2.0], [1, -5.0, -2.0, -4.0, 1.0], [34, 0.0, 1.0, 3.0, 1.0]]], [[6, 34], [9, 20], [14, 34]]], [[[[19, 3.0, 5.0, 4.0, 7.0]], [[8, 5.0, -5.0, 8.0, -5.0]]], []], [[[[1, -2.0, -2.0, 0.0, 1.0], [34, -2.0, 3.0, -2.0, 5.0], [17, 4.0, 0.0, 4.0, 3.0]], [[8, -2.0, 2.0, 1.0, 4.0], [36, -3.0, 5.0, -3.0, 7.0], [21, -1.0, -4.0, -1.0, -4.0]]], [[34, 8]]], [[[[37, -5.0, -2.0, -5.0, -1.0], [35, -3.0, 5.0, -2.0, 8.0], [10, -4.0, -1.0, -1.0, 0.0]], [[24, -5.0, -1.0, -2.0, 1.0], [19, 5.0, 3.0, 7.0, 4.0]]], [[10, 24], [37, 24]]], [[[[23, -2.0, -1.0, -2.0, 0.0], [39, 0.0, 0.0, 3.0, 0.0], [34, 3.0, -1.0, 3.0, -1.0]], [[7, 3.0, 4.0, 6.0, 5.0], [3, 0.0, 5.0, 3.0, 5.0], [1, -1.0, 0.0, 1.0, 0.0]]], [[39, 1]]], [[[[37, 5.0, -2.0, 5.0, -1.0], [13, -1.0, 0.0, 2.0, 1.0]], [[32, 5.0, -4.0, 5.0, -2.0], [9, 1.0, 1.0, 2.0, 4.0]]], [[13, 9], [37, 32]]], [[[[13, -5.0, 5.0, -4.0, 6.0], [36, 4.0, -5.0, 4.0, -3.0]], [[29, 4.0, -5.0, 7.0, -2.0], [34, -5.0, 4.0, -5.0, 7.0]]], [[13, 34], [36, 29]]]], [[[[[3, -5.0, -2.0, -4.0, 1.0], [32, -1.0, 0.0, 2.0, 0.0], [25, 4.0, -2.0, 7.0, 1.0]], [[6, 1.0, -1.0, 4.0, 2.0]]], [[25, 6], [32, 6]]], [[[[12, 4.0, 0.0, 6.0, 1.0], [37, -5.0, 1.0, -4.0, 2.0], [2, -2.0, -1.0, -1.0, 0.0], [38, -4.0, 2.0, -2.0, 4.0]], [[7, 4.0, 2.0, 6.0, 5.0]]], []], [[[[16, -2.0, -4.0, 1.0, -3.0], [25, 0.0, 1.0, 3.0, 1.0], [23, -2.0, -5.0, 0.0, -4.0], [33, 4.0, 5.0, 6.0, 8.0]], [[27, -2.0, 4.0, 0.0, 4.0], [14, 3.0, -1.0, 3.0, 2.0], [8, -4.0, -3.0, -4.0, -1.0], [37, 4.0, 2.0, 7.0, 4.0]]], [[25, 14]]], [[[[38, -1.0, 5.0, 0.0, 5.0], [31, 3.0, 0.0, 4.0, 0.0], [2, 2.0, -4.0, 3.0, -2.0], [6, -3.0, -1.0, -3.0, 0.0]], [[11, -1.0, 0.0, 5.0, 1.0], [24, 4.0, -5.0, 7.0, -4.0]]], [[31, 11]]], [[[[26, -4.0, -3.0, -2.0, -3.0]], [[28, -4.0, -4.0, 2.0, -2.0], [23, 5.0, -3.0, 8.0, 0.0]]], [[26, 28]]], [[[[21, 0.0, -2.0, 0.0, -1.0], [9, 4.0, -4.0, 5.0, -4.0]], [[13, 0.0, -1.0, 5.0, -1.0], [33, 2.0, 0.0, 3.0, 3.0], [28, -1.0, -3.0, -1.0, -2.0]]], [[21, 13]]], [[[[36, 4.0, -3.0, 4.0, 0.0], [6, -3.0, 1.0, -3.0, 1.0], [37, -3.0, -3.0, -1.0, -2.0]], [[33, 3.0, -2.0, 4.0, -2.0], [18, -1.0, 5.0, -1.0, 7.0], [25, -3.0, -1.0, -1.0, 1.0], [2, -3.0, 5.0, 0.0, 6.0]]], [[6, 25], [36, 33]]], [[[[28, -1.0, -5.0, 0.0, -4.0], [34, 5.0, 4.0, 7.0, 7.0], [14, 4.0, 4.0, 5.0, 6.0], [36, 0.0, -3.0, 2.0, -2.0]], [[7, -1.0, -4.0, -1.0, -3.0]]], [[28, 7]]]], [[[[[23, 1.0, 4.0, 3.0, 5.0], [4, 4.0, -4.0, 5.0, -3.0]], [[27, 5.0, -1.0, 7.0, 0.0], [18, -2.0, 2.0, 1.0, 4.0]]], [[23, 18]]], [[[[39, 4.0, 5.0, 7.0, 5.0], [32, 0.0, -4.0, 0.0, -2.0], [11, 5.0, 1.0, 5.0, 4.0]], [[28, 4.0, 3.0, 4.0, 5.0], [10, 0.0, 0.0, 0.0, 2.0], [13, 5.0, -3.0, 8.0, -2.0], [35, -3.0, -1.0, 0.0, 0.0]]], [[39, 28]]], [[[[16, -1.0, -4.0, 1.0, -1.0], [31, -5.0, -2.0, -5.0, -1.0]], [[6, -1.0, -4.0, 2.0, -4.0], [9, -2.0, -4.0, -2.0, -1.0], [8, -5.0, -5.0, -4.0, -3.0], [34, 5.0, 1.0, 8.0, 4.0]]], [[16, 6]]], [[[[36, -4.0, -1.0, -1.0, 2.0], [13, 5.0, 5.0, 7.0, 7.0], [30, -2.0, 4.0, 1.0, 4.0], [15, 2.0, 2.0, 2.0, 5.0]], [[22, -4.0, -1.0, 7.0, 2.0], [8, 3.0, 0.0, 6.0, 1.0], [9, 1.0, 2.0, 2.0, 3.0]]], [[15, 9], [15, 22], [36, 22]]], [[[[30, -4.0, 4.0, -3.0, 7.0], [7, -3.0, 1.0, -2.0, 1.0]], [[34, -3.0, 3.0, -2.0, 3.0], [9, 0.0, -3.0, 0.0, -2.0]]], []], [[[[38, -1.0, 5.0, 1.0, 6.0], [39, -2.0, -4.0, 1.0, -4.0], [9, 3.0, 0.0, 6.0, 0.0], [23, 1.0, 4.0, 2.0, 5.0]], [[16, 5.0, -5.0, 6.0, -3.0], [30, 4.0, -5.0, 6.0, -5.0], [6, 5.0, -5.0, 8.0, -3.0]]], []], [[[[37, -1.0, -2.0, 2.0, -2.0], [1, -2.0, -2.0, 1.0, 0.0], [23, 1.0, -5.0, 3.0, -5.0]], [[4, -1.0, 0.0, 7.0, 2.0], [28, 2.0, 1.0, 2.0, 2.0]]], [[1, 4]]], [[[[28, -5.0, 4.0, -5.0, 7.0], [9, -2.0, -1.0, 1.0, 2.0]], [[24, -5.0, 0.0, -4.0, 2.0], [25, 5.0, -2.0, 8.0, 0.0], [30, -2.0, 3.0, 0.0, 4.0]]], []]]]
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	`[[39, 9]]`	`[[39, 9]]`	Passed
case 1	`[[21, 20]]`	`[[21, 20]]`	Passed
case 2	`[[4, 7], [4, 28], [34, 28]]`	`[[4, 7], [4, 28], [34, 28]]`	Passed
case 3	`[[9, 10]]`	`[[9, 10]]`	Passed
case 4	`[[5, 15], [32, 15]]`	`[[5, 15], [32, 15]]`	Passed
case 5	`[]`	`[]`	Passed
case 6	`[[4, 39], [16, 20], [16, 39]]`	`[[4, 39], [16, 20], [16, 39]]`	Passed
case 7	`[]`	`[]`	Passed

SHA-256 / 4b302e517def3eeef5bf06317fd6615c72466179b8bd6851c84efccc32e7c336

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

Case digest / fc9eeaadc1e6bb7f3ab29cd599fd7a3ad388a1f5878c354895d7758a4b8fcbbc