May the fourth be with flu

Question

Since tomorrow is the 4th of May, here's a little Star Wars themed post to prepare you mentally to all the bad jokes coming tomorrow.

BACKSTORY

During a session of the galactic senate all the senators are sitting in an n*n grid. A sudden outbreak of JarJar flu (which lasts forever and causes the infected to speak like JarJar Binks) causes some of the senators to get infected.

Here's an example with a 6*6 grid where the X are the infected senators, the corresponding list is : [[0,5],[1,4],[2,3],[2,1],[3,3],[3,0],[4,5],[0,5]]:

After that the infection begins to spread step by step. Two senators are adjacent if they share a whole edge on the grid (i.e., top,bottom,right,left), which means we exclude diagonals.

We can conclude a senator can be adjacent to 2,3 or 4 other senators and claim the following rules for the infection :

• A senator that has been infected stays infected forever
• A senator is infected at a step if he was adjacent to 2 or more infected senator at the previous step

Here's an example with the previous grid which shows the 2 first steps of the infection :

After the nexts steps all the senate will be infected

YOUR TASK

Your code doesn't need to handle invalid inputs like a list greater than n*n or coordinates that aren't distincts.

Your code will take as input a list of couples of integers (or a binary grid or any other format that suits your language) and an integer n (which can be unnecessary if you use another format than a list) , for instance :

8 [[1,2],[1,1],[7,4],[2,7],[4,3]]

n being the side of the grid which means the grid will be a n*n grid, and the list of couples of integers being the coordinates of the cells of the initally infected senators.

The bottom left of the grid is [0,0] and the top right is [n-1,n-1]. The top left is [0,n-1].

Your code must output an integer :

-1 or a falsy value or an error if the whole grid will never be totally infected or the minimum number of steps required to infect the whole grid

Test cases

6 [[0,5],[1,4],[2,3],[2,1],[3,3],[3,0],[4,5],[5,0]] => 7

4 [[1,1][0,3][1,0][3,0][3,3]] => 9

Remember that this is code-golf, thus the shortest answer in bytes wins !

Answer 1

MATL, 29 28 bytes

tn:"tlY6Z+1>Z|t?@.]]Nl=?l_]&

Input is in the form of a 2D matrix of 1's and 0's

Try it at MATL Online

Explanation

        % Implicitly grab user input as a 2D matrix
t       % Duplicate the inputs
n:      % Count the number of elements in the input (N) and create the array [1...N]
"       % Loop this many times (maximum number of steps we analyze)
  t     % Duplicate the top element
  lY6   % Push the 2D array => [0 1 0; 1 0 1; 0 1 0]
  Z+    % Perform 2D convolution (and maintain the size)
  l>    % Find all values that are >= 2
  Z|    % Perform an element-wise OR with the previous state
  t?    % If all elements are 1's
    @.  % Push the current index and break out of the loop
  ]     % End of if 
]       % End of for loop
Nl=?    % If there is only one element on the stack
  l_    % Push a negative one
]       % End of if statement
&       % Display the top stack element

Answer 2

APL (Dyalog 16.0), 54 characters or 60 bytes

Takes enclosed matrix as argument, returns the step number which completes infection, i.e. 1=is already fully infected. 0=does not fully spread, which is just 1 + the OP's numbers.

54 characters (Unicode):

(≢×0=0∊⊃){(⊢≡f←⊢∨2≤{+/,⍵×3 3⍴0 1}⌺3 3)⊃⍵:⍵⋄(⊂f⊃⍵),⍵}⍣≡

60 bytes (Classic):

(≢×0=0∊⊃){(⊢≡f←⊢∨2≤{+/,⍵×3 3⍴0 1}⎕U233A 3 3)⊃⍵:⍵⋄(⊂f⊃⍵),⍵}⍣≡

⌺ is equivalent to ⎕U233A

Examples' run:

      g←(≢×0=0∊⊃){(⊢≡f←⊢∨2≤{+/,⍵×3 3⍴0 1}⌺3 3)⊃⍵:⍵ ⋄ (⊂f⊃⍵),⍵}⍣≡
      ⎕IO←0
      b←⊂⊖⍉~@(⎕JSON'[[0,5],[1,4],[2,3],[2,1],[3,3],[3,0],[4,5],[5,0]]')⊢0⍴⍨2⍴6
      g b
8
      b←⊂⊖⍉~@(⎕JSON'[[1,1],[0,3],[1,0],[3,0],[3,3]]')⊢0⍴⍨2⍴4
      g b
10

The steps are as follows:

┌─────────────┬─────────────┬─────────────┬─────────────┬─────────────┬─────────────┬─────────────┬─────────────┐
│ X       X   │ X X     X   │ X X X   X   │ X X X X X   │ X X X X X   │ X X X X X   │ X X X X X   │ X X X X X X │
│   X         │ X X X       │ X X X X     │ X X X X X   │ X X X X X   │ X X X X X   │ X X X X X X │ X X X X X X │
│     X X     │   X X X     │ X X X X     │ X X X X     │ X X X X X   │ X X X X X X │ X X X X X X │ X X X X X X │
│             │     X       │   X X X     │ X X X X X   │ X X X X X X │ X X X X X X │ X X X X X X │ X X X X X X │
│     X       │     X X     │     X X X   │   X X X X X │ X X X X X X │ X X X X X X │ X X X X X X │ X X X X X X │
│       X   X │     X X X X │     X X X X │     X X X X │   X X X X X │ X X X X X X │ X X X X X X │ X X X X X X │
└─────────────┴─────────────┴─────────────┴─────────────┴─────────────┴─────────────┴─────────────┴─────────────┘
┌─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┐
│ X     X │ X     X │ X     X │ X     X │ X     X │ X     X │ X   X X │ X X X X │ X X X X │ X X X X │
│         │         │         │         │       X │     X X │   X X X │ X X X X │ X X X X │ X X X X │
│   X     │   X     │   X X   │   X X X │   X X X │   X X X │   X X X │   X X X │ X X X X │ X X X X │
│   X   X │   X X X │   X X X │   X X X │   X X X │   X X X │   X X X │   X X X │   X X X │ X X X X │
└─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┘

Answer 3

Python, 231 bytes

g=input()
q=lambda r,c:g[r][c]if(0<=r<m)*(0<=c<m)else 0
m=len(g);p=t=0;n=range(m)
while not all([r for k in g for r in k]):h=[[g[r][c]or sum([q(r+1,c),q(r-1,c),q(r,c+1),q(r,c-1)])>1 for c in n] for r in n];t+=1;0/(g!=h);g=h
print t

It raises an error if it isn't possible.

Try it online!

Answer 4

Pyth, 49 bytes

J^UE2*lK.uS{+NeMf>hT1r8S@Jsmm+VdkNs_MB_MBU2Q)qJeK

Test suite.

Uses 1-indexing for the output.

Answer 5

JavaScript (ES6), 132 bytes

f=s=>(w=s.search`\n`,t=` `.repeat(w+1),t+=s+t,t=s.replace(/0/g,(_,i)=>1-t[i]-t[i+=w]-t[i+=2]-t[i+w]>>>31),t==s?0/!/0/.test(s):1+f(t))

Where \n represents the literal newline character. Takes input as a string of 0s and 1s in a newline-delimited array. Returns NaN if the grid will never become fully infected.