2. Domácí úkol: Conwayova hra života

Úvod

Cílem prvního úkolu je procvičit si práci s vlastními objekty (struct) a manipulacemi s dvourozměrnými poli. K tomuto účelu použijeme klasický příklad celulárního automatu známého pod jménem Hra života. Jde o dvourozměrný model navržený britským matematikem Johnem Hortonem Conwayem v roce 1970, který ilustruje vznik komplikovaného chování v systému kontrolovaném velmi jednoduchými pravidly.

Teoretický background

Popis modelu je poměrně jednoduchý. Hra se odehrává v nekonečné mřížce tvořené čtvercovými buňkami, které mohou být buď živé, nebo mrtvé. Každá z buněk interaguje se svými sousedy podle následujících pravidel:

živá buňka umírá, pokud má méně než dva živé sousedy (vymírání),
živá buňka přežívá, pokud má dva nebo tři sousedy,
živá buňka umírá, pokud má více než tři živé sousedy (přelidnění),
mrtvá buňka ožívá, pokud má právě tři živé sousedy (reprodukce).

K popisu takovýchto pravidel slouží zkrácená notace B3/S23: mrtvá buňka ožívá (Born 3) pokud má právě tři živé sousedy a živá buňka přežívá (Survive 2, 3) pokud má dva nebo tři sousedy, ve všech ostatních situacích umírá.

Přechod z jednoho stavu do druhou probíhá současnou aplikací uvedených pravidel. Tomuto kroku v čase, vývoje od jedné generace do druhé, se také říká tick.

Udáním počátečního stavu (rozložení živých buněk v mřížce) a pravidel se pak systém vyvíjí samostatně a můžeme zkoumat co vše se v takovémto světě může odehrát (viz přiložené testy případně wiki stránka).

Implementační pokyny

V souboru main.jl naleznete hrubou kostru implementace, kterou je potřeba doplnit. Ukázky použití lze nalézt v přiložených testech v adresáři test. Zde probereme základní části programu.

Objekty typu `Conway`

Hra je popsána objekty typu Conway, konstruktor tohoto typu přijímá

počáteční stav (čtvercová/obdélníková matice s více než jedním řádkem/sloupcem a celočíselnými prvky, nuly odpovídají mrtvým buňkám a jedničky živým buňkám),
nepovinný argument s klíčem B udávající pole počtu sousedů při kterém mrtvá buňka oživne, výchozí hodnota je B = [2] (typ Vector{Int64}),
nepovinný argument s klíčem S udávající pole počtu sousedů při kterém živá buňka přežije, výchozí hodnota je S = [2, 3] (typ Vector{Int64}).

Například tedy vytvoříme hru rozměru 5 krát 5 takto:

julia> g = Conway(rand([0, 1], 5, 5))
xxxxx
x x x
  x x
  x x
xxx

Zde vidíme i "pěknou" grafickou reprezentaci, kterou získáme dodefinováním metody Base.show pro objekty našeho typu, a kde jsou živé buňky označeny křížky. Způsob tohoto výpisu netestuji a nechávám ho na vás, zkuste být kreativní. Pouze doporučuji zůstat u maticovém/grafického pohledu, kdy počátek souřadnic je v levém horním rohu obrázku. Podobně máte volnou ruku ve volbě vnitřní reprezentace stavu "světa" a volbě, zda bude objekt mutable.

Konstruktor kontroluje rozměry matice, nepovolujeme nudle sestávající z právě jednoho sloupce nebo řádku.

Dále mřížku chápeme s periodickými hraničními podmínkami. Tj. je-li náš svět modelován maticí 5 krát pět, tak buňka na prvním řádku s indexy (1, 3) má za sousedy i buňky v posledním řádku s indexy (5, 2), (5, 3) a (5, 4). Podobně tomu je pro první a poslední sloupec.

Pomocné funkce

Pro sledování vlastností vývoje dále implementujte dvě pomocné funkce

world(game::Conway): vrátí aktuální pohled na svět jakožto matici,
population(game::Conway): vrátí aktuální počet živých buněk v populaci.

Časový vývoj

Konečně implementujte funkci tick!, která provede časový vývoj, přesun od jedné generace k druhé, přesněji:

tick!(game::Conway) provede právě jeden časový krok a vrátí hru (změněný objekt typu Conway),
tick!(game::Conway, steps::Int64) provede steps kroků a také vrátí hru, případně vyvolá výjimku při záporném počtu kroků.

Další poznámky

V souboru main.jl můžete definovat i další vlastní pomocné funkce/metody. Doporučuji také doplnit docstringy implementovaných metod a objektů. Jako bonus se můžete pokusit vytvořit i animaci časového vývoje (stačí v terminálu).

Testy

Svou implementaci můžete lokálně snadno otestovat příkazem julia test/runtests.jl, výstup by měl vypadat přibližně takto:

$ julia test/runtests.jl
┌ Info:
│ Running tests in test_conway.jl...
└ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Test Summary:                                                | Pass  Total  Time
Conway constructor and related functions                     |    7      7  0.3s
┌ Info:
│ Running tests in test_tick.jl...
└ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Test Summary:                                                | Pass  Total  Time
Time evolution (the tick! method)                            |    8      8  0.2s
Test Summary:                                                | Pass  Total  Time
Time evolution: toad                                         |    2      2  0.1s
Test Summary:                                                | Pass  Total  Time
Time evolution: blinker                                      |    2      2  0.0s
Test Summary:                                                | Pass  Total  Time
Time evolution: glider                                       |    1      1  0.0s
Test Summary:                                                | Pass  Total  Time
Time evolution: longer time periods and larger worlds        |    1      1  9.1s
Test Summary:                                                | Pass  Total  Time
Time evolution: custom rules                                 |    8      8  0.0s

Tyto testy se spouští i automaticky na Gitlabu.

Součástí vyhodnocení řešení bude porovnání rychlosti i robustnosti vaší implementace s ostatními studentskými řešeními.

Řešení a odevzdání

Opět vytvořte větev odvozenou z větve assignment/02-conway a nezvěte ji solution/02-conway. Do solution/02-conway vložte své řešení editací souboru main.jl případně přidáním testů do složky test. Až budete se svým řešením spokojeni, vytvořte MR (to můžete i dříve, aspoň uvidíte výsledek testů, pokud je nespouštíte lokálně) a přiřaďte mě k němu jako assignee. Tímto aktem úkol odevzdáte.