Blue mould on the bench

Blue mould spreads overnight from an infected plug to the plugs it touches. The grower wants the night the last sound plug goes.

The problem

A propagation bench is a rectangle of cells, given as a list of equal-length lists. 0 is an empty cell, 1 is a sound plug, 2 is a plug already mouldy.

Each night every mouldy plug infects the sound plugs sharing an edge with it. Corners do not count, and an empty cell carries nothing.

Report the number of nights until no sound plug is left, or -1 if some sound plug is never reached. A bench with nothing sound on it needs 0 nights.

Input. bench — a rectangle of 0, 1 and 2.

Output. The number of nights, or -1.

Example.

bench = [[1, 1, 0, 1],
         [1, 2, 1, 1],
         [0, 1, 1, 1]]   ->  3

Night one takes the four plugs edge-on to the mouldy one. Night two takes row 0 column 0, row 2 column 2 and row 1 column 3. Night three takes the last two, in column 3.

A second example, where two mouldy plugs share the work:

bench = [[2, 1, 1, 1, 2]]   ->  2

The two waves meet at the middle plug on night two. A single mouldy plug at one end would have needed four.

And a bench that never clears:

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

The empty cells cut off the two plugs in the bottom row: nothing edge-adjacent to either one ever turns.

Constraints.

• 1 <= rows, cols <= 300
• every entry is 0, 1 or 2
• the bench may hold no mould at all, or nothing sound

Hints

Approach

Brute force

Take each sound plug and search outward for the nearest mouldy one, keeping the largest distance found. A 300 by 300 bench runs 90,000 searches over 90,000 cells: 8.1 × 10^9 cell visits.

The insight

Every plug that starts mouldy is one night ahead of the same wave, so queue them together as layer zero and count the layers, not the plugs.

Each night costs one and the same everywhere, so no plug turns sooner by a longer route and no priority queue is needed. Popping exactly the entries the queue held when the night began keeps the layers honest — those are yesterday's plugs, and only they can spread tonight.

Algorithm

1. Copy the bench. Queue every mouldy plug and count the sound ones.
2. While the queue holds something and a sound plug is left, pop exactly as many entries as the queue held when the round began.
3. Turn each sound edge-neighbour of a popped plug, drop the sound count and queue it. Add one night when the round ends.
4. Return -1 if a sound plug survived the queue running dry, else the nights.

Complexity

Time O(R × C) — each plug is queued once and looks at four neighbours: 90,000 cells, not 8.1 × 10^9 visits. Space O(R × C) — the copy, and a queue that holds the whole bench when it all starts mouldy.

Solution

"""Blue mould on the bench — one night is one whole layer of the same wave."""

from collections import deque


def solve(bench):
    rows, cols = len(bench), len(bench[0])
    tray = [row[:] for row in bench]
    wave = deque()
    sound = 0
    for r in range(rows):
        for c in range(cols):
            if tray[r][c] == 2:
                wave.append((r, c))     # every mouldy plug seeds the same wave
            elif tray[r][c] == 1:
                sound += 1

    nights = 0
    while wave and sound:
        for _ in range(len(wave)):
            # Invariant: this many entries are the plugs that turned last night,
            # so everything they touch turns tonight and nothing turns twice.
            r, c = wave.popleft()
            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 tray[nr][nc] == 1:
                    tray[nr][nc] = 2
                    sound -= 1
                    wave.append((nr, nc))
        nights += 1
    return -1 if sound else nights

TESTS = [
    (([[1, 1, 0, 1], [1, 2, 1, 1], [0, 1, 1, 1]],), 3),
    (([[2, 1, 1], [0, 0, 1], [1, 1, 0]],), -1),      # two plugs the mould cannot reach
    (([[2, 1, 1, 1, 2]],), 2),                       # both ends seed the wave
    (([[1, 1], [1, 1]],), -1),                       # no mould on the bench
    (([[0, 2], [0, 0]],), 0),                        # nothing sound to lose
    (([[1]],), -1),
    (([[2]],), 0),
]

Pitfalls

• Looping on the queue alone. The last layer pops with nothing sound left and still adds a night, so the first example comes out 4 instead of 3.
• Returning the count without checking for survivors. The third example runs the queue dry after 4 nights with two plugs still sound; reporting 4 says the bench cleared when it never does.
• Counting a corner as contact. Allowing the four diagonals reaches the cut-off plugs of the third example and reports 4 rather than -1.

Variants

• Sheep that cannot stray — the same many-seeded flood on a grid, with no rounds to count.
• Crossing the mudflats — one seed, eight neighbours, a route rather than a spread.