broken_source:
"""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 = [[[[[[5, 1, 11, 3, 11], [44, 11, 8, 12, 9], [49, 10, 8, 11, 9], [19, 0, 12, 1, 12]], 2, 2, [8, 9, 12, 14]], [[5, 19, 44, 49], 5, 1]], [[[[41, 4, 10, 5, 12], [18, 13, 15, 14, 15], [8, 15, 2, 16, 5], [21, 13, 14, 14, 16], [43, 10, 4, 13, 6], [1, 8, 15, 9, 16]], 1, 3, [9, 8, 10, 12]], [[1, 8, 43], 17, 3]], [[[[3, 15, 7, 16, 7], [5, 1, 8, 3, 10], [28, 2, 13, 3, 14], [8, 13, 13, 14, 14], [16, 8, 14, 11, 16], [42, 11, 14, 14, 14], [17, 0, 15, 1, 15]], 1, 1, [3, 9, 5, 14]], [[5, 17, 28], 5, 1]], [[[[25, 14, 12, 16, 13], [7, 2, 13, 3, 14], [22, 7, 4, 7, 5], [33, 9, 9, 11, 11]], 1, 3, [5, 1, 5, 2]], [[22], 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]], [[[[2, 8, 0, 10, 1], [48, 2, 13, 2, 16], [16, 0, 6, 3, 8], [24, 0, 15, 1, 16], [21, 6, 1, 9, 4], [20, 10, 5, 11, 8], [9, 6, 7, 6, 7]], 2, 2, [7, 1, 12, 3]], [[2, 9, 16, 20, 21], 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]], [[[[42, 6, 14, 7, 16], [40, 13, 14, 13, 16]], 1, 3, [8, 6, 13, 7]], [[], 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]], [[[[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]], [[[[45, 15, 11, 16, 11], [24, 11, 4, 12, 5], [3, 1, 6, 1, 9], [37, 12, 8, 15, 11], [44, 7, 10, 9, 11], [9, 13, 4, 16, 5], [27, 11, 11, 11, 14]], 1, 3, [7, 13, 9, 15]], [[3, 27, 44], 17, 3]], [[[[44, 4, 13, 6, 13], [34, 7, 8, 8, 11], [5, 6, 8, 7, 10], [32, 0, 9, 3, 12], [47, 5, 0, 7, 1], [8, 13, 1, 13, 1], [1, 10, 15, 11, 16], [30, 0, 10, 3, 13], [45, 3, 7, 4, 7]], 2, 3, [2, 6, 6, 7]], [[34, 45, 47], 9, 2]], [[[[30, 13, 11, 14, 11], [37, 9, 10, 12, 13], [17, 4, 10, 5, 13], [2, 8, 8, 8, 11], [27, 12, 0, 12, 0], [31, 2, 3, 3, 4]], 1, 2, [11, 4, 12, 6]], [[27], 9, 2]], [[[[17, 15, 0, 15, 0], [8, 3, 11, 5, 11], [2, 13, 1, 13, 2], [37, 4, 11, 4, 12], [28, 3, 7, 6, 8], [30, 15, 3, 16, 4], [11, 1, 2, 1, 4]], 2, 3, [6, 11, 7, 16]], [[8, 28, 37], 9, 2]], [[[[16, 3, 0, 5, 3], [33, 4, 15, 7, 16], [42, 9, 9, 11, 11], [10, 11, 6, 14, 7], [29, 12, 11, 14, 11]], 3, 1, [5, 10, 6, 10]], [[33], 5, 1]], [[[[28, 8, 6, 10, 6], [2, 15, 11, 16, 14], [46, 11, 3, 12, 6], [48, 6, 1, 9, 1], [42, 6, 5, 7, 6], [20, 6, 0, 6, 0], [7, 15, 4, 16, 5], [25, 4, 15, 4, 16]], 1, 1, [2, 5, 6, 7]], [[20, 42, 48], 5, 1]]], [[[[[23, 8, 12, 9, 13], [11, 5, 4, 8, 6], [13, 4, 4, 4, 4], [40, 4, 5, 6, 5], [28, 15, 10, 16, 10], [14, 5, 14, 7, 16]], 3, 2, [2, 1, 4, 1]], [[11, 13, 40], 5, 1]], [[[[24, 7, 9, 7, 12], [27, 7, 14, 10, 15], [4, 6, 10, 8, 12]], 1, 2, [4, 10, 6, 10]], [[4, 24, 27], 5, 1]], [[[[15, 10, 8, 13, 11], [12, 14, 4, 16, 5], [28, 15, 13, 16, 13], [5, 3, 1, 4, 4], [29, 3, 0, 6, 2], [14, 6, 11, 8, 11], [37, 3, 11, 4, 13], [26, 13, 11, 15, 13], [35, 13, 9, 16, 12], [9, 15, 9, 16, 12]], 1, 1, [9, 14, 14, 18]], [[9, 14, 15, 26, 28, 35], 5, 1]], [[[[8, 15, 5, 16, 6], [23, 12, 4, 12, 5], [39, 8, 1, 8, 1], [41, 13, 11, 15, 14], [27, 12, 11, 12, 12]], 1, 2, [8, 3, 10, 8]], [[27, 39, 41], 13, 2]], [[[[42, 4, 12, 4, 15], [5, 15, 7, 15, 8], [35, 10, 5, 11, 5], [16, 2, 12, 4, 15], [39, 6, 12, 8, 15], [40, 15, 14, 16, 16], [33, 13, 7, 14, 9], [46, 9, 13, 9, 16]], 2, 1, [9, 1, 13, 6]], [[5, 33, 35, 39], 5, 1]], [[[[17, 1, 13, 1, 15], [4, 12, 5, 14, 8], [42, 0, 3, 1, 5], [1, 15, 3, 16, 3]], 2, 1, [13, 14, 18, 18]], [[4], 5, 1]], [[[[42, 9, 3, 10, 5], [26, 12, 6, 14, 7], [12, 15, 5, 16, 7], [28, 0, 7, 0, 8], [3, 1, 10, 3, 13], [22, 0, 11, 0, 14], [13, 5, 1, 8, 2], [45, 5, 7, 6, 10], [40, 13, 2, 14, 5]], 3, 3, [12, 11, 15, 11]], [[13, 28, 45], 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]]], [[[[[12, 15, 3, 16, 4], [5, 7, 11, 9, 14], [24, 9, 4, 11, 7]], 2, 2, [14, 5, 17, 10]], [[5, 12, 24], 5, 1]], [[[[46, 12, 14, 13, 15], [30, 1, 6, 2, 7], [2, 8, 0, 10, 0], [4, 15, 12, 15, 14], [24, 12, 5, 14, 5], [31, 2, 15, 2, 15]], 2, 3, [10, 11, 14, 14]], [[4, 46], 5, 1]], [[[[30, 5, 1, 5, 3], [15, 13, 14, 13, 16], [18, 15, 10, 16, 10]], 1, 1, [2, 3, 4, 4]], [[30], 5, 1]], [[[[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]], [[[[3, 14, 5, 15, 7], [29, 15, 0, 16, 1], [25, 1, 10, 1, 12], [10, 6, 14, 6, 16], [27, 5, 6, 5, 9], [43, 0, 10, 3, 13], [33, 4, 9, 7, 9], [45, 9, 4, 11, 7], [18, 8, 14, 11, 15], [28, 11, 9, 12, 10]], 1, 1, [8, 9, 11, 10]], [[10, 18, 25, 27, 28, 33, 43], 5, 1]], [[[[28, 4, 4, 4, 7], [24, 7, 10, 9, 12], [14, 5, 5, 7, 6], [49, 6, 0, 7, 3], [20, 6, 10, 7, 13], [13, 1, 8, 3, 10], [3, 10, 12, 10, 13], [36, 2, 5, 5, 7], [38, 11, 11, 14, 14], [40, 10, 5, 12, 6], [25, 14, 11, 16, 12]], 3, 2, [13, 13, 17, 14]], [[3, 24, 25, 38], 9, 2]], [[[[8, 3, 4, 3, 5], [37, 2, 9, 2, 9], [18, 9, 12, 10, 13], [6, 11, 7, 14, 10], [36, 0, 5, 1, 5], [25, 5, 2, 6, 5], [2, 3, 1, 3, 4], [39, 2, 11, 4, 12]], 1, 3, [0, 5, 2, 10]], [[2, 6, 8, 25, 36, 37, 39], 17, 3]], [[[[28, 6, 13, 6, 15], [12, 0, 1, 0, 3], [30, 1, 2, 2, 2], [9, 14, 12, 16, 13], [7, 5, 11, 8, 12]], 1, 3, [8, 2, 12, 3]], [[7], 13, 3]]], [[[[[41, 10, 13, 10, 13], [4, 5, 13, 5, 14], [36, 10, 15, 12, 16], [35, 5, 5, 7, 6], [47, 9, 4, 10, 5], [27, 10, 14, 13, 14], [13, 8, 8, 10, 10], [15, 6, 14, 8, 14], [11, 11, 3, 13, 4]], 2, 2, [7, 2, 7, 7]], [[15, 35], 9, 2]], [[[[49, 11, 1, 11, 4], [4, 9, 14, 12, 16], [3, 1, 4, 2, 7], [11, 10, 4, 10, 5], [25, 6, 12, 9, 12], [26, 11, 14, 13, 15], [36, 3, 14, 6, 16], [18, 3, 1, 3, 2], [6, 15, 5, 16, 7], [31, 3, 11, 3, 12], [40, 2, 6, 4, 9]], 3, 3, [11, 14, 15, 14]], [[4, 25, 26, 40], 5, 1]], [[[[34, 13, 8, 16, 9], [35, 0, 9, 2, 12], [8, 11, 12, 13, 13], [43, 12, 9, 15, 9], [42, 12, 3, 15, 5], [21, 13, 3, 13, 3], [27, 12, 0, 12, 3], [37, 6, 2, 8, 5], [25, 0, 9, 2, 12]], 2, 3, [10, 6, 10, 11]], [[8, 37, 42], 13, 2]], [[[[37, 6, 14, 6, 16], [40, 1, 4, 3, 4]], 3, 3, [5, 10, 6, 10]], [[37, 40], 1, 0]], [[[[27, 4, 14, 7, 14], [36, 6, 1, 8, 4], [10, 8, 9, 10, 11], [15, 13, 4, 13, 5], [24, 9, 5, 12, 7], [48, 11, 0, 14, 1], [20, 5, 6, 7, 9], [47, 1, 11, 1, 12]], 3, 3, [6, 7, 6, 7]], [[20, 36], 5, 1]], [[[[12, 12, 2, 13, 3], [39, 8, 10, 9, 10], [18, 7, 1, 7, 3]], 2, 3, [8, 12, 9, 16]], [[39], 5, 1]], [[[[40, 14, 12, 14, 13], [36, 3, 9, 5, 9], [27, 1, 0, 1, 3], [22, 0, 9, 2, 12], [9, 7, 11, 7, 12], [6, 10, 7, 12, 8]], 1, 1, [4, 10, 5, 10]], [[6, 9, 22, 36], 5, 1]], [[[[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]]]]
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)

source:
"""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 = [[[[[[5, 1, 11, 3, 11], [44, 11, 8, 12, 9], [49, 10, 8, 11, 9], [19, 0, 12, 1, 12]], 2, 2, [8, 9, 12, 14]], [[5, 19, 44, 49], 5, 1]], [[[[41, 4, 10, 5, 12], [18, 13, 15, 14, 15], [8, 15, 2, 16, 5], [21, 13, 14, 14, 16], [43, 10, 4, 13, 6], [1, 8, 15, 9, 16]], 1, 3, [9, 8, 10, 12]], [[1, 8, 43], 17, 3]], [[[[3, 15, 7, 16, 7], [5, 1, 8, 3, 10], [28, 2, 13, 3, 14], [8, 13, 13, 14, 14], [16, 8, 14, 11, 16], [42, 11, 14, 14, 14], [17, 0, 15, 1, 15]], 1, 1, [3, 9, 5, 14]], [[5, 17, 28], 5, 1]], [[[[25, 14, 12, 16, 13], [7, 2, 13, 3, 14], [22, 7, 4, 7, 5], [33, 9, 9, 11, 11]], 1, 3, [5, 1, 5, 2]], [[22], 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]], [[[[2, 8, 0, 10, 1], [48, 2, 13, 2, 16], [16, 0, 6, 3, 8], [24, 0, 15, 1, 16], [21, 6, 1, 9, 4], [20, 10, 5, 11, 8], [9, 6, 7, 6, 7]], 2, 2, [7, 1, 12, 3]], [[2, 9, 16, 20, 21], 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]], [[[[42, 6, 14, 7, 16], [40, 13, 14, 13, 16]], 1, 3, [8, 6, 13, 7]], [[], 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]], [[[[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]], [[[[45, 15, 11, 16, 11], [24, 11, 4, 12, 5], [3, 1, 6, 1, 9], [37, 12, 8, 15, 11], [44, 7, 10, 9, 11], [9, 13, 4, 16, 5], [27, 11, 11, 11, 14]], 1, 3, [7, 13, 9, 15]], [[3, 27, 44], 17, 3]], [[[[44, 4, 13, 6, 13], [34, 7, 8, 8, 11], [5, 6, 8, 7, 10], [32, 0, 9, 3, 12], [47, 5, 0, 7, 1], [8, 13, 1, 13, 1], [1, 10, 15, 11, 16], [30, 0, 10, 3, 13], [45, 3, 7, 4, 7]], 2, 3, [2, 6, 6, 7]], [[34, 45, 47], 9, 2]], [[[[30, 13, 11, 14, 11], [37, 9, 10, 12, 13], [17, 4, 10, 5, 13], [2, 8, 8, 8, 11], [27, 12, 0, 12, 0], [31, 2, 3, 3, 4]], 1, 2, [11, 4, 12, 6]], [[27], 9, 2]], [[[[17, 15, 0, 15, 0], [8, 3, 11, 5, 11], [2, 13, 1, 13, 2], [37, 4, 11, 4, 12], [28, 3, 7, 6, 8], [30, 15, 3, 16, 4], [11, 1, 2, 1, 4]], 2, 3, [6, 11, 7, 16]], [[8, 28, 37], 9, 2]], [[[[16, 3, 0, 5, 3], [33, 4, 15, 7, 16], [42, 9, 9, 11, 11], [10, 11, 6, 14, 7], [29, 12, 11, 14, 11]], 3, 1, [5, 10, 6, 10]], [[33], 5, 1]], [[[[28, 8, 6, 10, 6], [2, 15, 11, 16, 14], [46, 11, 3, 12, 6], [48, 6, 1, 9, 1], [42, 6, 5, 7, 6], [20, 6, 0, 6, 0], [7, 15, 4, 16, 5], [25, 4, 15, 4, 16]], 1, 1, [2, 5, 6, 7]], [[20, 42, 48], 5, 1]]], [[[[[23, 8, 12, 9, 13], [11, 5, 4, 8, 6], [13, 4, 4, 4, 4], [40, 4, 5, 6, 5], [28, 15, 10, 16, 10], [14, 5, 14, 7, 16]], 3, 2, [2, 1, 4, 1]], [[11, 13, 40], 5, 1]], [[[[24, 7, 9, 7, 12], [27, 7, 14, 10, 15], [4, 6, 10, 8, 12]], 1, 2, [4, 10, 6, 10]], [[4, 24, 27], 5, 1]], [[[[15, 10, 8, 13, 11], [12, 14, 4, 16, 5], [28, 15, 13, 16, 13], [5, 3, 1, 4, 4], [29, 3, 0, 6, 2], [14, 6, 11, 8, 11], [37, 3, 11, 4, 13], [26, 13, 11, 15, 13], [35, 13, 9, 16, 12], [9, 15, 9, 16, 12]], 1, 1, [9, 14, 14, 18]], [[9, 14, 15, 26, 28, 35], 5, 1]], [[[[8, 15, 5, 16, 6], [23, 12, 4, 12, 5], [39, 8, 1, 8, 1], [41, 13, 11, 15, 14], [27, 12, 11, 12, 12]], 1, 2, [8, 3, 10, 8]], [[27, 39, 41], 13, 2]], [[[[42, 4, 12, 4, 15], [5, 15, 7, 15, 8], [35, 10, 5, 11, 5], [16, 2, 12, 4, 15], [39, 6, 12, 8, 15], [40, 15, 14, 16, 16], [33, 13, 7, 14, 9], [46, 9, 13, 9, 16]], 2, 1, [9, 1, 13, 6]], [[5, 33, 35, 39], 5, 1]], [[[[17, 1, 13, 1, 15], [4, 12, 5, 14, 8], [42, 0, 3, 1, 5], [1, 15, 3, 16, 3]], 2, 1, [13, 14, 18, 18]], [[4], 5, 1]], [[[[42, 9, 3, 10, 5], [26, 12, 6, 14, 7], [12, 15, 5, 16, 7], [28, 0, 7, 0, 8], [3, 1, 10, 3, 13], [22, 0, 11, 0, 14], [13, 5, 1, 8, 2], [45, 5, 7, 6, 10], [40, 13, 2, 14, 5]], 3, 3, [12, 11, 15, 11]], [[13, 28, 45], 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]]], [[[[[12, 15, 3, 16, 4], [5, 7, 11, 9, 14], [24, 9, 4, 11, 7]], 2, 2, [14, 5, 17, 10]], [[5, 12, 24], 5, 1]], [[[[46, 12, 14, 13, 15], [30, 1, 6, 2, 7], [2, 8, 0, 10, 0], [4, 15, 12, 15, 14], [24, 12, 5, 14, 5], [31, 2, 15, 2, 15]], 2, 3, [10, 11, 14, 14]], [[4, 46], 5, 1]], [[[[30, 5, 1, 5, 3], [15, 13, 14, 13, 16], [18, 15, 10, 16, 10]], 1, 1, [2, 3, 4, 4]], [[30], 5, 1]], [[[[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]], [[[[3, 14, 5, 15, 7], [29, 15, 0, 16, 1], [25, 1, 10, 1, 12], [10, 6, 14, 6, 16], [27, 5, 6, 5, 9], [43, 0, 10, 3, 13], [33, 4, 9, 7, 9], [45, 9, 4, 11, 7], [18, 8, 14, 11, 15], [28, 11, 9, 12, 10]], 1, 1, [8, 9, 11, 10]], [[10, 18, 25, 27, 28, 33, 43], 5, 1]], [[[[28, 4, 4, 4, 7], [24, 7, 10, 9, 12], [14, 5, 5, 7, 6], [49, 6, 0, 7, 3], [20, 6, 10, 7, 13], [13, 1, 8, 3, 10], [3, 10, 12, 10, 13], [36, 2, 5, 5, 7], [38, 11, 11, 14, 14], [40, 10, 5, 12, 6], [25, 14, 11, 16, 12]], 3, 2, [13, 13, 17, 14]], [[3, 24, 25, 38], 9, 2]], [[[[8, 3, 4, 3, 5], [37, 2, 9, 2, 9], [18, 9, 12, 10, 13], [6, 11, 7, 14, 10], [36, 0, 5, 1, 5], [25, 5, 2, 6, 5], [2, 3, 1, 3, 4], [39, 2, 11, 4, 12]], 1, 3, [0, 5, 2, 10]], [[2, 6, 8, 25, 36, 37, 39], 17, 3]], [[[[28, 6, 13, 6, 15], [12, 0, 1, 0, 3], [30, 1, 2, 2, 2], [9, 14, 12, 16, 13], [7, 5, 11, 8, 12]], 1, 3, [8, 2, 12, 3]], [[7], 13, 3]]], [[[[[41, 10, 13, 10, 13], [4, 5, 13, 5, 14], [36, 10, 15, 12, 16], [35, 5, 5, 7, 6], [47, 9, 4, 10, 5], [27, 10, 14, 13, 14], [13, 8, 8, 10, 10], [15, 6, 14, 8, 14], [11, 11, 3, 13, 4]], 2, 2, [7, 2, 7, 7]], [[15, 35], 9, 2]], [[[[49, 11, 1, 11, 4], [4, 9, 14, 12, 16], [3, 1, 4, 2, 7], [11, 10, 4, 10, 5], [25, 6, 12, 9, 12], [26, 11, 14, 13, 15], [36, 3, 14, 6, 16], [18, 3, 1, 3, 2], [6, 15, 5, 16, 7], [31, 3, 11, 3, 12], [40, 2, 6, 4, 9]], 3, 3, [11, 14, 15, 14]], [[4, 25, 26, 40], 5, 1]], [[[[34, 13, 8, 16, 9], [35, 0, 9, 2, 12], [8, 11, 12, 13, 13], [43, 12, 9, 15, 9], [42, 12, 3, 15, 5], [21, 13, 3, 13, 3], [27, 12, 0, 12, 3], [37, 6, 2, 8, 5], [25, 0, 9, 2, 12]], 2, 3, [10, 6, 10, 11]], [[8, 37, 42], 13, 2]], [[[[37, 6, 14, 6, 16], [40, 1, 4, 3, 4]], 3, 3, [5, 10, 6, 10]], [[37, 40], 1, 0]], [[[[27, 4, 14, 7, 14], [36, 6, 1, 8, 4], [10, 8, 9, 10, 11], [15, 13, 4, 13, 5], [24, 9, 5, 12, 7], [48, 11, 0, 14, 1], [20, 5, 6, 7, 9], [47, 1, 11, 1, 12]], 3, 3, [6, 7, 6, 7]], [[20, 36], 5, 1]], [[[[12, 12, 2, 13, 3], [39, 8, 10, 9, 10], [18, 7, 1, 7, 3]], 2, 3, [8, 12, 9, 16]], [[39], 5, 1]], [[[[40, 14, 12, 14, 13], [36, 3, 9, 5, 9], [27, 1, 0, 1, 3], [22, 0, 9, 2, 12], [9, 7, 11, 7, 12], [6, 10, 7, 12, 8]], 1, 1, [4, 10, 5, 10]], [[6, 9, 22, 36], 5, 1]], [[[[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]]]]
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)

prompt:
Objects are stored in a child covering the wrong region and queries miss them.

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].

split: open-access


broken_source:
"""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)

meaning: Fixture-count band, not measured model difficulty

deps: stdlib

source:
"""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)

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

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].

split: open-access


prompt:
All ungrouped fixtures stop colliding with each other.

solve(fixtures, candidates): fixture [id, body, category bits, mask bits, group, sensor, body type]. A candidate [a,b] is accepted unless: same body; neither body is dynamic; both are sensors. Group rule: equal nonzero groups override masks (positive always collide, negative never); otherwise require (catA & maskB) and (catB & maskA). Return sorted unique [min,max] accepted pairs.

split: open-access


prompt:
A fixture that masks out another still collides with it.

solve(fixtures, candidates): fixture [id, body, category bits, mask bits, group, sensor, body type]. A candidate [a,b] is accepted unless: same body; neither body is dynamic; both are sensors. Group rule: equal nonzero groups override masks (positive always collide, negative never); otherwise require (catA & maskB) and (catB & maskA). Return sorted unique [min,max] accepted pairs.

split: open-access


prompt:
Ragdoll parts in the same positive group ignore each other when masks disagree.

solve(fixtures, candidates): fixture [id, body, category bits, mask bits, group, sensor, body type]. A candidate [a,b] is accepted unless: same body; neither body is dynamic; both are sensors. Group rule: equal nonzero groups override masks (positive always collide, negative never); otherwise require (catA & maskB) and (catB & maskA). Return sorted unique [min,max] accepted pairs.

split: open-access


prompt:
Kinematic platforms generate pairs with static level geometry.

solve(fixtures, candidates): fixture [id, body, category bits, mask bits, group, sensor, body type]. A candidate [a,b] is accepted unless: same body; neither body is dynamic; both are sensors. Group rule: equal nonzero groups override masks (positive always collide, negative never); otherwise require (catA & maskB) and (catB & maskA). Return sorted unique [min,max] accepted pairs.

split: open-access


prompt:
Compound bodies collide with themselves.

solve(fixtures, candidates): fixture [id, body, category bits, mask bits, group, sensor, body type]. A candidate [a,b] is accepted unless: same body; neither body is dynamic; both are sensors. Group rule: equal nonzero groups override masks (positive always collide, negative never); otherwise require (catA & maskB) and (catB & maskA). Return sorted unique [min,max] accepted pairs.

split: open-access


prompt:
Trigger volumes never report overlaps with bodies.

solve(fixtures, candidates): fixture [id, body, category bits, mask bits, group, sensor, body type]. A candidate [a,b] is accepted unless: same body; neither body is dynamic; both are sensors. Group rule: equal nonzero groups override masks (positive always collide, negative never); otherwise require (catA & maskB) and (catB & maskA). Return sorted unique [min,max] accepted pairs.

split: open-access


prompt:
The same pair appears twice when candidates list both orders.

solve(fixtures, candidates): fixture [id, body, category bits, mask bits, group, sensor, body type]. A candidate [a,b] is accepted unless: same body; neither body is dynamic; both are sensors. Group rule: equal nonzero groups override masks (positive always collide, negative never); otherwise require (catA & maskB) and (catB & maskA). Return sorted unique [min,max] accepted pairs.

split: open-access


prompt:
Pairs stored as (b,a) end and restart every frame.

solve(prev, curr, asleep): contact pair cache update. Pairs are unordered; self pairs in curr are ignored. Previous pairs whose two bodies are both asleep persist even if not re-reported. Return [begin, end, persist] as sorted [min,max] lists.

split: open-access


prompt:
A body starts a contact with itself.

solve(prev, curr, asleep): contact pair cache update. Pairs are unordered; self pairs in curr are ignored. Previous pairs whose two bodies are both asleep persist even if not re-reported. Return [begin, end, persist] as sorted [min,max] lists.

split: open-access


prompt:
Contacts between a sleeping and a departing awake body never end.

solve(prev, curr, asleep): contact pair cache update. Pairs are unordered; self pairs in curr are ignored. Previous pairs whose two bodies are both asleep persist even if not re-reported. Return [begin, end, persist] as sorted [min,max] lists.

split: open-access


prompt:
Stacks that fall asleep lose their contacts and wake up falling.

solve(prev, curr, asleep): contact pair cache update. Pairs are unordered; self pairs in curr are ignored. Previous pairs whose two bodies are both asleep persist even if not re-reported. Return [begin, end, persist] as sorted [min,max] lists.

split: open-access


prompt:
New contacts are reported as ending on their first frame.

solve(prev, curr, asleep): contact pair cache update. Pairs are unordered; self pairs in curr are ignored. Previous pairs whose two bodies are both asleep persist even if not re-reported. Return [begin, end, persist] as sorted [min,max] lists.

split: open-access


prompt:
Objects on the far edge sort next to the origin and the LBVH gets huge nodes.

solve(pts, bounds): LBVH ordering. Each centroid [id,x,y] is quantized per axis to min(1023, max(0, floor((c-lo)/(hi-lo)*1024))) (0 for a flat axis), and the 10-bit values are interleaved with x in even bits and y in odd bits. Return [[id, code]] sorted by (code, numeric id).

split: open-access


prompt:
Sort order becomes y-major, contradicting the contract and cached codes.

solve(pts, bounds): LBVH ordering. Each centroid [id,x,y] is quantized per axis to min(1023, max(0, floor((c-lo)/(hi-lo)*1024))) (0 for a flat axis), and the 10-bit values are interleaved with x in even bits and y in odd bits. Return [[id, code]] sorted by (code, numeric id).

split: open-access


prompt:
Coordinate bits collide at the nibble stage and distant objects share codes.

solve(pts, bounds): LBVH ordering. Each centroid [id,x,y] is quantized per axis to min(1023, max(0, floor((c-lo)/(hi-lo)*1024))) (0 for a flat axis), and the 10-bit values are interleaved with x in even bits and y in odd bits. Return [[id, code]] sorted by (code, numeric id).

split: open-access


prompt:
Scenes that are not square produce skewed codes.

solve(pts, bounds): LBVH ordering. Each centroid [id,x,y] is quantized per axis to min(1023, max(0, floor((c-lo)/(hi-lo)*1024))) (0 for a flat axis), and the 10-bit values are interleaved with x in even bits and y in odd bits. Return [[id, code]] sorted by (code, numeric id).

split: open-access


prompt:
Planar scenes get codes offset from the contract and mismatch cached trees.

solve(pts, bounds): LBVH ordering. Each centroid [id,x,y] is quantized per axis to min(1023, max(0, floor((c-lo)/(hi-lo)*1024))) (0 for a flat axis), and the 10-bit values are interleaved with x in even bits and y in odd bits. Return [[id, code]] sorted by (code, numeric id).

split: open-access


prompt:
Build output is nondeterministic across id widths (10 sorts before 9).

solve(pts, bounds): LBVH ordering. Each centroid [id,x,y] is quantized per axis to min(1023, max(0, floor((c-lo)/(hi-lo)*1024))) (0 for a flat axis), and the 10-bit values are interleaved with x in even bits and y in odd bits. Return [[id, code]] sorted by (code, numeric id).

split: open-access


prompt:
Slightly out-of-bounds objects land at the far end of the order.

solve(pts, bounds): LBVH ordering. Each centroid [id,x,y] is quantized per axis to min(1023, max(0, floor((c-lo)/(hi-lo)*1024))) (0 for a flat axis), and the 10-bit values are interleaved with x in even bits and y in odd bits. Return [[id, code]] sorted by (code, numeric id).

split: open-access


prompt:
Leftward rays step cells at the wrong times and skip cells.

solve(o, d, cs, max_t): Amanatides-Woo traversal of a uniform grid for a ray o+t*d (d not normalized). Start in cell floor(o/cs); step the axis with the smaller next boundary t (x on ties) while that t <= max_t, at most 64 cells. Return the visited cells [[ix,iy],...].

split: open-access


prompt:
Leftward rays step x repeatedly without advancing the boundary time.

solve(o, d, cs, max_t): Amanatides-Woo traversal of a uniform grid for a ray o+t*d (d not normalized). Start in cell floor(o/cs); step the axis with the smaller next boundary t (x on ties) while that t <= max_t, at most 64 cells. Return the visited cells [[ix,iy],...].

split: open-access


prompt:
Diagonal rays visit a different neighbor than the contract and cached tests.

solve(o, d, cs, max_t): Amanatides-Woo traversal of a uniform grid for a ray o+t*d (d not normalized). Start in cell floor(o/cs); step the axis with the smaller next boundary t (x on ties) while that t <= max_t, at most 64 cells. Return the visited cells [[ix,iy],...].

split: open-access


prompt:
A ray ending exactly on a cell border misses that cell.

solve(o, d, cs, max_t): Amanatides-Woo traversal of a uniform grid for a ray o+t*d (d not normalized). Start in cell floor(o/cs); step the axis with the smaller next boundary t (x on ties) while that t <= max_t, at most 64 cells. Return the visited cells [[ix,iy],...].

split: open-access


prompt:
Rays that do not start at y=0 cross rows at wrong times.

solve(o, d, cs, max_t): Amanatides-Woo traversal of a uniform grid for a ray o+t*d (d not normalized). Start in cell floor(o/cs); step the axis with the smaller next boundary t (x on ties) while that t <= max_t, at most 64 cells. Return the visited cells [[ix,iy],...].

split: open-access


prompt:
Long thin objects are placed on too fine a level and span many cells.

solve(objs, base, levels): multi-level grid. Each [id,minx,miny,maxx,maxy] goes to the smallest level l (cell size base*2^l) whose cell size is >= the larger box extent, capped at levels-1; its home cell is floor(min corner / level cell size). Return sorted [[id, level, cx, cy]].

split: open-access


prompt:
Grid level populations shift upward and coarse levels get crowded.

solve(objs, base, levels): multi-level grid. Each [id,minx,miny,maxx,maxy] goes to the smallest level l (cell size base*2^l) whose cell size is >= the larger box extent, capped at levels-1; its home cell is floor(min corner / level cell size). Return sorted [[id, level, cx, cy]].

split: open-access


prompt:
Huge objects are assigned to a level that does not exist.

solve(objs, base, levels): multi-level grid. Each [id,minx,miny,maxx,maxy] goes to the smallest level l (cell size base*2^l) whose cell size is >= the larger box extent, capped at levels-1; its home cell is floor(min corner / level cell size). Return sorted [[id, level, cx, cy]].

split: open-access


prompt:
Objects on coarse levels are hashed to non-existent fine cells.

solve(objs, base, levels): multi-level grid. Each [id,minx,miny,maxx,maxy] goes to the smallest level l (cell size base*2^l) whose cell size is >= the larger box extent, capped at levels-1; its home cell is floor(min corner / level cell size). Return sorted [[id, level, cx, cy]].

split: open-access


prompt:
Neighbor search offsets assume the min corner and miss overlaps.

solve(objs, base, levels): multi-level grid. Each [id,minx,miny,maxx,maxy] goes to the smallest level l (cell size base*2^l) whose cell size is >= the larger box extent, capped at levels-1; its home cell is floor(min corner / level cell size). Return sorted [[id, level, cx, cy]].

split: open-access


prompt:
Large objects need many levels and land on the wrong one.

solve(objs, base, levels): multi-level grid. Each [id,minx,miny,maxx,maxy] goes to the smallest level l (cell size base*2^l) whose cell size is >= the larger box extent, capped at levels-1; its home cell is floor(min corner / level cell size). Return sorted [[id, level, cx, cy]].

split: open-access


prompt:
Scenes with mixed box sizes sweep along a poorly separating axis.

solve(boxes): 3D sweep-and-prune axis selection. Boxes [id,minx,miny,minz,maxx,maxy,maxz]. Pick the axis with the largest population variance of box centres (first axis on ties), then order ids by (min on that axis, id). Return [axis, variance rounded to 6, ordered ids].

split: open-access


prompt:
Reported spread disagrees with the population-variance contract.

solve(boxes): 3D sweep-and-prune axis selection. Boxes [id,minx,miny,minz,maxx,maxy,maxz]. Pick the axis with the largest population variance of box centres (first axis on ties), then order ids by (min on that axis, id). Return [axis, variance rounded to 6, ordered ids].

split: open-access


prompt:
Axis choice flips for distributions with outliers.

solve(boxes): 3D sweep-and-prune axis selection. Boxes [id,minx,miny,minz,maxx,maxy,maxz]. Pick the axis with the largest population variance of box centres (first axis on ties), then order ids by (min on that axis, id). Return [axis, variance rounded to 6, ordered ids].

split: open-access


prompt:
Axis variances mix two axes.

solve(boxes): 3D sweep-and-prune axis selection. Boxes [id,minx,miny,minz,maxx,maxy,maxz]. Pick the axis with the largest population variance of box centres (first axis on ties), then order ids by (min on that axis, id). Return [axis, variance rounded to 6, ordered ids].

split: open-access


prompt:
Endpoint arrays are built out of order and pruning breaks.

solve(boxes): 3D sweep-and-prune axis selection. Boxes [id,minx,miny,minz,maxx,maxy,maxz]. Pick the axis with the largest population variance of box centres (first axis on ties), then order ids by (min on that axis, id). Return [axis, variance rounded to 6, ordered ids].

split: open-access


prompt:
Skewed distributions report the wrong spread.

solve(boxes): 3D sweep-and-prune axis selection. Boxes [id,minx,miny,minz,maxx,maxy,maxz]. Pick the axis with the largest population variance of box centres (first axis on ties), then order ids by (min on that axis, id). Return [axis, variance rounded to 6, ordered ids].

split: open-access


prompt:
Objects moving left or down tunnel because the swept box shrinks.

solve(box, vel, dt, margin, others): CCD broadphase bounds. Swept box = union of box at t and t+dt expanded by margin on all sides. fast = displacement length > half the smaller box extent. Return [swept rounded to 6, fast, sorted ids of others ([id,minx,miny,maxx,maxy]) overlapping the swept box with closed intervals].

split: open-access


prompt:
Sweeps are dt^-1 times too long, flooding narrowphase with candidates.

solve(box, vel, dt, margin, others): CCD broadphase bounds. Swept box = union of box at t and t+dt expanded by margin on all sides. fast = displacement length > half the smaller box extent. Return [swept rounded to 6, fast, sorted ids of others ([id,minx,miny,maxx,maxy]) overlapping the swept box with closed intervals].

split: open-access


prompt:
Contacts approaching from below or left start late.

solve(box, vel, dt, margin, others): CCD broadphase bounds. Swept box = union of box at t and t+dt expanded by margin on all sides. fast = displacement length > half the smaller box extent. Return [swept rounded to 6, fast, sorted ids of others ([id,minx,miny,maxx,maxy]) overlapping the swept box with closed intervals].

split: open-access


prompt:
Thin fast objects are not flagged and tunnel through walls.

solve(box, vel, dt, margin, others): CCD broadphase bounds. Swept box = union of box at t and t+dt expanded by margin on all sides. fast = displacement length > half the smaller box extent. Return [swept rounded to 6, fast, sorted ids of others ([id,minx,miny,maxx,maxy]) overlapping the swept box with closed intervals].

split: open-access


prompt:
At high frame rates everything is flagged for CCD.

solve(box, vel, dt, margin, others): CCD broadphase bounds. Swept box = union of box at t and t+dt expanded by margin on all sides. fast = displacement length > half the smaller box extent. Return [swept rounded to 6, fast, sorted ids of others ([id,minx,miny,maxx,maxy]) overlapping the swept box with closed intervals].

split: open-access


prompt:
Objects resting exactly at the sweep boundary are skipped.

solve(box, vel, dt, margin, others): CCD broadphase bounds. Swept box = union of box at t and t+dt expanded by margin on all sides. fast = displacement length > half the smaller box extent. Return [swept rounded to 6, fast, sorted ids of others ([id,minx,miny,maxx,maxy]) overlapping the swept box with closed intervals].

split: open-access


prompt:
Two bodies moving into each other never collide.

solve(proxies, moved): dynamic-tree pair update. For each distinct moved proxy q (first occurrence order) test every other proxy p; skip p when p also moved and p>q (that pair is found from p). Count every overlap test performed; closed intervals. Return [sorted unique [min,max] pairs, test count].

split: open-access


prompt:
Overlap tests double for moving crowds.

solve(proxies, moved): dynamic-tree pair update. For each distinct moved proxy q (first occurrence order) test every other proxy p; skip p when p also moved and p>q (that pair is found from p). Count every overlap test performed; closed intervals. Return [sorted unique [min,max] pairs, test count].

split: open-access


prompt:
Tree queries and test counts double for proxies touched twice.

solve(proxies, moved): dynamic-tree pair update. For each distinct moved proxy q (first occurrence order) test every other proxy p; skip p when p also moved and p>q (that pair is found from p). Count every overlap test performed; closed intervals. Return [sorted unique [min,max] pairs, test count].

split: open-access


prompt:
Proxies stacked far above still pair.

solve(proxies, moved): dynamic-tree pair update. For each distinct moved proxy q (first occurrence order) test every other proxy p; skip p when p also moved and p>q (that pair is found from p). Count every overlap test performed; closed intervals. Return [sorted unique [min,max] pairs, test count].

split: open-access


prompt:
A self pair is created and one wasted test is counted.

solve(proxies, moved): dynamic-tree pair update. For each distinct moved proxy q (first occurrence order) test every other proxy p; skip p when p also moved and p>q (that pair is found from p). Count every overlap test performed; closed intervals. Return [sorted unique [min,max] pairs, test count].

split: open-access


prompt:
Particles pair with ghosts of where neighbours were last frame.

solve(frames, n): particle hash table of n buckets reused across frames without clearing; a bucket whose stamp is older than the frame is lazily reset on first insert. Cell = floor(x), floor(y); bucket = ((ix*73856093 mod 2^32) xor (iy*19349663 mod 2^32)) mod n. A particle pairs with earlier particles in the same bucket only if they share the exact cell. Per frame return [sorted [min,max] pairs, buckets stamped this frame].

split: open-access


prompt:
Distant particles that hash to the same bucket become neighbours.

solve(frames, n): particle hash table of n buckets reused across frames without clearing; a bucket whose stamp is older than the frame is lazily reset on first insert. Cell = floor(x), floor(y); bucket = ((ix*73856093 mod 2^32) xor (iy*19349663 mod 2^32)) mod n. A particle pairs with earlier particles in the same bucket only if they share the exact cell. Per frame return [sorted [min,max] pairs, buckets stamped this frame].

split: open-access


prompt:
Negative cells map to different buckets than the native engine.

solve(frames, n): particle hash table of n buckets reused across frames without clearing; a bucket whose stamp is older than the frame is lazily reset on first insert. Cell = floor(x), floor(y); bucket = ((ix*73856093 mod 2^32) xor (iy*19349663 mod 2^32)) mod n. A particle pairs with earlier particles in the same bucket only if they share the exact cell. Per frame return [sorted [min,max] pairs, buckets stamped this frame].

split: open-access


prompt:
Bucket distribution differs from the contract and collisions cluster.

solve(frames, n): particle hash table of n buckets reused across frames without clearing; a bucket whose stamp is older than the frame is lazily reset on first insert. Cell = floor(x), floor(y); bucket = ((ix*73856093 mod 2^32) xor (iy*19349663 mod 2^32)) mod n. A particle pairs with earlier particles in the same bucket only if they share the exact cell. Per frame return [sorted [min,max] pairs, buckets stamped this frame].

split: open-access


prompt:
Load reports grow monotonically across frames.

solve(frames, n): particle hash table of n buckets reused across frames without clearing; a bucket whose stamp is older than the frame is lazily reset on first insert. Cell = floor(x), floor(y); bucket = ((ix*73856093 mod 2^32) xor (iy*19349663 mod 2^32)) mod n. A particle pairs with earlier particles in the same bucket only if they share the exact cell. Per frame return [sorted [min,max] pairs, buckets stamped this frame].

split: open-access


prompt:
Pairs with equal minimum x are reported twice.

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

split: open-access


prompt:
Static boxes that just touch a dynamic box are missed.

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

split: open-access


prompt:
Static boxes that start before a dynamic box never pair with it.

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

split: open-access


prompt:
The running index skips boxes and pairs are lost.

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

split: open-access


prompt:
Consumers index the static set with a dynamic id.

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

split: open-access


prompt:
Boxes that move into touching contact never begin a pair.

solve(prev, curr): incremental sweep-and-prune on x. Endpoints [x, 0=min/1=max, id] of prev are sorted, refreshed with curr coordinates and insertion-sorted by (x, kind). Each swap where a min passes left over a max begins a pair (if y overlaps in curr); a max passing left over a min ends a pair. Return [sorted begin pairs, sorted end pairs, swap count], pairs as [min,max].

split: open-access


prompt:
Boxes crossing on x far apart in y create contacts.

solve(prev, curr): incremental sweep-and-prune on x. Endpoints [x, 0=min/1=max, id] of prev are sorted, refreshed with curr coordinates and insertion-sorted by (x, kind). Each swap where a min passes left over a max begins a pair (if y overlaps in curr); a max passing left over a min ends a pair. Return [sorted begin pairs, sorted end pairs, swap count], pairs as [min,max].

split: open-access


prompt:
Boxes sliding past each other while overlapping lose their contact.

solve(prev, curr): incremental sweep-and-prune on x. Endpoints [x, 0=min/1=max, id] of prev are sorted, refreshed with curr coordinates and insertion-sorted by (x, kind). Each swap where a min passes left over a max begins a pair (if y overlaps in curr); a max passing left over a min ends a pair. Return [sorted begin pairs, sorted end pairs, swap count], pairs as [min,max].

split: open-access


prompt:
The endpoint array is corrupted every frame and spurious events fire.

solve(prev, curr): incremental sweep-and-prune on x. Endpoints [x, 0=min/1=max, id] of prev are sorted, refreshed with curr coordinates and insertion-sorted by (x, kind). Each swap where a min passes left over a max begins a pair (if y overlaps in curr); a max passing left over a min ends a pair. Return [sorted begin pairs, sorted end pairs, swap count], pairs as [min,max].

split: open-access


prompt:
No swaps happen so no pairs ever begin or end.

solve(prev, curr): incremental sweep-and-prune on x. Endpoints [x, 0=min/1=max, id] of prev are sorted, refreshed with curr coordinates and insertion-sorted by (x, kind). Each swap where a min passes left over a max begins a pair (if y overlaps in curr); a max passing left over a min ends a pair. Return [sorted begin pairs, sorted end pairs, swap count], pairs as [min,max].

split: open-access


prompt:
The same pair appears as both (a,b) and (b,a).

solve(prev, curr): incremental sweep-and-prune on x. Endpoints [x, 0=min/1=max, id] of prev are sorted, refreshed with curr coordinates and insertion-sorted by (x, kind). Each swap where a min passes left over a max begins a pair (if y overlaps in curr); a max passing left over a min ends a pair. Return [sorted begin pairs, sorted end pairs, swap count], pairs as [min,max].

split: open-access


prompt:
Boxes rotated into the second quadrant get inverted, too small bounds.

solve(cx, cy, hx, hy, angle, margin): broadphase proxy for a box with centre, half extents and rotation in degrees. Half sizes ex=|cos|hx+|sin|hy, ey=|sin|hx+|cos|hy; fatten by margin on every side. Return [minx, miny, maxx, maxy] rounded to 6.

split: open-access


prompt:
Rotated boxes get square-ish wrong proxies.

solve(cx, cy, hx, hy, angle, margin): broadphase proxy for a box with centre, half extents and rotation in degrees. Half sizes ex=|cos|hx+|sin|hy, ey=|sin|hx+|cos|hy; fatten by margin on every side. Return [minx, miny, maxx, maxy] rounded to 6.

split: open-access


prompt:
Proxy bounds wobble unpredictably with rotation.

solve(cx, cy, hx, hy, angle, margin): broadphase proxy for a box with centre, half extents and rotation in degrees. Half sizes ex=|cos|hx+|sin|hy, ey=|sin|hx+|cos|hy; fatten by margin on every side. Return [minx, miny, maxx, maxy] rounded to 6.

split: open-access


prompt:
Contacts from the left and below begin late.

solve(cx, cy, hx, hy, angle, margin): broadphase proxy for a box with centre, half extents and rotation in degrees. Half sizes ex=|cos|hx+|sin|hy, ey=|sin|hx+|cos|hy; fatten by margin on every side. Return [minx, miny, maxx, maxy] rounded to 6.

split: open-access


prompt:
Proxies are half the size of the shape and contacts are missed.

solve(cx, cy, hx, hy, angle, margin): broadphase proxy for a box with centre, half extents and rotation in degrees. Half sizes ex=|cos|hx+|sin|hy, ey=|sin|hx+|cos|hy; fatten by margin on every side. Return [minx, miny, maxx, maxy] rounded to 6.

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    l1,l2,px,py,elbow=x
    r2=px*px+py*py
    reach=l1+l2
    if r2>=reach*reach: return 'unreachable'
    if r2<(l1-l2)**2-1e-9: return 'unreachable'
    c=(r2-l1*l1-l2*l2)/(2*l1*l2)
    c=max(-1.0,min(1.0,c))
    s=math.sqrt(1-c*c)
    if elbow=='down': s=-s
    q2=math.atan2(s,c)
    q1=math.atan2(py,px)-math.atan2(l2*s,l1+l2*c)
    d1=math.degrees(q1)
    d1=(d1+180.0)%360.0-180.0
    return [round(d1,4),round(math.degrees(q2),4)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['general elbow up', [[2, 1, 2, 1, 'up']], [0.0, 90.0]], ['general elbow down', [[2, 1, 2, 1, 'down']], [53.1301, -90.0]], ['fully extended on x axis', [[2, 1, 3, 0, 'up']], [0.0, 0.0]], ['fully extended diagonal', [[3, 4, 4.2, 5.6, 'up']], [53.1301, 0.0]], ['outside workspace', [[2, 1, 3, 1, 'up']], 'unreachable'], ['between reach and reach squared', [[1, 1, 1.9, 1.2, 'up']], 'unreachable'], ['inside inner hole', [[3, 1, 1, 0, 'up']], 'unreachable']], [['general elbow down', [[2, 1, 2, 1, 'down']], [53.1301, -90.0]], ['fully extended diagonal', [[3, 4, 4.2, 5.6, 'up']], [53.1301, 0.0]], ['between reach and reach squared', [[1, 1, 1.9, 1.2, 'up']], 'unreachable'], ['inside inner hole', [[3, 1, 1, 0, 'up']], 'unreachable'], ['inner boundary folded', [[3, 1, 2, 0, 'down']], [0.0, -180.0]], ['third quadrant target', [[2, 2, -2, -1, 'up']], [150.5529, 112.0243]], ['second quadrant target', [[2, 1.5, -2, 1, 'down']], [-165.5619, -102.0247]]], [['fully extended on x axis', [[2, 1, 3, 0, 'up']], [0.0, 0.0]], ['inner boundary folded', [[3, 1, 2, 0, 'down']], [0.0, -180.0]], ['third quadrant target', [[2, 2, -2, -1, 'up']], [150.5529, 112.0243]], ['second quadrant target', [[2, 1.5, -2, 1, 'down']], [-165.5619, -102.0247]], ['negative y axis', [[1.5, 1, 0, -2, 'up']], [-118.955, 75.5225]], ['behind base elbow down', [[2, 1, -2.5, -0.5, 'down']], [-147.3681, -67.9757]], ['equal links near base', [[1, 1, 0.5, 0.2, 'up']], [-52.5785, 148.7597]]], [['fully extended diagonal', [[3, 4, 4.2, 5.6, 'up']], [53.1301, 0.0]], ['negative y axis', [[1.5, 1, 0, -2, 'up']], [-118.955, 75.5225]], ['behind base elbow down', [[2, 1, -2.5, -0.5, 'down']], [-147.3681, -67.9757]], ['equal links near base', [[1, 1, 0.5, 0.2, 'up']], [-52.5785, 148.7597]], ['long forearm hole', [[1, 3, 0.5, 1, 'down']], 'unreachable'], ['long forearm reachable', [[1, 3, 2.5, 0.5, 'up']], [-95.7981, 125.6853]], ['positive y axis', [[2, 2, 0, 3, 'down']], [131.4096, -82.8192]]], [['fully extended on x axis', [[2, 1, 3, 0, 'up']], [0.0, 0.0]], ['third quadrant target', [[2, 2, -2, -1, 'up']], [150.5529, 112.0243]], ['long forearm reachable', [[1, 3, 2.5, 0.5, 'up']], [-95.7981, 125.6853]], ['positive y axis', [[2, 2, 0, 3, 'down']], [131.4096, -82.8192]], ['wrap past minus 180', [[1, 2, -2.2, -0.3, 'up']], [123.5259, 91.0027]], ['upper left down', [[3, 2, -1, 4, 'down']], [131.2512, -70.5288]], ['near full reach', [[5, 3, 7.9, 0.5, 'down']], [10.0523, -17.1893]]]]
for label, args, expected in fixtures[N-1]:
    check(label, 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)

source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    l1,l2,px,py,elbow=x
    r2=px*px+py*py
    reach=l1+l2
    if r2>reach+1e-9: return 'unreachable'
    if r2<(l1-l2)**2-1e-9: return 'unreachable'
    c=(r2-l1*l1-l2*l2)/(2*l1*l2)
    c=max(-1.0,min(1.0,c))
    s=math.sqrt(1-c*c)
    if elbow=='down': s=-s
    q2=math.atan2(s,c)
    q1=math.atan2(py,px)-math.atan2(l2*s,l1+l2*c)
    d1=math.degrees(q1)
    d1=(d1+180.0)%360.0-180.0
    return [round(d1,4),round(math.degrees(q2),4)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['general elbow up', [[2, 1, 2, 1, 'up']], [0.0, 90.0]], ['general elbow down', [[2, 1, 2, 1, 'down']], [53.1301, -90.0]], ['fully extended on x axis', [[2, 1, 3, 0, 'up']], [0.0, 0.0]], ['fully extended diagonal', [[3, 4, 4.2, 5.6, 'up']], [53.1301, 0.0]], ['outside workspace', [[2, 1, 3, 1, 'up']], 'unreachable'], ['between reach and reach squared', [[1, 1, 1.9, 1.2, 'up']], 'unreachable'], ['inside inner hole', [[3, 1, 1, 0, 'up']], 'unreachable']], [['general elbow down', [[2, 1, 2, 1, 'down']], [53.1301, -90.0]], ['fully extended diagonal', [[3, 4, 4.2, 5.6, 'up']], [53.1301, 0.0]], ['between reach and reach squared', [[1, 1, 1.9, 1.2, 'up']], 'unreachable'], ['inside inner hole', [[3, 1, 1, 0, 'up']], 'unreachable'], ['inner boundary folded', [[3, 1, 2, 0, 'down']], [0.0, -180.0]], ['third quadrant target', [[2, 2, -2, -1, 'up']], [150.5529, 112.0243]], ['second quadrant target', [[2, 1.5, -2, 1, 'down']], [-165.5619, -102.0247]]], [['fully extended on x axis', [[2, 1, 3, 0, 'up']], [0.0, 0.0]], ['inner boundary folded', [[3, 1, 2, 0, 'down']], [0.0, -180.0]], ['third quadrant target', [[2, 2, -2, -1, 'up']], [150.5529, 112.0243]], ['second quadrant target', [[2, 1.5, -2, 1, 'down']], [-165.5619, -102.0247]], ['negative y axis', [[1.5, 1, 0, -2, 'up']], [-118.955, 75.5225]], ['behind base elbow down', [[2, 1, -2.5, -0.5, 'down']], [-147.3681, -67.9757]], ['equal links near base', [[1, 1, 0.5, 0.2, 'up']], [-52.5785, 148.7597]]], [['fully extended diagonal', [[3, 4, 4.2, 5.6, 'up']], [53.1301, 0.0]], ['negative y axis', [[1.5, 1, 0, -2, 'up']], [-118.955, 75.5225]], ['behind base elbow down', [[2, 1, -2.5, -0.5, 'down']], [-147.3681, -67.9757]], ['equal links near base', [[1, 1, 0.5, 0.2, 'up']], [-52.5785, 148.7597]], ['long forearm hole', [[1, 3, 0.5, 1, 'down']], 'unreachable'], ['long forearm reachable', [[1, 3, 2.5, 0.5, 'up']], [-95.7981, 125.6853]], ['positive y axis', [[2, 2, 0, 3, 'down']], [131.4096, -82.8192]]], [['fully extended on x axis', [[2, 1, 3, 0, 'up']], [0.0, 0.0]], ['third quadrant target', [[2, 2, -2, -1, 'up']], [150.5529, 112.0243]], ['long forearm reachable', [[1, 3, 2.5, 0.5, 'up']], [-95.7981, 125.6853]], ['positive y axis', [[2, 2, 0, 3, 'down']], [131.4096, -82.8192]], ['wrap past minus 180', [[1, 2, -2.2, -0.3, 'up']], [123.5259, 91.0027]], ['upper left down', [[3, 2, -1, 4, 'down']], [131.2512, -70.5288]], ['near full reach', [[5, 3, 7.9, 0.5, 'down']], [10.0523, -17.1893]]]]
