HW2: Hra Života | PB160 Programování v jazyce C

Odevzdávání částí A a B je ukončeno.

Autoři zadání	xhanulik Roman Lacko
Odevzdávané soubory	src/*
Konec odevzdání části A	2026-03-16 24:00
Konec odevzdání části B	2026-04-14 24:00

Kostru k úkolu nelze stáhnout

Představení úkolu

Cílem úkolu je naprogramovat simulaci a vizualizaci Conwayovy Hry života, klasického dvourozměrného buněčného automatu. Program bude načítat počáteční stav buněk v obdélníkové síti a simulovat jeho vývoj v čase podle přesně definovaných pravidel.

První část (A)

Naše hra života bude probíhat na dvourozměrné obdélníkové síti, kde každá buňka může být živá nebo mrtvá. Vývoj buněčné sítě je rozdělen do generací. V každé generaci se současný stav sítě převede na nový stav pomocí pravidel uvedených níže.

Pravidla aktualizace buněk v síti

Pro každý krok simulace (generaci) se u každé buňky spočítá počet živých sousedů z osmi okolních buněk (horizontálně, vertikálně i diagonálně). Podle počtu sousedů se stav buňky změní následovně:

Živá buňka s méně než dvěma živými sousedy zemře kvůli nedostatku podpory (underpopulation).
Živá buňka se dvěma nebo třemi živými sousedy přežije do další generace.
Živá buňka s více než třemi živými sousedy zemře kvůli přelidnění (overcrowding).
Mrtvá buňka s přesně třemi živými sousedy ožije díky reprodukci.

Pro hranice sítě platí následující pravidla:

Buňky u okraje sítě mají méně sousedů.
Buňky, které se nachází mimo síť, se považují za mrtvé.
Pokud by měly buňky za okrajem sítě ožít, nestane se nic.

Rozhraní

Váš program pro simulaci vývoje buněčné sítě bude obsahovat následující funkci:

bool evolve(size_t gens, size_t rows, size_t cols, const char *input, char *output);

Funkce evolve() spočítá vývoj buněk pro daný počet generací. Její argumenty jsou:

gens: počet generací, které program nasimuluje a vytiskne odpovídající rozložení sítě (kladné celé číslo),
rows: počet řádků (kladné celé číslo),
cols: počet sloupců (kladné celé číslo),
input: posloupnost znaků . a # délky rows × cols obsahující počáteční rozložení mrtvých resp. živých buněk,
output: výstupní řetězec dělky alespoň rows × cols, do kterého funkce vloží výsledek.

Řetězec input reprezentuje obsah sítě po řádcích:

prvních cols znaků odpovídá prvnímu řádku,
dalších cols znaků druhému řádku,
atd.

Buňky ve vstupním a výstupním řetězci jsou reprezentovány následujícími znaky:

#: živá buňka
.: mrtvá buňka

Pomocí assert() ověřte vstupní podmínky funkce:

rows a cols jsou větší, než 0,
input a output jsou navzájem různé ukazatele a žadný z nich není nullptr,

Pokud řetězec input obsahuje jiné znaky, než # nebo ., nebo nastane nějaká chyba (viz Poznámky), funkce vrátí false. Jinak funkce provede požadovaný počet simulací. Pokud všechno proběhne v pořádku, vrátí true.

Ukázka formátu vstupu:

Pro argument input v následujícím formátu:

.#.#....##..

se buněčná síť interpretuje následujícím způsobem:

. # . #
. . . .
# # . .

Výsledek funkce

Funkce evolve() vypočítá vývoj sítě a zapíše výsledek to řetězce output. Síť je opět reprezentována po řádcích, stejně jako u vstupnímu argumentu input.

Příklad vstupu a výstupu

Pro následující volání:

evolve(2, 3, 4, ".#.#....##..", output)

Proběhne vývoj následujícím způsobem:

0. (počáteční) generace:
. # . #
. . . .
# # . .

1. generace:
. . . .
# # # .
. . . .

2. (výsledná) generace:
. # . .
. # . .
. # . .

Funkce evolve() zapíše do output následující řetězec:

".#...#...#.."

Druhá část (B)

Simulace z první části trpí jedním zásadním nedostatkem: hranice sítě uměle deformují výsledky — vzory, které by se přirozeně šířily dál, jsou oříznuty. Navíc binární model buňky nedokáže zachytit, že nově vzniklá buňka se může chovat jinak než stará. Druhá část proto rozšiřuje simulaci o nekonečnou síť a model stárnutí.

Nekonečná síť

Síť buněk je nyní potenciálně nekonečná. Pokud by v průběhu výpočtu generace měla vzniknout živá buňka za aktuálním okrajem sítě, implementace síť automaticky rozšíří tak, aby výpočet mohl proběhnout správně. Implementace tedy musí zajistit, že výstup odpovídá výsledku simulace na nekonečné síti.

Výstup bude obsahovat minimální obdélníkovou oblast, která obsahuje všechny živé buňky po dokončení všech generací.

Stavy buněk

Buňky již nejsou pouze živé nebo mrtvé, ale rozlišujeme čtyři stavy:

+: mladá buňka (young)
#: dospělá buňka (adult)
-: stará buňka (old)
.: mrtvá buňka (dead)

Za živou buňku se považuje buňka v libovolném stavu - mladá, dospělá nebo stará.

Pravidla aktualizace buněk

Výpočet každé generace probíhá ve dvou fázích: nejprve se vyhodnotí smrt a narození, poté stárnutí.

Smrt a narození

Pro každou buňku se spočítá počet živých sousedů z osmi okolních buněk.

Smrt:

Stejně jako v části A:
- Smrt se vyhodnocuje pouze na buňkách, které existovaly na začátku generace.
- Živá buňka zemře, pokud má méně než 2 nebo více než 3 živé sousedy.

Narození:

Mrtvá buňka s přesně 3 živými sousedy ožije.
Nová buňka vznikne jako mladá buňka (+).

Stárnutí

Stárnutí se aplikuje pouze na buňky, které:

existovaly na začátku generace
a nebyly nově narozeny v této generaci.

Tedy nově narozené buňky nestárnou.

Pro všechny ostatní přeživší buňky platí:

mladá → dospělá,
dospělá → stará,
stará → stará.

Rozhraní

Funkce evolve() z části A bude doplněna o novou verzi s upraveným rozhraním:

bool evolve_infinite(size_t gens, size_t rows, size_t cols, const char *input,
            char **output, size_t *out_rows, size_t *out_cols);

Argumenty funkce:

gens: počet generací k simulaci (kladné celé číslo),
rows, cols: rozměry vstupní sítě (kladná celá čísla),
input: vstupní řetězec délky rows × cols reprezentující síť po řádcích (stejný formát jako v části A), avšak s rozšířenou abecedou znaků ., +, #, - pro mrtvou, mladou, dospělou a starou buňku,
out_rows, out_cols: ukazatele, do kterých funkce zapíše rozměry výstupní sítě,
output: ukazatel na ukazatel; funkce alokuje výsledný řetězec a zapíše jeho adresu do *output. Volající je zodpovědný za uvolnění alokované paměti pomocí free().

Pomocí assert() ověřte vstupní podmínky funkce:

gens, rows a cols jsou větší než 0,
input, output, out_rows a out_cols nejsou nullptr.

Pokud řetězec input obsahuje jiné znaky než ., +, # nebo -, nebo nastane chyba při alokaci paměti, funkce vrátí false a hodnoty *output, *out_rows, *out_cols jsou nedefinované.

Výsledek funkce

Výstupní síť musí obsahovat všechny živé buňky a zároveň žádné zbytečné mrtvé řádky nebo sloupce navíc. Funkce zapíše do proměnné *output nejmenší obdélníkové rozložení sítě, které zachytí všechny živé buňky (tzv. bounding box). Hodnoty *out_rows a *out_cols budou odpovídat rozměrům tohoto bounding boxu. Pokud vše proběhne v pořádku, funkce vrátí true.

Pokud po dokončení libovolné generace nejsou v síti žádné živé buňky, funkce může skončit a:

do *output zapíše řetězec "." (síť 1 × 1 s jednou mrtvou buňkou),
nastaví *out_rows = 1 a *out_cols = 1,
vrátí true.

Příklad vstupu a výstupu

Pro následující volání:

evolve_infinite(2, 3, 4, ".+#.-##+....", &output, &out_rows, &out_cols);

Proběhne vývoj následujícím způsobem:

0. (počáteční) generace:
. + # .
- # # +
. . . .

1. generace:
+ . . +
- . . #
. + + .

2. (výsledná) generace:
- . . -
. # # .

Funkce evolve_infinite() naalokuje a zapíše do *output následující řetězec:

"-..-.##."

Poznámky

Na závěr pár poznámek před implementací.

Část A

Kostra úlohy, společně s velmi základními testy, je připravena ve větvi hw2/a vašeho repozitáře.
Tato úloha vyžaduje práci s pamětí. Je tedy klíčové, že váš přistup do paměti bude řádně ošetřen, aby nedocházelo ke čtení mimo její hranice.

Knihovna `matrix`

Podle zadání je pole output dostatečně veliké pro jednu instanci sítě. Pokud chcete další, nejlepší řešení je alokovat si další paměť dynamicky. Dynamická alokace však zatím na přednášce nebyla, proto máte k dispozici knihovnu matrix s kouzelnou správou paměti C23.

Funkce matrix_new() vrátí ukazatel, který můžete používat jako dvourozměrně pole. Návratový typ je matrix (alias pro char **), který musí volající kód uklidit na konci programu voláním matrix_destroy(). Tuto hodnotu však můžete zachytit i do proměnné kouzelného typu auto_matrix, který se postará o úklid alokované paměti sám na konci rozsahu proměnné.

Pokud funkce z nějakého důvodu selže, vrátí nullptr.

#include "matrix.h"

int main()
{
    auto_matrix m = matrix_new(ROWS, COLS);

    if (m == nullptr)
        return EXIT_FAILURE;

      m[1][2] = '#';
    /*  ^  ^- column */
    /*  \---- row    */

}   // m is freed here

Nepoužívejte Variable Length Array! Pro dostatečně velký vstup se totiž může stát, že vyčerpáte celý zásobník programu.

Představení úkolu

První část (A)

Pravidla aktualizace buněk v síti

Rozhraní

Ukázka formátu vstupu:

Výsledek funkce

Příklad vstupu a výstupu

Druhá část (B)

Nekonečná síť

Stavy buněk

Pravidla aktualizace buněk

Smrt a narození

Stárnutí

Rozhraní

Výsledek funkce

Příklad vstupu a výstupu

Poznámky

Část A

Knihovna matrix

Knihovna `matrix`