Druhá série dvacátého druhého ročníku KSP

Celý leták, který posíláme také papírově, v PDF.

Zadání úloh

I přes naše nejvyspělejší technologie se nám sem tam přihodí, že se z některých řešení vytratí číslo úlohy či jméno autora. Dokonce jeden záludný řešitel, zkoušeje nás, na tři různá řešení různých úloh napsal „úloha 22-1-2“. Prosíme, i do řešení, která nám posíláte přes submitovátko, pište kompletní hlavičky, jako byste je psali rukou na papír.

Letošní druhý příběh nesoucí honosný název „Hint“, velmi volně navazující na první dílko, sepsal Martin Böhm. Můžeme vám slíbit, že tentokrát si se stroji času hrát nebudeme – na soustředení jsme se vytrestali dostatečně. Další díl seriálu o Erlangu vám přináší Michal Vaner.

Mimochodem, také jste si jistě všimli, že v této sérii se objeví příklad s magickým číslem 22-2-2, což je vzácnost, která se objevuje jednou za 11 let, 1 sérii a jeden příklad k tomu. Není to důvod k malým oslavám?

Jsem si jist, že každý máme nějakou superschopnost. Někdo hravě vyřeší ty nejtěžší programátorské úlohy, jiný umí dělat radost jiným lidem. A někteří z nás opravdu rychle běhají a driblují s míčem. Já mám Hint. I když možná mají všichni Hint, jen se o tom nebavíme.

Nespadl na mne meteorit a nekousl mne ozářený hroch. Prostě jsem se jednoho dne probudil a věděl jsem, že mám v hlavě Hint. Jak Hint funguje? Občas jdu po ulici, a přemýšlím, jestli si koupit zmrzlinu. V tu chvíli se mi hlavě aktivuje Hint a řekne, jaká z těchto dvou možností je pro mne lepší. Na maličký okamžik jako kdybych mohl spustit prohlédávání obou životů a porovnat návratové hodnoty.

Přiznávám se, moc tomu nerozumím. Vím, že to pracuje tak intuitivně, jako můj zrak nebo sluch. Častokrát v noci sedím a přemýšlím, jak by naše životy vypadaly, kdybychom jako lidstvo vůbec neměli Hint.

22-2-1 Jednoznačný svět (8 bodů)

Představme si lidské životy v alternativním vesmíru, kde lidé neumí činit rozhodnutí, a tak tam nenajdeme žádné křižovatky. V tomto vesmíru se právě vydal turista na cestu ze svého domu. Před domem má ukazatel jen s jednou cestou, a tak se vydává právě touto cestou. Dojde k druhému rozcestníku, ale zde je opět jen jeden ukazatel, kudy jít dál. Cestovatel vždy poslouchá rozcestníky a nikdy se nevrací zpět.

Mohlo by se zdát, že turista bude do nekonečna potkávat nové rozcestníky, ale i jeho planeta je konečná, a tak se po konečném počtu kroků stane, že dorazil na křižovatku, na které už byl. Turista tedy odteď bude pokračovat po smyčce (neboť zpět jít nesmí).

Vašim úkolem je napsat algoritmus, který bude postupně procházet rozcestníky (od prvního dále), ale dá si pozor na opakování, někdy skončí (pozor na zacyklení) a vypíše délku periody smyčky (jsme-li už na smyčce, tak kolik rozcestníků musíme navštívit, abychom se dostali na stejné místo, na kterém teď jsme).

Vstup si můžete představit jako nekonečnou posloupnost přirozených čísel, která představují identifikační čísla jednotlivých křižovatek v pořadí, jak je cestovatel prochází, tedy například

1 2 5 8 12 35 123 42 8 12 35 123 …

Aby to nebylo příliš jednoduché, tak dbejte na to, že si cestovatel (a tedy i váš algoritmus) v hlavě udrží pouze malé množství pomocné informace – snažte se tedy najít algoritmus, který spotřebuje co možná nejmenší množství paměti.

Do jednoho integeru se vám třeba vejde výsledná délka periody, délka začátku před periodou nebo jedno identifikační číslo jedné z křižovatek. Ne však už celá posloupnost (vždyť je nekonečná) ani její část – na uložení K hodnot vždy potřebujete K integerů – ne více, ne méně.

