FA-70796 / GIS polygon topology / Open access

Dissolve grouping by attribute and shared edges: group ordering · case 01

Groups are reported in root order rather than by their first polygon.

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

ROOT CAUSE

Groups are sorted by their union-find root index, which is an arbitrary member rather than the first one.

THE FAILURE

Groups are sorted by their union-find root index, which is an arbitrary member rather than the first one.

Unsuccessful approach: Sorting by group size does not order groups by their first index.

Case contract

Input [polygons, keys]: closed rings on a noded coverage and one attribute value per polygon. Polygons are merged when their keys are exactly equal (type-sensitive, None never merges) and they share at least one edge, transitively. Return the groups as ascending index lists, the list of groups sorted by first index.

Why this case matters

Dissolving parcels into zoning or ownership blocks is a core GIS operation; grouping errors merge blocks that only touch at a corner or split contiguous ones.

1 / The failure

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    polys, keys = x
    def edges(r):
        return {tuple(sorted([tuple(a), tuple(b)])) for a, b in zip(r, r[1:]) if a != b}
    E = [edges(p) for p in polys]
    parent = list(range(len(polys)))
    def find(a):
        while parent[a] != a:
            a = parent[a]
        return a
    for i in range(len(polys)):
        for j in range(i + 1, len(polys)):
            if keys[i] is not None and keys[i] == keys[j] and E[i] & E[j]:
                parent[find(i)] = find(j)
    groups = {}
    for i in range(len(polys)):
        groups.setdefault(find(i), []).append(i)
    return sorted(groups.values(), key=lambda g: find(g[0]))
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('control #0', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], ['a', 'a', 'b', 'a', 'b', 'b', 'c', 'c', 'c']], [[0, 1, 3], [2, 4, 5], [6, 7, 8]]), ('regression #1', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], ['a', 'b', 'a', 'b', 'a', 'b', 'a', 'b', 'a']], [[0], [1], [2], [3], [4], [5], [6], [7], [8]]), ('regression #2', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], ['a', 'a', 'a', 'b', 'b', 'a', 'a', 'a', 'a']], [[0, 1, 2, 5, 6, 7, 8], [3, 4]]), ('regression #3', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], [None, None, 'x', 'x', None, 'x', None, None, 'x']], [[0], [1], [2, 5, 8], [3], [4], [6], [7]]), ('regression #4', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], [1, '1', 1, 2, 2, '2', 1, 1, 1]], [[0], [1], [2], [3, 4], [5], [6, 7, 8]]), ('regression #5', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], ['', '', 'k', 'k', '', 'k', 'k', 'k', 'k']], [[0, 1, 4], [2, 3, 5, 6, 7, 8]]), ('control #6', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], ['z', 'z', 'z', 'z', 'z', 'z', 'z', 'z', 'z']], [[0, 1, 2, 3, 4, 5, 6, 7, 8]]), ('control #7', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i']], [[0], [1], [2], [3], [4], [5], [6], [7], [8]])], [('regression #3', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], [None, None, 'x', 'x', None, 'x', None, None, 'x']], [[0], [1], [2, 5, 8], [3], [4], [6], [7]]), ('regression #4', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], [1, '1', 1, 2, 2, '2', 1, 1, 1]], [[0], [1], [2], [3, 4], [5], [6, 7, 8]]), ('regression #5', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], ['', '', 'k', 'k', '', 'k', 'k', 'k', 'k']], [[0, 1, 4], [2, 3, 5, 6, 7, 8]]), ('control #6', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], ['z', 'z', 'z', 'z', 'z', 'z', 'z', 'z', 'z']], [[0, 1, 2, 3, 4, 5, 6, 7, 8]]), ('control #7', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i']], [[0], [1], [2], [3], [4], [5], [6], [7], [8]]), ('regression #8', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], ['a', 'b', 'c', 'a', 'b', 'c', 'a', 'b', 'c']], [[0, 3, 6], [1, 4, 7], [2, 5, 8]]), ('regression #9', [[[[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]]], ['q', 'q', 'q', 'r']], [[0, 1, 2], [3]]), ('regression #10', [[[[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]]], ['m', 'm', 'm', 'm']], [[0, 1, 2], [3]])], [('regression #4', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], [1, '1', 1, 2, 2, '2', 1, 1, 1]], [[0], [1], [2], [3, 4], [5], [6, 7, 8]]), ('control #7', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i']], [[0], [1], [2], [3], [4], [5], [6], [7], [8]]), ('regression #8', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], ['a', 'b', 'c', 'a', 'b', 'c', 'a', 'b', 'c']], [[0, 3, 6], [1, 4, 7], [2, 5, 8]]), ('regression #9', [[[[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]]], ['q', 'q', 'q', 'r']], [[0, 1, 2], [3]]), ('regression #10', [[[[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]]], ['m', 'm', 'm', 'm']], [[0, 1, 2], [3]]), ('regression #11', [[[[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]]], ['s', 's', 't', 's', 's']], [[0, 1], [2], [3, 4]]), ('boundary #12', [[], []], []), ('regression #13', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], ['p', 'q', 'q', 'p', 'q', 'p', 'p', 'p', 'p']], [[0, 3, 5, 6, 7, 8], [1, 2, 4]])], [('control #0', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], ['a', 'a', 'b', 'a', 'b', 'b', 'c', 'c', 'c']], [[0, 1, 3], [2, 4, 5], [6, 7, 8]]), ('regression #1', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], ['a', 'b', 'a', 'b', 'a', 'b', 'a', 'b', 'a']], [[0], [1], [2], [3], [4], [5], [6], [7], [8]]), ('regression #9', [[[[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]]], ['q', 'q', 'q', 'r']], [[0, 1, 2], [3]]), ('regression #10', [[[[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]]], ['m', 'm', 'm', 'm']], [[0, 1, 2], [3]]), ('regression #11', [[[[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]]], ['s', 's', 't', 's', 's']], [[0, 1], [2], [3, 4]]), ('boundary #12', [[], []], []), ('regression #13', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], ['p', 'q', 'q', 'p', 'q', 'p', 'p', 'p', 'p']], [[0, 3, 5, 6, 7, 8], [1, 2, 4]]), ('regression #14', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]]], ['w', 'w', 'w', 'w']], [[0, 1, 3], [2]])], [('control #0', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], ['a', 'a', 'b', 'a', 'b', 'b', 'c', 'c', 'c']], [[0, 1, 3], [2, 4, 5], [6, 7, 8]]), ('regression #1', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], ['a', 'b', 'a', 'b', 'a', 'b', 'a', 'b', 'a']], [[0], [1], [2], [3], [4], [5], [6], [7], [8]]), ('regression #2', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], ['a', 'a', 'a', 'b', 'b', 'a', 'a', 'a', 'a']], [[0, 1, 2, 5, 6, 7, 8], [3, 4]]), ('regression #3', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], [None, None, 'x', 'x', None, 'x', None, None, 'x']], [[0], [1], [2, 5, 8], [3], [4], [6], [7]]), ('regression #4', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], [1, '1', 1, 2, 2, '2', 1, 1, 1]], [[0], [1], [2], [3, 4], [5], [6, 7, 8]]), ('regression #5', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], ['', '', 'k', 'k', '', 'k', 'k', 'k', 'k']], [[0, 1, 4], [2, 3, 5, 6, 7, 8]]), ('regression #11', [[[[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]]], ['s', 's', 't', 's', 's']], [[0, 1], [2], [3, 4]]), ('regression #14', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]]], ['w', 'w', 'w', 'w']], [[0, 1, 3], [2]])]]
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)

