There is a virus inside a recipient of 5x5. As we know how it propagates its contamination, your mission is to output the last stage of the contamination.

The recipient

It will be representend as a two dimensional array of 5x5:

Where 1 means a position where the virus has already contaminated, and 0 a position not contaminated.

How the virus propagates

A contaminated position can not be clean.
A clean position will be contaminated in the next stage only if at least two of its adjacent positions (north, east, south and west cells) are contaminated.
The last stage of the contamination occurs when no more clean cells can be contaminated.

Sample

Using as as stage 1 of the contamination the recipient described above, the stage 2 will be:

The stage 3 of the contamination will be:

The stage 4 of the contamination will be:

And the stage 5 (in this example, the last one) will be:

Challenge

Given as input one stage of the contamination, you should output the last stage of the contamination.

You are allowed to write full program or a function. You can take the input as array/list, as separated numbers, or even as string. Chooses the best way that fits to your language.

The shortest answer in bytes wins!

Another test cases

removed

Posted 2016-03-20T01:25:10.913

Reputation: 2 785

1How can 1 0 1 occur in the output? Isn’t the center zero adjacent to two 1s? – Lynn – 2016-03-20T02:19:55.123

@Lynn.. I've updated ;) ... sorry for that – removed – 2016-03-20T02:25:32.740

1Could you add 1 0 0 1 0 \ 0 0 1 0 1 \ 0 0 0 0 0 \ 1 0 0 0 0 \ 0 0 1 0 0 as a test case? – Conor O'Brien – 2016-03-20T02:59:52.297

@CᴏɴᴏʀO'Bʀɪᴇɴ. Added thanks – removed – 2016-03-20T03:05:38.050

2All the test cases so far have only full row and columns finishing empty. I'd suggest 0 1 0 0 0 \ 0 0 0 0 1 \ 0 0 1 0 0 \ 1 0 0 0 0 \ 0 0 0 1 0, which stays unchanged. – xnor – 2016-03-20T08:18:51.540

@xnor. Sorry for the delay, and thanks for the test case, I've added :) – removed – 2016-03-21T01:14:41.193

Answers

Since this is basically talking about a cellular automaton I give you..

Golly Quicklife rule, 10 bytes

01234/234V

Input the rule, paste the grid into Golly, run pattern. The resulting pattern is the output.

Explanation:

01234 Survive on any number of neighbors
     /234 Born on >2 neighbors
         V Only directly adjacent neighbors count

Or if you insist on a full RuleLoader rule, 89 bytes:

@RULE X
@TABLE
n_states:2
neighborhood:vonNeumann
symmetries:permute
011001
011101
011111

Rulename is X, same steps as before.

CalculatorFeline

Posted 2016-03-20T01:25:10.913

Reputation: 2 608

Is this a programming language?

– Lynn – 2016-03-20T03:14:11.927

1Golly Quicklife can simulate B3/S23 which can do anything! ...But it does have strict input format (like the entire program is included in the input (how else would you do it?)). BUT WHY RUIN THE FUN?? – CalculatorFeline – 2016-03-20T03:17:21.140

Well, we just need to wait for a question that boils down to the long-term behavior of a cellular automaton! – CalculatorFeline – 2016-03-20T15:35:04.280