Když jsem v 15 letech objevil Hint, musel jsem se s ním naučit stejně tak, jako se učíme chodit nebo mluvit. Trvalo to dlouho a raději jsem to dělal potají, aby se mi spolužáci nesmáli. Také byste se smáli, kdyby se někdo až v 15 letech učil chodit! Když jsem byl doma sám, stavěl jsem si různé labyrinty a bludiště a učil se, jak takové bludiště projít na první pokus jen s použitím Hintu.

Řešení

22-2-2 Zkouška (15 bodů)

Náš hrdina si vyskládal do každého pokoje svého domu mince. Dům má tvar matice M×N a mezi každými dvěma sousedními pokoji jsou dveře. Nyní se nachází na políčku (1,1) – levý horní roh – a dovolil si chodit jen dveřmi doprava a dolů. Tedy, ne úplně všude. V domě je ještě K speciálních místností, ve kterých může podvádět a jít i nahoru nebo doleva.

Za pomocí Hintu se mu snadno podaří dojít do místnosti (M,N) a nasbírat co nejvíce peněz. Vymyslete algoritmus, který dojde do stejné místnosti a také se mu to podaří. Na výstupu postačí maximální suma peněz, která lze sebrat.

Bodování:

Úloha má přesně definované bodování, není však praktická. Výše zmíněné konstanty berte jako nápovědu, jak budou řešení bodována v závislosti na časové složitosti.

Příklad:

Počty mincí v místnostech:

1 2 1 1
1 1 1 1
2 1 1 3

Místnosti, kde lze podvádět: (2,2) (3,3)

Výstup:

14

Jak jsem se s Hintem sžíval, začal mi pomáhat i v každodenním životě. Nemusel jsem se učit moc na písemky, Hint mi radil, co v nich bude, a já se naučil jen to minimum, které bylo třeba na jedničku. To není tak překvapující – ve třídě bylo hodně lidí, kteří také dostávali snadno jedničky. Hint mi začal radit víc a víc – věděl jsem, co si mám dát k snídani, kudy mám jít do školy, co mám dělat po obědě. Někdy nebylo hned jasné, proč je tohle či tamto rozhodnutí lepší než jeho opak, ale věřil jsem Hintu stejně pevně, jako věřím svým očím nebo uším.

Vůbec nerozumím lidským starostem. Proč se těmi věcmi trápí? Bojí se, že jejich Hint jim neporadí to správné řešení konfliktů? Nebo jsou ještě více opožděni než já, a svůj Hint ještě neobjevili? Světské starosti mi připadaly jako malinkaté tečky na papíře, kterým se lze jen smát. Některé životy jsou tak podobné, že jsem je spojoval kružnicemi. Samozřejmě jen ty, které mi poradil Hint.

Řešení

22-2-3 Kružnice (10 bodů)

Máte před sebou papír, na kterém jsou rozmístěny body. Váš algoritmus by vám měl nahradit Hint a určit, která z možných kružnic se má nakreslit. Nesmíte ale zvolit libovolnou – algoritmus musí najít tu kružnici, na jejíž hraně leží co nejvíce vyznačených bodů. Pokud je takových kružnic více, stačí vrátit libovolnou splňující.

Jestli jsem o Hintu pochyboval? Ano, měl jsem jednu chvíli, kdy jsem byl na vážkách, jestli mi Hint neradí špatně. Ale zkušenost mi radila, že to se mnou Hint myslí upřímně a že se není čeho bát.

Jeli jsme s mamkou v úterý nakoupit do supermarketu a blížili jsme se ke kolejím, když mi najednou Hint poradil (když jsem se ho ptal, co je pro mne aktuálně nejlepší), ať za žádnou cenu nepřekračuji ty koleje. Široko daleko žádný vlak, ale Hint je Hint. Zakřičel jsem na matku, ať zastaví auto, a jak jsme zastavili, ihned jsem vystoupil ven.

Sedl jsem si na obrubník a na skoro zoufalý křík matky, proč jsem to probůh udělal, jsem řekl, že mi to Hint doporučil. A pak už jsem radši byl zticha, protože situace začala být opravdu divoká. Lidé se kolem mne střídali, auta houkala a troubila, vlaky se lopotily přes přejezd. Jen billboard za kolejemi se na mne klidně usmíval.

Řešení

22-2-4 Billboard (10 bodů)

