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

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

Řešení úloh

• 22-2-1: Jednoznačný svět
• 22-2-2: Zkouška
• 22-2-3: Kružnice
• 22-2-4: Billboard
• 22-2-5: Pružinky
• 22-2-6: Otázka
• 22-2-7: Sto oslů umořilo nic

22-2-1 Jednoznačný svět (Zadání)

Nejprve trochu o výpočetním modelu – zadání nebylo v pár věcech úplně důsledné, tak to nyní napravíme. V úlohách s potenciálně velkými čísly na vstupu, kde nás zajímá hlavně počet operací s těmito čísly, a ne až tak složitost jednotlivých operací, se často používá model s buňkami (integery) schopnými pojmout čísla maximálně konstanta-krát větší než max{číslo na vstupu, délka vstupu} (v našem případě považujeme délku vstupu za délku periody + délku aperiodického počátku), o čemž byla v zadání zmínka. Pro každý vstup má tedy model jinou kapacitu (ač se to může zdát divné, našemu měření to vyhovuje víc), speciálně tedy nelze v programu kalkulovat s kapacitou proměnných a maximální uložitelnou hodnotou jako s čísly, či dokonce s  přetečením jako s rozpoznatelnou událostí – tyto termíny prostě nejsou v takovém slova smyslu definovány. Nekonečnou vstupní posloupnost si lze představit jako funkci, jejíž zavolání posune cestovatele na další křižovatku a vrátí její číslo. Teď už ale k řešení.

Hledání smyčky rozdělíme na dvě fáze: nejprve se do smyčky musíme dostat a všimnout si toho (smyčka rozhodně nemusí procházet první křižovatkou), poté zjistíme její délku. Jak smyčku najít? Představme si, že cestovatel si občas zapamatuje číslo nějaké křižovatky. Pak bude nějakou dobu chodit, a dorazí-li znovu na křižovatku se zapamatovaným číslem, má jistotu, že je v periodě. Pokud se mu to nějakou dobu nebude dařit, tak ono číslo zapomene, zapamatuje si místo něho současnou křižovatku a jde dál. Řekněme, že první křižovatku si bude pamatovat jen 1 krok, další 2, pak 4,8,16, …, 2^k, …

A jak určit délku smyčky? To je již snadné, je to přesně počet kroků od posledního zapamatování křižovatky.

Pseudokódem by postup vypadal takto (dál! buď funkce vracející další křižovatku):

kde_jsem_teď := dál!
i := 1
j := 0
while (pořád ):
    kde_jsem_byl := kde_jsem_teď
    while(j < i ):
        kde_jsem_teď := dál!
        j := j+1
        if(kde_jsem_teď == kde_jsem_byl ):
            return j
    j := 0
    i := i*2

To, že cestovatel správně určí délku periody, je zjevné, perioda je definována jako vzdálenost dvou nejbližších výskytů libovolného prvku, což je přesně to, co cestovatel odkrokuje.

Dle modelu popsaného v úvodu potřebujeme 4 paměťové buňky (nikdy neukládáme číslo, jež by mohlo přetéci), což je asymptoticky optimální.

Časová složitost odpovídá počtu kroků. Ukázali jsme, že stačí 2^l - 1 + 2^l kroků, kde l je nejmenší, aby 2^l - 1 > z+p. To znamená, že 2^l-1 ≤ z+p, a tedy 2^l - 1 + 2^l < 2^l+1 = 4 ·2^l-1 ≤ 4 ·(z+p). Počet oběhnutých křižovatek je tedy Θ(z+p) – opět jsme na asymptotickém optimu, neboť vstup jsme nuceni čísti sekvenčně.

Vojta Tůma

22-2-2 Zkouška (Zadání)

Pre začiatok si dom predstavíme ako graf, kde jednotlivé miestnosti sú vrcholy orientovaného grafu a hrana z vrcholu v do vrcholu u bude viesť práve vtedy, ak sa z odpovedajúcej miestnosti môžeme dvermi dostať priamo do druhej miestnosti. Ďalej si počet mincí v miestnosti odpovedajúcej vrcholu v nazvime hodnota vrchola v a označme h(v).

