12
\$\begingroup\$

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

enter image description here

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 :

enter image description here

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

\$\endgroup\$
  • 1
    \$\begingroup\$ Related post on Mathematica.SE. \$\endgroup\$ – Martin Ender May 3 '17 at 18:22
  • \$\begingroup\$ Related \$\endgroup\$ – Beta Decay May 3 '17 at 18:41
  • \$\begingroup\$ What's the minimum value of n? Is there a max value? \$\endgroup\$ – mbomb007 May 3 '17 at 18:44
  • \$\begingroup\$ @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 \$\endgroup\$ – user68509 May 3 '17 at 18:46
  • 2
    \$\begingroup\$ Looks like a job for Mathematica's CellularAutomaton... \$\endgroup\$ – mbomb007 May 3 '17 at 18:48
2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ @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" \$\endgroup\$ – Suever May 3 '17 at 21:40
  • \$\begingroup\$ 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 \$\endgroup\$ – Luis Mendo May 3 '17 at 21:57
3
\$\begingroup\$

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 │
└─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┘
\$\endgroup\$
2
\$\begingroup\$

Pyth, 49 bytes

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

Test suite.

Uses 1-indexing for the output.

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ 0/0 saves two bytes from raise. Maybe 1/(g!=h) would work? (then the whole while could be inlined too). \$\endgroup\$ – Jonathan Allan May 3 '17 at 22:24
  • \$\begingroup\$ @JonathanAllan I updated it, thanks for the input. \$\endgroup\$ – Neil May 3 '17 at 22:45
  • \$\begingroup\$ 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. \$\endgroup\$ – Jonathan Allan May 3 '17 at 22:59
  • \$\begingroup\$ @JonathanAllan Updated again. Thanks \$\endgroup\$ – Neil May 3 '17 at 23:01
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy