Plant Infection Grid Simulation: Days to Stabilize, Immune Plants, Expiring Immunity

A garden is an `R × C` grid. Each cell is empty, holds a healthy plant, or holds an infected plant. The infection spreads in daily steps: on each day, every healthy plant that is directly adjacent (up, down, left or right) to a plant that was already infected at the end of the previous day becomes infected. Empty cells never change and do not carry the infection. Plants infected at the start count as infected on day 0. The garden **stabilizes** once no further infections can ever happen. The question is progressive: each part adds a rule, and your code should evolve to handle it. ### Clarifying Questions - How is the grid given (for example a list of strings with one character per cell), and how large can it be? - If some healthy plants can never be reached by the infection, should the answer change (for example to `-1`), or should those plants only be reported alongside the day count? - Do infected plants ever recover? - In Part 2, are immune plants present from the start, or can a plant become immune during the simulation? ### Part 1 — Days until the garden stabilizes Given the starting grid, return the number of days until the garden stabilizes, that is, the last day on which at least one new plant becomes infected (0 if none ever is). ```hint Many sources at once All the initially infected plants spread at the same time; think about a traversal that processes the whole garden in order of infection day. ``` #### What This Part Should Cover - A simultaneous spread from all infected cells, with correct day counting - Correct handling of empty cells, isolated healthy plants and a garden with no infection - Time and space complexity in terms of the number of cells - A comparison between a naive day-by-day simulation and the efficient approach ### Part 2 — Immune plants Some cells now hold immune plants, which never become infected. Update your solution. ```hint What does an immune plant change Trace the spread rule for a cell that can never be infected, and check what, if anything, in your Part 1 code must change. ``` #### What This Part Should Cover - The new cell type integrated cleanly into the parsing and the spread rule - Whether immune plants block the spread, justified from the rule - Reporting of plants that can never be infected ### Part 3 — Immunity that counts down Immunity is now temporary. In this version, each immune plant has a countdown of `k` days: it resists infection on days `1` through `k`, and from day `k + 1` on it behaves like an ordinary healthy plant. Different plants can have different countdowns. Return the day on which the garden stabilizes. ```hint Infection can wait An immune plant next to an infected one does not become infected right away, but it will as soon as its protection lapses; think about how to compute each plant's infection day directly instead of simulating every day. ``` #### What This Part Should Cover - A correct rule for the infection day of a plant whose immunity expires - An algorithm that does not step through every day when countdowns are long - Correct behavior when immunity expires with no infected neighbor, or with several - Complexity, and a test that compares against a straightforward simulation ### What a Strong Answer Covers - Clean code that evolves from part to part rather than being rewritten each time - Precisely stated rules for each ambiguity, confirmed with the interviewer - Efficient algorithms with correct complexity, and awareness of when simulation is too slow - Tests covering empty gardens, unreachable plants, ties and long countdowns ### Follow-up Questions - Infected plants now recover after a fixed number of days and become immune for a while. Can the garden still be guaranteed to stabilize, and how would you detect a repeating pattern? - How would you handle a grid too large to fit in memory? - The infection also spreads diagonally with some probability. What changes in your approach? - How would you report the order in which plants were infected, for visualization?