Simulate Infection Spread on a Grid

Problem Statement

You are tasked with building a discrete-time simulation of an epidemic spreading through an R x C population grid over a given number of days.

Each cell on the grid is in one of five base states:

• . : Empty space (cannot contract or spread the infection)
• S : Susceptible individual
• I : Infected individual
• R : Recovered individual (temporarily immune)
• D : Deceased individual (permanent terminal state)

Simulation Rules

All state transitions occur synchronously at discrete daily steps based on the state of the grid at the beginning of the day:

1. Infection Dynamics:

   • An infected individual remains infected for exactly t_inf days.
   • Any S cell with at least k_trans adjacent infected neighbors (considering all 8 directions: horizontal, vertical, diagonal) contracts the virus and transitions to I at the end of the day, starting with t_inf days remaining.

2. Recovery and Mortality:

   • When an infected cell reaches the end of its t_inf-th day of infection:
     • If it has at least k_death currently infected neighbors (8-directional) at that time step, the individual dies and transitions to D.
     • Otherwise, the individual recovers and transitions to R, starting with t_rec days of immunity remaining.

3. Immunity Waning:

   • A recovered individual remains immune for t_rec days.
   • At the end of its t_rec-th day, if t_rec > 0, the individual loses immunity and transitions back to S.
   • If t_rec == 0, a recovering individual transitions directly to S instead of R.

4. Terminal / Inactive States:

   • Empty cells (.) and deceased individuals (D) never change state.

Initially, all 'I' cells in the starting grid have t_inf days remaining, and any 'R' cells have t_rec days remaining.

Write a function simulate_infection(grid, days, t_inf, t_rec, k_trans, k_death) that returns the grid state after days full days of simulation, where each cell is represented by its base character ('.' | 'S' | 'I' | 'R' | 'D').

Function Signature

def simulate_infection(
    grid: list[list[str]],
    days: int,
    t_inf: int,
    t_rec: int,
    k_trans: int,
    k_death: int
) -> list[list[str]]:
    pass

Constraints

• 1 <= R, C <= 100
• 0 <= days <= 1000
• 1 <= t_inf <= 50
• 0 <= t_rec <= 50
• 1 <= k_trans <= 8
• 1 <= k_death <= 8
• grid[r][c] is one of ['.', 'S', 'I', 'R', 'D']

Examples

Example 1

grid = [
    ["S", "S", "."],
    ["S", "I", "."],
    [".", ".", "."]
]
days = 2
t_inf = 2
t_rec = 1
k_trans = 1
k_death = 2

# Day 1:
# (1, 1) was I with 2 days left -> now 1 day left.
# (0, 0), (0, 1), (1, 0) are S and have 1 infected neighbor (>= k_trans=1) -> become I with 2 days left.
# Day 2:
# (1, 1) finishes infection (reached 0 days left). It has 3 currently infected neighbors: (0,0), (0,1), (1,0). Since 3 >= k_death (2), it dies -> 'D'.
# (0, 0), (0, 1), (1, 0) were I with 2 days left -> now 1 day left.

output = [
    ["I", "I", "."],
    ["I", "D", "."],
    [".", ".", "."]
]

Example 2

grid = [["I"]]
days = 3
t_inf = 1
t_rec = 1
k_trans = 1
k_death = 1

# Day 1: (0, 0) has 0 infected neighbors ( R with 1 day.
# Day 2: (0, 0) finishes immunity -> transitions to S.
# Day 3: (0, 0) remains S (no infected neighbors).

output = [["S"]]