FAILURE MAP
← Case archive

FA-70786 / GIS polygon topology / Open access

Dissolve grouping by attribute and shared edges: transitive union · case 01

Chains of same-valued polygons are split into several groups.

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

ROOT CAUSE

Raw indices are linked instead of their roots, overwriting earlier links.

VERIFIED REPAIR

At the transitive union step restore `parent[find(i)] = find(j)`, leaving the rest of the model unchanged.

Unsuccessful approach: Linking j directly under the root of i still overwrites the link j already had.

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[i] = j
    groups = {}
    for i in range(len(polys)):
        groups.setdefault(find(i), []).append(i)
    return sorted(groups.values())
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 #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 #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 #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]]), ('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 #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]])]]
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 fixtureActualExpectedOutcome
control #0[[0, 3], [1], [2, 4, 5], [6, 7, 8]][[0, 1, 3], [2, 4, 5], [6, 7, 8]]Failed
regression #1[[0], [1], [2], [3], [4], [5], [6], [7], [8]][[0], [1], [2], [3], [4], [5], [6], [7], [8]]Passed
regression #2[[0, 1, 2, 5, 6, 7, 8], [3, 4]][[0, 1, 2, 5, 6, 7, 8], [3, 4]]Passed
regression #3[[0], [1], [2, 5, 8], [3], [4], [6], [7]][[0], [1], [2, 5, 8], [3], [4], [6], [7]]Passed
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 / 7e1cbb12ebd4025e1fad0c16b2ed204ab2893a7663cc0a324b353c96cc3c80d3

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[j] = find(i)
    groups = {}
    for i in range(len(polys)):
        groups.setdefault(find(i), []).append(i)
    return sorted(groups.values())
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 #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 #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 #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]]), ('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 #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]])]]
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 fixtureActualExpectedOutcome
control #0[[0, 1, 3], [2], [4, 5], [6, 7, 8]][[0, 1, 3], [2, 4, 5], [6, 7, 8]]Failed
regression #1[[0], [1], [2], [3], [4], [5], [6], [7], [8]][[0], [1], [2], [3], [4], [5], [6], [7], [8]]Passed
regression #2[[0, 1, 2, 5], [3, 4], [6, 7, 8]][[0, 1, 2, 5, 6, 7, 8], [3, 4]]Failed
regression #3[[0], [1], [2, 5, 8], [3], [4], [6], [7]][[0], [1], [2, 5, 8], [3], [4], [6], [7]]Passed
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, 5], [3, 6, 7, 8]][[0, 1, 4], [2, 3, 5, 6, 7, 8]]Failed
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 / 20d87f32966e8b50634bb53450c22703a0746e1cf2f2d1d79b1e6722ad2a38dc

3 / The verified repair

Exit 0
"""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())
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 #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 #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 #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]]), ('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 #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]])]]
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 fixtureActualExpectedOutcome
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[[0, 1, 2, 5, 6, 7, 8], [3, 4]][[0, 1, 2, 5, 6, 7, 8], [3, 4]]Passed
regression #3[[0], [1], [2, 5, 8], [3], [4], [6], [7]][[0], [1], [2, 5, 8], [3], [4], [6], [7]]Passed
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 / 91902a7849bb91ee180aa5bd0aef56788fa0e3059e6cb9a1b1ff4929f05486d2

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

Case digest / 268018a0d7d2e20c7bd0debae2da5e6d523b1e65f883ffc315cdb72010435bce