L'étrange vie d'une ruche

Les chercheurs ont récemment découvert une colonie d'abeilles intéressante qui vit dans un champ infini de nids d'abeilles:

Chaque cellule peut héberger une abeille ou non. En fait, la vie de ces créatures semble être un peu ... chaotique. On pourrait calculer qu'une colonie commence toujours par le modèle suivant:

_{(Abeille dessinée par Emmanuel Boutet sur Wikimedia Commons . Cette image en nid d'abeille est donc publiée sous CC-By-SA . Grommelle )}

Après cela, les cycles de vie de l'abeille sont divisés en soi-disant générations. Chaque génération d'abeilles meurent et de nouvelles éclosent et cela dépend principalement des voisins de leur cellule:

• Si une abeille a moins de deux voisins, elle meurt à cause de la solitude.
• Si une abeille a plus de trois voisins, elle meurt à cause du surpeuplement.
• Si une cellule a deux, trois ou quatre abeilles vivantes dans les cellules voisines, une nouvelle abeille éclosera dans la prochaine génération.

Les abeilles mourantes ne meurent pas avant la fin d'une génération, elles affectent donc toujours les cellules environnantes qui pourraient éclore des abeilles dans la génération suivante.

Maintenant que nous savons comment fonctionne une telle colonie, nous pouvons la simuler à travers un certain nombre de générations.

Contribution

L'entrée est un seul nombre N , donné sur l'entrée standard, terminé par un saut de ligne. 0 ≤ N ≤ 150. Il s'agit du nombre de générations à simuler.

Production

La sortie est un nombre unique, sur la sortie standard et éventuellement suivi d'un saut de ligne unique, qui représente le nombre d'abeilles vivantes après N générations.

La sortie supplémentaire sur l'erreur standard est ignorée.

Exemples d'entrées

0
5
42
100

Exemples de sorties

6
44
1029
5296

Condition gagnante

Le code le plus court gagne, comme c'est la coutume dans le golf. En cas d'égalité, la solution précédente l'emporte.

Cas de test

Il existe deux scripts de test, contenant des cas de test identiques:

• frapper
• PowerShell

L'invocation est dans les deux cas:, <test script> <my program> [arguments]par exemple ./test ruby beehive.rbou ./test.ps1 ./beehive.exe.

Je sais qu'il n'y a que 22 tests au lieu de 151 (principalement parce que les solutions sont souvent assez lentes). Veuillez vous abstenir d'incorporer les cas de test exacts au lieu de résoudre la tâche. Ces scripts vous permettent de tester si une modification entraîne toujours le comportement correct du programme; pas que vous puissiez adapter votre code aux cas de test spécifiques.

Une autre note

Cette tâche faisait partie d'un concours de golf organisé dans mon université en 2011-S24. Les scores et les langues de nos candidats étaient les suivants:

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

Notre propre solution était

• 230 - Rubis

Ruby, 181 163 153 153 146 caractères

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

Cette implémentation suit une approche standard utilisant un tableau h(dimensions 200x 200aplati), où chaque élément est soit 0(pas d'abeille) ou 1(abeille incluse). Le tableau [0,-200,201,202,2,3]décrit les positions initiales des abeilles (par rapport à n'importe quelle cellule initiale).

L'entrée et la sortie, comme spécifié ci-dessus, réussissent tous les cas de test définis.

Édition 1: reconvertie en une solution d'encapsulation au lieu de la version "espace supplémentaire" (qui était plus courte dans une version intermédiaire mais qui a maintenant plusieurs caractères de plus).

Edit 2: variable supprimée bcomplètement.

Édition 3: avertissement: cette édition a rendu le programme horriblement lent. J'ai ainsi réduit les dimensions à 200 chacune ce qui est encore suffisant pour jusqu'à 150 itérations. Au lieu d'indexer le tableau par une variable, nous tournons constamment le tableau vers l'avant. Pas vraiment un bon design, mais maintenant nous sommes considérablement en dessous du 150.

Python, 152 caractères

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)

Cette solution garde la trace des emplacements des abeilles avec un ensemble de nombres complexes. C'est assez lent car la boucle intérieure est quadratique en nombre d'abeilles. J'ai testé jusqu'à 50 et ça marche.

Python, 171 169 158 158 caractères

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)

Je modélise le monde comme un tableau 300 * 300 = 900000 1D ( hest en fait plus grand, mais la fin n'est pas utilisée), où une abeille est un 1 et vide est 0. La taille de 300 est bien parce que tout au plus la croissance serait de 2 dans chaque dimension pour chaque génération, et il n'y a pas plus de 150 générations.

Voici une version légèrement non golfée et commentée:

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)