Byl jsem v dosti stresové situaci, a tak jsem počítal, kolikrát přes přejezd uvidím pána na Billboardu. Na přejezdu byly dvoje koleje a po obou zrovna projížděl vlak (vlaky jely proti sobě) s vysokými a nízkými vagóny. Když zrovna byly dva nízké vagóny vedle sebe, bylo skrz přejezd vidět na billboard, ale když na přejezdu byl vysoký vagón, nic jsem neviděl.

Vlaky byly opravdu dlouhé (dá se říci, že nekonečné), ale oba byly řazeny tak, že se tam opakoval stále dokola vzorek vysokých a nízkých vagónů.

Pokaždé, když byly dva vagóny proti sobě, podíval jsem se, jestli vidím na billboard, a počítal jsem poměr mezi situacemi, kdy jsem jej viděl, a kdy ne. Měřit jsem začal ve chvíli, kdy se proti sobě setkaly první dva vagóny.

Vašim úkolem je napsat program, který ověří mé výpočty.

Příklad:

Jsou-li vlaky řazeny takto: první VVNVV a druhý NNV, pak nejprve nevidím billboard, protože na obou kolejích je vysoký vagón:

      -
  <== VVNVV
      VNN ==>
      ^

Ve druhém kroku nevidím billboard, na druhé koleji je vysoký vagón:

      -
  <== VNVVV
      NVN ==>
      ^

Ve třetím kroku ho konečně vidím (dva nízké vagóny výhledu nevadí):

      -
  <== NVVVV
      NNV ==>
      ^

A tak dále. Celkový poměr je v tomto případě 2/15.

A tak jsem se přestěhoval do Bohnic. Chybí mi tu trochu kamarádi a rodina, ale není to zas tak zlé. Místní jsou uzavření a tiší, starostí je málo. Občas se mne sice snaží přesvědčít, že Hint nemám a není skutečný, ale to se jim nemůže podařit – kdybych nemohl věřit svým vlastním smyslům, tak komu?

V očích sester a lékařů vidím zklamání, že se jim nedaří mne vyléčit. Jinak jsou ale se mnou spokojeni, jsem hodný a tichý. Občas mi dovolí vyjít ven s ostatními pacienty, kde si pak společně hrajeme a dovádíme.

Řešení

22-2-5 Pružinky (10 bodů)

Znáte hru na pružinky? Oblíbená hra nejen v Bohnicích, ale i mezi matfyzáky (kdo by se divil). Hráči/blázni se postaví do kruhu, první začne a řekne „p“. Následuje hráč po jeho levici a říká „r“. Takto se hraje podle hodinových ručiček, až některý hráč musí říci poslední písmenko „y“. Tento hráč vypadává, odstupuje (odskakuje) z kruhu, kruh se zmenší a hráč po jeho levici opět říká „p“. Pokračuje se tak dlouho, dokud někdo ve hře zůstává. Poslední hráč ve hře vítězí.

Na vstupu dostanete slovo, které se bude vyslovovat místo slova „pružinky“. Hráče číslujeme od 1 (začínající) podle hodinových ručiček až ke K-tému. Vymyslete program, který určí číslo hráče, který zůstane ve hře jako poslední.

Jak jsem už říkal, je to tu úžasné. Líbí se mi, že mám spoustu času na zkoušení možností, které mi Hint nabízí. Hint se dá trénovat podobně jako ruce nebo nohy. Myslím si, že bych ho mohl začít využívat pro dobro ostatních.

Ale začnu pěkně pomalu – odpovědí na dopis. Před týdnem mi příšlo psaní, kde se jakési Bratrstvo ptá, jestli nemohu použít Hint a odpovědět na jejich dvě otázky. První mi připadala naprosto nesrozumitelná. Asi jsou příliš zápalení do jejich okultních akcí, až zapomněli psát česky.

Řešení

22-2-6 Otázka (10 bodů)

Mocný věštče, poraď nám s naším problémem! Nevyřešíme-li jej, bude to mít nedozírné následky.

Po velkém putování a obětování několika Bratrů jsme se dopátrali k magickému obdélníku. V obvyklém stavu má následující podobu:

1 2 3 4
8 7 6 5

Ve starých svitcích stojí, že správné čtení je podle hodinových ručiček od levého rohu, čili této konfiguraci zapíšeme do našich análů jako 1 2 3 4 5 6 7 8.

Aby magický obdélník začal působit tak, jak my žádáme, musíme ho přemístit do jiné konfigurace. K dispozici máme tři kouzelné operace:

Předvedeme Vám, co se stane s obdélníkem v obvyklém stavu, když aplikujeme jen jednu z operací:

