Infection Spread / Cellular Automata

Requirements

Part 1 (basic spread)

• Each day every infected cell (1) simultaneously infects all 4-neighbor healthy (0) cells (orthogonal only, no diagonals); cells newly infected today only start propagating tomorrow.
  • The general rule the levels build on: a healthy cell becomes infected next step if it has at least N infected 4-neighbors. Part 1 is the N = 1 specialization (any single infected neighbor suffices); later parts raise N (Part 4) or add state.
  • Minority variant: some reports describe 8-neighbor propagation (diagonal-inclusive) — clarify before coding; it changes day-counts on every test case.
• Multiple infection sources allowed.
• Return the number of days to reach full infection, or -1 if it is impossible (no infection source, or some cells are permanently unreachable).
  • Minority variant: return days until the grid stabilizes rather than days until full infection; clarify the stopping condition before coding.
• Edge cases: empty grid, no sources (return -1), all-infected (return 0), 1×1, multiple sources, single row/column line spread.

def time_to_full_infection(grid: list[list[int]]) -> int:
    """
    Args:
        grid: An n×m grid where 0 = healthy, 1 = infected.
    Returns:
        Steps until all cells are infected, or -1 if impossible
        (no initial source, or unreachable healthy cells remain).
    """
    ...

Part 2 (immune cells)

• Introduce immune cells (2): never get infected, never propagate, skipped when counting neighbors.
  • Minority variant (encoding): the immune sentinel is sometimes -1 instead of 2; some loops use letter notation — . / X / I for healthy / infected / immune — clarify encoding before coding.
• Return days until all reachable healthy cells are infected, or -1 if any healthy cell remains permanently blocked behind immune walls (it will never be infected).

def time_to_full_infection_with_immunity(grid: list[list[int]]) -> int:
    """
    Grid values: 0 = healthy, 1 = infected, 2 = immune (permanent wall).
    Returns steps until all non-immune healthy cells are infected,
    or -1 if any healthy cell is unreachable (walled off by immune cells).
    """
    ...

Part 3 (D-day recovery → immunity)

• After being infected for D days, a cell becomes immune (2, self-heals — no longer propagates).
• Balance condition: no active infected cells remain (grid is fully stable — some cells may be healthy forever).
• Watch day semantics / off-by-one: a cell infected on day t becomes immune when current_day - t >= D; immunity takes effect before spread on the same tick.

def time_to_stable_state(grid: list[list[int]], D: int) -> int:
    """
    Grid values: 0 = healthy, 1 = initially infected.
    D: days until an infected cell becomes immune (stops spreading).
    Returns days until no active infections remain.
    """
    ...

Part 4 (threshold + death) — three confirmed variants

• Variant A: a healthy cell only becomes infected next day if it has ≥ K infected 4-neighbors (threshold spread).
• Variant B: an infected cell that's alive and not yet immune begins a death countdown if ≥ K infected neighbors; dies after N days. In the stricter version, a cell that was infected while surrounded by at least K infected neighbors dies when its recovery timer expires instead of becoming immune. Return days-to-end + final death count.
• Variant C (composite): Part 1+2+3 + death all stacked.

Part 5 (very few candidates reach this)

• Each day, choose any row or column and burn everything on it. Minimize total deaths.
  • Minority variant: choose a row, a column, or no burn to minimize total deaths; clarify whether this is a single choice or a repeated daily decision before coding.
• Some loops swap this optimization branch for engineering follow-ups ("what if the grid is huge").

Examples

Part 1 (N = 1), 4-neighbor spread:

• Single center source in a 3×3 → 2 (neighbors at step 1, corners at step 2).
• Two opposite corners infected in a 3×3 → 2 (waves meet in the middle).
• All-healthy grid → -1 (no source can start the spread).
• Single-row line [[1,0,0,0,0]] → 4 (linear chain; a single center source in a 5×5 likewise reaches the farthest cell in 4).
• [[1]] → 0; [[0]] → -1.

Notes

Canonical pattern

Parts 1–2 are textbook multi-source BFS on a grid (the canonical "rotting oranges" pattern): enqueue every initial X as a level-0 source, expand wavefronts of 4-neighbors (orthogonal only, no diagonals) in lockstep, count levels until the queue stops producing newly-infected cells. Complexity is O(R·C) time and space per part — every cell is enqueued and dequeued at most once. The "newly infected today only propagate tomorrow" rule maps directly onto BFS level boundaries; do not confuse it with per-cell DFS or with 8-neighbor (diagonal-inclusive) rotations, which are a different problem.

Parts 3–4 break the pure BFS skeleton because cells carry per-cell state (days-infected-so-far, death countdown, threshold-based activation predicate). Keep BFS as the outer loop, but advance the grid in a full simultaneous-update step: snapshot the current grid, compute every cell's next state from the snapshot, then swap. Mutating in place during the same day is the most common bug source.

• Extreme speed focus. Interviewers sometimes frame "finish all 5 to pass", but in practice a "strong" verdict is reachable after just Parts 1-3 with clean edge cases.
• BFS + a newly_infected list is the consensus implementation. Use the simplest implementation, don't optimize.
• Part 3 commonly uses hashMap[day] -> set((i, j)) for "which cells heal on which day".
• A current Part 4 framing expresses spread/death as a neighbor-count threshold rather than a fixed direction list; ask whether K is an infection threshold, a death threshold, or both before coding.
• An LLM-friendly version of the prompt — usable to generate a practice harness + tests in Claude/GPT — circulates in candidate prep notes.

BFS vs naive simulation — the complexity trap

Two implementations exist for Part 1, and the difference is testable. Multi-source BFS (enqueue all sources at level 0, each cell touched once) is O(R·C) time and space. The naive per-step simulation — rescan the whole grid each day, collect cells that now have ≥ N infected neighbors, apply them simultaneously, repeat — is O((R·C)²) time because it re-scans the entire grid on every one of up to O(R·C) steps. Simulation is easier to extend to Parts 3–4 (where per-cell state breaks pure BFS), so the usual play is BFS for Parts 1–2 and a simultaneous-update simulation for the stateful parts; be ready to state the complexity penalty of simulation on Part 1 if asked.

Part 3 state-tracking precision

Track infection_day[i][j] (the day each cell got infected; None = healthy, sentinel = immune). On each tick: first compute who turns immune (current_day - infection_day[i][j] >= D) and remove them from the active set; then spread from remaining active cells. The order matters — newly-immune cells do not spread on the same day they recover. Common off-by-one: using > D instead of >= D.

Preparation

• Drill until you can finish Parts 1-3 in 30-40 min with all fixed tests passing and edges handled.
• Focus drills: synchronous update (double buffer vs queue + day stamp), off-by-one, multi-source BFS, immune barriers.
• Don't get fancy — clarity beats efficiency.