CCC 2016: Círculo de la vida

8

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 nevoluciones 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 1001011010evolucionaría, dónde 1hay una célula viva y 0una 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

Hiperneutrino
fuente
2
No creo que esto deba etiquetarse como código de golf si el conteo de bytes es simplemente un desempate. Tampoco estoy seguro de si es un buen desempate, ya que el concurso degenerará en una competencia de código de golf si simplemente puede portar respuestas a un lenguaje más conciso para ganar.
Dennis
@ Dennis Correcto, eliminaré la etiqueta. ¿Qué sugieres para el desempate entonces? La sumisión más temprana es otra de mis ideas.
HyperNeutrino
2
Estoy votando como poco claro por el momento, ya que no se sabe qué se entiende por complejidad cuando hay múltiples parámetros.
fiesta
1
@feersum, hay un poco de juego en el algoritmo más rápido . El algoritmo ingenuo toma Theta(nt)dónde nestá la longitud de la matriz y tes el número de evoluciones; toma un algoritmo más rápido Theta(n lg t).
Peter Taylor
1
@ Notts90 Espero que mi última edición lo aclare más.
HyperNeutrino

Respuestas:

6

APL (Dyalog) , 14 bytes

Solicita el estado de inicio como lista booleana y luego el número de iteraciones

(1∘⌽≠¯1∘⌽)⍣⎕⊢⎕

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 izquierda

Adán
fuente
1

05AB1E , 6 bytes

FDÀÀ^Á

Pruébalo en línea!

Explicación

F        # input_1 times do
 D       # duplicate last iteration (input_2 the first iteration)
  ÀÀ     # rotate left twice
    ^    # XOR
     Á   # rotate right
Emigna
fuente