Convey’s Game of Life
Gra w życie zakłada, że mamy planszę o nieskończonych wymiarach. Plansza ta podzielona jest na pola, w podobny sposób jak kartka w kratkę. Każda kratka reprezentuje pole. Każde pole ma dokładnie 8 sąsiadów, osiem kratek wokół.
Każde z pól może być w dwóch stanach. Może być żywe bądź martwe.
W przykładzie powyżej widzisz wycinek planszy na którym mamy żywą komórkę o współrzędnych (1, 3). Oznaczona jest ona czarnym kwadratem.
Gra sprowadza się do przygotowania kolejnych generacji planszy na podstawie jej aktualnego stanu. Kolejna generacja powstaje na podstawie czterech zasad:
- Każda żywa komórka z mniej niż dwoma żywymi sąsiadami umiera w kolejnej generacji z powodu wyludnienia,
- każda żywa komórka z dwoma lub trzema żywymi sąsiadami jest w stanie przetrwać do następnej generacji,
- każda żywa komórka z więcej niż trzema żywymi sąsiadami umiera w kolejnej genracji z powodu przeludnienia,
- każda martwa komórka z dokładnie trzema żywymi sąsiadami staje się żywa w kolejnej generacji.
Zobacz jak te zasady wyglądają na kilku przykładach.
Pobierz opracowania zadań z rozmów kwalifikacyjnych
Przygotowałem rozwiązania kilku zadań algorytmicznych z rozmów kwalifikacyjnych. Rozkładam je na czynniki pierwsze i pokazuję różne sposoby ich rozwiązania. Dołącz do grupy ponad 6147 Samouków, którzy jako pierwsi dowiadują się o nowych treściach na blogu, a prześlę je na Twój e-mail.
Przykład 1.
W tym przykładzie pierwsza generacja planszy zawiera wyłącznie żywą komórkę na pozycji (1, 3). W kolejnej generacji komórka ta ginie ponieważ nie ma dwóch żywych sąsiadów.
Przykład 2.
W tym przykładzie, w pierwszej generacji mamy trzy żywe komórki na pozycjach (1, 2), (2, 2) i (3, 2). W kolejnej generacji dzieje się już trochę więcej:
- Komórka (1, 2) i (3, 2) giną ponieważ mają tylko jednego żywego sąsiada,
- komórka (2, 2) przeżywa ponieważ ma dokładnie dwóch żywych sąsiadów,
- komórki (2, 1) i (2, 3) ożywają ponieważ mają trzech żywych sąsiadów,
- pozostałe komórki pozostają martwe.
Zauważ, że kolejna generacja prowadzi do kształtu podobnego do poprzedniej. W przypadku tego kształtu i kolejnych generacji okazuje się, że zawsze jakieś żywe komórki powstaną na planszy. Kolejne generacje można pokazać przy pomocy animacji:
Kolejne przykłady
Bardziej skomplikowane kształty możesz zobaczyć na filmiku poniżej:
Zadanie do wykonania
Twoim zadaniem jest napisanie gry w życie.
Aby trochę ułatwić wizualizację, nie będziemy implementowali nieskończonej planszy. Zodyfikujemy wymagania dotyczące planszy. W naszym przypadku planszę ograniczymy do kwadratu o boku N, gdzie N będzie parametrem konstruktora planszy. Nie będzie ona nieskończona, a będzie się „zawijała”. Co to oznacza?
Na poniższym obrazku zaznaczyłem sąsiedztwo dla pola (1, 0). Jak widzisz, „zawija się” ono w taki sposób, że obejmuje także ostatni rząd planszy.
Podobnie ma się sytuacja dla narożników. Poniższy obrazek pokazuje sąsiedztwo dla narożnika (0, 0).
Napisz program, który będzie w stanie wygenerować kolejną generację planszy w „grze w życie”. Nie zapominaj o testach jednostkowych dla swojego programu.
Dla przykładu poniżej umieściłem jeden z testów z przykładowego rozwiązania.
@Test
public void shouldBeAbleToProvideNextGenerationWithPeriod() {
String boardVisualisation = "+----+" + System.lineSeparator() +
"| |" + System.lineSeparator() +
"| o |" + System.lineSeparator() +
"| o |" + System.lineSeparator() +
"| o |" + System.lineSeparator() +
"+----+";
Board board = new Board(4, Cell.live(1, 0), Cell.live(1, 1), Cell.live(1, 2));
assertEquals(boardVisualisation, board.toString());
String expected = "+----+" + System.lineSeparator() +
"| |" + System.lineSeparator() +
"| |" + System.lineSeparator() +
"|ooo |" + System.lineSeparator() +
"| |" + System.lineSeparator() +
"+----+";
Board boardNextGeneration = board.nextGeneration();
assertEquals(expected, boardNextGeneration.toString());
}
Przygotowałem też dla Ciebie przykładowe rozwiązanie wraz z testami jednostkowymi. Możesz zajrzeć na samouczkowego githuba.
Materiały dodatkowe
- Artykuł na wikipedii na temat gry w życie,
- wywiad z autorem Game of Life – John H. Convey opowiada o Grze w Życie :)
Podsumowanie
Mam nadzieję, że udało Ci się napisać grę w życie. Nie jest to duży projekt jednak rozbudowany na tyle, że musisz przećwiczyć podstawowe zagadnienia programowania obiektowego. Niby prosty zestaw zasad, a jaki ciekawy efekt można uzyskać :). Jeśli chciałbyś dostawać informacje o kolejnych artykułach prosto na Twoją skrzynkę zapisz się na mojego newslettera.
Na koniec proszę Cię, żebyś podzielił się informacją o Samouczku ze swoimi znajomymi, którzy też są zainteresowani programowaniem – zależy mi na dotarciu do jak największej liczby czytelników.
Pobierz opracowania zadań z rozmów kwalifikacyjnych
Przygotowałem rozwiązania kilku zadań algorytmicznych z rozmów kwalifikacyjnych. Rozkładam je na czynniki pierwsze i pokazuję różne sposoby ich rozwiązania. Dołącz do grupy ponad 6147 Samouków, którzy jako pierwsi dowiadują się o nowych treściach na blogu, a prześlę je na Twój e-mail.
Zostaw komentarz