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.

Żywa komórka (1, 3)

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.

Żywa komórka (1, 3)
Pusta plansza

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.
Figura okresowa
Figura okresowa

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:

Figura okresowa

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.

Sąsiednie pola dla (1, 0)

Podobnie ma się sytuacja dla narożników. Poniższy obrazek pokazuje sąsiedztwo dla narożnika (0, 0).

Sąsiednie pola dla (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

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.

Kategorie:

Ostatnia aktualizacja:

Autor: Marcin Pietraszek


Nie popełnia błędów tylko ten, kto nic nie robi ;). Bardzo możliwe, że znajdziesz błąd, literówkę, coś co wymaga poprawy. Jeśli chcesz możesz samodzielnie poprawić tę stronę. Jeśli nie chcesz poprawiać błędu, który udało Ci się znaleźć będę wdzięczny jeśli go zgłosisz. Z góry dziękuję!

Zostaw komentarz