for label, args, expected in fixtures[N-1]:
    check(label, 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)

prompt:
A target exactly at l1+l2 is reported unreachable although the straight arm touches it.

Input [l1,l2,px,py,elbow] with positive link lengths. Return [q1,q2] in degrees (4 decimals) for a planar two-link arm whose end effector reaches (px,py); elbow "up" gives q2>=0, "down" gives q2<=0; q1 is wrapped to [-180,180). Points outside the annulus |l1-l2|<=r<=l1+l2 (1e-9 slack on r squared) return "unreachable".

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    l1,l2,px,py,elbow=x
    r2=px*px+py*py
    reach=l1+l2
    if r2>reach*reach+1e-9: return 'unreachable'
    c=(r2-l1*l1-l2*l2)/(2*l1*l2)
    c=max(-1.0,min(1.0,c))
    s=math.sqrt(1-c*c)
    if elbow=='down': s=-s
    q2=math.atan2(s,c)
    q1=math.atan2(py,px)-math.atan2(l2*s,l1+l2*c)
    d1=math.degrees(q1)
    d1=(d1+180.0)%360.0-180.0
    return [round(d1,4),round(math.degrees(q2),4)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['general elbow up', [[2, 1, 2, 1, 'up']], [0.0, 90.0]], ['general elbow down', [[2, 1, 2, 1, 'down']], [53.1301, -90.0]], ['fully extended on x axis', [[2, 1, 3, 0, 'up']], [0.0, 0.0]], ['fully extended diagonal', [[3, 4, 4.2, 5.6, 'up']], [53.1301, 0.0]], ['outside workspace', [[2, 1, 3, 1, 'up']], 'unreachable'], ['inside inner hole', [[3, 1, 1, 0, 'up']], 'unreachable'], ['inner boundary folded', [[3, 1, 2, 0, 'down']], [0.0, -180.0]]], [['fully extended diagonal', [[3, 4, 4.2, 5.6, 'up']], [53.1301, 0.0]], ['outside workspace', [[2, 1, 3, 1, 'up']], 'unreachable'], ['between reach and reach squared', [[1, 1, 1.9, 1.2, 'up']], 'unreachable'], ['inside inner hole', [[3, 1, 1, 0, 'up']], 'unreachable'], ['inner boundary folded', [[3, 1, 2, 0, 'down']], [0.0, -180.0]], ['third quadrant target', [[2, 2, -2, -1, 'up']], [150.5529, 112.0243]], ['long forearm hole', [[1, 3, 0.5, 1, 'down']], 'unreachable']], [['inside inner hole', [[3, 1, 1, 0, 'up']], 'unreachable'], ['inner boundary folded', [[3, 1, 2, 0, 'down']], [0.0, -180.0]], ['third quadrant target', [[2, 2, -2, -1, 'up']], [150.5529, 112.0243]], ['second quadrant target', [[2, 1.5, -2, 1, 'down']], [-165.5619, -102.0247]], ['negative y axis', [[1.5, 1, 0, -2, 'up']], [-118.955, 75.5225]], ['behind base elbow down', [[2, 1, -2.5, -0.5, 'down']], [-147.3681, -67.9757]], ['equal links near base', [[1, 1, 0.5, 0.2, 'up']], [-52.5785, 148.7597]]], [['second quadrant target', [[2, 1.5, -2, 1, 'down']], [-165.5619, -102.0247]], ['negative y axis', [[1.5, 1, 0, -2, 'up']], [-118.955, 75.5225]], ['behind base elbow down', [[2, 1, -2.5, -0.5, 'down']], [-147.3681, -67.9757]], ['equal links near base', [[1, 1, 0.5, 0.2, 'up']], [-52.5785, 148.7597]], ['long forearm hole', [[1, 3, 0.5, 1, 'down']], 'unreachable'], ['long forearm reachable', [[1, 3, 2.5, 0.5, 'up']], [-95.7981, 125.6853]], ['positive y axis', [[2, 2, 0, 3, 'down']], [131.4096, -82.8192]]], [['inside inner hole', [[3, 1, 1, 0, 'up']], 'unreachable'], ['inner boundary folded', [[3, 1, 2, 0, 'down']], [0.0, -180.0]], ['long forearm reachable', [[1, 3, 2.5, 0.5, 'up']], [-95.7981, 125.6853]], ['positive y axis', [[2, 2, 0, 3, 'down']], [131.4096, -82.8192]], ['wrap past minus 180', [[1, 2, -2.2, -0.3, 'up']], [123.5259, 91.0027]], ['upper left down', [[3, 2, -1, 4, 'down']], [131.2512, -70.5288]], ['near full reach', [[5, 3, 7.9, 0.5, 'down']], [10.0523, -17.1893]]]]