1I have some doubts about the validity. If Golly only displayed the final result, it would be fine, but it also displays intermediate results (unless I'm wrong) – lirtosiast – 2016-03-20T23:23:39.670

It won't (Assuming you're on Golly 2.7 or earlier, OSX10.11) (but it's a bug) And plus WHY RUIN THE FUN?? – CalculatorFeline – 2016-03-21T01:52:43.710

1@CatsAreFluffy You have my upvote then. – lirtosiast – 2016-03-22T00:52:35.723

Slightly better answer to above question: Turn the speed up. – CalculatorFeline – 2017-01-04T20:01:28.110

Python 2, 97 bytes

s=' '*6+input()
exec"s=s[1:]+('1'+s)[sum(s[i]<'1'for i in[-6,-1,1,6])>2or'/'>s];"*980
print s[6:]

Try it online. Input is taken as a quoted string with each row delimited by newlines. The 980 is not optimal and can be replaced with a lower multiple of 35. Since it has no impact on the length of this program, I have left the determination of the lowest safe upper bound as an exercise for the reader.

xsot

Posted 2016-03-20T01:25:10.913

Reputation: 5 069

Requires quotes around input and \n escaped newlines. – CalculatorFeline – 2016-03-20T03:10:44.327

@CatsAreFluffy I believe the Ideone link already clarifies how the input is taken. – xsot – 2016-03-20T03:13:59.537

Input is taken as a quoted string with each row delimited by \n s. – CalculatorFeline – 2016-03-20T03:18:50.187

Alright, I'll edit it to make it less ambiguous. – xsot – 2016-03-20T03:21:17.287

Javascript (ES6), 91 89 87 bytes

As a function which accepts input as an array of numbers or strings.

-2 bytes from Neil (combining assignment of y with string conversion)

-2 bytes (removing variable j)

f=x=>(y=x.map((z,i)=>~(i%5&&x[i-1])+~(i%5<4&x[i+1])+~x[i-5]+~x[i+5]<-5|z))+[]==x?y:f(y)

<!-- Snippet demo with array <-> string conversion for convenience -->
<textarea id="input" cols="10" rows="5">0 0 0 0 1
0 0 0 0 1
0 0 0 1 1
0 0 1 1 1
0 1 1 1 1</textarea>
<button id="submit">Run</button>
<pre id="output"></pre>
<script>
strToArray=x=>x.match(/\d/g)
arrayToStr=x=>([]+x).replace(/(.),(.),(.),(.),(.),*/g, '$1 $2 $3 $4 $5\n')
submit.onclick=_=>output.innerHTML=arrayToStr(f(strToArray(input.value)))
</script>

nderscore

Posted 2016-03-20T01:25:10.913

Reputation: 4 912

Save 2 bytes by writing (y=...)+''==x instead of (y=...),y+''==x. – Neil – 2016-03-20T10:17:49.607

MATL, 22 bytes

tn:"t5Bt!=~2X53$Y+1>Y|

This works in current version (15.0.0) of the language.

Try it online!

Input format is: 2D array with rows separated by semicolons. So the four test cases have the following inputs:

[0 0 0 0 1; 0 0 0 0 1; 0 0 0 1 1; 0 0 1 1 1; 0 1 1 1 1]

[1 1 0 0 1; 0 0 0 0 0; 0 1 0 0 1; 0 0 0 0 0; 1 0 0 0 1]

[1 0 0 0 0; 0 1 0 0 0; 0 0 1 0 0; 0 0 0 1 0; 0 0 0 0 1]

[1 0 0 1 0; 0 0 1 0 1; 0 0 0 0 0; 1 0 0 0 0; 0 0 1 0 0]

Explanation

This repeatedly performs a 2D convolution of the input array with the following mask, which defines which neighbours count as contaminating:

0 1 0
1 0 1
0 1 0

In order to obtain a result the same size as the original array, it is first padded with a frame of zeros and then only the "valid" part of the convolution is kept (i.e. that without edge effects).

A threshold of 2 is applied to the output of the convolution, and the result is element-wise ORed with the original input.

This must be done a sufficient number of times to ensure the final state has been reached. A simple criterion that fulfills this is: iterate as many times as the number of entries in the input array (that is, 25 times in the test cases).

t          % get input 2D array implicitly. Duplicate
n:"        % repeat as many times as elements in the input array
  t        %   duplicate array
  5B       %   number 5 in binary: row vector [1 0 1] 
  t!       %   duplicate and transpose into column
  =~       %   compare for inequality with broadcast. Gives desired mask
  2X53$Y+  %   2D convolution. Output has same size as input 
  1>       %   true for elements equal or greater than 2
  Y|       %   element-wise OR with previous copy of the array
           % end loop. Implicitly display

Luis Mendo

Posted 2016-03-20T01:25:10.913

Reputation: 87 464

TI-BASIC, 151 bytes

Prompt [A]
[A]→[B]
Lbl 0
[B]→[A]
For(Y,1,5
For(X,1,5
DelVar ADelVar BDelVar CDelVar D
If Y>1:[A](Y-1,X→A
If Y<5:[A](Y+1,X→B
If X>1:[A](Y,X-1→C
If X<5:[A](Y,X+1→D
max(A+B+C+D≥2,[A](Y,X→[B](Y,X
End
End
If [A]≠[B]:Goto 0
[B]

Input as [[1,0,0,1,1][1,0,0,0,0]...].

Conor O'Brien

Posted 2016-03-20T01:25:10.913

Reputation: 36 228

1I think you can get this to about 100 bytes. First tip: Use a Repeat loop. – lirtosiast – 2016-03-20T22:44:39.573

Lua, 236 bytes

s=arg[1]u=s.sub while p~=s do p=s s=s:gsub("(%d)()",function(d,p)t=0 t=t+((p-2)%6>0 and u(s,p-2,p-2)or 0)t=t+(p-7>0 and u(s,p-7,p-7)or 0)t=t+(p+5<30 and u(s,p+5,p+5)or 0)t=t+(p%6>0 and u(s,p,p)or 0)return t>1 and 1 or d end)end print(s)

Accepts input on the command line, and uses Lua's string manipulation to get the answer.

Ungolfed:

s=arg[1]
u=s.sub
while p~=s do
    p=s
    s=s:gsub("(%d)()", function(d, p)
                 t=0
                 t=t+((p-2)%6>0 and u(s,p-2,p-2)or 0)
                 t=t+(p-7>0 and u(s,p-7,p-7)or 0)
                 t=t+(p+5<30 and u(s,p+5,p+5)or 0)
                 t=t+(p%6>0 and u(s,p,p)or 0)
                 return t>1 and 1 or d
    end)
end
print(s)

Trebuchette

Posted 2016-03-20T01:25:10.913

Reputation: 1 692

APL, 76 72 70 bytes

{⍵∨1<¯1 ¯1↓1 1↓↑+/(1 0)(¯1 0)(0 ¯1)(0 1){⍺[1]⊖⍺[2]⌽⍵}¨⊂¯1⊖¯1⌽7 7↑⍵}⍣≡

What this does is: expand the matrix to a 7x7 one, then center our argument (omega). From this matrix, generate 4 "child" matrices, each one shifted in a different direction (up/down/left/right), add them together (so we get the number of neighbours), drop the frame (to go back to a 5x5 matrix). Or this new matrix with the "old" one, to make sure we didn't drop any cells in the process (i.e. at the edge). Then, use the ⍣≡ combination to get to a fixed-point value.

{⍵∨1<¯1 ¯1↓1 1↓↑+/(1 0)(¯1 0)(0 ¯1)(0 1){⍺[1]⊖⍺[2]⌽⍵}¨⊂¯1⊖¯1⌽7 7↑⍵}⍣≡
                                                             7 7↑⍵    ⍝ Expand the matrix
                                                       ¯1⊖¯1⌽         ⍝ Center the original matrix
                  (1 0)(¯1 0)(0 ¯1)(0 1){⍺[1]⊖⍺[2]⌽⍵}¨⊂               ⍝ Construct 4 child matrices, each offset from the original one by the values on the left of {}
                +/                                                    ⍝ Sum each matrix into one giant matrix
               ↑                                                      ⍝ Mix
     ¯1 ¯1↓1 1↓                                                       ⍝ Transform the 7x7 matrix back to a 5x5 matrix
   1<                                                                 ⍝ Check which elements are smaller than 1
 ⍵∨                                                                   ⍝ "Or" this matrix and the generated matrix
{                                                                 }⍣≡ ⍝ Find the fixpoint

example (considering the function was assigned to contaminate):

          stage ⍝ the base matrix
0 0 0 0 1
0 0 0 0 1
0 0 0 1 1
0 0 1 1 1
0 1 1 1 1
      contaminate stage ⍝ apply the function
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1

Ven

Posted 2016-03-20T01:25:10.913

Reputation: 3 382

The last stage of contamination

The recipient

How the virus propagates

Sample

Challenge

Another test cases

Answers

Golly Quicklife rule, 10 bytes

Python 2, 97 bytes

Javascript (ES6), 91 89 87 bytes

MATL, 22 bytes

Explanation

TI-BASIC, 151 bytes

Lua, 236 bytes

APL, 76 72 70 bytes