cover

cover.py

# This solver covers a rectangular grid of '.' and 'X' with two non-rotatable tiles:
#   • A (U-shape): on row i it occupies (i,j) and (i,j+3), and on row i+1 it occupies (i+1, j..j+3).
#   • B (horizontal domino): occupies (i,j) and (i,j+1) on the same row.
# We scan left→right, row→row using top-down DP with memoization. The DP state is
# (i, j, needA, anchors):
#   – i, j: current row and column being decided.
#   – needA: tuple[bool] of length W marking cells in the CURRENT row that are forced to 'A'
#            because they are the bottom strip of some A placed in the PREVIOUS row.
#   – anchors: tuple of columns where we have already anchored an A in the CURRENT row before j;
#              each anchor at column a also forces (i, a+3) to be 'A' (its top-right leg) and
#              reserves bottom cells (i+1, a..a+3) for the next row.
# Transition at cell (i,j):
#   – If '.', it must stay '.' and cannot be occupied by any 'A' leg; move to j+1.
#   – If 'X' but already forced to 'A' (by needA or because it’s a right-top leg from anchors),
#     write 'A' and move to j+1.
#   – Otherwise try placing A anchored at j (if legal), ELSE try placing B covering (j, j+1).
#     We always try A before B so the first successful path is lexicographically minimal
#     (since 'A' < 'B' in the output strings).
# At end of row, we convert current row’s anchors into next row’s needA by setting True on
# columns a..a+3 for each anchor a, then recurse to the next row.
# The DP memoizes by (i, j, needA, anchors), so each subproblem is solved once.
#
# Complexity (informal but tight enough for practice):
#   Let H×W be the grid. For a fixed row, valid A-anchors must be ≥4 apart and also satisfy
#   strong “X” availability constraints (two X corners on row i and four X below on row i+1).
#   The number of feasible anchor subsets along a row of length W is upper-bounded by a
#   Fibonacci-like recurrence f(W) = f(W-1) + f(W-4) (place/no-place with a 4-cell exclusion),
#   so worst-case states per row are O(f(W)). With memoization over (i, j, needA, anchors),
#   the total time is roughly O(H · W · f(W)) with O(H · f(W)) memory for cached states.

from functools import lru_cache
from time import perf_counter

class SpecificPolyominoCovering:
    @staticmethod
    def _right_tops(anchors):
        # Cells in the current row that are forced to 'A' as the top-right legs of already-placed A's
        return {a + 3 for a in anchors}

    # ---- A tile helpers ----
    def can_place_A(self, i, j, needA, anchors):
        H, W, g = self.H, self.W, self.g
        if i + 1 >= H or j + 3 >= W:
            return False
        # top corners must be 'X'
        if g[i][j] != 'X' or g[i][j + 3] != 'X':
            return False
        # bottom strip must be all 'X' on next row
        for c in range(j, j + 4):
            if g[i + 1][c] != 'X':
                return False
        # cannot collide with already forced 'A' in current row
        rt = self._right_tops(anchors)
        if needA[j] or (j in rt):
            return False
        if needA[j + 3] or ((j + 3) in rt):
            return False
        # A bottoms from different anchors in same row cannot overlap → anchors ≥ 4 apart
        for a in anchors:
            if abs(a - j) < 4:
                return False
        return True

    def place_A(self, anchors, j):
        return anchors + (j,)

    def unplace_A(self, anchors, j):
        # Immutable state; included for symmetry / readability
        if anchors and anchors[-1] == j:
            return anchors[:-1]
        return anchors

    # ---- B tile helpers ----
    def can_place_B(self, i, j, needA, anchors):
        H, W, g = self.H, self.W, self.g
        if j + 1 >= W:
            return False
        if g[i][j] != 'X' or g[i][j + 1] != 'X':
            return False
        rt = self._right_tops(anchors)
        # Neither endpoint may already be forced to 'A'
        if needA[j] or needA[j + 1] or (j in rt) or ((j + 1) in rt):
            return False
        return True

    def place_B(self, j):
        return j + 2

    def unplace_B(self):
        return

    # ---- Core DP ----
    def findCovering(self, region):
        self.H = len(region)
        self.W = len(region[0])
        self.g = [list(r) for r in region]  # work on char grid

        @lru_cache(maxsize=None)
        def dp(i: int, j: int, needA: tuple, anchors: tuple):
            # Finished all rows: success only if no pending obligations
            if i == self.H:
                return () if (not anchors and all(x is False for x in needA)) else None

            # End of row: convert anchors → next row's needA
            if j == self.W:
                next_need = [False] * self.W
                for a in anchors:
                    for c in range(a, a + 4):
                        next_need[c] = True
                tail = dp(i + 1, 0, tuple(next_need), ())
                return None if tail is None else ("",) + tail  # prepend empty suffix for this row

            cell = self.g[i][j]
            rt = self._right_tops(anchors)

            # '.' must remain '.'; cannot be occupied by A
            if cell == '.':
                if needA[j] or (j in rt):
                    return None
                tail = dp(i, j + 1, needA, anchors)
                return None if tail is None else ("." + tail[0],) + tail[1:]

            # cell == 'X'
            # Already forced 'A' here?
            if needA[j] or (j in rt):
                tail = dp(i, j + 1, needA, anchors)
                return None if tail is None else ("A" + tail[0],) + tail[1:]

            # Try 'A' first (lexicographic minimality)
            if self.can_place_A(i, j, needA, anchors):
                new_anchors = self.place_A(anchors, j)
                tail = dp(i, j + 1, needA, new_anchors)
                if tail is not None:
                    return ("A" + tail[0],) + tail[1:]
                _ = self.unplace_A(new_anchors, j)  # no-op in immutable style

            # Try 'B'
            if self.can_place_B(i, j, needA, anchors):
                j2 = self.place_B(j)
                tail = dp(i, j2, needA, anchors)
                if tail is not None:
                    return ("BB" + tail[0],) + tail[1:]
                self.unplace_B()

            # No valid placement
            return None

        ans = dp(0, 0, tuple([False] * self.W), ())
        return list(ans) if ans is not None else []


# ---- quick demo on first 3 official examples ----
if __name__ == "__main__":
    examples = [
        ["XXXX", "XXXX"],
        ["X..XXXX..X", "XXXX..XXXX"],
        ["XXXXXX", "XXXXXX", "XXXXXX"],
    ]
    expected = [
        ["ABBA", "AAAA"],
        ["A..ABBA..A", "AAAA..AAAA"],
        ["ABBABB", "AAAABB", "BBBBBB"],
    ]

    solver = SpecificPolyominoCovering()
    for idx, region in enumerate(examples, 1):
        out = solver.findCovering(region)
        print(f"Example {idx}")
        print("Input:")
        for r in region:
            print(" ", r)
        print("Output:")
        for r in out:
            print(" ", r)
        print("Matches expected:", out == expected[idx - 1])
        print("-" * 40)

    # Large example to show performance
    H, W = 20, 50
    large_region = ["X" * W for _ in range(H)]
    t0 = perf_counter()
    large_out = solver.findCovering(large_region)
    t1 = perf_counter()
    print(f"Large example {H}x{W}: solved in {(t1 - t0)*1000:.1f} ms")
    print("Preview:", large_out[0][:20], "...")