# The last stage of contamination

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:

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


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

### How the virus propagates

1. A contaminated position can not be clean.
2. 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.
3. 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:

0 0 0 0 1
0 0 0 1 1
0 0 1 1 1
0 1 1 1 1
0 1 1 1 1


The stage 3 of the contamination will be:

0 0 0 1 1
0 0 1 1 1
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1


The stage 4 of the contamination will be:

0 0 1 1 1
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1


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

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


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

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

Output:
1 1 0 0 1
1 1 0 0 1
1 1 0 0 1
1 1 0 0 1
1 1 0 0 1


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

Output:
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1


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

Output:
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1


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

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

• How can 1 0 1 occur in the output? Isn’t the center zero adjacent to two 1s? – Lynn Mar 20 '16 at 2:19
• @Lynn.. I've updated ;) ... sorry for that – removed Mar 20 '16 at 2:25
• Could 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 Mar 20 '16 at 2:59
• @CᴏɴᴏʀO'Bʀɪᴇɴ. Added thanks – removed Mar 20 '16 at 3:05
• All 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 Mar 20 '16 at 8:18

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.

• Is this a programming language? – Lynn Mar 20 '16 at 3:14
• Golly 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 Mar 20 '16 at 3:17
• Well, we just need to wait for a question that boils down to the long-term behavior of a cellular automaton! – CalculatorFeline Mar 20 '16 at 15:35
• I 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 Mar 20 '16 at 23:23
• @CatsAreFluffy You have my upvote then. – lirtosiast Mar 22 '16 at 0:52

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

• Requires quotes around input and \n escaped newlines. – CalculatorFeline Mar 20 '16 at 3:10
• @CatsAreFluffy I believe the Ideone link already clarifies how the input is taken. – xsot Mar 20 '16 at 3:13
• Input is taken as a quoted string with each row delimited by \n s. – CalculatorFeline Mar 20 '16 at 3:18
• Alright, I'll edit it to make it less ambiguous. – xsot Mar 20 '16 at 3:21

# Javascript (ES6), 9189 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> • Save 2 bytes by writing (y=...)+''==x instead of (y=...),y+''==x. – Neil Mar 20 '16 at 10:17 # 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
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


# TI-BASIC, 151 bytes

Prompt [A]
[A]→[B]
Lbl 0
[B]→[A]
For(Y,1,5
For(X,1,5
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]...].

• I think you can get this to about 100 bytes. First tip: Use a Repeat loop. – lirtosiast Mar 20 '16 at 22:44

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


# APL, 7672 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