Boundary fixture	Actual	Expected	Outcome
control #0	`[[0, 1, 3], [2, 4, 5], [6, 7, 8]]`	`[[0, 1, 3], [2, 4, 5], [6, 7, 8]]`	Passed
regression #1	`[[0], [1], [2], [3], [4], [5], [6], [7], [8]]`	`[[0], [1], [2], [3], [4], [5], [6], [7], [8]]`	Passed
regression #2	`[[3, 4], [0, 1, 2, 5, 6, 7, 8]]`	`[[0, 1, 2, 5, 6, 7, 8], [3, 4]]`	Failed
regression #3	`[[0], [1], [3], [4], [6], [7], [2, 5, 8]]`	`[[0], [1], [2, 5, 8], [3], [4], [6], [7]]`	Failed
regression #4	`[[0], [1], [2], [3, 4], [5], [6, 7, 8]]`	`[[0], [1], [2], [3, 4], [5], [6, 7, 8]]`	Passed
regression #5	`[[0, 1, 4], [2, 3, 5, 6, 7, 8]]`	`[[0, 1, 4], [2, 3, 5, 6, 7, 8]]`	Passed
control #6	`[[0, 1, 2, 3, 4, 5, 6, 7, 8]]`	`[[0, 1, 2, 3, 4, 5, 6, 7, 8]]`	Passed
control #7	`[[0], [1], [2], [3], [4], [5], [6], [7], [8]]`	`[[0], [1], [2], [3], [4], [5], [6], [7], [8]]`	Passed

SHA-256 / 8056a5141e579c1d92e285389c1a75250d3fd9dc8f0570bfc0bb3dba34a0efe5

