FA-87456 / Collision detection broadphase / Open access

BVH traversal prunes nodes that only touch the query on x · case 01

Queries flush against an object edge return nothing.

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

ROOT CAUSE

The x overlap uses strict comparisons.

VERIFIED REPAIR

Use closed-interval overlap for pruning.

Unsuccessful approach: Making only the upper x comparison inclusive still prunes the other touching side.

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]
        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, 0, 15, 12, 1, 4, -1], [0, 0, 3, 2, 2, 3, -1], [0, 2, 0, 2, -1, -1, 102], [1, 0, 3, 2, -1, -1, 100], [6, 2, 15, 12, 5, 6, -1], [6, 2, 6, 2, -1, -1, 101], [12, 10, 15, 12, -1, -1, 103]], [4, 10, 6, 13]], [[], 5]], [[[[2, 0, 10, 9, 1, 6, -1], [2, 0, 5, 9, 2, 3, -1], [2, 8, 3, 8, -1, -1, 104], [2, 0, 5, 9, 4, 5, -1], [2, 8, 5, 9, -1, -1, 101], [3, 0, 4, 0, -1, -1, 102], [4, 1, 10, 8, 7, 8, -1], [4, 5, 4, 8, -1, -1, 100], [5, 1, 10, 4, 9, 10, -1], [5, 3, 6, 4, -1, -1, 103], [10, 1, 10, 1, -1, -1, 105]], [12, 2, 16, 2]], [[], 1]], [[[[0, 1, 10, 11, 1, 2, -1], [0, 8, 3, 11, -1, -1, 101], [1, 1, 10, 11, 3, 4, -1], [1, 10, 4, 11, -1, -1, 100], [9, 1, 10, 2, -1, -1, 102]], [1, 11, 1, 11]], [[100, 101], 5]], [[[[1, 3, 11, 14, 1, 2, -1], [1, 3, 4, 4, -1, -1, 100], [4, 6, 11, 14, 3, 4, -1], [4, 11, 7, 14, -1, -1, 101], [11, 6, 11, 6, -1, -1, 102]], [12, 0, 14, 1]], [[], 1]], [[[[0, 5, 10, 14, 1, 4, -1], [0, 5, 3, 10, 2, 3, -1], [0, 5, 3, 5, -1, -1, 102], [2, 7, 2, 10, -1, -1, 100], [4, 6, 10, 14, 5, 6, -1], [4, 6, 7, 9, -1, -1, 101], [8, 12, 10, 14, -1, -1, 103]], [2, 12, 6, 14]], [[], 5]], [[[[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]], [[[[3, 0, 10, 11, 1, 4, -1], [3, 8, 5, 11, 2, 3, -1], [3, 10, 5, 11, -1, -1, 100], [3, 8, 5, 9, -1, -1, 102], [4, 0, 10, 4, 5, 6, -1], [4, 4, 7, 4, -1, -1, 101], [10, 0, 10, 3, -1, -1, 103]], [4, 2, 6, 3]], [[], 5]], [[[[7, 7, 13, 13, 1, 2, -1], [7, 10, 8, 11, -1, -1, 102], [11, 7, 13, 13, 3, 4, -1], [11, 7, 11, 9, -1, -1, 100], [12, 10, 13, 13, -1, -1, 101]], [7, 12, 7, 14]], [[], 3]]], [[[[[1, 2, 12, 12, 1, 2, -1], [1, 9, 3, 9, -1, -1, 102], [5, 2, 12, 12, 3, 4, -1], [5, 12, 6, 12, -1, -1, 101], [12, 2, 12, 3, -1, -1, 100]], [1, 8, 5, 8]], [[], 5]], [[[[0, 4, 12, 12, 1, 4, -1], [0, 7, 3, 10, 2, 3, -1], [0, 10, 3, 10, -1, -1, 101], [2, 7, 3, 9, -1, -1, 104], [6, 4, 12, 12, 5, 6, -1], [6, 8, 9, 11, -1, -1, 102], [10, 4, 12, 12, 7, 8, -1], [10, 4, 12, 5, -1, -1, 100], [10, 11, 12, 12, -1, -1, 103]], [8, 8, 10, 9]], [[102], 7]], [[[[9, 12, 12, 14, -1, -1, 100]], [11, 5, 12, 8]], [[], 1]], [[[[0, 0, 11, 13, 1, 6, -1], [0, 0, 4, 13, 2, 3, -1], [0, 0, 1, 1, -1, -1, 100], [3, 9, 4, 13, 4, 5, -1], [3, 9, 3, 9, -1, -1, 106], [4, 11, 4, 13, -1, -1, 102], [4, 0, 11, 12, 7, 10, -1], [4, 5, 9, 12, 8, 9, -1], [4, 5, 7, 6, -1, -1, 104], [7, 10, 9, 12, -1, -1, 105], [8, 0, 11, 2, 11, 12, -1], [8, 0, 11, 2, -1, -1, 101], [10, 1, 11, 1, -1, -1, 103]], [10, 4, 12, 6]], [[], 5]], [[[[1, 0, 11, 14, 1, 4, -1], [1, 12, 3, 14, 2, 3, -1], [1, 12, 3, 14, -1, -1, 103], [2, 12, 3, 12, -1, -1, 102], [7, 0, 11, 6, 5, 6, -1], [7, 0, 7, 1, -1, -1, 100], [8, 2, 11, 6, 7, 8, -1], [8, 2, 9, 5, -1, -1, 101], [8, 3, 11, 6, -1, -1, 104]], [5, 10, 6, 10]], [[], 3]], [[[[1, 1, 15, 12, 1, 6, -1], [1, 6, 4, 12, 2, 3, -1], [1, 12, 4, 12, -1, -1, 103], [1, 6, 4, 10, 4, 5, -1], [1, 9, 4, 10, -1, -1, 105], [3, 6, 3, 6, -1, -1, 104], [3, 1, 15, 6, 7, 8, -1], [3, 6, 4, 6, -1, -1, 100], [5, 1, 15, 5, 9, 10, -1], [5, 1, 5, 3, -1, -1, 102], [12, 4, 15, 5, -1, -1, 101]], [3, 6, 6, 8]], [[100, 104], 9]], [[[[7, 0, 13, 15, 1, 4, -1], [7, 0, 10, 9, 2, 3, -1], [7, 0, 10, 2, -1, -1, 103], [8, 9, 10, 9, -1, -1, 101], [9, 10, 13, 15, 5, 6, -1], [9, 12, 11, 15, -1, -1, 102], [11, 10, 13, 11, -1, -1, 100]], [6, 11, 9, 12]], [[102], 5]], [[[[3, 4, 9, 12, 1, 2, -1], [3, 10, 5, 12, -1, -1, 101], [6, 4, 9, 12, 3, 4, -1], [6, 12, 8, 12, -1, -1, 100], [9, 4, 9, 7, -1, -1, 102]], [1, 8, 3, 11]], [[101], 3]]], [[[[[2, 9, 12, 13, 1, 2, -1], [2, 11, 4, 13, -1, -1, 100], [2, 9, 12, 13, 3, 4, -1], [2, 9, 4, 12, -1, -1, 102], [10, 10, 12, 13, -1, -1, 101]], [0, 7, 2, 11]], [[100, 102], 5]], [[[[2, 1, 15, 15, 1, 8, -1], [2, 3, 10, 9, 2, 5, -1], [2, 3, 4, 6, 3, 4, -1], [2, 3, 2, 4, -1, -1, 105], [2, 4, 4, 6, -1, -1, 101], [3, 4, 10, 9, 6, 7, -1], [3, 6, 5, 9, -1, -1, 104], [7, 4, 10, 7, -1, -1, 107], [8, 1, 15, 15, 9, 12, -1], [8, 1, 10, 9, 10, 11, -1], [8, 8, 10, 9, -1, -1, 103], [9, 1, 10, 4, -1, -1, 100], [11, 11, 15, 15, 13, 14, -1], [11, 11, 11, 13, -1, -1, 106], [12, 12, 15, 15, -1, -1, 102]], [0, 4, 3, 8]], [[101, 104, 105], 9]], [[[[5, 1, 15, 15, 1, 6, -1], [5, 2, 10, 14, 2, 3, -1], [5, 2, 8, 4, -1, -1, 103], [6, 5, 10, 14, 4, 5, -1], [6, 12, 9, 14, -1, -1, 104], [8, 5, 10, 7, -1, -1, 106], [8, 1, 15, 15, 7, 10, -1], [8, 5, 11, 15, 8, 9, -1], [8, 12, 11, 15, -1, -1, 101], [9, 5, 10, 5, -1, -1, 105], [12, 1, 15, 12, 11, 12, -1], [12, 10, 15, 12, -1, -1, 100], [12, 1, 15, 3, -1, -1, 102]], [12, 0, 13, 2]], [[102], 7]], [[[[0, 0, 14, 12, 1, 6, -1], [0, 2, 5, 6, 2, 3, -1], [0, 5, 2, 6, -1, -1, 100], [2, 2, 5, 6, 4, 5, -1], [2, 2, 4, 2, -1, -1, 104], [2, 4, 5, 6, -1, -1, 102], [4, 0, 14, 12, 7, 8, -1], [4, 7, 4, 8, -1, -1, 101], [11, 0, 14, 12, 9, 10, -1], [11, 12, 12, 12, -1, -1, 105], [11, 0, 14, 3, -1, -1, 103]], [0, 7, 3, 11]], [[], 3]], [[[[5, 0, 13, 9, 1, 6, -1], [5, 0, 8, 9, 2, 3, -1], [5, 0, 7, 0, -1, -1, 102], [5, 5, 8, 9, 4, 5, -1], [5, 5, 8, 8, -1, -1, 104], [5, 8, 8, 9, -1, -1, 105], [10, 2, 13, 9, 7, 10, -1], [10, 2, 11, 9, 8, 9, -1], [10, 8, 11, 9, -1, -1, 101], [10, 2, 11, 4, -1, -1, 106], [10, 5, 13, 8, 11, 12, -1], [10, 5, 12, 6, -1, -1, 103], [10, 8, 13, 8, -1, -1, 100]], [7, 6, 10, 6]], [[103, 104], 13]], [[[[4, 9, 9, 13, 1, 2, -1], [4, 12, 5, 13, -1, -1, 100], [7, 9, 9, 10, -1, -1, 101]], [8, 11, 8, 13]], [[], 3]], [[[[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]], [[[[1, 0, 12, 11, 1, 4, -1], [1, 0, 3, 11, 2, 3, -1], [1, 0, 3, 0, -1, -1, 103], [1, 9, 3, 11, -1, -1, 104], [6, 5, 12, 10, 5, 6, -1], [6, 5, 6, 6, -1, -1, 102], [8, 8, 12, 10, 7, 8, -1], [8, 8, 9, 10, -1, -1, 101], [11, 8, 12, 8, -1, -1, 100]], [3, 6, 4, 10]], [[104], 5]]], [[[[[1, 5, 12, 14, 1, 2, -1], [1, 11, 3, 14, -1, -1, 102], [11, 5, 12, 11, 3, 4, -1], [11, 5, 11, 5, -1, -1, 101], [11, 11, 12, 11, -1, -1, 100]], [1, 5, 3, 7]], [[], 3]], [[[[2, 1, 13, 14, 1, 8, -1], [2, 2, 10, 14, 2, 5, -1], [2, 6, 5, 14, 3, 4, -1], [2, 11, 5, 14, -1, -1, 101], [5, 6, 5, 7, -1, -1, 105], [5, 2, 10, 12, 6, 7, -1], [5, 10, 6, 12, -1, -1, 103], [7, 2, 10, 2, -1, -1, 106], [7, 1, 13, 9, 9, 12, -1], [7, 2, 12, 9, 10, 11, -1], [7, 2, 10, 3, -1, -1, 107], [9, 7, 12, 9, -1, -1, 104], [11, 1, 13, 6, 13, 14, -1], [11, 6, 12, 6, -1, -1, 100], [11, 1, 13, 1, -1, -1, 102]], [9, 6, 11, 10]], [[100, 104], 13]], [[[[0, 1, 13, 13, 1, 10, -1], [0, 1, 7, 10, 2, 5, -1], [0, 3, 2, 9, 3, 4, -1], [0, 8, 1, 9, -1, -1, 102], [2, 3, 2, 5, -1, -1, 103], [4, 1, 7, 10, 6, 7, -1], [4, 8, 7, 10, -1, -1, 104], [5, 1, 7, 8, 8, 9, -1], [5, 5, 7, 8, -1, -1, 100], [6, 1, 7, 4, -1, -1, 109], [7, 1, 13, 13, 11, 14, -1], [7, 8, 8, 11, 12, 13, -1], [7, 8, 7, 11, -1, -1, 101], [7, 8, 8, 11, -1, -1, 107], [7, 1, 13, 13, 15, 16, -1], [7, 6, 9, 6, -1, -1, 108], [9, 1, 13, 13, 17, 18, -1], [9, 10, 10, 13, -1, -1, 106], [12, 1, 13, 4, -1, -1, 105]], [8, 0, 11, 1]], [[], 9]], [[[[3, 6, 12, 12, 1, 4, -1], [3, 6, 7, 9, 2, 3, -1], [3, 6, 6, 8, -1, -1, 101], [4, 6, 7, 9, -1, -1, 103], [8, 6, 12, 12, 5, 6, -1], [8, 7, 11, 9, -1, -1, 102], [10, 6, 12, 12, 7, 8, -1], [10, 6, 10, 7, -1, -1, 104], [11, 12, 12, 12, -1, -1, 100]], [10, 6, 13, 9]], [[102, 104], 7]], [[[[0, 0, 12, 13, 1, 8, -1], [0, 0, 4, 8, 2, 5, -1], [0, 0, 3, 3, 3, 4, -1], [0, 0, 1, 2, -1, -1, 105], [0, 3, 3, 3, -1, -1, 101], [1, 5, 4, 8, 6, 7, -1], [2, 7, 2, 8, -1, -1, 103], [1, 5, 4, 7, -1, -1, 106], [4, 0, 12, 13, 9, 12, -1], [4, 1, 7, 5, 10, 11, -1], [5, 1, 6, 3, -1, -1, 102], [4, 4, 7, 5, -1, -1, 107], [11, 0, 12, 13, 13, 14, -1], [11, 12, 11, 13, -1, -1, 100], [11, 0, 12, 2, -1, -1, 104]], [7, 0, 10, 2]], [[], 7]], [[[[1, 4, 11, 15, 1, 4, -1], [1, 4, 5, 9, 2, 3, -1], [1, 7, 2, 9, -1, -1, 103], [5, 4, 5, 5, -1, -1, 100], [7, 9, 11, 15, 5, 6, -1], [7, 9, 9, 11, -1, -1, 102], [10, 12, 11, 15, -1, -1, 101]], [4, 6, 6, 7]], [[], 5]], [[[[0, 0, 14, 8, 1, 4, -1], [0, 0, 1, 7, 2, 3, -1], [0, 7, 1, 7, -1, -1, 100], [0, 0, 1, 2, -1, -1, 102], [3, 4, 14, 8, 5, 6, -1], [3, 4, 5, 4, -1, -1, 103], [9, 5, 14, 8, 7, 8, -1], [9, 5, 11, 5, -1, -1, 104], [12, 8, 14, 8, -1, -1, 101]], [6, 5, 9, 9]], [[104], 7]], [[[[1, 0, 11, 13, 1, 8, -1], [1, 0, 8, 11, 2, 5, -1], [1, 0, 3, 11, 3, 4, -1], [1, 10, 1, 11, -1, -1, 103], [1, 0, 3, 1, -1, -1, 107], [4, 0, 8, 10, 6, 7, -1], [4, 10, 6, 10, -1, -1, 105], [6, 0, 8, 0, -1, -1, 108], [7, 0, 11, 13, 9, 12, -1], [7, 1, 8, 13, 10, 11, -1], [7, 1, 8, 3, -1, -1, 104], [8, 11, 8, 13, -1, -1, 106], [9, 0, 11, 13, 13, 14, -1], [9, 10, 11, 13, -1, -1, 100], [10, 0, 11, 5, 15, 16, -1], [10, 0, 10, 3, -1, -1, 102], [11, 2, 11, 5, -1, -1, 101]], [6, 2, 7, 6]], [[104], 11]]], [[[[[2, 0, 9, 8, 1, 6, -1], [2, 0, 8, 8, 2, 3, -1], [2, 8, 4, 8, -1, -1, 101], [4, 0, 8, 5, 4, 5, -1], [4, 0, 5, 1, -1, -1, 102], [5, 4, 8, 5, -1, -1, 103], [7, 0, 9, 3, 7, 8, -1], [7, 0, 7, 3, -1, -1, 104], [7, 1, 9, 3, 9, 10, -1], [7, 2, 8, 3, -1, -1, 105], [7, 1, 9, 3, -1, -1, 100]], [6, 1, 9, 4]], [[100, 103, 104, 105], 11]], [[[[0, 0, 10, 11, 1, 10, -1], [0, 1, 5, 10, 2, 5, -1], [0, 1, 2, 10, 3, 4, -1], [1, 7, 1, 10, -1, -1, 102], [0, 1, 2, 4, -1, -1, 105], [3, 6, 5, 8, 6, 7, -1], [4, 7, 4, 8, -1, -1, 100], [3, 6, 5, 7, 8, 9, -1], [3, 6, 5, 7, -1, -1, 104], [3, 6, 5, 6, -1, -1, 108], [4, 0, 10, 11, 11, 14, -1], [4, 0, 7, 11, 12, 13, -1], [4, 0, 6, 1, -1, -1, 101], [4, 10, 7, 11, -1, -1, 109], [7, 0, 10, 11, 15, 16, -1], [7, 4, 7, 5, -1, -1, 103], [8, 0, 10, 11, 17, 18, -1], [8, 10, 9, 11, -1, -1, 106], [10, 0, 10, 0, -1, -1, 107]], [5, 3, 8, 6]], [[103, 104, 108], 17]], [[[[0, 3, 12, 13, 1, 6, -1], [0, 4, 11, 13, 2, 3, -1], [1, 4, 1, 4, -1, -1, 105], [0, 9, 11, 13, 4, 5, -1], [0, 9, 3, 10, -1, -1, 100], [8, 12, 11, 13, -1, -1, 102], [10, 3, 12, 9, 7, 8, -1], [10, 5, 12, 7, -1, -1, 103], [12, 3, 12, 9, 9, 10, -1], [12, 9, 12, 9, -1, -1, 101], [12, 3, 12, 6, -1, -1, 104]], [11, 5, 11, 9]], [[103], 9]], [[[[0, 0, 14, 15, 1, 10, -1], [0, 2, 8, 14, 2, 5, -1], [0, 9, 1, 14, 3, 4, -1], [0, 12, 0, 14, -1, -1, 107], [1, 9, 1, 10, -1, -1, 109], [1, 2, 8, 8, 6, 7, -1], [1, 2, 3, 4, -1, -1, 103], [3, 5, 8, 8, 8, 9, -1], [3, 8, 3, 8, -1, -1, 106], [5, 5, 8, 7, -1, -1, 102], [6, 0, 14, 15, 11, 16, -1], [6, 0, 11, 15, 12, 13, -1], [6, 1, 7, 2, -1, -1, 105], [7, 0, 11, 15, 14, 15, -1], [7, 0, 8, 0, -1, -1, 104], [9, 12, 11, 15, -1, -1, 101], [11, 6, 14, 12, 17, 18, -1], [11, 7, 13, 8, -1, -1, 100], [11, 6, 14, 12, 19, 20, -1], [11, 12, 14, 12, -1, -1, 108], [11, 6, 14, 6, -1, -1, 110]], [6, 1, 10, 1]], [[105], 9]], [[[[0, 4, 14, 14, 1, 6, -1], [0, 4, 3, 10, 2, 3, -1], [0, 10, 0, 10, -1, -1, 101], [0, 4, 3, 9, 4, 5, -1], [1, 7, 2, 9, -1, -1, 104], [0, 4, 3, 5, -1, -1, 105], [6, 4, 14, 14, 7, 8, -1], [6, 10, 8, 11, -1, -1, 103], [9, 4, 14, 14, 9, 10, -1], [9, 4, 10, 4, -1, -1, 102], [11, 12, 14, 14, -1, -1, 100]], [9, 12, 13, 13]], [[100], 7]], [[[[1, 0, 14, 14, 1, 8, -1], [1, 5, 6, 14, 2, 5, -1], [1, 5, 5, 14, 3, 4, -1], [1, 5, 2, 8, -1, -1, 104], [3, 12, 5, 14, -1, -1, 101], [3, 9, 6, 10, 6, 7, -1], [3, 9, 6, 10, -1, -1, 100], [5, 9, 6, 9, -1, -1, 102], [7, 0, 14, 12, 9, 12, -1], [7, 6, 10, 12, 10, 11, -1], [8, 11, 8, 12, -1, -1, 103], [7, 6, 10, 9, -1, -1, 106], [11, 0, 14, 12, 13, 14, -1], [11, 0, 13, 3, -1, -1, 105], [11, 11, 14, 12, -1, -1, 107]], [5, 12, 9, 15]], [[101, 103], 11]], [[[[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, 13, 13, 1, 6, -1], [1, 0, 10, 13, 2, 3, -1], [1, 11, 1, 13, -1, -1, 102], [8, 0, 10, 10, 4, 5, -1], [8, 0, 8, 1, -1, -1, 103], [8, 7, 10, 10, -1, -1, 106], [10, 7, 13, 10, 7, 10, -1], [10, 7, 13, 10, 8, 9, -1], [10, 10, 11, 10, -1, -1, 105], [11, 7, 13, 8, -1, -1, 101], [12, 8, 13, 9, 11, 12, -1], [12, 8, 12, 9, -1, -1, 104], [12, 8, 13, 9, -1, -1, 100]], [12, 0, 12, 0]], [[], 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]`	`[[], 5]`	Failed
case 1	`[[], 1]`	`[[], 1]`	Passed
case 2	`[[101], 3]`	`[[100, 101], 5]`	Failed
case 3	`[[], 1]`	`[[], 1]`	Passed
case 4	`[[], 5]`	`[[], 5]`	Passed
case 5	`[[], 1]`	`[[104], 5]`	Failed
case 6	`[[], 5]`	`[[], 5]`	Passed
case 7	`[[], 1]`	`[[], 3]`	Failed

SHA-256 / 91f7c5d427671b089406da3ec0ebf403f0d7a305c81cc79fc56857fdfd842bbe

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 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, 0, 15, 12, 1, 4, -1], [0, 0, 3, 2, 2, 3, -1], [0, 2, 0, 2, -1, -1, 102], [1, 0, 3, 2, -1, -1, 100], [6, 2, 15, 12, 5, 6, -1], [6, 2, 6, 2, -1, -1, 101], [12, 10, 15, 12, -1, -1, 103]], [4, 10, 6, 13]], [[], 5]], [[[[2, 0, 10, 9, 1, 6, -1], [2, 0, 5, 9, 2, 3, -1], [2, 8, 3, 8, -1, -1, 104], [2, 0, 5, 9, 4, 5, -1], [2, 8, 5, 9, -1, -1, 101], [3, 0, 4, 0, -1, -1, 102], [4, 1, 10, 8, 7, 8, -1], [4, 5, 4, 8, -1, -1, 100], [5, 1, 10, 4, 9, 10, -1], [5, 3, 6, 4, -1, -1, 103], [10, 1, 10, 1, -1, -1, 105]], [12, 2, 16, 2]], [[], 1]], [[[[0, 1, 10, 11, 1, 2, -1], [0, 8, 3, 11, -1, -1, 101], [1, 1, 10, 11, 3, 4, -1], [1, 10, 4, 11, -1, -1, 100], [9, 1, 10, 2, -1, -1, 102]], [1, 11, 1, 11]], [[100, 101], 5]], [[[[1, 3, 11, 14, 1, 2, -1], [1, 3, 4, 4, -1, -1, 100], [4, 6, 11, 14, 3, 4, -1], [4, 11, 7, 14, -1, -1, 101], [11, 6, 11, 6, -1, -1, 102]], [12, 0, 14, 1]], [[], 1]], [[[[0, 5, 10, 14, 1, 4, -1], [0, 5, 3, 10, 2, 3, -1], [0, 5, 3, 5, -1, -1, 102], [2, 7, 2, 10, -1, -1, 100], [4, 6, 10, 14, 5, 6, -1], [4, 6, 7, 9, -1, -1, 101], [8, 12, 10, 14, -1, -1, 103]], [2, 12, 6, 14]], [[], 5]], [[[[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]], [[[[3, 0, 10, 11, 1, 4, -1], [3, 8, 5, 11, 2, 3, -1], [3, 10, 5, 11, -1, -1, 100], [3, 8, 5, 9, -1, -1, 102], [4, 0, 10, 4, 5, 6, -1], [4, 4, 7, 4, -1, -1, 101], [10, 0, 10, 3, -1, -1, 103]], [4, 2, 6, 3]], [[], 5]], [[[[7, 7, 13, 13, 1, 2, -1], [7, 10, 8, 11, -1, -1, 102], [11, 7, 13, 13, 3, 4, -1], [11, 7, 11, 9, -1, -1, 100], [12, 10, 13, 13, -1, -1, 101]], [7, 12, 7, 14]], [[], 3]]], [[[[[1, 2, 12, 12, 1, 2, -1], [1, 9, 3, 9, -1, -1, 102], [5, 2, 12, 12, 3, 4, -1], [5, 12, 6, 12, -1, -1, 101], [12, 2, 12, 3, -1, -1, 100]], [1, 8, 5, 8]], [[], 5]], [[[[0, 4, 12, 12, 1, 4, -1], [0, 7, 3, 10, 2, 3, -1], [0, 10, 3, 10, -1, -1, 101], [2, 7, 3, 9, -1, -1, 104], [6, 4, 12, 12, 5, 6, -1], [6, 8, 9, 11, -1, -1, 102], [10, 4, 12, 12, 7, 8, -1], [10, 4, 12, 5, -1, -1, 100], [10, 11, 12, 12, -1, -1, 103]], [8, 8, 10, 9]], [[102], 7]], [[[[9, 12, 12, 14, -1, -1, 100]], [11, 5, 12, 8]], [[], 1]], [[[[0, 0, 11, 13, 1, 6, -1], [0, 0, 4, 13, 2, 3, -1], [0, 0, 1, 1, -1, -1, 100], [3, 9, 4, 13, 4, 5, -1], [3, 9, 3, 9, -1, -1, 106], [4, 11, 4, 13, -1, -1, 102], [4, 0, 11, 12, 7, 10, -1], [4, 5, 9, 12, 8, 9, -1], [4, 5, 7, 6, -1, -1, 104], [7, 10, 9, 12, -1, -1, 105], [8, 0, 11, 2, 11, 12, -1], [8, 0, 11, 2, -1, -1, 101], [10, 1, 11, 1, -1, -1, 103]], [10, 4, 12, 6]], [[], 5]], [[[[1, 0, 11, 14, 1, 4, -1], [1, 12, 3, 14, 2, 3, -1], [1, 12, 3, 14, -1, -1, 103], [2, 12, 3, 12, -1, -1, 102], [7, 0, 11, 6, 5, 6, -1], [7, 0, 7, 1, -1, -1, 100], [8, 2, 11, 6, 7, 8, -1], [8, 2, 9, 5, -1, -1, 101], [8, 3, 11, 6, -1, -1, 104]], [5, 10, 6, 10]], [[], 3]], [[[[1, 1, 15, 12, 1, 6, -1], [1, 6, 4, 12, 2, 3, -1], [1, 12, 4, 12, -1, -1, 103], [1, 6, 4, 10, 4, 5, -1], [1, 9, 4, 10, -1, -1, 105], [3, 6, 3, 6, -1, -1, 104], [3, 1, 15, 6, 7, 8, -1], [3, 6, 4, 6, -1, -1, 100], [5, 1, 15, 5, 9, 10, -1], [5, 1, 5, 3, -1, -1, 102], [12, 4, 15, 5, -1, -1, 101]], [3, 6, 6, 8]], [[100, 104], 9]], [[[[7, 0, 13, 15, 1, 4, -1], [7, 0, 10, 9, 2, 3, -1], [7, 0, 10, 2, -1, -1, 103], [8, 9, 10, 9, -1, -1, 101], [9, 10, 13, 15, 5, 6, -1], [9, 12, 11, 15, -1, -1, 102], [11, 10, 13, 11, -1, -1, 100]], [6, 11, 9, 12]], [[102], 5]], [[[[3, 4, 9, 12, 1, 2, -1], [3, 10, 5, 12, -1, -1, 101], [6, 4, 9, 12, 3, 4, -1], [6, 12, 8, 12, -1, -1, 100], [9, 4, 9, 7, -1, -1, 102]], [1, 8, 3, 11]], [[101], 3]]], [[[[[2, 9, 12, 13, 1, 2, -1], [2, 11, 4, 13, -1, -1, 100], [2, 9, 12, 13, 3, 4, -1], [2, 9, 4, 12, -1, -1, 102], [10, 10, 12, 13, -1, -1, 101]], [0, 7, 2, 11]], [[100, 102], 5]], [[[[2, 1, 15, 15, 1, 8, -1], [2, 3, 10, 9, 2, 5, -1], [2, 3, 4, 6, 3, 4, -1], [2, 3, 2, 4, -1, -1, 105], [2, 4, 4, 6, -1, -1, 101], [3, 4, 10, 9, 6, 7, -1], [3, 6, 5, 9, -1, -1, 104], [7, 4, 10, 7, -1, -1, 107], [8, 1, 15, 15, 9, 12, -1], [8, 1, 10, 9, 10, 11, -1], [8, 8, 10, 9, -1, -1, 103], [9, 1, 10, 4, -1, -1, 100], [11, 11, 15, 15, 13, 14, -1], [11, 11, 11, 13, -1, -1, 106], [12, 12, 15, 15, -1, -1, 102]], [0, 4, 3, 8]], [[101, 104, 105], 9]], [[[[5, 1, 15, 15, 1, 6, -1], [5, 2, 10, 14, 2, 3, -1], [5, 2, 8, 4, -1, -1, 103], [6, 5, 10, 14, 4, 5, -1], [6, 12, 9, 14, -1, -1, 104], [8, 5, 10, 7, -1, -1, 106], [8, 1, 15, 15, 7, 10, -1], [8, 5, 11, 15, 8, 9, -1], [8, 12, 11, 15, -1, -1, 101], [9, 5, 10, 5, -1, -1, 105], [12, 1, 15, 12, 11, 12, -1], [12, 10, 15, 12, -1, -1, 100], [12, 1, 15, 3, -1, -1, 102]], [12, 0, 13, 2]], [[102], 7]], [[[[0, 0, 14, 12, 1, 6, -1], [0, 2, 5, 6, 2, 3, -1], [0, 5, 2, 6, -1, -1, 100], [2, 2, 5, 6, 4, 5, -1], [2, 2, 4, 2, -1, -1, 104], [2, 4, 5, 6, -1, -1, 102], [4, 0, 14, 12, 7, 8, -1], [4, 7, 4, 8, -1, -1, 101], [11, 0, 14, 12, 9, 10, -1], [11, 12, 12, 12, -1, -1, 105], [11, 0, 14, 3, -1, -1, 103]], [0, 7, 3, 11]], [[], 3]], [[[[5, 0, 13, 9, 1, 6, -1], [5, 0, 8, 9, 2, 3, -1], [5, 0, 7, 0, -1, -1, 102], [5, 5, 8, 9, 4, 5, -1], [5, 5, 8, 8, -1, -1, 104], [5, 8, 8, 9, -1, -1, 105], [10, 2, 13, 9, 7, 10, -1], [10, 2, 11, 9, 8, 9, -1], [10, 8, 11, 9, -1, -1, 101], [10, 2, 11, 4, -1, -1, 106], [10, 5, 13, 8, 11, 12, -1], [10, 5, 12, 6, -1, -1, 103], [10, 8, 13, 8, -1, -1, 100]], [7, 6, 10, 6]], [[103, 104], 13]], [[[[4, 9, 9, 13, 1, 2, -1], [4, 12, 5, 13, -1, -1, 100], [7, 9, 9, 10, -1, -1, 101]], [8, 11, 8, 13]], [[], 3]], [[[[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]], [[[[1, 0, 12, 11, 1, 4, -1], [1, 0, 3, 11, 2, 3, -1], [1, 0, 3, 0, -1, -1, 103], [1, 9, 3, 11, -1, -1, 104], [6, 5, 12, 10, 5, 6, -1], [6, 5, 6, 6, -1, -1, 102], [8, 8, 12, 10, 7, 8, -1], [8, 8, 9, 10, -1, -1, 101], [11, 8, 12, 8, -1, -1, 100]], [3, 6, 4, 10]], [[104], 5]]], [[[[[1, 5, 12, 14, 1, 2, -1], [1, 11, 3, 14, -1, -1, 102], [11, 5, 12, 11, 3, 4, -1], [11, 5, 11, 5, -1, -1, 101], [11, 11, 12, 11, -1, -1, 100]], [1, 5, 3, 7]], [[], 3]], [[[[2, 1, 13, 14, 1, 8, -1], [2, 2, 10, 14, 2, 5, -1], [2, 6, 5, 14, 3, 4, -1], [2, 11, 5, 14, -1, -1, 101], [5, 6, 5, 7, -1, -1, 105], [5, 2, 10, 12, 6, 7, -1], [5, 10, 6, 12, -1, -1, 103], [7, 2, 10, 2, -1, -1, 106], [7, 1, 13, 9, 9, 12, -1], [7, 2, 12, 9, 10, 11, -1], [7, 2, 10, 3, -1, -1, 107], [9, 7, 12, 9, -1, -1, 104], [11, 1, 13, 6, 13, 14, -1], [11, 6, 12, 6, -1, -1, 100], [11, 1, 13, 1, -1, -1, 102]], [9, 6, 11, 10]], [[100, 104], 13]], [[[[0, 1, 13, 13, 1, 10, -1], [0, 1, 7, 10, 2, 5, -1], [0, 3, 2, 9, 3, 4, -1], [0, 8, 1, 9, -1, -1, 102], [2, 3, 2, 5, -1, -1, 103], [4, 1, 7, 10, 6, 7, -1], [4, 8, 7, 10, -1, -1, 104], [5, 1, 7, 8, 8, 9, -1], [5, 5, 7, 8, -1, -1, 100], [6, 1, 7, 4, -1, -1, 109], [7, 1, 13, 13, 11, 14, -1], [7, 8, 8, 11, 12, 13, -1], [7, 8, 7, 11, -1, -1, 101], [7, 8, 8, 11, -1, -1, 107], [7, 1, 13, 13, 15, 16, -1], [7, 6, 9, 6, -1, -1, 108], [9, 1, 13, 13, 17, 18, -1], [9, 10, 10, 13, -1, -1, 106], [12, 1, 13, 4, -1, -1, 105]], [8, 0, 11, 1]], [[], 9]], [[[[3, 6, 12, 12, 1, 4, -1], [3, 6, 7, 9, 2, 3, -1], [3, 6, 6, 8, -1, -1, 101], [4, 6, 7, 9, -1, -1, 103], [8, 6, 12, 12, 5, 6, -1], [8, 7, 11, 9, -1, -1, 102], [10, 6, 12, 12, 7, 8, -1], [10, 6, 10, 7, -1, -1, 104], [11, 12, 12, 12, -1, -1, 100]], [10, 6, 13, 9]], [[102, 104], 7]], [[[[0, 0, 12, 13, 1, 8, -1], [0, 0, 4, 8, 2, 5, -1], [0, 0, 3, 3, 3, 4, -1], [0, 0, 1, 2, -1, -1, 105], [0, 3, 3, 3, -1, -1, 101], [1, 5, 4, 8, 6, 7, -1], [2, 7, 2, 8, -1, -1, 103], [1, 5, 4, 7, -1, -1, 106], [4, 0, 12, 13, 9, 12, -1], [4, 1, 7, 5, 10, 11, -1], [5, 1, 6, 3, -1, -1, 102], [4, 4, 7, 5, -1, -1, 107], [11, 0, 12, 13, 13, 14, -1], [11, 12, 11, 13, -1, -1, 100], [11, 0, 12, 2, -1, -1, 104]], [7, 0, 10, 2]], [[], 7]], [[[[1, 4, 11, 15, 1, 4, -1], [1, 4, 5, 9, 2, 3, -1], [1, 7, 2, 9, -1, -1, 103], [5, 4, 5, 5, -1, -1, 100], [7, 9, 11, 15, 5, 6, -1], [7, 9, 9, 11, -1, -1, 102], [10, 12, 11, 15, -1, -1, 101]], [4, 6, 6, 7]], [[], 5]], [[[[0, 0, 14, 8, 1, 4, -1], [0, 0, 1, 7, 2, 3, -1], [0, 7, 1, 7, -1, -1, 100], [0, 0, 1, 2, -1, -1, 102], [3, 4, 14, 8, 5, 6, -1], [3, 4, 5, 4, -1, -1, 103], [9, 5, 14, 8, 7, 8, -1], [9, 5, 11, 5, -1, -1, 104], [12, 8, 14, 8, -1, -1, 101]], [6, 5, 9, 9]], [[104], 7]], [[[[1, 0, 11, 13, 1, 8, -1], [1, 0, 8, 11, 2, 5, -1], [1, 0, 3, 11, 3, 4, -1], [1, 10, 1, 11, -1, -1, 103], [1, 0, 3, 1, -1, -1, 107], [4, 0, 8, 10, 6, 7, -1], [4, 10, 6, 10, -1, -1, 105], [6, 0, 8, 0, -1, -1, 108], [7, 0, 11, 13, 9, 12, -1], [7, 1, 8, 13, 10, 11, -1], [7, 1, 8, 3, -1, -1, 104], [8, 11, 8, 13, -1, -1, 106], [9, 0, 11, 13, 13, 14, -1], [9, 10, 11, 13, -1, -1, 100], [10, 0, 11, 5, 15, 16, -1], [10, 0, 10, 3, -1, -1, 102], [11, 2, 11, 5, -1, -1, 101]], [6, 2, 7, 6]], [[104], 11]]], [[[[[2, 0, 9, 8, 1, 6, -1], [2, 0, 8, 8, 2, 3, -1], [2, 8, 4, 8, -1, -1, 101], [4, 0, 8, 5, 4, 5, -1], [4, 0, 5, 1, -1, -1, 102], [5, 4, 8, 5, -1, -1, 103], [7, 0, 9, 3, 7, 8, -1], [7, 0, 7, 3, -1, -1, 104], [7, 1, 9, 3, 9, 10, -1], [7, 2, 8, 3, -1, -1, 105], [7, 1, 9, 3, -1, -1, 100]], [6, 1, 9, 4]], [[100, 103, 104, 105], 11]], [[[[0, 0, 10, 11, 1, 10, -1], [0, 1, 5, 10, 2, 5, -1], [0, 1, 2, 10, 3, 4, -1], [1, 7, 1, 10, -1, -1, 102], [0, 1, 2, 4, -1, -1, 105], [3, 6, 5, 8, 6, 7, -1], [4, 7, 4, 8, -1, -1, 100], [3, 6, 5, 7, 8, 9, -1], [3, 6, 5, 7, -1, -1, 104], [3, 6, 5, 6, -1, -1, 108], [4, 0, 10, 11, 11, 14, -1], [4, 0, 7, 11, 12, 13, -1], [4, 0, 6, 1, -1, -1, 101], [4, 10, 7, 11, -1, -1, 109], [7, 0, 10, 11, 15, 16, -1], [7, 4, 7, 5, -1, -1, 103], [8, 0, 10, 11, 17, 18, -1], [8, 10, 9, 11, -1, -1, 106], [10, 0, 10, 0, -1, -1, 107]], [5, 3, 8, 6]], [[103, 104, 108], 17]], [[[[0, 3, 12, 13, 1, 6, -1], [0, 4, 11, 13, 2, 3, -1], [1, 4, 1, 4, -1, -1, 105], [0, 9, 11, 13, 4, 5, -1], [0, 9, 3, 10, -1, -1, 100], [8, 12, 11, 13, -1, -1, 102], [10, 3, 12, 9, 7, 8, -1], [10, 5, 12, 7, -1, -1, 103], [12, 3, 12, 9, 9, 10, -1], [12, 9, 12, 9, -1, -1, 101], [12, 3, 12, 6, -1, -1, 104]], [11, 5, 11, 9]], [[103], 9]], [[[[0, 0, 14, 15, 1, 10, -1], [0, 2, 8, 14, 2, 5, -1], [0, 9, 1, 14, 3, 4, -1], [0, 12, 0, 14, -1, -1, 107], [1, 9, 1, 10, -1, -1, 109], [1, 2, 8, 8, 6, 7, -1], [1, 2, 3, 4, -1, -1, 103], [3, 5, 8, 8, 8, 9, -1], [3, 8, 3, 8, -1, -1, 106], [5, 5, 8, 7, -1, -1, 102], [6, 0, 14, 15, 11, 16, -1], [6, 0, 11, 15, 12, 13, -1], [6, 1, 7, 2, -1, -1, 105], [7, 0, 11, 15, 14, 15, -1], [7, 0, 8, 0, -1, -1, 104], [9, 12, 11, 15, -1, -1, 101], [11, 6, 14, 12, 17, 18, -1], [11, 7, 13, 8, -1, -1, 100], [11, 6, 14, 12, 19, 20, -1], [11, 12, 14, 12, -1, -1, 108], [11, 6, 14, 6, -1, -1, 110]], [6, 1, 10, 1]], [[105], 9]], [[[[0, 4, 14, 14, 1, 6, -1], [0, 4, 3, 10, 2, 3, -1], [0, 10, 0, 10, -1, -1, 101], [0, 4, 3, 9, 4, 5, -1], [1, 7, 2, 9, -1, -1, 104], [0, 4, 3, 5, -1, -1, 105], [6, 4, 14, 14, 7, 8, -1], [6, 10, 8, 11, -1, -1, 103], [9, 4, 14, 14, 9, 10, -1], [9, 4, 10, 4, -1, -1, 102], [11, 12, 14, 14, -1, -1, 100]], [9, 12, 13, 13]], [[100], 7]], [[[[1, 0, 14, 14, 1, 8, -1], [1, 5, 6, 14, 2, 5, -1], [1, 5, 5, 14, 3, 4, -1], [1, 5, 2, 8, -1, -1, 104], [3, 12, 5, 14, -1, -1, 101], [3, 9, 6, 10, 6, 7, -1], [3, 9, 6, 10, -1, -1, 100], [5, 9, 6, 9, -1, -1, 102], [7, 0, 14, 12, 9, 12, -1], [7, 6, 10, 12, 10, 11, -1], [8, 11, 8, 12, -1, -1, 103], [7, 6, 10, 9, -1, -1, 106], [11, 0, 14, 12, 13, 14, -1], [11, 0, 13, 3, -1, -1, 105], [11, 11, 14, 12, -1, -1, 107]], [5, 12, 9, 15]], [[101, 103], 11]], [[[[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, 13, 13, 1, 6, -1], [1, 0, 10, 13, 2, 3, -1], [1, 11, 1, 13, -1, -1, 102], [8, 0, 10, 10, 4, 5, -1], [8, 0, 8, 1, -1, -1, 103], [8, 7, 10, 10, -1, -1, 106], [10, 7, 13, 10, 7, 10, -1], [10, 7, 13, 10, 8, 9, -1], [10, 10, 11, 10, -1, -1, 105], [11, 7, 13, 8, -1, -1, 101], [12, 8, 13, 9, 11, 12, -1], [12, 8, 12, 9, -1, -1, 104], [12, 8, 13, 9, -1, -1, 100]], [12, 0, 12, 0]], [[], 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]`	`[[], 5]`	Failed
case 1	`[[], 1]`	`[[], 1]`	Passed
case 2	`[[101], 3]`	`[[100, 101], 5]`	Failed
case 3	`[[], 1]`	`[[], 1]`	Passed
case 4	`[[], 5]`	`[[], 5]`	Passed
case 5	`[[], 1]`	`[[104], 5]`	Failed
case 6	`[[], 5]`	`[[], 5]`	Passed
case 7	`[[], 1]`	`[[], 3]`	Failed

SHA-256 / 3fa6c670c7f7333bfb688e1d1d1b679e767e8d6d9b45419d851e2422234cc53d

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, 0, 15, 12, 1, 4, -1], [0, 0, 3, 2, 2, 3, -1], [0, 2, 0, 2, -1, -1, 102], [1, 0, 3, 2, -1, -1, 100], [6, 2, 15, 12, 5, 6, -1], [6, 2, 6, 2, -1, -1, 101], [12, 10, 15, 12, -1, -1, 103]], [4, 10, 6, 13]], [[], 5]], [[[[2, 0, 10, 9, 1, 6, -1], [2, 0, 5, 9, 2, 3, -1], [2, 8, 3, 8, -1, -1, 104], [2, 0, 5, 9, 4, 5, -1], [2, 8, 5, 9, -1, -1, 101], [3, 0, 4, 0, -1, -1, 102], [4, 1, 10, 8, 7, 8, -1], [4, 5, 4, 8, -1, -1, 100], [5, 1, 10, 4, 9, 10, -1], [5, 3, 6, 4, -1, -1, 103], [10, 1, 10, 1, -1, -1, 105]], [12, 2, 16, 2]], [[], 1]], [[[[0, 1, 10, 11, 1, 2, -1], [0, 8, 3, 11, -1, -1, 101], [1, 1, 10, 11, 3, 4, -1], [1, 10, 4, 11, -1, -1, 100], [9, 1, 10, 2, -1, -1, 102]], [1, 11, 1, 11]], [[100, 101], 5]], [[[[1, 3, 11, 14, 1, 2, -1], [1, 3, 4, 4, -1, -1, 100], [4, 6, 11, 14, 3, 4, -1], [4, 11, 7, 14, -1, -1, 101], [11, 6, 11, 6, -1, -1, 102]], [12, 0, 14, 1]], [[], 1]], [[[[0, 5, 10, 14, 1, 4, -1], [0, 5, 3, 10, 2, 3, -1], [0, 5, 3, 5, -1, -1, 102], [2, 7, 2, 10, -1, -1, 100], [4, 6, 10, 14, 5, 6, -1], [4, 6, 7, 9, -1, -1, 101], [8, 12, 10, 14, -1, -1, 103]], [2, 12, 6, 14]], [[], 5]], [[[[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]], [[[[3, 0, 10, 11, 1, 4, -1], [3, 8, 5, 11, 2, 3, -1], [3, 10, 5, 11, -1, -1, 100], [3, 8, 5, 9, -1, -1, 102], [4, 0, 10, 4, 5, 6, -1], [4, 4, 7, 4, -1, -1, 101], [10, 0, 10, 3, -1, -1, 103]], [4, 2, 6, 3]], [[], 5]], [[[[7, 7, 13, 13, 1, 2, -1], [7, 10, 8, 11, -1, -1, 102], [11, 7, 13, 13, 3, 4, -1], [11, 7, 11, 9, -1, -1, 100], [12, 10, 13, 13, -1, -1, 101]], [7, 12, 7, 14]], [[], 3]]], [[[[[1, 2, 12, 12, 1, 2, -1], [1, 9, 3, 9, -1, -1, 102], [5, 2, 12, 12, 3, 4, -1], [5, 12, 6, 12, -1, -1, 101], [12, 2, 12, 3, -1, -1, 100]], [1, 8, 5, 8]], [[], 5]], [[[[0, 4, 12, 12, 1, 4, -1], [0, 7, 3, 10, 2, 3, -1], [0, 10, 3, 10, -1, -1, 101], [2, 7, 3, 9, -1, -1, 104], [6, 4, 12, 12, 5, 6, -1], [6, 8, 9, 11, -1, -1, 102], [10, 4, 12, 12, 7, 8, -1], [10, 4, 12, 5, -1, -1, 100], [10, 11, 12, 12, -1, -1, 103]], [8, 8, 10, 9]], [[102], 7]], [[[[9, 12, 12, 14, -1, -1, 100]], [11, 5, 12, 8]], [[], 1]], [[[[0, 0, 11, 13, 1, 6, -1], [0, 0, 4, 13, 2, 3, -1], [0, 0, 1, 1, -1, -1, 100], [3, 9, 4, 13, 4, 5, -1], [3, 9, 3, 9, -1, -1, 106], [4, 11, 4, 13, -1, -1, 102], [4, 0, 11, 12, 7, 10, -1], [4, 5, 9, 12, 8, 9, -1], [4, 5, 7, 6, -1, -1, 104], [7, 10, 9, 12, -1, -1, 105], [8, 0, 11, 2, 11, 12, -1], [8, 0, 11, 2, -1, -1, 101], [10, 1, 11, 1, -1, -1, 103]], [10, 4, 12, 6]], [[], 5]], [[[[1, 0, 11, 14, 1, 4, -1], [1, 12, 3, 14, 2, 3, -1], [1, 12, 3, 14, -1, -1, 103], [2, 12, 3, 12, -1, -1, 102], [7, 0, 11, 6, 5, 6, -1], [7, 0, 7, 1, -1, -1, 100], [8, 2, 11, 6, 7, 8, -1], [8, 2, 9, 5, -1, -1, 101], [8, 3, 11, 6, -1, -1, 104]], [5, 10, 6, 10]], [[], 3]], [[[[1, 1, 15, 12, 1, 6, -1], [1, 6, 4, 12, 2, 3, -1], [1, 12, 4, 12, -1, -1, 103], [1, 6, 4, 10, 4, 5, -1], [1, 9, 4, 10, -1, -1, 105], [3, 6, 3, 6, -1, -1, 104], [3, 1, 15, 6, 7, 8, -1], [3, 6, 4, 6, -1, -1, 100], [5, 1, 15, 5, 9, 10, -1], [5, 1, 5, 3, -1, -1, 102], [12, 4, 15, 5, -1, -1, 101]], [3, 6, 6, 8]], [[100, 104], 9]], [[[[7, 0, 13, 15, 1, 4, -1], [7, 0, 10, 9, 2, 3, -1], [7, 0, 10, 2, -1, -1, 103], [8, 9, 10, 9, -1, -1, 101], [9, 10, 13, 15, 5, 6, -1], [9, 12, 11, 15, -1, -1, 102], [11, 10, 13, 11, -1, -1, 100]], [6, 11, 9, 12]], [[102], 5]], [[[[3, 4, 9, 12, 1, 2, -1], [3, 10, 5, 12, -1, -1, 101], [6, 4, 9, 12, 3, 4, -1], [6, 12, 8, 12, -1, -1, 100], [9, 4, 9, 7, -1, -1, 102]], [1, 8, 3, 11]], [[101], 3]]], [[[[[2, 9, 12, 13, 1, 2, -1], [2, 11, 4, 13, -1, -1, 100], [2, 9, 12, 13, 3, 4, -1], [2, 9, 4, 12, -1, -1, 102], [10, 10, 12, 13, -1, -1, 101]], [0, 7, 2, 11]], [[100, 102], 5]], [[[[2, 1, 15, 15, 1, 8, -1], [2, 3, 10, 9, 2, 5, -1], [2, 3, 4, 6, 3, 4, -1], [2, 3, 2, 4, -1, -1, 105], [2, 4, 4, 6, -1, -1, 101], [3, 4, 10, 9, 6, 7, -1], [3, 6, 5, 9, -1, -1, 104], [7, 4, 10, 7, -1, -1, 107], [8, 1, 15, 15, 9, 12, -1], [8, 1, 10, 9, 10, 11, -1], [8, 8, 10, 9, -1, -1, 103], [9, 1, 10, 4, -1, -1, 100], [11, 11, 15, 15, 13, 14, -1], [11, 11, 11, 13, -1, -1, 106], [12, 12, 15, 15, -1, -1, 102]], [0, 4, 3, 8]], [[101, 104, 105], 9]], [[[[5, 1, 15, 15, 1, 6, -1], [5, 2, 10, 14, 2, 3, -1], [5, 2, 8, 4, -1, -1, 103], [6, 5, 10, 14, 4, 5, -1], [6, 12, 9, 14, -1, -1, 104], [8, 5, 10, 7, -1, -1, 106], [8, 1, 15, 15, 7, 10, -1], [8, 5, 11, 15, 8, 9, -1], [8, 12, 11, 15, -1, -1, 101], [9, 5, 10, 5, -1, -1, 105], [12, 1, 15, 12, 11, 12, -1], [12, 10, 15, 12, -1, -1, 100], [12, 1, 15, 3, -1, -1, 102]], [12, 0, 13, 2]], [[102], 7]], [[[[0, 0, 14, 12, 1, 6, -1], [0, 2, 5, 6, 2, 3, -1], [0, 5, 2, 6, -1, -1, 100], [2, 2, 5, 6, 4, 5, -1], [2, 2, 4, 2, -1, -1, 104], [2, 4, 5, 6, -1, -1, 102], [4, 0, 14, 12, 7, 8, -1], [4, 7, 4, 8, -1, -1, 101], [11, 0, 14, 12, 9, 10, -1], [11, 12, 12, 12, -1, -1, 105], [11, 0, 14, 3, -1, -1, 103]], [0, 7, 3, 11]], [[], 3]], [[[[5, 0, 13, 9, 1, 6, -1], [5, 0, 8, 9, 2, 3, -1], [5, 0, 7, 0, -1, -1, 102], [5, 5, 8, 9, 4, 5, -1], [5, 5, 8, 8, -1, -1, 104], [5, 8, 8, 9, -1, -1, 105], [10, 2, 13, 9, 7, 10, -1], [10, 2, 11, 9, 8, 9, -1], [10, 8, 11, 9, -1, -1, 101], [10, 2, 11, 4, -1, -1, 106], [10, 5, 13, 8, 11, 12, -1], [10, 5, 12, 6, -1, -1, 103], [10, 8, 13, 8, -1, -1, 100]], [7, 6, 10, 6]], [[103, 104], 13]], [[[[4, 9, 9, 13, 1, 2, -1], [4, 12, 5, 13, -1, -1, 100], [7, 9, 9, 10, -1, -1, 101]], [8, 11, 8, 13]], [[], 3]], [[[[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]], [[[[1, 0, 12, 11, 1, 4, -1], [1, 0, 3, 11, 2, 3, -1], [1, 0, 3, 0, -1, -1, 103], [1, 9, 3, 11, -1, -1, 104], [6, 5, 12, 10, 5, 6, -1], [6, 5, 6, 6, -1, -1, 102], [8, 8, 12, 10, 7, 8, -1], [8, 8, 9, 10, -1, -1, 101], [11, 8, 12, 8, -1, -1, 100]], [3, 6, 4, 10]], [[104], 5]]], [[[[[1, 5, 12, 14, 1, 2, -1], [1, 11, 3, 14, -1, -1, 102], [11, 5, 12, 11, 3, 4, -1], [11, 5, 11, 5, -1, -1, 101], [11, 11, 12, 11, -1, -1, 100]], [1, 5, 3, 7]], [[], 3]], [[[[2, 1, 13, 14, 1, 8, -1], [2, 2, 10, 14, 2, 5, -1], [2, 6, 5, 14, 3, 4, -1], [2, 11, 5, 14, -1, -1, 101], [5, 6, 5, 7, -1, -1, 105], [5, 2, 10, 12, 6, 7, -1], [5, 10, 6, 12, -1, -1, 103], [7, 2, 10, 2, -1, -1, 106], [7, 1, 13, 9, 9, 12, -1], [7, 2, 12, 9, 10, 11, -1], [7, 2, 10, 3, -1, -1, 107], [9, 7, 12, 9, -1, -1, 104], [11, 1, 13, 6, 13, 14, -1], [11, 6, 12, 6, -1, -1, 100], [11, 1, 13, 1, -1, -1, 102]], [9, 6, 11, 10]], [[100, 104], 13]], [[[[0, 1, 13, 13, 1, 10, -1], [0, 1, 7, 10, 2, 5, -1], [0, 3, 2, 9, 3, 4, -1], [0, 8, 1, 9, -1, -1, 102], [2, 3, 2, 5, -1, -1, 103], [4, 1, 7, 10, 6, 7, -1], [4, 8, 7, 10, -1, -1, 104], [5, 1, 7, 8, 8, 9, -1], [5, 5, 7, 8, -1, -1, 100], [6, 1, 7, 4, -1, -1, 109], [7, 1, 13, 13, 11, 14, -1], [7, 8, 8, 11, 12, 13, -1], [7, 8, 7, 11, -1, -1, 101], [7, 8, 8, 11, -1, -1, 107], [7, 1, 13, 13, 15, 16, -1], [7, 6, 9, 6, -1, -1, 108], [9, 1, 13, 13, 17, 18, -1], [9, 10, 10, 13, -1, -1, 106], [12, 1, 13, 4, -1, -1, 105]], [8, 0, 11, 1]], [[], 9]], [[[[3, 6, 12, 12, 1, 4, -1], [3, 6, 7, 9, 2, 3, -1], [3, 6, 6, 8, -1, -1, 101], [4, 6, 7, 9, -1, -1, 103], [8, 6, 12, 12, 5, 6, -1], [8, 7, 11, 9, -1, -1, 102], [10, 6, 12, 12, 7, 8, -1], [10, 6, 10, 7, -1, -1, 104], [11, 12, 12, 12, -1, -1, 100]], [10, 6, 13, 9]], [[102, 104], 7]], [[[[0, 0, 12, 13, 1, 8, -1], [0, 0, 4, 8, 2, 5, -1], [0, 0, 3, 3, 3, 4, -1], [0, 0, 1, 2, -1, -1, 105], [0, 3, 3, 3, -1, -1, 101], [1, 5, 4, 8, 6, 7, -1], [2, 7, 2, 8, -1, -1, 103], [1, 5, 4, 7, -1, -1, 106], [4, 0, 12, 13, 9, 12, -1], [4, 1, 7, 5, 10, 11, -1], [5, 1, 6, 3, -1, -1, 102], [4, 4, 7, 5, -1, -1, 107], [11, 0, 12, 13, 13, 14, -1], [11, 12, 11, 13, -1, -1, 100], [11, 0, 12, 2, -1, -1, 104]], [7, 0, 10, 2]], [[], 7]], [[[[1, 4, 11, 15, 1, 4, -1], [1, 4, 5, 9, 2, 3, -1], [1, 7, 2, 9, -1, -1, 103], [5, 4, 5, 5, -1, -1, 100], [7, 9, 11, 15, 5, 6, -1], [7, 9, 9, 11, -1, -1, 102], [10, 12, 11, 15, -1, -1, 101]], [4, 6, 6, 7]], [[], 5]], [[[[0, 0, 14, 8, 1, 4, -1], [0, 0, 1, 7, 2, 3, -1], [0, 7, 1, 7, -1, -1, 100], [0, 0, 1, 2, -1, -1, 102], [3, 4, 14, 8, 5, 6, -1], [3, 4, 5, 4, -1, -1, 103], [9, 5, 14, 8, 7, 8, -1], [9, 5, 11, 5, -1, -1, 104], [12, 8, 14, 8, -1, -1, 101]], [6, 5, 9, 9]], [[104], 7]], [[[[1, 0, 11, 13, 1, 8, -1], [1, 0, 8, 11, 2, 5, -1], [1, 0, 3, 11, 3, 4, -1], [1, 10, 1, 11, -1, -1, 103], [1, 0, 3, 1, -1, -1, 107], [4, 0, 8, 10, 6, 7, -1], [4, 10, 6, 10, -1, -1, 105], [6, 0, 8, 0, -1, -1, 108], [7, 0, 11, 13, 9, 12, -1], [7, 1, 8, 13, 10, 11, -1], [7, 1, 8, 3, -1, -1, 104], [8, 11, 8, 13, -1, -1, 106], [9, 0, 11, 13, 13, 14, -1], [9, 10, 11, 13, -1, -1, 100], [10, 0, 11, 5, 15, 16, -1], [10, 0, 10, 3, -1, -1, 102], [11, 2, 11, 5, -1, -1, 101]], [6, 2, 7, 6]], [[104], 11]]], [[[[[2, 0, 9, 8, 1, 6, -1], [2, 0, 8, 8, 2, 3, -1], [2, 8, 4, 8, -1, -1, 101], [4, 0, 8, 5, 4, 5, -1], [4, 0, 5, 1, -1, -1, 102], [5, 4, 8, 5, -1, -1, 103], [7, 0, 9, 3, 7, 8, -1], [7, 0, 7, 3, -1, -1, 104], [7, 1, 9, 3, 9, 10, -1], [7, 2, 8, 3, -1, -1, 105], [7, 1, 9, 3, -1, -1, 100]], [6, 1, 9, 4]], [[100, 103, 104, 105], 11]], [[[[0, 0, 10, 11, 1, 10, -1], [0, 1, 5, 10, 2, 5, -1], [0, 1, 2, 10, 3, 4, -1], [1, 7, 1, 10, -1, -1, 102], [0, 1, 2, 4, -1, -1, 105], [3, 6, 5, 8, 6, 7, -1], [4, 7, 4, 8, -1, -1, 100], [3, 6, 5, 7, 8, 9, -1], [3, 6, 5, 7, -1, -1, 104], [3, 6, 5, 6, -1, -1, 108], [4, 0, 10, 11, 11, 14, -1], [4, 0, 7, 11, 12, 13, -1], [4, 0, 6, 1, -1, -1, 101], [4, 10, 7, 11, -1, -1, 109], [7, 0, 10, 11, 15, 16, -1], [7, 4, 7, 5, -1, -1, 103], [8, 0, 10, 11, 17, 18, -1], [8, 10, 9, 11, -1, -1, 106], [10, 0, 10, 0, -1, -1, 107]], [5, 3, 8, 6]], [[103, 104, 108], 17]], [[[[0, 3, 12, 13, 1, 6, -1], [0, 4, 11, 13, 2, 3, -1], [1, 4, 1, 4, -1, -1, 105], [0, 9, 11, 13, 4, 5, -1], [0, 9, 3, 10, -1, -1, 100], [8, 12, 11, 13, -1, -1, 102], [10, 3, 12, 9, 7, 8, -1], [10, 5, 12, 7, -1, -1, 103], [12, 3, 12, 9, 9, 10, -1], [12, 9, 12, 9, -1, -1, 101], [12, 3, 12, 6, -1, -1, 104]], [11, 5, 11, 9]], [[103], 9]], [[[[0, 0, 14, 15, 1, 10, -1], [0, 2, 8, 14, 2, 5, -1], [0, 9, 1, 14, 3, 4, -1], [0, 12, 0, 14, -1, -1, 107], [1, 9, 1, 10, -1, -1, 109], [1, 2, 8, 8, 6, 7, -1], [1, 2, 3, 4, -1, -1, 103], [3, 5, 8, 8, 8, 9, -1], [3, 8, 3, 8, -1, -1, 106], [5, 5, 8, 7, -1, -1, 102], [6, 0, 14, 15, 11, 16, -1], [6, 0, 11, 15, 12, 13, -1], [6, 1, 7, 2, -1, -1, 105], [7, 0, 11, 15, 14, 15, -1], [7, 0, 8, 0, -1, -1, 104], [9, 12, 11, 15, -1, -1, 101], [11, 6, 14, 12, 17, 18, -1], [11, 7, 13, 8, -1, -1, 100], [11, 6, 14, 12, 19, 20, -1], [11, 12, 14, 12, -1, -1, 108], [11, 6, 14, 6, -1, -1, 110]], [6, 1, 10, 1]], [[105], 9]], [[[[0, 4, 14, 14, 1, 6, -1], [0, 4, 3, 10, 2, 3, -1], [0, 10, 0, 10, -1, -1, 101], [0, 4, 3, 9, 4, 5, -1], [1, 7, 2, 9, -1, -1, 104], [0, 4, 3, 5, -1, -1, 105], [6, 4, 14, 14, 7, 8, -1], [6, 10, 8, 11, -1, -1, 103], [9, 4, 14, 14, 9, 10, -1], [9, 4, 10, 4, -1, -1, 102], [11, 12, 14, 14, -1, -1, 100]], [9, 12, 13, 13]], [[100], 7]], [[[[1, 0, 14, 14, 1, 8, -1], [1, 5, 6, 14, 2, 5, -1], [1, 5, 5, 14, 3, 4, -1], [1, 5, 2, 8, -1, -1, 104], [3, 12, 5, 14, -1, -1, 101], [3, 9, 6, 10, 6, 7, -1], [3, 9, 6, 10, -1, -1, 100], [5, 9, 6, 9, -1, -1, 102], [7, 0, 14, 12, 9, 12, -1], [7, 6, 10, 12, 10, 11, -1], [8, 11, 8, 12, -1, -1, 103], [7, 6, 10, 9, -1, -1, 106], [11, 0, 14, 12, 13, 14, -1], [11, 0, 13, 3, -1, -1, 105], [11, 11, 14, 12, -1, -1, 107]], [5, 12, 9, 15]], [[101, 103], 11]], [[[[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, 13, 13, 1, 6, -1], [1, 0, 10, 13, 2, 3, -1], [1, 11, 1, 13, -1, -1, 102], [8, 0, 10, 10, 4, 5, -1], [8, 0, 8, 1, -1, -1, 103], [8, 7, 10, 10, -1, -1, 106], [10, 7, 13, 10, 7, 10, -1], [10, 7, 13, 10, 8, 9, -1], [10, 10, 11, 10, -1, -1, 105], [11, 7, 13, 8, -1, -1, 101], [12, 8, 13, 9, 11, 12, -1], [12, 8, 12, 9, -1, -1, 104], [12, 8, 13, 9, -1, -1, 100]], [12, 0, 12, 0]], [[], 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	`[[], 5]`	`[[], 5]`	Passed
case 1	`[[], 1]`	`[[], 1]`	Passed
case 2	`[[100, 101], 5]`	`[[100, 101], 5]`	Passed
case 3	`[[], 1]`	`[[], 1]`	Passed
case 4	`[[], 5]`	`[[], 5]`	Passed
case 5	`[[104], 5]`	`[[104], 5]`	Passed
case 6	`[[], 5]`	`[[], 5]`	Passed
case 7	`[[], 3]`	`[[], 3]`	Passed

SHA-256 / c2ef0711b1919c9079cb01369421c4b0730497debfd8946e7fad927432f2c796

Verification & scope

A deterministic bounded teaching model with stipulated toy conventions; not a production physics engine or spatial index. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.

Observations recorded using Python 3.12.14 at 2026-09-29T14:50:58.999291+00:00.

Case digest / 57a945e35ea33f0dc1251a345cc85590f7dd9dd40eceea67b86af53e4c95906f