SAH normalizes by the parent perimeter at half scale · case 01

"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(prims):
    n = len(prims)
    cent = [((p[0] + p[2]) / 2, (p[1] + p[3]) / 2) for p in prims]
    ex = max(c[0] for c in cent) - min(c[0] for c in cent)
    ey = max(c[1] for c in cent) - min(c[1] for c in cent)
    axis = 0 if ex >= ey else 1
    order = sorted(range(n), key=lambda i: (cent[i][axis], i))
    def box(ids):
        return [min(prims[i][0] for i in ids), min(prims[i][1] for i in ids), max(prims[i][2] for i in ids), max(prims[i][3] for i in ids)]
    def perim(b):
        return 2 * ((b[2] - b[0]) + (b[3] - b[1]))
    pa = 2 * (ex + ey)
    best_k, best = 0, float(n)
    for k in range(1, n):
        cost = 1 + (perim(box(order[:k])) * k + perim(box(order[k:])) * (n - k)) / pa
        if cost < best:
            best_k, best = k, cost
    return [best_k, axis, round(best, 6), sorted(order[:best_k])]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[[[[[6, 10, 11, 14], [2, 7, 4, 13], [8, 10, 11, 13], [1, 9, 5, 16]]], [2, 0, 3.315789, [1, 3]]], [[[[8, 1, 13, 2], [9, 2, 16, 9]]], [0, 1, 2.0, []]], [[[[5, 10, 9, 17], [7, 1, 11, 5], [1, 8, 8, 15]]], [1, 1, 2.615385, [1]]], [[[[6, 5, 10, 11], [5, 2, 11, 4]]], [0, 1, 2.0, []]], [[[[2, 3, 3, 7], [4, 8, 10, 11]]], [1, 0, 1.875, [0]]], [[[[3, 2, 7, 9], [6, 0, 8, 5], [4, 1, 8, 8], [9, 3, 11, 7], [1, 1, 3, 2], [0, 4, 6, 11]]], [3, 0, 5.363636, [0, 4, 5]]], [[[[10, 6, 16, 8], [1, 10, 4, 16], [0, 8, 6, 13], [9, 0, 15, 1], [3, 10, 9, 16], [1, 9, 8, 15]]], [2, 1, 4.0625, [0, 3]]], [[[[9, 8, 14, 10], [5, 6, 9, 8]]], [0, 0, 2.0, []]]], [[[[[9, 3, 13, 6], [4, 9, 6, 15]]], [1, 1, 1.714286, [0]]], [[[[10, 3, 12, 9], [6, 9, 10, 16], [4, 3, 9, 10], [6, 4, 10, 8], [8, 5, 11, 7]]], [4, 1, 4.380952, [0, 2, 3, 4]]], [[[[3, 2, 8, 6], [5, 10, 10, 17], [2, 1, 9, 5], [6, 5, 10, 10], [1, 9, 4, 14], [10, 10, 15, 12], [3, 9, 7, 12]]], [3, 1, 5.633333, [0, 2, 3]]], [[[[9, 0, 12, 5], [8, 3, 14, 7]]], [0, 1, 2.0, []]], [[[[5, 1, 12, 7], [10, 7, 17, 11], [3, 8, 6, 10], [8, 2, 14, 5], [2, 0, 3, 4], [9, 5, 14, 7], [2, 4, 7, 10]]], [3, 0, 6.115385, [2, 4, 6]]], [[[[9, 3, 16, 10], [5, 8, 11, 13]]], [0, 0, 2.0, []]], [[[[6, 2, 10, 4], [4, 1, 11, 6], [3, 3, 4, 4]]], [0, 0, 3.0, []]], [[[[3, 4, 8, 7], [6, 9, 8, 10], [2, 6, 4, 7], [7, 0, 13, 1], [7, 4, 9, 11], [6, 2, 8, 7], [6, 9, 9, 16]]], [4, 1, 5.333333, [0, 2, 3, 5]]]], [[[[[3, 4, 7, 5], [1, 2, 3, 4]]], [0, 0, 2.0, []]], [[[[1, 9, 7, 12], [9, 4, 14, 6], [7, 7, 11, 9], [9, 8, 16, 10], [2, 3, 6, 5], [7, 10, 12, 11]]], [2, 0, 4.916667, [0, 4]]], [[[[8, 5, 15, 8], [2, 3, 7, 7]]], [0, 0, 2.0, []]], [[[[9, 7, 11, 11], [4, 6, 6, 8], [7, 4, 12, 5]]], [1, 0, 2.866667, [1]]], [[[[9, 0, 16, 2], [2, 1, 5, 2], [6, 10, 9, 16], [8, 2, 13, 4], [3, 6, 7, 12], [2, 5, 8, 8]]], [3, 1, 4.6, [0, 1, 3]]], [[[[1, 3, 5, 10], [3, 0, 7, 7], [10, 4, 17, 6], [2, 2, 6, 9]]], [3, 0, 3.192308, [0, 1, 3]]], [[[[4, 6, 10, 12], [7, 8, 12, 14]]], [0, 0, 2.0, []]], [[[[1, 3, 2, 7], [0, 3, 2, 10], [2, 8, 8, 9], [0, 4, 6, 5], [4, 8, 7, 14], [7, 10, 9, 11]]], [3, 0, 4.9, [0, 1, 3]]]], [[[[[3, 8, 4, 15], [8, 6, 14, 12], [6, 0, 9, 3], [1, 9, 2, 12], [9, 4, 12, 9]]], [3, 1, 3.857143, [1, 2, 4]]], [[[[4, 4, 7, 11], [0, 5, 2, 9]]], [0, 0, 2.0, []]], [[[[0, 1, 3, 2], [7, 6, 9, 8], [3, 7, 7, 9], [5, 0, 7, 1], [7, 0, 13, 7], [7, 2, 12, 8]]], [3, 0, 5.090909, [0, 2, 3]]], [[[[7, 6, 11, 11], [7, 8, 12, 9], [10, 3, 17, 8], [0, 6, 3, 10]]], [1, 0, 3.44, [3]]], [[[[4, 6, 8, 7], [5, 5, 12, 11], [7, 2, 14, 7]]], [0, 0, 3.0, []]], [[[[2, 1, 8, 2], [5, 5, 12, 7]]], [0, 1, 2.0, []]], [[[[10, 5, 13, 7], [9, 3, 12, 10], [10, 0, 14, 5], [6, 0, 10, 2], [6, 4, 8, 5], [1, 4, 4, 5]]], [3, 0, 4.782609, [3, 4, 5]]], [[[[1, 10, 4, 15], [7, 0, 11, 6], [0, 3, 4, 8], [1, 10, 2, 14], [10, 3, 13, 7]]], [3, 0, 3.642857, [0, 2, 3]]]], [[[[[4, 8, 9, 10], [5, 6, 11, 9], [1, 10, 3, 12], [10, 10, 12, 11], [0, 6, 3, 8], [1, 9, 5, 15], [9, 6, 14, 11]]], [3, 0, 5.434783, [2, 4, 5]]], [[[[0, 0, 4, 5], [7, 8, 12, 12], [7, 0, 11, 3], [10, 8, 12, 12]]], [2, 0, 3.083333, [0, 2]]], [[[[8, 4, 11, 8], [8, 1, 14, 2]]], [0, 1, 2.0, []]], [[[[7, 1, 13, 7], [5, 0, 8, 5]]], [0, 0, 2.0, []]], [[[[0, 2, 7, 5], [8, 0, 9, 5], [9, 7, 12, 8]]], [2, 0, 2.6, [0, 1]]], [[[[5, 0, 10, 3], [1, 1, 6, 7], [6, 4, 12, 10]]], [0, 0, 3.0, []]], [[[[8, 0, 15, 2], [7, 10, 14, 11], [1, 8, 3, 15], [4, 1, 10, 5]]], [2, 1, 3.482759, [0, 3]]], [[[[9, 10, 16, 16], [0, 5, 2, 12], [9, 1, 10, 5], [1, 8, 2, 11]]], [2, 0, 3.0, [1, 3]]]]]
