Há um vírus dentro de um destinatário de 5x5. Como sabemos como ele propaga sua contaminação, sua missão é produzir o último estágio da contaminação.

O destinatário

Será representado como uma matriz bidimensional de 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

Onde 1significa uma posição em que o vírus já está contaminado e 0uma posição não contaminada.

Como o vírus se propaga

1. Uma posição contaminada não pode estar limpa.
2. Uma posição limpa será contaminada no estágio seguinte somente se pelo menos duas de suas posições adjacentes (células norte, leste, sul e oeste) estiverem contaminadas.
3. O último estágio da contaminação ocorre quando não é possível contaminar mais células limpas.

Amostra

Usando como estágio 1 da contaminação o recipiente descrito acima, o estágio 2 será:

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

O estágio 3 da contaminação será:

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

O estágio 4 da contaminação será:

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

E o estágio 5 (neste exemplo, o último) será:

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

Desafio

Como entrada em um estágio da contaminação, você deve gerar o último estágio da contaminação.

Você tem permissão para escrever um programa completo ou uma função. Você pode usar a entrada como matriz / lista, como números separados ou mesmo como sequência. Escolhe a melhor maneira que se ajusta ao seu idioma.

A resposta mais curta em bytes vence!

Outros casos de teste

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

Já que isso é basicamente um autômato celular, eu te dou ...

Regra Golly Quicklife, 10 bytes

01234/234V

Insira a regra, cole a grade no Golly, padrão de execução. O padrão resultante é a saída.

Explicação:

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

Ou, se você insistir em uma regra completa do RuleLoader, 89 bytes:

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

Nome da regra é X, as mesmas etapas de antes.

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

Experimente online . A entrada é tomada como uma cadeia de caracteres entre aspas, com cada linha delimitada por novas linhas. O 980não é o ideal e pode ser substituído por um múltiplo menor de 35. Como não tem impacto na duração deste programa, deixei a determinação do limite superior seguro mais baixo como um exercício para o leitor.

Javascript (ES6), 91 89 87 bytes

Como uma função que aceita entrada como uma matriz de números ou seqüências de caracteres.

-2 bytes de Neil (combinando atribuição de ycom conversão de string)

-2 bytes (removendo variável 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>

MATL , 22 bytes

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

Isso funciona na versão atual (15.0.0) do idioma.

Experimente online !

O formato de entrada é: matriz 2D com linhas separadas por ponto e vírgula. Portanto, os quatro casos de teste têm as seguintes entradas:

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

Explicação

Isso executa repetidamente uma convolução 2D da matriz de entrada com a seguinte máscara, que define quais vizinhos contam como contaminantes:

0 1 0
1 0 1
0 1 0

Para obter um resultado do mesmo tamanho da matriz original, ele é preenchido primeiro com um quadro de zeros e, em seguida, apenas a parte "válida" da convolução é mantida (isto é, sem efeitos de borda).

Um limite de 2 é aplicado à saída da convolução e o resultado é ORed a nível dos elementos com a entrada original.

Isso deve ser feito um número suficiente de vezes para garantir que o estado final seja alcançado. Um critério simples que atende a isso é: itere quantas vezes o número de entradas na matriz de entrada (ou seja, 25 vezes nos casos de teste).

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

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]

Entrada como [[1,0,0,1,1][1,0,0,0,0]...].

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)

Aceita entrada na linha de comando e usa a manipulação de strings de Lua para obter a resposta.

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, 76 72 70 bytes

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

O que isso faz é: expanda a matriz para 7x7 e centralize nosso argumento (ômega). A partir dessa matriz, gere 4 matrizes "filho", cada uma delas deslocada em uma direção diferente (para cima / baixo / esquerda / direita), adicione-as (para obter o número de vizinhos), solte o quadro (para retornar a uma Matriz 5x5). Ou essa nova matriz com a "antiga", para garantir que não deixamos cair nenhuma célula no processo (ou seja, no limite). Em seguida, use a ⍣≡combinação para obter um valor de ponto fixo.

{⍵∨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

exemplo (considerando que a função foi atribuída 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