Calculate COVID spread

Question

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 code-golf, 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

---

Answer 1

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)

Answer 2

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)

Answer 3

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

Answer 4

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.

Answer 5

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

Answer 6

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.

Answer 7

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.

Answer 8

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

Answer 9

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.

Answer 10

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

Answer 11

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
                                     

Answer 12

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

Answer 13

05AB1E, 18 bytes

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

Outputs the result including the first step.

Try it online or verify all test cases.

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)

Answer 14

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

Answer 15

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

Answer 16

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.

Answer 17

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!

Answer 18

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.