Das seltsame Leben eines Bienenstocks

Forscher entdeckten kürzlich eine interessante Bienenkolonie, die in einem unendlichen Wabenfeld lebt:

Jede Zelle kann eine Biene beherbergen oder nicht. Tatsächlich scheint das Leben dieser Kreaturen ein bisschen ... chaotisch zu sein. Es könnte berechnet werden, dass eine Kolonie immer mit dem folgenden Muster beginnt:

_{(Biene gezeichnet von Emmanuel Boutet auf Wikimedia Commons . Dieses Waben-Bienen-Bild wird also unter CC-By-SA veröffentlicht . Murren )}

Danach werden die Lebenszyklen der Bienen in sogenannte Generationen unterteilt. Jede Generation alter Bienen stirbt und neue schlüpfen, und das hängt in erster Linie von den Nachbarn ihrer Zelle ab:

• Wenn eine Biene weniger als zwei Nachbarn hat, stirbt sie an Einsamkeit.
• Wenn eine Biene mehr als drei Nachbarn hat, stirbt sie an Überfüllung.
• Wenn eine Zelle zwei, drei oder vier lebende Bienen in benachbarten Zellen hat, schlüpft dort in der nächsten Generation eine neue Biene.

Sterbende Bienen sterben erst am Ende einer Generation ab, daher wirken sie sich immer noch auf umliegende Zellen aus, die Bienen in der nächsten Generation ausbrüten könnten.

Jetzt, da wir wissen, wie eine solche Kolonie funktioniert, können wir sie über eine beliebige Anzahl von Generationen simulieren.

Eingang

Die Eingabe ist eine einzelne Zahl N , die bei der Standardeingabe angegeben wird und durch einen Zeilenumbruch abgeschlossen wird. 0 ≤ N ≤ 150. Dies ist die Anzahl der zu simulierenden Generationen.

Ausgabe

Die Ausgabe ist eine einzelne Zahl in der Standardausgabe und optional gefolgt von einem einzelnen Zeilenumbruch, der die Anzahl der lebenden Bienen nach N Generationen darstellt.

Zusätzliche Ausgabe bei Standardfehler wird ignoriert.

Beispieleingaben

0
5
42
100

Beispielausgaben

6
44
1029
5296

Gewinnbedingung

Der kürzeste Code gewinnt, wie es im Golf üblich ist. Bei einem Gleichstand gewinnt die frühere Lösung.

Testfälle

Es gibt zwei Testskripte mit identischen Testfällen:

• Bash
• Power Shell

Der Aufruf erfolgt in beiden Fällen: <test script> <my program> [arguments]zB ./test ruby beehive.rboder ./test.ps1 ./beehive.exe.

Ich weiß, dass es statt 151 nur 22 Tests gibt (hauptsächlich, weil Lösungen oft sehr langsam sind). Bitte unterlassen Sie es, die genauen Testfälle einzubetten, anstatt die Aufgabe zu lösen. Mit diesen Skripten können Sie bequem testen, ob das Programm nach einer Änderung immer noch korrekt reagiert. nicht, dass Sie Ihren Code an die spezifischen Testfälle anpassen können.

Noch ein Hinweis

Diese Aufgabe war Teil eines Golfwettbewerbs an meiner Universität im Zeitraum 2011-24. Die Partituren und Sprachen unserer Teilnehmer waren wie folgt:

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

Unsere eigene Lösung war

• 230 - Rubin

Ruby, 181 163 153 146 Zeichen

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

Diese Implementierung folgt einem Standardansatz unter Verwendung eines Arrays h(Abmessungen 200x 200abgeflacht), wobei jedes Element entweder 0(keine Biene) oder 1(Biene eingeschlossen) ist. Das Array [0,-200,201,202,2,3]beschreibt die Anfangspositionen der Bienen (relativ zu jeder Anfangszelle).

Eingabe und Ausgabe wie oben angegeben bestehen alle definierten Testfälle.

Edit 1: Zurück zu einer Wrapping-Lösung anstelle der "Additional Space" -Version (die in einer Zwischenversion kürzer war, jetzt aber mehrere Zeichen länger ist).

Edit 2: Variable bkomplett entfernt.

Edit 3: Warnung: Diese Bearbeitung hat das Programm fürchterlich langsam gemacht. So habe ich die Abmessungen auf jeweils 200 reduziert, was noch für bis zu 150 Iterationen ausreicht. Anstatt das Array durch eine Variable zu indizieren, drehen wir das Array ständig vorwärts. Nicht wirklich gutes Design, aber jetzt sind wir deutlich unter den 150.

Python, 152 Zeichen

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)

Diese Lösung verfolgt Bienenstandorte mit einer Reihe komplexer Zahlen. Es ist ziemlich langsam, weil die innere Schleife in der Anzahl der Bienen quadratisch ist. Ich habe bis zu 50 getestet und es funktioniert.

Python, 171 169 158 Zeichen

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)

Ich modelliere die Welt als 300 * 300 = 900000 1D-Array ( hist tatsächlich größer, aber das Ende wird nicht verwendet), wobei eine Biene eine 1 und leer eine 0 ist. Die Größe von 300 ist in Ordnung, weil höchstens das Wachstum von wäre 2 in jeder Dimension für jede Generation, und es gibt nicht mehr als 150 Generationen.

Hier ist eine leicht ungolfederte und kommentierte Version:

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)