Calculate COVID spread
Jelly, 10 bytes
ŒJạ€ŒṪ§Ṃ€Ṁ
Try it online!
-2 bytes thanks to Sisyphus
Calculate the Manhattan differences from all 0s to all 1s, and the answer is the maximum of the minimums (each row's minimum is the number of stages until it gets infected, so the number of stages needed is the maximum of the stages needed for each person).
Conveniently, if all elements are 1, this returns 0 since that's the default value for minmax.
If no person is infected in the initial state, this also returns 0.
Explanation
ŒJạ€ŒṪ§Ṃ€Ṁ Main Link
ŒJ Get all indices in the grid (2D indices in a matrix)
ŒṪ Get all truthy indices in the grid (finds all infected people)
ạ€ § Manhattan distance between each point to each truthy point
Ṃ€ Minimum of each (minimum number of days for each person to get infected)
Ṁ Maximum (of each point's required days to get infected)
Stencil ≢
, 2 bytes
×v
Try it online!
≢
tallies the number of necessary steps (including the initial state) until stability is reached. This command line argument isn't counted towards the byte count, as per Meta consensus.
Each cell's next state is determined by:
×
the sign of
v
the sum of all values in its von Neumann neighbourhood (including itself)
Wolfram Language (Mathematica), 90 78 bytes
f=Length@FixedPointList[ListConvolve[CrossMatrix@1,#,{2,2},0,Times,Max]&,#]-2&
Try it online!
-12 bytes, because of course there is a built-in CrossMatrix
to construct the kernel \$K\$.
Defines a pure function f
that takes a matrix as input. If no one is infected, return 0
. Uses list convolution to spread the disease day-by-day and a Mathematica built-in to loop until a fixed point is reached (i.e. everyone is infected). Explanation:
To spread the disease, use a kernel
$$K=\begin{pmatrix} 0 & 1 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 0 \end{pmatrix}$$
and list convolution. For example, if we start at
$$I_0=\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ \end{pmatrix}$$
then applying
ListConvolve[{{0, 1, 0}, {1, 1, 1}, {0, 1, 0}}, #, {2, 2}, 0] &
results in
$$\begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 2 & 2 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ \end{pmatrix}.$$
We don't actually need to know whether a person is infected multiple times, so within the list convolution, instead of summing, we'll just take the maximum
ListConvolve[{{0, 1, 0}, {1, 1, 1}, {0, 1, 0}}, #, {2, 2}, 0, Times, Max] &
which gives
$$\begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ \end{pmatrix}.$$
Then we just need to iterate it until a fixed point is reached, i.e. everyone is infected to no new infections can occur. There's (as usual) a handy built-in in Mathematica, FixedPointList
, which gives a list of all the iterations until a fixed point is reached. Since this list contains the input and the fixed point twice, just subtract two from the list length to get the answer.
As a sidenote, the parameters in ListConvolve
ensure that the convolution works well with the kernel. With the default parameters, convolving
$$\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{pmatrix}$$
with the kernel
$$\begin{pmatrix} a & b & c \\ d & e & f \\ g & h & i \end{pmatrix}$$
gives rather uselessly
$$\begin{pmatrix} 0 & 0 \\ b & c \end{pmatrix}.$$
To at least preserve the dimensions, we'll add the parameter {1,1}
, which now gives
$$\begin{pmatrix} 0 & d & e & f \\ 0 & g & h & i \\ 0 & 0 & 0 & 0 \\ 0 & a & b & c \\ \end{pmatrix}.$$
This time, the problem is that the convolution starts at the top-left corner instead of at the center of the kernel, so let's change the {1,1}
to {2,2}
, which gives
$$\begin{pmatrix} g & h & i & 0 \\ 0 & 0 & 0 & 0 \\ a & b & c & 0 \\ d & e & f & 0 \\ \end{pmatrix}.$$
This is almost what we need, but the bottom of the kernel overflows to the top. To fix this, we'll just add a padding parameter 0
. Finally
$$\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ a & b & c & 0 \\ d & e & f & 0 \\ \end{pmatrix}.$$