V:
8 7 6 5
1 2 3 4

S:
4 1 2 3
5 8 7 6

R:
1 7 2 4
8 6 3 5

Prosím, velký mudrci, pomož nám vymyslet program, který vypíše nejkratší posloupnost magických operací takovou, že změní obvyklou konfiguraci na tu, kterou mu zadáme!

Například, zadáme-li žádanou konfiguraci

2 6 8 4 5 7 3 1

tak by měl odpovědět číslem a posloupností, tedy:

7
SRVSRRS

Tato úloha je praktická a řeší se ve vyhodnocovacím systému CodEx. Pokud jste zatím žádnou praktickou úlohu neřešili, přečtěte si nápovědu u nějaké starší úlohy, např. Optimalizace kotlů.

Druhá otázka byla podstatně kratší. Ptají se, jestli se písmeno P rovná dvěma písmenům NP. Sice bych řekl, že se nemůže rovnat, vždyť jsou to jiná písmena, ale stejně mi to přišlo o dost jednodušší, než ta první otázka. Pro jistotu jsem použil Hint, to abych pochopil, na co se vlastně ptají. Musím říci, určitě je moje odpověď potěší!

Řešení

22-2-7 Sto oslů umořilo nic (12 bodů)

Opět se posuneme o kousek blíže našemu cíli. Budeme chtít, aby náš program běžel na více počítačích zároveň (tedy, byl distribuovaný). Používáme k tomu jazyk zvaný Erlang, jehož silnou stránkou je právě paralelizmus a distribuovanost. V dnešním díle se podíváme na procesy, jak jich pustit sto jako nic a jak vyřešit komunikaci mezi nimi.

Mocné funkce

V minulém díle jsme si řekli, že Erlang je funkcionální jazyk. To se jednak projevuje tím, že nepotřebuje cykly, stačí mu rekurze, jednak stylem jeho zápisu. Ale k funkcionálním jazykům patří i další věci. Jednou z nich je myšlenka, že funkce jsou také data, tedy jdou předávat, ukládat a dokonce i vytvářet za běhu.

Představme si, že nějak získáme takto uloženou funkci. Jak ji použít? Inu, úplně stejně, jako libovolnou jinou, prostě ji zavoláme – jen bude začínat velkým písmenem, protože je uložená v některé proměnné. Ukázkou může být například funkce map (která se dá najít v knihovně lists). Ta vezme seznam a funkci, na každý prvek zavolá tuto funkci a vrátí seznam výsledků. Vypadá takto:

  map(_, []) -> [];
  map(Fun, [Hlava | Ocas]) ->
	[Fun(Hlava) | map(Fun, Ocas)].

Nyní, jak se taková funkce předá? Možnosti jsou dvě. První, kterou jsme si v tomto příkladě předvedli také, je, že už funkci máme uloženou v nějaké proměnné, resp. je výsledkem nějakého výrazu. Jak již bylo zmíněno, chová se jako data, takže s ní lze také tak zacházet.

Druhá možnost je někam uložit (předat) pojmenovanou funkci. To se dělá tak, že se vytvoří dvojice skládající se ze jména modulu, kde funkce bydlí, a jejího jména. Pozor, taková funkce musí být z tohoto modulu exportovaná. Předpokládejme, že máme funkci zpracuj v modulu data. Potom by šlo psát toto:

  map({data, zpracuj}, vstup).

Ale úplně nejzajímavější vlastnost je, že můžeme funkce vyrábět za běhu, šité na míru aktuální potřebě. Jak se to dělá? Místo jména funkce se použije klíčové slovo fun. Malá ukázka:

  Funkce = fun(X) -> X * 2 end.

Toto vytvoří funkci, která násobí svůj parametr dvěma, a uloží ji do proměnné Funkce. A jak je to s tím šitím na míru? V kódu funkce můžeme použít i proměnné, které nepřebírá přímo tato funkce, ale které máme v aktuálním kontextu k dispozici. Tedy třeba takto:

  nasobitko(Cim) -> fun(X) -> X * Cim end.

Tato funkce vrací funkci, která vždy dostane jeden parametr a přenásobí ho číslem Cim. Pro tuto funkci je Cim konstanta, ale můžeme vytvořit libovolně mnoho různých funkcí pro různá Cim.

Procesy

