Because the coronavirus is still at large, I thought it would be fitting to have a epidemic-themed challenge.

## Challenge

You are given a 2D array of people, where 1 represents someone with the virus, and 0 represents someone without the virus. Every day, the people with the virus infect their neighbours. You must calculate, given such a grid, how many days it will take to infect the population (i.e., every item is 1).

## Rules

• The input counts as Day 0, and every day after increases by 1 (you can count the first day as Day 1 if you want, but indicate that in your answer).
• The grid items don't have to be 1s and 0s, they can be any truthy/falsy values. Every item in the grid is randomized to one of those values. Please specify which truthy/falsy values your program will/will not accept.
• The input grid can be any size between 2x2 and 100x100. The grid does not have to be square. The grid size is randomized (i.e. you can't choose).
• Diagonal squares do not count as adjacent.
• This is , so the shortest answer wins!

## Examples

[[1, 0, 0, 0, 1],  # Input
[0, 1, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 1, 0]]

[[1, 1, 0, 1, 1],  # Day 1
[1, 1, 1, 0, 1],
[0, 1, 0, 1, 0],
[0, 0, 1, 1, 1]]

[[1, 1, 1, 1, 1],  # Day 2
[1, 1, 1, 1, 1],
[1, 1, 1, 1, 1],
[0, 1, 1, 1, 1]]

[[1, 1, 1, 1, 1],  # Day 3
[1, 1, 1, 1, 1],
[1, 1, 1, 1, 1],
[1, 1, 1, 1, 1]]

output = 3

[[1, 0],  # Input
[0, 0],
[0, 0]]

[[1, 1],  # Day 1
[1, 0],
[0, 0]]

[[1, 1],  # Day 2
[1, 1],
[1, 0]]

[[1, 1],  # Day 3
[1, 1],
[1, 1]]

output = 3


• Are we guaranteed that there will be at least one person infected at the start? – hyper-neutrino Oct 31 '20 at 2:23
• 2 hours is far too quick to accept an answer. Generally, we discourage accepting an answer in the first place, to promote the idea that code golf has a winner in each language, but if you do accept an answer, you should generally wait a day or two to give everyone a chance to compete. – caird coinheringaahing Oct 31 '20 at 4:43
• @cairdcoinheringaahing I was thinking that I could simply change the accepted answer if a newer answer with less bytes is posted. If what you are saying is considered best practice, I'll do that, but out of curiosity, which is my aforementioned solution not recommended? – applemonkey496 Oct 31 '20 at 18:56
• @applemonkey496 Generally on SE, when an asker marks an answer as accepted, it signifies that the question is „over“, which we don’t really like here – caird coinheringaahing Oct 31 '20 at 19:52
• To make it more realistic, how about adding a second 0/1 matrix that acts as a mask, reducing the transmission rate to and/or from the corresponding element by 90%? (Not a serious suggestion, but it might have some interesting results as an actual program.) – Ray Butterworth Nov 1 '20 at 0:24

# 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)

• Command-line options should be included in the byte count. ≢ is 3 bytes in UTF-8. So is ×. So I believe should be 7 bytes. – user253751 Nov 2 '20 at 13:10
• (I disagree with the meta question, but clearly I'm in the minority.) – user253751 Nov 2 '20 at 13:13
• @user253751 Relevant. – Adám Nov 2 '20 at 15:03
• @user253751, tbh, I agree that each character should be 1 byte, but I also disagree with the meta question in that command line options should count towards byte count. Nevertheless, I don't think it's fair to retrospectively change the rules in a way that could affect this sort of thing, so maybe I will simply be more specific about this in future questions. Adám, I will leave it up to you to leave your answer as 2 bytes or use 3 bytes to include the command line options. (Or 7 bytes, as user253751 has proposed.) – applemonkey496 Nov 2 '20 at 17:42

# 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)

• Hmm... that's almost a justification to restrict the number of test cases provided and to rely on the explanation for future challenges... – Dominic van Essen Oct 31 '20 at 10:53
• @Sisyphus Oh, looks like I missed the solution by one byte (was using the wrong quick for this method). Thanks! – hyper-neutrino Oct 31 '20 at 14:17
• @DominicvanEssen that's a fair point. I understand the method though and it's almost identical to what I had in mind, I was just using the wrong quick by accident. – hyper-neutrino Oct 31 '20 at 14:18

# 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}.$$

# Octave, 26 bytes

@(x)max(bwdist(x,'ci')(:))


Try it online!

For each cell, compute the distance to the nearest nonzero cell under the $$\L_1\$$ norm (taxicab metric). The solution is the maximum value.

# APL (Dyalog Extended), 20 bytes

{⌈/⌊⌿⍵∘.(1⊥∘|-)⍥⍸~⍵}


Try it online!

Uses the Manhattan Distance method from HyperNeutrino's Jelly answer.

Input is a binary matrix.

## Explanation

{⌈/⌊⌿⍵∘.(1⊥∘|-)⍥⍸~⍵}
⍵           ~⍵  input and input negated
⍥⍸    coordinates of truthy values
∘.             outer product using
(1⊥∘|-)      Manhattan distance function (APLcart)
⌊⌿                Minimum of each column
⌈/                  Maximum of the minima


# C (gcc), 270 $$\\cdots\$$ 214 213 bytes

Saved a whopping 31 39 40 44 56 57 bytes thanks to ceilingcat!!!

z;C;i;j;n;d;*p;f(a,r,c)int*a;{p=calloc(C=c+2,4*r+8);for(n=d=0;d<r*c;++n){for(d=0,i=r;i--;)for(j=c;j--;)a[i*c+j]?p[i*C-~j]=p[(i+2)*C-~j]=p[z=j-~i*C]=p[z+2]=1:0;for(;++i<r*c;)d+=a[i/c*c+i%c]=p[1-~(i/c)*C+i%c];}d=n;}


Try it online!

Inputs the population grid as a pointer to an array of ints, that are either $$\1\$$ for infected or $$\0\$$ otherwise, along with the number of rows and columns. Returns the number of days it will take to infect the population.

### How?

Creates a shadow array p that has a one element boarder around it so we don't have to worry about the neighbours not being there when we're at the edges. Initialises all of its elements to $$\0\$$. For each day we then go though the input population grid row-by-row and column-by-column checking for infected elements. For everyone found we mark that position in the shadow array and its $$\4\$$ neighbours as infected. After that, on the same day, we then go through the input array again, copying over the corresponding shadow elements and counting the total number of infected for that day. Returns the number of days passed until all are infected.

# J, 35 bytes

1-~&#<@_>./@:(|.!.0)~&(0,(,-)=i.2)]


Try it online!

• (0,(,-)=i.2): 0 0,1 0,0 1,-1 0,0 -1
• <@_ f&dirs ] repeat input f dirs until the result does not change, and return all intermediate steps.
• >./@:(|.!.0)~ shift the board along the directions (with 0s getting shifted in at the borders), and take the maximum of them all.
• 1-~&# count the steps minus 1.

# JavaScript (ES6),  97  95 bytes

f=m=>/0/.test(a=[1,...m,1])&&1+f(m.map((r,y)=>r.map((v,x)=>v|r[x-1]|r[x+1]|a[y][x]|a[y+2][x])))


Try it online!

### Commented

f = m =>              // m[] = matrix
/0/.test(           // if there's still a zero in
a = [1, ...m, 1]  //   a[] which is defined as m[] with two dummy border rows
) &&                // then:
1 + f(              //   increment the final result and do a recursive call:
m.map((r, y) =>   //     for each row r[] at position y in m[]:
r.map((v, x) => //       for each value v at position x in r[]:
//         the cell is set if:
v |           //           it's already set
r[x - 1] |    //           or the cell on the left is set
r[x + 1] |    //           or the cell on the right is set
a[y][x] |     //           or the cell above is set
a[y + 2][x]   //           or the cell below is set
//           NB: both a[0][x] and a[a.length - 1][x] are
//               undefined (falsy) for any x
)               //       end of inner map()
)                 //     end of outer map()
)                   //   end of recursive call


# Python 3, 131 bytes

lambda a,e=enumerate:max([min([abs(x-X)+abs(y-Y)for X,I in e(a)for Y,J in e(I)if J]or[0])for x,i in e(a)for y,j in e(i)if j<1]+[0])


Try it online!

If nobody is infected in the original, this will return 0.

-11 bytes thanks to caird coinheringaahing

Try it online!

Older method using recursion:

# Python 3, 199 bytes

f=lambda a,c=0:all(sum(a,[]))and c or f([[g(a,x,y+1)+g(a,x,y-1)+g(a,x+1,y)+g(a,x-1,y)+g(a,x,y)for y in range(len(a[x]))]for x in range(len(a))],c+1)
g=lambda q,x,y:len(q)>x>=0<=y<len(q[x])and q[x][y]


Try it online!

If there is nobody infected in the original, this will recursion overflow.

# Charcoal, 39 bytes

Ｉ⌈Ｅθ∨⌈Ｅ⌕Ａι⁰∨⌊ΦＥθ⌊Ｅ⌕Ａν¹⁺↔⁻ξκ↔⁻πλ¬⁼νＩν⁰¦⁰


Try it online! Link is to verbose version of code. Uses the Manhattan distance method again. Charcoal can't flatten lists, plus it returns None for the minimum or maximum of an empty list, which complicates the code somewhat. Explanation:

  Ｅθ                                    For each row
Ｅ⌕Ａι⁰                             For each 0 value in that row
Ｅθ                        For each row
Ｅ⌕Ａν¹                  For each 1 value in that row
↔⁻ξκ↔⁻πλ         Calculate the Manhattan distance
⌊                       Take the minimum
Φ                 ¬⁼νＩν    Filter out None values
⌊                           Take the minimum
∨                        ⁰   Or zero if the list was empty
⌈                                  Take the maximum
∨⌈                                ⁰ Or zero if the list was empty
⌈                                      Take the maximum
Ｉ                                       Cast to string
Implicitly print


# K (oK), 41 bytes

{|/&/{+/x|-x}''u-\:/:(1=x.)#u:+!(#x),#*x}


Try it online!

Maximum of the minimums of the Manhattan distance of each point to each truthy point.

{                                        } \ a function with parameter x
#*x  \ length of the first row
,     \ appended to
(#x)      \ the number of rows
!          \ odometer (coordinates of the points)
+           \ transpose
u:            \ assign to u
#              \ filter
(1=x.)               \ the coordinates of the truthy points
u-\:/:                     \ find the differences of the cooridinates
\ of each point to each truthy point
{+/x|-x}''                           \ find the absolute value and sum
&/                                     \ minimum of the Manhattan distances
\ to each truthy point
|/                                       \ maximum



# Java 8, 204 bytes

m->{int r=0,f=1,l=m[0].length,i,t,I,J,n;for(;f>0;r++)for(n=f,f=0,i=m.length*l;i-->0;)for(t=4;m[I=i/l][J=i%l]==n&t-->0;)try{m[I-=t-t%3*t>>1][J-=t<2?1-2*t:0]+=m[I][J]<1?f=n+1:0;}finally{continue;}return r;}


Minor modification of my answer here.

Outputs the result including the first step.

Try it online.

Explanation:

m->{                          // Method with integer-matrix parameter and integer return-type
int r=0,                    //  Result-integer, starting at 0
f=1,                    //  Flag-integer, starting at 1
l=m[0].length,          //  Amount of rows
i,t,I,J,n;              //  Temp integers
for(;f>0;                   //  Loop as long as the flag is NOT 0:
r++)                    //    After every iteration: increase the result by 1
for(n=f,                  //   Set n to the current flag-value
f=0,                  //   And then reset the flag to 0
i=m.length*l;i-->0;)  //   Loop over the cells of the matrix:
for(t=4;                //    Set the temp integer t to 4
m[I=i/l][J=i%l]==n  //    If the current cell contains value n
&t-->0;)            //     Loop t in the range (4,0]:
try{m                 //      Get the cell at a location relative to the current cell:
[I-=t-t%3*t>>1]  //       If t is 3:
//        Take the cell above
//       Else-if t is 2:
//        Take the cell below
[J-=t<2?1-2*t:0] //       Else-if t is 0:
//        Take the cell left
//       Else-if t is 1:
//        Take the cell right
+=m[I][J]<1?    //      And if this cell contains a 0:
f=n+1       //       Fill it with n+1,
//       And set the flag to n+1 as well
:            //      Else:
0;          //       Keep the value the same by increasing with 0
}finally{continue;}   //      Catch and ignore ArrayIndexOutOfBoundsExceptions
//      (saves bytes in comparison to manual boundary checks)
return r;}                  //  And after the loop: return the result


# 05AB1E, 18 bytes

ΔĀ2FøJTÂ‚12Â‚:€S]N


Outputs the result including the first step.

Explanation:

Δ                # Loop until the result no longer changes,
# using the (implicit) input-matrix in the first iteration
Ā               #  Python-style truthify each integer, changing all potential 2s to 1s
2F             #  Loop 2 times:
ø            #   Zip/transpose; swapping rows/columns
J           #   Join each row of digits together to a string
TÂ‚        #   Pair 10 with its reversed: ["10","01"]
12Â‚    #   Do the same for 12: ["12","21"]
:   #   Replace all "10" with "12" and all "01" with "21" in all rows
€S #   And convert each row back to a list of digits
]                # Close the nested loops
N               # And push the 0-based index of the outer loop
# (note that the loop until the result no longer changes will loop an
#  additional time, which is why this results in the correct result
#  despite having 0-based indexing instead of 1-based)
# (after which it is output implicitly as result)


# R, 105 101 bytes

Edit: -4 bytes thanks to Giuseppe

function(m)max(apply(as.matrix(dist(which(m<2,T)[order(-!m),],"man"))[f<-1:sum(!m),-f,drop=F],1,min))


Try it online!

covidsteps=
function(m,             # m is input matrix
e=m<1)                  # e is uninfected cells
max(                    # get the max of the distances from each uninfected cell
# to its closest infected cell, by
apply(...,1,min)       # getting the minima of
as.matrix(
dist(...,"man")       # the pairwise manhattan distances between
which(m<2,T)          # all coordinates
[order(-e),])         # ordered with infected cells first
[                     # and selecting only distances between
f<-1:sum(e),         # uninfected cells (rows in the distance matrix)
-f,                  # and infected cells (cols of the distance matrix)
drop=F])

• 101 bytes – Giuseppe Nov 29 '20 at 13:27
• Thanks @Giuseppe. I think I had the e=m<1 as a left-over from trying (unsuccessfully) to find a shorter iterative solution... – Dominic van Essen Nov 29 '20 at 13:38

# Retina 0.8.2, 100 bytes

^
¶
{1s¶(1.*0|0.*1)
_$& }(?<=(.)*)0(?=(.*¶(?<-1>.)*(?(1)$))?1|(?<=10|¶(?(1)^)(?<-1>.)*1.*¶.*))
1
_


Try it online! Takes input as a rectangular digit array. Explanation:

^
¶


Prepend a newline to provide a work area to build up the result. (While I can append the result instead, that complicates the regular expressions, so it's not any golfier.)

{
}


Repeat until a stable position is reached (either all 0s or all 1s).

1s¶(1.*0|0.*1)
_$&  If the position contains a mixture of 0s and 1s then increment the number of days. (?<=(.)*)0  If there is a 0 that ... (?=(.*¶(?<-1>.)*(?(1)$))?1|


... is directly next to a 1 which either to the right or below, or ...

(?<=10|¶(?(1)^)(?<-1>.)*1.*¶.*))


... is either directly to the right of a 1 or directly below a 1...

1


... then replace it with a 1.

_


Output the number of days in decimal.

The above/below checks are made using .NET balancing groups. The initial (?<=(.)*) grabs the column number into $#1, and then we have two cases: • .*¶(?<-1>.)*(?(1)$)1 advances to the next line, advances one character for every column, checks for the correct column ($ can't possibly match before 1, so (?(1)$) can only match if there are no columns left to advance), and then matches 1.
• (?<=¶(?(1)^)(?<-1>.)*1.*¶.*) is a lookbehind, so is matched right-to-left: first it advances to the previous line, then finds a 1, then advances and checks for the correct column (^ can't match after ¶ because we're not in multiline mode, but $ would also work), then checks for the start of the line (it won't be the start of the buffer because of the ¶ added at the beginning of the program). # CJam, 68 bytes {__{,,:)}:M~\zMm*\_{{_M.*}%\z}2*..{_{a+}{;;}?}:~f{\f{.-:z:+}$0=}$W=}  Try it online! If only I knew how to properly manipulate 2D arrays in this language... Calculates the maximum of each minimum Manhattan distance from each point to each infected point. # Perl 5-00p, 63, 60 bytes Saved some bytes thanks to Dom Hastings. / /;$,='.'x"@-";$\++while s/(?<=1$,)0|1\K0|0(?=$,1|1)/1/gs}{  Try it online! • Nice, rally like precalculating $,. I might've missed something but I think you can save bytes re-working the search pattern: Try it online! – Dom Hastings Nov 2 '20 at 8:02
• adding say seems not to work as expected – Nahuel Fouilleul Nov 2 '20 at 8:58
• however could save some bytes – Nahuel Fouilleul Nov 2 '20 at 9:01
• I'm not sure where the say came from, I think it might've been in your header? :) I think you can still combine (?<=1$,)0|1\K0 into 1($,)?\K0 though for -5! – Dom Hastings Nov 2 '20 at 9:10
• the issue with 1(\$,)?\K0 is that the cursor in input string will move forward one line and miss other changes as seen in my link, also puting the 1 in the center will give 3 instead of 2. – Nahuel Fouilleul Nov 2 '20 at 9:25

# Python 3, 115 bytes

f=lambda a,e=enumerate:all(map(all,a))or-~f([[1in[0,*r][j:j+3]+[0,*c][i:i+3]for j,c in e(zip(*a))]for i,r in e(a)])


Try it online!

1-indexed recursive solution. Replaces each item with True if itself or any of its orthogonal neighbours are 1 (==True). Recursion stops when all values in the array are True`.