DÚ C1 - Celulární Automaty 1

Vytvořte program v jazyce C (standard C99), který pro zadanou velikost okolí spočítá celkový počet jednorozměrných binárních celulárních automatů a zobrazí jednotlivá pravidla pro zadané číslo automatu.

• velikost okolí (celé číslo)
• číslo automatu (celé číslo)

• velikost okolí
• počet pravidel (automatů)
• číslo zadaného automatu
• vizualizace přepisovacích pravidel zadaného automatu

Detaily formátování viz níže v přehledu ukázkových výstupů.

• v případě, že je zadaná velikost okolí záporná, nebo větší než 2, program vypíše “Chybna velikost okoli!”
• v případě, že je zadáno chybné číslo automatu (mimo rozsah, odpovídající danému okolí), program vypíše “Chybne cislo pravidla!”

• 0 - úspěch
• 101 - chybná velikost okolí
• 102 - chybné číslo automatu

• základy jazyka C
• vstup dat z klávesnice resp. standardního vstupu
• formátovaný výstup
• celočíselné datové typy
• podmínky, cykly
• bitové operace

Jelikož mnozí z vás s jazykem C teprve začínají a cílem tohoto úkolu je procvičit základy, nepředpokládá se rozdělení programu do více souborů.

Celulární automaty jsou výpočetní struktury diskrétní v čase a prostoru. Parametry celulárního automatu jsou typicky:

• dimenze (1D, 2D, 3D, …)
• počet barev
• velikost a tvar okolí

Prostor o dané dimenzi je vyplněn buňkami, které nabývají různých hodnot (barev). V čase se stav buněk mění na základě pravidel automatu. V našem případě pracujeme s binárním automatem - t.j. počet barev je 2 a buňka může nabývat pouze hodnot 0/1 (bílá/černá). Pravidlo říká, jakou hodnotu bude mít buňka v čase “t+1”, pokud v čase “t” mělo její okolí a ona sama určitou hodnotu/kombinaci hodnot. Pokud zvolíme např. okolí velikosti 1, znamená to, že na vstupu pravidla pro jednorozměrný binární automat budou vždy 3 hodnoty (hodnota buňky vlevo, hodnota buňky pro kterou počítáme nový stav a hodnota buňky vpravo) - takový vstup si lze představit jako 3-bitové číslo. Celý automat je v takovém případě popsán sadou pravidel, která pro každou kombinaci těchto tří hodnot stanovuje hodnotu buňky v následujícícm časovém kroku.

Vaším úkolem je napsat program, který vypočítá počet všech automatů pro zadané parametry. Pozor - počet automatů roste velmi rychle s rostoucím počtem barev či velikostí okolí (a samozřejmě dimenzí, kterou však v našem případě nezadáváme a počítáme vždy 1D). Např. pro 3 barvy a okolí velikosti 3 je celkový počet automatů jen velmi těžko představitelných: 443426488243037769948249630619149892803. Zmenšením velikosti okolí na 2, klesne počet automatů na “pouhých”: 7625597484987.

V našem případě je vstup omezen na maximální velikost 2.

Každý takový automat je možné popsat jediným číslem, které kóduje všechna pravidla automatu. Pokud seřadíme všechny kombinace vstupních hodnot (u okolí 1 jsou to 3 bitová čísla) vzestupně zleva doprava a k nim přiřadíme hodnotu následující buňky je toto n-bitové číslo, vyjadřující hodnotu následující buňky resp. buňky v následujícím časovém kroku, práve číslem automatu (n je počet kombinací na vstupu).

Nejlépe to lze vyjádřit následujícím obrázkem automatu číslo 30 - známého jako “rule 30”, který se používá jako generátor náhodných čísel. (zdroj: http://mathworld.wolfram.com/Rule30.html). Obrázek obsahuje i vizualizaci vývoje automatu v čase - to v našem zadání neřešíme.

• http://mathworld.wolfram.com/CellularAutomaton.html
• http://demonstrations.wolfram.com/CellularAutomataEvaluation/
• http://www.wolframalpha.com/input/?i=rule+30
• http://cs.wikipedia.org/wiki/Celulárn%C3%AD_automat

1
300
Chybne cislo pravidla!

3
Chybna velikost okoli!

1
30
Velikost okoli: 1
Pocet automatu: 256
Cislo automatu: 30

...
 .

..*
 *

.*.
 *

.**
 *

*..
 *

*.*
 .

**.
 .

***
 .

1
255
Velikost okoli: 1
Pocet automatu: 256
Cislo automatu: 255

...
 *

..*
 *

.*.
 *

.**
 *

*..
 *

*.*
 *

**.
 *

***
 *

2
1020304050
Velikost okoli: 2
Pocet automatu: 4294967296
Cislo automatu: 1020304050

.....
  .

....*
  *

...*.
  .

...**
  .

..*..
  *

..*.*
  *

..**.
  .

..***
  *

.*...
  .

.*..*
  *

.*.*.
  .

.*.**
  *

.**..
  *

.**.*
  .

.***.
  .

.****
  *

*....
  .

*...*
  .

*..*.
  .

*..**
  .

*.*..
  *

*.*.*
  .

*.**.
  *

*.***
  *

**...
  .

**..*
  .

**.*.
  *

**.**
  *

***..
  *

***.*
  *

****.
  .

*****
  .

2
4611686018427387904
Chybne cislo pravidla!