La última etapa de contaminación.

10

Hay un virus dentro de un receptor de 5x5. Como sabemos cómo propaga su contaminación, su misión es generar la última etapa de la contaminación.

El recipiente

Se representará como una 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

Donde 1significa una posición donde el virus ya se ha contaminado, y0 una posición no contaminada.

Cómo se propaga el virus

  1. Una posición contaminada no puede estar limpia.
  2. Una posición limpia se contaminará en la siguiente etapa solo si al menos dos de sus posiciones adyacentes (celdas norte, este, sur y oeste) están contaminadas.
  3. La última etapa de la contaminación ocurre cuando no se pueden contaminar más células limpias.

Muestra

Utilizando como la etapa 1 de la contaminación el receptor descrito anteriormente, la etapa 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

La etapa 3 de la contaminación 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

La etapa 4 de la contaminación 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

Y la etapa 5 (en este ejemplo, la última) 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

Desafío

Dada como entrada una etapa de la contaminación, debe dar salida a la última etapa de la contaminación.

Se le permite escribir un programa completo o una función. Puede tomar la entrada como matriz / lista, como números separados o incluso como cadena. Elige la mejor manera que se adapte a tu idioma.

¡La respuesta más corta en bytes gana!

Otros casos de prueba

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
remoto
fuente
1
¿Cómo puede 1 0 1ocurrir en la salida? ¿No es el centro cero adyacente a dos 1s?
Lynn
@ Lynn .. He actualizado;) ... perdón por eso
eliminado
1
¿Podría agregar 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 un caso de prueba?
Conor O'Brien
@ CᴏɴᴏʀO'Bʀɪᴇɴ. Gracias añadidas
eliminado el
2
Todos los casos de prueba hasta ahora solo tienen filas completas y columnas que terminan vacías. Sugeriría 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 se mantiene sin cambios.
xnor

Respuestas:

12

Como básicamente se trata de un autómata celular, te doy ...

Regla Golly Quicklife, 10 bytes

01234/234V

Ingrese la regla, pegue la cuadrícula en Golly, ejecute el patrón. El patrón resultante es la salida.

Explicación:

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

O si insiste en una regla completa de RuleLoader, 89 bytes:

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

Rulename es X, los mismos pasos que antes.

CalculadoraFeline
fuente
3
¿Es este un lenguaje de programación ?
Lynn
1
¡Golly Quicklife puede simular B3/S23qué puede hacer cualquier cosa! ... Pero tiene un formato de entrada estricto (como todo el programa está incluido en la entrada (¿de qué otra forma lo haría?)). ¿Pero por qué arruinar la diversión?
CalculatorFeline
Bueno, ¡solo tenemos que esperar una pregunta que se reduzca al comportamiento a largo plazo de un autómata celular!
CalculatorFeline
1
Tengo algunas dudas sobre la validez. Si Golly solo mostrara el resultado final, estaría bien, pero también muestra resultados intermedios (a menos que me equivoque)
lirtosiast
1
@CatsAreFluffy Entonces tienes mi voto a favor.
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:]

Pruébalo en línea . La entrada se toma como una cadena entre comillas con cada fila delimitada por nuevas líneas. El 980no es óptimo y puede reemplazarse con un múltiplo inferior de 35. Como no tiene impacto en la duración de este programa, he dejado la determinación del límite superior seguro más bajo como ejercicio para el lector.

xsot
fuente
Requiere comillas alrededor de la entrada y \ n líneas nuevas escapadas.
CalculatorFeline
@CatsAreFluffy Creo que el enlace Ideone ya aclara cómo se toma la entrada.
xsot
La entrada se toma como una cadena entre comillas con cada fila delimitada por \ n s.
CalculatorFeline
Muy bien, lo editaré para que sea menos ambiguo.
xsot
3

Javascript (ES6), 91 89 87 bytes

Como una función que acepta la entrada como una matriz de números o cadenas.

-2 bytes de Neil (combinación de asignación de y con conversión de cadena)

-2 bytes (eliminando la 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
fuente
Ahorre 2 bytes escribiendo en (y=...)+''==xlugar de (y=...),y+''==x.
Neil
2

MATL , 22 bytes

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

Esto funciona en la versión actual (15.0.0) del lenguaje.

Pruébalo en línea !

El formato de entrada es: matriz 2D con filas separadas por punto y coma. Entonces los cuatro casos de prueba tienen las siguientes 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]

Explicación

Esto realiza repetidamente una convolución 2D de la matriz de entrada con la siguiente máscara, que define qué vecinos cuentan como contaminantes:

0 1 0
1 0 1
0 1 0

Para obtener un resultado del mismo tamaño que la matriz original, primero se rellena con un marco de ceros y luego solo se mantiene la parte "válida" de la convolución (es decir, sin efectos de borde).

Se aplica un umbral de 2 a la salida de la convolución, y el resultado se ORE por elementos con la entrada original.

Esto debe hacerse un número suficiente de veces para garantizar que se haya alcanzado el estado final. Un criterio simple que cumple esto es: iterar tantas veces como el número de entradas en la matriz de entrada (es decir, 25 veces en los casos de prueba).

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

Ingresar como [[1,0,0,1,1][1,0,0,0,0]...].

Conor O'Brien
fuente
1
Creo que puedes llevar esto a unos 100 bytes. Primer consejo: use un Repeatbucle.
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)

Acepta entradas en la línea de comandos y usa la manipulación de cadenas de Lua para obtener la respuesta.

Sin golf:

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
fuente
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↑⍵}⍣≡

Lo que esto hace es: expandir la matriz a 7x7, luego centrar nuestro argumento (omega). A partir de esta matriz, genere 4 matrices "secundarias", cada una desplazada en una dirección diferente (arriba / abajo / izquierda / derecha), agréguelas (para obtener el número de vecinos), suelte el marco (para volver a un Matriz 5x5). O esta nueva matriz con la "antigua", para asegurarnos de que no hayamos soltado ninguna celda en el proceso (es decir, en el borde). Luego, use la ⍣≡combinación para llegar a un valor de punto fijo.

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

ejemplo (considerando que la función fue asignada a 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
fuente