Threshold infection spread on a grid

This is a synchronous cellular automaton. Every day, each healthy cell looks at
its 8 neighbors as they were at the start of the day. If at least
threshold of them are infected, the cell becomes infected at the end of the
day. Infection never goes away, so the infected set only grows, and the
simulation must stop after at most m * n days. We report how many days
produced at least one new infection, plus the final grid.

The one trap is simultaneity. If you infect cells in place while you scan
the grid, a cell infected early in the scan counts toward its neighbors later
in the same scan. Infection then spreads several cells in one "day". Collect
the day's new infections first and apply them together.

Brute force. Each day, scan every healthy cell, count its infected
neighbors, and collect the cells that reach the threshold. Then apply the batch.
Stop on the first day with no new infections. A day costs O(m * n), and there
can be O(m * n) days (think of a long snake-shaped path), so the total is
O((m * n)^2). Say this first. It is correct and it is easy to check against.

Optimal: incremental neighbor counts plus a frontier. A healthy cell's
count of infected neighbors changes only when one of its neighbors becomes
infected. So:

1. Precompute count[r][c], the number of infected neighbors, for every cell.
   Each infected cell adds 1 to each of its neighbors.
2. Day 1 candidates are all healthy cells with count >= threshold.
3. Infect the whole batch for the day. For each newly infected cell, add 1 to
   each neighbor's count. A healthy neighbor whose count has just reached
   threshold joins the next day's batch.
4. Repeat until a day's batch is empty.

Why it is correct: a cell enters a batch exactly when its count reaches the
threshold. Counts are only updated after the whole batch is chosen, so the
batch for day d + 1 depends only on the state after day d. That is the
synchronous rule. Counts only increase, so each healthy cell reaches the
threshold at most once. We check count == threshold on the increment, so a
cell is never queued twice.

Invariants:

• At the start of each day, count[r][c] equals the number of infected
  neighbors in the current grid.
• frontier holds exactly the healthy cells that will be infected today.

Edge cases: threshold <= 0 infects every healthy cell on day 1 (if there
are any). threshold > 8 means nothing ever spreads. An empty grid returns 0.

from typing import List, Tuple

Grid = List[List[int]]
DIRS = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]


def spread(grid: Grid, threshold: int) -> Tuple[int, Grid]:
    """Return (days with at least one new infection, final grid).

    Does not mutate the input grid.
    """
    if not grid or not grid[0]:
        return 0, [row[:] for row in grid]
    m, n = len(grid), len(grid[0])
    g = [row[:] for row in grid]

    def neighbors(r: int, c: int):
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n:
                yield nr, nc

    # count[r][c] = number of infected neighbors of (r, c).
    count = [[0] * n for _ in range(m)]
    for r in range(m):
        for c in range(n):
            if g[r][c] == 1:
                for nr, nc in neighbors(r, c):
                    count[nr][nc] += 1

    frontier = [(r, c) for r in range(m) for c in range(n)
                if g[r][c] == 0 and count[r][c] >= threshold]

    days = 0
    while frontier:
        days += 1
        for r, c in frontier:          # apply the whole day at once
            g[r][c] = 1
        nxt: List[Tuple[int, int]] = []
        for r, c in frontier:          # then propagate count changes
            for nr, nc in neighbors(r, c):
                count[nr][nc] += 1
                # "== threshold" queues each cell at most once.
                if g[nr][nc] == 0 and count[nr][nc] == threshold:
                    nxt.append((nr, nc))
        frontier = nxt
    return days, g


def spread_naive(grid: Grid, threshold: int) -> Tuple[int, Grid]:
    """Day-by-day full rescan. O((m*n)^2) worst case; used as a reference."""
    g = [row[:] for row in grid]
    m, n = len(g), len(g[0]) if g else 0
    days = 0
    while True:
        new = []
        for r in range(m):
            for c in range(n):
                if g[r][c] == 0:
                    k = sum(1 for dr, dc in DIRS
                            if 0 <= r + dr < m and 0 <= c + dc < n
                            and g[r + dr][c + dc] == 1)
                    if k >= threshold:
                        new.append((r, c))
        if not new:
            return days, g
        for r, c in new:
            g[r][c] = 1
        days += 1


if __name__ == "__main__":
    import random

    assert spread([[1, 0, 0, 0]], 1) == (3, [[1, 1, 1, 1]])
    assert spread([[1, 0], [0, 1]], 2) == (1, [[1, 1], [1, 1]])
    assert spread([[1, 0, 0], [0, 0, 0], [0, 0, 1]], 2)[0] == 3
    assert spread([[0, 0], [0, 0]], 1) == (0, [[0, 0], [0, 0]])
    assert spread([[0, 0], [0, 0]], 0) == (1, [[1, 1], [1, 1]])
    assert spread([[1, 1], [1, 0]], 9) == (0, [[1, 1], [1, 0]])
    assert spread([], 1) == (0, [])
    for _ in range(500):
        m, n = random.randint(1, 7), random.randint(1, 7)
        grid = [[int(random.random() < 0.25) for _ in range(n)] for _ in range(m)]
        t = random.randint(0, 4)
        assert spread(grid, t) == spread_naive(grid, t), (grid, t)
    print("ok")