for label, args, expected in fixtures[N-1]:
    check(label, 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)

source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    l1,l2,px,py,elbow=x
    r2=px*px+py*py
    reach=l1+l2
    if r2>reach*reach+1e-9: return 'unreachable'
    if r2<l1*l1-l2*l2-1e-9: return 'unreachable'
    c=(r2-l1*l1-l2*l2)/(2*l1*l2)
    c=max(-1.0,min(1.0,c))
    s=math.sqrt(1-c*c)
    if elbow=='down': s=-s
    q2=math.atan2(s,c)
    q1=math.atan2(py,px)-math.atan2(l2*s,l1+l2*c)
    d1=math.degrees(q1)
    d1=(d1+180.0)%360.0-180.0
    return [round(d1,4),round(math.degrees(q2),4)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['general elbow up', [[2, 1, 2, 1, 'up']], [0.0, 90.0]], ['general elbow down', [[2, 1, 2, 1, 'down']], [53.1301, -90.0]], ['fully extended on x axis', [[2, 1, 3, 0, 'up']], [0.0, 0.0]], ['fully extended diagonal', [[3, 4, 4.2, 5.6, 'up']], [53.1301, 0.0]], ['outside workspace', [[2, 1, 3, 1, 'up']], 'unreachable'], ['inside inner hole', [[3, 1, 1, 0, 'up']], 'unreachable'], ['inner boundary folded', [[3, 1, 2, 0, 'down']], [0.0, -180.0]]], [['fully extended diagonal', [[3, 4, 4.2, 5.6, 'up']], [53.1301, 0.0]], ['outside workspace', [[2, 1, 3, 1, 'up']], 'unreachable'], ['between reach and reach squared', [[1, 1, 1.9, 1.2, 'up']], 'unreachable'], ['inside inner hole', [[3, 1, 1, 0, 'up']], 'unreachable'], ['inner boundary folded', [[3, 1, 2, 0, 'down']], [0.0, -180.0]], ['third quadrant target', [[2, 2, -2, -1, 'up']], [150.5529, 112.0243]], ['long forearm hole', [[1, 3, 0.5, 1, 'down']], 'unreachable']], [['inside inner hole', [[3, 1, 1, 0, 'up']], 'unreachable'], ['inner boundary folded', [[3, 1, 2, 0, 'down']], [0.0, -180.0]], ['third quadrant target', [[2, 2, -2, -1, 'up']], [150.5529, 112.0243]], ['second quadrant target', [[2, 1.5, -2, 1, 'down']], [-165.5619, -102.0247]], ['negative y axis', [[1.5, 1, 0, -2, 'up']], [-118.955, 75.5225]], ['behind base elbow down', [[2, 1, -2.5, -0.5, 'down']], [-147.3681, -67.9757]], ['equal links near base', [[1, 1, 0.5, 0.2, 'up']], [-52.5785, 148.7597]]], [['second quadrant target', [[2, 1.5, -2, 1, 'down']], [-165.5619, -102.0247]], ['negative y axis', [[1.5, 1, 0, -2, 'up']], [-118.955, 75.5225]], ['behind base elbow down', [[2, 1, -2.5, -0.5, 'down']], [-147.3681, -67.9757]], ['equal links near base', [[1, 1, 0.5, 0.2, 'up']], [-52.5785, 148.7597]], ['long forearm hole', [[1, 3, 0.5, 1, 'down']], 'unreachable'], ['long forearm reachable', [[1, 3, 2.5, 0.5, 'up']], [-95.7981, 125.6853]], ['positive y axis', [[2, 2, 0, 3, 'down']], [131.4096, -82.8192]]], [['inside inner hole', [[3, 1, 1, 0, 'up']], 'unreachable'], ['inner boundary folded', [[3, 1, 2, 0, 'down']], [0.0, -180.0]], ['long forearm reachable', [[1, 3, 2.5, 0.5, 'up']], [-95.7981, 125.6853]], ['positive y axis', [[2, 2, 0, 3, 'down']], [131.4096, -82.8192]], ['wrap past minus 180', [[1, 2, -2.2, -0.3, 'up']], [123.5259, 91.0027]], ['upper left down', [[3, 2, -1, 4, 'down']], [131.2512, -70.5288]], ['near full reach', [[5, 3, 7.9, 0.5, 'down']], [10.0523, -17.1893]]]]
