S1 Buňkový automat

var datasets = [
  {argv: [1, ["010"]], out: 1},
  {argv: [2, ["010"]], out: 1},
  {argv: [1, []], out: 0},
  {argv: [0, []], out: 1},
  {argv: [1, ["101", "100", "001"]], out: 0},
  {argv: [2, ["101", "100", "001"]], out: 1},
  {argv: [100, ["101", "100", "001"]], out: 1},
  {argv: [100, ["100", "010", "001", "011"]], out: 0},
  {argv: [101, ["100", "010", "001", "011"]], out: 1},
  {argv: [102, ["100", "010", "001", "011"]], out: 1},
  {argv: [103, ["100", "010", "001", "011"]], out: 1},
  {argv: [104, ["100", "010", "001", "011"]], out: 0},
  {argv: [105, ["100", "010", "001", "011"]], out: 0},
  {argv: [106, ["100", "010", "001", "011"]], out: 0},
  {argv: [107, ["100", "010", "001", "011"]], out: 1},
  {argv: [108, ["100", "010", "001", "011"]], out: 1},
  {argv: [109, ["100", "010", "001", "011"]], out: 0},
  {argv: [110, ["100", "010", "001", "011"]], out: 1},
]
names = ["kroky", "pravidla"]

Buňkový automat je nekonečný pás buněk, které můžou být ve stavu 0 nebo 1. Vyvíjí se v krocích, kdy každá buňka svůj stav v následujícím kroku určí podle současného stavu sebe a svých dvou sousedů. Přesná pravidla se můžou lišit podle zadání úlohy.

Na začátku víme, že buňka uprostřed pásky je ve stavu 1 a všechny ostatní buňky jsou ve stavu 0. Program má určit, v jakém stavu bude buňka uprostřed pásky potom, co proběhne daný počet kroků.

Program dostává dva parametry:

• první parametr je číslo udávající počet kroků, které máme provést.
• druhý parametr je seznam popisující situace, ve kterých následující stav bude 1. Každá situace je zapsaná jako řetězec ze tří číslic: stav levého souseda, stav dotyčné buňky, stav pravého souseda. Například:
  • řetězec "010" znamená, že buňka zůstane ve stavu 1, pokud oba její sousedi jsou ve stavu 0.
  • řetězec "100" znamená, že buňka se změní do stavu 1, pokud její levý soused je ve stavu 1.
  • řetězce "100", "110", "111", "010","011", "001", "101" společně znamenají, že buňka bude ve stavu 1, když aspoň jedna buňka kolem ní je ve stavu 1.
• v ostatních situacích bude následující stav buňky 0.
• máme záruku, že řetězec "000" v zadání nikdy nebude. Ten by totiž znamenal, že se buňka změní do stavu 1 uprostřed nekonečného pásu nul, a to by chtělo hodně práce navíc.

Výstupem programu je buďto 0, nebo 1, udávající stav buňky uprostřed pásky po daném počtu kroků.

Rady

• Když se automat má vyvíjet 100 kroků, bezpečně vám stačí 100 buněk nalevo i napravo.
• Kdyby pro vás bylo těžké zvládnout všechny podrobnosti zadání, zkuste zvládnout aspoň některé případy.

Na vysvětlenou

Cellular automaton si možná pamatujete z kvinty, já ho považuju za krásnou hračku. Můžete se na něj podívat na septima.dominec.eu/automat.html.

• Přepínač Náhodně nechte vypnutý, ten pro tuhle úlohu není zajímavý.
• Všimněte si, že když žádné pravidlo není zapnuté, tak nahoře přesně uprostřed stránky je jeden černý pixel. To je ta buňka uprostřed pásky, co je na začátku 1.
• Stránku si můžete přiblížit, abyste viděli podrobnosti. Je lepší pak dát refresh, aby se správně nastavila šířka.
• Můžete po stránce scrollovat neomezeně dolů a automat se dopočítá.

def main(kroky, pravidla):
  bunky = [0] * (2*kroky + 1)
  bunky[kroky] = 1
  for i in range(kroky):
    priste = list(bunky)
    for j in range(1, len(bunky) - 1):
      priste[j] = 0  # tohle chcete změnit
    bunky = priste
  return bunky[kroky]