La extraña vida de una colmena

Los investigadores descubrieron recientemente una interesante colonia de abejas que vive en un campo infinito de panal:

Cada celda puede albergar una abeja o no. De hecho, la vida de esas criaturas parece ser un poco ... caótica. Se podría calcular que una colonia siempre comienza con el siguiente patrón:

_{(Abeja dibujada por Emmanuel Boutet en Wikimedia Commons . Esta imagen de nido de abeja y abejas se publica bajo CC-By-SA . Gruñe )}

Después de eso, los ciclos de vida de la abeja se dividen en las llamadas generaciones. Cada generación de abejas viejas mueren y las nuevas eclosionan y depende principalmente de los vecinos de sus células:

• Si una abeja tiene menos de dos vecinos, muere debido a la soledad.
• Si una abeja tiene más de tres vecinos, muere debido al hacinamiento.
• Si una célula tiene dos, tres o cuatro abejas vivas en las celdas vecinas, una nueva abeja eclosiona allí en la próxima generación.

Las abejas moribundas no mueren hasta el final de una generación, por lo que aún afectan las células circundantes que podrían eclosionar en la próxima generación.

Ahora que sabemos cómo funciona esa colonia, podemos simularla a través de cualquier cantidad de generaciones.

Entrada

La entrada es un solo número N , dado en la entrada estándar, terminado por un salto de línea. 0 ≤ N ≤ 150. Este es el número de generaciones a simular.

Salida

La salida es un número único, en la salida estándar y opcionalmente seguido de un salto de línea único, que representa el número de abejas vivas después de N generaciones.

Se ignora la salida adicional en el error estándar.

Entradas de muestra

0
5
42
100

Resultados de muestra

6
44
1029
5296

Condición ganadora

El código más corto gana, como es habitual en el golf. En caso de empate, la solución anterior gana.

Casos de prueba

Hay dos scripts de prueba que contienen casos de prueba idénticos:

• golpetazo
• Potencia Shell

La invocación es en ambos casos: <test script> <my program> [arguments]por ejemplo, ./test ruby beehive.rbo ./test.ps1 ./beehive.exe.

Sé que solo hay 22 pruebas en lugar de 151 (principalmente porque las soluciones son a menudo bastante lentas). Abstenerse de incorporar los casos de prueba exactos en lugar de resolver la tarea. Estos scripts son convenientes para que usted pruebe si un cambio aún hace que el programa se comporte correctamente; no es que pueda adaptar su código a los casos de prueba específicos.

Otra nota

Esta tarea fue parte de un concurso de golf celebrado en mi universidad durante 2011-W24. Los puntajes e idiomas de nuestros concursantes fueron los siguientes:

• 336 - C
• 363 - C
• 387 - C
• 389 - Haskell
• 455 - C

Nuestra propia solución fue

• 230 - Rubí

Ruby, 181 163 153 146 caracteres

h=[0]*4e4
[0,-200,201,202,2,3].map{|i|h[i]=1}
gets.to_i.times{h=h.map{[g=1,200,201].map{|x|g+=h[x]+h[-x]};g>5-h.rotate![-1]||g<3?0:1}}
p h.count 1

Esta implementación sigue un enfoque estándar utilizando una matriz h(dimensiones 200x 200aplanado), donde cada elemento es 0(sin abeja) o 1(abeja incluida). La matriz [0,-200,201,202,2,3]describe las posiciones iniciales de las abejas (en relación con cualquier celda inicial).

La entrada y salida como se especifica arriba, pasa todos los casos de prueba definidos.

Edición 1: cambió de nuevo a una solución de ajuste en lugar de la versión "espacio adicional" (que era más corta en una versión intermedia pero ahora tiene varios caracteres más).

Edición 2: variable eliminada por bcompleto.

Edición 3: advertencia: esta edición hizo que el programa fuera terriblemente lento. Por lo tanto, reduje las dimensiones a 200 cada una, lo que aún es suficiente para hasta 150 iteraciones. En lugar de indexar la matriz por una variable, rotamos constantemente la matriz hacia adelante. Realmente no es un buen diseño, pero ahora estamos considerablemente por debajo de los 150.

Python, 152 caracteres

P=[0,2,3,1j,1+1j,1-1j]
for i in' '*input():Q=[p+d for d in(1,-1,1j,-1j,1j-1,1-1j)for p in P];P=set(p for p in Q if 1<Q.count(p)<5-(p in P))
print len(P)

Esta solución realiza un seguimiento de las ubicaciones de las abejas con un conjunto de números complejos. Es bastante lento porque el bucle interno es cuadrático en el número de abejas. He probado hasta 50 y funciona.

Python, 171 169 158 caracteres

w=300
s=w*w
x=[0]*297
h=[1,1,0]+x+[1,0,1,1]+x+[1]+x*s
exec('h=[1<sum(h[(i+x)%s]for x in[-1,-w-1,-w,1,w+1,w])<5-h[i]for i in range(s)];'*input())
print sum(h)

Modelo el mundo como una matriz 1D 300 * 300 = 900000 (en hrealidad es más grande, pero el final no se usa), donde una abeja es un 1 y el vacío es 0. El tamaño de 300 está bien porque a lo sumo el crecimiento sería de 2 en cada dimensión para cada generación, y no hay más de 150 generaciones.

Aquí hay una versión ungolfed y comentada:

w=300 # width and height of the world
s=w*w
# create initial grid
l=[1,1]+[0]*298+[1,0,1,1]+[0]*297+[1]+[0]*s

for k in range(input()):
  h=l[:]

  for i in range(s):

    # for each point, compute the number of neighbors
    n=sum(map(lambda x:h[(i+x)%s],[-1,-w-1,-w,1,w+1,w]))

    # if that number verifies the conditions, put 1 here, if not put 0
    l[i]=1<n<5-h[i]

print sum(l)