Ak sa v dome nenachádzajú miestnosti, kde sa dá podvádzať, potom náš graf má tú vlastnosť, že je acyklický (hrany vedú len doprava a dole), a teda každú miestnosť môžeme navštíviť len raz. Všimnime si, že každá cesta v našom grafe zodpovedá validnej ceste po dome a naopak. Úlohou je teda nájsť cestu v našom grafe z vrchola odpovedajúceho miestnosti (1,1) do vrchola (M,N), na ktorej je súčet hodnôt vrcholov maximálny.

Na vyriešenie tohto problému použijeme dynamické programovanie.

Ako to tak v dynamickom programovaní chodí, na vyriešenie celého problému sa použijú riešenia podproblémov. V našom prípade budú podproblémy zodpovedať odpovediam na otázku: „Aká je najdrahšia cesta z počiatočného vrchola do vrchola v?“ Označme danú odpoveď f(v). Pre v = počiatočný vrchol je zrejme f(v) = 1.

Druhý krok v dynamickom programovaní je nájdenie obecného rekurentného vzťahu medzi podproblémami. Teda hľadáme vzťah na vyjadrenie f(v), ak už vieme f pre nejakú množinu vrcholov.

Hľadaný vzťah je f(v) = max{f(u) |u vedie hrana do v } + h(v). Tento vzťah je korektný, pretože každá cesta, a teda aj tá najdrahšia, končiaca vo vrchole v, musí pozostávať z cesty vedúcej do nejakého vrchola, z ktorého vedie do v hrana, plus posledný vrchol v.

Ak teda chceme vypočítať hodnotu f(v), musíme vedieť hodnotu f pre všetky vrcholy, z ktorých vedie do v hrana. Dôležité je uvedomiť si, že práve acyklickosť grafu nám zaisťuje to, že nevznikne cyklická závislosť hodnôt f.

Posledným krokom v dynamickom programovaní je implementácia odvodeného vzťahu. Tá sa dá priamočiaro vykonať implementáciou zisteného rekurentného vzťahu pomocou rekurzie a memoizácie už raz vypočítaných hodnôt.

Pseudokód

f(v):
  if v == počiatočný vrchol
  then
    return 1
  if hodnota f(v) už raz spočítaná
  then // rovno vrátime hodnotu ktorú sme už raz spočítali
    return f(v)
  else // inak danú hodnotu spočítame
    f(v) = max { f(u) | z u vedie hrana do v } + h (v)
    return f(v)

Pričom odpoveďou na náš vstup je f(u), kde u je vrchol odpovedajúci miestnosti (M,N). Práve memoizácia už raz spočítaných hodnôt nám zaisťuje, že každú hodnotu f(v) spočítame práve raz a celkovo pri tom vykonáme lineárne veľa práce od veľkosti grafu, pretože na každú hranu sa pozrieme práve raz.

Takto vieme vyriešiť úlohu, ak je graf acyklický. Ak sa však v dome nachádzajú podvádzacie miestnosti, potom sa v našom grafe nachádzajú cykly. Všimnime si, že ak sa v našom grafe nachádza cyklus, potom ak sa dostaneme v dome do miestnosti, ktorej odpovedajúci vrchol patrí do tohto cyklu, môžeme sa dostať do všetkých miestností na danom cykle a zase späť do danej miestnosti. Obecne môžeme povedať, že vrcholy tvoriace cyklus sú istým spôsobom ekvivalentné v tom zmysle, že ak sa dostaneme do ktoréhokoľvek z nich, potom môžeme navštíviť všetky vrcholy s ním na cykle a zase pokračovať z ľubovolného z nich. Takéto množiny vrcholov, z ktorých sa dá prechádzať z ľubovolného vrchola do ľubovolného a zase späť, sa volajú silno-súvislé komponenty orientovaného grafu.

Viacej si o nich môžete prečítať na Wikipedii, rovnako aj o algoritme ako ich pre daný graf nájsť v čase lineárnom od veľkosti grafu.

Platí, že po navštívení ľubovolného vrcholu patriaceho do určitej silno-súvislej komponenty môžeme vyzbierať celú príslušnú komponentu a zase pokračovať z ľubovolného vrcholu v nej obsiahnutom. Preto si môžeme dovoliť každú silno-súvislú komponentu nahradiť jediným vrcholom s hodnotou rovnou sume hodnôt všetkých vrcholov patriacich do tejto komponenty.

