# May the fourth be with flu

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 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 , thus the shortest answer in bytes wins !

• Related post on Mathematica.SE. – Martin Ender May 3 '17 at 18:22
• Related – Beta Decay May 3 '17 at 18:41
• What's the minimum value of n? Is there a max value? – mbomb007 May 3 '17 at 18:44
• @mbomb007 there's no max value in theory but it should be computable. For the minimum value I'd say 1 which outputs 0 or -1 – user68509 May 3 '17 at 18:46
• Looks like a job for Mathematica's CellularAutomaton... – mbomb007 May 3 '17 at 18:48

# 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

• @LuisMendo Unfortunately I don't think so because there are some 0's in the output of the convolution which would become -1 and therefore be "true" – Suever May 3 '17 at 21:40
• How about tn:"tlY6Z+1>Z|t?x@D.]]N?xl_? (I'm haven't tested much). If all elements are 1 at some point, display the loop index immediately and delete stack. At the end of the loop, if the stack is non-empty delete and push -1 – Luis Mendo May 3 '17 at 21:57

# 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 │
└─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┘


# Pyth, 49 bytes

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


Uses 1-indexing for the output.

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

• 0/0 saves two bytes from raise. Maybe 1/(g!=h) would work? (then the whole while could be inlined too). – Jonathan Allan May 3 '17 at 22:24
• @JonathanAllan I updated it, thanks for the input. – Neil May 3 '17 at 22:45
• q=lambda r,c:g[r][c]if(0<=r<m)*(0<=c<m)else 0 saves 12. You can remove the space between (a) 1 and for and (b) ] and for too. – Jonathan Allan May 3 '17 at 22:59
• @JonathanAllan Updated again. Thanks – Neil May 3 '17 at 23:01

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