2 / The unsuccessful fix

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
    polys, keys = x
    def edges(r):
        return {tuple(sorted([tuple(a), tuple(b)])) for a, b in zip(r, r[1:]) if a != b}
    E = [edges(p) for p in polys]
    parent = list(range(len(polys)))
    def find(a):
        while parent[a] != a:
            a = parent[a]
        return a
    for i in range(len(polys)):
        for j in range(i + 1, len(polys)):
            if keys[i] is not None and keys[i] == keys[j] and E[i] & E[j]:
                parent[find(i)] = find(j)
    groups = {}
    for i in range(len(polys)):
        groups.setdefault(find(i), []).append(i)
    return sorted(groups.values(), key=len)
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('control #0', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], ['a', 'a', 'b', 'a', 'b', 'b', 'c', 'c', 'c']], [[0, 1, 3], [2, 4, 5], [6, 7, 8]]), ('regression #1', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], ['a', 'b', 'a', 'b', 'a', 'b', 'a', 'b', 'a']], [[0], [1], [2], [3], [4], [5], [6], [7], [8]]), ('regression #2', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], ['a', 'a', 'a', 'b', 'b', 'a', 'a', 'a', 'a']], [[0, 1, 2, 5, 6, 7, 8], [3, 4]]), ('regression #3', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], [None, None, 'x', 'x', None, 'x', None, None, 'x']], [[0], [1], [2, 5, 8], [3], [4], [6], [7]]), ('regression #4', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], [1, '1', 1, 2, 2, '2', 1, 1, 1]], [[0], [1], [2], [3, 4], [5], [6, 7, 8]]), ('regression #5', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], ['', '', 'k', 'k', '', 'k', 'k', 'k', 'k']], [[0, 1, 4], [2, 3, 5, 6, 7, 8]]), ('control #6', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], ['z', 'z', 'z', 'z', 'z', 'z', 'z', 'z', 'z']], [[0, 1, 2, 3, 4, 5, 6, 7, 8]]), ('control #7', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i']], [[0], [1], [2], [3], [4], [5], [6], [7], [8]])], [('regression #3', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], [None, None, 'x', 'x', None, 'x', None, None, 'x']], [[0], [1], [2, 5, 8], [3], [4], [6], [7]]), ('regression #4', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], [1, '1', 1, 2, 2, '2', 1, 1, 1]], [[0], [1], [2], [3, 4], [5], [6, 7, 8]]), ('regression #5', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], ['', '', 'k', 'k', '', 'k', 'k', 'k', 'k']], [[0, 1, 4], [2, 3, 5, 6, 7, 8]]), ('control #6', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], ['z', 'z', 'z', 'z', 'z', 'z', 'z', 'z', 'z']], [[0, 1, 2, 3, 4, 5, 6, 7, 8]]), ('control #7', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i']], [[0], [1], [2], [3], [4], [5], [6], [7], [8]]), ('regression #8', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], ['a', 'b', 'c', 'a', 'b', 'c', 'a', 'b', 'c']], [[0, 3, 6], [1, 4, 7], [2, 5, 8]]), ('regression #9', [[[[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]]], ['q', 'q', 'q', 'r']], [[0, 1, 2], [3]]), ('regression #10', [[[[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]]], ['m', 'm', 'm', 'm']], [[0, 1, 2], [3]])], [('regression #4', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], [1, '1', 1, 2, 2, '2', 1, 1, 1]], [[0], [1], [2], [3, 4], [5], [6, 7, 8]]), ('control #7', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i']], [[0], [1], [2], [3], [4], [5], [6], [7], [8]]), ('regression #8', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], ['a', 'b', 'c', 'a', 'b', 'c', 'a', 'b', 'c']], [[0, 3, 6], [1, 4, 7], [2, 5, 8]]), ('regression #9', [[[[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]]], ['q', 'q', 'q', 'r']], [[0, 1, 2], [3]]), ('regression #10', [[[[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]]], ['m', 'm', 'm', 'm']], [[0, 1, 2], [3]]), ('regression #11', [[[[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]]], ['s', 's', 't', 's', 's']], [[0, 1], [2], [3, 4]]), ('boundary #12', [[], []], []), ('regression #13', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], ['p', 'q', 'q', 'p', 'q', 'p', 'p', 'p', 'p']], [[0, 3, 5, 6, 7, 8], [1, 2, 4]])], [('control #0', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], ['a', 'a', 'b', 'a', 'b', 'b', 'c', 'c', 'c']], [[0, 1, 3], [2, 4, 5], [6, 7, 8]]), ('regression #1', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], ['a', 'b', 'a', 'b', 'a', 'b', 'a', 'b', 'a']], [[0], [1], [2], [3], [4], [5], [6], [7], [8]]), ('regression #9', [[[[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]]], ['q', 'q', 'q', 'r']], [[0, 1, 2], [3]]), ('regression #10', [[[[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]]], ['m', 'm', 'm', 'm']], [[0, 1, 2], [3]]), ('regression #11', [[[[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]]], ['s', 's', 't', 's', 's']], [[0, 1], [2], [3, 4]]), ('boundary #12', [[], []], []), ('regression #13', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], ['p', 'q', 'q', 'p', 'q', 'p', 'p', 'p', 'p']], [[0, 3, 5, 6, 7, 8], [1, 2, 4]]), ('regression #14', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]]], ['w', 'w', 'w', 'w']], [[0, 1, 3], [2]])], [('control #0', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], ['a', 'a', 'b', 'a', 'b', 'b', 'c', 'c', 'c']], [[0, 1, 3], [2, 4, 5], [6, 7, 8]]), ('regression #1', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], ['a', 'b', 'a', 'b', 'a', 'b', 'a', 'b', 'a']], [[0], [1], [2], [3], [4], [5], [6], [7], [8]]), ('regression #2', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], ['a', 'a', 'a', 'b', 'b', 'a', 'a', 'a', 'a']], [[0, 1, 2, 5, 6, 7, 8], [3, 4]]), ('regression #3', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], [None, None, 'x', 'x', None, 'x', None, None, 'x']], [[0], [1], [2, 5, 8], [3], [4], [6], [7]]), ('regression #4', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], [1, '1', 1, 2, 2, '2', 1, 1, 1]], [[0], [1], [2], [3, 4], [5], [6, 7, 8]]), ('regression #5', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 2], [6, 2], [6, 4], [4, 4], [4, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]], [[2, 4], [4, 4], [4, 6], [2, 6], [2, 4]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]]], ['', '', 'k', 'k', '', 'k', 'k', 'k', 'k']], [[0, 1, 4], [2, 3, 5, 6, 7, 8]]), ('regression #11', [[[[4, 0], [6, 0], [6, 2], [4, 2], [4, 0]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]], [[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[0, 2], [2, 2], [2, 4], [0, 4], [0, 2]], [[0, 4], [2, 4], [2, 6], [0, 6], [0, 4]]], ['s', 's', 't', 's', 's']], [[0, 1], [2], [3, 4]]), ('regression #14', [[[[0, 0], [2, 0], [2, 2], [0, 2], [0, 0]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]], [[4, 4], [6, 4], [6, 6], [4, 6], [4, 4]], [[2, 0], [4, 0], [4, 2], [2, 2], [2, 0]]], ['w', 'w', 'w', 'w']], [[0, 1, 3], [2]])]]
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)