Pokud chceme vytvořit distribuovaný systém (ať už kvůli výkonu nebo proto, aby při záplavách v jedné serverovně nespadl celý systém), prvním krokem je rozdělit program na nějaké části, které běží skoro nezávisle na sobě – ve výsledku bude každý server provádět nějakou činnost (nebo více činností) a s ostatními se jen domlouvat.

Pokud dvě věci mohou běžet nezávisle na sobě, pustíme je v různých procesech. Ke spuštění nového procesu se používá funkce spawn a přebírá tři parametry. První dva udávají modul a funkci, která se v tomto procesu má vykonat. Třetí je seznam parametrů, se kterými bude tato funkce spuštěna (musí mít tolik položek, kolik jich daná funkce přebírá). Obdobně jako u předávání funkce, je potřeba, aby tato funkce byla exportovaná. Malá ukázka:

-module(blekota).
-export([start/0, vypis/2]).
 
vypis(_, 0) -> done;
vypis(Co, Kolikrat) ->
  io:format("~w~n", [Co]),
  vypis(Co, Kolikrat - 1).
 
start() ->
  spawn(blekota, vypis, ["Ahoj", 3]),
  spawn(blekota, vypis, ["Ble", 8]).

Funkce vypis prostě nějaký řetězec vypíše tolikrát, kolikrát se jí řekne. Ale když ji pustíme dvakrát, v různých procesech (jak děláme ve funkci start), tak budou „blekotat“ přes sebe.

Trocha komunikace

Procesy, které sice běží, ale navzájem se nemohou nijak ovlivňovat, jsou celkem nezajímavé. Některé procedurální jazyky mají možnost vláken, která se podobá procesům v Erlangu. Tam komunikují pomocí sdílené paměti (nějakých proměnných, kam zapisují společně). Nic takového v Erlangu není - proměnná, kam by se dalo jen tak zapisovat, neexistuje (lze si klást filozofickou otázku, jestli to, co má Erlang, lze považovat za plnohodnotnou proměnnou). Místo toho máme k dispozici mechanizmus zpráv.

Když chceme některému procesu poslat zprávu, musíme vědět, kterému. K tomu slouží jeho PID (z Process ID). Vrací nám ho spawn, který tento proces pustil. Druhou možností získání PID je funkce self(), která vrátí PID aktuálního procesu. Pro zaslání zprávy slouží operátor !, kde nalevo je PID, napravo zpráva. Zpráva je libovolný výraz. Například takto:

pustAPosli() ->
  Pid = spawn(modul, funkce, []),
  Pid ! {posel, "zpráva"}.

Posílat zprávy nestačí, je třeba je také přijímat. K tomu slouží výraz receive, který má podobnou syntaxi, jako case. Obsahuje vzory, do kterých se příchozí zpráva pokouší „napasovat“, pokud se povede, použije se odpovídající podvýraz. Pro ukázku syntaxe:

prijimac() ->
  receive
    % Přišlo vyhlášení války
    {valka, PidUtocnika} ->
      bojuj(PidUtocnika);
    % Přišla jen obyčejná zpráva
    {posel, Zprava} ->
      io:format("~w~n", [Zprava])
  end.

Nyní, jak vlastně zprávy cestují? Pokud nějaká přijde, zařadí se do fronty. Když se spustí receive (nebo již běží), podívá se na první zprávu ve frontě a pokusí se ji postupně použít v jednotlivých vzorech. První, který bude odpovídat se použije. Pokud nebude vyhovovat žádný, zpráva se nechá ve frontě a zkusí se druhá zpráva. Pokud se nepoužije ani ta, pokračuje se na třetí. A tak dále, dokud tam nebude nějaká, která použít půjde.

Toto má tu výhodu, že proces nemusí znát všechny typy zpráv, které dostává, v jednom místě. Například můžeme mít funkci, která se optá jiného procesu na názor a počká si na odpověď. Mezitím mohou chodit zprávy, které se týkají něčeho úplně jiného, ale ty počkají do chvíle, než se dojde ke správnému místu v programu. Nevýhodou je, že pokud nějaký typ zprávy neošetřujeme, ale dostáváme, bude nám postupně plnit paměť.

Posílání zpráv je důležitá součást jazyka, proto si uvedeme i malou ukázku. Předpokládejme, že máme modul zpracovani, který obsahuje dvě funkce. První, vyrob, vytvoří nějaká data. Těchto dat máme dostatek (kdykoliv nějaká potřebujeme, vytvoří nám nová). Druhá, spotrebuj, vezme blok dat a zpracuje ho. Mohli bychom udělat cyklus (za pomoci rekurze), ve kterém by se jednoduše zavolaly obě. Ale my si ukážeme řešení, při kterém budou moct tyto dvě funkce běžet paralelně.

