FA-87461 / Collision detection broadphase / Open access

Leaves are accepted without testing their own bounds · case 01

Every leaf under an overlapping parent is returned as a hit.

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

ROOT CAUSE

The traversal appends leaf ids before the overlap test.

VERIFIED REPAIR

Test leaves like any other node before reporting them.

Unsuccessful approach: Testing leaves but not counting the tests hides the traversal cost.

Case contract

solve(nodes, q): BVH nodes [minx,miny,maxx,maxy,left,right,leaf_id], leaves have left=-1; root is node 0. Stack traversal tests every popped node against the closed query box (counting each test) and descends only into overlapping internal nodes. Return [sorted leaf ids overlapping q, number of node tests].

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(nodes, q):
    if not nodes:
        return [[], 0]
    stack = [0]
    hits = []
    tests = 0
    while stack:
        i = stack.pop()
        nd = nodes[i]
        if nd[4] < 0:
            hits.append(nd[6])
            continue
        tests += 1
        if not (nd[0] <= q[2] and q[0] <= nd[2] and nd[1] <= q[3] and q[1] <= nd[3]):
            continue
        if nd[4] < 0:
            hits.append(nd[6])
        else:
            stack.append(nd[4])
            stack.append(nd[5])
    return [sorted(hits), tests]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[[[[[0, 2, 12, 12, 1, 4, -1], [0, 2, 7, 4, 2, 3, -1], [0, 4, 2, 4, -1, -1, 100], [5, 2, 7, 2, -1, -1, 103], [8, 4, 12, 12, 5, 6, -1], [8, 4, 9, 6, -1, -1, 104], [10, 6, 12, 12, 7, 8, -1], [11, 10, 11, 12, -1, -1, 101], [10, 6, 12, 8, -1, -1, 102]], [6, 5, 7, 7]], [[], 3]], [[[[2, 1, 11, 12, 1, 6, -1], [2, 1, 6, 5, 2, 3, -1], [2, 1, 5, 3, -1, -1, 104], [5, 2, 6, 5, 4, 5, -1], [5, 2, 5, 5, -1, -1, 103], [6, 3, 6, 3, -1, -1, 105], [6, 1, 11, 12, 7, 10, -1], [6, 1, 8, 12, 8, 9, -1], [6, 11, 7, 12, -1, -1, 102], [6, 1, 8, 2, -1, -1, 106], [9, 6, 11, 8, 11, 12, -1], [9, 6, 9, 7, -1, -1, 101], [10, 6, 11, 8, -1, -1, 100]], [7, 6, 10, 9]], [[100, 101], 9]], [[[[0, 4, 13, 14, 1, 6, -1], [0, 4, 5, 14, 2, 3, -1], [0, 4, 1, 4, -1, -1, 104], [1, 6, 5, 14, 4, 5, -1], [1, 6, 3, 7, -1, -1, 102], [2, 12, 5, 14, -1, -1, 105], [6, 4, 13, 13, 7, 10, -1], [6, 11, 8, 13, 8, 9, -1], [6, 11, 8, 13, -1, -1, 101], [7, 11, 8, 11, -1, -1, 100], [7, 4, 13, 7, 11, 12, -1], [7, 4, 8, 4, -1, -1, 106], [12, 5, 13, 7, -1, -1, 103]], [0, 2, 0, 4]], [[104], 5]], [[[[0, 5, 8, 13, 1, 4, -1], [0, 5, 1, 13, 2, 3, -1], [0, 5, 0, 6, -1, -1, 101], [1, 12, 1, 13, -1, -1, 104], [5, 8, 8, 13, 5, 6, -1], [5, 8, 7, 10, -1, -1, 102], [6, 12, 8, 13, 7, 8, -1], [6, 12, 7, 12, -1, -1, 103], [6, 12, 8, 13, -1, -1, 100]], [12, 3, 13, 6]], [[], 1]], [[[[1, 1, 13, 15, 1, 6, -1], [1, 1, 8, 11, 2, 3, -1], [1, 9, 4, 11, -1, -1, 100], [2, 1, 8, 5, 4, 5, -1], [2, 3, 4, 5, -1, -1, 104], [6, 1, 8, 3, -1, -1, 103], [6, 4, 13, 15, 7, 8, -1], [6, 4, 9, 6, -1, -1, 105], [10, 10, 13, 15, 9, 10, -1], [10, 12, 12, 15, -1, -1, 101], [10, 10, 13, 12, -1, -1, 102]], [1, 8, 5, 11]], [[100], 5]], [[[[0, 1, 13, 15, 1, 6, -1], [0, 6, 5, 15, 2, 3, -1], [0, 12, 0, 15, -1, -1, 100], [2, 6, 5, 12, 4, 5, -1], [2, 10, 5, 12, -1, -1, 103], [3, 6, 5, 8, -1, -1, 101], [8, 1, 13, 7, 7, 8, -1], [8, 1, 9, 4, -1, -1, 104], [9, 4, 13, 7, 9, 10, -1], [9, 5, 11, 7, -1, -1, 105], [11, 4, 13, 5, -1, -1, 102]], [3, 11, 6, 12]], [[103], 7]], [[[[3, 5, 10, 10, 1, 2, -1], [3, 5, 4, 7, -1, -1, 100], [4, 6, 10, 10, 3, 4, -1], [4, 10, 6, 10, -1, -1, 102], [8, 6, 10, 8, -1, -1, 101]], [3, 3, 6, 4]], [[], 1]], [[[[0, 1, 12, 12, 1, 2, -1], [0, 9, 3, 10, -1, -1, 102], [10, 1, 12, 12, 3, 4, -1], [10, 11, 10, 12, -1, -1, 101], [11, 1, 12, 4, -1, -1, 100]], [4, 10, 8, 10]], [[], 3]]], [[[[[4, 0, 10, 13, 1, 6, -1], [4, 5, 7, 12, 2, 3, -1], [4, 8, 4, 8, -1, -1, 103], [5, 5, 7, 12, 4, 5, -1], [5, 11, 5, 12, -1, -1, 105], [6, 5, 7, 8, -1, -1, 102], [7, 0, 10, 13, 7, 8, -1], [7, 0, 7, 2, -1, -1, 101], [8, 2, 10, 13, 9, 10, -1], [8, 2, 10, 2, -1, -1, 100], [9, 12, 10, 13, -1, -1, 104]], [3, 9, 5, 13]], [[105], 7]], [[[[9, 4, 14, 10, 1, 4, -1], [9, 8, 12, 10, 2, 3, -1], [9, 9, 12, 10, -1, -1, 101], [10, 8, 11, 9, -1, -1, 102], [9, 4, 14, 10, 5, 6, -1], [9, 10, 12, 10, -1, -1, 103], [12, 4, 14, 4, -1, -1, 100]], [7, 5, 7, 8]], [[], 1]], [[[[2, 3, 15, 14, 1, 8, -1], [2, 3, 11, 12, 2, 5, -1], [2, 5, 10, 12, 3, 4, -1], [2, 5, 3, 7, -1, -1, 100], [8, 12, 10, 12, -1, -1, 105], [8, 3, 11, 6, 6, 7, -1], [8, 3, 11, 3, -1, -1, 101], [11, 4, 11, 6, -1, -1, 102], [12, 4, 15, 14, 9, 12, -1], [12, 4, 13, 14, 10, 11, -1], [12, 11, 13, 14, -1, -1, 103], [12, 4, 13, 6, -1, -1, 104], [12, 5, 15, 10, 13, 14, -1], [12, 5, 13, 7, -1, -1, 107], [12, 7, 15, 10, -1, -1, 106]], [3, 2, 3, 2]], [[], 1]], [[[[0, 0, 12, 11, 1, 4, -1], [0, 6, 3, 11, 2, 3, -1], [1, 10, 1, 11, -1, -1, 101], [0, 6, 3, 8, -1, -1, 104], [5, 0, 12, 4, 5, 6, -1], [5, 1, 5, 3, -1, -1, 103], [8, 0, 12, 4, 7, 8, -1], [8, 0, 9, 0, -1, -1, 102], [11, 4, 12, 4, -1, -1, 100]], [11, 9, 14, 11]], [[], 3]], [[[[1, 3, 12, 12, 1, 6, -1], [1, 4, 6, 6, 2, 3, -1], [1, 5, 1, 6, -1, -1, 103], [5, 4, 6, 6, 4, 5, -1], [5, 4, 6, 5, -1, -1, 100], [6, 5, 6, 6, -1, -1, 104], [7, 3, 12, 12, 7, 8, -1], [7, 3, 9, 6, -1, -1, 105], [8, 3, 12, 12, 9, 10, -1], [8, 10, 10, 12, -1, -1, 101], [11, 3, 12, 6, -1, -1, 102]], [9, 6, 13, 6]], [[102, 105], 7]], [[[[1, 0, 12, 14, 1, 4, -1], [1, 2, 3, 5, 2, 3, -1], [2, 2, 2, 2, -1, -1, 101], [1, 3, 3, 5, -1, -1, 102], [2, 0, 12, 14, 5, 6, -1], [2, 6, 4, 8, -1, -1, 104], [3, 0, 12, 14, 7, 8, -1], [3, 12, 4, 14, -1, -1, 100], [11, 0, 12, 0, -1, -1, 103]], [11, 10, 14, 13]], [[], 7]], [[[[1, 0, 12, 11, 1, 6, -1], [1, 0, 4, 11, 2, 3, -1], [1, 0, 2, 0, -1, -1, 100], [2, 7, 4, 11, 4, 5, -1], [2, 7, 2, 7, -1, -1, 105], [3, 11, 4, 11, -1, -1, 104], [5, 4, 12, 8, 7, 8, -1], [5, 6, 5, 8, -1, -1, 102], [6, 4, 12, 6, 9, 10, -1], [6, 4, 8, 6, -1, -1, 101], [10, 4, 12, 4, -1, -1, 103]], [6, 7, 7, 7]], [[], 5]], [[[[0, 5, 14, 14, 1, 6, -1], [0, 5, 5, 14, 2, 3, -1], [0, 5, 0, 8, -1, -1, 105], [2, 8, 5, 14, 4, 5, -1], [2, 12, 3, 14, -1, -1, 103], [4, 8, 5, 9, -1, -1, 102], [6, 11, 14, 12, 7, 8, -1], [6, 11, 9, 11, -1, -1, 101], [10, 11, 14, 12, 9, 10, -1], [10, 11, 13, 11, -1, -1, 100], [11, 12, 14, 12, -1, -1, 104]], [2, 2, 5, 6]], [[], 5]]], [[[[[4, 2, 6, 13, 1, 2, -1], [4, 11, 6, 13, -1, -1, 100], [4, 2, 6, 8, 3, 4, -1], [4, 2, 6, 4, -1, -1, 102], [6, 6, 6, 8, -1, -1, 101]], [11, 12, 11, 13]], [[], 1]], [[[[0, 0, 14, 11, 1, 8, -1], [0, 4, 2, 11, 2, 5, -1], [0, 6, 2, 9, 3, 4, -1], [0, 6, 1, 9, -1, -1, 106], [0, 9, 2, 9, -1, -1, 104], [1, 4, 2, 11, 6, 7, -1], [1, 8, 2, 11, -1, -1, 101], [1, 4, 2, 6, -1, -1, 107], [2, 0, 14, 11, 9, 12, -1], [2, 0, 6, 11, 10, 11, -1], [2, 0, 4, 1, -1, -1, 105], [6, 10, 6, 11, -1, -1, 100], [8, 1, 14, 10, 13, 14, -1], [8, 2, 9, 4, -1, -1, 103], [9, 1, 14, 10, 15, 16, -1], [9, 9, 12, 10, -1, -1, 108], [11, 1, 14, 1, -1, -1, 102]], [4, 6, 5, 7]], [[], 7]], [[[[7, 6, 14, 12, 1, 4, -1], [7, 6, 9, 8, 2, 3, -1], [7, 6, 8, 8, -1, -1, 102], [7, 7, 9, 7, -1, -1, 103], [10, 7, 14, 12, 5, 6, -1], [10, 10, 13, 12, -1, -1, 101], [11, 7, 14, 7, -1, -1, 100]], [11, 6, 12, 10]], [[100, 101], 5]], [[[[0, 0, 11, 14, 1, 8, -1], [0, 1, 8, 10, 2, 5, -1], [0, 4, 3, 9, 3, 4, -1], [0, 4, 1, 4, -1, -1, 101], [3, 9, 3, 9, -1, -1, 106], [3, 1, 8, 10, 6, 7, -1], [3, 10, 6, 10, -1, -1, 104], [7, 1, 8, 4, -1, -1, 103], [8, 0, 11, 14, 9, 12, -1], [8, 0, 11, 14, 10, 11, -1], [8, 11, 10, 14, -1, -1, 107], [8, 0, 11, 3, -1, -1, 100], [9, 8, 11, 14, 13, 14, -1], [9, 8, 10, 8, -1, -1, 105], [11, 11, 11, 14, -1, -1, 102]], [12, 2, 14, 4]], [[], 1]], [[[[2, 0, 14, 14, 1, 8, -1], [2, 4, 5, 14, 2, 5, -1], [2, 5, 4, 12, 3, 4, -1], [2, 11, 2, 12, -1, -1, 106], [4, 5, 4, 5, -1, -1, 102], [4, 4, 5, 14, 6, 7, -1], [4, 4, 5, 7, -1, -1, 107], [5, 12, 5, 14, -1, -1, 105], [7, 0, 14, 8, 9, 12, -1], [7, 0, 10, 3, 10, 11, -1], [7, 0, 7, 3, -1, -1, 104], [8, 1, 10, 2, -1, -1, 101], [8, 0, 14, 8, 13, 14, -1], [8, 5, 11, 8, -1, -1, 100], [12, 0, 14, 3, -1, -1, 103]], [6, 0, 8, 1]], [[101, 104], 9]], [[[[10, 2, 11, 5, -1, -1, 100]], [0, 11, 3, 14]], [[], 1]], [[[[0, 0, 15, 14, 1, 8, -1], [0, 7, 7, 14, 2, 5, -1], [0, 7, 2, 13, 3, 4, -1], [0, 11, 2, 13, -1, -1, 106], [1, 7, 1, 10, -1, -1, 107], [6, 10, 7, 14, 6, 7, -1], [6, 10, 6, 11, -1, -1, 105], [6, 11, 7, 14, -1, -1, 104], [8, 0, 15, 11, 9, 12, -1], [8, 6, 13, 11, 10, 11, -1], [8, 9, 10, 11, -1, -1, 103], [11, 6, 13, 9, -1, -1, 100], [11, 0, 15, 9, 13, 14, -1], [11, 0, 13, 0, -1, -1, 102], [12, 9, 15, 9, -1, -1, 101]], [10, 4, 11, 7]], [[100], 9]], [[[[2, 0, 14, 13, 1, 8, -1], [2, 1, 7, 13, 2, 5, -1], [2, 1, 4, 7, 3, 4, -1], [2, 1, 2, 3, -1, -1, 104], [2, 5, 4, 7, -1, -1, 101], [4, 4, 7, 13, 6, 7, -1], [4, 11, 5, 13, -1, -1, 103], [7, 4, 7, 4, -1, -1, 102], [8, 0, 14, 10, 9, 12, -1], [8, 4, 9, 4, 10, 11, -1], [8, 4, 8, 4, -1, -1, 100], [8, 4, 9, 4, -1, -1, 105], [10, 0, 14, 10, 13, 14, -1], [10, 8, 12, 10, -1, -1, 107], [11, 0, 14, 5, 15, 16, -1], [11, 0, 12, 2, -1, -1, 106], [12, 4, 14, 5, -1, -1, 108]], [12, 12, 14, 16]], [[], 3]]], [[[[[0, 1, 14, 13, 1, 10, -1], [0, 1, 3, 13, 2, 5, -1], [0, 2, 2, 13, 3, 4, -1], [0, 11, 1, 13, -1, -1, 104], [0, 2, 2, 2, -1, -1, 106], [0, 1, 3, 12, 6, 7, -1], [0, 11, 3, 12, -1, -1, 102], [1, 1, 3, 7, 8, 9, -1], [1, 1, 3, 2, -1, -1, 107], [3, 4, 3, 7, -1, -1, 109], [4, 3, 14, 12, 11, 14, -1], [4, 7, 7, 10, 12, 13, -1], [4, 8, 5, 10, -1, -1, 101], [4, 7, 7, 9, -1, -1, 105], [8, 3, 14, 12, 15, 16, -1], [8, 10, 11, 12, -1, -1, 108], [11, 3, 14, 8, 17, 18, -1], [11, 7, 13, 8, -1, -1, 103], [11, 3, 14, 4, -1, -1, 100]], [8, 3, 8, 7]], [[], 7]], [[[[5, 0, 6, 10, 1, 2, -1], [5, 0, 5, 0, -1, -1, 101], [6, 7, 6, 10, -1, -1, 100]], [9, 9, 13, 13]], [[], 1]], [[[[5, 4, 7, 4, -1, -1, 100]], [10, 7, 10, 11]], [[], 1]], [[[[1, 0, 15, 13, 1, 8, -1], [1, 2, 4, 8, 2, 5, -1], [1, 5, 3, 8, 3, 4, -1], [1, 5, 3, 7, -1, -1, 101], [1, 6, 3, 8, -1, -1, 106], [1, 2, 4, 4, 6, 7, -1], [1, 2, 4, 2, -1, -1, 103], [4, 3, 4, 4, -1, -1, 104], [3, 0, 15, 13, 9, 12, -1], [3, 0, 6, 3, 10, 11, -1], [3, 1, 6, 2, -1, -1, 108], [5, 0, 5, 3, -1, -1, 105], [9, 9, 15, 13, 13, 14, -1], [9, 11, 10, 13, -1, -1, 102], [12, 9, 15, 11, 15, 16, -1], [12, 9, 13, 10, -1, -1, 100], [12, 10, 15, 11, -1, -1, 107]], [6, 10, 6, 13]], [[], 5]], [[[[2, 1, 7, 8, 1, 2, -1], [2, 1, 5, 2, -1, -1, 101], [4, 5, 7, 8, 3, 4, -1], [4, 6, 7, 8, -1, -1, 102], [5, 5, 7, 8, -1, -1, 100]], [5, 9, 6, 12]], [[], 1]], [[[[8, 5, 9, 12, 1, 2, -1], [8, 10, 9, 12, -1, -1, 100], [8, 5, 9, 5, -1, -1, 101]], [5, 7, 5, 9]], [[], 1]], [[[[1, 1, 12, 13, 1, 6, -1], [1, 1, 7, 13, 2, 3, -1], [1, 11, 2, 13, -1, -1, 102], [4, 1, 7, 13, 4, 5, -1], [5, 1, 5, 3, -1, -1, 104], [4, 11, 7, 13, -1, -1, 103], [5, 1, 12, 6, 7, 8, -1], [5, 1, 7, 2, -1, -1, 101], [10, 2, 12, 6, 9, 10, -1], [10, 6, 12, 6, -1, -1, 100], [12, 2, 12, 4, -1, -1, 105]], [6, 6, 8, 9]], [[], 9]], [[[[0, 0, 14, 14, 1, 6, -1], [0, 4, 6, 14, 2, 3, -1], [0, 4, 0, 5, -1, -1, 102], [1, 7, 6, 14, 4, 5, -1], [1, 7, 1, 8, -1, -1, 103], [6, 11, 6, 14, -1, -1, 104], [8, 0, 14, 14, 7, 10, -1], [8, 0, 11, 7, 8, 9, -1], [8, 5, 11, 7, -1, -1, 101], [9, 0, 11, 3, -1, -1, 100], [11, 6, 14, 14, 11, 12, -1], [11, 6, 14, 8, -1, -1, 106], [12, 12, 14, 14, -1, -1, 105]], [12, 9, 15, 9]], [[], 7]]], [[[[[8, 0, 13, 15, 1, 4, -1], [8, 4, 12, 15, 2, 3, -1], [8, 12, 9, 15, -1, -1, 100], [9, 4, 12, 4, -1, -1, 101], [10, 0, 13, 11, 5, 6, -1], [10, 8, 12, 11, -1, -1, 102], [11, 0, 13, 3, -1, -1, 103]], [2, 0, 5, 1]], [[], 1]], [[[[3, 3, 12, 13, 1, 6, -1], [3, 8, 8, 13, 2, 3, -1], [3, 10, 6, 13, -1, -1, 104], [5, 8, 8, 11, 4, 5, -1], [5, 9, 5, 9, -1, -1, 101], [5, 8, 8, 11, -1, -1, 100], [6, 3, 12, 11, 7, 8, -1], [6, 8, 8, 11, -1, -1, 103], [9, 3, 12, 11, 9, 10, -1], [9, 8, 12, 11, -1, -1, 105], [11, 3, 11, 5, -1, -1, 102]], [11, 11, 14, 12]], [[105], 7]], [[[[0, 0, 8, 14, 1, 4, -1], [0, 0, 2, 3, 2, 3, -1], [0, 0, 2, 2, -1, -1, 101], [0, 0, 2, 3, -1, -1, 104], [0, 9, 8, 14, 5, 6, -1], [0, 9, 3, 12, -1, -1, 102], [6, 12, 8, 14, 7, 8, -1], [6, 12, 6, 14, -1, -1, 103], [6, 12, 8, 14, -1, -1, 100]], [5, 9, 9, 11]], [[], 5]], [[[[0, 2, 13, 12, 1, 4, -1], [0, 5, 5, 8, 2, 3, -1], [0, 5, 1, 7, -1, -1, 103], [2, 8, 5, 8, -1, -1, 104], [8, 2, 13, 12, 5, 6, -1], [8, 11, 11, 12, -1, -1, 100], [11, 2, 13, 5, 7, 8, -1], [11, 2, 13, 2, -1, -1, 101], [12, 4, 12, 5, -1, -1, 102]], [8, 4, 10, 7]], [[], 5]], [[[[0, 0, 15, 15, 1, 10, -1], [0, 0, 11, 14, 2, 5, -1], [0, 5, 1, 14, 3, 4, -1], [0, 5, 0, 8, -1, -1, 110], [1, 12, 1, 14, -1, -1, 105], [8, 0, 11, 10, 6, 7, -1], [8, 1, 10, 2, -1, -1, 102], [8, 0, 11, 10, 8, 9, -1], [8, 0, 10, 1, -1, -1, 108], [8, 8, 11, 10, -1, -1, 101], [10, 2, 15, 15, 11, 16, -1], [10, 6, 12, 15, 12, 13, -1], [10, 6, 12, 7, -1, -1, 104], [10, 11, 12, 15, 14, 15, -1], [10, 11, 12, 14, -1, -1, 106], [11, 12, 12, 15, -1, -1, 100], [11, 2, 15, 11, 17, 18, -1], [11, 11, 13, 11, -1, -1, 109], [11, 2, 15, 7, 19, 20, -1], [11, 7, 14, 7, -1, -1, 103], [12, 2, 15, 5, -1, -1, 107]], [10, 9, 10, 12]], [[101, 106], 15]], [[[[1, 0, 11, 11, 1, 6, -1], [1, 4, 6, 11, 2, 3, -1], [1, 9, 1, 11, -1, -1, 105], [2, 4, 6, 10, 4, 5, -1], [2, 4, 2, 5, -1, -1, 104], [6, 9, 6, 10, -1, -1, 100], [6, 0, 11, 8, 7, 8, -1], [6, 8, 8, 8, -1, -1, 102], [7, 0, 11, 4, 9, 10, -1], [7, 3, 9, 4, -1, -1, 101], [9, 0, 11, 1, -1, -1, 103]], [9, 9, 10, 9]], [[], 3]], [[[[0, 2, 13, 14, 1, 10, -1], [0, 4, 4, 14, 2, 5, -1], [0, 5, 1, 14, 3, 4, -1], [0, 12, 0, 14, -1, -1, 100], [0, 5, 1, 6, -1, -1, 105], [1, 4, 4, 12, 6, 7, -1], [1, 8, 1, 8, -1, -1, 102], [1, 4, 4, 12, 8, 9, -1], [1, 9, 2, 12, -1, -1, 106], [4, 4, 4, 7, -1, -1, 101], [6, 2, 13, 12, 11, 14, -1], [6, 9, 8, 12, 12, 13, -1], [6, 9, 7, 12, -1, -1, 103], [7, 9, 8, 9, -1, -1, 107], [6, 2, 13, 5, 15, 16, -1], [6, 3, 9, 3, -1, -1, 109], [11, 2, 13, 5, 17, 18, -1], [11, 2, 12, 5, -1, -1, 108], [11, 2, 13, 2, -1, -1, 104]], [8, 4, 10, 6]], [[], 7]], [[[[0, 2, 8, 11, 1, 6, -1], [0, 2, 4, 10, 2, 3, -1], [0, 7, 0, 10, -1, -1, 103], [0, 2, 4, 8, 4, 5, -1], [0, 2, 1, 2, -1, -1, 100], [4, 8, 4, 8, -1, -1, 102], [5, 4, 8, 11, 7, 8, -1], [6, 6, 6, 9, -1, -1, 101], [5, 4, 8, 11, 9, 10, -1], [5, 8, 8, 11, -1, -1, 105], [7, 4, 8, 7, -1, -1, 104]], [7, 1, 9, 2]], [[], 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	`[[], 3]`	`[[], 3]`	Passed
case 1	`[[100, 101, 102, 106], 5]`	`[[100, 101], 9]`	Failed
case 2	`[[104], 4]`	`[[104], 5]`	Failed
case 3	`[[], 1]`	`[[], 1]`	Passed
case 4	`[[100], 4]`	`[[100], 5]`	Failed
case 5	`[[100, 101, 103], 4]`	`[[103], 7]`	Failed
case 6	`[[], 1]`	`[[], 1]`	Passed
case 7	`[[102], 2]`	`[[], 3]`	Failed

SHA-256 / 15b2e50198be0c16d0882b925c51ba165c381892c491101f69ff0a171b3638df

2 / The unsuccessful fix

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(nodes, q):
    if not nodes:
        return [[], 0]
    stack = [0]
    hits = []
    tests = 0
    while stack:
        i = stack.pop()
        nd = nodes[i]
        tests += 1 if nd[4] >= 0 else 0
        if not (nd[0] <= q[2] and q[0] <= nd[2] and nd[1] <= q[3] and q[1] <= nd[3]):
            continue
        if nd[4] < 0:
            hits.append(nd[6])
        else:
            stack.append(nd[4])
            stack.append(nd[5])
    return [sorted(hits), tests]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[[[[[0, 2, 12, 12, 1, 4, -1], [0, 2, 7, 4, 2, 3, -1], [0, 4, 2, 4, -1, -1, 100], [5, 2, 7, 2, -1, -1, 103], [8, 4, 12, 12, 5, 6, -1], [8, 4, 9, 6, -1, -1, 104], [10, 6, 12, 12, 7, 8, -1], [11, 10, 11, 12, -1, -1, 101], [10, 6, 12, 8, -1, -1, 102]], [6, 5, 7, 7]], [[], 3]], [[[[2, 1, 11, 12, 1, 6, -1], [2, 1, 6, 5, 2, 3, -1], [2, 1, 5, 3, -1, -1, 104], [5, 2, 6, 5, 4, 5, -1], [5, 2, 5, 5, -1, -1, 103], [6, 3, 6, 3, -1, -1, 105], [6, 1, 11, 12, 7, 10, -1], [6, 1, 8, 12, 8, 9, -1], [6, 11, 7, 12, -1, -1, 102], [6, 1, 8, 2, -1, -1, 106], [9, 6, 11, 8, 11, 12, -1], [9, 6, 9, 7, -1, -1, 101], [10, 6, 11, 8, -1, -1, 100]], [7, 6, 10, 9]], [[100, 101], 9]], [[[[0, 4, 13, 14, 1, 6, -1], [0, 4, 5, 14, 2, 3, -1], [0, 4, 1, 4, -1, -1, 104], [1, 6, 5, 14, 4, 5, -1], [1, 6, 3, 7, -1, -1, 102], [2, 12, 5, 14, -1, -1, 105], [6, 4, 13, 13, 7, 10, -1], [6, 11, 8, 13, 8, 9, -1], [6, 11, 8, 13, -1, -1, 101], [7, 11, 8, 11, -1, -1, 100], [7, 4, 13, 7, 11, 12, -1], [7, 4, 8, 4, -1, -1, 106], [12, 5, 13, 7, -1, -1, 103]], [0, 2, 0, 4]], [[104], 5]], [[[[0, 5, 8, 13, 1, 4, -1], [0, 5, 1, 13, 2, 3, -1], [0, 5, 0, 6, -1, -1, 101], [1, 12, 1, 13, -1, -1, 104], [5, 8, 8, 13, 5, 6, -1], [5, 8, 7, 10, -1, -1, 102], [6, 12, 8, 13, 7, 8, -1], [6, 12, 7, 12, -1, -1, 103], [6, 12, 8, 13, -1, -1, 100]], [12, 3, 13, 6]], [[], 1]], [[[[1, 1, 13, 15, 1, 6, -1], [1, 1, 8, 11, 2, 3, -1], [1, 9, 4, 11, -1, -1, 100], [2, 1, 8, 5, 4, 5, -1], [2, 3, 4, 5, -1, -1, 104], [6, 1, 8, 3, -1, -1, 103], [6, 4, 13, 15, 7, 8, -1], [6, 4, 9, 6, -1, -1, 105], [10, 10, 13, 15, 9, 10, -1], [10, 12, 12, 15, -1, -1, 101], [10, 10, 13, 12, -1, -1, 102]], [1, 8, 5, 11]], [[100], 5]], [[[[0, 1, 13, 15, 1, 6, -1], [0, 6, 5, 15, 2, 3, -1], [0, 12, 0, 15, -1, -1, 100], [2, 6, 5, 12, 4, 5, -1], [2, 10, 5, 12, -1, -1, 103], [3, 6, 5, 8, -1, -1, 101], [8, 1, 13, 7, 7, 8, -1], [8, 1, 9, 4, -1, -1, 104], [9, 4, 13, 7, 9, 10, -1], [9, 5, 11, 7, -1, -1, 105], [11, 4, 13, 5, -1, -1, 102]], [3, 11, 6, 12]], [[103], 7]], [[[[3, 5, 10, 10, 1, 2, -1], [3, 5, 4, 7, -1, -1, 100], [4, 6, 10, 10, 3, 4, -1], [4, 10, 6, 10, -1, -1, 102], [8, 6, 10, 8, -1, -1, 101]], [3, 3, 6, 4]], [[], 1]], [[[[0, 1, 12, 12, 1, 2, -1], [0, 9, 3, 10, -1, -1, 102], [10, 1, 12, 12, 3, 4, -1], [10, 11, 10, 12, -1, -1, 101], [11, 1, 12, 4, -1, -1, 100]], [4, 10, 8, 10]], [[], 3]]], [[[[[4, 0, 10, 13, 1, 6, -1], [4, 5, 7, 12, 2, 3, -1], [4, 8, 4, 8, -1, -1, 103], [5, 5, 7, 12, 4, 5, -1], [5, 11, 5, 12, -1, -1, 105], [6, 5, 7, 8, -1, -1, 102], [7, 0, 10, 13, 7, 8, -1], [7, 0, 7, 2, -1, -1, 101], [8, 2, 10, 13, 9, 10, -1], [8, 2, 10, 2, -1, -1, 100], [9, 12, 10, 13, -1, -1, 104]], [3, 9, 5, 13]], [[105], 7]], [[[[9, 4, 14, 10, 1, 4, -1], [9, 8, 12, 10, 2, 3, -1], [9, 9, 12, 10, -1, -1, 101], [10, 8, 11, 9, -1, -1, 102], [9, 4, 14, 10, 5, 6, -1], [9, 10, 12, 10, -1, -1, 103], [12, 4, 14, 4, -1, -1, 100]], [7, 5, 7, 8]], [[], 1]], [[[[2, 3, 15, 14, 1, 8, -1], [2, 3, 11, 12, 2, 5, -1], [2, 5, 10, 12, 3, 4, -1], [2, 5, 3, 7, -1, -1, 100], [8, 12, 10, 12, -1, -1, 105], [8, 3, 11, 6, 6, 7, -1], [8, 3, 11, 3, -1, -1, 101], [11, 4, 11, 6, -1, -1, 102], [12, 4, 15, 14, 9, 12, -1], [12, 4, 13, 14, 10, 11, -1], [12, 11, 13, 14, -1, -1, 103], [12, 4, 13, 6, -1, -1, 104], [12, 5, 15, 10, 13, 14, -1], [12, 5, 13, 7, -1, -1, 107], [12, 7, 15, 10, -1, -1, 106]], [3, 2, 3, 2]], [[], 1]], [[[[0, 0, 12, 11, 1, 4, -1], [0, 6, 3, 11, 2, 3, -1], [1, 10, 1, 11, -1, -1, 101], [0, 6, 3, 8, -1, -1, 104], [5, 0, 12, 4, 5, 6, -1], [5, 1, 5, 3, -1, -1, 103], [8, 0, 12, 4, 7, 8, -1], [8, 0, 9, 0, -1, -1, 102], [11, 4, 12, 4, -1, -1, 100]], [11, 9, 14, 11]], [[], 3]], [[[[1, 3, 12, 12, 1, 6, -1], [1, 4, 6, 6, 2, 3, -1], [1, 5, 1, 6, -1, -1, 103], [5, 4, 6, 6, 4, 5, -1], [5, 4, 6, 5, -1, -1, 100], [6, 5, 6, 6, -1, -1, 104], [7, 3, 12, 12, 7, 8, -1], [7, 3, 9, 6, -1, -1, 105], [8, 3, 12, 12, 9, 10, -1], [8, 10, 10, 12, -1, -1, 101], [11, 3, 12, 6, -1, -1, 102]], [9, 6, 13, 6]], [[102, 105], 7]], [[[[1, 0, 12, 14, 1, 4, -1], [1, 2, 3, 5, 2, 3, -1], [2, 2, 2, 2, -1, -1, 101], [1, 3, 3, 5, -1, -1, 102], [2, 0, 12, 14, 5, 6, -1], [2, 6, 4, 8, -1, -1, 104], [3, 0, 12, 14, 7, 8, -1], [3, 12, 4, 14, -1, -1, 100], [11, 0, 12, 0, -1, -1, 103]], [11, 10, 14, 13]], [[], 7]], [[[[1, 0, 12, 11, 1, 6, -1], [1, 0, 4, 11, 2, 3, -1], [1, 0, 2, 0, -1, -1, 100], [2, 7, 4, 11, 4, 5, -1], [2, 7, 2, 7, -1, -1, 105], [3, 11, 4, 11, -1, -1, 104], [5, 4, 12, 8, 7, 8, -1], [5, 6, 5, 8, -1, -1, 102], [6, 4, 12, 6, 9, 10, -1], [6, 4, 8, 6, -1, -1, 101], [10, 4, 12, 4, -1, -1, 103]], [6, 7, 7, 7]], [[], 5]], [[[[0, 5, 14, 14, 1, 6, -1], [0, 5, 5, 14, 2, 3, -1], [0, 5, 0, 8, -1, -1, 105], [2, 8, 5, 14, 4, 5, -1], [2, 12, 3, 14, -1, -1, 103], [4, 8, 5, 9, -1, -1, 102], [6, 11, 14, 12, 7, 8, -1], [6, 11, 9, 11, -1, -1, 101], [10, 11, 14, 12, 9, 10, -1], [10, 11, 13, 11, -1, -1, 100], [11, 12, 14, 12, -1, -1, 104]], [2, 2, 5, 6]], [[], 5]]], [[[[[4, 2, 6, 13, 1, 2, -1], [4, 11, 6, 13, -1, -1, 100], [4, 2, 6, 8, 3, 4, -1], [4, 2, 6, 4, -1, -1, 102], [6, 6, 6, 8, -1, -1, 101]], [11, 12, 11, 13]], [[], 1]], [[[[0, 0, 14, 11, 1, 8, -1], [0, 4, 2, 11, 2, 5, -1], [0, 6, 2, 9, 3, 4, -1], [0, 6, 1, 9, -1, -1, 106], [0, 9, 2, 9, -1, -1, 104], [1, 4, 2, 11, 6, 7, -1], [1, 8, 2, 11, -1, -1, 101], [1, 4, 2, 6, -1, -1, 107], [2, 0, 14, 11, 9, 12, -1], [2, 0, 6, 11, 10, 11, -1], [2, 0, 4, 1, -1, -1, 105], [6, 10, 6, 11, -1, -1, 100], [8, 1, 14, 10, 13, 14, -1], [8, 2, 9, 4, -1, -1, 103], [9, 1, 14, 10, 15, 16, -1], [9, 9, 12, 10, -1, -1, 108], [11, 1, 14, 1, -1, -1, 102]], [4, 6, 5, 7]], [[], 7]], [[[[7, 6, 14, 12, 1, 4, -1], [7, 6, 9, 8, 2, 3, -1], [7, 6, 8, 8, -1, -1, 102], [7, 7, 9, 7, -1, -1, 103], [10, 7, 14, 12, 5, 6, -1], [10, 10, 13, 12, -1, -1, 101], [11, 7, 14, 7, -1, -1, 100]], [11, 6, 12, 10]], [[100, 101], 5]], [[[[0, 0, 11, 14, 1, 8, -1], [0, 1, 8, 10, 2, 5, -1], [0, 4, 3, 9, 3, 4, -1], [0, 4, 1, 4, -1, -1, 101], [3, 9, 3, 9, -1, -1, 106], [3, 1, 8, 10, 6, 7, -1], [3, 10, 6, 10, -1, -1, 104], [7, 1, 8, 4, -1, -1, 103], [8, 0, 11, 14, 9, 12, -1], [8, 0, 11, 14, 10, 11, -1], [8, 11, 10, 14, -1, -1, 107], [8, 0, 11, 3, -1, -1, 100], [9, 8, 11, 14, 13, 14, -1], [9, 8, 10, 8, -1, -1, 105], [11, 11, 11, 14, -1, -1, 102]], [12, 2, 14, 4]], [[], 1]], [[[[2, 0, 14, 14, 1, 8, -1], [2, 4, 5, 14, 2, 5, -1], [2, 5, 4, 12, 3, 4, -1], [2, 11, 2, 12, -1, -1, 106], [4, 5, 4, 5, -1, -1, 102], [4, 4, 5, 14, 6, 7, -1], [4, 4, 5, 7, -1, -1, 107], [5, 12, 5, 14, -1, -1, 105], [7, 0, 14, 8, 9, 12, -1], [7, 0, 10, 3, 10, 11, -1], [7, 0, 7, 3, -1, -1, 104], [8, 1, 10, 2, -1, -1, 101], [8, 0, 14, 8, 13, 14, -1], [8, 5, 11, 8, -1, -1, 100], [12, 0, 14, 3, -1, -1, 103]], [6, 0, 8, 1]], [[101, 104], 9]], [[[[10, 2, 11, 5, -1, -1, 100]], [0, 11, 3, 14]], [[], 1]], [[[[0, 0, 15, 14, 1, 8, -1], [0, 7, 7, 14, 2, 5, -1], [0, 7, 2, 13, 3, 4, -1], [0, 11, 2, 13, -1, -1, 106], [1, 7, 1, 10, -1, -1, 107], [6, 10, 7, 14, 6, 7, -1], [6, 10, 6, 11, -1, -1, 105], [6, 11, 7, 14, -1, -1, 104], [8, 0, 15, 11, 9, 12, -1], [8, 6, 13, 11, 10, 11, -1], [8, 9, 10, 11, -1, -1, 103], [11, 6, 13, 9, -1, -1, 100], [11, 0, 15, 9, 13, 14, -1], [11, 0, 13, 0, -1, -1, 102], [12, 9, 15, 9, -1, -1, 101]], [10, 4, 11, 7]], [[100], 9]], [[[[2, 0, 14, 13, 1, 8, -1], [2, 1, 7, 13, 2, 5, -1], [2, 1, 4, 7, 3, 4, -1], [2, 1, 2, 3, -1, -1, 104], [2, 5, 4, 7, -1, -1, 101], [4, 4, 7, 13, 6, 7, -1], [4, 11, 5, 13, -1, -1, 103], [7, 4, 7, 4, -1, -1, 102], [8, 0, 14, 10, 9, 12, -1], [8, 4, 9, 4, 10, 11, -1], [8, 4, 8, 4, -1, -1, 100], [8, 4, 9, 4, -1, -1, 105], [10, 0, 14, 10, 13, 14, -1], [10, 8, 12, 10, -1, -1, 107], [11, 0, 14, 5, 15, 16, -1], [11, 0, 12, 2, -1, -1, 106], [12, 4, 14, 5, -1, -1, 108]], [12, 12, 14, 16]], [[], 3]]], [[[[[0, 1, 14, 13, 1, 10, -1], [0, 1, 3, 13, 2, 5, -1], [0, 2, 2, 13, 3, 4, -1], [0, 11, 1, 13, -1, -1, 104], [0, 2, 2, 2, -1, -1, 106], [0, 1, 3, 12, 6, 7, -1], [0, 11, 3, 12, -1, -1, 102], [1, 1, 3, 7, 8, 9, -1], [1, 1, 3, 2, -1, -1, 107], [3, 4, 3, 7, -1, -1, 109], [4, 3, 14, 12, 11, 14, -1], [4, 7, 7, 10, 12, 13, -1], [4, 8, 5, 10, -1, -1, 101], [4, 7, 7, 9, -1, -1, 105], [8, 3, 14, 12, 15, 16, -1], [8, 10, 11, 12, -1, -1, 108], [11, 3, 14, 8, 17, 18, -1], [11, 7, 13, 8, -1, -1, 103], [11, 3, 14, 4, -1, -1, 100]], [8, 3, 8, 7]], [[], 7]], [[[[5, 0, 6, 10, 1, 2, -1], [5, 0, 5, 0, -1, -1, 101], [6, 7, 6, 10, -1, -1, 100]], [9, 9, 13, 13]], [[], 1]], [[[[5, 4, 7, 4, -1, -1, 100]], [10, 7, 10, 11]], [[], 1]], [[[[1, 0, 15, 13, 1, 8, -1], [1, 2, 4, 8, 2, 5, -1], [1, 5, 3, 8, 3, 4, -1], [1, 5, 3, 7, -1, -1, 101], [1, 6, 3, 8, -1, -1, 106], [1, 2, 4, 4, 6, 7, -1], [1, 2, 4, 2, -1, -1, 103], [4, 3, 4, 4, -1, -1, 104], [3, 0, 15, 13, 9, 12, -1], [3, 0, 6, 3, 10, 11, -1], [3, 1, 6, 2, -1, -1, 108], [5, 0, 5, 3, -1, -1, 105], [9, 9, 15, 13, 13, 14, -1], [9, 11, 10, 13, -1, -1, 102], [12, 9, 15, 11, 15, 16, -1], [12, 9, 13, 10, -1, -1, 100], [12, 10, 15, 11, -1, -1, 107]], [6, 10, 6, 13]], [[], 5]], [[[[2, 1, 7, 8, 1, 2, -1], [2, 1, 5, 2, -1, -1, 101], [4, 5, 7, 8, 3, 4, -1], [4, 6, 7, 8, -1, -1, 102], [5, 5, 7, 8, -1, -1, 100]], [5, 9, 6, 12]], [[], 1]], [[[[8, 5, 9, 12, 1, 2, -1], [8, 10, 9, 12, -1, -1, 100], [8, 5, 9, 5, -1, -1, 101]], [5, 7, 5, 9]], [[], 1]], [[[[1, 1, 12, 13, 1, 6, -1], [1, 1, 7, 13, 2, 3, -1], [1, 11, 2, 13, -1, -1, 102], [4, 1, 7, 13, 4, 5, -1], [5, 1, 5, 3, -1, -1, 104], [4, 11, 7, 13, -1, -1, 103], [5, 1, 12, 6, 7, 8, -1], [5, 1, 7, 2, -1, -1, 101], [10, 2, 12, 6, 9, 10, -1], [10, 6, 12, 6, -1, -1, 100], [12, 2, 12, 4, -1, -1, 105]], [6, 6, 8, 9]], [[], 9]], [[[[0, 0, 14, 14, 1, 6, -1], [0, 4, 6, 14, 2, 3, -1], [0, 4, 0, 5, -1, -1, 102], [1, 7, 6, 14, 4, 5, -1], [1, 7, 1, 8, -1, -1, 103], [6, 11, 6, 14, -1, -1, 104], [8, 0, 14, 14, 7, 10, -1], [8, 0, 11, 7, 8, 9, -1], [8, 5, 11, 7, -1, -1, 101], [9, 0, 11, 3, -1, -1, 100], [11, 6, 14, 14, 11, 12, -1], [11, 6, 14, 8, -1, -1, 106], [12, 12, 14, 14, -1, -1, 105]], [12, 9, 15, 9]], [[], 7]]], [[[[[8, 0, 13, 15, 1, 4, -1], [8, 4, 12, 15, 2, 3, -1], [8, 12, 9, 15, -1, -1, 100], [9, 4, 12, 4, -1, -1, 101], [10, 0, 13, 11, 5, 6, -1], [10, 8, 12, 11, -1, -1, 102], [11, 0, 13, 3, -1, -1, 103]], [2, 0, 5, 1]], [[], 1]], [[[[3, 3, 12, 13, 1, 6, -1], [3, 8, 8, 13, 2, 3, -1], [3, 10, 6, 13, -1, -1, 104], [5, 8, 8, 11, 4, 5, -1], [5, 9, 5, 9, -1, -1, 101], [5, 8, 8, 11, -1, -1, 100], [6, 3, 12, 11, 7, 8, -1], [6, 8, 8, 11, -1, -1, 103], [9, 3, 12, 11, 9, 10, -1], [9, 8, 12, 11, -1, -1, 105], [11, 3, 11, 5, -1, -1, 102]], [11, 11, 14, 12]], [[105], 7]], [[[[0, 0, 8, 14, 1, 4, -1], [0, 0, 2, 3, 2, 3, -1], [0, 0, 2, 2, -1, -1, 101], [0, 0, 2, 3, -1, -1, 104], [0, 9, 8, 14, 5, 6, -1], [0, 9, 3, 12, -1, -1, 102], [6, 12, 8, 14, 7, 8, -1], [6, 12, 6, 14, -1, -1, 103], [6, 12, 8, 14, -1, -1, 100]], [5, 9, 9, 11]], [[], 5]], [[[[0, 2, 13, 12, 1, 4, -1], [0, 5, 5, 8, 2, 3, -1], [0, 5, 1, 7, -1, -1, 103], [2, 8, 5, 8, -1, -1, 104], [8, 2, 13, 12, 5, 6, -1], [8, 11, 11, 12, -1, -1, 100], [11, 2, 13, 5, 7, 8, -1], [11, 2, 13, 2, -1, -1, 101], [12, 4, 12, 5, -1, -1, 102]], [8, 4, 10, 7]], [[], 5]], [[[[0, 0, 15, 15, 1, 10, -1], [0, 0, 11, 14, 2, 5, -1], [0, 5, 1, 14, 3, 4, -1], [0, 5, 0, 8, -1, -1, 110], [1, 12, 1, 14, -1, -1, 105], [8, 0, 11, 10, 6, 7, -1], [8, 1, 10, 2, -1, -1, 102], [8, 0, 11, 10, 8, 9, -1], [8, 0, 10, 1, -1, -1, 108], [8, 8, 11, 10, -1, -1, 101], [10, 2, 15, 15, 11, 16, -1], [10, 6, 12, 15, 12, 13, -1], [10, 6, 12, 7, -1, -1, 104], [10, 11, 12, 15, 14, 15, -1], [10, 11, 12, 14, -1, -1, 106], [11, 12, 12, 15, -1, -1, 100], [11, 2, 15, 11, 17, 18, -1], [11, 11, 13, 11, -1, -1, 109], [11, 2, 15, 7, 19, 20, -1], [11, 7, 14, 7, -1, -1, 103], [12, 2, 15, 5, -1, -1, 107]], [10, 9, 10, 12]], [[101, 106], 15]], [[[[1, 0, 11, 11, 1, 6, -1], [1, 4, 6, 11, 2, 3, -1], [1, 9, 1, 11, -1, -1, 105], [2, 4, 6, 10, 4, 5, -1], [2, 4, 2, 5, -1, -1, 104], [6, 9, 6, 10, -1, -1, 100], [6, 0, 11, 8, 7, 8, -1], [6, 8, 8, 8, -1, -1, 102], [7, 0, 11, 4, 9, 10, -1], [7, 3, 9, 4, -1, -1, 101], [9, 0, 11, 1, -1, -1, 103]], [9, 9, 10, 9]], [[], 3]], [[[[0, 2, 13, 14, 1, 10, -1], [0, 4, 4, 14, 2, 5, -1], [0, 5, 1, 14, 3, 4, -1], [0, 12, 0, 14, -1, -1, 100], [0, 5, 1, 6, -1, -1, 105], [1, 4, 4, 12, 6, 7, -1], [1, 8, 1, 8, -1, -1, 102], [1, 4, 4, 12, 8, 9, -1], [1, 9, 2, 12, -1, -1, 106], [4, 4, 4, 7, -1, -1, 101], [6, 2, 13, 12, 11, 14, -1], [6, 9, 8, 12, 12, 13, -1], [6, 9, 7, 12, -1, -1, 103], [7, 9, 8, 9, -1, -1, 107], [6, 2, 13, 5, 15, 16, -1], [6, 3, 9, 3, -1, -1, 109], [11, 2, 13, 5, 17, 18, -1], [11, 2, 12, 5, -1, -1, 108], [11, 2, 13, 2, -1, -1, 104]], [8, 4, 10, 6]], [[], 7]], [[[[0, 2, 8, 11, 1, 6, -1], [0, 2, 4, 10, 2, 3, -1], [0, 7, 0, 10, -1, -1, 103], [0, 2, 4, 8, 4, 5, -1], [0, 2, 1, 2, -1, -1, 100], [4, 8, 4, 8, -1, -1, 102], [5, 4, 8, 11, 7, 8, -1], [6, 6, 6, 9, -1, -1, 101], [5, 4, 8, 11, 9, 10, -1], [5, 8, 8, 11, -1, -1, 105], [7, 4, 8, 7, -1, -1, 104]], [7, 1, 9, 2]], [[], 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	`[[], 3]`	`[[], 3]`	Passed
case 1	`[[100, 101], 5]`	`[[100, 101], 9]`	Failed
case 2	`[[104], 4]`	`[[104], 5]`	Failed
case 3	`[[], 1]`	`[[], 1]`	Passed
case 4	`[[100], 4]`	`[[100], 5]`	Failed
case 5	`[[103], 4]`	`[[103], 7]`	Failed
case 6	`[[], 1]`	`[[], 1]`	Passed
case 7	`[[], 2]`	`[[], 3]`	Failed

SHA-256 / f5697213328a1ab7e95ea42d1f4966bd49e2783edbeb4e98bcc09858440ef939

3 / The verified repair

Exit 0

"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(nodes, q):
    if not nodes:
        return [[], 0]
    stack = [0]
    hits = []
    tests = 0
    while stack:
        i = stack.pop()
        nd = nodes[i]
        tests += 1
        if not (nd[0] <= q[2] and q[0] <= nd[2] and nd[1] <= q[3] and q[1] <= nd[3]):
            continue
        if nd[4] < 0:
            hits.append(nd[6])
        else:
            stack.append(nd[4])
            stack.append(nd[5])
    return [sorted(hits), tests]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[[[[[0, 2, 12, 12, 1, 4, -1], [0, 2, 7, 4, 2, 3, -1], [0, 4, 2, 4, -1, -1, 100], [5, 2, 7, 2, -1, -1, 103], [8, 4, 12, 12, 5, 6, -1], [8, 4, 9, 6, -1, -1, 104], [10, 6, 12, 12, 7, 8, -1], [11, 10, 11, 12, -1, -1, 101], [10, 6, 12, 8, -1, -1, 102]], [6, 5, 7, 7]], [[], 3]], [[[[2, 1, 11, 12, 1, 6, -1], [2, 1, 6, 5, 2, 3, -1], [2, 1, 5, 3, -1, -1, 104], [5, 2, 6, 5, 4, 5, -1], [5, 2, 5, 5, -1, -1, 103], [6, 3, 6, 3, -1, -1, 105], [6, 1, 11, 12, 7, 10, -1], [6, 1, 8, 12, 8, 9, -1], [6, 11, 7, 12, -1, -1, 102], [6, 1, 8, 2, -1, -1, 106], [9, 6, 11, 8, 11, 12, -1], [9, 6, 9, 7, -1, -1, 101], [10, 6, 11, 8, -1, -1, 100]], [7, 6, 10, 9]], [[100, 101], 9]], [[[[0, 4, 13, 14, 1, 6, -1], [0, 4, 5, 14, 2, 3, -1], [0, 4, 1, 4, -1, -1, 104], [1, 6, 5, 14, 4, 5, -1], [1, 6, 3, 7, -1, -1, 102], [2, 12, 5, 14, -1, -1, 105], [6, 4, 13, 13, 7, 10, -1], [6, 11, 8, 13, 8, 9, -1], [6, 11, 8, 13, -1, -1, 101], [7, 11, 8, 11, -1, -1, 100], [7, 4, 13, 7, 11, 12, -1], [7, 4, 8, 4, -1, -1, 106], [12, 5, 13, 7, -1, -1, 103]], [0, 2, 0, 4]], [[104], 5]], [[[[0, 5, 8, 13, 1, 4, -1], [0, 5, 1, 13, 2, 3, -1], [0, 5, 0, 6, -1, -1, 101], [1, 12, 1, 13, -1, -1, 104], [5, 8, 8, 13, 5, 6, -1], [5, 8, 7, 10, -1, -1, 102], [6, 12, 8, 13, 7, 8, -1], [6, 12, 7, 12, -1, -1, 103], [6, 12, 8, 13, -1, -1, 100]], [12, 3, 13, 6]], [[], 1]], [[[[1, 1, 13, 15, 1, 6, -1], [1, 1, 8, 11, 2, 3, -1], [1, 9, 4, 11, -1, -1, 100], [2, 1, 8, 5, 4, 5, -1], [2, 3, 4, 5, -1, -1, 104], [6, 1, 8, 3, -1, -1, 103], [6, 4, 13, 15, 7, 8, -1], [6, 4, 9, 6, -1, -1, 105], [10, 10, 13, 15, 9, 10, -1], [10, 12, 12, 15, -1, -1, 101], [10, 10, 13, 12, -1, -1, 102]], [1, 8, 5, 11]], [[100], 5]], [[[[0, 1, 13, 15, 1, 6, -1], [0, 6, 5, 15, 2, 3, -1], [0, 12, 0, 15, -1, -1, 100], [2, 6, 5, 12, 4, 5, -1], [2, 10, 5, 12, -1, -1, 103], [3, 6, 5, 8, -1, -1, 101], [8, 1, 13, 7, 7, 8, -1], [8, 1, 9, 4, -1, -1, 104], [9, 4, 13, 7, 9, 10, -1], [9, 5, 11, 7, -1, -1, 105], [11, 4, 13, 5, -1, -1, 102]], [3, 11, 6, 12]], [[103], 7]], [[[[3, 5, 10, 10, 1, 2, -1], [3, 5, 4, 7, -1, -1, 100], [4, 6, 10, 10, 3, 4, -1], [4, 10, 6, 10, -1, -1, 102], [8, 6, 10, 8, -1, -1, 101]], [3, 3, 6, 4]], [[], 1]], [[[[0, 1, 12, 12, 1, 2, -1], [0, 9, 3, 10, -1, -1, 102], [10, 1, 12, 12, 3, 4, -1], [10, 11, 10, 12, -1, -1, 101], [11, 1, 12, 4, -1, -1, 100]], [4, 10, 8, 10]], [[], 3]]], [[[[[4, 0, 10, 13, 1, 6, -1], [4, 5, 7, 12, 2, 3, -1], [4, 8, 4, 8, -1, -1, 103], [5, 5, 7, 12, 4, 5, -1], [5, 11, 5, 12, -1, -1, 105], [6, 5, 7, 8, -1, -1, 102], [7, 0, 10, 13, 7, 8, -1], [7, 0, 7, 2, -1, -1, 101], [8, 2, 10, 13, 9, 10, -1], [8, 2, 10, 2, -1, -1, 100], [9, 12, 10, 13, -1, -1, 104]], [3, 9, 5, 13]], [[105], 7]], [[[[9, 4, 14, 10, 1, 4, -1], [9, 8, 12, 10, 2, 3, -1], [9, 9, 12, 10, -1, -1, 101], [10, 8, 11, 9, -1, -1, 102], [9, 4, 14, 10, 5, 6, -1], [9, 10, 12, 10, -1, -1, 103], [12, 4, 14, 4, -1, -1, 100]], [7, 5, 7, 8]], [[], 1]], [[[[2, 3, 15, 14, 1, 8, -1], [2, 3, 11, 12, 2, 5, -1], [2, 5, 10, 12, 3, 4, -1], [2, 5, 3, 7, -1, -1, 100], [8, 12, 10, 12, -1, -1, 105], [8, 3, 11, 6, 6, 7, -1], [8, 3, 11, 3, -1, -1, 101], [11, 4, 11, 6, -1, -1, 102], [12, 4, 15, 14, 9, 12, -1], [12, 4, 13, 14, 10, 11, -1], [12, 11, 13, 14, -1, -1, 103], [12, 4, 13, 6, -1, -1, 104], [12, 5, 15, 10, 13, 14, -1], [12, 5, 13, 7, -1, -1, 107], [12, 7, 15, 10, -1, -1, 106]], [3, 2, 3, 2]], [[], 1]], [[[[0, 0, 12, 11, 1, 4, -1], [0, 6, 3, 11, 2, 3, -1], [1, 10, 1, 11, -1, -1, 101], [0, 6, 3, 8, -1, -1, 104], [5, 0, 12, 4, 5, 6, -1], [5, 1, 5, 3, -1, -1, 103], [8, 0, 12, 4, 7, 8, -1], [8, 0, 9, 0, -1, -1, 102], [11, 4, 12, 4, -1, -1, 100]], [11, 9, 14, 11]], [[], 3]], [[[[1, 3, 12, 12, 1, 6, -1], [1, 4, 6, 6, 2, 3, -1], [1, 5, 1, 6, -1, -1, 103], [5, 4, 6, 6, 4, 5, -1], [5, 4, 6, 5, -1, -1, 100], [6, 5, 6, 6, -1, -1, 104], [7, 3, 12, 12, 7, 8, -1], [7, 3, 9, 6, -1, -1, 105], [8, 3, 12, 12, 9, 10, -1], [8, 10, 10, 12, -1, -1, 101], [11, 3, 12, 6, -1, -1, 102]], [9, 6, 13, 6]], [[102, 105], 7]], [[[[1, 0, 12, 14, 1, 4, -1], [1, 2, 3, 5, 2, 3, -1], [2, 2, 2, 2, -1, -1, 101], [1, 3, 3, 5, -1, -1, 102], [2, 0, 12, 14, 5, 6, -1], [2, 6, 4, 8, -1, -1, 104], [3, 0, 12, 14, 7, 8, -1], [3, 12, 4, 14, -1, -1, 100], [11, 0, 12, 0, -1, -1, 103]], [11, 10, 14, 13]], [[], 7]], [[[[1, 0, 12, 11, 1, 6, -1], [1, 0, 4, 11, 2, 3, -1], [1, 0, 2, 0, -1, -1, 100], [2, 7, 4, 11, 4, 5, -1], [2, 7, 2, 7, -1, -1, 105], [3, 11, 4, 11, -1, -1, 104], [5, 4, 12, 8, 7, 8, -1], [5, 6, 5, 8, -1, -1, 102], [6, 4, 12, 6, 9, 10, -1], [6, 4, 8, 6, -1, -1, 101], [10, 4, 12, 4, -1, -1, 103]], [6, 7, 7, 7]], [[], 5]], [[[[0, 5, 14, 14, 1, 6, -1], [0, 5, 5, 14, 2, 3, -1], [0, 5, 0, 8, -1, -1, 105], [2, 8, 5, 14, 4, 5, -1], [2, 12, 3, 14, -1, -1, 103], [4, 8, 5, 9, -1, -1, 102], [6, 11, 14, 12, 7, 8, -1], [6, 11, 9, 11, -1, -1, 101], [10, 11, 14, 12, 9, 10, -1], [10, 11, 13, 11, -1, -1, 100], [11, 12, 14, 12, -1, -1, 104]], [2, 2, 5, 6]], [[], 5]]], [[[[[4, 2, 6, 13, 1, 2, -1], [4, 11, 6, 13, -1, -1, 100], [4, 2, 6, 8, 3, 4, -1], [4, 2, 6, 4, -1, -1, 102], [6, 6, 6, 8, -1, -1, 101]], [11, 12, 11, 13]], [[], 1]], [[[[0, 0, 14, 11, 1, 8, -1], [0, 4, 2, 11, 2, 5, -1], [0, 6, 2, 9, 3, 4, -1], [0, 6, 1, 9, -1, -1, 106], [0, 9, 2, 9, -1, -1, 104], [1, 4, 2, 11, 6, 7, -1], [1, 8, 2, 11, -1, -1, 101], [1, 4, 2, 6, -1, -1, 107], [2, 0, 14, 11, 9, 12, -1], [2, 0, 6, 11, 10, 11, -1], [2, 0, 4, 1, -1, -1, 105], [6, 10, 6, 11, -1, -1, 100], [8, 1, 14, 10, 13, 14, -1], [8, 2, 9, 4, -1, -1, 103], [9, 1, 14, 10, 15, 16, -1], [9, 9, 12, 10, -1, -1, 108], [11, 1, 14, 1, -1, -1, 102]], [4, 6, 5, 7]], [[], 7]], [[[[7, 6, 14, 12, 1, 4, -1], [7, 6, 9, 8, 2, 3, -1], [7, 6, 8, 8, -1, -1, 102], [7, 7, 9, 7, -1, -1, 103], [10, 7, 14, 12, 5, 6, -1], [10, 10, 13, 12, -1, -1, 101], [11, 7, 14, 7, -1, -1, 100]], [11, 6, 12, 10]], [[100, 101], 5]], [[[[0, 0, 11, 14, 1, 8, -1], [0, 1, 8, 10, 2, 5, -1], [0, 4, 3, 9, 3, 4, -1], [0, 4, 1, 4, -1, -1, 101], [3, 9, 3, 9, -1, -1, 106], [3, 1, 8, 10, 6, 7, -1], [3, 10, 6, 10, -1, -1, 104], [7, 1, 8, 4, -1, -1, 103], [8, 0, 11, 14, 9, 12, -1], [8, 0, 11, 14, 10, 11, -1], [8, 11, 10, 14, -1, -1, 107], [8, 0, 11, 3, -1, -1, 100], [9, 8, 11, 14, 13, 14, -1], [9, 8, 10, 8, -1, -1, 105], [11, 11, 11, 14, -1, -1, 102]], [12, 2, 14, 4]], [[], 1]], [[[[2, 0, 14, 14, 1, 8, -1], [2, 4, 5, 14, 2, 5, -1], [2, 5, 4, 12, 3, 4, -1], [2, 11, 2, 12, -1, -1, 106], [4, 5, 4, 5, -1, -1, 102], [4, 4, 5, 14, 6, 7, -1], [4, 4, 5, 7, -1, -1, 107], [5, 12, 5, 14, -1, -1, 105], [7, 0, 14, 8, 9, 12, -1], [7, 0, 10, 3, 10, 11, -1], [7, 0, 7, 3, -1, -1, 104], [8, 1, 10, 2, -1, -1, 101], [8, 0, 14, 8, 13, 14, -1], [8, 5, 11, 8, -1, -1, 100], [12, 0, 14, 3, -1, -1, 103]], [6, 0, 8, 1]], [[101, 104], 9]], [[[[10, 2, 11, 5, -1, -1, 100]], [0, 11, 3, 14]], [[], 1]], [[[[0, 0, 15, 14, 1, 8, -1], [0, 7, 7, 14, 2, 5, -1], [0, 7, 2, 13, 3, 4, -1], [0, 11, 2, 13, -1, -1, 106], [1, 7, 1, 10, -1, -1, 107], [6, 10, 7, 14, 6, 7, -1], [6, 10, 6, 11, -1, -1, 105], [6, 11, 7, 14, -1, -1, 104], [8, 0, 15, 11, 9, 12, -1], [8, 6, 13, 11, 10, 11, -1], [8, 9, 10, 11, -1, -1, 103], [11, 6, 13, 9, -1, -1, 100], [11, 0, 15, 9, 13, 14, -1], [11, 0, 13, 0, -1, -1, 102], [12, 9, 15, 9, -1, -1, 101]], [10, 4, 11, 7]], [[100], 9]], [[[[2, 0, 14, 13, 1, 8, -1], [2, 1, 7, 13, 2, 5, -1], [2, 1, 4, 7, 3, 4, -1], [2, 1, 2, 3, -1, -1, 104], [2, 5, 4, 7, -1, -1, 101], [4, 4, 7, 13, 6, 7, -1], [4, 11, 5, 13, -1, -1, 103], [7, 4, 7, 4, -1, -1, 102], [8, 0, 14, 10, 9, 12, -1], [8, 4, 9, 4, 10, 11, -1], [8, 4, 8, 4, -1, -1, 100], [8, 4, 9, 4, -1, -1, 105], [10, 0, 14, 10, 13, 14, -1], [10, 8, 12, 10, -1, -1, 107], [11, 0, 14, 5, 15, 16, -1], [11, 0, 12, 2, -1, -1, 106], [12, 4, 14, 5, -1, -1, 108]], [12, 12, 14, 16]], [[], 3]]], [[[[[0, 1, 14, 13, 1, 10, -1], [0, 1, 3, 13, 2, 5, -1], [0, 2, 2, 13, 3, 4, -1], [0, 11, 1, 13, -1, -1, 104], [0, 2, 2, 2, -1, -1, 106], [0, 1, 3, 12, 6, 7, -1], [0, 11, 3, 12, -1, -1, 102], [1, 1, 3, 7, 8, 9, -1], [1, 1, 3, 2, -1, -1, 107], [3, 4, 3, 7, -1, -1, 109], [4, 3, 14, 12, 11, 14, -1], [4, 7, 7, 10, 12, 13, -1], [4, 8, 5, 10, -1, -1, 101], [4, 7, 7, 9, -1, -1, 105], [8, 3, 14, 12, 15, 16, -1], [8, 10, 11, 12, -1, -1, 108], [11, 3, 14, 8, 17, 18, -1], [11, 7, 13, 8, -1, -1, 103], [11, 3, 14, 4, -1, -1, 100]], [8, 3, 8, 7]], [[], 7]], [[[[5, 0, 6, 10, 1, 2, -1], [5, 0, 5, 0, -1, -1, 101], [6, 7, 6, 10, -1, -1, 100]], [9, 9, 13, 13]], [[], 1]], [[[[5, 4, 7, 4, -1, -1, 100]], [10, 7, 10, 11]], [[], 1]], [[[[1, 0, 15, 13, 1, 8, -1], [1, 2, 4, 8, 2, 5, -1], [1, 5, 3, 8, 3, 4, -1], [1, 5, 3, 7, -1, -1, 101], [1, 6, 3, 8, -1, -1, 106], [1, 2, 4, 4, 6, 7, -1], [1, 2, 4, 2, -1, -1, 103], [4, 3, 4, 4, -1, -1, 104], [3, 0, 15, 13, 9, 12, -1], [3, 0, 6, 3, 10, 11, -1], [3, 1, 6, 2, -1, -1, 108], [5, 0, 5, 3, -1, -1, 105], [9, 9, 15, 13, 13, 14, -1], [9, 11, 10, 13, -1, -1, 102], [12, 9, 15, 11, 15, 16, -1], [12, 9, 13, 10, -1, -1, 100], [12, 10, 15, 11, -1, -1, 107]], [6, 10, 6, 13]], [[], 5]], [[[[2, 1, 7, 8, 1, 2, -1], [2, 1, 5, 2, -1, -1, 101], [4, 5, 7, 8, 3, 4, -1], [4, 6, 7, 8, -1, -1, 102], [5, 5, 7, 8, -1, -1, 100]], [5, 9, 6, 12]], [[], 1]], [[[[8, 5, 9, 12, 1, 2, -1], [8, 10, 9, 12, -1, -1, 100], [8, 5, 9, 5, -1, -1, 101]], [5, 7, 5, 9]], [[], 1]], [[[[1, 1, 12, 13, 1, 6, -1], [1, 1, 7, 13, 2, 3, -1], [1, 11, 2, 13, -1, -1, 102], [4, 1, 7, 13, 4, 5, -1], [5, 1, 5, 3, -1, -1, 104], [4, 11, 7, 13, -1, -1, 103], [5, 1, 12, 6, 7, 8, -1], [5, 1, 7, 2, -1, -1, 101], [10, 2, 12, 6, 9, 10, -1], [10, 6, 12, 6, -1, -1, 100], [12, 2, 12, 4, -1, -1, 105]], [6, 6, 8, 9]], [[], 9]], [[[[0, 0, 14, 14, 1, 6, -1], [0, 4, 6, 14, 2, 3, -1], [0, 4, 0, 5, -1, -1, 102], [1, 7, 6, 14, 4, 5, -1], [1, 7, 1, 8, -1, -1, 103], [6, 11, 6, 14, -1, -1, 104], [8, 0, 14, 14, 7, 10, -1], [8, 0, 11, 7, 8, 9, -1], [8, 5, 11, 7, -1, -1, 101], [9, 0, 11, 3, -1, -1, 100], [11, 6, 14, 14, 11, 12, -1], [11, 6, 14, 8, -1, -1, 106], [12, 12, 14, 14, -1, -1, 105]], [12, 9, 15, 9]], [[], 7]]], [[[[[8, 0, 13, 15, 1, 4, -1], [8, 4, 12, 15, 2, 3, -1], [8, 12, 9, 15, -1, -1, 100], [9, 4, 12, 4, -1, -1, 101], [10, 0, 13, 11, 5, 6, -1], [10, 8, 12, 11, -1, -1, 102], [11, 0, 13, 3, -1, -1, 103]], [2, 0, 5, 1]], [[], 1]], [[[[3, 3, 12, 13, 1, 6, -1], [3, 8, 8, 13, 2, 3, -1], [3, 10, 6, 13, -1, -1, 104], [5, 8, 8, 11, 4, 5, -1], [5, 9, 5, 9, -1, -1, 101], [5, 8, 8, 11, -1, -1, 100], [6, 3, 12, 11, 7, 8, -1], [6, 8, 8, 11, -1, -1, 103], [9, 3, 12, 11, 9, 10, -1], [9, 8, 12, 11, -1, -1, 105], [11, 3, 11, 5, -1, -1, 102]], [11, 11, 14, 12]], [[105], 7]], [[[[0, 0, 8, 14, 1, 4, -1], [0, 0, 2, 3, 2, 3, -1], [0, 0, 2, 2, -1, -1, 101], [0, 0, 2, 3, -1, -1, 104], [0, 9, 8, 14, 5, 6, -1], [0, 9, 3, 12, -1, -1, 102], [6, 12, 8, 14, 7, 8, -1], [6, 12, 6, 14, -1, -1, 103], [6, 12, 8, 14, -1, -1, 100]], [5, 9, 9, 11]], [[], 5]], [[[[0, 2, 13, 12, 1, 4, -1], [0, 5, 5, 8, 2, 3, -1], [0, 5, 1, 7, -1, -1, 103], [2, 8, 5, 8, -1, -1, 104], [8, 2, 13, 12, 5, 6, -1], [8, 11, 11, 12, -1, -1, 100], [11, 2, 13, 5, 7, 8, -1], [11, 2, 13, 2, -1, -1, 101], [12, 4, 12, 5, -1, -1, 102]], [8, 4, 10, 7]], [[], 5]], [[[[0, 0, 15, 15, 1, 10, -1], [0, 0, 11, 14, 2, 5, -1], [0, 5, 1, 14, 3, 4, -1], [0, 5, 0, 8, -1, -1, 110], [1, 12, 1, 14, -1, -1, 105], [8, 0, 11, 10, 6, 7, -1], [8, 1, 10, 2, -1, -1, 102], [8, 0, 11, 10, 8, 9, -1], [8, 0, 10, 1, -1, -1, 108], [8, 8, 11, 10, -1, -1, 101], [10, 2, 15, 15, 11, 16, -1], [10, 6, 12, 15, 12, 13, -1], [10, 6, 12, 7, -1, -1, 104], [10, 11, 12, 15, 14, 15, -1], [10, 11, 12, 14, -1, -1, 106], [11, 12, 12, 15, -1, -1, 100], [11, 2, 15, 11, 17, 18, -1], [11, 11, 13, 11, -1, -1, 109], [11, 2, 15, 7, 19, 20, -1], [11, 7, 14, 7, -1, -1, 103], [12, 2, 15, 5, -1, -1, 107]], [10, 9, 10, 12]], [[101, 106], 15]], [[[[1, 0, 11, 11, 1, 6, -1], [1, 4, 6, 11, 2, 3, -1], [1, 9, 1, 11, -1, -1, 105], [2, 4, 6, 10, 4, 5, -1], [2, 4, 2, 5, -1, -1, 104], [6, 9, 6, 10, -1, -1, 100], [6, 0, 11, 8, 7, 8, -1], [6, 8, 8, 8, -1, -1, 102], [7, 0, 11, 4, 9, 10, -1], [7, 3, 9, 4, -1, -1, 101], [9, 0, 11, 1, -1, -1, 103]], [9, 9, 10, 9]], [[], 3]], [[[[0, 2, 13, 14, 1, 10, -1], [0, 4, 4, 14, 2, 5, -1], [0, 5, 1, 14, 3, 4, -1], [0, 12, 0, 14, -1, -1, 100], [0, 5, 1, 6, -1, -1, 105], [1, 4, 4, 12, 6, 7, -1], [1, 8, 1, 8, -1, -1, 102], [1, 4, 4, 12, 8, 9, -1], [1, 9, 2, 12, -1, -1, 106], [4, 4, 4, 7, -1, -1, 101], [6, 2, 13, 12, 11, 14, -1], [6, 9, 8, 12, 12, 13, -1], [6, 9, 7, 12, -1, -1, 103], [7, 9, 8, 9, -1, -1, 107], [6, 2, 13, 5, 15, 16, -1], [6, 3, 9, 3, -1, -1, 109], [11, 2, 13, 5, 17, 18, -1], [11, 2, 12, 5, -1, -1, 108], [11, 2, 13, 2, -1, -1, 104]], [8, 4, 10, 6]], [[], 7]], [[[[0, 2, 8, 11, 1, 6, -1], [0, 2, 4, 10, 2, 3, -1], [0, 7, 0, 10, -1, -1, 103], [0, 2, 4, 8, 4, 5, -1], [0, 2, 1, 2, -1, -1, 100], [4, 8, 4, 8, -1, -1, 102], [5, 4, 8, 11, 7, 8, -1], [6, 6, 6, 9, -1, -1, 101], [5, 4, 8, 11, 9, 10, -1], [5, 8, 8, 11, -1, -1, 105], [7, 4, 8, 7, -1, -1, 104]], [7, 1, 9, 2]], [[], 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	`[[], 3]`	`[[], 3]`	Passed
case 1	`[[100, 101], 9]`	`[[100, 101], 9]`	Passed
case 2	`[[104], 5]`	`[[104], 5]`	Passed
case 3	`[[], 1]`	`[[], 1]`	Passed
case 4	`[[100], 5]`	`[[100], 5]`	Passed
case 5	`[[103], 7]`	`[[103], 7]`	Passed
case 6	`[[], 1]`	`[[], 1]`	Passed
case 7	`[[], 3]`	`[[], 3]`	Passed

SHA-256 / abbfb42562ce2beecb91d4de7996cbe5702549d9201ea89e43e7e51a1b09ceee

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

Case digest / ff04a75a8b4fef56c8d99a4c3e3eb076d44594b59350954cd7d22fc5ac750db6