{"abstract":"Connected mazes are reported as loops or disconnected.","category":"Procedural level generation constraints","checks":8,"contract":"Cells (x, y) with 0 <= x < w, 0 <= y < h. First pass over passages [[x1, y1], [x2, y2]]: out-of-bounds or non-orthogonally-adjacent pairs -> 'invalid-edge'; the same passage twice in either orientation -> 'duplicate'. Then union passages in order: joining already connected cells -> 'loop'. Finally 'perfect' if all cells are connected, else 'disconnected'.","evaluation_group":"w2-procedural-level-generation-constraints-perfect-maze","failed_approach":"Linking the endpoint to the other root still detaches the rest of its tree.","family":"w2-procedural-level-generation-constraints-perfect-maze-union-linkage","id":"FA-86631","implementations":{"attempt":{"sha256":"f54249e4f6839867c8ae54adf81b58b9d7f45b506e79e6d2261c772f388527de","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(w, h, passages):\n    seen = set()\n    parent = {(x, y): (x, y) for x in range(w) for y in range(h)}\n    def find(p):\n        while parent[p] != p:\n            parent[p] = parent[parent[p]]\n            p = parent[p]\n        return p\n    for (x1, y1), (x2, y2) in passages:\n        if not (0 <= x1 < w and 0 <= y1 < h and 0 <= x2 < w and 0 <= y2 < h):\n            return 'invalid-edge'\n        if abs(x1 - x2) + abs(y1 - y2) != 1:\n            return 'invalid-edge'\n        key = tuple(sorted([(x1, y1), (x2, y2)]))\n        if key in seen:\n            return 'duplicate'\n        seen.add(key)\n    for (x1, y1), (x2, y2) in passages:\n        a, b = find((x1, y1)), find((x2, y2))\n        if a == b:\n            return 'loop'\n        parent[(x1, y1)] = b\n    roots = {find(p) for p in parent}\n    return 'perfect' if len(roots) == 1 else 'disconnected'\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[('regression union linkage #1',\n   [4,\n    3,\n    [[[1, 0], [1, 1]],\n     [[0, 1], [0, 0]],\n     [[0, 1], [0, 2]],\n     [[2, 0], [2, 1]],\n     [[1, 0], [0, 0]],\n     [[1, 0], [2, 0]],\n     [[2, 1], [2, 2]],\n     [[2, 2], [3, 2]],\n     [[2, 1], [3, 1]],\n     [[2, 2], [1, 2]],\n     [[1, 1], [0, 1]],\n     [[0, 2], [1, 2]]]],\n   'loop'),\n  ('regression union linkage #2',\n   [3,\n    3,\n    [[[2, 1], [2, 0]],\n     [[2, 0], [1, 0]],\n     [[0, 1], [0, 0]],\n     [[0, 1], [1, 1]],\n     [[1, 0], [1, 1]],\n     [[0, 0], [1, 0]],\n     [[0, 1], [0, 2]]]],\n   'loop'),\n  ('regression union linkage #3',\n   [4,\n    2,\n    [[[1, 0], [0, 0]],\n     [[1, 0], [1, 1]],\n     [[3, 0], [2, 0]],\n     [[2, 1], [3, 1]],\n     [[2, 1], [2, 0]],\n     [[1, 1], [2, 1]],\n     [[1, 1], [0, 1]],\n     [[3, 1], [3, 0]]]],\n   'loop'),\n  ('regression union linkage #4',\n   [4,\n    4,\n    [[[0, 0], [0, 1]],\n     [[2, 0], [3, 0]],\n     [[0, 2], [0, 1]],\n     [[1, 0], [2, 0]],\n     [[2, 1], [3, 1]],\n     [[1, 3], [2, 3]],\n     [[3, 3], [3, 2]],\n     [[0, 2], [0, 3]],\n     [[2, 1], [1, 1]],\n     [[2, 2], [2, 1]],\n     [[1, 3], [0, 3]],\n     [[1, 1], [1, 2]],\n     [[2, 0], [2, 1]],\n     [[2, 2], [2, 3]],\n     [[2, 3], [3, 3]],\n     [[1, 2], [2, 2]]]],\n   'loop'),\n  ('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),\n  ('reversed duplicate #1', [2, 1, [[[0, 0], [1, 0]], [[1, 0], [0, 0]]]], 'duplicate'),\n  ('single cell maze #1', [1, 1, []], 'perfect'),\n  ('control #1',\n   [3, 2, [[[2, 1], [1, 1]], [[0, 1], [0, 0]], [[1, 1], [2, 2]], [[0, 0], [1, 0]]]],\n   'invalid-edge')],\n [('regression union linkage #1',\n   [4,\n    2,\n    [[[1, 0], [0, 0]],\n     [[1, 0], [1, 1]],\n     [[3, 0], [2, 0]],\n     [[2, 1], [3, 1]],\n     [[2, 1], [2, 0]],\n     [[1, 1], [2, 1]],\n     [[1, 1], [0, 1]],\n     [[3, 1], [3, 0]]]],\n   'loop'),\n  ('regression union linkage #2',\n   [4,\n    4,\n    [[[0, 0], [0, 1]],\n     [[2, 0], [3, 0]],\n     [[0, 2], [0, 1]],\n     [[1, 0], [2, 0]],\n     [[2, 1], [3, 1]],\n     [[1, 3], [2, 3]],\n     [[3, 3], [3, 2]],\n     [[0, 2], [0, 3]],\n     [[2, 1], [1, 1]],\n     [[2, 2], [2, 1]],\n     [[1, 3], [0, 3]],\n     [[1, 1], [1, 2]],\n     [[2, 0], [2, 1]],\n     [[2, 2], [2, 3]],\n     [[2, 3], [3, 3]],\n     [[1, 2], [2, 2]]]],\n   'loop'),\n  ('regression union linkage #3',\n   [3, 2, [[[0, 1], [0, 0]], [[1, 1], [2, 1]], [[1, 1], [0, 1]], [[1, 0], [1, 1]], [[2, 1], [2, 0]]]],\n   'perfect'),\n  ('regression union linkage #4', [1, 3, [[[0, 1], [0, 2]], [[0, 1], [0, 0]]]], 'perfect'),\n  ('single cell maze #1', [1, 1, []], 'perfect'),\n  ('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),\n  ('control #1',\n   [3, 2, [[[2, 1], [1, 1]], [[0, 1], [0, 0]], [[1, 1], [2, 2]], [[0, 0], [1, 0]]]],\n   'invalid-edge'),\n  ('control #2',\n   [4, 1, [[[2, 0], [1, 0]], [[3, 0], [2, 0]], [[0, 0], [1, 0]], [[1, 0], [0, 0]]]],\n   'duplicate')],\n [('regression union linkage #1',\n   [3, 2, [[[0, 1], [0, 0]], [[1, 1], [2, 1]], [[1, 1], [0, 1]], [[1, 0], [1, 1]], [[2, 1], [2, 0]]]],\n   'perfect'),\n  ('regression union linkage #2', [1, 3, [[[0, 1], [0, 2]], [[0, 1], [0, 0]]]], 'perfect'),\n  ('regression union linkage #3',\n   [2, 2, [[[1, 1], [1, 0]], [[1, 1], [0, 1]], [[0, 0], [1, 0]], [[0, 1], [0, 0]]]],\n   'loop'),\n  ('regression union linkage #4',\n   [4,\n    3,\n    [[[1, 2], [0, 2]],\n     [[1, 1], [2, 1]],\n     [[3, 0], [2, 0]],\n     [[3, 1], [3, 0]],\n     [[3, 2], [3, 1]],\n     [[1, 1], [1, 0]],\n     [[2, 1], [3, 1]],\n     [[2, 1], [2, 2]],\n     [[2, 1], [2, 0]],\n     [[0, 1], [1, 1]],\n     [[0, 0], [0, 1]],\n     [[0, 2], [0, 1]],\n     [[1, 2], [2, 2]]]],\n   'loop'),\n  ('reversed duplicate #1', [2, 1, [[[0, 0], [1, 0]], [[1, 0], [0, 0]]]], 'duplicate'),\n  ('single cell maze #1', [1, 1, []], 'perfect'),\n  ('control #1',\n   [4, 1, [[[2, 0], [1, 0]], [[3, 0], [2, 0]], [[0, 0], [1, 0]], [[1, 0], [0, 0]]]],\n   'duplicate'),\n  ('control #2', [4, 1, [[[2, 0], [2, 0]], [[1, 0], [0, 0]], [[2, 0], [1, 0]]]], 'invalid-edge')],\n [('regression union linkage #1',\n   [2, 2, [[[1, 1], [1, 0]], [[1, 1], [0, 1]], [[0, 0], [1, 0]], [[0, 1], [0, 0]]]],\n   'loop'),\n  ('regression union linkage #2',\n   [4,\n    3,\n    [[[1, 2], [0, 2]],\n     [[1, 1], [2, 1]],\n     [[3, 0], [2, 0]],\n     [[3, 1], [3, 0]],\n     [[3, 2], [3, 1]],\n     [[1, 1], [1, 0]],\n     [[2, 1], [3, 1]],\n     [[2, 1], [2, 2]],\n     [[2, 1], [2, 0]],\n     [[0, 1], [1, 1]],\n     [[0, 0], [0, 1]],\n     [[0, 2], [0, 1]],\n     [[1, 2], [2, 2]]]],\n   'loop'),\n  ('regression union linkage #3',\n   [4,\n    4,\n    [[[1, 1], [1, 2]],\n     [[3, 1], [2, 1]],\n     [[0, 2], [1, 2]],\n     [[0, 0], [0, 1]],\n     [[0, 2], [0, 3]],\n     [[1, 1], [1, 0]],\n     [[1, 1], [2, 1]],\n     [[1, 0], [2, 0]],\n     [[1, 3], [1, 2]],\n     [[2, 1], [2, 0]],\n     [[3, 1], [3, 0]],\n     [[0, 0], [1, 0]],\n     [[3, 2], [3, 1]]]],\n   'loop'),\n  ('regression union linkage #4', [1, 4, [[[0, 2], [0, 3]], [[0, 2], [0, 1]], [[0, 1], [0, 0]]]], 'perfect'),\n  ('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),\n  ('reversed duplicate #1', [2, 1, [[[0, 0], [1, 0]], [[1, 0], [0, 0]]]], 'duplicate'),\n  ('control #1',\n   [3,\n    3,\n    [[[1, 0], [1, 0]],\n     [[1, 0], [2, 0]],\n     [[0, 2], [0, 1]],\n     [[2, 2], [2, 1]],\n     [[0, 2], [1, 2]],\n     [[1, 0], [0, 0]],\n     [[0, 1], [1, 1]]]],\n   'invalid-edge'),\n  ('control #2',\n   [3,\n    4,\n    [[[1, 1], [1, 1]],\n     [[1, 3], [2, 3]],\n     [[2, 2], [2, 1]],\n     [[2, 0], [1, 0]],\n     [[1, 2], [2, 2]],\n     [[1, 2], [1, 3]],\n     [[1, 2], [0, 2]],\n     [[1, 2], [1, 1]],\n     [[0, 1], [1, 1]],\n     [[2, 2], [2, 3]],\n     [[2, 1], [2, 0]],\n     [[1, 1], [2, 1]]]],\n   'invalid-edge')],\n [('regression union linkage #1',\n   [4,\n    4,\n    [[[1, 1], [1, 2]],\n     [[3, 1], [2, 1]],\n     [[0, 2], [1, 2]],\n     [[0, 0], [0, 1]],\n     [[0, 2], [0, 3]],\n     [[1, 1], [1, 0]],\n     [[1, 1], [2, 1]],\n     [[1, 0], [2, 0]],\n     [[1, 3], [1, 2]],\n     [[2, 1], [2, 0]],\n     [[3, 1], [3, 0]],\n     [[0, 0], [1, 0]],\n     [[3, 2], [3, 1]]]],\n   'loop'),\n  ('regression union linkage #2', [1, 4, [[[0, 2], [0, 3]], [[0, 2], [0, 1]], [[0, 1], [0, 0]]]], 'perfect'),\n  ('regression union linkage #3',\n   [4,\n    2,\n    [[[2, 0], [2, 1]],\n     [[1, 0], [0, 0]],\n     [[0, 1], [0, 0]],\n     [[2, 1], [1, 1]],\n     [[2, 0], [1, 0]],\n     [[1, 0], [1, 1]]]],\n   'loop'),\n  ('regression union linkage #4',\n   [3, 2, [[[1, 1], [2, 1]], [[0, 0], [1, 0]], [[2, 1], [2, 0]], [[0, 0], [0, 1]], [[1, 0], [2, 0]]]],\n   'perfect'),\n  ('single cell maze #1', [1, 1, []], 'perfect'),\n  ('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),\n  ('control #1', [2, 1, []], 'disconnected'),\n  ('control #2', [1, 2, [[[0, 0], [0, 1]]]], 'perfect')]]\nfor label, args, expected in cases[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":"4eee95538f41e26ac3b97cf47e4ffb6d2c47b0aa9793f224971c35ea3a62f78c","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(w, h, passages):\n    seen = set()\n    parent = {(x, y): (x, y) for x in range(w) for y in range(h)}\n    def find(p):\n        while parent[p] != p:\n            parent[p] = parent[parent[p]]\n            p = parent[p]\n        return p\n    for (x1, y1), (x2, y2) in passages:\n        if not (0 <= x1 < w and 0 <= y1 < h and 0 <= x2 < w and 0 <= y2 < h):\n            return 'invalid-edge'\n        if abs(x1 - x2) + abs(y1 - y2) != 1:\n            return 'invalid-edge'\n        key = tuple(sorted([(x1, y1), (x2, y2)]))\n        if key in seen:\n            return 'duplicate'\n        seen.add(key)\n    for (x1, y1), (x2, y2) in passages:\n        a, b = find((x1, y1)), find((x2, y2))\n        if a == b:\n            return 'loop'\n        parent[(x1, y1)] = (x2, y2)\n    roots = {find(p) for p in parent}\n    return 'perfect' if len(roots) == 1 else 'disconnected'\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[('regression union linkage #1',\n   [4,\n    3,\n    [[[1, 0], [1, 1]],\n     [[0, 1], [0, 0]],\n     [[0, 1], [0, 2]],\n     [[2, 0], [2, 1]],\n     [[1, 0], [0, 0]],\n     [[1, 0], [2, 0]],\n     [[2, 1], [2, 2]],\n     [[2, 2], [3, 2]],\n     [[2, 1], [3, 1]],\n     [[2, 2], [1, 2]],\n     [[1, 1], [0, 1]],\n     [[0, 2], [1, 2]]]],\n   'loop'),\n  ('regression union linkage #2',\n   [3,\n    3,\n    [[[2, 1], [2, 0]],\n     [[2, 0], [1, 0]],\n     [[0, 1], [0, 0]],\n     [[0, 1], [1, 1]],\n     [[1, 0], [1, 1]],\n     [[0, 0], [1, 0]],\n     [[0, 1], [0, 2]]]],\n   'loop'),\n  ('regression union linkage #3',\n   [4,\n    2,\n    [[[1, 0], [0, 0]],\n     [[1, 0], [1, 1]],\n     [[3, 0], [2, 0]],\n     [[2, 1], [3, 1]],\n     [[2, 1], [2, 0]],\n     [[1, 1], [2, 1]],\n     [[1, 1], [0, 1]],\n     [[3, 1], [3, 0]]]],\n   'loop'),\n  ('regression union linkage #4',\n   [4,\n    4,\n    [[[0, 0], [0, 1]],\n     [[2, 0], [3, 0]],\n     [[0, 2], [0, 1]],\n     [[1, 0], [2, 0]],\n     [[2, 1], [3, 1]],\n     [[1, 3], [2, 3]],\n     [[3, 3], [3, 2]],\n     [[0, 2], [0, 3]],\n     [[2, 1], [1, 1]],\n     [[2, 2], [2, 1]],\n     [[1, 3], [0, 3]],\n     [[1, 1], [1, 2]],\n     [[2, 0], [2, 1]],\n     [[2, 2], [2, 3]],\n     [[2, 3], [3, 3]],\n     [[1, 2], [2, 2]]]],\n   'loop'),\n  ('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),\n  ('reversed duplicate #1', [2, 1, [[[0, 0], [1, 0]], [[1, 0], [0, 0]]]], 'duplicate'),\n  ('single cell maze #1', [1, 1, []], 'perfect'),\n  ('control #1',\n   [3, 2, [[[2, 1], [1, 1]], [[0, 1], [0, 0]], [[1, 1], [2, 2]], [[0, 0], [1, 0]]]],\n   'invalid-edge')],\n [('regression union linkage #1',\n   [4,\n    2,\n    [[[1, 0], [0, 0]],\n     [[1, 0], [1, 1]],\n     [[3, 0], [2, 0]],\n     [[2, 1], [3, 1]],\n     [[2, 1], [2, 0]],\n     [[1, 1], [2, 1]],\n     [[1, 1], [0, 1]],\n     [[3, 1], [3, 0]]]],\n   'loop'),\n  ('regression union linkage #2',\n   [4,\n    4,\n    [[[0, 0], [0, 1]],\n     [[2, 0], [3, 0]],\n     [[0, 2], [0, 1]],\n     [[1, 0], [2, 0]],\n     [[2, 1], [3, 1]],\n     [[1, 3], [2, 3]],\n     [[3, 3], [3, 2]],\n     [[0, 2], [0, 3]],\n     [[2, 1], [1, 1]],\n     [[2, 2], [2, 1]],\n     [[1, 3], [0, 3]],\n     [[1, 1], [1, 2]],\n     [[2, 0], [2, 1]],\n     [[2, 2], [2, 3]],\n     [[2, 3], [3, 3]],\n     [[1, 2], [2, 2]]]],\n   'loop'),\n  ('regression union linkage #3',\n   [3, 2, [[[0, 1], [0, 0]], [[1, 1], [2, 1]], [[1, 1], [0, 1]], [[1, 0], [1, 1]], [[2, 1], [2, 0]]]],\n   'perfect'),\n  ('regression union linkage #4', [1, 3, [[[0, 1], [0, 2]], [[0, 1], [0, 0]]]], 'perfect'),\n  ('single cell maze #1', [1, 1, []], 'perfect'),\n  ('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),\n  ('control #1',\n   [3, 2, [[[2, 1], [1, 1]], [[0, 1], [0, 0]], [[1, 1], [2, 2]], [[0, 0], [1, 0]]]],\n   'invalid-edge'),\n  ('control #2',\n   [4, 1, [[[2, 0], [1, 0]], [[3, 0], [2, 0]], [[0, 0], [1, 0]], [[1, 0], [0, 0]]]],\n   'duplicate')],\n [('regression union linkage #1',\n   [3, 2, [[[0, 1], [0, 0]], [[1, 1], [2, 1]], [[1, 1], [0, 1]], [[1, 0], [1, 1]], [[2, 1], [2, 0]]]],\n   'perfect'),\n  ('regression union linkage #2', [1, 3, [[[0, 1], [0, 2]], [[0, 1], [0, 0]]]], 'perfect'),\n  ('regression union linkage #3',\n   [2, 2, [[[1, 1], [1, 0]], [[1, 1], [0, 1]], [[0, 0], [1, 0]], [[0, 1], [0, 0]]]],\n   'loop'),\n  ('regression union linkage #4',\n   [4,\n    3,\n    [[[1, 2], [0, 2]],\n     [[1, 1], [2, 1]],\n     [[3, 0], [2, 0]],\n     [[3, 1], [3, 0]],\n     [[3, 2], [3, 1]],\n     [[1, 1], [1, 0]],\n     [[2, 1], [3, 1]],\n     [[2, 1], [2, 2]],\n     [[2, 1], [2, 0]],\n     [[0, 1], [1, 1]],\n     [[0, 0], [0, 1]],\n     [[0, 2], [0, 1]],\n     [[1, 2], [2, 2]]]],\n   'loop'),\n  ('reversed duplicate #1', [2, 1, [[[0, 0], [1, 0]], [[1, 0], [0, 0]]]], 'duplicate'),\n  ('single cell maze #1', [1, 1, []], 'perfect'),\n  ('control #1',\n   [4, 1, [[[2, 0], [1, 0]], [[3, 0], [2, 0]], [[0, 0], [1, 0]], [[1, 0], [0, 0]]]],\n   'duplicate'),\n  ('control #2', [4, 1, [[[2, 0], [2, 0]], [[1, 0], [0, 0]], [[2, 0], [1, 0]]]], 'invalid-edge')],\n [('regression union linkage #1',\n   [2, 2, [[[1, 1], [1, 0]], [[1, 1], [0, 1]], [[0, 0], [1, 0]], [[0, 1], [0, 0]]]],\n   'loop'),\n  ('regression union linkage #2',\n   [4,\n    3,\n    [[[1, 2], [0, 2]],\n     [[1, 1], [2, 1]],\n     [[3, 0], [2, 0]],\n     [[3, 1], [3, 0]],\n     [[3, 2], [3, 1]],\n     [[1, 1], [1, 0]],\n     [[2, 1], [3, 1]],\n     [[2, 1], [2, 2]],\n     [[2, 1], [2, 0]],\n     [[0, 1], [1, 1]],\n     [[0, 0], [0, 1]],\n     [[0, 2], [0, 1]],\n     [[1, 2], [2, 2]]]],\n   'loop'),\n  ('regression union linkage #3',\n   [4,\n    4,\n    [[[1, 1], [1, 2]],\n     [[3, 1], [2, 1]],\n     [[0, 2], [1, 2]],\n     [[0, 0], [0, 1]],\n     [[0, 2], [0, 3]],\n     [[1, 1], [1, 0]],\n     [[1, 1], [2, 1]],\n     [[1, 0], [2, 0]],\n     [[1, 3], [1, 2]],\n     [[2, 1], [2, 0]],\n     [[3, 1], [3, 0]],\n     [[0, 0], [1, 0]],\n     [[3, 2], [3, 1]]]],\n   'loop'),\n  ('regression union linkage #4', [1, 4, [[[0, 2], [0, 3]], [[0, 2], [0, 1]], [[0, 1], [0, 0]]]], 'perfect'),\n  ('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),\n  ('reversed duplicate #1', [2, 1, [[[0, 0], [1, 0]], [[1, 0], [0, 0]]]], 'duplicate'),\n  ('control #1',\n   [3,\n    3,\n    [[[1, 0], [1, 0]],\n     [[1, 0], [2, 0]],\n     [[0, 2], [0, 1]],\n     [[2, 2], [2, 1]],\n     [[0, 2], [1, 2]],\n     [[1, 0], [0, 0]],\n     [[0, 1], [1, 1]]]],\n   'invalid-edge'),\n  ('control #2',\n   [3,\n    4,\n    [[[1, 1], [1, 1]],\n     [[1, 3], [2, 3]],\n     [[2, 2], [2, 1]],\n     [[2, 0], [1, 0]],\n     [[1, 2], [2, 2]],\n     [[1, 2], [1, 3]],\n     [[1, 2], [0, 2]],\n     [[1, 2], [1, 1]],\n     [[0, 1], [1, 1]],\n     [[2, 2], [2, 3]],\n     [[2, 1], [2, 0]],\n     [[1, 1], [2, 1]]]],\n   'invalid-edge')],\n [('regression union linkage #1',\n   [4,\n    4,\n    [[[1, 1], [1, 2]],\n     [[3, 1], [2, 1]],\n     [[0, 2], [1, 2]],\n     [[0, 0], [0, 1]],\n     [[0, 2], [0, 3]],\n     [[1, 1], [1, 0]],\n     [[1, 1], [2, 1]],\n     [[1, 0], [2, 0]],\n     [[1, 3], [1, 2]],\n     [[2, 1], [2, 0]],\n     [[3, 1], [3, 0]],\n     [[0, 0], [1, 0]],\n     [[3, 2], [3, 1]]]],\n   'loop'),\n  ('regression union linkage #2', [1, 4, [[[0, 2], [0, 3]], [[0, 2], [0, 1]], [[0, 1], [0, 0]]]], 'perfect'),\n  ('regression union linkage #3',\n   [4,\n    2,\n    [[[2, 0], [2, 1]],\n     [[1, 0], [0, 0]],\n     [[0, 1], [0, 0]],\n     [[2, 1], [1, 1]],\n     [[2, 0], [1, 0]],\n     [[1, 0], [1, 1]]]],\n   'loop'),\n  ('regression union linkage #4',\n   [3, 2, [[[1, 1], [2, 1]], [[0, 0], [1, 0]], [[2, 1], [2, 0]], [[0, 0], [0, 1]], [[1, 0], [2, 0]]]],\n   'perfect'),\n  ('single cell maze #1', [1, 1, []], 'perfect'),\n  ('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),\n  ('control #1', [2, 1, []], 'disconnected'),\n  ('control #2', [1, 2, [[[0, 0], [0, 1]]]], 'perfect')]]\nfor label, args, expected in cases[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":"39f96ebb059a040b38a5413d51bd38863a0e7f967dac921553106a9419c8f7d9","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(w, h, passages):\n    seen = set()\n    parent = {(x, y): (x, y) for x in range(w) for y in range(h)}\n    def find(p):\n        while parent[p] != p:\n            parent[p] = parent[parent[p]]\n            p = parent[p]\n        return p\n    for (x1, y1), (x2, y2) in passages:\n        if not (0 <= x1 < w and 0 <= y1 < h and 0 <= x2 < w and 0 <= y2 < h):\n            return 'invalid-edge'\n        if abs(x1 - x2) + abs(y1 - y2) != 1:\n            return 'invalid-edge'\n        key = tuple(sorted([(x1, y1), (x2, y2)]))\n        if key in seen:\n            return 'duplicate'\n        seen.add(key)\n    for (x1, y1), (x2, y2) in passages:\n        a, b = find((x1, y1)), find((x2, y2))\n        if a == b:\n            return 'loop'\n        parent[a] = b\n    roots = {find(p) for p in parent}\n    return 'perfect' if len(roots) == 1 else 'disconnected'\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[('regression union linkage #1',\n   [4,\n    3,\n    [[[1, 0], [1, 1]],\n     [[0, 1], [0, 0]],\n     [[0, 1], [0, 2]],\n     [[2, 0], [2, 1]],\n     [[1, 0], [0, 0]],\n     [[1, 0], [2, 0]],\n     [[2, 1], [2, 2]],\n     [[2, 2], [3, 2]],\n     [[2, 1], [3, 1]],\n     [[2, 2], [1, 2]],\n     [[1, 1], [0, 1]],\n     [[0, 2], [1, 2]]]],\n   'loop'),\n  ('regression union linkage #2',\n   [3,\n    3,\n    [[[2, 1], [2, 0]],\n     [[2, 0], [1, 0]],\n     [[0, 1], [0, 0]],\n     [[0, 1], [1, 1]],\n     [[1, 0], [1, 1]],\n     [[0, 0], [1, 0]],\n     [[0, 1], [0, 2]]]],\n   'loop'),\n  ('regression union linkage #3',\n   [4,\n    2,\n    [[[1, 0], [0, 0]],\n     [[1, 0], [1, 1]],\n     [[3, 0], [2, 0]],\n     [[2, 1], [3, 1]],\n     [[2, 1], [2, 0]],\n     [[1, 1], [2, 1]],\n     [[1, 1], [0, 1]],\n     [[3, 1], [3, 0]]]],\n   'loop'),\n  ('regression union linkage #4',\n   [4,\n    4,\n    [[[0, 0], [0, 1]],\n     [[2, 0], [3, 0]],\n     [[0, 2], [0, 1]],\n     [[1, 0], [2, 0]],\n     [[2, 1], [3, 1]],\n     [[1, 3], [2, 3]],\n     [[3, 3], [3, 2]],\n     [[0, 2], [0, 3]],\n     [[2, 1], [1, 1]],\n     [[2, 2], [2, 1]],\n     [[1, 3], [0, 3]],\n     [[1, 1], [1, 2]],\n     [[2, 0], [2, 1]],\n     [[2, 2], [2, 3]],\n     [[2, 3], [3, 3]],\n     [[1, 2], [2, 2]]]],\n   'loop'),\n  ('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),\n  ('reversed duplicate #1', [2, 1, [[[0, 0], [1, 0]], [[1, 0], [0, 0]]]], 'duplicate'),\n  ('single cell maze #1', [1, 1, []], 'perfect'),\n  ('control #1',\n   [3, 2, [[[2, 1], [1, 1]], [[0, 1], [0, 0]], [[1, 1], [2, 2]], [[0, 0], [1, 0]]]],\n   'invalid-edge')],\n [('regression union linkage #1',\n   [4,\n    2,\n    [[[1, 0], [0, 0]],\n     [[1, 0], [1, 1]],\n     [[3, 0], [2, 0]],\n     [[2, 1], [3, 1]],\n     [[2, 1], [2, 0]],\n     [[1, 1], [2, 1]],\n     [[1, 1], [0, 1]],\n     [[3, 1], [3, 0]]]],\n   'loop'),\n  ('regression union linkage #2',\n   [4,\n    4,\n    [[[0, 0], [0, 1]],\n     [[2, 0], [3, 0]],\n     [[0, 2], [0, 1]],\n     [[1, 0], [2, 0]],\n     [[2, 1], [3, 1]],\n     [[1, 3], [2, 3]],\n     [[3, 3], [3, 2]],\n     [[0, 2], [0, 3]],\n     [[2, 1], [1, 1]],\n     [[2, 2], [2, 1]],\n     [[1, 3], [0, 3]],\n     [[1, 1], [1, 2]],\n     [[2, 0], [2, 1]],\n     [[2, 2], [2, 3]],\n     [[2, 3], [3, 3]],\n     [[1, 2], [2, 2]]]],\n   'loop'),\n  ('regression union linkage #3',\n   [3, 2, [[[0, 1], [0, 0]], [[1, 1], [2, 1]], [[1, 1], [0, 1]], [[1, 0], [1, 1]], [[2, 1], [2, 0]]]],\n   'perfect'),\n  ('regression union linkage #4', [1, 3, [[[0, 1], [0, 2]], [[0, 1], [0, 0]]]], 'perfect'),\n  ('single cell maze #1', [1, 1, []], 'perfect'),\n  ('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),\n  ('control #1',\n   [3, 2, [[[2, 1], [1, 1]], [[0, 1], [0, 0]], [[1, 1], [2, 2]], [[0, 0], [1, 0]]]],\n   'invalid-edge'),\n  ('control #2',\n   [4, 1, [[[2, 0], [1, 0]], [[3, 0], [2, 0]], [[0, 0], [1, 0]], [[1, 0], [0, 0]]]],\n   'duplicate')],\n [('regression union linkage #1',\n   [3, 2, [[[0, 1], [0, 0]], [[1, 1], [2, 1]], [[1, 1], [0, 1]], [[1, 0], [1, 1]], [[2, 1], [2, 0]]]],\n   'perfect'),\n  ('regression union linkage #2', [1, 3, [[[0, 1], [0, 2]], [[0, 1], [0, 0]]]], 'perfect'),\n  ('regression union linkage #3',\n   [2, 2, [[[1, 1], [1, 0]], [[1, 1], [0, 1]], [[0, 0], [1, 0]], [[0, 1], [0, 0]]]],\n   'loop'),\n  ('regression union linkage #4',\n   [4,\n    3,\n    [[[1, 2], [0, 2]],\n     [[1, 1], [2, 1]],\n     [[3, 0], [2, 0]],\n     [[3, 1], [3, 0]],\n     [[3, 2], [3, 1]],\n     [[1, 1], [1, 0]],\n     [[2, 1], [3, 1]],\n     [[2, 1], [2, 2]],\n     [[2, 1], [2, 0]],\n     [[0, 1], [1, 1]],\n     [[0, 0], [0, 1]],\n     [[0, 2], [0, 1]],\n     [[1, 2], [2, 2]]]],\n   'loop'),\n  ('reversed duplicate #1', [2, 1, [[[0, 0], [1, 0]], [[1, 0], [0, 0]]]], 'duplicate'),\n  ('single cell maze #1', [1, 1, []], 'perfect'),\n  ('control #1',\n   [4, 1, [[[2, 0], [1, 0]], [[3, 0], [2, 0]], [[0, 0], [1, 0]], [[1, 0], [0, 0]]]],\n   'duplicate'),\n  ('control #2', [4, 1, [[[2, 0], [2, 0]], [[1, 0], [0, 0]], [[2, 0], [1, 0]]]], 'invalid-edge')],\n [('regression union linkage #1',\n   [2, 2, [[[1, 1], [1, 0]], [[1, 1], [0, 1]], [[0, 0], [1, 0]], [[0, 1], [0, 0]]]],\n   'loop'),\n  ('regression union linkage #2',\n   [4,\n    3,\n    [[[1, 2], [0, 2]],\n     [[1, 1], [2, 1]],\n     [[3, 0], [2, 0]],\n     [[3, 1], [3, 0]],\n     [[3, 2], [3, 1]],\n     [[1, 1], [1, 0]],\n     [[2, 1], [3, 1]],\n     [[2, 1], [2, 2]],\n     [[2, 1], [2, 0]],\n     [[0, 1], [1, 1]],\n     [[0, 0], [0, 1]],\n     [[0, 2], [0, 1]],\n     [[1, 2], [2, 2]]]],\n   'loop'),\n  ('regression union linkage #3',\n   [4,\n    4,\n    [[[1, 1], [1, 2]],\n     [[3, 1], [2, 1]],\n     [[0, 2], [1, 2]],\n     [[0, 0], [0, 1]],\n     [[0, 2], [0, 3]],\n     [[1, 1], [1, 0]],\n     [[1, 1], [2, 1]],\n     [[1, 0], [2, 0]],\n     [[1, 3], [1, 2]],\n     [[2, 1], [2, 0]],\n     [[3, 1], [3, 0]],\n     [[0, 0], [1, 0]],\n     [[3, 2], [3, 1]]]],\n   'loop'),\n  ('regression union linkage #4', [1, 4, [[[0, 2], [0, 3]], [[0, 2], [0, 1]], [[0, 1], [0, 0]]]], 'perfect'),\n  ('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),\n  ('reversed duplicate #1', [2, 1, [[[0, 0], [1, 0]], [[1, 0], [0, 0]]]], 'duplicate'),\n  ('control #1',\n   [3,\n    3,\n    [[[1, 0], [1, 0]],\n     [[1, 0], [2, 0]],\n     [[0, 2], [0, 1]],\n     [[2, 2], [2, 1]],\n     [[0, 2], [1, 2]],\n     [[1, 0], [0, 0]],\n     [[0, 1], [1, 1]]]],\n   'invalid-edge'),\n  ('control #2',\n   [3,\n    4,\n    [[[1, 1], [1, 1]],\n     [[1, 3], [2, 3]],\n     [[2, 2], [2, 1]],\n     [[2, 0], [1, 0]],\n     [[1, 2], [2, 2]],\n     [[1, 2], [1, 3]],\n     [[1, 2], [0, 2]],\n     [[1, 2], [1, 1]],\n     [[0, 1], [1, 1]],\n     [[2, 2], [2, 3]],\n     [[2, 1], [2, 0]],\n     [[1, 1], [2, 1]]]],\n   'invalid-edge')],\n [('regression union linkage #1',\n   [4,\n    4,\n    [[[1, 1], [1, 2]],\n     [[3, 1], [2, 1]],\n     [[0, 2], [1, 2]],\n     [[0, 0], [0, 1]],\n     [[0, 2], [0, 3]],\n     [[1, 1], [1, 0]],\n     [[1, 1], [2, 1]],\n     [[1, 0], [2, 0]],\n     [[1, 3], [1, 2]],\n     [[2, 1], [2, 0]],\n     [[3, 1], [3, 0]],\n     [[0, 0], [1, 0]],\n     [[3, 2], [3, 1]]]],\n   'loop'),\n  ('regression union linkage #2', [1, 4, [[[0, 2], [0, 3]], [[0, 2], [0, 1]], [[0, 1], [0, 0]]]], 'perfect'),\n  ('regression union linkage #3',\n   [4,\n    2,\n    [[[2, 0], [2, 1]],\n     [[1, 0], [0, 0]],\n     [[0, 1], [0, 0]],\n     [[2, 1], [1, 1]],\n     [[2, 0], [1, 0]],\n     [[1, 0], [1, 1]]]],\n   'loop'),\n  ('regression union linkage #4',\n   [3, 2, [[[1, 1], [2, 1]], [[0, 0], [1, 0]], [[2, 1], [2, 0]], [[0, 0], [0, 1]], [[1, 0], [2, 0]]]],\n   'perfect'),\n  ('single cell maze #1', [1, 1, []], 'perfect'),\n  ('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),\n  ('control #1', [2, 1, []], 'disconnected'),\n  ('control #2', [1, 2, [[[0, 0], [0, 1]]]], 'perfect')]]\nfor label, args, expected in cases[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":"Deterministic toy contract stipulated for this model; integer or exact arithmetic only, not a reproduction of any specific game engine. 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-procedural-level-generation-constraints-perfect-maze-union-linkage","generated_at":"2026-09-29T14:50:51.414989+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"Procedural generators silently emit unplayable or unfair levels when a single constraint check uses the wrong boundary, axis, neighborhood or update order; the defect is visible in exact generated geometry.","repair":"Restore `parent[a] = b` at the union linkage step.","root_cause":"The union step re-parents the endpoint cell instead of its root.","sha256":"89bb088cc63991bb2d37b7bfb4269c87ca76d8bef3c32078124f71305a215b9a","title":"Perfect maze validator: Union links cells instead of roots · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verification":{"attempt":{"elapsed_ms":44.306,"exit_code":1,"observations":[{"actual":"disconnected","check":"regression union linkage #1","expected":"loop","passed":false},{"actual":"disconnected","check":"regression union linkage #2","expected":"loop","passed":false},{"actual":"disconnected","check":"regression union linkage #3","expected":"loop","passed":false},{"actual":"disconnected","check":"regression union linkage #4","expected":"loop","passed":false},{"actual":"invalid-edge","check":"diagonal passage #1","expected":"invalid-edge","passed":true},{"actual":"duplicate","check":"reversed duplicate #1","expected":"duplicate","passed":true},{"actual":"perfect","check":"single cell maze #1","expected":"perfect","passed":true},{"actual":"invalid-edge","check":"control #1","expected":"invalid-edge","passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"regression union linkage #1\", \"actual\": \"disconnected\", \"expected\": \"loop\", \"passed\": false}, {\"check\": \"regression union linkage #2\", \"actual\": \"disconnected\", \"expected\": \"loop\", \"passed\": false}, {\"check\": \"regression union linkage #3\", \"actual\": \"disconnected\", \"expected\": \"loop\", \"passed\": false}, {\"check\": \"regression union linkage #4\", \"actual\": \"disconnected\", \"expected\": \"loop\", \"passed\": false}, {\"check\": \"diagonal passage #1\", \"actual\": \"invalid-edge\", \"expected\": \"invalid-edge\", \"passed\": true}, {\"check\": \"reversed duplicate #1\", \"actual\": \"duplicate\", \"expected\": \"duplicate\", \"passed\": true}, {\"check\": \"single cell maze #1\", \"actual\": \"perfect\", \"expected\": \"perfect\", \"passed\": true}, {\"check\": \"control #1\", \"actual\": \"invalid-edge\", \"expected\": \"invalid-edge\", \"passed\": true}], \"passed\": false}\n"},"broken":{"elapsed_ms":42.927,"exit_code":1,"observations":[{"actual":"disconnected","check":"regression union linkage #1","expected":"loop","passed":false},{"actual":"disconnected","check":"regression union linkage #2","expected":"loop","passed":false},{"actual":"disconnected","check":"regression union linkage #3","expected":"loop","passed":false},{"actual":"disconnected","check":"regression union linkage #4","expected":"loop","passed":false},{"actual":"invalid-edge","check":"diagonal passage #1","expected":"invalid-edge","passed":true},{"actual":"duplicate","check":"reversed duplicate #1","expected":"duplicate","passed":true},{"actual":"perfect","check":"single cell maze #1","expected":"perfect","passed":true},{"actual":"invalid-edge","check":"control #1","expected":"invalid-edge","passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"regression union linkage #1\", \"actual\": \"disconnected\", \"expected\": \"loop\", \"passed\": false}, {\"check\": \"regression union linkage #2\", \"actual\": \"disconnected\", \"expected\": \"loop\", \"passed\": false}, {\"check\": \"regression union linkage #3\", \"actual\": \"disconnected\", \"expected\": \"loop\", \"passed\": false}, {\"check\": \"regression union linkage #4\", \"actual\": \"disconnected\", \"expected\": \"loop\", \"passed\": false}, {\"check\": \"diagonal passage #1\", \"actual\": \"invalid-edge\", \"expected\": \"invalid-edge\", \"passed\": true}, {\"check\": \"reversed duplicate #1\", \"actual\": \"duplicate\", \"expected\": \"duplicate\", \"passed\": true}, {\"check\": \"single cell maze #1\", \"actual\": \"perfect\", \"expected\": \"perfect\", \"passed\": true}, {\"check\": \"control #1\", \"actual\": \"invalid-edge\", \"expected\": \"invalid-edge\", \"passed\": true}], \"passed\": false}\n"},"fixed":{"elapsed_ms":40.521,"exit_code":0,"observations":[{"actual":"loop","check":"regression union linkage #1","expected":"loop","passed":true},{"actual":"loop","check":"regression union linkage #2","expected":"loop","passed":true},{"actual":"loop","check":"regression union linkage #3","expected":"loop","passed":true},{"actual":"loop","check":"regression union linkage #4","expected":"loop","passed":true},{"actual":"invalid-edge","check":"diagonal passage #1","expected":"invalid-edge","passed":true},{"actual":"duplicate","check":"reversed duplicate #1","expected":"duplicate","passed":true},{"actual":"perfect","check":"single cell maze #1","expected":"perfect","passed":true},{"actual":"invalid-edge","check":"control #1","expected":"invalid-edge","passed":true}],"passed":true,"stderr":"","stdout":"{\"observations\": [{\"check\": \"regression union linkage #1\", \"actual\": \"loop\", \"expected\": \"loop\", \"passed\": true}, {\"check\": \"regression union linkage #2\", \"actual\": \"loop\", \"expected\": \"loop\", \"passed\": true}, {\"check\": \"regression union linkage #3\", \"actual\": \"loop\", \"expected\": \"loop\", \"passed\": true}, {\"check\": \"regression union linkage #4\", \"actual\": \"loop\", \"expected\": \"loop\", \"passed\": true}, {\"check\": \"diagonal passage #1\", \"actual\": \"invalid-edge\", \"expected\": \"invalid-edge\", \"passed\": true}, {\"check\": \"reversed duplicate #1\", \"actual\": \"duplicate\", \"expected\": \"duplicate\", \"passed\": true}, {\"check\": \"single cell maze #1\", \"actual\": \"perfect\", \"expected\": \"perfect\", \"passed\": true}, {\"check\": \"control #1\", \"actual\": \"invalid-edge\", \"expected\": \"invalid-edge\", \"passed\": true}], \"passed\": true}\n"}},"verified":true,"visibility":"public"}