{"abstract":"Fully connected mazes are reported 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'.","contract_signature":"w, h, passages","evaluation_group":"w2-procedural-level-generation-constraints-perfect-maze","failed_approach":"Skipping self-parented cells misses isolated cells.","family":"w2-procedural-level-generation-constraints-perfect-maze-component-roots","id":"FA-86636","implementations":{"attempt":{"sha256":"627b4d52a16d29e2e5426b0dccf36d7fb02b1186058a6ee1d747affb52a0c6d0","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 if parent[p] != p}\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 = [[('single cell maze #1', [1, 1, []], 'perfect'),\n  ('fault site component roots #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  ('fault site component roots #2', [3, 1, [[[0, 0], [1, 0]], [[1, 0], [2, 0]]]], 'perfect'),\n  ('partial repair boundary #1', [1, 3, [[[0, 1], [0, 2]]]], 'disconnected'),\n  ('partial repair boundary #2',\n   [4,\n    2,\n    [[[2, 1], [2, 0]],\n     [[1, 1], [2, 1]],\n     [[1, 1], [0, 1]],\n     [[2, 0], [1, 0]],\n     [[2, 1], [3, 1]],\n     [[3, 0], [3, 1]]]],\n   'disconnected'),\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, 2, [[[2, 1], [1, 1]], [[0, 1], [0, 0]], [[1, 1], [2, 2]], [[0, 0], [1, 0]]]],\n   'invalid-edge')],\n [('single cell maze #1', [1, 1, []], 'perfect'),\n  ('fault site component roots #1',\n   [2, 2, [[[0, 0], [0, 1]], [[0, 1], [1, 1]], [[1, 1], [1, 0]]]],\n   'perfect'),\n  ('fault site component roots #2', [1, 3, [[[0, 1], [0, 2]], [[0, 1], [0, 0]]]], 'perfect'),\n  ('partial repair boundary #1',\n   [4,\n    2,\n    [[[2, 1], [2, 0]],\n     [[1, 1], [2, 1]],\n     [[1, 1], [0, 1]],\n     [[2, 0], [1, 0]],\n     [[2, 1], [3, 1]],\n     [[3, 0], [3, 1]]]],\n   'disconnected'),\n  ('partial repair boundary #2',\n   [4, 2, [[[2, 1], [1, 1]], [[1, 0], [0, 0]], [[2, 1], [2, 0]], [[1, 0], [1, 1]]]],\n   'disconnected'),\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, 2, [[[2, 1], [1, 1]], [[0, 1], [0, 0]], [[1, 1], [2, 2]], [[0, 0], [1, 0]]]],\n   'invalid-edge')],\n [('single cell maze #1', [1, 1, []], 'perfect'),\n  ('fault site component roots #1',\n   [1, 4, [[[0, 2], [0, 3]], [[0, 2], [0, 1]], [[0, 1], [0, 0]]]],\n   'perfect'),\n  ('fault site component roots #2',\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  ('partial repair boundary #1', [3, 1, [[[0, 0], [1, 0]]]], 'disconnected'),\n  ('partial repair boundary #2',\n   [3,\n    4,\n    [[[2, 0], [1, 0]],\n     [[1, 2], [1, 1]],\n     [[2, 2], [2, 3]],\n     [[2, 2], [2, 1]],\n     [[1, 0], [1, 1]],\n     [[1, 1], [2, 1]],\n     [[1, 0], [0, 0]],\n     [[1, 3], [1, 2]],\n     [[0, 2], [0, 1]],\n     [[1, 2], [0, 2]]]],\n   'disconnected'),\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, 2, [[[2, 1], [1, 1]], [[0, 1], [0, 0]], [[1, 1], [2, 2]], [[0, 0], [1, 0]]]],\n   'invalid-edge')],\n [('single cell maze #1', [1, 1, []], 'perfect'),\n  ('fault site component roots #1',\n   [2,\n    4,\n    [[[0, 0], [1, 0]],\n     [[0, 2], [0, 1]],\n     [[1, 2], [1, 3]],\n     [[1, 2], [0, 2]],\n     [[0, 3], [1, 3]],\n     [[1, 0], [1, 1]],\n     [[1, 1], [0, 1]]]],\n   'perfect'),\n  ('fault site component roots #2',\n   [2, 3, [[[0, 2], [0, 1]], [[0, 0], [0, 1]], [[1, 1], [1, 0]], [[1, 2], [0, 2]], [[0, 0], [1, 0]]]],\n   'perfect'),\n  ('partial repair boundary #1', [1, 3, [[[0, 1], [0, 0]]]], 'disconnected'),\n  ('partial repair boundary #2', [1, 3, [[[0, 2], [0, 1]]]], 'disconnected'),\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   [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 [('single cell maze #1', [1, 1, []], 'perfect'),\n  ('fault site component roots #1',\n   [1, 4, [[[0, 0], [0, 1]], [[0, 1], [0, 2]], [[0, 2], [0, 3]]]],\n   'perfect'),\n  ('fault site component roots #2',\n   [4,\n    2,\n    [[[1, 0], [1, 1]],\n     [[0, 0], [0, 1]],\n     [[3, 1], [3, 0]],\n     [[3, 1], [2, 1]],\n     [[1, 1], [0, 1]],\n     [[2, 0], [3, 0]],\n     [[2, 1], [1, 1]]]],\n   'perfect'),\n  ('partial repair boundary #1', [2, 3, [[[0, 1], [0, 0]], [[0, 1], [0, 2]]]], 'disconnected'),\n  ('partial repair boundary #2', [4, 1, [[[3, 0], [2, 0]], [[1, 0], [2, 0]]]], 'disconnected'),\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   [4, 1, [[[2, 0], [1, 0]], [[3, 0], [2, 0]], [[0, 0], [1, 0]], [[1, 0], [0, 0]]]],\n   'duplicate')]]\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":"bfffe05d4e63e6937d78ee22866d800113b6e04a0d66e485228665911a0e5918","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 = {parent[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 = [[('single cell maze #1', [1, 1, []], 'perfect'),\n  ('fault site component roots #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  ('fault site component roots #2', [3, 1, [[[0, 0], [1, 0]], [[1, 0], [2, 0]]]], 'perfect'),\n  ('partial repair boundary #1', [1, 3, [[[0, 1], [0, 2]]]], 'disconnected'),\n  ('partial repair boundary #2',\n   [4,\n    2,\n    [[[2, 1], [2, 0]],\n     [[1, 1], [2, 1]],\n     [[1, 1], [0, 1]],\n     [[2, 0], [1, 0]],\n     [[2, 1], [3, 1]],\n     [[3, 0], [3, 1]]]],\n   'disconnected'),\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, 2, [[[2, 1], [1, 1]], [[0, 1], [0, 0]], [[1, 1], [2, 2]], [[0, 0], [1, 0]]]],\n   'invalid-edge')],\n [('single cell maze #1', [1, 1, []], 'perfect'),\n  ('fault site component roots #1',\n   [2, 2, [[[0, 0], [0, 1]], [[0, 1], [1, 1]], [[1, 1], [1, 0]]]],\n   'perfect'),\n  ('fault site component roots #2', [1, 3, [[[0, 1], [0, 2]], [[0, 1], [0, 0]]]], 'perfect'),\n  ('partial repair boundary #1',\n   [4,\n    2,\n    [[[2, 1], [2, 0]],\n     [[1, 1], [2, 1]],\n     [[1, 1], [0, 1]],\n     [[2, 0], [1, 0]],\n     [[2, 1], [3, 1]],\n     [[3, 0], [3, 1]]]],\n   'disconnected'),\n  ('partial repair boundary #2',\n   [4, 2, [[[2, 1], [1, 1]], [[1, 0], [0, 0]], [[2, 1], [2, 0]], [[1, 0], [1, 1]]]],\n   'disconnected'),\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, 2, [[[2, 1], [1, 1]], [[0, 1], [0, 0]], [[1, 1], [2, 2]], [[0, 0], [1, 0]]]],\n   'invalid-edge')],\n [('single cell maze #1', [1, 1, []], 'perfect'),\n  ('fault site component roots #1',\n   [1, 4, [[[0, 2], [0, 3]], [[0, 2], [0, 1]], [[0, 1], [0, 0]]]],\n   'perfect'),\n  ('fault site component roots #2',\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  ('partial repair boundary #1', [3, 1, [[[0, 0], [1, 0]]]], 'disconnected'),\n  ('partial repair boundary #2',\n   [3,\n    4,\n    [[[2, 0], [1, 0]],\n     [[1, 2], [1, 1]],\n     [[2, 2], [2, 3]],\n     [[2, 2], [2, 1]],\n     [[1, 0], [1, 1]],\n     [[1, 1], [2, 1]],\n     [[1, 0], [0, 0]],\n     [[1, 3], [1, 2]],\n     [[0, 2], [0, 1]],\n     [[1, 2], [0, 2]]]],\n   'disconnected'),\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, 2, [[[2, 1], [1, 1]], [[0, 1], [0, 0]], [[1, 1], [2, 2]], [[0, 0], [1, 0]]]],\n   'invalid-edge')],\n [('single cell maze #1', [1, 1, []], 'perfect'),\n  ('fault site component roots #1',\n   [2,\n    4,\n    [[[0, 0], [1, 0]],\n     [[0, 2], [0, 1]],\n     [[1, 2], [1, 3]],\n     [[1, 2], [0, 2]],\n     [[0, 3], [1, 3]],\n     [[1, 0], [1, 1]],\n     [[1, 1], [0, 1]]]],\n   'perfect'),\n  ('fault site component roots #2',\n   [2, 3, [[[0, 2], [0, 1]], [[0, 0], [0, 1]], [[1, 1], [1, 0]], [[1, 2], [0, 2]], [[0, 0], [1, 0]]]],\n   'perfect'),\n  ('partial repair boundary #1', [1, 3, [[[0, 1], [0, 0]]]], 'disconnected'),\n  ('partial repair boundary #2', [1, 3, [[[0, 2], [0, 1]]]], 'disconnected'),\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   [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 [('single cell maze #1', [1, 1, []], 'perfect'),\n  ('fault site component roots #1',\n   [1, 4, [[[0, 0], [0, 1]], [[0, 1], [0, 2]], [[0, 2], [0, 3]]]],\n   'perfect'),\n  ('fault site component roots #2',\n   [4,\n    2,\n    [[[1, 0], [1, 1]],\n     [[0, 0], [0, 1]],\n     [[3, 1], [3, 0]],\n     [[3, 1], [2, 1]],\n     [[1, 1], [0, 1]],\n     [[2, 0], [3, 0]],\n     [[2, 1], [1, 1]]]],\n   'perfect'),\n  ('partial repair boundary #1', [2, 3, [[[0, 1], [0, 0]], [[0, 1], [0, 2]]]], 'disconnected'),\n  ('partial repair boundary #2', [4, 1, [[[3, 0], [2, 0]], [[1, 0], [2, 0]]]], 'disconnected'),\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   [4, 1, [[[2, 0], [1, 0]], [[3, 0], [2, 0]], [[0, 0], [1, 0]], [[1, 0], [0, 0]]]],\n   'duplicate')]]\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-component-roots","generated_at":"2026-09-29T14:50:51.413138+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.","root_cause":"Components are counted from raw parent pointers.","sha256":"82e2d46cd0857f8d7c4139297cc84d754c064918a21072e9ec3d439f7a5d39be","title":"Perfect maze validator: Uncompressed parents counted as roots · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verified":true,"visibility":"public","verification":{"attempt":{"elapsed_ms":42.447,"exit_code":1,"observations":[{"actual":"disconnected","check":"single cell maze #1","expected":"perfect","passed":false},{"actual":"perfect","check":"fault site component roots #1","expected":"perfect","passed":true},{"actual":"perfect","check":"fault site component roots #2","expected":"perfect","passed":true},{"actual":"perfect","check":"partial repair boundary #1","expected":"disconnected","passed":false},{"actual":"perfect","check":"partial repair boundary #2","expected":"disconnected","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":"invalid-edge","check":"control #1","expected":"invalid-edge","passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"single cell maze #1\", \"actual\": \"disconnected\", \"expected\": \"perfect\", \"passed\": false}, {\"check\": \"fault site component roots #1\", \"actual\": \"perfect\", \"expected\": \"perfect\", \"passed\": true}, {\"check\": \"fault site component roots #2\", \"actual\": \"perfect\", \"expected\": \"perfect\", \"passed\": true}, {\"check\": \"partial repair boundary #1\", \"actual\": \"perfect\", \"expected\": \"disconnected\", \"passed\": false}, {\"check\": \"partial repair boundary #2\", \"actual\": \"perfect\", \"expected\": \"disconnected\", \"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\": \"control #1\", \"actual\": \"invalid-edge\", \"expected\": \"invalid-edge\", \"passed\": true}], \"passed\": false}\n"},"broken":{"elapsed_ms":41.311,"exit_code":1,"observations":[{"actual":"perfect","check":"single cell maze #1","expected":"perfect","passed":true},{"actual":"disconnected","check":"fault site component roots #1","expected":"perfect","passed":false},{"actual":"disconnected","check":"fault site component roots #2","expected":"perfect","passed":false},{"actual":"disconnected","check":"partial repair boundary #1","expected":"disconnected","passed":true},{"actual":"disconnected","check":"partial repair boundary #2","expected":"disconnected","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":"invalid-edge","check":"control #1","expected":"invalid-edge","passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"single cell maze #1\", \"actual\": \"perfect\", \"expected\": \"perfect\", \"passed\": true}, {\"check\": \"fault site component roots #1\", \"actual\": \"disconnected\", \"expected\": \"perfect\", \"passed\": false}, {\"check\": \"fault site component roots #2\", \"actual\": \"disconnected\", \"expected\": \"perfect\", \"passed\": false}, {\"check\": \"partial repair boundary #1\", \"actual\": \"disconnected\", \"expected\": \"disconnected\", \"passed\": true}, {\"check\": \"partial repair boundary #2\", \"actual\": \"disconnected\", \"expected\": \"disconnected\", \"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\": \"control #1\", \"actual\": \"invalid-edge\", \"expected\": \"invalid-edge\", \"passed\": true}], \"passed\": false}\n"}},"member_only":{"stages":["fixed"],"fields":["implementations.fixed","verification.fixed","harness","repair"],"note":"The verified repair, its recorded checks, the repair description, and the scoring harness are available to members."}}