Boundary fixture	Actual	Expected	Outcome
control #0	`[[0, 1, 3], [2, 4, 5], [6, 7, 8]]`	`[[0, 1, 3], [2, 4, 5], [6, 7, 8]]`	Passed
regression #1	`[[0], [1], [2], [3], [4], [5], [6], [7], [8]]`	`[[0], [1], [2], [3], [4], [5], [6], [7], [8]]`	Passed
regression #2	`[[3, 4], [0, 1, 2, 5, 6, 7, 8]]`	`[[0, 1, 2, 5, 6, 7, 8], [3, 4]]`	Failed
regression #3	`[[0], [1], [3], [4], [6], [7], [2, 5, 8]]`	`[[0], [1], [2, 5, 8], [3], [4], [6], [7]]`	Failed
regression #4	`[[0], [1], [2], [5], [3, 4], [6, 7, 8]]`	`[[0], [1], [2], [3, 4], [5], [6, 7, 8]]`	Failed
regression #5	`[[0, 1, 4], [2, 3, 5, 6, 7, 8]]`	`[[0, 1, 4], [2, 3, 5, 6, 7, 8]]`	Passed
control #6	`[[0, 1, 2, 3, 4, 5, 6, 7, 8]]`	`[[0, 1, 2, 3, 4, 5, 6, 7, 8]]`	Passed
control #7	`[[0], [1], [2], [3], [4], [5], [6], [7], [8]]`	`[[0], [1], [2], [3], [4], [5], [6], [7], [8]]`	Passed

SHA-256 / 9c467f9a3023484167808c7b4649834e7788fb13f5f4799f553addef21023fb5

HELD IN THE MEMBER ARCHIVE

The verified repair and its recorded checks are member-only.

This mechanism has 8 recorded checks per implementation. The open-access tier publishes the failure and the unsuccessful fix; the repaired source that passes every check, and the observations that prove it, are available to members.

Every case sharing this mechanism uses the same contract and the same repair, so this one record is held back for all of them.

Member access is invitation-based. Sign in with your invited account to inspect the repair.

Verification & scope

Stipulated deterministic toy contract on a bounded input domain; results are rounded as stated and no conformance with any published standard or library is claimed. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.

Observations recorded using Python 3.12.14 at 2026-09-29T14:48:23.963816+00:00.

Case digest / 7c733ed20eed4115bf1cbd0ca244d952c8dc69ddab7f9ed9356dfbf533a2c649