Air pockets in the casting

A foundry X-rays every casting before it ships. A void that opens out to the surface is a channel the machinist will find; a void sealed in on all sides is a pocket, and pockets are what the inspector counts.

The problem

The radiograph is printed as a rectangular grid of cells. A cell is # where the scan reads solid metal and . where it reads void.

Two void cells belong to the same patch when they share an edge — up, down, left or right. Cells meeting only at a corner are in different patches: the metal between them is unbroken.

A patch is a pocket when none of its cells lies on the outer ring of the scan. A patch with a cell on that ring runs out of the casting and is a channel.

Count the pockets — patches, not cells, so a pocket of nine cells counts once.

Example.

scan = ["######",
        "#..#.#",
        "#.##.#",
        "##...#",
        "#####."]   ->  2

Three cells in the upper left form one pocket. Five more — the right-hand column and the row beneath it — form a second. The cell in the bottom right sits on the outer ring, so it is a channel. Counting cells would answer 8.

A second example, where two voids look like one:

scan = ["####",
        "#.##",
        "##.#",
        "####"]   ->  2

The two voids touch corner to corner only, so they are two pockets, not one.

scan = ["#####",
        "#..##",
        "#.###",
        "..###",
        "#####"]   ->  0

The void winds down to the left-hand edge, so the whole patch is one channel.

Input. scan — a list of strings of equal length, each character # or ..

Output. An integer: the number of pockets.

Constraints.

• 1 <= len(scan) <= 300
• 1 <= len(scan[0]) <= 300, every row the same length
• every character is # or .

Hints

Approach

Brute force

For each void cell, search outward to see whether it reaches the outer ring, then group the ones that do not. That is up to r · c searches of r · c cells each — about 8 × 10⁹ steps on a 300 × 300 scan.

The insight

Flood each patch exactly once and let the flood itself carry the verdict: the patch is a pocket when no cell the flood visits lies on the outer ring.

Every cell of a patch reaches every other, so they share one answer, and a single flood settles it for all of them at the price of visiting each cell once. The flag is an aggregate over the flood, not a reason to stop it: the verdict is only final once the whole patch has been seen.

Algorithm

1. Keep a seen grid of the same shape, all false.
2. Sweep the cells; on a void cell not yet seen, start a flood there.
3. The flood marks each cell as it is pushed, and sets a flag when the cell it pops is in row 0, the last row, column 0 or the last column.
4. Push unseen void neighbours in the four directions.
5. When the flood drains, add one to the count if the flag is unset.

Complexity

Time O(r · c) — every cell is pushed at most once and looks at four neighbours. Space O(r · c) for seen, plus a stack that on an all-void scan holds every cell.

Solution

"""Air pockets in the casting — flood each void once and let the flood report the edge."""


def flood(scan, seen, start):
    """Mark every cell of one void patch; report whether it reached the outer ring."""
    rows, cols = len(scan), len(scan[0])
    stack = [start]
    seen[start[0]][start[1]] = True
    open_to_air = False
    while stack:
        r, c = stack.pop()
        if r == 0 or c == 0 or r == rows - 1 or c == cols - 1:
            open_to_air = True        # noted, but the patch is still walked to the end
        for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
            if 0 <= nr < rows and 0 <= nc < cols and scan[nr][nc] == '.' and not seen[nr][nc]:
                seen[nr][nc] = True   # marked on the push, so no cell is stacked twice
                stack.append((nr, nc))
    return open_to_air


def solve(scan):
    rows, cols = len(scan), len(scan[0])
    seen = [[False] * cols for _ in range(rows)]

    pockets = 0
    for r in range(rows):
        for c in range(cols):
            if scan[r][c] == '.' and not seen[r][c]:
                if not flood(scan, seen, (r, c)):
                    pockets += 1      # one patch, one pocket, whatever its size
    return pockets

TESTS = [
    ((["######", "#..#.#", "#.##.#", "##...#", "#####."],), 2),
    ((["####", "#.##", "##.#", "####"],), 2),        # corner to corner is not joined
    ((["#####", "#..##", "#.###", "..###", "#####"],), 0),  # a channel to the edge
    ((["#####", "#...#", "#.#.#", "#...#", "#####"],), 1),  # a ring is one pocket
    ((["####", "####"],), 0),                        # solid metal
    (((["...", "...", "..."]),), 0),                 # all void, all of it open
    ((["#"],), 0),
    ((["."],), 0),
]

Pitfalls

• Stopping the flood as soon as it touches the ring. The rest of that patch stays unmarked, the sweep finds it again and counts it as a pocket — in the third example, 1 instead of 0.
• Counting cells instead of patches. The first example answers 8.
• Joining cells that meet at a corner. The second example becomes one patch and answers 1.

Variants

• Sheep that cannot stray — the same enclosure test run the other way, flooding inward from the border and counting cells.
• Repainting the lido mosaic — one flood from one seed, with nothing to decide at the end.