-module(spojeni).
-export([vypocet/0,vyrobce/0,spotrebitel/1]).
-import(zpracovani).
 
vyrobce() ->
  Data = zpracovani:vyrob(),
  receive
    {chciData, Pid} ->
      Pid ! {data, Data},
      vyrobce();
    konec -> ok
  end.
 
spotrebitel(Vyrobce) ->
  Vyrobce ! {chciData, self()},
  receive {data, Data} ->
    case zpracovani:spotrebuj(Data) of
      dalsi -> spotrebitel(Vyrobce);
      konec -> Vyrobce ! konec
    end;
  end.
 
vypocet() ->
  Vyrobce = spawn(spojeni, vyrobce, []),
  spawn(spojeni, spotrebitel, [Vyrobce]).

Co se zde děje? Funkce vypocet jen spustí dva procesy, jeden, který bude data vyrábět, a druhý, který je bude spotřebovávat.

Výrobce napřed vyrobí jednu část dat a poté počká, až si o ni někdo řekne. Požadavek obsahuje i zpáteční adresu objednávky, tedy ví, kam data poslat. Poté jde vyrobit nová data a opakuje. V případě, že místo objednávky dostane oznámení, že už toho bylo dost, skončí.

Spotřebitel získá adresu výrobce jako svůj parametr. Na začátku mu pošle objednávku (a připojí k ní i své vlastní PID). Poté si počká na odpověď a příchozí data zpracuje. Podle výsledku zpracování se rozhodne, jestli bude chtít zpracovávat další data a nebo oznámí, že již ne.

Tímto způsobem se výrobce pustí do tvorby nových dat hned po odeslání, tedy v době, kdy je spotřebitel zpracovává. Práci jsme si však malinko zjednodušili – poslední data vyrobíme zbytečně, protože to, že je nikdo nechce se dozvíme až poté, co je máme hotová.

Kdyby nám přišlo, že jsou vzory, do kterých se pokoušíme zprávu dostat, příliš slabé, máme k dispozici ještě konstrukci when, která funguje obdobně, jako u parametrů funkce. Jednoduše napíšeme něco takového:

prijmi(IChyby) ->
  receive
    zprava -> zpracujZpravu();
    chyba when IChyby -> zpracujChybu()
  end.

Toto bude chyby přijímat jen v případě, že IChyby bude true, jinak je bude nechávat ve frontě.

Objektové programování

V dnešní moderní době musí každý programovací jazyk podporovat objektové programování. Ale Erlang klíčové slovo class nemá (a ani jinou přímou podporu pro objekty v jazyce). Přesto nebudeme zoufat a objekty si postavíme vlastní.

Jak na to půjdeme? Máme procesy a umíme posílat zprávy. Tak si tedy z každého objektu uděláme proces. A když po něm budeme něco chtít, pošleme mu zprávu, ve které mu vysvětlíme svůj požadavek. Pokud potřebujeme výsledek, tak si na něj počkáme.

Ukázka

Jako bonbónek na konec tu máme ukázku, která používá v podstatě vše, co bylo v tomto díle probráno. Bude jí hra nim (každý jistě zná, dva hráči střídavě odebírají jednu až tři sirky, kdo nemůže táhnout, prohrál). Budeme mít čtyři objekty – dva hráče, hromádku a rozhodčího (pravda, kdybychom hru implementovali přímočaře přes funkce v jednom procesu, vyšla by kratší, ale tady jde o to ukázat komunikaci).

-module(nim).
-export([rozhodci/3, hromadka/1, prvni/1, druhy/1, hraj/0, hrac/1]).
 
hromadka(Kolik) ->
  receive
    {dotaz, Pid} -> Pid ! {odpoved, Kolik}, hromadka(Kolik);
    {odeber, KolikOdebrat} -> hromadka(Kolik - KolikOdebrat)
  end.
 
