Dziwne życie ula

Naukowcy odkryli niedawno ciekawą kolonię pszczół, która żyje w nieskończonej dziedzinie plastra miodu:

Każda komórka może pomieścić pszczołę lub nie. W rzeczywistości życie tych stworzeń wydaje się być trochę ... chaotyczne. Można obliczyć, że kolonia zawsze zaczyna się od następującego wzoru:

_{(Pszczoła narysowana przez Emmanuela Bouteta na Wikimedia Commons . Ten obraz o strukturze plastra miodu i pszczół został wydany na licencji CC-By-SA . Narzeka )}

Następnie cykle życia pszczoły dzielą się na tak zwane pokolenia. Z każdym pokoleniem stare pszczoły giną, a nowe wykluwają się i zależy to przede wszystkim od sąsiadów ich komórek:

• Jeśli pszczoła ma mniej niż dwóch sąsiadów, umiera z powodu samotności.
• Jeśli pszczoła ma więcej niż trzech sąsiadów, umiera z powodu przeludnienia.
• Jeśli komórka ma dwie, trzy lub cztery żywe pszczoły w sąsiednich komórkach, wykluwa się tam nowa pszczoła w następnym pokoleniu.

Umierające pszczoły nie umierają do końca pokolenia, więc nadal wpływają na otaczające komórki, które mogą wykluć się w następnym pokoleniu.

Teraz, gdy wiemy, jak działa taka kolonia, możemy ją symulować przez wiele pokoleń.

Wejście

Wejście to pojedyncza liczba N , podana na standardowym wejściu, zakończona przerwaniem linii. 0 ≤ N ≤ 150. Jest to liczba pokoleń do symulacji.

Wynik

Wyjście to pojedyncza liczba, na standardowym wyjściu i opcjonalnie po niej następuje pojedyncza przerwa, która reprezentuje liczbę żywych pszczół po N pokoleniach.

Dodatkowe dane wyjściowe dotyczące błędu standardowego są ignorowane.

Przykładowe dane wejściowe

0
5
42
100

Przykładowe wyniki

6
44
1029
5296

Warunki wygranej

Wygrywa najkrótszy kod, jak to zwykle jest w golfie. W przypadku remisu wygrywa wcześniejsze rozwiązanie.

Przypadki testowe

Istnieją dwa skrypty testowe, zawierające identyczne przypadki testowe:

• grzmotnąć
• PowerShell

Wywołanie jest w obu przypadkach: <test script> <my program> [arguments]np . ./test ruby beehive.rbLub ./test.ps1 ./beehive.exe.

Wiem, że są tylko 22 testy zamiast 151 (głównie dlatego, że rozwiązania są często dość powolne). Proszę powstrzymać się od osadzania dokładnych przypadków testowych zamiast rozwiązywania zadania. Te skrypty są dla Ciebie wygodnym narzędziem do testowania, czy zmiana nadal powoduje prawidłowe działanie programu; nie że możesz dostosować swój kod do konkretnych przypadków testowych.

Kolejna uwaga

To zadanie było częścią konkursu golfowego, który odbył się na mojej uczelni w latach 2011-W24. Wyniki i języki naszych zawodników były następujące:

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

Nasze własne rozwiązanie było

• 230 - Rubinowy

Ruby, 181 163 153 146 znaków

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

Ta implementacja jest zgodna ze standardowym podejściem przy użyciu tablicy h(wymiary 200x 200spłaszczone), gdzie każdy element to 0(brak pszczoły) lub 1(pszczoła włącznie). Tablica [0,-200,201,202,2,3]opisuje początkowe pozycje pszczół (względem dowolnej początkowej komórki).

Dane wejściowe i wyjściowe, jak określono powyżej, przechodzą wszystkie zdefiniowane przypadki testowe.

Edycja 1: zmieniono z powrotem na rozwiązanie owijania zamiast wersji „dodatkowej przestrzeni” (która była krótsza w wersji pośredniej, ale teraz jest o kilka znaków dłuższa).

Edycja 2:b całkowicie usunięto zmienną .

Edycja 3: ostrzeżenie: ta edycja spowolniła program. W ten sposób zmniejszyłem wymiary do 200, co wciąż wystarcza na 150 powtórzeń. Zamiast indeksować tablicę zmienną, stale obracamy tablicę do przodu. Niezbyt dobry projekt, ale teraz jesteśmy znacznie poniżej 150.

Python, 152 znaki

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)

To rozwiązanie śledzi lokalizacje pszczół za pomocą zestawu liczb zespolonych. Jest dość wolny, ponieważ wewnętrzna pętla jest kwadratowa pod względem liczby pszczół. Testowałem do 50 i działa.

Python, 171 169 158 znaków

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)

Modeluję świat jako macierz 300 * 300 = 900000 1D ( hjest właściwie większa, ale koniec nie jest używany), gdzie pszczoła ma wartość 1, a pusta wynosi 0. Rozmiar 300 jest w porządku, ponieważ co najwyżej wzrost byłby 2 w każdym wymiarze dla każdego pokolenia, a nie ma więcej niż 150 pokoleń.

Oto nieco niepoznana i skomentowana wersja:

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)