for i, (args, expected) in enumerate(fixtures[N-1]):
    check("case %d" % i, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

SHA-256 / 03a1f15852a544b2268febcee82021a45575dad985795b078b0e393c745993e3

"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(prims):
    n = len(prims)
    cent = [((p[0] + p[2]) / 2, (p[1] + p[3]) / 2) for p in prims]
    ex = max(c[0] for c in cent) - min(c[0] for c in cent)
    ey = max(c[1] for c in cent) - min(c[1] for c in cent)
    axis = 0 if ex >= ey else 1
    order = sorted(range(n), key=lambda i: (cent[i][axis], i))
    def box(ids):
        return [min(prims[i][0] for i in ids), min(prims[i][1] for i in ids), max(prims[i][2] for i in ids), max(prims[i][3] for i in ids)]
    def perim(b):
        return 2 * ((b[2] - b[0]) + (b[3] - b[1]))
    pa = perim(box(order)) / 2
    best_k, best = 0, float(n)
    for k in range(1, n):
        cost = 1 + (perim(box(order[:k])) * k + perim(box(order[k:])) * (n - k)) / pa
        if cost < best:
            best_k, best = k, cost
    return [best_k, axis, round(best, 6), sorted(order[:best_k])]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[[[[[6, 10, 11, 14], [2, 7, 4, 13], [8, 10, 11, 13], [1, 9, 5, 16]]], [2, 0, 3.315789, [1, 3]]], [[[[8, 1, 13, 2], [9, 2, 16, 9]]], [0, 1, 2.0, []]], [[[[5, 10, 9, 17], [7, 1, 11, 5], [1, 8, 8, 15]]], [1, 1, 2.615385, [1]]], [[[[6, 5, 10, 11], [5, 2, 11, 4]]], [0, 1, 2.0, []]], [[[[2, 3, 3, 7], [4, 8, 10, 11]]], [1, 0, 1.875, [0]]], [[[[3, 2, 7, 9], [6, 0, 8, 5], [4, 1, 8, 8], [9, 3, 11, 7], [1, 1, 3, 2], [0, 4, 6, 11]]], [3, 0, 5.363636, [0, 4, 5]]], [[[[10, 6, 16, 8], [1, 10, 4, 16], [0, 8, 6, 13], [9, 0, 15, 1], [3, 10, 9, 16], [1, 9, 8, 15]]], [2, 1, 4.0625, [0, 3]]], [[[[9, 8, 14, 10], [5, 6, 9, 8]]], [0, 0, 2.0, []]]], [[[[[9, 3, 13, 6], [4, 9, 6, 15]]], [1, 1, 1.714286, [0]]], [[[[10, 3, 12, 9], [6, 9, 10, 16], [4, 3, 9, 10], [6, 4, 10, 8], [8, 5, 11, 7]]], [4, 1, 4.380952, [0, 2, 3, 4]]], [[[[3, 2, 8, 6], [5, 10, 10, 17], [2, 1, 9, 5], [6, 5, 10, 10], [1, 9, 4, 14], [10, 10, 15, 12], [3, 9, 7, 12]]], [3, 1, 5.633333, [0, 2, 3]]], [[[[9, 0, 12, 5], [8, 3, 14, 7]]], [0, 1, 2.0, []]], [[[[5, 1, 12, 7], [10, 7, 17, 11], [3, 8, 6, 10], [8, 2, 14, 5], [2, 0, 3, 4], [9, 5, 14, 7], [2, 4, 7, 10]]], [3, 0, 6.115385, [2, 4, 6]]], [[[[9, 3, 16, 10], [5, 8, 11, 13]]], [0, 0, 2.0, []]], [[[[6, 2, 10, 4], [4, 1, 11, 6], [3, 3, 4, 4]]], [0, 0, 3.0, []]], [[[[3, 4, 8, 7], [6, 9, 8, 10], [2, 6, 4, 7], [7, 0, 13, 1], [7, 4, 9, 11], [6, 2, 8, 7], [6, 9, 9, 16]]], [4, 1, 5.333333, [0, 2, 3, 5]]]], [[[[[3, 4, 7, 5], [1, 2, 3, 4]]], [0, 0, 2.0, []]], [[[[1, 9, 7, 12], [9, 4, 14, 6], [7, 7, 11, 9], [9, 8, 16, 10], [2, 3, 6, 5], [7, 10, 12, 11]]], [2, 0, 4.916667, [0, 4]]], [[[[8, 5, 15, 8], [2, 3, 7, 7]]], [0, 0, 2.0, []]], [[[[9, 7, 11, 11], [4, 6, 6, 8], [7, 4, 12, 5]]], [1, 0, 2.866667, [1]]], [[[[9, 0, 16, 2], [2, 1, 5, 2], [6, 10, 9, 16], [8, 2, 13, 4], [3, 6, 7, 12], [2, 5, 8, 8]]], [3, 1, 4.6, [0, 1, 3]]], [[[[1, 3, 5, 10], [3, 0, 7, 7], [10, 4, 17, 6], [2, 2, 6, 9]]], [3, 0, 3.192308, [0, 1, 3]]], [[[[4, 6, 10, 12], [7, 8, 12, 14]]], [0, 0, 2.0, []]], [[[[1, 3, 2, 7], [0, 3, 2, 10], [2, 8, 8, 9], [0, 4, 6, 5], [4, 8, 7, 14], [7, 10, 9, 11]]], [3, 0, 4.9, [0, 1, 3]]]], [[[[[3, 8, 4, 15], [8, 6, 14, 12], [6, 0, 9, 3], [1, 9, 2, 12], [9, 4, 12, 9]]], [3, 1, 3.857143, [1, 2, 4]]], [[[[4, 4, 7, 11], [0, 5, 2, 9]]], [0, 0, 2.0, []]], [[[[0, 1, 3, 2], [7, 6, 9, 8], [3, 7, 7, 9], [5, 0, 7, 1], [7, 0, 13, 7], [7, 2, 12, 8]]], [3, 0, 5.090909, [0, 2, 3]]], [[[[7, 6, 11, 11], [7, 8, 12, 9], [10, 3, 17, 8], [0, 6, 3, 10]]], [1, 0, 3.44, [3]]], [[[[4, 6, 8, 7], [5, 5, 12, 11], [7, 2, 14, 7]]], [0, 0, 3.0, []]], [[[[2, 1, 8, 2], [5, 5, 12, 7]]], [0, 1, 2.0, []]], [[[[10, 5, 13, 7], [9, 3, 12, 10], [10, 0, 14, 5], [6, 0, 10, 2], [6, 4, 8, 5], [1, 4, 4, 5]]], [3, 0, 4.782609, [3, 4, 5]]], [[[[1, 10, 4, 15], [7, 0, 11, 6], [0, 3, 4, 8], [1, 10, 2, 14], [10, 3, 13, 7]]], [3, 0, 3.642857, [0, 2, 3]]]], [[[[[4, 8, 9, 10], [5, 6, 11, 9], [1, 10, 3, 12], [10, 10, 12, 11], [0, 6, 3, 8], [1, 9, 5, 15], [9, 6, 14, 11]]], [3, 0, 5.434783, [2, 4, 5]]], [[[[0, 0, 4, 5], [7, 8, 12, 12], [7, 0, 11, 3], [10, 8, 12, 12]]], [2, 0, 3.083333, [0, 2]]], [[[[8, 4, 11, 8], [8, 1, 14, 2]]], [0, 1, 2.0, []]], [[[[7, 1, 13, 7], [5, 0, 8, 5]]], [0, 0, 2.0, []]], [[[[0, 2, 7, 5], [8, 0, 9, 5], [9, 7, 12, 8]]], [2, 0, 2.6, [0, 1]]], [[[[5, 0, 10, 3], [1, 1, 6, 7], [6, 4, 12, 10]]], [0, 0, 3.0, []]], [[[[8, 0, 15, 2], [7, 10, 14, 11], [1, 8, 3, 15], [4, 1, 10, 5]]], [2, 1, 3.482759, [0, 3]]], [[[[9, 10, 16, 16], [0, 5, 2, 12], [9, 1, 10, 5], [1, 8, 2, 11]]], [2, 0, 3.0, [1, 3]]]]]
for i, (args, expected) in enumerate(fixtures[N-1]):
    check("case %d" % i, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

SHA-256 / 08d6dc82d75844450de6ff612a43727ea78e3c3a8bdfbe4a6c9d9e8f887a6712