for label, args, expected in fixtures[N-1]:
    check(label, 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)

prompt:
Targets closer than |l1-l2| to the base return a folded pose instead of "unreachable".

Input [l1,l2,px,py,elbow] with positive link lengths. Return [q1,q2] in degrees (4 decimals) for a planar two-link arm whose end effector reaches (px,py); elbow "up" gives q2>=0, "down" gives q2<=0; q1 is wrapped to [-180,180). Points outside the annulus |l1-l2|<=r<=l1+l2 (1e-9 slack on r squared) return "unreachable".

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    l1,l2,px,py,elbow=x
    r2=px*px+py*py
    reach=l1+l2
    if r2>reach*reach+1e-9: return 'unreachable'
    if r2<(l1-l2)**2-1e-9: return 'unreachable'
    c=(l1*l1+l2*l2-r2)/(2*l1*l2)
    c=max(-1.0,min(1.0,c))
    s=math.sqrt(1-c*c)
    if elbow=='down': s=-s
    q2=math.atan2(s,c)
    q1=math.atan2(py,px)-math.atan2(l2*s,l1+l2*c)
    d1=math.degrees(q1)
    d1=(d1+180.0)%360.0-180.0
    return [round(d1,4),round(math.degrees(q2),4)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['general elbow up', [[2, 1, 2, 1, 'up']], [0.0, 90.0]], ['general elbow down', [[2, 1, 2, 1, 'down']], [53.1301, -90.0]], ['fully extended on x axis', [[2, 1, 3, 0, 'up']], [0.0, 0.0]], ['fully extended diagonal', [[3, 4, 4.2, 5.6, 'up']], [53.1301, 0.0]], ['outside workspace', [[2, 1, 3, 1, 'up']], 'unreachable'], ['between reach and reach squared', [[1, 1, 1.9, 1.2, 'up']], 'unreachable'], ['third quadrant target', [[2, 2, -2, -1, 'up']], [150.5529, 112.0243]]], [['fully extended diagonal', [[3, 4, 4.2, 5.6, 'up']], [53.1301, 0.0]], ['outside workspace', [[2, 1, 3, 1, 'up']], 'unreachable'], ['between reach and reach squared', [[1, 1, 1.9, 1.2, 'up']], 'unreachable'], ['inside inner hole', [[3, 1, 1, 0, 'up']], 'unreachable'], ['inner boundary folded', [[3, 1, 2, 0, 'down']], [0.0, -180.0]], ['third quadrant target', [[2, 2, -2, -1, 'up']], [150.5529, 112.0243]], ['second quadrant target', [[2, 1.5, -2, 1, 'down']], [-165.5619, -102.0247]]], [['inside inner hole', [[3, 1, 1, 0, 'up']], 'unreachable'], ['inner boundary folded', [[3, 1, 2, 0, 'down']], [0.0, -180.0]], ['third quadrant target', [[2, 2, -2, -1, 'up']], [150.5529, 112.0243]], ['second quadrant target', [[2, 1.5, -2, 1, 'down']], [-165.5619, -102.0247]], ['negative y axis', [[1.5, 1, 0, -2, 'up']], [-118.955, 75.5225]], ['behind base elbow down', [[2, 1, -2.5, -0.5, 'down']], [-147.3681, -67.9757]], ['equal links near base', [[1, 1, 0.5, 0.2, 'up']], [-52.5785, 148.7597]]], [['third quadrant target', [[2, 2, -2, -1, 'up']], [150.5529, 112.0243]], ['negative y axis', [[1.5, 1, 0, -2, 'up']], [-118.955, 75.5225]], ['behind base elbow down', [[2, 1, -2.5, -0.5, 'down']], [-147.3681, -67.9757]], ['equal links near base', [[1, 1, 0.5, 0.2, 'up']], [-52.5785, 148.7597]], ['long forearm hole', [[1, 3, 0.5, 1, 'down']], 'unreachable'], ['long forearm reachable', [[1, 3, 2.5, 0.5, 'up']], [-95.7981, 125.6853]], ['positive y axis', [[2, 2, 0, 3, 'down']], [131.4096, -82.8192]]], [['second quadrant target', [[2, 1.5, -2, 1, 'down']], [-165.5619, -102.0247]], ['equal links near base', [[1, 1, 0.5, 0.2, 'up']], [-52.5785, 148.7597]], ['long forearm reachable', [[1, 3, 2.5, 0.5, 'up']], [-95.7981, 125.6853]], ['positive y axis', [[2, 2, 0, 3, 'down']], [131.4096, -82.8192]], ['wrap past minus 180', [[1, 2, -2.2, -0.3, 'up']], [123.5259, 91.0027]], ['upper left down', [[3, 2, -1, 4, 'down']], [131.2512, -70.5288]], ['near full reach', [[5, 3, 7.9, 0.5, 'down']], [10.0523, -17.1893]]]]
