Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

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.

share|improve this answer
3  
Is this a programming language? – Lynn Mar 20 at 3:14
1  
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 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 at 15:35
1  
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 at 23:23
1  
@CatsAreFluffy You have my upvote then. – lirtosiast Mar 22 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.

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

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>

share|improve this answer
    
Save 2 bytes by writing (y=...)+''==x instead of (y=...),y+''==x. – Neil Mar 20 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
  =~       %   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
share|improve this answer

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

share|improve this answer
1  
I think you can get this to about 100 bytes. First tip: Use a Repeat loop. – lirtosiast Mar 20 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)
share|improve this answer

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.

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

I couldn't (yet) find a way to generate the indices...

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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