FA-87496 / Collision detection broadphase / Open access

Splitting a node does not push existing objects down · case 01

Objects inserted before the split remain in the parent and appear in unrelated queries.

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

ROOT CAUSE

The split creates children but never re-inserts the node's current objects.

VERIFIED REPAIR

Re-insert every object held by the node when it splits.

Unsuccessful approach: Re-inserting only the newest object leaves the older ones stuck in the parent.

Case contract

solve(objs, cap, max_depth, q): quadtree over [0,16]^2. Insert [id,minx,miny,maxx,maxy] in order. A node splits when it holds more than cap objects and depth<max_depth; children are ordered cy*2+cx. An object goes to a child only if it fits entirely: maxx<mid -> left, minx>=mid -> right (same for y); straddlers stay. On split all node objects are re-inserted. Query returns [sorted ids of objects in nodes whose closed bounds overlap q, total node count, max depth].

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(objs, cap, max_depth, q):
    def make(x, y, s, d):
        return {'x': x, 'y': y, 's': s, 'd': d, 'objs': [], 'kids': None}
    def child_index(n, o):
        h = n['s'] / 2
        mx, my = n['x'] + h, n['y'] + h
        if o[3] < mx:
            cx = 0
        elif o[1] >= mx:
            cx = 1
        else:
            return -1
        if o[4] < my:
            cy = 0
        elif o[2] >= my:
            cy = 1
        else:
            return -1
        return cy * 2 + cx
    def split(n):
        h = n['s'] / 2
        n['kids'] = [make(n['x'] + (k % 2) * h, n['y'] + (k // 2) * h, h, n['d'] + 1) for k in range(4)]
    def insert(n, o):
        if n['kids'] is not None:
            k = child_index(n, o)
            if k >= 0:
                insert(n['kids'][k], o)
                return
        n['objs'].append(o)
        if n['kids'] is None and len(n['objs']) > cap and n['d'] < max_depth:
            split(n)
    root = make(0, 0, 16, 0)
    for o in objs:
        insert(root, o)
    found, count, deep = [], 0, 0
    stack = [root]
    while stack:
        n = stack.pop()
        count += 1
        deep = max(deep, n['d'])
        if n['kids']:
            stack.extend(n['kids'])
        if n['x'] <= q[2] and q[0] <= n['x'] + n['s'] and n['y'] <= q[3] and q[1] <= n['y'] + n['s']:
            found.extend(o[0] for o in n['objs'])
    return [sorted(found), count, deep]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[[[[[26, 2, 3, 4, 3], [46, 5, 9, 6, 9], [19, 11, 13, 12, 13], [30, 3, 15, 5, 16], [42, 0, 11, 3, 13], [8, 14, 5, 16, 8]], 2, 2, [0, 2, 2, 3]], [[8, 26], 9, 2]], [[[[41, 13, 0, 13, 2], [46, 3, 11, 3, 14], [28, 12, 0, 14, 3], [35, 14, 12, 16, 14], [27, 10, 15, 10, 15], [33, 0, 15, 0, 16]], 2, 3, [12, 14, 16, 16]], [[27, 35], 5, 1]], [[[[8, 4, 3, 5, 5], [30, 7, 3, 8, 5], [26, 10, 12, 13, 14], [37, 7, 5, 10, 8], [47, 1, 9, 4, 10], [42, 5, 8, 5, 9], [36, 15, 14, 16, 16]], 1, 2, [8, 5, 13, 7]], [[8, 30, 37], 13, 2]], [[[[41, 8, 14, 11, 16], [7, 7, 6, 8, 8], [38, 10, 10, 10, 13], [17, 7, 9, 8, 11], [2, 6, 3, 9, 4], [6, 12, 10, 12, 10], [30, 9, 12, 10, 12]], 3, 3, [1, 4, 1, 6]], [[2, 7, 17], 9, 2]], [[[[7, 15, 7, 16, 9], [25, 3, 3, 6, 4], [9, 0, 4, 3, 6], [15, 11, 10, 14, 10]], 3, 2, [9, 10, 13, 13]], [[7, 15], 5, 1]], [[[[10, 2, 7, 2, 9], [15, 13, 3, 13, 3], [48, 9, 7, 10, 7]], 3, 3, [0, 13, 0, 18]], [[10, 15, 48], 1, 0]], [[[[38, 7, 0, 10, 3], [19, 0, 15, 0, 16]], 1, 3, [2, 12, 4, 16]], [[19, 38], 5, 1]], [[[[11, 13, 14, 15, 15], [7, 15, 15, 16, 16], [21, 2, 5, 2, 5], [5, 13, 14, 13, 15], [37, 14, 6, 15, 7]], 2, 2, [13, 10, 18, 12]], [[5, 7, 11], 9, 2]]], [[[[[25, 12, 3, 14, 4], [19, 11, 9, 13, 12]], 3, 3, [14, 12, 17, 13]], [[19, 25], 1, 0]], [[[[37, 6, 12, 7, 15], [36, 13, 15, 16, 16], [24, 9, 12, 12, 15]], 3, 2, [8, 8, 13, 13]], [[24, 36, 37], 1, 0]], [[[[35, 4, 1, 4, 1], [1, 4, 2, 7, 4], [5, 12, 6, 15, 7]], 2, 1, [9, 7, 11, 11]], [[5], 5, 1]], [[[[18, 13, 7, 13, 9], [37, 13, 0, 14, 1], [36, 5, 15, 8, 16], [44, 10, 5, 12, 5], [15, 5, 15, 7, 16], [45, 10, 10, 12, 12], [17, 3, 15, 6, 16], [43, 9, 7, 12, 9], [28, 7, 4, 8, 4]], 3, 1, [6, 7, 10, 9]], [[15, 17, 18, 28, 36, 37, 43, 44, 45], 5, 1]], [[[[41, 6, 10, 7, 11], [20, 2, 3, 5, 5]], 1, 3, [7, 7, 10, 9]], [[20, 41], 5, 1]], [[[[14, 1, 8, 3, 8], [22, 0, 2, 0, 3], [49, 11, 5, 13, 8], [4, 9, 9, 11, 9], [31, 5, 6, 8, 7], [9, 13, 8, 14, 8], [46, 5, 11, 7, 12], [1, 5, 0, 6, 2]], 3, 1, [1, 13, 3, 16]], [[14, 31, 46, 49], 5, 1]], [[[[20, 12, 5, 13, 6], [26, 14, 0, 16, 1], [6, 1, 2, 1, 5], [35, 9, 1, 12, 1], [23, 3, 15, 4, 16]], 3, 1, [5, 12, 6, 17]], [[23], 5, 1]], [[[[14, 13, 9, 15, 10], [36, 11, 1, 11, 2]], 2, 3, [10, 8, 12, 8]], [[14, 36], 1, 0]]], [[[[[7, 12, 2, 12, 5], [38, 9, 14, 9, 16], [5, 5, 12, 7, 13], [14, 11, 3, 11, 3], [26, 0, 4, 3, 5], [6, 12, 1, 12, 1], [27, 7, 3, 10, 5], [22, 14, 1, 15, 2]], 2, 2, [5, 10, 10, 13]], [[5, 27, 38], 9, 2]], [[[[24, 6, 6, 9, 6], [27, 0, 1, 1, 3], [19, 4, 1, 4, 1]], 2, 2, [7, 8, 7, 10]], [[19, 24, 27], 5, 1]], [[[[25, 1, 10, 3, 11], [47, 2, 11, 5, 11], [38, 14, 11, 16, 12], [43, 8, 5, 9, 5]], 3, 1, [5, 8, 10, 12]], [[25, 38, 43, 47], 5, 1]], [[[[15, 4, 10, 4, 11], [10, 11, 8, 13, 10], [35, 11, 4, 12, 4], [5, 2, 10, 2, 13]], 1, 3, [7, 10, 11, 10]], [[5, 10, 15], 9, 2]], [[[[49, 13, 11, 13, 12], [21, 13, 3, 15, 3], [23, 11, 15, 13, 16], [7, 10, 8, 13, 10], [31, 4, 10, 6, 10], [36, 10, 5, 13, 8], [6, 14, 10, 16, 13], [34, 3, 10, 3, 10], [35, 0, 4, 3, 7], [17, 9, 7, 10, 9]], 3, 3, [0, 11, 2, 16]], [[17, 31, 34, 36], 9, 2]], [[[[21, 7, 7, 9, 9], [20, 10, 9, 13, 11], [32, 3, 5, 3, 5], [2, 13, 14, 13, 16], [35, 12, 4, 15, 6], [42, 8, 5, 9, 7]], 2, 3, [12, 2, 14, 5]], [[21, 35, 42], 5, 1]], [[[[27, 0, 2, 3, 3], [21, 0, 12, 2, 14], [38, 0, 2, 2, 5], [2, 0, 5, 3, 5], [31, 10, 9, 10, 12], [20, 10, 2, 11, 5]], 2, 2, [2, 10, 6, 14]], [[21], 9, 2]], [[[[31, 9, 1, 11, 1], [18, 6, 9, 9, 9], [28, 4, 7, 5, 8]], 2, 3, [14, 6, 16, 10]], [[18, 28, 31], 5, 1]]], [[[[[21, 9, 0, 11, 2], [17, 9, 15, 10, 16], [49, 13, 0, 15, 1], [44, 3, 11, 3, 12], [13, 15, 3, 16, 5], [3, 10, 11, 12, 13], [16, 3, 15, 6, 15], [20, 0, 1, 0, 3]], 3, 3, [14, 4, 18, 7]], [[13, 21, 49], 5, 1]], [[[[10, 14, 1, 16, 4], [22, 6, 5, 9, 8], [12, 0, 13, 3, 16]], 1, 2, [5, 3, 10, 8]], [[10, 12, 22], 5, 1]], [[[[6, 8, 7, 9, 8], [36, 9, 11, 12, 12], [34, 11, 4, 14, 4], [42, 13, 0, 15, 0], [14, 14, 1, 16, 3], [47, 12, 0, 13, 2], [12, 15, 12, 15, 12], [49, 6, 13, 6, 15], [28, 8, 15, 11, 16], [5, 3, 13, 6, 14]], 2, 3, [7, 0, 11, 2]], [[6, 34], 17, 3]], [[[[32, 4, 11, 6, 14], [9, 2, 6, 5, 8], [21, 7, 5, 8, 8], [25, 2, 4, 3, 6], [17, 5, 5, 6, 6], [23, 1, 8, 4, 8], [4, 6, 11, 9, 13], [41, 0, 5, 1, 7], [33, 14, 10, 15, 10], [14, 14, 4, 15, 7]], 1, 1, [5, 8, 9, 10]], [[4, 9, 14, 17, 21, 23, 25, 32, 33, 41], 5, 1]], [[[[33, 10, 2, 10, 2], [34, 15, 11, 15, 12]], 2, 3, [11, 4, 16, 4]], [[33, 34], 1, 0]], [[[[3, 10, 6, 12, 7], [4, 10, 14, 11, 15], [29, 6, 7, 6, 10], [26, 10, 15, 11, 16]], 2, 3, [12, 12, 13, 13]], [[4, 26, 29], 5, 1]], [[[[41, 6, 14, 8, 14], [46, 5, 5, 8, 8], [44, 1, 1, 2, 3], [18, 0, 8, 1, 11], [30, 4, 5, 7, 6]], 3, 1, [10, 11, 10, 11]], [[41, 46], 5, 1]], [[[[6, 4, 7, 6, 9], [39, 15, 0, 15, 2], [13, 11, 7, 12, 8], [7, 14, 1, 14, 1], [8, 14, 3, 14, 4], [5, 6, 13, 7, 15], [15, 1, 8, 2, 8]], 1, 3, [1, 7, 3, 10]], [[6, 13, 15], 17, 3]]], [[[[[45, 11, 12, 11, 14], [46, 10, 11, 11, 14], [5, 14, 10, 16, 12], [25, 13, 4, 14, 5], [14, 1, 4, 4, 6], [33, 11, 10, 11, 10]], 2, 2, [11, 14, 11, 18]], [[5, 45, 46], 9, 2]], [[[[19, 14, 13, 15, 13], [37, 9, 0, 10, 2], [30, 1, 14, 3, 16], [42, 0, 12, 0, 12], [29, 9, 8, 9, 9], [41, 1, 3, 1, 6], [10, 7, 4, 9, 4], [28, 4, 12, 7, 15], [38, 7, 6, 8, 6], [40, 9, 1, 11, 4], [33, 12, 1, 12, 1], [5, 1, 15, 4, 16]], 1, 2, [8, 3, 11, 6]], [[10, 37, 38, 40, 41], 17, 2]], [[[[2, 11, 2, 14, 2], [16, 4, 4, 5, 7]], 2, 1, [12, 2, 17, 5]], [[2, 16], 1, 0]], [[[[27, 10, 6, 12, 6], [34, 4, 9, 4, 12]], 3, 3, [6, 13, 10, 15]], [[27, 34], 1, 0]], [[[[39, 1, 10, 2, 13], [45, 11, 10, 13, 11], [12, 7, 6, 7, 6], [33, 6, 15, 9, 16], [47, 1, 8, 4, 11]], 1, 1, [9, 8, 14, 8]], [[33, 45], 5, 1]], [[[[11, 13, 1, 14, 2], [32, 0, 11, 1, 12], [13, 9, 11, 12, 14], [21, 2, 1, 3, 2], [35, 15, 9, 15, 11], [22, 12, 2, 13, 4], [30, 3, 3, 5, 4], [38, 10, 8, 10, 10], [1, 0, 1, 1, 2], [40, 4, 13, 4, 15], [8, 14, 9, 14, 10], [45, 2, 2, 5, 3]], 2, 1, [11, 8, 13, 10]], [[8, 11, 13, 22, 35, 38], 5, 1]], [[[[1, 11, 1, 12, 2], [4, 2, 8, 4, 9], [21, 9, 12, 11, 13], [44, 7, 5, 10, 8], [33, 8, 8, 8, 11], [25, 10, 12, 10, 13], [43, 12, 7, 15, 10], [15, 2, 14, 5, 15], [2, 5, 2, 5, 5], [9, 11, 8, 13, 9], [48, 6, 15, 9, 16]], 2, 1, [7, 8, 9, 11]], [[1, 2, 4, 9, 15, 21, 25, 33, 43, 44, 48], 5, 1]], [[[[36, 14, 12, 14, 12], [41, 7, 0, 8, 0], [20, 15, 10, 16, 12], [43, 11, 3, 13, 4], [12, 10, 11, 12, 12], [5, 6, 3, 6, 5], [11, 7, 1, 8, 1], [15, 10, 14, 11, 16], [17, 0, 13, 0, 15], [18, 8, 5, 8, 6], [13, 1, 6, 4, 6]], 2, 2, [8, 2, 12, 3]], [[5, 11, 13, 18, 41, 43], 9, 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	`[[8, 19, 26, 46], 5, 1]`	`[[8, 26], 9, 2]`	Failed
case 1	`[[27, 28, 35, 41, 46], 5, 1]`	`[[27, 35], 5, 1]`	Failed
case 2	`[[8, 30, 37], 13, 2]`	`[[8, 30, 37], 13, 2]`	Passed
case 3	`[[2, 7, 17, 38, 41], 5, 1]`	`[[2, 7, 17], 9, 2]`	Failed
case 4	`[[7, 9, 15, 25], 5, 1]`	`[[7, 15], 5, 1]`	Failed
case 5	`[[10, 15, 48], 1, 0]`	`[[10, 15, 48], 1, 0]`	Passed
case 6	`[[19, 38], 5, 1]`	`[[19, 38], 5, 1]`	Passed
case 7	`[[5, 7, 11, 21], 5, 1]`	`[[5, 7, 11], 9, 2]`	Failed

SHA-256 / 5b25838cc8a70e3a2f33c9755a073848e69da00076bb97ca459f887dd4d559f4

2 / The unsuccessful fix

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(objs, cap, max_depth, q):
    def make(x, y, s, d):
        return {'x': x, 'y': y, 's': s, 'd': d, 'objs': [], 'kids': None}
    def child_index(n, o):
        h = n['s'] / 2
        mx, my = n['x'] + h, n['y'] + h
        if o[3] < mx:
            cx = 0
        elif o[1] >= mx:
            cx = 1
        else:
            return -1
        if o[4] < my:
            cy = 0
        elif o[2] >= my:
            cy = 1
        else:
            return -1
        return cy * 2 + cx
    def split(n):
        h = n['s'] / 2
        n['kids'] = [make(n['x'] + (k % 2) * h, n['y'] + (k // 2) * h, h, n['d'] + 1) for k in range(4)]
        old, n['objs'] = n['objs'][-1:], n['objs'][:-1]
        for o in old:
            insert(n, o)
    def insert(n, o):
        if n['kids'] is not None:
            k = child_index(n, o)
            if k >= 0:
                insert(n['kids'][k], o)
                return
        n['objs'].append(o)
        if n['kids'] is None and len(n['objs']) > cap and n['d'] < max_depth:
            split(n)
    root = make(0, 0, 16, 0)
    for o in objs:
        insert(root, o)
    found, count, deep = [], 0, 0
    stack = [root]
    while stack:
        n = stack.pop()
        count += 1
        deep = max(deep, n['d'])
        if n['kids']:
            stack.extend(n['kids'])
        if n['x'] <= q[2] and q[0] <= n['x'] + n['s'] and n['y'] <= q[3] and q[1] <= n['y'] + n['s']:
            found.extend(o[0] for o in n['objs'])
    return [sorted(found), count, deep]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[[[[[26, 2, 3, 4, 3], [46, 5, 9, 6, 9], [19, 11, 13, 12, 13], [30, 3, 15, 5, 16], [42, 0, 11, 3, 13], [8, 14, 5, 16, 8]], 2, 2, [0, 2, 2, 3]], [[8, 26], 9, 2]], [[[[41, 13, 0, 13, 2], [46, 3, 11, 3, 14], [28, 12, 0, 14, 3], [35, 14, 12, 16, 14], [27, 10, 15, 10, 15], [33, 0, 15, 0, 16]], 2, 3, [12, 14, 16, 16]], [[27, 35], 5, 1]], [[[[8, 4, 3, 5, 5], [30, 7, 3, 8, 5], [26, 10, 12, 13, 14], [37, 7, 5, 10, 8], [47, 1, 9, 4, 10], [42, 5, 8, 5, 9], [36, 15, 14, 16, 16]], 1, 2, [8, 5, 13, 7]], [[8, 30, 37], 13, 2]], [[[[41, 8, 14, 11, 16], [7, 7, 6, 8, 8], [38, 10, 10, 10, 13], [17, 7, 9, 8, 11], [2, 6, 3, 9, 4], [6, 12, 10, 12, 10], [30, 9, 12, 10, 12]], 3, 3, [1, 4, 1, 6]], [[2, 7, 17], 9, 2]], [[[[7, 15, 7, 16, 9], [25, 3, 3, 6, 4], [9, 0, 4, 3, 6], [15, 11, 10, 14, 10]], 3, 2, [9, 10, 13, 13]], [[7, 15], 5, 1]], [[[[10, 2, 7, 2, 9], [15, 13, 3, 13, 3], [48, 9, 7, 10, 7]], 3, 3, [0, 13, 0, 18]], [[10, 15, 48], 1, 0]], [[[[38, 7, 0, 10, 3], [19, 0, 15, 0, 16]], 1, 3, [2, 12, 4, 16]], [[19, 38], 5, 1]], [[[[11, 13, 14, 15, 15], [7, 15, 15, 16, 16], [21, 2, 5, 2, 5], [5, 13, 14, 13, 15], [37, 14, 6, 15, 7]], 2, 2, [13, 10, 18, 12]], [[5, 7, 11], 9, 2]]], [[[[[25, 12, 3, 14, 4], [19, 11, 9, 13, 12]], 3, 3, [14, 12, 17, 13]], [[19, 25], 1, 0]], [[[[37, 6, 12, 7, 15], [36, 13, 15, 16, 16], [24, 9, 12, 12, 15]], 3, 2, [8, 8, 13, 13]], [[24, 36, 37], 1, 0]], [[[[35, 4, 1, 4, 1], [1, 4, 2, 7, 4], [5, 12, 6, 15, 7]], 2, 1, [9, 7, 11, 11]], [[5], 5, 1]], [[[[18, 13, 7, 13, 9], [37, 13, 0, 14, 1], [36, 5, 15, 8, 16], [44, 10, 5, 12, 5], [15, 5, 15, 7, 16], [45, 10, 10, 12, 12], [17, 3, 15, 6, 16], [43, 9, 7, 12, 9], [28, 7, 4, 8, 4]], 3, 1, [6, 7, 10, 9]], [[15, 17, 18, 28, 36, 37, 43, 44, 45], 5, 1]], [[[[41, 6, 10, 7, 11], [20, 2, 3, 5, 5]], 1, 3, [7, 7, 10, 9]], [[20, 41], 5, 1]], [[[[14, 1, 8, 3, 8], [22, 0, 2, 0, 3], [49, 11, 5, 13, 8], [4, 9, 9, 11, 9], [31, 5, 6, 8, 7], [9, 13, 8, 14, 8], [46, 5, 11, 7, 12], [1, 5, 0, 6, 2]], 3, 1, [1, 13, 3, 16]], [[14, 31, 46, 49], 5, 1]], [[[[20, 12, 5, 13, 6], [26, 14, 0, 16, 1], [6, 1, 2, 1, 5], [35, 9, 1, 12, 1], [23, 3, 15, 4, 16]], 3, 1, [5, 12, 6, 17]], [[23], 5, 1]], [[[[14, 13, 9, 15, 10], [36, 11, 1, 11, 2]], 2, 3, [10, 8, 12, 8]], [[14, 36], 1, 0]]], [[[[[7, 12, 2, 12, 5], [38, 9, 14, 9, 16], [5, 5, 12, 7, 13], [14, 11, 3, 11, 3], [26, 0, 4, 3, 5], [6, 12, 1, 12, 1], [27, 7, 3, 10, 5], [22, 14, 1, 15, 2]], 2, 2, [5, 10, 10, 13]], [[5, 27, 38], 9, 2]], [[[[24, 6, 6, 9, 6], [27, 0, 1, 1, 3], [19, 4, 1, 4, 1]], 2, 2, [7, 8, 7, 10]], [[19, 24, 27], 5, 1]], [[[[25, 1, 10, 3, 11], [47, 2, 11, 5, 11], [38, 14, 11, 16, 12], [43, 8, 5, 9, 5]], 3, 1, [5, 8, 10, 12]], [[25, 38, 43, 47], 5, 1]], [[[[15, 4, 10, 4, 11], [10, 11, 8, 13, 10], [35, 11, 4, 12, 4], [5, 2, 10, 2, 13]], 1, 3, [7, 10, 11, 10]], [[5, 10, 15], 9, 2]], [[[[49, 13, 11, 13, 12], [21, 13, 3, 15, 3], [23, 11, 15, 13, 16], [7, 10, 8, 13, 10], [31, 4, 10, 6, 10], [36, 10, 5, 13, 8], [6, 14, 10, 16, 13], [34, 3, 10, 3, 10], [35, 0, 4, 3, 7], [17, 9, 7, 10, 9]], 3, 3, [0, 11, 2, 16]], [[17, 31, 34, 36], 9, 2]], [[[[21, 7, 7, 9, 9], [20, 10, 9, 13, 11], [32, 3, 5, 3, 5], [2, 13, 14, 13, 16], [35, 12, 4, 15, 6], [42, 8, 5, 9, 7]], 2, 3, [12, 2, 14, 5]], [[21, 35, 42], 5, 1]], [[[[27, 0, 2, 3, 3], [21, 0, 12, 2, 14], [38, 0, 2, 2, 5], [2, 0, 5, 3, 5], [31, 10, 9, 10, 12], [20, 10, 2, 11, 5]], 2, 2, [2, 10, 6, 14]], [[21], 9, 2]], [[[[31, 9, 1, 11, 1], [18, 6, 9, 9, 9], [28, 4, 7, 5, 8]], 2, 3, [14, 6, 16, 10]], [[18, 28, 31], 5, 1]]], [[[[[21, 9, 0, 11, 2], [17, 9, 15, 10, 16], [49, 13, 0, 15, 1], [44, 3, 11, 3, 12], [13, 15, 3, 16, 5], [3, 10, 11, 12, 13], [16, 3, 15, 6, 15], [20, 0, 1, 0, 3]], 3, 3, [14, 4, 18, 7]], [[13, 21, 49], 5, 1]], [[[[10, 14, 1, 16, 4], [22, 6, 5, 9, 8], [12, 0, 13, 3, 16]], 1, 2, [5, 3, 10, 8]], [[10, 12, 22], 5, 1]], [[[[6, 8, 7, 9, 8], [36, 9, 11, 12, 12], [34, 11, 4, 14, 4], [42, 13, 0, 15, 0], [14, 14, 1, 16, 3], [47, 12, 0, 13, 2], [12, 15, 12, 15, 12], [49, 6, 13, 6, 15], [28, 8, 15, 11, 16], [5, 3, 13, 6, 14]], 2, 3, [7, 0, 11, 2]], [[6, 34], 17, 3]], [[[[32, 4, 11, 6, 14], [9, 2, 6, 5, 8], [21, 7, 5, 8, 8], [25, 2, 4, 3, 6], [17, 5, 5, 6, 6], [23, 1, 8, 4, 8], [4, 6, 11, 9, 13], [41, 0, 5, 1, 7], [33, 14, 10, 15, 10], [14, 14, 4, 15, 7]], 1, 1, [5, 8, 9, 10]], [[4, 9, 14, 17, 21, 23, 25, 32, 33, 41], 5, 1]], [[[[33, 10, 2, 10, 2], [34, 15, 11, 15, 12]], 2, 3, [11, 4, 16, 4]], [[33, 34], 1, 0]], [[[[3, 10, 6, 12, 7], [4, 10, 14, 11, 15], [29, 6, 7, 6, 10], [26, 10, 15, 11, 16]], 2, 3, [12, 12, 13, 13]], [[4, 26, 29], 5, 1]], [[[[41, 6, 14, 8, 14], [46, 5, 5, 8, 8], [44, 1, 1, 2, 3], [18, 0, 8, 1, 11], [30, 4, 5, 7, 6]], 3, 1, [10, 11, 10, 11]], [[41, 46], 5, 1]], [[[[6, 4, 7, 6, 9], [39, 15, 0, 15, 2], [13, 11, 7, 12, 8], [7, 14, 1, 14, 1], [8, 14, 3, 14, 4], [5, 6, 13, 7, 15], [15, 1, 8, 2, 8]], 1, 3, [1, 7, 3, 10]], [[6, 13, 15], 17, 3]]], [[[[[45, 11, 12, 11, 14], [46, 10, 11, 11, 14], [5, 14, 10, 16, 12], [25, 13, 4, 14, 5], [14, 1, 4, 4, 6], [33, 11, 10, 11, 10]], 2, 2, [11, 14, 11, 18]], [[5, 45, 46], 9, 2]], [[[[19, 14, 13, 15, 13], [37, 9, 0, 10, 2], [30, 1, 14, 3, 16], [42, 0, 12, 0, 12], [29, 9, 8, 9, 9], [41, 1, 3, 1, 6], [10, 7, 4, 9, 4], [28, 4, 12, 7, 15], [38, 7, 6, 8, 6], [40, 9, 1, 11, 4], [33, 12, 1, 12, 1], [5, 1, 15, 4, 16]], 1, 2, [8, 3, 11, 6]], [[10, 37, 38, 40, 41], 17, 2]], [[[[2, 11, 2, 14, 2], [16, 4, 4, 5, 7]], 2, 1, [12, 2, 17, 5]], [[2, 16], 1, 0]], [[[[27, 10, 6, 12, 6], [34, 4, 9, 4, 12]], 3, 3, [6, 13, 10, 15]], [[27, 34], 1, 0]], [[[[39, 1, 10, 2, 13], [45, 11, 10, 13, 11], [12, 7, 6, 7, 6], [33, 6, 15, 9, 16], [47, 1, 8, 4, 11]], 1, 1, [9, 8, 14, 8]], [[33, 45], 5, 1]], [[[[11, 13, 1, 14, 2], [32, 0, 11, 1, 12], [13, 9, 11, 12, 14], [21, 2, 1, 3, 2], [35, 15, 9, 15, 11], [22, 12, 2, 13, 4], [30, 3, 3, 5, 4], [38, 10, 8, 10, 10], [1, 0, 1, 1, 2], [40, 4, 13, 4, 15], [8, 14, 9, 14, 10], [45, 2, 2, 5, 3]], 2, 1, [11, 8, 13, 10]], [[8, 11, 13, 22, 35, 38], 5, 1]], [[[[1, 11, 1, 12, 2], [4, 2, 8, 4, 9], [21, 9, 12, 11, 13], [44, 7, 5, 10, 8], [33, 8, 8, 8, 11], [25, 10, 12, 10, 13], [43, 12, 7, 15, 10], [15, 2, 14, 5, 15], [2, 5, 2, 5, 5], [9, 11, 8, 13, 9], [48, 6, 15, 9, 16]], 2, 1, [7, 8, 9, 11]], [[1, 2, 4, 9, 15, 21, 25, 33, 43, 44, 48], 5, 1]], [[[[36, 14, 12, 14, 12], [41, 7, 0, 8, 0], [20, 15, 10, 16, 12], [43, 11, 3, 13, 4], [12, 10, 11, 12, 12], [5, 6, 3, 6, 5], [11, 7, 1, 8, 1], [15, 10, 14, 11, 16], [17, 0, 13, 0, 15], [18, 8, 5, 8, 6], [13, 1, 6, 4, 6]], 2, 2, [8, 2, 12, 3]], [[5, 11, 13, 18, 41, 43], 9, 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	`[[8, 26, 46], 5, 1]`	`[[8, 26], 9, 2]`	Failed
case 1	`[[27, 35, 41, 46], 5, 1]`	`[[27, 35], 5, 1]`	Failed
case 2	`[[8, 30, 37], 13, 2]`	`[[8, 30, 37], 13, 2]`	Passed
case 3	`[[2, 7, 17, 38, 41], 5, 1]`	`[[2, 7, 17], 9, 2]`	Failed
case 4	`[[7, 9, 15, 25], 5, 1]`	`[[7, 15], 5, 1]`	Failed
case 5	`[[10, 15, 48], 1, 0]`	`[[10, 15, 48], 1, 0]`	Passed
case 6	`[[19, 38], 5, 1]`	`[[19, 38], 5, 1]`	Passed
case 7	`[[5, 7, 11], 5, 1]`	`[[5, 7, 11], 9, 2]`	Failed

SHA-256 / cf5d074128200d3604f752a2099cd22d9ef3c1daf695cff1f63c824d112f461d

3 / The verified repair

Exit 0

"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(objs, cap, max_depth, q):
    def make(x, y, s, d):
        return {'x': x, 'y': y, 's': s, 'd': d, 'objs': [], 'kids': None}
    def child_index(n, o):
        h = n['s'] / 2
        mx, my = n['x'] + h, n['y'] + h
        if o[3] < mx:
            cx = 0
        elif o[1] >= mx:
            cx = 1
        else:
            return -1
        if o[4] < my:
            cy = 0
        elif o[2] >= my:
            cy = 1
        else:
            return -1
        return cy * 2 + cx
    def split(n):
        h = n['s'] / 2
        n['kids'] = [make(n['x'] + (k % 2) * h, n['y'] + (k // 2) * h, h, n['d'] + 1) for k in range(4)]
        old, n['objs'] = n['objs'], []
        for o in old:
            insert(n, o)
    def insert(n, o):
        if n['kids'] is not None:
            k = child_index(n, o)
            if k >= 0:
                insert(n['kids'][k], o)
                return
        n['objs'].append(o)
        if n['kids'] is None and len(n['objs']) > cap and n['d'] < max_depth:
            split(n)
    root = make(0, 0, 16, 0)
    for o in objs:
        insert(root, o)
    found, count, deep = [], 0, 0
    stack = [root]
    while stack:
        n = stack.pop()
        count += 1
        deep = max(deep, n['d'])
        if n['kids']:
            stack.extend(n['kids'])
        if n['x'] <= q[2] and q[0] <= n['x'] + n['s'] and n['y'] <= q[3] and q[1] <= n['y'] + n['s']:
            found.extend(o[0] for o in n['objs'])
    return [sorted(found), count, deep]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[[[[[26, 2, 3, 4, 3], [46, 5, 9, 6, 9], [19, 11, 13, 12, 13], [30, 3, 15, 5, 16], [42, 0, 11, 3, 13], [8, 14, 5, 16, 8]], 2, 2, [0, 2, 2, 3]], [[8, 26], 9, 2]], [[[[41, 13, 0, 13, 2], [46, 3, 11, 3, 14], [28, 12, 0, 14, 3], [35, 14, 12, 16, 14], [27, 10, 15, 10, 15], [33, 0, 15, 0, 16]], 2, 3, [12, 14, 16, 16]], [[27, 35], 5, 1]], [[[[8, 4, 3, 5, 5], [30, 7, 3, 8, 5], [26, 10, 12, 13, 14], [37, 7, 5, 10, 8], [47, 1, 9, 4, 10], [42, 5, 8, 5, 9], [36, 15, 14, 16, 16]], 1, 2, [8, 5, 13, 7]], [[8, 30, 37], 13, 2]], [[[[41, 8, 14, 11, 16], [7, 7, 6, 8, 8], [38, 10, 10, 10, 13], [17, 7, 9, 8, 11], [2, 6, 3, 9, 4], [6, 12, 10, 12, 10], [30, 9, 12, 10, 12]], 3, 3, [1, 4, 1, 6]], [[2, 7, 17], 9, 2]], [[[[7, 15, 7, 16, 9], [25, 3, 3, 6, 4], [9, 0, 4, 3, 6], [15, 11, 10, 14, 10]], 3, 2, [9, 10, 13, 13]], [[7, 15], 5, 1]], [[[[10, 2, 7, 2, 9], [15, 13, 3, 13, 3], [48, 9, 7, 10, 7]], 3, 3, [0, 13, 0, 18]], [[10, 15, 48], 1, 0]], [[[[38, 7, 0, 10, 3], [19, 0, 15, 0, 16]], 1, 3, [2, 12, 4, 16]], [[19, 38], 5, 1]], [[[[11, 13, 14, 15, 15], [7, 15, 15, 16, 16], [21, 2, 5, 2, 5], [5, 13, 14, 13, 15], [37, 14, 6, 15, 7]], 2, 2, [13, 10, 18, 12]], [[5, 7, 11], 9, 2]]], [[[[[25, 12, 3, 14, 4], [19, 11, 9, 13, 12]], 3, 3, [14, 12, 17, 13]], [[19, 25], 1, 0]], [[[[37, 6, 12, 7, 15], [36, 13, 15, 16, 16], [24, 9, 12, 12, 15]], 3, 2, [8, 8, 13, 13]], [[24, 36, 37], 1, 0]], [[[[35, 4, 1, 4, 1], [1, 4, 2, 7, 4], [5, 12, 6, 15, 7]], 2, 1, [9, 7, 11, 11]], [[5], 5, 1]], [[[[18, 13, 7, 13, 9], [37, 13, 0, 14, 1], [36, 5, 15, 8, 16], [44, 10, 5, 12, 5], [15, 5, 15, 7, 16], [45, 10, 10, 12, 12], [17, 3, 15, 6, 16], [43, 9, 7, 12, 9], [28, 7, 4, 8, 4]], 3, 1, [6, 7, 10, 9]], [[15, 17, 18, 28, 36, 37, 43, 44, 45], 5, 1]], [[[[41, 6, 10, 7, 11], [20, 2, 3, 5, 5]], 1, 3, [7, 7, 10, 9]], [[20, 41], 5, 1]], [[[[14, 1, 8, 3, 8], [22, 0, 2, 0, 3], [49, 11, 5, 13, 8], [4, 9, 9, 11, 9], [31, 5, 6, 8, 7], [9, 13, 8, 14, 8], [46, 5, 11, 7, 12], [1, 5, 0, 6, 2]], 3, 1, [1, 13, 3, 16]], [[14, 31, 46, 49], 5, 1]], [[[[20, 12, 5, 13, 6], [26, 14, 0, 16, 1], [6, 1, 2, 1, 5], [35, 9, 1, 12, 1], [23, 3, 15, 4, 16]], 3, 1, [5, 12, 6, 17]], [[23], 5, 1]], [[[[14, 13, 9, 15, 10], [36, 11, 1, 11, 2]], 2, 3, [10, 8, 12, 8]], [[14, 36], 1, 0]]], [[[[[7, 12, 2, 12, 5], [38, 9, 14, 9, 16], [5, 5, 12, 7, 13], [14, 11, 3, 11, 3], [26, 0, 4, 3, 5], [6, 12, 1, 12, 1], [27, 7, 3, 10, 5], [22, 14, 1, 15, 2]], 2, 2, [5, 10, 10, 13]], [[5, 27, 38], 9, 2]], [[[[24, 6, 6, 9, 6], [27, 0, 1, 1, 3], [19, 4, 1, 4, 1]], 2, 2, [7, 8, 7, 10]], [[19, 24, 27], 5, 1]], [[[[25, 1, 10, 3, 11], [47, 2, 11, 5, 11], [38, 14, 11, 16, 12], [43, 8, 5, 9, 5]], 3, 1, [5, 8, 10, 12]], [[25, 38, 43, 47], 5, 1]], [[[[15, 4, 10, 4, 11], [10, 11, 8, 13, 10], [35, 11, 4, 12, 4], [5, 2, 10, 2, 13]], 1, 3, [7, 10, 11, 10]], [[5, 10, 15], 9, 2]], [[[[49, 13, 11, 13, 12], [21, 13, 3, 15, 3], [23, 11, 15, 13, 16], [7, 10, 8, 13, 10], [31, 4, 10, 6, 10], [36, 10, 5, 13, 8], [6, 14, 10, 16, 13], [34, 3, 10, 3, 10], [35, 0, 4, 3, 7], [17, 9, 7, 10, 9]], 3, 3, [0, 11, 2, 16]], [[17, 31, 34, 36], 9, 2]], [[[[21, 7, 7, 9, 9], [20, 10, 9, 13, 11], [32, 3, 5, 3, 5], [2, 13, 14, 13, 16], [35, 12, 4, 15, 6], [42, 8, 5, 9, 7]], 2, 3, [12, 2, 14, 5]], [[21, 35, 42], 5, 1]], [[[[27, 0, 2, 3, 3], [21, 0, 12, 2, 14], [38, 0, 2, 2, 5], [2, 0, 5, 3, 5], [31, 10, 9, 10, 12], [20, 10, 2, 11, 5]], 2, 2, [2, 10, 6, 14]], [[21], 9, 2]], [[[[31, 9, 1, 11, 1], [18, 6, 9, 9, 9], [28, 4, 7, 5, 8]], 2, 3, [14, 6, 16, 10]], [[18, 28, 31], 5, 1]]], [[[[[21, 9, 0, 11, 2], [17, 9, 15, 10, 16], [49, 13, 0, 15, 1], [44, 3, 11, 3, 12], [13, 15, 3, 16, 5], [3, 10, 11, 12, 13], [16, 3, 15, 6, 15], [20, 0, 1, 0, 3]], 3, 3, [14, 4, 18, 7]], [[13, 21, 49], 5, 1]], [[[[10, 14, 1, 16, 4], [22, 6, 5, 9, 8], [12, 0, 13, 3, 16]], 1, 2, [5, 3, 10, 8]], [[10, 12, 22], 5, 1]], [[[[6, 8, 7, 9, 8], [36, 9, 11, 12, 12], [34, 11, 4, 14, 4], [42, 13, 0, 15, 0], [14, 14, 1, 16, 3], [47, 12, 0, 13, 2], [12, 15, 12, 15, 12], [49, 6, 13, 6, 15], [28, 8, 15, 11, 16], [5, 3, 13, 6, 14]], 2, 3, [7, 0, 11, 2]], [[6, 34], 17, 3]], [[[[32, 4, 11, 6, 14], [9, 2, 6, 5, 8], [21, 7, 5, 8, 8], [25, 2, 4, 3, 6], [17, 5, 5, 6, 6], [23, 1, 8, 4, 8], [4, 6, 11, 9, 13], [41, 0, 5, 1, 7], [33, 14, 10, 15, 10], [14, 14, 4, 15, 7]], 1, 1, [5, 8, 9, 10]], [[4, 9, 14, 17, 21, 23, 25, 32, 33, 41], 5, 1]], [[[[33, 10, 2, 10, 2], [34, 15, 11, 15, 12]], 2, 3, [11, 4, 16, 4]], [[33, 34], 1, 0]], [[[[3, 10, 6, 12, 7], [4, 10, 14, 11, 15], [29, 6, 7, 6, 10], [26, 10, 15, 11, 16]], 2, 3, [12, 12, 13, 13]], [[4, 26, 29], 5, 1]], [[[[41, 6, 14, 8, 14], [46, 5, 5, 8, 8], [44, 1, 1, 2, 3], [18, 0, 8, 1, 11], [30, 4, 5, 7, 6]], 3, 1, [10, 11, 10, 11]], [[41, 46], 5, 1]], [[[[6, 4, 7, 6, 9], [39, 15, 0, 15, 2], [13, 11, 7, 12, 8], [7, 14, 1, 14, 1], [8, 14, 3, 14, 4], [5, 6, 13, 7, 15], [15, 1, 8, 2, 8]], 1, 3, [1, 7, 3, 10]], [[6, 13, 15], 17, 3]]], [[[[[45, 11, 12, 11, 14], [46, 10, 11, 11, 14], [5, 14, 10, 16, 12], [25, 13, 4, 14, 5], [14, 1, 4, 4, 6], [33, 11, 10, 11, 10]], 2, 2, [11, 14, 11, 18]], [[5, 45, 46], 9, 2]], [[[[19, 14, 13, 15, 13], [37, 9, 0, 10, 2], [30, 1, 14, 3, 16], [42, 0, 12, 0, 12], [29, 9, 8, 9, 9], [41, 1, 3, 1, 6], [10, 7, 4, 9, 4], [28, 4, 12, 7, 15], [38, 7, 6, 8, 6], [40, 9, 1, 11, 4], [33, 12, 1, 12, 1], [5, 1, 15, 4, 16]], 1, 2, [8, 3, 11, 6]], [[10, 37, 38, 40, 41], 17, 2]], [[[[2, 11, 2, 14, 2], [16, 4, 4, 5, 7]], 2, 1, [12, 2, 17, 5]], [[2, 16], 1, 0]], [[[[27, 10, 6, 12, 6], [34, 4, 9, 4, 12]], 3, 3, [6, 13, 10, 15]], [[27, 34], 1, 0]], [[[[39, 1, 10, 2, 13], [45, 11, 10, 13, 11], [12, 7, 6, 7, 6], [33, 6, 15, 9, 16], [47, 1, 8, 4, 11]], 1, 1, [9, 8, 14, 8]], [[33, 45], 5, 1]], [[[[11, 13, 1, 14, 2], [32, 0, 11, 1, 12], [13, 9, 11, 12, 14], [21, 2, 1, 3, 2], [35, 15, 9, 15, 11], [22, 12, 2, 13, 4], [30, 3, 3, 5, 4], [38, 10, 8, 10, 10], [1, 0, 1, 1, 2], [40, 4, 13, 4, 15], [8, 14, 9, 14, 10], [45, 2, 2, 5, 3]], 2, 1, [11, 8, 13, 10]], [[8, 11, 13, 22, 35, 38], 5, 1]], [[[[1, 11, 1, 12, 2], [4, 2, 8, 4, 9], [21, 9, 12, 11, 13], [44, 7, 5, 10, 8], [33, 8, 8, 8, 11], [25, 10, 12, 10, 13], [43, 12, 7, 15, 10], [15, 2, 14, 5, 15], [2, 5, 2, 5, 5], [9, 11, 8, 13, 9], [48, 6, 15, 9, 16]], 2, 1, [7, 8, 9, 11]], [[1, 2, 4, 9, 15, 21, 25, 33, 43, 44, 48], 5, 1]], [[[[36, 14, 12, 14, 12], [41, 7, 0, 8, 0], [20, 15, 10, 16, 12], [43, 11, 3, 13, 4], [12, 10, 11, 12, 12], [5, 6, 3, 6, 5], [11, 7, 1, 8, 1], [15, 10, 14, 11, 16], [17, 0, 13, 0, 15], [18, 8, 5, 8, 6], [13, 1, 6, 4, 6]], 2, 2, [8, 2, 12, 3]], [[5, 11, 13, 18, 41, 43], 9, 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	`[[8, 26], 9, 2]`	`[[8, 26], 9, 2]`	Passed
case 1	`[[27, 35], 5, 1]`	`[[27, 35], 5, 1]`	Passed
case 2	`[[8, 30, 37], 13, 2]`	`[[8, 30, 37], 13, 2]`	Passed
case 3	`[[2, 7, 17], 9, 2]`	`[[2, 7, 17], 9, 2]`	Passed
case 4	`[[7, 15], 5, 1]`	`[[7, 15], 5, 1]`	Passed
case 5	`[[10, 15, 48], 1, 0]`	`[[10, 15, 48], 1, 0]`	Passed
case 6	`[[19, 38], 5, 1]`	`[[19, 38], 5, 1]`	Passed
case 7	`[[5, 7, 11], 9, 2]`	`[[5, 7, 11], 9, 2]`	Passed

SHA-256 / 350590f38a5c3e415e369ecd36fda01f53593d6b050c34223ff4beea2a240b96

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

Case digest / 794abb83d97028c7f4b1946db8aa3418186361181992e1aa1bbf9a21917c1022