Infection Spread / Cellular Automata

M×N grid with infected cells (X) and susceptible cells (./*); infection propagates each day under escalating rules. 5 sub-parts in 60 min; passing bar is typically solving the first 3 with clean BFS. 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). 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. Some loops swap this optimization branch for engineering follow-ups ("what if the grid is huge"). 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. 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. 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.