Touto úpravou sme dostali acyklický graf, na ktorom použijeme algoritmus pre acyklické grafy, s tým rozdielom, že hľadáme najdrahšiu cestu z vrcholu, ktorý reprezentuje skontrahovaná komponenta obsahujúca počiatočný vrchol (1,1), do vrcholu, ktorý reprezentuje komponenta obsahujúca cieľový vrchol (M,N).

Rozbor časovej zložitosti

Treba si najskôr uvedomiť, že náš graf má MN vrcholov a každý vrchol má stupeň maximálne štyri, teda hrán bude tiež O(MN). Po skonštruovaní grafu aplikujeme algoritmus na nájdenie silno-súvislých komponent v čase lineárnom od veľkosti grafu, teda O(MN). Následne nahradíme každú komponentu jedným vrcholom, čím sa nám veľkosť grafu určite nezväčší a nakoniec aplikujeme algoritmus na nájdenie najdrahšej cesty v acyklickom grafe, ktorý tiež beží lineárne. Celková časová zložitosť je teda O(MN). V pamäti si budeme držať vstup a reprezentáciu grafu, pamäťová zložitosť je preto tiež O(MN).

Program

Peter Ondrúška

22-2-3 Kružnice (Zadání)

Jednoduchý přístup, o který se pokoušela valná většina z desítky zaslaných řešení, spočívá v tom, že se podíváme pro každou trojici bodů, jakou kružnici opsanou trojúhelník nad těmito body určuje, a pro každý z dalších bodů si ověříme, nachází-li se na této kružnici. Něco takového bude trvat O(N⁴) a zabere O(N) paměti.

Samozřejmě je potřeba si rozmyslet, jak najít střed kružnice opsané: řešením je soustava dvou rovnic o dvou neznámých, které snadno vyjádříme z analytických předpisů pro rovnice os dvou stran daného trojúhelníka. Zvláštním případem tu bude stav, kdy tři vyšetřované body leží na jedné přímce, ten můžeme zapomenout.

Hezčí řešení tkví ve využití vlastností obvodového úhlu: zafixujeme-li si úsečku AB (pro každé dva body A, B), můžeme se pro každý další bod C ptát, pod jakým úhlem tuto úsečku AB vidí. Pokud nějaké dva C₁, C₂ koukají pod stejným úhlem (a ze stejné strany!), musejí se nacházet na společné kružnici s AB.

Když si zároveň vzpomeneme na důležitou vlastnost standardního skalárního součinu v euklidovské rovině, totiž že cosα= u ·v / (|u|·|v|), získáme snadno dobrý nástoj, jak „koukání pod stejným úhlem“ testovat: stačí porovnávat kosíny vypočítané pro vektory CA a CB.

Jak spočítat, kolik se pod jedním úhlem dívá bodů? Můžeme to řešit třeba tak, že si naměřené úhly (tedy kosíny) seřadíme podle velikosti (v čase O(N log N)), načež je projdeme a napočítáme shodné veličiny – už je máme vedle sebe. Tím získáme algoritmus časové složitosti O(N³ log N) při prostoru O(N).

Druhou možností, která se nabízí, je využít hešování. To nabízí ubití logaritmu za cenu toho, že se tak stane jen v průměrném případě. V závislosti na použitém algoritmu se nám totiž při hešování reálných čísel snadno může stát, že řešení kolizí u nevhodného vstupu zabere lineární čas.

Program

Lukáš Lánský

22-2-4 Billboard (Zadání)

Označme si délky vzorů A a B. Pak si očíslujeme vagóny ve vzorech tak, že vždy v k-tém kroku budou na přejezdu vagóny s číslem k. To očíslování je pro první vlak (0, 1, 2, …, A-1) a pro druhý vlak (0, B-1, B-2, …, 2, 1), ale protože se vzor periodicky opakuje, bude na každém vagónu prvního vlaku kromě nějakého i také i+A a analogicky na každém vagónu druhého vlaku kromě nějakého j také j+B.

Praktičtější je, když můžeme pole indexovat číslem vagónu, takže si druhý vzor přeskládáme v Θ(B) na (0, 1, 2, …, B-1).

Nyní tedy víme, že v k-tém kroku bude na přejezdu vagón prvního vlaku s číslem k mod A a vagón s číslem k mod B. Protože máme jen konečně možností setkání, ale nekonečně setkání samotných, musí se v jednu chvíli setkat znovu tytéž vagóny a od té chvíle se bude situace periodicky opakovat, protože máme periodické zadání. Kdy to bude poprvé?