for label, args, expected in fixtures[N-1]:
    check(label, 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)

source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    l1,l2,px,py,elbow=x
    r2=px*px+py*py
    reach=l1+l2
    if r2>reach*reach+1e-9: return 'unreachable'
    if r2<(l1-l2)**2-1e-9: return 'unreachable'
    c=(r2-l1*l1-l2*l2)/(l1*l2)
    c=max(-1.0,min(1.0,c))
    s=math.sqrt(1-c*c)
    if elbow=='down': s=-s
    q2=math.atan2(s,c)
    q1=math.atan2(py,px)-math.atan2(l2*s,l1+l2*c)
    d1=math.degrees(q1)
    d1=(d1+180.0)%360.0-180.0
    return [round(d1,4),round(math.degrees(q2),4)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['general elbow up', [[2, 1, 2, 1, 'up']], [0.0, 90.0]], ['general elbow down', [[2, 1, 2, 1, 'down']], [53.1301, -90.0]], ['fully extended on x axis', [[2, 1, 3, 0, 'up']], [0.0, 0.0]], ['fully extended diagonal', [[3, 4, 4.2, 5.6, 'up']], [53.1301, 0.0]], ['outside workspace', [[2, 1, 3, 1, 'up']], 'unreachable'], ['between reach and reach squared', [[1, 1, 1.9, 1.2, 'up']], 'unreachable'], ['third quadrant target', [[2, 2, -2, -1, 'up']], [150.5529, 112.0243]]], [['fully extended diagonal', [[3, 4, 4.2, 5.6, 'up']], [53.1301, 0.0]], ['outside workspace', [[2, 1, 3, 1, 'up']], 'unreachable'], ['between reach and reach squared', [[1, 1, 1.9, 1.2, 'up']], 'unreachable'], ['inside inner hole', [[3, 1, 1, 0, 'up']], 'unreachable'], ['inner boundary folded', [[3, 1, 2, 0, 'down']], [0.0, -180.0]], ['third quadrant target', [[2, 2, -2, -1, 'up']], [150.5529, 112.0243]], ['second quadrant target', [[2, 1.5, -2, 1, 'down']], [-165.5619, -102.0247]]], [['inside inner hole', [[3, 1, 1, 0, 'up']], 'unreachable'], ['inner boundary folded', [[3, 1, 2, 0, 'down']], [0.0, -180.0]], ['third quadrant target', [[2, 2, -2, -1, 'up']], [150.5529, 112.0243]], ['second quadrant target', [[2, 1.5, -2, 1, 'down']], [-165.5619, -102.0247]], ['negative y axis', [[1.5, 1, 0, -2, 'up']], [-118.955, 75.5225]], ['behind base elbow down', [[2, 1, -2.5, -0.5, 'down']], [-147.3681, -67.9757]], ['equal links near base', [[1, 1, 0.5, 0.2, 'up']], [-52.5785, 148.7597]]], [['third quadrant target', [[2, 2, -2, -1, 'up']], [150.5529, 112.0243]], ['negative y axis', [[1.5, 1, 0, -2, 'up']], [-118.955, 75.5225]], ['behind base elbow down', [[2, 1, -2.5, -0.5, 'down']], [-147.3681, -67.9757]], ['equal links near base', [[1, 1, 0.5, 0.2, 'up']], [-52.5785, 148.7597]], ['long forearm hole', [[1, 3, 0.5, 1, 'down']], 'unreachable'], ['long forearm reachable', [[1, 3, 2.5, 0.5, 'up']], [-95.7981, 125.6853]], ['positive y axis', [[2, 2, 0, 3, 'down']], [131.4096, -82.8192]]], [['second quadrant target', [[2, 1.5, -2, 1, 'down']], [-165.5619, -102.0247]], ['equal links near base', [[1, 1, 0.5, 0.2, 'up']], [-52.5785, 148.7597]], ['long forearm reachable', [[1, 3, 2.5, 0.5, 'up']], [-95.7981, 125.6853]], ['positive y axis', [[2, 2, 0, 3, 'down']], [131.4096, -82.8192]], ['wrap past minus 180', [[1, 2, -2.2, -0.3, 'up']], [123.5259, 91.0027]], ['upper left down', [[3, 2, -1, 4, 'down']], [131.2512, -70.5288]], ['near full reach', [[5, 3, 7.9, 0.5, 'down']], [10.0523, -17.1893]]]]
