Antes de comenzar, este desafío no era mío originalmente
Créditos a la Universidad de Waterloo. Esto vino de Canadian Computing Competition 2016, Senior Problema 5. Aquí hay un enlace en el que se puede hacer clic en el concurso PDF:
http://cemc.uwaterloo.ca/contests/computing/2016/stage%201/seniorEn.pdf
Aquí hay un enlace al sitio:
http://cemc.uwaterloo.ca/contests/past_contests.html
Desafío
Dada una matriz envolvente de dos valores constantes, determine la configuración después de las n
evoluciones para la entrada entera positiva n
. Estos dos valores representan una célula viva y una célula muerta. Las evoluciones funcionan así:
¡Evolución!
Después de cada iteración, una celda está viva si tenía exactamente un vecino vivo en la iteración anterior. Menos y muere de soledad; más y se muere de hacinamiento. El vecindario es exclusivo: es decir, cada celda tiene dos vecinos, no tres.
Por ejemplo, veamos cómo 1001011010
evolucionaría, dónde 1
hay una célula viva y 0
una célula muerta.
(0) 1 0 0 1 0 1 1 0 1 0 (1)
* $ %
La celda en el *
tiene una celda muerta a ambos lados, por lo que muere de soledad.
La celda en el $
tiene una celda viva en un lado y una celda muerta en el otro. Se vuelve vivo.
El cel en el %
tiene una celda viva a ambos lados, por lo que permanece muerto por hacinamiento.
Criterios ganadores
El código más corto gana.
I / O
La entrada será una lista de los estados de las celdas como dos valores consistentes y un número entero que representa el número de entradas, en algún formato razonable. La salida debe ser una lista de los estados de las celdas después del número especificado de iteraciones.
Casos de prueba
start, iterations -> end
1001011010, 1000 -> 1100001100
100101011010000, 100 -> 000110101001010
0000000101011000010000010010001111110100110100000100011111111100111101011010100010110000100111111010, 1000 -> 1001111111100010010100000100100100111010010110001011001101010111011011011100110110100000100011011001
Caso de
prueba Este caso de prueba congeló hastebin y excedió el límite de tamaño de pastebin
fuente
Theta(nt)
dónden
está la longitud de la matriz yt
es el número de evoluciones; toma un algoritmo más rápidoTheta(n lg t)
.Respuestas:
APL (Dyalog) , 14 bytes
Solicita el estado de inicio como lista booleana y luego el número de iteraciones
Pruébalo en línea!
⎕
solicitud numérica (para la lista booleana del estado de inicio)⊢
sobre eso, aplicar(
...)⍣⎕
la siguiente función tácita, tiempos de solicitud numérica¯1∘⌽
el argumento giró un paso a la derecha≠
diferente de (XOR)1∘⌽
el argumento giró un paso a la izquierdafuente
Jalea , 7 bytes
Pruébalo en línea!
Caso de prueba adicional (pie de página para formatear) .
Explicación
fuente
05AB1E , 6 bytes
Pruébalo en línea!
Explicación
fuente