V takovou chvíli musí určitě platit, že k-p ≡ k  mod A a k-p ≡ k  mod B*. Pak tedy p ≡ 0  mod A a p ≡ 0  mod B, neboli p je dělitelné jak A, tak B. Nejmenší číslo, které toto splňuje, je nejmenší společný násobek A a B. Snadno pak ověříme, že poprvé se situace musí opakovat ve chvíli, kdy se znovu setkají vagóny s čísly 0.

* x ≡ y  mod z znamená „x a y dává stejný zbytek po dělení z“

Pokud jsou A a B nesoudělná, není skoro co řešit. Platí totiž Čínská zbytková věta, která říká, že když mám k po dvou nesoudělných čísel x₁, x₂, …, x_k, pak když si vyberu jakékoli celočíselné zbytky m₁, m₂, …, m_k: 0 ≤ m_i < x_i pro všechna i, pak existuje právě jedno číslo C takové, že C ≡ m_i  mod x_i pro všechna i a 0 ≤ C ≤ x₁ x₂ …x_k - 1.

Podle této věty (pro k = 2) se tedy mezi nulou a AB-1 potká každá dvojice vagónů právě jednou. Takže stačí spočítat poměr počtu všech dvojic nízkých vagónů ku počtu všech vagónů a máme vyhráno.

Když jsou soudělná, neplatí Čínská zbytková věta. To ale můžeme jednoduše obejít. Označme si A = ad a B = bd, kde d je jejich největší společný dělitel. Pak už jsou a a b nesoudělná. V k-tém kroku máme tedy vagón s číslem k mod da a k mod db. Když ale spočítám zbytek po dělení těchto čísel dělitelem d, zjistím, že je stejný.

Rozdělíme si tedy každý vlak na d podvlaků, Podvlak A_i bude obsahovat všechny vagóny z A, jejichž čísla dávají po dělení d zbytek i, podobně podvlak B_i. Každý vagón podvlaku A_i určitě potká každý vagón podvlaku B_i a žádný z jiného podvlaku.

Teď stačí úlohu vyřešit nezávisle pro každý z d podvlaků (nesoudělných délek), sečíst dohromady počet setkání v každém podvlaku a vydělit počtem setkání celkem. Pro každý podvlak proběhne ab setkání, podvlaků je celkem d, což dává dohromady abd – nejmenší společný násobek A a B. Tedy každé setkání proběhne opravdu právě jednou.

Časová složitost algoritmu je O(A + B), protože na každý vagón se podívám právě jednou. Rychleji to nejde – musím alespoň přečíst celý vstup. Kdybych dostal vstup jako seznam pozic nízkých vagónů, mohl bych se dostat na O(A_N + B_N), kde A_N a B_N jsou počty nízkých vagónů ve vlacích, nicméně pro vlak, který by sestával z mnoha nízkých vagónů a jednoho vysokého, dojdeme zase asymptoticky k O(A+B). Paměti mi stačí O(A+B) na uložení vstupu a na ostatní jen konstatně mnoho.

Program

Jan "Moskyt" Matějka

22-2-5 Pružinky (Zadání)

Hodně z vás hraje Pružinky natolik rádo, že jste hru nechali hrát i svůj program. Nejjednodušší bylo si v poli o každém hráči pamatovat, který z nich je ještě ve hře a který již ne. Při výpočtu složitosti nesmíte zapomenout, že ke konci můžete projít skoro všechny hráče, než narazíte na nějakého hrajícího. Pokud si označíme H počet hráčů a S délka slova, vyjde tedy časová složitost O(H²S) – provedeme H kol hry, v každém řekneme S písmenek a pro každé z nich přeskočíme až H hráčů, než najdeme dalšího hrajícího. To jde zrychlit na O(H²), když hráče, který vypadne, rovnou odstraníme z pole – hrajeme H kol, v každém v konstantním čase najdeme, kdo vypadne, ale pak potřebujeme čas O(H) na „setřepání“ pole. Pokud místo pole použijeme seznam, zvládneme hráče odstranit v konstantním čase, ale zato musíme skákat po jednom hráči, takže jedno kolo trvá O(S) a celá hra O(HS).