for label, args, expected in fixtures[N-1]:
    check(label, 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)

prompt:
Every reachable pose has the elbow bent to the supplementary angle and misses the target.

Input [l1,l2,px,py,elbow] with positive link lengths. Return [q1,q2] in degrees (4 decimals) for a planar two-link arm whose end effector reaches (px,py); elbow "up" gives q2>=0, "down" gives q2<=0; q1 is wrapped to [-180,180). Points outside the annulus |l1-l2|<=r<=l1+l2 (1e-9 slack on r squared) return "unreachable".

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    l1,l2,px,py,elbow=x
    r2=px*px+py*py
    reach=l1+l2
    if r2>reach*reach+1e-9: return 'unreachable'
    if r2<(l1-l2)**2-1e-9: return 'unreachable'
    c=(r2-l1*l1-l2*l2)/(2*l1*l2)
    c=max(-1.0,min(1.0,c))
    s=math.sqrt(1-c*c)
    if elbow=='up': s=-s
    q2=math.atan2(s,c)
    q1=math.atan2(py,px)-math.atan2(l2*s,l1+l2*c)
    d1=math.degrees(q1)
    d1=(d1+180.0)%360.0-180.0
    return [round(d1,4),round(math.degrees(q2),4)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['general elbow up', [[2, 1, 2, 1, 'up']], [0.0, 90.0]], ['general elbow down', [[2, 1, 2, 1, 'down']], [53.1301, -90.0]], ['fully extended on x axis', [[2, 1, 3, 0, 'up']], [0.0, 0.0]], ['fully extended diagonal', [[3, 4, 4.2, 5.6, 'up']], [53.1301, 0.0]], ['outside workspace', [[2, 1, 3, 1, 'up']], 'unreachable'], ['between reach and reach squared', [[1, 1, 1.9, 1.2, 'up']], 'unreachable'], ['inside inner hole', [[3, 1, 1, 0, 'up']], 'unreachable']], [['general elbow down', [[2, 1, 2, 1, 'down']], [53.1301, -90.0]], ['outside workspace', [[2, 1, 3, 1, 'up']], 'unreachable'], ['between reach and reach squared', [[1, 1, 1.9, 1.2, 'up']], 'unreachable'], ['inside inner hole', [[3, 1, 1, 0, 'up']], 'unreachable'], ['inner boundary folded', [[3, 1, 2, 0, 'down']], [0.0, -180.0]], ['third quadrant target', [[2, 2, -2, -1, 'up']], [150.5529, 112.0243]], ['second quadrant target', [[2, 1.5, -2, 1, 'down']], [-165.5619, -102.0247]]], [['inside inner hole', [[3, 1, 1, 0, 'up']], 'unreachable'], ['inner boundary folded', [[3, 1, 2, 0, 'down']], [0.0, -180.0]], ['third quadrant target', [[2, 2, -2, -1, 'up']], [150.5529, 112.0243]], ['second quadrant target', [[2, 1.5, -2, 1, 'down']], [-165.5619, -102.0247]], ['negative y axis', [[1.5, 1, 0, -2, 'up']], [-118.955, 75.5225]], ['behind base elbow down', [[2, 1, -2.5, -0.5, 'down']], [-147.3681, -67.9757]], ['equal links near base', [[1, 1, 0.5, 0.2, 'up']], [-52.5785, 148.7597]]], [['third quadrant target', [[2, 2, -2, -1, 'up']], [150.5529, 112.0243]], ['negative y axis', [[1.5, 1, 0, -2, 'up']], [-118.955, 75.5225]], ['behind base elbow down', [[2, 1, -2.5, -0.5, 'down']], [-147.3681, -67.9757]], ['equal links near base', [[1, 1, 0.5, 0.2, 'up']], [-52.5785, 148.7597]], ['long forearm hole', [[1, 3, 0.5, 1, 'down']], 'unreachable'], ['long forearm reachable', [[1, 3, 2.5, 0.5, 'up']], [-95.7981, 125.6853]], ['positive y axis', [[2, 2, 0, 3, 'down']], [131.4096, -82.8192]]], [['second quadrant target', [[2, 1.5, -2, 1, 'down']], [-165.5619, -102.0247]], ['long forearm hole', [[1, 3, 0.5, 1, 'down']], 'unreachable'], ['long forearm reachable', [[1, 3, 2.5, 0.5, 'up']], [-95.7981, 125.6853]], ['positive y axis', [[2, 2, 0, 3, 'down']], [131.4096, -82.8192]], ['wrap past minus 180', [[1, 2, -2.2, -0.3, 'up']], [123.5259, 91.0027]], ['upper left down', [[3, 2, -1, 4, 'down']], [131.2512, -70.5288]], ['near full reach', [[5, 3, 7.9, 0.5, 'down']], [10.0523, -17.1893]]]]