• Initial counts: O(m * n). Each infected cell touches at most 8 neighbors.
• Simulation: every cell is infected at most once, and each infection updates
  at most 8 counts. Total O(m * n) across all days, however many days there
  are.
• Space: O(m * n) for the copy of the grid, the counts and the frontier.
• The naive rescan is O(m * n) per day and O((m * n)^2) in the worst case,
  with O(m * n) space.

• [[1, 0, 0, 0]], threshold 1 → 3 days, [[1, 1, 1, 1]] (one cell per day).
• [[1, 0], [0, 1]], threshold 2 → 1 day, all infected. Both healthy cells
  see two infected diagonal/orthogonal neighbors on day 1.
• [[1, 0, 0], [0, 0, 0], [0, 0, 1]], threshold 2 → 3 days, all infected.
  Day 1: only the center sees both seeds. Day 2: the four edge cells each see
  a seed plus the center. Day 3: the two remaining corners see three infected
  cells each.
• All healthy, threshold 1 → 0 days, grid unchanged (nothing to spread from).
• All healthy, threshold 0 → 1 day, everything infected (edge case: decide
  and state this rule with the interviewer).
• Threshold 9 → 0 days. No cell has more than 8 neighbors.
• Empty grid → (0, []).
• Simultaneity check: [[1, 0, 0]], threshold 1 must take 2 days, not 1.
  An in-place scan would wrongly infect both cells on day 1.
• Randomized grids, thresholds 0–4: the optimal version matches the naive
  reference.

1. Return -1 if the grid never becomes fully infected (like Rotting
   Oranges). After the loop, check whether any 0 remains. The cost does not
   change.
2. Recovery / immunity after D days. An infected cell becomes immune
   (state 2) after D days. Immune cells cannot be infected and do not
   count as infected neighbors. Store infected_on[r][c]. Each day, cells
   with day - infected_on == D recover, and they decrement their neighbors'
   counts. Counts can now go down, so a cell can cross the threshold more than
   once. Rebuild candidates from the cells whose counts changed today (both
   the new infections' and the recoveries' neighbors), rather than relying on
   == threshold. The run ends when no cell is infected or nothing changes.
   It always ends, because immune cells never revert.
3. Death / overcrowding rule. A cell with at least K infected neighbors
   dies (state 3, inert). This is the same pattern: each day, compute the
   transitions from the start-of-day state only, then apply them all and
   update the counts. Make the order of the rules explicit (does death beat
   infection on the same day?), and test it.
4. Sparse or very large / infinite grid. Store the infected cells in a set
   and the counts in a dict keyed by (r, c). Only cells next to an infected
   cell can change, so the work is proportional to the infected region, not to
   the bounding box.
5. Query the state at day k, or simulate many thresholds. Record each
   cell's infection day during one run, then answer "is (r, c) infected on
   day k" in O(1). Across thresholds the outcome is monotone: by
   induction on days, a higher threshold never infects a cell earlier. So
   "smallest threshold that leaves cell X healthy through day k" can be
   binary searched over 0–9 with one run per probe.

Mid-level (L4)

• Restates the rule correctly: 8 neighbors, at least threshold, simultaneous
  updates, infection is permanent.
• Writes a working day-by-day simulation that uses a separate "next" buffer,
  and explains why updating in place is wrong.
• Gets the termination condition and the day count right, and handles the
  boundaries.

Senior (L5)

• Starts with the rescan, states the O((m * n)^2) worst case, and moves to
  incremental counts with a frontier for O(m * n) total.
• Argues correctness: counts only increase, == threshold queues each cell
  once, and the batch is fixed before the counts change.
• Handles threshold <= 0, threshold > 8 and empty grids, and tests
  against the brute force.
• Adapts quickly to recovery: sees that counts can now decrease and changes
  the candidate logic to match.

Staff (L6+)

• Designs the update step so that new rules (immunity, death, recovery) can
  be added without rewriting it: compute every transition from the
  start-of-day state, then apply them and update the counts in one place.
• Discusses sparse and unbounded grids, memory on huge boards, and
  termination guarantees once states can cycle.
• Pins down ambiguous parts of the spec early (rule order, what counts as a
  "day", the meaning of threshold 0) and states the assumptions out loud.