{"abstract":"Holes in islands inside lakes are attached to the outer mainland ring.","category":"GIS polygon topology","checks":8,"contract":"Input: a list of closed integer rings from one shapefile record. Clockwise rings (negative shoelace sum) are exteriors, counter-clockwise rings are holes, zero-area rings are ignored. Each hole joins the SMALLEST-area exterior whose interior contains the hole first vertex (crossing-number test). A hole contained by no exterior is promoted to an exterior of its own. Return [[exterior_index, sorted hole indexes], ...] sorted by exterior index.","evaluation_group":"w2-gis-polygon-topology-shapefile-ring-assembly","failed_approach":"Choosing the largest containing exterior repeats the error for nested islands.","family":"w2-gis-polygon-topology-shapefile-ring-assembly-smallest-containing-exterior","id":"FA-70681","implementations":{"attempt":{"sha256":"a2a6ccc6b669dbce3467111d22544b52fe30d9ecf8129d084d6cb1abdeca0980","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nimport math\nN = 1\nobservations = []\ndef solve(x):\n    rings = x\n    def a2(r):\n        return sum(p[0] * q[1] - q[0] * p[1] for p, q in zip(r, r[1:]))\n    def inside(pt, r):\n        c = False\n        for a, b in zip(r, r[1:]):\n            if (a[1] > pt[1]) != (b[1] > pt[1]) and pt[0] < a[0] + (pt[1] - a[1]) * (b[0] - a[0]) / (b[1] - a[1]):\n                c = not c\n        return c\n    outers = [i for i, r in enumerate(rings) if a2(r) < 0]\n    holes = [i for i, r in enumerate(rings) if a2(r) > 0]\n    assign = {i: [] for i in outers}\n    for h in holes:\n        best = None\n        for o in outers:\n            if inside(rings[h][0], rings[o]) and (best is None or abs(a2(rings[o])) > abs(a2(rings[best]))):\n                best = o\n        if best is None:\n            assign[h] = []\n        else:\n            assign[best].append(h)\n    return [[o, sorted(assign[o])] for o in sorted(assign)]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\nfixtures = [[('control #0', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]]], [[0, [1]]]), ('control #1', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[20, 0], [20, 10], [30, 10], [30, 0], [20, 0]], [[22, 2], [24, 2], [24, 4], [22, 4], [22, 2]], [[2, 6], [4, 6], [4, 8], [2, 8], [2, 6]]], [[0, [3]], [1, [2]]]), ('regression #2', [[[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]], [[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]]], [[0, [1]], [2, [3]]]), ('regression #3', [[[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]], [[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]]], [[0, [1]], [2, [3]]]), ('regression #4', [[[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[6, 6], [8, 6], [8, 8], [6, 8], [6, 6]]], [[0, []], [1, []]]), ('regression #5', [[[40, 40], [42, 40], [42, 42], [40, 42], [40, 40]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]]], [[0, []], [1, []]]), ('regression #6', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[40, 40], [42, 40], [42, 42], [40, 42], [40, 40]]], [[0, []], [1, []]]), ('boundary #7', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[1, 1], [2, 2], [3, 3], [1, 1]]], [[0, []]])], [('regression #3', [[[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]], [[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]]], [[0, [1]], [2, [3]]]), ('regression #4', [[[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[6, 6], [8, 6], [8, 8], [6, 8], [6, 6]]], [[0, []], [1, []]]), ('regression #5', [[[40, 40], [42, 40], [42, 42], [40, 42], [40, 40]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]]], [[0, []], [1, []]]), ('regression #6', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[40, 40], [42, 40], [42, 42], [40, 42], [40, 40]]], [[0, []], [1, []]]), ('boundary #7', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[1, 1], [2, 2], [3, 3], [1, 1]]], [[0, []]]), ('control #8', [[[1, 1], [2, 1], [2, 2], [1, 2], [1, 1]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[3, 3], [4, 3], [4, 4], [3, 4], [3, 3]]], [[1, [0, 2]]]), ('regression #9', [[[50, 50], [52, 50], [52, 52], [50, 52], [50, 50]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[2, 2], [3, 2], [3, 3], [2, 3], [2, 2]], [[20, 20], [20, 40], [40, 40], [40, 20], [20, 20]]], [[0, []], [1, [2]], [3, []]]), ('regression #11', [[[0, 0], [0, 12], [12, 12], [12, 0], [0, 0]], [[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[1, 1], [2, 1], [2, 2], [1, 2], [1, 1]]], [[0, []], [1, [2]]])], [('regression #2', [[[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]], [[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]]], [[0, [1]], [2, [3]]]), ('regression #3', [[[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]], [[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]]], [[0, [1]], [2, [3]]]), ('control #8', [[[1, 1], [2, 1], [2, 2], [1, 2], [1, 1]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[3, 3], [4, 3], [4, 4], [3, 4], [3, 3]]], [[1, [0, 2]]]), ('regression #9', [[[50, 50], [52, 50], [52, 52], [50, 52], [50, 50]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[2, 2], [3, 2], [3, 3], [2, 3], [2, 2]], [[20, 20], [20, 40], [40, 40], [40, 20], [20, 20]]], [[0, []], [1, [2]], [3, []]]), ('regression #10', [[[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[0, 0], [0, 12], [12, 12], [12, 0], [0, 0]], [[6, 6], [8, 6], [8, 8], [6, 8], [6, 6]]], [[0, []], [1, [2]]]), ('regression #11', [[[0, 0], [0, 12], [12, 12], [12, 0], [0, 0]], [[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[1, 1], [2, 1], [2, 2], [1, 2], [1, 1]]], [[0, []], [1, [2]]]), ('control #12', [[[0, 0], [0, 4], [4, 4], [4, 0], [0, 0]]], [[0, []]]), ('regression #13', [[[0, 0], [4, 0], [4, 4], [0, 4], [0, 0]]], [[0, []]])], [('control #0', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]]], [[0, [1]]]), ('control #1', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[20, 0], [20, 10], [30, 10], [30, 0], [20, 0]], [[22, 2], [24, 2], [24, 4], [22, 4], [22, 2]], [[2, 6], [4, 6], [4, 8], [2, 8], [2, 6]]], [[0, [3]], [1, [2]]]), ('regression #2', [[[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]], [[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]]], [[0, [1]], [2, [3]]]), ('regression #3', [[[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]], [[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]]], [[0, [1]], [2, [3]]]), ('regression #10', [[[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[0, 0], [0, 12], [12, 12], [12, 0], [0, 0]], [[6, 6], [8, 6], [8, 8], [6, 8], [6, 6]]], [[0, []], [1, [2]]]), ('regression #11', [[[0, 0], [0, 12], [12, 12], [12, 0], [0, 0]], [[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[1, 1], [2, 1], [2, 2], [1, 2], [1, 1]]], [[0, []], [1, [2]]]), ('control #12', [[[0, 0], [0, 4], [4, 4], [4, 0], [0, 0]]], [[0, []]]), ('regression #13', [[[0, 0], [4, 0], [4, 4], [0, 4], [0, 0]]], [[0, []]])], [('control #0', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]]], [[0, [1]]]), ('control #1', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[20, 0], [20, 10], [30, 10], [30, 0], [20, 0]], [[22, 2], [24, 2], [24, 4], [22, 4], [22, 2]], [[2, 6], [4, 6], [4, 8], [2, 8], [2, 6]]], [[0, [3]], [1, [2]]]), ('regression #2', [[[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]], [[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]]], [[0, [1]], [2, [3]]]), ('regression #3', [[[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]], [[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]]], [[0, [1]], [2, [3]]]), ('regression #4', [[[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[6, 6], [8, 6], [8, 8], [6, 8], [6, 6]]], [[0, []], [1, []]]), ('regression #5', [[[40, 40], [42, 40], [42, 42], [40, 42], [40, 40]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]]], [[0, []], [1, []]]), ('regression #6', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[40, 40], [42, 40], [42, 42], [40, 42], [40, 40]]], [[0, []], [1, []]]), ('boundary #7', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[1, 1], [2, 2], [3, 3], [1, 1]]], [[0, []]])]]\nfor label, args, expected in fixtures[N-1]:\n    check(label, solve(args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"broken":{"sha256":"0242479df31ba7a88cafae6f832cea989ef22e4bc888f7529a3f707e352b357e","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nimport math\nN = 1\nobservations = []\ndef solve(x):\n    rings = x\n    def a2(r):\n        return sum(p[0] * q[1] - q[0] * p[1] for p, q in zip(r, r[1:]))\n    def inside(pt, r):\n        c = False\n        for a, b in zip(r, r[1:]):\n            if (a[1] > pt[1]) != (b[1] > pt[1]) and pt[0] < a[0] + (pt[1] - a[1]) * (b[0] - a[0]) / (b[1] - a[1]):\n                c = not c\n        return c\n    outers = [i for i, r in enumerate(rings) if a2(r) < 0]\n    holes = [i for i, r in enumerate(rings) if a2(r) > 0]\n    assign = {i: [] for i in outers}\n    for h in holes:\n        best = None\n        for o in outers:\n            if inside(rings[h][0], rings[o]) and best is None:\n                best = o\n        if best is None:\n            assign[h] = []\n        else:\n            assign[best].append(h)\n    return [[o, sorted(assign[o])] for o in sorted(assign)]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\nfixtures = [[('control #0', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]]], [[0, [1]]]), ('control #1', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[20, 0], [20, 10], [30, 10], [30, 0], [20, 0]], [[22, 2], [24, 2], [24, 4], [22, 4], [22, 2]], [[2, 6], [4, 6], [4, 8], [2, 8], [2, 6]]], [[0, [3]], [1, [2]]]), ('regression #2', [[[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]], [[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]]], [[0, [1]], [2, [3]]]), ('regression #3', [[[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]], [[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]]], [[0, [1]], [2, [3]]]), ('regression #4', [[[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[6, 6], [8, 6], [8, 8], [6, 8], [6, 6]]], [[0, []], [1, []]]), ('regression #5', [[[40, 40], [42, 40], [42, 42], [40, 42], [40, 40]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]]], [[0, []], [1, []]]), ('regression #6', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[40, 40], [42, 40], [42, 42], [40, 42], [40, 40]]], [[0, []], [1, []]]), ('boundary #7', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[1, 1], [2, 2], [3, 3], [1, 1]]], [[0, []]])], [('regression #3', [[[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]], [[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]]], [[0, [1]], [2, [3]]]), ('regression #4', [[[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[6, 6], [8, 6], [8, 8], [6, 8], [6, 6]]], [[0, []], [1, []]]), ('regression #5', [[[40, 40], [42, 40], [42, 42], [40, 42], [40, 40]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]]], [[0, []], [1, []]]), ('regression #6', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[40, 40], [42, 40], [42, 42], [40, 42], [40, 40]]], [[0, []], [1, []]]), ('boundary #7', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[1, 1], [2, 2], [3, 3], [1, 1]]], [[0, []]]), ('control #8', [[[1, 1], [2, 1], [2, 2], [1, 2], [1, 1]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[3, 3], [4, 3], [4, 4], [3, 4], [3, 3]]], [[1, [0, 2]]]), ('regression #9', [[[50, 50], [52, 50], [52, 52], [50, 52], [50, 50]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[2, 2], [3, 2], [3, 3], [2, 3], [2, 2]], [[20, 20], [20, 40], [40, 40], [40, 20], [20, 20]]], [[0, []], [1, [2]], [3, []]]), ('regression #11', [[[0, 0], [0, 12], [12, 12], [12, 0], [0, 0]], [[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[1, 1], [2, 1], [2, 2], [1, 2], [1, 1]]], [[0, []], [1, [2]]])], [('regression #2', [[[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]], [[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]]], [[0, [1]], [2, [3]]]), ('regression #3', [[[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]], [[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]]], [[0, [1]], [2, [3]]]), ('control #8', [[[1, 1], [2, 1], [2, 2], [1, 2], [1, 1]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[3, 3], [4, 3], [4, 4], [3, 4], [3, 3]]], [[1, [0, 2]]]), ('regression #9', [[[50, 50], [52, 50], [52, 52], [50, 52], [50, 50]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[2, 2], [3, 2], [3, 3], [2, 3], [2, 2]], [[20, 20], [20, 40], [40, 40], [40, 20], [20, 20]]], [[0, []], [1, [2]], [3, []]]), ('regression #10', [[[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[0, 0], [0, 12], [12, 12], [12, 0], [0, 0]], [[6, 6], [8, 6], [8, 8], [6, 8], [6, 6]]], [[0, []], [1, [2]]]), ('regression #11', [[[0, 0], [0, 12], [12, 12], [12, 0], [0, 0]], [[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[1, 1], [2, 1], [2, 2], [1, 2], [1, 1]]], [[0, []], [1, [2]]]), ('control #12', [[[0, 0], [0, 4], [4, 4], [4, 0], [0, 0]]], [[0, []]]), ('regression #13', [[[0, 0], [4, 0], [4, 4], [0, 4], [0, 0]]], [[0, []]])], [('control #0', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]]], [[0, [1]]]), ('control #1', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[20, 0], [20, 10], [30, 10], [30, 0], [20, 0]], [[22, 2], [24, 2], [24, 4], [22, 4], [22, 2]], [[2, 6], [4, 6], [4, 8], [2, 8], [2, 6]]], [[0, [3]], [1, [2]]]), ('regression #2', [[[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]], [[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]]], [[0, [1]], [2, [3]]]), ('regression #3', [[[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]], [[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]]], [[0, [1]], [2, [3]]]), ('regression #10', [[[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[0, 0], [0, 12], [12, 12], [12, 0], [0, 0]], [[6, 6], [8, 6], [8, 8], [6, 8], [6, 6]]], [[0, []], [1, [2]]]), ('regression #11', [[[0, 0], [0, 12], [12, 12], [12, 0], [0, 0]], [[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[1, 1], [2, 1], [2, 2], [1, 2], [1, 1]]], [[0, []], [1, [2]]]), ('control #12', [[[0, 0], [0, 4], [4, 4], [4, 0], [0, 0]]], [[0, []]]), ('regression #13', [[[0, 0], [4, 0], [4, 4], [0, 4], [0, 0]]], [[0, []]])], [('control #0', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]]], [[0, [1]]]), ('control #1', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[20, 0], [20, 10], [30, 10], [30, 0], [20, 0]], [[22, 2], [24, 2], [24, 4], [22, 4], [22, 2]], [[2, 6], [4, 6], [4, 8], [2, 8], [2, 6]]], [[0, [3]], [1, [2]]]), ('regression #2', [[[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]], [[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]]], [[0, [1]], [2, [3]]]), ('regression #3', [[[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]], [[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]]], [[0, [1]], [2, [3]]]), ('regression #4', [[[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[6, 6], [8, 6], [8, 8], [6, 8], [6, 6]]], [[0, []], [1, []]]), ('regression #5', [[[40, 40], [42, 40], [42, 42], [40, 42], [40, 40]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]]], [[0, []], [1, []]]), ('regression #6', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[40, 40], [42, 40], [42, 42], [40, 42], [40, 40]]], [[0, []], [1, []]]), ('boundary #7', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[1, 1], [2, 2], [3, 3], [1, 1]]], [[0, []]])]]\nfor label, args, expected in fixtures[N-1]:\n    check(label, solve(args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"fixed":{"sha256":"9a8c26b80f778b36d9c30f0999733848b664d607a7d57d197524ff3af4952019","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nimport math\nN = 1\nobservations = []\ndef solve(x):\n    rings = x\n    def a2(r):\n        return sum(p[0] * q[1] - q[0] * p[1] for p, q in zip(r, r[1:]))\n    def inside(pt, r):\n        c = False\n        for a, b in zip(r, r[1:]):\n            if (a[1] > pt[1]) != (b[1] > pt[1]) and pt[0] < a[0] + (pt[1] - a[1]) * (b[0] - a[0]) / (b[1] - a[1]):\n                c = not c\n        return c\n    outers = [i for i, r in enumerate(rings) if a2(r) < 0]\n    holes = [i for i, r in enumerate(rings) if a2(r) > 0]\n    assign = {i: [] for i in outers}\n    for h in holes:\n        best = None\n        for o in outers:\n            if inside(rings[h][0], rings[o]) and (best is None or abs(a2(rings[o])) < abs(a2(rings[best]))):\n                best = o\n        if best is None:\n            assign[h] = []\n        else:\n            assign[best].append(h)\n    return [[o, sorted(assign[o])] for o in sorted(assign)]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\nfixtures = [[('control #0', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]]], [[0, [1]]]), ('control #1', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[20, 0], [20, 10], [30, 10], [30, 0], [20, 0]], [[22, 2], [24, 2], [24, 4], [22, 4], [22, 2]], [[2, 6], [4, 6], [4, 8], [2, 8], [2, 6]]], [[0, [3]], [1, [2]]]), ('regression #2', [[[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]], [[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]]], [[0, [1]], [2, [3]]]), ('regression #3', [[[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]], [[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]]], [[0, [1]], [2, [3]]]), ('regression #4', [[[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[6, 6], [8, 6], [8, 8], [6, 8], [6, 6]]], [[0, []], [1, []]]), ('regression #5', [[[40, 40], [42, 40], [42, 42], [40, 42], [40, 40]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]]], [[0, []], [1, []]]), ('regression #6', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[40, 40], [42, 40], [42, 42], [40, 42], [40, 40]]], [[0, []], [1, []]]), ('boundary #7', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[1, 1], [2, 2], [3, 3], [1, 1]]], [[0, []]])], [('regression #3', [[[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]], [[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]]], [[0, [1]], [2, [3]]]), ('regression #4', [[[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[6, 6], [8, 6], [8, 8], [6, 8], [6, 6]]], [[0, []], [1, []]]), ('regression #5', [[[40, 40], [42, 40], [42, 42], [40, 42], [40, 40]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]]], [[0, []], [1, []]]), ('regression #6', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[40, 40], [42, 40], [42, 42], [40, 42], [40, 40]]], [[0, []], [1, []]]), ('boundary #7', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[1, 1], [2, 2], [3, 3], [1, 1]]], [[0, []]]), ('control #8', [[[1, 1], [2, 1], [2, 2], [1, 2], [1, 1]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[3, 3], [4, 3], [4, 4], [3, 4], [3, 3]]], [[1, [0, 2]]]), ('regression #9', [[[50, 50], [52, 50], [52, 52], [50, 52], [50, 50]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[2, 2], [3, 2], [3, 3], [2, 3], [2, 2]], [[20, 20], [20, 40], [40, 40], [40, 20], [20, 20]]], [[0, []], [1, [2]], [3, []]]), ('regression #11', [[[0, 0], [0, 12], [12, 12], [12, 0], [0, 0]], [[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[1, 1], [2, 1], [2, 2], [1, 2], [1, 1]]], [[0, []], [1, [2]]])], [('regression #2', [[[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]], [[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]]], [[0, [1]], [2, [3]]]), ('regression #3', [[[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]], [[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]]], [[0, [1]], [2, [3]]]), ('control #8', [[[1, 1], [2, 1], [2, 2], [1, 2], [1, 1]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[3, 3], [4, 3], [4, 4], [3, 4], [3, 3]]], [[1, [0, 2]]]), ('regression #9', [[[50, 50], [52, 50], [52, 52], [50, 52], [50, 50]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[2, 2], [3, 2], [3, 3], [2, 3], [2, 2]], [[20, 20], [20, 40], [40, 40], [40, 20], [20, 20]]], [[0, []], [1, [2]], [3, []]]), ('regression #10', [[[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[0, 0], [0, 12], [12, 12], [12, 0], [0, 0]], [[6, 6], [8, 6], [8, 8], [6, 8], [6, 6]]], [[0, []], [1, [2]]]), ('regression #11', [[[0, 0], [0, 12], [12, 12], [12, 0], [0, 0]], [[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[1, 1], [2, 1], [2, 2], [1, 2], [1, 1]]], [[0, []], [1, [2]]]), ('control #12', [[[0, 0], [0, 4], [4, 4], [4, 0], [0, 0]]], [[0, []]]), ('regression #13', [[[0, 0], [4, 0], [4, 4], [0, 4], [0, 0]]], [[0, []]])], [('control #0', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]]], [[0, [1]]]), ('control #1', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[20, 0], [20, 10], [30, 10], [30, 0], [20, 0]], [[22, 2], [24, 2], [24, 4], [22, 4], [22, 2]], [[2, 6], [4, 6], [4, 8], [2, 8], [2, 6]]], [[0, [3]], [1, [2]]]), ('regression #2', [[[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]], [[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]]], [[0, [1]], [2, [3]]]), ('regression #3', [[[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]], [[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]]], [[0, [1]], [2, [3]]]), ('regression #10', [[[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[0, 0], [0, 12], [12, 12], [12, 0], [0, 0]], [[6, 6], [8, 6], [8, 8], [6, 8], [6, 6]]], [[0, []], [1, [2]]]), ('regression #11', [[[0, 0], [0, 12], [12, 12], [12, 0], [0, 0]], [[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[1, 1], [2, 1], [2, 2], [1, 2], [1, 1]]], [[0, []], [1, [2]]]), ('control #12', [[[0, 0], [0, 4], [4, 4], [4, 0], [0, 0]]], [[0, []]]), ('regression #13', [[[0, 0], [4, 0], [4, 4], [0, 4], [0, 0]]], [[0, []]])], [('control #0', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[2, 2], [4, 2], [4, 4], [2, 4], [2, 2]]], [[0, [1]]]), ('control #1', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[20, 0], [20, 10], [30, 10], [30, 0], [20, 0]], [[22, 2], [24, 2], [24, 4], [22, 4], [22, 2]], [[2, 6], [4, 6], [4, 8], [2, 8], [2, 6]]], [[0, [3]], [1, [2]]]), ('regression #2', [[[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]], [[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]]], [[0, [1]], [2, [3]]]), ('regression #3', [[[5, 5], [5, 25], [25, 25], [25, 5], [5, 5]], [[10, 10], [12, 10], [12, 12], [10, 12], [10, 10]], [[0, 0], [0, 30], [30, 30], [30, 0], [0, 0]], [[2, 2], [28, 2], [28, 28], [2, 28], [2, 2]]], [[0, [1]], [2, [3]]]), ('regression #4', [[[0, 0], [0, 10], [4, 10], [4, 4], [10, 4], [10, 0], [0, 0]], [[6, 6], [8, 6], [8, 8], [6, 8], [6, 6]]], [[0, []], [1, []]]), ('regression #5', [[[40, 40], [42, 40], [42, 42], [40, 42], [40, 40]], [[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]]], [[0, []], [1, []]]), ('regression #6', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[40, 40], [42, 40], [42, 42], [40, 42], [40, 40]]], [[0, []], [1, []]]), ('boundary #7', [[[0, 0], [0, 10], [10, 10], [10, 0], [0, 0]], [[1, 1], [2, 2], [3, 3], [1, 1]]], [[0, []]])]]\nfor label, args, expected in fixtures[N-1]:\n    check(label, solve(args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"}},"limitations":"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.","method":"Deterministic executable model with adversarial boundary fixtures.","provenance":{"created_by":"Failure Map","dependencies":"Python standard library","family":"w2-gis-polygon-topology-shapefile-ring-assembly-smallest-containing-exterior","generated_at":"2026-09-29T14:48:22.955302+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"Shapefile readers must rebuild polygon structure from flat part lists; islands in lakes and orphan holes are the classic failure cases.","repair":"At the smallest containing exterior step restore `and (best is None or abs(a2(rings[o])) < abs(a2(rings[best])))`, leaving the rest of the model unchanged.","root_cause":"Each hole is attached to the first exterior that contains it.","sha256":"c66d2e23e7b4d4db46acd4b83f4a59cf3d1bd7d3f42bde532166be509805de6c","title":"Shapefile part rings assembled into polygons: smallest containing exterior · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verification":{"attempt":{"elapsed_ms":40.708,"exit_code":1,"observations":[{"actual":[[0,[1]]],"check":"control #0","expected":[[0,[1]]],"passed":true},{"actual":[[0,[3]],[1,[2]]],"check":"control #1","expected":[[0,[3]],[1,[2]]],"passed":true},{"actual":[[0,[1,3]],[2,[]]],"check":"regression #2","expected":[[0,[1]],[2,[3]]],"passed":false},{"actual":[[0,[]],[2,[1,3]]],"check":"regression #3","expected":[[0,[1]],[2,[3]]],"passed":false},{"actual":[[0,[]],[1,[]]],"check":"regression #4","expected":[[0,[]],[1,[]]],"passed":true},{"actual":[[0,[]],[1,[]]],"check":"regression #5","expected":[[0,[]],[1,[]]],"passed":true},{"actual":[[0,[]],[1,[]]],"check":"regression #6","expected":[[0,[]],[1,[]]],"passed":true},{"actual":[[0,[]]],"check":"boundary #7","expected":[[0,[]]],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"control #0\", \"actual\": [[0, [1]]], \"expected\": [[0, [1]]], \"passed\": true}, {\"check\": \"control #1\", \"actual\": [[0, [3]], [1, [2]]], \"expected\": [[0, [3]], [1, [2]]], \"passed\": true}, {\"check\": \"regression #2\", \"actual\": [[0, [1, 3]], [2, []]], \"expected\": [[0, [1]], [2, [3]]], \"passed\": false}, {\"check\": \"regression #3\", \"actual\": [[0, []], [2, [1, 3]]], \"expected\": [[0, [1]], [2, [3]]], \"passed\": false}, {\"check\": \"regression #4\", \"actual\": [[0, []], [1, []]], \"expected\": [[0, []], [1, []]], \"passed\": true}, {\"check\": \"regression #5\", \"actual\": [[0, []], [1, []]], \"expected\": [[0, []], [1, []]], \"passed\": true}, {\"check\": \"regression #6\", \"actual\": [[0, []], [1, []]], \"expected\": [[0, []], [1, []]], \"passed\": true}, {\"check\": \"boundary #7\", \"actual\": [[0, []]], \"expected\": [[0, []]], \"passed\": true}], \"passed\": false}\n"},"broken":{"elapsed_ms":39.135,"exit_code":1,"observations":[{"actual":[[0,[1]]],"check":"control #0","expected":[[0,[1]]],"passed":true},{"actual":[[0,[3]],[1,[2]]],"check":"control #1","expected":[[0,[3]],[1,[2]]],"passed":true},{"actual":[[0,[1,3]],[2,[]]],"check":"regression #2","expected":[[0,[1]],[2,[3]]],"passed":false},{"actual":[[0,[1]],[2,[3]]],"check":"regression #3","expected":[[0,[1]],[2,[3]]],"passed":true},{"actual":[[0,[]],[1,[]]],"check":"regression #4","expected":[[0,[]],[1,[]]],"passed":true},{"actual":[[0,[]],[1,[]]],"check":"regression #5","expected":[[0,[]],[1,[]]],"passed":true},{"actual":[[0,[]],[1,[]]],"check":"regression #6","expected":[[0,[]],[1,[]]],"passed":true},{"actual":[[0,[]]],"check":"boundary #7","expected":[[0,[]]],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"control #0\", \"actual\": [[0, [1]]], \"expected\": [[0, [1]]], \"passed\": true}, {\"check\": \"control #1\", \"actual\": [[0, [3]], [1, [2]]], \"expected\": [[0, [3]], [1, [2]]], \"passed\": true}, {\"check\": \"regression #2\", \"actual\": [[0, [1, 3]], [2, []]], \"expected\": [[0, [1]], [2, [3]]], \"passed\": false}, {\"check\": \"regression #3\", \"actual\": [[0, [1]], [2, [3]]], \"expected\": [[0, [1]], [2, [3]]], \"passed\": true}, {\"check\": \"regression #4\", \"actual\": [[0, []], [1, []]], \"expected\": [[0, []], [1, []]], \"passed\": true}, {\"check\": \"regression #5\", \"actual\": [[0, []], [1, []]], \"expected\": [[0, []], [1, []]], \"passed\": true}, {\"check\": \"regression #6\", \"actual\": [[0, []], [1, []]], \"expected\": [[0, []], [1, []]], \"passed\": true}, {\"check\": \"boundary #7\", \"actual\": [[0, []]], \"expected\": [[0, []]], \"passed\": true}], \"passed\": false}\n"},"fixed":{"elapsed_ms":39.628,"exit_code":0,"observations":[{"actual":[[0,[1]]],"check":"control #0","expected":[[0,[1]]],"passed":true},{"actual":[[0,[3]],[1,[2]]],"check":"control #1","expected":[[0,[3]],[1,[2]]],"passed":true},{"actual":[[0,[1]],[2,[3]]],"check":"regression #2","expected":[[0,[1]],[2,[3]]],"passed":true},{"actual":[[0,[1]],[2,[3]]],"check":"regression #3","expected":[[0,[1]],[2,[3]]],"passed":true},{"actual":[[0,[]],[1,[]]],"check":"regression #4","expected":[[0,[]],[1,[]]],"passed":true},{"actual":[[0,[]],[1,[]]],"check":"regression #5","expected":[[0,[]],[1,[]]],"passed":true},{"actual":[[0,[]],[1,[]]],"check":"regression #6","expected":[[0,[]],[1,[]]],"passed":true},{"actual":[[0,[]]],"check":"boundary #7","expected":[[0,[]]],"passed":true}],"passed":true,"stderr":"","stdout":"{\"observations\": [{\"check\": \"control #0\", \"actual\": [[0, [1]]], \"expected\": [[0, [1]]], \"passed\": true}, {\"check\": \"control #1\", \"actual\": [[0, [3]], [1, [2]]], \"expected\": [[0, [3]], [1, [2]]], \"passed\": true}, {\"check\": \"regression #2\", \"actual\": [[0, [1]], [2, [3]]], \"expected\": [[0, [1]], [2, [3]]], \"passed\": true}, {\"check\": \"regression #3\", \"actual\": [[0, [1]], [2, [3]]], \"expected\": [[0, [1]], [2, [3]]], \"passed\": true}, {\"check\": \"regression #4\", \"actual\": [[0, []], [1, []]], \"expected\": [[0, []], [1, []]], \"passed\": true}, {\"check\": \"regression #5\", \"actual\": [[0, []], [1, []]], \"expected\": [[0, []], [1, []]], \"passed\": true}, {\"check\": \"regression #6\", \"actual\": [[0, []], [1, []]], \"expected\": [[0, []], [1, []]], \"passed\": true}, {\"check\": \"boundary #7\", \"actual\": [[0, []]], \"expected\": [[0, []]], \"passed\": true}], \"passed\": true}\n"}},"verified":true,"visibility":"public"}