rozhodci(Hromadka, Prvni, Druhy) ->
  Hromadka ! {dotaz, self()},
  receive
    {odpoved, 0} ->
      Prvni ! {konec, prohral},
      Druhy ! {konec, vyhral},
      {vitez, Druhy};
    {odpoved, Zbytek} ->
      Prvni ! {hraj, self(), Hromadka},
      receive {tah, Kolik} ->
        if (Kolik >= 1) and (Kolik =< 3)
          and (Kolik =< Zbytek) ->
            Hromadka ! {odeber, Kolik},
            rozhodci(Hromadka, Druhy, Prvni);
          true -> rozhodci(Hromadka, Prvni, Druhy)
        end
      end
    end.
 
hrac(AI) ->
  receive
    {hraj, Rozhodci, Hromadka} ->
      Hromadka ! {dotaz, self()},
      receive {odpoved, Kolik} -> Rozhodci ! {tah, AI(Kolik)} end,
      hrac(AI);
    {konec, Vysledek} -> Vysledek
  end.
 
prvni(_) -> 1.
 
druhy(1) -> 1;
druhy(_) -> 2.
 
hraj() ->
  Hromadka = spawn(nim, hromadka, [5]),
  Prvni = spawn(nim, hrac, [{nim, prvni}]),
  Druhy = spawn(nim, hrac, [{nim, druhy}]),
  rozhodci(Hromadka, Prvni, Druhy).

Trochu vysvětlení k tomuto kódu. Hromádka si jen pamatuje, kolik sirek na ní zbývá. Pokud je požádána, tento svůj stav sdělí. Druhá věc, kterou umí, je nějaké množství odebrat. Poté se vždy funkce pustí znovu a čeká na další požadavek.

Poté zde máme hráče. Hráč dostane funkci na umělou inteligenci. Poté si počká, až mu někdo řekne, že je na tahu a dá mu k tomu Pid hromádky a rozhodčího. Hromádky se zeptá, kolik na ní zbývá, nechá umělou inteligenci rozhodnout, kolik odebrat a sdělí to rozhodčímu.

Nejsložitější je zde rozhodčí. Každé kolo napřed zkontroluje (dotazem na hromádku), zda ještě jsou nějaké sirky. Pokud ne, oznámí hráčům, jestli vyhráli nebo prohráli a skončí. Pokud ano, řekne prvnímu hráči, ze je na tahu a počká si na jeho rozhodnutí. Zkontroluje, že je v pořádku a pokud ano, tah provede, hráče prohodí a začne nový tah. Pokud táhne proti pravidlům, tak tah odignoruje a zeptá se znovu.

Nakonec tu máme už jen funkci, která to celé spustí. Hromádku a hráče pustí jako nové procesy a rozhodčího nechá běžet ve svém.

Úložky

Nakonec je potřeba nabyté znalosti procvičit. A jak lépe, než že si každý napíšeme nějaké malé cvičení? (Jdu se stydět za to, jak zním jako učitel.)

Producent-konzument se skladištěm: Vzpomeňte si na ukázku, kde jeden proces produkoval nějaká data a druhý je spotřebovával. Budeme chtít vylepšit tuto ukázku o skladiště. Skladiště, když se pustí, tak se mu zadá jeho velikost. Dokud nebude skladiště plné, tak bude moct producent produkovat nová data, dokud nebude prázdné, tak konzument bude spotřebovávat. Pokud chybí místo nebo data, tak producent, resp. konzument čeká, než to ten druhý uvede do lepšího stavu.

Napište tedy modul s třemi veřejnými funkcemi. První bude spouštět skladiště a bude přebírat velikost. Druhá bude spouštět producenta, dostane PID skladiště a funkci na vytváření dat. Třetí bude pro konzumenta a parametry bude mít obdobné.

Můžete předpokládat, že na jednom skladišti bude pracovat maximálně jeden producent a jeden konzument. Pokud vaše řešení bude fungovat i pro libovolné množství producentů a konzumentů, dostanete další dva bonusové body. [5 bodů]

Balené funkce: Rozhraní minulé úlohy umožňovalo předat pouze funkci bez parametrů. Představme si, že máme funkci generuj, která generuje potřebná data, ale potřebuje k tomu dostat parametr, řekněme třeba číslo 42. Jak ji dostaneme do tohoto rozhraní? [2 body]

Centrum práce: Představme si, že máme nějaké úložiště práce. Chceme funkci, která bude do tohoto úložiště přidávat novou práci. Dále bude několik pracovních procesů. Ty budou provádět tyto úkoly. Když proces práci provede, řekne si o další (a případně počká, až nějaká práce přibude).

Rozhraní nechť si každý navrhne sám – jeho kvalita bude součástí hodnocení. [5 bodů]

Řešení