Lichen on the north wall

A conservation survey has photographed a barn wall block by block. Two patches in opposite corners may count as one shape, so how many shapes are there really?

The problem

The north wall is recorded as a rectangular grid of blocks. A block holds 1 if lichen covers it and 0 if it is bare. A patch is a maximal group of lichen blocks joined edge to edge — up, down, left or right; blocks meeting only at a corner are different patches.

The survey wants the number of distinct patch shapes. Two patches share a shape when one slides onto the other: sliding is free, turning and flipping are not. The same L in the top corner and the bottom corner is one shape; an L and its mirror image are two.

Input. wall — a list of lists of integers, each 0 or 1, every row the same length.

Output. How many distinct shapes appear, counting each once however often it occurs.

Example.

wall = [[1, 1, 0, 0, 0],
        [1, 1, 0, 0, 0],
        [0, 0, 0, 1, 1],
        [0, 0, 0, 1, 1]]   ->  1

Two square patches of four blocks. They sit three columns apart, but one slides onto the other exactly, so the survey records one shape.

A second example, where mirror images must be kept apart:

wall = [[1, 1, 0, 1, 1],
        [1, 0, 0, 0, 1],
        [0, 0, 0, 0, 0],
        [1, 1, 0, 1, 1],
        [0, 1, 0, 1, 0]]   ->  2

Four patches of three blocks. Top-left and bottom-right are the same corner piece; top-right and bottom-left are its reflection, which no amount of sliding matches, so the count is 2.

Constraints.

• 1 <= len(wall) <= 300 and 1 <= len(wall[0]) <= 300
• every entry is 0 or 1
• the wall may be entirely bare, giving 0

Hints

Approach

Brute force

Flood-fill every patch into a list of coordinates, then compare each with every earlier one by trying the offset that lines up their first blocks. With p patches that is p²/2 comparisons, and a 300×300 wall holds up to 45,000 single-block patches: about 10⁹ comparisons.

The insight

A shape becomes comparable the moment you describe it relative to a point that belongs to the patch rather than to the wall.

Sliding a patch moves every block and the reference point by the same amount, so the differences between them do not change: the offset set is an invariant of the shape. The precondition is that the reference point follows a rule depending only on the patch — the first block a row-major scan reaches is such a rule.

Algorithm

1. Scan the wall in row-major order.
2. On an unvisited lichen block, take it as the anchor and flood its patch with an explicit stack: an all-lichen wall would recurse 90,000 deep.
3. For each block reached, record (row - anchor_row, col - anchor_col).
4. Sort the offsets into a tuple and add it to a set of shapes.
5. Return the size of that set.

Complexity

Time O(rc log k) — every block is visited once, and each patch of k blocks is sorted once. Space O(rc) for the visited grid and the largest patch.

Solution

"""Lichen on the north wall — count patch shapes up to translation."""


def patch_signature(wall, start_row, start_col, seen):
    """Flood one patch and return its cells as offsets from the anchor block."""
    rows, cols = len(wall), len(wall[0])
    stack = [(start_row, start_col)]
    seen[start_row][start_col] = True
    cells = []
    while stack:
        r, c = stack.pop()
        # Offsets are taken from the scan-order anchor, so two patches that are
        # translations of one another produce identical offset sets.
        cells.append((r - start_row, c - start_col))
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and wall[nr][nc] == 1 and not seen[nr][nc]:
                seen[nr][nc] = True
                stack.append((nr, nc))
    # Sorting removes any dependence on the order the flood happened to visit.
    return tuple(sorted(cells))


def solve(wall):
    if not wall or not wall[0]:
        return 0
    rows, cols = len(wall), len(wall[0])
    seen = [[False] * cols for _ in range(rows)]
    shapes = set()
    for r in range(rows):
        for c in range(cols):
            if wall[r][c] == 1 and not seen[r][c]:
                shapes.add(patch_signature(wall, r, c, seen))
    return len(shapes)

TESTS = [
    (([[1, 1, 0, 0, 0],
       [1, 1, 0, 0, 0],
       [0, 0, 0, 1, 1],
       [0, 0, 0, 1, 1]],), 1),
    (([[1, 1, 0, 1, 1],
       [1, 0, 0, 0, 1],
       [0, 0, 0, 0, 0],
       [1, 1, 0, 1, 1],
       [0, 1, 0, 1, 0]],), 2),
    (([[0, 0, 0],
       [0, 0, 0]],), 0),
    (([[1]],), 1),
    (([[1, 0, 1],
       [0, 0, 0],
       [1, 0, 1]],), 1),
    (([[1, 1, 1, 0, 1],
       [0, 0, 0, 0, 1],
       [1, 1, 0, 0, 1]],), 3),
    # the Pitfalls grid: four-way flooding sees two shapes here, eight-way one
    (([[1, 0, 0],
       [0, 1, 1],
       [0, 0, 0]],), 2),
]

Pitfalls

• Anchoring on the wall instead of the patch. Storing raw coordinates, or offsets from (0, 0), gives every patch a signature nothing else matches: the second example returns 4, the patch count, not 2.
• Hashing the offsets in visit order. The stack pops blocks in whatever order it likes, so two identical patches can produce different tuples and be counted twice. Sort the offsets first.
• Joining blocks that only touch at a corner. Adding the four diagonals to the flood merges patches the survey keeps apart: on [[1,0,0],[0,1,1],[0,0,0]] the four-way answer is 2 shapes and the eight-way answer is 1.

Variants

• Crossing the mudflats — the same grid-as-graph reading, with eight neighbours and a distance to report.
• BFS and DFS — the traversal this leans on, and why the stack beats recursion here.