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:
Wywołanie jest w obu przypadkach: <test script> <my program> [arguments]
np . ./test ruby beehive.rb
Lub ./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
Odpowiedzi:
Ruby,
181163153146 znakówTa implementacja jest zgodna ze standardowym podejściem przy użyciu tablicy
h
(wymiary200
x200
spłaszczone), gdzie każdy element to0
(brak pszczoły) lub1
(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.
źródło
Python, 152 znaki
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.
źródło
P={0,2,3,1j,1+1j,1-1j}
a następnie używać{p}<P
do testowania członkostwa (zapisuje 1 znak)Python,
171169158 znakówModeluję świat jako macierz 300 * 300 = 900000 1D (
h
jest 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:
źródło