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\$ – Antoine 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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.