for label, args, expected in fixtures[N-1]:
    check(label, 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)

source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    l1,l2,px,py,elbow=x
    r2=px*px+py*py
    reach=l1+l2
    if r2>reach*reach+1e-9: return 'unreachable'
    if r2<(l1-l2)**2-1e-9: return 'unreachable'
    c=(r2-l1*l1-l2*l2)/(2*l1*l2)
    c=max(-1.0,min(1.0,c))
    s=math.sqrt(1-c*c)
    if elbow=='down': c=-c
    q2=math.atan2(s,c)
    q1=math.atan2(py,px)-math.atan2(l2*s,l1+l2*c)
    d1=math.degrees(q1)
    d1=(d1+180.0)%360.0-180.0
    return [round(d1,4),round(math.degrees(q2),4)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['general elbow up', [[2, 1, 2, 1, 'up']], [0.0, 90.0]], ['general elbow down', [[2, 1, 2, 1, 'down']], [53.1301, -90.0]], ['fully extended on x axis', [[2, 1, 3, 0, 'up']], [0.0, 0.0]], ['fully extended diagonal', [[3, 4, 4.2, 5.6, 'up']], [53.1301, 0.0]], ['outside workspace', [[2, 1, 3, 1, 'up']], 'unreachable'], ['between reach and reach squared', [[1, 1, 1.9, 1.2, 'up']], 'unreachable'], ['inside inner hole', [[3, 1, 1, 0, 'up']], 'unreachable']], [['general elbow down', [[2, 1, 2, 1, 'down']], [53.1301, -90.0]], ['outside workspace', [[2, 1, 3, 1, 'up']], 'unreachable'], ['between reach and reach squared', [[1, 1, 1.9, 1.2, 'up']], 'unreachable'], ['inside inner hole', [[3, 1, 1, 0, 'up']], 'unreachable'], ['inner boundary folded', [[3, 1, 2, 0, 'down']], [0.0, -180.0]], ['third quadrant target', [[2, 2, -2, -1, 'up']], [150.5529, 112.0243]], ['second quadrant target', [[2, 1.5, -2, 1, 'down']], [-165.5619, -102.0247]]], [['inside inner hole', [[3, 1, 1, 0, 'up']], 'unreachable'], ['inner boundary folded', [[3, 1, 2, 0, 'down']], [0.0, -180.0]], ['third quadrant target', [[2, 2, -2, -1, 'up']], [150.5529, 112.0243]], ['second quadrant target', [[2, 1.5, -2, 1, 'down']], [-165.5619, -102.0247]], ['negative y axis', [[1.5, 1, 0, -2, 'up']], [-118.955, 75.5225]], ['behind base elbow down', [[2, 1, -2.5, -0.5, 'down']], [-147.3681, -67.9757]], ['equal links near base', [[1, 1, 0.5, 0.2, 'up']], [-52.5785, 148.7597]]], [['third quadrant target', [[2, 2, -2, -1, 'up']], [150.5529, 112.0243]], ['negative y axis', [[1.5, 1, 0, -2, 'up']], [-118.955, 75.5225]], ['behind base elbow down', [[2, 1, -2.5, -0.5, 'down']], [-147.3681, -67.9757]], ['equal links near base', [[1, 1, 0.5, 0.2, 'up']], [-52.5785, 148.7597]], ['long forearm hole', [[1, 3, 0.5, 1, 'down']], 'unreachable'], ['long forearm reachable', [[1, 3, 2.5, 0.5, 'up']], [-95.7981, 125.6853]], ['positive y axis', [[2, 2, 0, 3, 'down']], [131.4096, -82.8192]]], [['second quadrant target', [[2, 1.5, -2, 1, 'down']], [-165.5619, -102.0247]], ['long forearm hole', [[1, 3, 0.5, 1, 'down']], 'unreachable'], ['long forearm reachable', [[1, 3, 2.5, 0.5, 'up']], [-95.7981, 125.6853]], ['positive y axis', [[2, 2, 0, 3, 'down']], [131.4096, -82.8192]], ['wrap past minus 180', [[1, 2, -2.2, -0.3, 'up']], [123.5259, 91.0027]], ['upper left down', [[3, 2, -1, 4, 'down']], [131.2512, -70.5288]], ['near full reach', [[5, 3, 7.9, 0.5, 'down']], [10.0523, -17.1893]]]]
for label, args, expected in fixtures[N-1]:
    check(label, 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)

prompt:
Asking for elbow up yields a negative q2 and elbow down a positive one.

Input [l1,l2,px,py,elbow] with positive link lengths. Return [q1,q2] in degrees (4 decimals) for a planar two-link arm whose end effector reaches (px,py); elbow "up" gives q2>=0, "down" gives q2<=0; q1 is wrapped to [-180,180). Points outside the annulus |l1-l2|<=r<=l1+l2 (1e-9 slack on r squared) return "unreachable".

split: open-access