A última etapa da contaminação

10

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
removido
fonte
11
Como pode 1 0 1ocorrer na saída? O zero do centro não é adjacente a dois 1s?
Lynn
@Lynn .. Eu atualizei;) ... desculpe por isso
removido
11
Você poderia adicionar 1 0 0 1 0 \ 0 0 1 0 1 \ 0 0 0 0 0 \ 1 0 0 0 0 \ 0 0 1 0 0como um caso de teste?
Conor O'Brien
@ CᴏɴᴏʀO'Bʀɪᴇɴ. Adicionado agradecimentos
removido
2
Até agora, todos os casos de teste têm apenas a linha completa e as colunas terminando vazias. Eu sugiro 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, que permanece inalterado.
Xnor

Respostas:

12

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.

CalculatorFeline
fonte
3
Esta é uma linguagem de programação ?
Lynn
11
Golly Quicklife pode simular o B3/S23que pode fazer qualquer coisa! ... Mas ele tem um formato de entrada estrito (como o programa inteiro está incluído na entrada (de que outra forma você faria isso?)). Mas por que estragar a diversão ??
CalculatorFeline
Bem, só precisamos esperar por uma pergunta que se resume ao comportamento de longo prazo de um autômato celular!
CalculatorFeline
11
Eu tenho algumas dúvidas sobre a validade. Se Golly exibido apenas o resultado final, que seria bom, mas também exibe resultados intermediários (a menos que eu esteja errado)
lirtosiast
11
@CatsAreFluffy Você tem o meu voto positivo então.
lirtosiast
5

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.

xsot
fonte
Requer aspas ao redor da entrada e \ n novas linhas de escape.
CalculatorFeline
@CatsAreFluffy Acredito que o link Ideone já esclareça como a entrada é recebida.
Xsot #
A entrada é tomada como uma string entre aspas, com cada linha delimitada por \ n s.
CalculatorFeline
Tudo bem, eu vou editá-lo para torná-lo menos ambíguo.
xsot
3

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>

nderscore
fonte
Salve 2 bytes escrevendo em (y=...)+''==xvez de (y=...),y+''==x.
Neil
2

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
Luis Mendo
fonte
1

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

Conor O'Brien
fonte
11
Eu acho que você pode obter isso para cerca de 100 bytes. Primeira dica: use um Repeatloop.
lirtosiast
1

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)
Trebuchette
fonte
1

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
Ven
fonte