Rychlejší algoritmus získáme, když se zamyslíme nad rekurentním vzorcem pro nalezení vítěze. Nechť F(H,S) říká, který z H hráčů vyhraje (hráče budeme číslovat od 0 do H-1, abychom mohli počítat modulo H). F(1,S) je zjevně 0. Pokud H>1, vypadne v prvním kole hráč S mod H, a pak bude hra vypadat podobně jako hra F(H-1,S), jen s tím rozdílem, že nezačínáme hráčem 0, nýbrž S. A jelikož jsme posunuli o S (modulo H) začátek hry, musí se úplně stejně posunout i konec. Dostaneme tedy vzorec

Podle tohoto vzorce lze už v lineárním čase vítěze dopočítat:

int main(void) {
	int i, H, S;
	int vitez=0;
	scanf("%d%d", &H, &S);
	for (i=2;i<=H;i++)
		vitez=(vitez+S)%i;
	printf("%d\n", vitez+1);
	return 0;
}

Pojďme zkusit algoritmus ještě trochu zrychlit. Pokud je S výrazně menší než H, hra se ze začátku chová docela pravidelně: prvních k=⌊H/S⌋ kol se hráči nebudou opakovat, takže vypadnou ti s čísly 0,S,2S,… ,(k-1)S. Tím jsme hru převedli na nějakou s H-k hráči, jen tentokrát není pouze posunutá o S kroků, ale navíc „prostrkaná“ jednotlivými vypadlými hráči. Abychom spočítali, jak, označme f=F(H-S,S) a z=H-kS=H mod S (výsledek menší hry a počet hráčů, kteří si v prvních k kolech nezahráli). Pokud f≤ z, bude výsledek menší hry ležet v posledních z hráčích té větší a pouze jej posuneme: F(H,S)=(f+kS) mod H. V opačném případě bude ležet na (f-z)-té pozici od počátku, ovšem musíme přeskakovat hráče, kteří už vypadli – podíváme se, do které (S-1)-tice mezi 0,S,2S,… pozice f-z padla a přičteme patřičný počet vypadlých hráčů: F(H,S)=(f+kS+⌊(f-z)/(S-1) ⌋) mod H.

Jak moc tato úprava pomůže? Dokud H>S, vypadne v každé iteraci algoritmu přibližně jedna S-tina hráčů, takže se H zmenší na (1-1/S)H. Velikost hry tedy klesá exponenciálně, a proto iterací bude O(log_S/(S-1) H). Jakmile ovšem H klesne pod S, nebude nový algoritmus o nic lepší než starý a dohrajeme v čase O(S). Celková složitost je tedy O(S+ log_S/(S-1) H).

Pokud si navíc vzpomeneme, že log_a b = log a / log b a že pro malé ε>0 platí log(1+ε) ≈ ε, můžeme odhad složitosti upravit na:

(`≈ ' není `=', ale rozdíl se schová do O-čka). Zrychlený algoritmus je tedy pro velká H výhodnější.

(Mimochodem, pro S=2 byla naše úloha známá už v antických dobách, konkrétně od historika Josepha Flavia. Tato konkrétní varianta má moc pěkné řešení pomocí dvojkových zápisů čísel. Zkuste se Wikipedie zeptat na „Josephus Problem.“)

Program

Martin Mareš & Jitka Novotná

22-2-6 Otázka (Zadání)

Ačkoli se ostřílení programátoři na prohledávání do šířky dívají trochu s despektem, pravdou je, že i dobré BFS (jak se mu zkráceně poanglicku – Breadth-First Search – říká) si občas zaslouží procvičit. Úloha s magickým obdélníkem stačila řešit právě tímto algoritmem. Stavů je sice skutečně mnoho (exponenciálně k velikosti obdélníku) a náš algoritmus by v nejhorším případě musel projít všechny, ale pro 8 to zas tolik nevadilo, neboť 8! je relativně malé číslo.

Algoritmus pracuje tak, že postupně prochází od startovního obdélníku všechny obdélníky, které z něj můžeme vytvořit pomocí povolených transformací, a ukládá si nové pozice. Jakmile zjistí, že v dané „hladině“ (množina všech obdélníků, které jde vytvořit pomocí k operací) se ještě hledaný obdélník nenachází, prohledá postupně celou další hladinu.

K prohledávání celé jedné hladiny do šírky se používá datová struktura, tzv. fronta (seznam prvků, kde kdo dřív přijde, ten dřív mele a odchází) a dovolili jsme si využít již zavedenou implementaci v C++. Pokud byste se rádi dozvěděli více o prohledávání do šířky a práci front, nahlédněte do našeho textu Recepty z programátorské kuchařky, sekce Grafy.

Jako u dalších příkladů s BFS, i zde bylo třeba si pamatovat, které permutace jsme už probrali. Jinak bychom příliš často hledali tam, kde už jsme byli, což by naši závodní želvu zpomalilo na rychlost obyčejné želvy.

Malý zádrhel tkvěl v tom, že 8! možností si musíme zapamatovat alespoň trochu chytře, jinak se nám všechny probrané permutace do paměti nevejdou. Nejlépe tak, aby se vešly do jednoho integeru. 8! = 40320, to by se rozhodně mělo vejít. Jakou zvolit metodu, abychom uměli číslo rychle přeložit na standardní reprezentaci obdélníku = permutaci?

Metoda Céčkového vousáče

Znalce Céčka, C++, C# a sběratelé Céček hned napadne uložit si celou permutaci do jednoho integeru pomocí bitového kódování. Pro zakódování čísel od 0 do 7 včetně nám postačí log₂ 8 = 3 bity, v jednom integeru máme bohatých 32 bitů, což je o 8 více, než potřebujeme. K jednotlivým bitům se můžeme dostat pomocí operace „x modulo 8“, která vrátí zbytek po dělení osmi, čili poslední tři bity daného čísla x. V Céčku bychom napsali x % 8;.

Jakmile přečteme první tři bity z x, x můžeme „oříznout“ o poslední tři bity pomocí operace „right shift“.To znamená, že první tři číslice (zprava) v binárním zápisu smažeme, a aby to opět bylo platné číslo, tak zleva doplníme nulami. Číslo 101010 se posunem o 3 doprava změní na 000101. V Céčku tuto operaci zapisujeme jako x >> 3;.

Metoda sčítajícího Pascalisty

Co dělat, když se nám takto nízkoúrovňově s čísly pracovat nechce, nebo to náš jazyk (například Pascal. Většina implementací Pascalu bitové operace podporuje, ale syntaxí se mohou lišit.) příliš nepodporuje? Nezbývá, než si vymyslet jinou metodu.

Jedna z metod, kterou používáme ve vzorovém řešení, je založena na klasickém principu: přičteme i! tolikrát, které číslo chceme zapsat, a pro získání původního čísla na i-té pozici jen podělíme zakódované číslo správným faktoriálem i!. Abychom měli jednodušší život, budeme postupovat pozpátku, tedy první člen zakódujeme násobkem 7!=5040 a posledním 0!=1. Rovněž si budeme uchovávat čísla o jedno menší, než jsou, ušetří to paměť – nulu si pamatovat nepotřebujeme.

Avšak pozor! Kdyby například na páté pozici bylo číslo 8, mohli bychom nešikovně zákódovat osmičku jako 7 ·3! = 42 > 24 = 4!, a to by pokazilo rozluštění čísla zpět na permutaci. Proto si pomůžeme snadným pozorováním: Pro první číslo, násobek 7!, tento problém nenastane, a pro každé další (p-té) číslo x přičítám (8-p)! jen tolikrát, kolikrát v seznamu čísel 1..8 sáhnu na doposud v zadané permutaci nepoužitá čísla, než dojdu k číslu x.

Ukážeme si to na příkladu: pokud nyní máme v permutaci na 5. pozici 8 a víme, že obdélník začíná [4,5,3,7], spočítáme si, že seznam dosud nepoužitých čísel je [1,2,6,8] a přičteme 3 ·3! < 4! (neboť osmička je v tomto seznamu třetí, indexujeme-li úsporně od nuly). A máme nasčítáno!

Za vzorové řešení ze svých archivů děkujeme Zbyňku Faltovi.

Program

Martin Böhm & Martin "Bobřík" Kruliš & CodEx

22-2-7 Sto oslů umořilo nic (Zadání)

Producent a konzument se skladištěm

Toto se, kupodivu, skládá ze tří částí – producent, konzument a skladiště.

Producent je docela jednoduchý. Vyprodukuje jeden kousek dat a odešle ho do skladiště. Když dostane doručenku, vyprodukuje další a zase odešle.

Konzument funguje v jistém smyslu opačně. Pošle do skladu požadavek, že chce data a počká až přijdou. Poté je zpracuje a pošle nový požadavek.

Nejsložitější část je vlastní skladiště. Kdyby bylo nekonečné a mělo už nekonečně mnoho dat uložených, tak budeme jen vyřizovat požadavky o nová data (odešleme je a znovu čekáme na požadavek) a požadavky o zařazení dat (přidáme a odešleme doručenku).

Potřebujeme ale ošetřit případy, kdy jsme buď úplně plní, nebo úplně prázdní. To uděláme tak, že v době, kdy jsme plní, nebudeme zprávy s novými daty přijímat (pomocí when) a data počkají ve frontě zpráv. Proto bude v té době čekat i producent a nic produkovat nebude – nedostal doručenku. Obdobně, když nebudeme mít žádná data, nebudeme přijímat požadavky o data a ty počkají do doby, než nějaká data přijdou.

Všimněme si, že skladiště (v ukázkovém vzoráku se jmenuje buffer) si nikde nepamatuje, koho obsluhuje. Vždy má jeho PID ve zprávě, to rovnou obslouží (a nebo i s PID počká ve frontě zpráv) a zase ho zapomene. Takže nám funguje i v případě, že konzumentů či producentů je jiný počet než 1.

Program

Balené funkce

Tato úloha byla více na pozorné čtení než na programování. Použijeme lambda funkci a uvnitř si tu opravdovou funkci zavoláme i s parametrem:

producent(Skladiste, fun() -> generuj(42) end).

Samozřejmě, její parametr nemusí být konstanta, může to být cokoliv, co je k dispozici v tomto místě kódu.

Mnoho z řešitelů chtělo přidávat nový parametr do původního rozhraní. To ovšem není řešení dané úlohy (kromě toho, že je to silně nepohodlné, přepsat celé vnitřnosti kvůli změně počtu parametrů), protože požaduje dostat funkci s parametrem do stávajícího rozhraní.

Centrum práce

Napřed si popíšeme, jaké vlastně má modul rozhraní. K použití jsou tu dvě funkce (ostatní jsou exportované jen proto, aby se daly předat do spawn): start a pracant.

Když spustíme start, tak nám vrátí dvojici. První prvek je funkce, které, když se jí předá nějaká funkce, tak ji předá do centra práce jako úkol. Druhý prvek je PID centra práce.

Druhá funkce, pracant spouští pracanta. Ten potřebuje znát PID centra a začne vykonávat činnosti, které mu centrum pošle.

Nyní, jak funguje funkce na zadání práce? Jen vezme parametr a centru pošle zprávu obsahující předanou funkci (je vytvořena nová funkce pro každé PID centra, nese si ho s sebou).

Pracant hned po startu pošle centru zprávu, že by rád dostal nějakou práci a k ní přiloží své PID. Když mu přijde odpověď, spustí funkci, která v ní byla. A potom vše opakuje – opět pošle žádost o novou práci a až přijde, tak ji vykoná.

Nakonec zde máme vlastní centrum práce. Mohli bychom si pamatovat pracanty a jednotlivé úkoly. Ale to by bylo pracné a dělat to nebudeme. Raději budeme fungovat tak, že vždy přijmeme jeden úkol, přijmeme jednoho pracanta a tomu úkol přijmeme.

Jak je možné, že tohle funguje? Jednoduše, fronta zpráv si za nás pamatuje vše potřebné. Když máme k dispozici jak pracanty, tak úkoly, tak je prostě vybíráme z fronty a práci přidělujeme. Pokud se nám jedněch z nich nedostává, pak nemá cenu ty druhé vybírat z fronty a někde si je shromažďovat, stejně musíme s přidělením čekat.

A nakonec, jaká chyba se často vyskytovala? Že rozhraní bylo navržené zcela nesmyslně. Tedy, byl nějaký „generátor práce“, který centrum plnil zcela zbytečnou prací (nebo, v lepším případě, k zadání nové práce bylo potřeba udělat generátor, ten vygeneroval jednu práci a skončil). Toto ale nejen že přidávalo novou (nesmyslnou) práci, ale také si ji to vymýšlelo, což je kromě toho, že je to nepohodlné, více méně v nesouladu se zadáním.

Program