Čtvrtá série dvacátého sedmého ročníku KSP
Celý leták, který posíláme také papírově, v PDF.
Řešení úloh
- 27-4-1: Zadávání úkolů
- 27-4-2: Čtverce v síti
- 27-4-3: Vysoké napětí
- 27-4-4: NP-úplný hlavolam
- 27-4-5: Večeře pro opraváře
- 27-4-6: Stěhování pásek
- 27-4-7: Nástroj pro zpracování textu
27-4-1 Zadávání úkolů (Zadání)
Napřed uděláme jedno jednoduché pozorování. Kdybychom věděli, kolik úkolů přes konkrétního zaměstnance projde, je snadné určit, komu bude posílat další. Pokud prošel sudý počet úkolů, bude to stejný podřízený jako na začátku, v lichém případě to bude ten druhý.
Stejně tak lze snadno určit, kolik úkolů takový vedoucí předá kterému podřízenému. Pokud je počet sudý, oba podřízení dostanou polovinu. V lichém případě dostane ten začínající o jeden úkol více.
Jak tedy určit, kolik úkolů skrz kterého vedoucího projde? Začneme u ředitele. Ten svůj počet úkolů ví, máme ho tedy vyřešeného. Jeho přímým podřízeným přidáme úkoly. Poté si vybereme některého zaměstnance, který už všechny úkoly od svých nadřízených dostal; už tedy také ví, co ho čeká a nemine. Opět rozdělíme jeho úkoly a opět si vybereme někoho, kdo má všechny své nadřízené vyřešené. To děláme tak dlouho, dokud ještě někdo zbývá. Zjednodušeně, vedoucí začne rozdělovat, až když dostane všechny své úkoly.
A proč se nám nemůže stát, že sice máme ještě nějaké nevyřešené zaměstnance, ale všichni mají nějakého svého nadřízeného ještě nevyřešeného? Pro spor si představme, že se nám přesně taková nepříjemná věc stala. Vezměme tedy libovolného nevyřešeného zaměstnance. A z něj postupme do některého jeho nevyřešeného nadřízeného – takový musí z definice této nepříjemné situace existovat. A u toho nadřízeného si zase vybereme některého jeho nevyřešeného nadřízeného. Takto budeme pokračovat „nahoru“ v hierarchii, ale nikdy neskončíme. Zaměstnanců však musí být konečný počet (zřejmě v dané společnosti mohou pracovat maximálně všichni lidé na Zemi), musíme tedy jednou navštívit některého vícekrát. To ale znamená, že je v grafu cyklus, a ten máme zadáním zakázaný.
Nyní nám tedy zbývá rozmyslet, jak to napsat s co nejlepšími složitostmi. Napřed si spočítáme, kolik má který zaměstnanec nevyřešených nadřízených. Všichni začnou na nule, projdeme všechny vedoucí a každému podřízenému vždy přičteme jedničku. To zvládneme v konstantním čase na každého vedoucího. Založíme si skladiště na zaměstnance bez nevyřešeného nadřízeného (třeba zásobník, ten je příjemně jednoduchý) a při dalším průchodu přes zaměstnance do něj nastrkáme všechny, kteří mají nulu (v dobře fungující společnosti by to měl být jen ředitel). To opět zvládneme v celkově lineárním čase.
Nyní opakovaně vyndáme zaměstnance ze skladiště, vyřešíme ho a oběma jeho podřízeným odečteme jedničku. Pokud číslo u některého z nich (nebo obou) klesne na nulu, přidáme ho do skladiště také. Vyřešení jednoho nám opět bude trvat konstantní čas.
Celkově tedy zvládneme celý výpočet v lineárním čase. Lépe to nepůjde, protože jen nastavení výsledku každého zaměstnance bude trvat takovou dobu.
Co se týče paměťové složitosti, potřebujeme si ke každému zaměstnanci zapamatovat konstantně mnoho informací a potřebujeme skladiště, do kterého uložíme každého zaměstnance maximálně jednou. Tedy si vystačíme s lineární paměťovou složitostí.
A pro znalé: ano, je to topologické třídění.
27-4-2 Čtverce v síti (Zadání)
Nejdříve se zamysleme nad triviálním řešením. Můžeme zkusit vzít každou čtveřici přímek a podívat se, jestli náhodou netvoří čtverec. To pro každou čtveřici zkontrolujeme snadno – ověříme, že dvě a dvě z nich jsou rovnoběžné, tyto dvojice rovnoběžek jsou na sebe kolmé, a navíc jsou od sebe stejně daleko. Pokud si potřebujete trochu připomenout základy analytické geometrie, nahlédněte do naší kuchařky o geometrii.
Takový přístup nám zabere celkově čas O(N4). Neumíme to ale lépe? Již jsme si všimli toho, že čtverce tvoří vždy dvě dvojice rovnoběžek, toho jistě můžeme nějak využít. Tím nám ale vzniká nová otázka, a to jak rychle najít rovnoběžky mezi N přímkami v rovině.
Pokud bychom místo přímek měli třeba reálná čísla, stačilo by nám je v čase O(N log N) setřídit, čímž by se stejné hodnoty dostaly k sobě, a pak bychom jedním lineárním průchodem našli všechny duplicity. Přímky sice nejsou reálná čísla, ale můžeme si je jimi popsat.
V této fázi nás zajímá jen směr přímek, ne jejich poloha, takže nám stačí namísto popisu celé přímky vzít její směrový vektor (tedy dvojici čísel (x,y) vyjadřujících směr přímky vůči souřadným osám). Směrové vektory bychom museli ještě „znormalizovat“, tedy upravit je všechny tak, aby třeba x=1, čímž z nich vlastně získáme jedno reálné číslo, a to jejich směrnici.
Nyní si tedy můžeme všechny přímky v čase O(N log N) setřídit, dostat tak rovnoběžky k sobě a pak takto setříděné přímky lineárně projít. Pro každou nalezenou skupinu rovnoběžek budeme chtít nalézt rovnoběžky na ně kolmé. To můžeme pokaždé dělat binárním vyhledáváním v čase O(log N) na dotaz, nebo na to můžeme jít chytřeji.
Stačí nám držet si v setříděném seznamu přímek dva ukazatele posunuté od sebe o 90° a posouvat je oba najednou. Pokud nám druhý ukazatel skočí až na skupinu rovnoběžek, které ve směru otáčení svírají s rovnoběžkami na první pozici úhel větší než 90°, posuneme zase první ukazatel a tak stále dokola. Takto projdeme všechny skupiny na sebe kolmých rovnoběžek, a to v lineárním čase. Celkově nám to zabere čas O(N log N) (kvůli třídění).
Pokud by vždy byly na sebe kolmé jen dvě a dvě rovnoběžky, bylo by ověření, jestli tvoří čtverec, triviální (jen bychom zkontrolovali jejich vzdálenosti, jestli jsou stejné). Za takové řešení jste mohli získat většinu bodů, ale ne všechny. Pro plný počet bodů bylo potřeba zamyslet se i nad situací, kdy se vyskytne velké množství na sebe kolmých rovnoběžek – třeba v případě přímek uspořádaných v pravoúhlé síti (jako na obrázku ze zadání níže).
Co dělat v takové chvíli? Bylo by možné vyzkoušet každou dvojici rovnoběžek z první skupiny s každou dvojicí rovnoběžek z kolmé skupiny. Ale to by nám vlastně zdegenerovalo až na naše původní triviální řešení v čase O(N4). Nás však nezajímají jednotlivé přímky, ale jen vzdálenosti mezi nimi. V každé skupině si tedy vezmeme všechny možné vzdálenosti mezi přímkami (těch je K2 pro K přímek, tedy O(N2) pro nejhorší případ), ty si v čase O(N2 log N2) = O(N2 log N) utřiďme a pak tyto dvě setříděné posloupnosti porovnejme.
Stačí nám pro každou vzdálenost, která se vyskytne v jedné z posloupností, spočítat součin počtu výskytů této vzdálenosti v první posloupnosti a počtu výskytů této vzdálenosti ve druhé posloupnosti (součin proto, že čtverec tvoří každé dvě dvojice). Všechny tyto součiny sečteme a dostaneme tak počet vytvořených čtverců.
Pro případy, kdy se na vstupu vyskytne mnoho rovnoběžných přímek, umíme dosáhnout času O(N2 log N) s paměťovou složitostí O(N). Pro případy, kdy bude rovnoběžných přímek málo, se bude čas běhu našeho postupu blížit spíše O(N log N).
27-4-3 Vysoké napětí (Zadání)
Lehčí varianta
Většina z vás si všimla, že máme-li nějaké korektní řešení, můžeme vyrobit další správné řešení tím, že prohodíme všechna 100kV napětí v uzlech za 0kV a 100kV za 0kV. Z toho speciálně dostáváme, že si můžeme vybrat libovolný uzel a přiřknout mu hodnotu 0 kV. Existuje-li totiž nějaké korektní řešení, kde tento uzel má napěťovou hladinu 100 kV, existuje korektní řešení, kde má hladinu 0 kV.
Pak si stačí všimnout, že napěťová hladina v prvním uzlu jednoznačně určuje napěťové hladiny v sousedních uzlech, ty zase ve svých sousedech a tak dále, až se jednoznačně určí celý graf. Toto řešení můžeme tedy nalézt jednoduchým průchodem například do hloubky.
Vždy když zkoumáme nějaký uzel, který ještě nemá určenou napěťovou hladinu, určíme ji podle napěťové hladiny předchozího uzlu a rozdílu napětí na vodiči, jež tyto uzly spojuje – v případě, že rozdíl napětí byl 0 kV, budou napětí v uzlech stejná, pokud byl rozdíl 100 kV, budou napětí opačná. Pak začneme prohledávat všechny jeho sousedy.
Pokud zkoumaný uzel již má určenou napěťovou hladinu, jen zkontrolujeme, jestli tato hladina souhlasí s hladinou, kterou bychom jí jinak přiřkli. Jestliže nesouhlasí, dostáváme spor a graf nelze ohodnotit. Pokud souhlasí, tak je vše v pořádku (jeho sousedy již prohledávat nemusíme, neboť jsme je prohledali při první návštěvě tohoto uzlu).
Musíme si pamatovat celý graf a u každého uzlu a hrany konstantní množství informací, paměťová složitost bude tedy O(n+m), kde n je počet uzlů a m počet hran. Celý graf musíme načíst a pak pro každou hranu provedeme konstantní množství kroků (zpracování jednoho uzlu), dostáváme tedy opět O(n+m).
Tři napěťové hladiny
Dobrý nápad je využít řešení jednodušší varianty. Vezměme náš graf a odstraňme z něj všechny vodiče s rozdílem napětí 100 kV. Tímto se nám graf rozpadne na několik komponent. Smažme ty, které neobsahují žádný vodič s rozdílem 200 kV. Zůstavší komponenty vyřešíme podobně jako jednodušší variantu. Jen musíme místo 100 kV pracovat s 200 kV a také nám tu nastává ten problém, že máme více komponent. Musíme tedy prohledávání z jednodušší varianty postupně spouštět ze všech uzlů. Rozmyslete si, že to nám nijak nezhorší asymptotickou časovou složitost (většinou se spustíme na uzel s již určenou hladinou, a tedy hned skončíme).
Máme tedy určené napěťové hladiny všech uzlů sousedících s vodičem s rozdílem 200 kV a uzlů, které jsou z těchto uzlů jednoznačně určené. Zbývá tedy určit napěťové hladiny uzlů, které s žádným 200kV vodičem nesousedí, a zkontrolovat, jestli hladiny, které jsme určili, souhlasí s uzly k nim připojenými 100kV vodičem (0kV vodiče řešit nemusíme, neboť ty jsme řešili již v prvním kroku).
Rozmysleme si, že ohodnocené komponenty jsou navzájem spojeny cestičkami z vodičů s rozdílem 100 nebo 0 kV, kde navíc první a poslední vodič v každé cestičce je 100kV. Uzel na druhém konci tohoto vodiče musí mít hladinu 100 kV, protože výchozí uzel má hladinu buď 200 kV, nebo 0 kV. Kromě toho musíme ještě zkontrolovat, že toto přiřazení nenarušilo dosavadní přiřazení hladin (to by nastalo v případě, že by byly dvě komponenty spojeny právě jedním vodičem), pak by řešení neexistovalo.
Nyní si stačí dočasně odmyslet již ohodnocené komponenty (až na ty poslední uzly s hladinou 100 kV). Zbudou nám tedy pouze uzly s hladinou 100 kV a vodiče s rozdíly napětí 0 kV a 100 kV. Nabízí se tedy opět využít řešení jednodušší varianty. Spor s dosud ohodnocenými komponentami nám určitě nenastane, neboť s nimi jsme spojeni pouze přes původní 100kV uzly. Takto tedy dojdeme ke sporu a zjistíme, že řešení neexistuje, nebo nalezneme korektní řešení.
Opět si stačí pamatovat graf, takže paměťová složitost bude O(n+m). Co se týká časové, tak nejprve provedeme jednou jednodušší variantu na ohodnocení části grafu, poté v lineárním čase označíme nějaké 100kV uzly a poté znovu provedeme variantu jednoduššího algoritmu. Opět tedy dostaneme časovou složitost O(n+m).
27-4-4 NP-úplný hlavolam (Zadání)
Jak dobře víte z kuchařky, důkaz NP-úplnosti obvykle sestává ze dvou kroků – důkazu toho, že problém leží ve třídě NP, a převodu některého problému, o kterém již víme, že je NP-úplný, na tento náš problém.
První krok je v našem případě velice snadný. Jako certifikát použijeme seznam sloupců,
pod které jsou zasunuty barevné proužky. Ověření certifikátu určitě v polynomiálním čase
zvládneme, stačí totiž pro každý řádek přímočaře spočítat, kolik barevných polí je vidět.
Druhý krok lze provést více způsoby. Pokud jste pečlivě prohledávali informatickou literaturu (či Wikipedii), mohli jste zjistit, že náš problém (přirozeně trochu jinak formulovaný) lze najít už ve slavné knize Computers and Intractability: A Guide to the Theory of NP-Completeness pánů Gareyho a Johnsona z roku 1979 pod kódem LO4.
Zde si předvedeme převod z problému Trojbarevnosti grafu. Jeho znění pro jistotu připomínáme.
Název problému: Trojbarevnost grafu
Vstup: Neorientovaný graf.
Problém: Lze vrcholy tohoto grafu obarvit třemi barvami tak, že každá hrana sousedí s vrcholy dvou různých barev? (V obarvení musí mít každé dva sousední vrcholy různou barvu.)
Nechť G = (V,E) je neorientovaný graf, jehož trojbarevnost máme rozhodnout. Značíme n = |V| a m = |E|. Naším cílem je konstrukce hlavolamu, který má řešení právě tehdy, když je graf G trojbarevný. Tento hlavolam bude mít celkem 3n+3m sloupců. Pro každý vrchol v ∈V mějme tři sloupce čv, mv a zv. Pro každou hranu e ∈E a každou barvu b ∈{č,m,z} sloupec se,b.
Nejprve zajistěme, že každé řešení hlavolamu vůbec reprezentuje nějaké obarvení grafu. Pro každý řádek přidáme řádek, který vynucuje, že právě jeden ze sloupců čv, mv a zv je barevný. Jak poznáme, jakou barvu má vrchol v? Podíváme se, který ze sloupců čv, mv a zv je barevný.
Zbývá zajistit, aby každé řešení hlavolamu reprezentovalo obarvení, ve kterém mají sousední vrcholy různé barvy. Pro každou barvu b ∈{č, m, z} a každou hranu e = {u, v} přidáme řádek, který říká, že právě jeden ze sloupců bu, bv a sb,e je barevný. Podotkněme, že sloupec sb,e má úlohu ryze pomocnou – umožňuje nám říci „nejvýše jeden ze sloupců bu a bv je barevný“.
Každé řešení hlavolamu tudíž odpovídá správnému trojobarvení. Naopak i pro každé správné trojobarvení, jak si snadno rozmyslíte, lze nalézt odpovídající řešení zadaného hlavolamu.
Náš převod je tedy korektní a zřejmě je možné jej realizovat v polynomiálním čase. Důkaz je hotov.
27-4-5 Večeře pro opraváře (Zadání)
V úloze procházíme čtvercovou síť a cílem je najít nejkratší cestu, která vede přes všechny vyznačené hospody a restaurace, těch je maximálně n ≤ 20. Na zadání se podíváme jako na úplný ohodnocený graf s n vrcholy reprezentujícími hospody. Ohodnocení získáme jako vzdálenosti mezi hospodami ve čtvercové síti, které můžeme získat spuštěním průchodu do šířky z každé hospody zvlášť. Určitě se nám nevyplatí používat jiné než tyto nejkratší cesty, protože mezi dvěma hospodami se vždy vyplatí jít přímo bez jakéhokoliv odbočování. Toto převedení zvládneme v čase O(n · WH), kde W a H značí šířku a výšku mapy.
Teď stačí najít nejkratší cestu v úplném ohodnoceném grafu, která každý vrchol navštíví právě jednou. Tento problém je známý pod jménem „Problém obchodního cestujícího“ (TSP) a je NP-úplný. To znamená, že není známý žádný polynomiální algoritmus, který by jej řešil. My si ukážeme algoritmus, který jej řeší v čase O(n2 2n) a v prostoru O(n2n), což je pro n ≤ 20 dostačující.
Úloha by se dala řešit obyčejným backtrackem. Víme, v jakém vrcholu aktuálně stojíme (pro počáteční vrchol zkusíme všechny možnosti) a které vrcholy jsme již navštívili. Pro další v pořadí postupně zkusíme všechny možnosti nenavštívených vrcholů, přesuneme se tam a pokračujeme v backtracku z nich. Takové řešení by ale mělo časovou složitost až O(n n!), protože vlastně postupně zkoušíme všechny permutace vrcholů.
My ale toto řešení dokážeme vylepšit. Stačí nám do backtracku přidat ještě myšlenku dynamického programování: Při každém volání backtrackové funkce se stejnými parametry (aktuální vrchol, množina navštívených vrcholů), musíme nutně dostat i stejný výsledek. Tedy jakmile jednou výsledek pro konkrétní parametry spočítáme, tak si jej uložíme do paměti a při dalším volání jej v konstantním čase vrátíme. Počet možností pro aktuální vrchol je n a počet možností pro množinu navštívených vrcholů je 2n (každý vrchol v ní buď je, anebo není). Celkově tedy backtracková funkce proběhne maximálně O(n2n)-krát.
Zbývá určit čas, který nám zabere jedno volání backtrackové funkce. Ta jen pro každý z n vrcholů zkontroluje, zda je v množině již navštívených vrcholů a pokud ne, tak v něm rekurzivně zavolá backtrack. Pokud testování, zda vrchol je součástí množiny, zvládneme v konstantním čase, dostáváme se na časovou složitost O(n2 2n) a paměťovou O(n 2n).
Jelikož vrcholů je maximálně 20, můžeme si jakoukoliv podmnožinu vrcholů reprezentovat jako n-bitové číslo. Pak, pokud i-tý bit má hodnotu 1, vrchol je v podmnožině a pokud 0, vrchol v ní není. Přidávání do množiny a zjišťování, jestli v ní vrchol je, tedy zvládneme v konstantním čase pomocí bitových operací, vizte vzorový kód.
27-4-6 Stěhování pásek (Zadání)
Jak jste možná poznali, přesouvání kotoučů ze zadání odpovídá slavné úloze o Hanojských
věžích, kterou poprvé popsal francouzský matematik Édouard Lucas. (Zadání úlohy z pera
autora si můžete přečíst i nyní. Je sepsáno ve třetím svazku jeho díla Récréations
mathématiques na straně 55, dostupno on-line: https://archive.org/details/recretionmatedou03lucarich)
Pro úplnost dodejme, že v původní podobě úlohy se místa A, B a C
nazývají tyčemi, kotoučů je celkem čtyřiašedesát, všechny kotouče jsou z ryzího zlata a na začátku
jsou umístěny na jedné tyči. Mnichové každý den jeden kotouč přesunou z tyče na tyč (stále
platí, že nesmí být větší kotouč položen na menší). V okamžiku, kdy se jim podaří
přemístit všechny kotouče na třetí tyč, nastane podle legendy konec světa.
Než se pustíme do samotného uspořádávání fotografií pořízených při stěhování dat, potřebujeme porozumět tomu, jak se kotouče správně přesouvají. Konkrétně si ukážeme, jak lze přemístit všechny kotouče na co nejmenší počet tahů, a společně s tím dokážeme, že se jedná o jediný možný postup s nejmenším počtem tahů. To nám dá jistotu, že tentýž postup použili i pracovníci vystupující v zadání úlohy. Celý postup popíšeme rekurzivně (pokud si s rekurzí příliš nerozumíte, můžete v případě nesnází nahlédnout do naší kuchařky o základních algoritmech). Celkově máme N kotoučů, očíslujeme si je od nejmenšího po největší čísly 1 až N.
Funkce přesun(k, výchozí, cílová, pomocná):
- Pokud k = 0 → skonči
- Zavolej přesun(k-1, výchozí, pomocná, cílová)
- Přesuň kotouč k z tyče výchozí na tyč cílová
- Zavolej přesun(k-1, pomocná, cílová, výchozí)
Funkce přesun(k, výchozí, cílová, pomocná) předpokládá, že na tyči výchozí se nachází kotouče 1, 2, … , k, a zařídí přesun všech těchto kotoučů na tyč cílová. Nyní pomocí matematické indukce dokážeme, že nejmenší možný počet tahů pro přesunutí všech N kotoučů je 2N-1 a lze jej dosáhnout pouze pomocí našeho postupu.
Když nemáme žádné kotouče, přesuneme je pomocí nula tahů a je to jediný možný způsob přesunu (nebo spíš nepřesunu). Platí rovnost 20 - 1 = 0 a základ indukce je ověřen.
Předpokládejme nyní, že jsme již toto tvrzení dokázali pro N = k-1. Dokažme jej pro N = k. Klíčové je následující pozorování: v okamžiku, kdy je přesouván největší kotouč mezi dvěma tyčemi, musí být všech k-1 ostatních kotoučů umístěno na třetí tyči. Z předpokladu víme, že jediný způsob, jak přesunout k-1 kotoučů z výchozí tyče na pomocnou tyč na co nejmenší počet tahů, je použít náš postup, který potřebuje 2k-1-1 tahů. V dalším kroku je přesunut největší kotouč na cílovou tyč a zbývá na tuto tyč přesunout zbylých k-1 kotoučů. Opět díky předpokladu víme, že na nejmenší počet tahů toho docílíme jedině s použitím našeho postupu. Ukázali jsme tak, že v případě N = k náš postup potřebuje 2(2k-1-1) + 1 = 2k-1 tahů a každý jiný postup by tahů potřeboval víc.
Když už rozumíme tomu, jak kotouče přesunovat, můžeme se pustit do samotného řazení fotografií. Postupně budeme rekonstruovat pro zadané fotografie, v jaké fázi přesunu se nacházíme. Na začátku si fotografie můžeme rozdělit do dvou přihrádek podle toho, kde se nachází největší kotouč. Pokud se nachází na výchozí tyči, znamená to, že teprve přesouváme menší kotouče z výchozí na pomocnou tyč; takové fotografie určitě předchází všechny fotografie, u kterých se největší kotouč nachází na tyči cílové, tam už jsme ve fázi přesunu menších kotoučů z pomocné na cílovou tyč. Podobný postup můžeme zopakovat pro uspořádání každé z hromádek, když se podíváme na polohu druhého největšího kotouče. Tento postup lze opakovat, dokud nesetřídíme všechny fotografie. Celou proceduru shrnuje pseudokód.
Funkce uspořádej(k, fotografie, v, c, p):
- Pokud k = 0 → skonči
- Pro každou fotografii z pole fotografie:
- Pokud se k-tý kotouč nachází na tyči v, umísti fotografii do pole h1
- Jinak umísti fotografii do pole h2
- seřazení1 = uspořádej(k-1, h1, v, p, c)
- seřazení2 = uspořádej(k-1, h2, p, c, v)
- Výstup: Zřetězení seřazení1 a seřazení2
Uspořádání všech fotografií docílíme následujícím zavoláním: uspořádej(N, fotografie, A, B, C), kde fotografie označuje pole všech fotografií.
Celkový počet fotografií označme jako F. Každá fotografie je v průběhu řazení zpracována celkem N-krát. Pokud bychom proceduru implementovali doslova podle pseudokódu, dosáhli bychom složitosti O(FN2), protože bychom pokaždé potřebovali čas O(N) na zpracování jedné fotografie, například při umisťování do přihrádek. Nám ovšem stačí pracovat pouze s odkazy na fotografie, což nám dá výslednou časovou složitost O(FN). Paměťová složitost je přirozeně taktéž O(FN).
27-4-7 Nástroj pro zpracování textu (Zadání)
Seriál opět patřil mezi vaše oblíbené úlohy, patřil mezi tři úlohy s nejvíce odevzdáními. Proto doufáme, že se ze řešení naučíte třeba nové triky a že s námi zůstanete i v poslední sérii.
Úkol 1 – Náhodné dvojice
Většina řešitelů se shodla na základním postupu: vstupní soubor zamícháme
(pomocí shuf) a poté spárujeme sousední dvojice řádek. Ukážeme si hned
několik způsobů, které se mezi řešeními objevily.
Asi nejjednodušší na vymyšlení je použití bashového cyklu
a readů:
shuf | while read a; do
read b
echo "$a:$b"
done
O něco elegantněji a stále jednoduše se dá využít sedu:
shuf | sed -re 'N; s/\n/:/;'
Jak již víme, příkaz N načte další řádek a přilepí ho do
pattern space oddělený znakem \n. Ten stačí nahradit
dvojtečkou a jsme hotovi. Při příští iteraci se pokračuje
nejbližším ještě nezpracovaným řádkem, tedy třetím, pak pátým, atd.
Velmi podobná věc se dá udělat i pomocí awk (inspirováno
řešením Štěpána Hudečka):
awk '{ printf "%s:", $0; getline; print; }'
A na závěr jedno mile bláznivé řešení podle Jakuba Tětka:
shuf | awk '{ ORS = NR%2 ? ":" : "\n" } 1'
Zkuste schválně vymyslet, co dělá ta jednička na konci ;-).
Tato úloha byla původně zamýšlena jako cvičení na paste,
leč ukázalo se, že naše řešení je výrazně složitější než ta ukázaná
výše. Základní myšlenka je zamíchat vstup, rozdělit do dvou souborů
jeho první a druhou polovinu, a ty poté spojit do dvojic právě pomocí
paste:
shuf >jmena.rand
half=$(($(wc -l jmena.rand) / 2 ))
head -n $half >prvni.tmp
tail -n $half >druzi.tmp
paste -d: prvni.tmp druzi.tmp
Úkol 2 – Převrácená slova
Nejprve vyřešíme nalezení vyhovujících slov, výběr nejdelšího doplníme na konci.
Dobrým začátkem určitě bude vytvořit si soubor s převrácenými verzemi všech slov
ze slovníku, což nám zařídí onen podivný příkaz rev. Snadno si rozmyslíte,
že hledaným řešením jsou právě slova, která se vyskytují jak v původním slovníku,
tak v tomto pomocném souboru. K hledání průniku dvou souborů přímočaře poslouží
příkaz comm – jen si nejdřív oba musíme setřídit. Řešení by mohlo vypadat
takto:
sort -u slovnik >slovnik.sort
rev slovnik | sort -u >slovnik.rev
comm -12 slovnik.sort slovnik.rev
Někteří řešitelé přišli s alternativním postupem, který namísto comm používá
příkaz uniq. Hledání průniku můžeme provést taky tak, že oba soubory (původní
slovník a jeho reverzi) slepíme do jednoho a z něj vybereme všechny duplicitní řádky.
K tomu lze (po setřídění) použít příkaz uniq -d, který přikazuje vypisovat
pouze řádky s více než jedním opakováním.
Alternativně lze použít uniq -c
a z výsledku odgrepovat všechny řádky s jedničkou na místě počtu opakování. Za předpokladu,
že původní slovník neobsahoval duplicity, jeden z výskytů duplicitního řádku musel
pocházet z jednoho souboru a druhý z druhého, tedy patří do průniku. A případných
duplicit se snadno na začátku zbavíme příkazem sort -u.
{ sort -u slovnik; rev slovnik | sort -u; } \
| sort | uniq -d
Nyní k výběru nejdelšího. To snadno vyřešíme jednoduchým skriptem pro awk,
který bude v nějakých proměnných průběžně udržovat dosud nejdelší
slovo a jeho délku a na konci ho jen vypíše:
awk '{
if (length > maxlen) {
maxlen = length;
word = $0;
}
}
END { print word; }'
Pokud vám přijde toto řešení příliš „céčkové“, dá se postupovat
i jinak.
Necháme awk jen připsat ke každému řádku jeho délku a pak
využijeme příkazu sort. Takové řešení má sice složitost
O(N log N) namísto lineární, ale to nás v praxi příliš netrápí.
awk '{print length,$0}' | sort -nr | head -n 1 \
| cut -d' ' -f2-
Úkol 3 – Seriály
Tato úloha byla spíš technickým cvičením a asi se nedá vymyslet úplně hezké a elegantní řešení. K úloze lze přistoupit ze dvou stran:
- Projít soubory v cílovém adresáři, z každého z nich zkusit vytáhnout správná čísla, najít informace v seznamu epizod a přejmenovat ho.
- Projít stažený seznam epizod, pro každou se pokusit najít odpovídající soubor a přejmenovat ho.
Většina řešitelů se přiklonila k první variantě. Ta se ale ukázala
poměrně nebezpečnou, neb téměř nikdo neřešil, co se stane se soubory,
jejichž název není ve správném formátu, případně pokud příslušná epizoda není
nalezena v seznamu. Ve většině případů to skončilo tím, že se čísla
série a epizody naparsovaly jako prázdné řetězce, název se v seznamu
nenašel a z toho vznikl název typu S00E00_.avi. Pokud by bylo
v adresáři nerozpoznaných souborů víc, všechny byly přejmenovány na
tento stejný název, čímž se navzájem přepsaly.
Například většina skriptů byla
ochotna takto přejmenovat i sebe sama, pokud si je člověk uloží do
stejného adresáře, případně i své pomocné soubory.
Tento úkol mě přesvědčil, že opravování KSP je riziková činnost. Jeden z došlých skriptů totiž začal takovýmto způsobem přepisovat soubory v mém domovském adresáři. Za to mohl (společně s problémem popsaným výše) nevinně vypadající příkaz na začátku skriptu:
cd $1
Pokud takovýto skript omylem spustíte bez parametrů, dle pravidel bashové
expanze se $1 zcela zahodí a spustí se příkaz cd bez
parametrů, který skočí do domovského adresáře uživatele.
Samozřejmě všechny tyto problémy se dají ošetřit (testováním, zda
soubory mají správný formát názvu, přidáním uvozovek na vhodná místa,
použitím mv -i, atd.), ale je to docela otrava a není jednoduché
na nic nezapomenout. Proto si raději ukážeme druhý způsob, který těmito
neduhy netrpí.
Celé řešení může vypadat třeba takto:
w='http://en.wikipedia.org/wiki/'
for S in $(seq 1 8); do
art="The_Big_Bang_Theory_(season_$S)"
curl -s "$w/$art?action=raw" \
| grep -E '\|(EpisodeNumber2|Title)' \
| cut -d= -f 2 \
| sed -re 's/^ +//' \
-e 's/^\apl{\tt \[.*\|(.*)\]\]$/\1/;' \
| tr -d '[}' | tr ' ' . \
| while read E; do
read title
newfn="$(printf 'S%02dE%02d.%s.avi' \
"$S" "$E" "$title")"
re="[^0-9]0*$S[^0-9]+0*$E[^0-9].*\.avi"
oldfn="$(ls |grep -E "$re" |head -n1)"
if [ -n "$oldfn" ]; then
mv -vi "$oldfn" "$newfn"
fi
done
done
První část (před while) stáhne seznam epizod a převede jej do
zpracovatelného formátu. Po grepu vypadá seznam takto:
|EpisodeNumber2 = 1
|Title = [[Pilot (TBBT)|Pilot]]
|EpisodeNumber2 = 2
|Title = The Big Bran Hypothesis
...
Dvojité hranaté závorky značí odkaz na jiný článek, kterého se musíme
zbavit. Má tvar [[název článku]] nebo
[[název článku|text odkazu]].
Seznam sloužící jako vstup pro while cyklus vypadá po zpracování takto:
1
Pilot
2
The.Big.Bran.Hypothesis
...
Poté načítáme dvojice řádků stejným trikem jako v prvním úkolu.
Pro každou epizodu pak sestavíme nový název a regex, kterému musí
vyhovovat původní název (bohužel se nedá jednoduše matchovat pomocí
wildcardů). U obojího si musíme dát pozor na úvodní nuly
u čísla série a epizody. Původní názvy je mít mohou a nemusí, nové
názvy by měly, kvůli správnému řazení. Poté se stačí jen podívat,
jestli existuje soubor vyhovující danému regexu, a pokud ano, přejmenovat
jej. Parametr -v informuje uživatele o tom, jaká přejmenování
byla provedena, a -i předchází nechtěnému přepisování souborů.
Úkol 4 – Identifikátory
Tento úkol měl dvě netriviální části: odstranění řetězců a víceřádkových
komentářů. Začněme řetězci. Na céčkový řetězec se dá dívat jako na
posloupnost „elementů“, kde každý z nich je buď obyčejný znak, nebo
escape sekvence. Escape sekvence jsou obvykle ve tvaru \znak, existují
i složitější, ale ty si dovolíme ignorovat, princip je podobný. Lze
tedy sestavit jednoduchý regex, kterému vyhovuje právě jeden céčkový
řetězec, i když obsahuje escapované znaky, včetně uvozovek:
"([^\\"]|\\.)*"
Tento regex vlastně docela blízce simuluje to, jak skutečný céčkový
překladač parsuje zdrojový kód.
Rozmyslete si, že opravdu namatchuje, co má, bez ohledu
na počet escapovaných uvozovek a zpětných lomítek, včetně případů jako
"\\\"\\". Někteří řešitelé přišli s o trochu méně elegantním,
ale správným a myšlenkově jednodušším postupem: nejdřív odstraníme
ze zdrojáku
všechny escape sekvence (nemusíme kontrolovat, jestli jsou uvnitř
řetězce, jinde se legálně vyskytnout nemohou) a poté už řetězce najdeme
jednoduše:
sed -re 's/\\.//g; s/"[^"]*"//g;'
Nyní zbývá odstranění víceřádkových komentářů. To jde jednoduše vyřešit
tak, že z celého zdrojáku uděláme jeden řádek a chováme se k nim jako
k jednořádkovým. Leč z cvičných důvodů jsme chtěli, abyste to vyřešili
jinak, a na to se velmi dobře hodí pokročilý sed.
Ale ještě než se začneme starat o víceřádkovost, musíme vyřešit opačný problém: více komentářů na jednom řádku, např. takto:
int h /*pocet hrochu*/, b /*pocet bagru*/;
Ne, že bychom tento styl kódu doporučovali, ale náš skript by
se jím neměl nechat zaskočit. Díky žravosti regexů nemůžeme napsat prostě
/\*.*\*/, neb tomuto výrazu by vyhovovalo vše od prvního /*
k poslednímu */, tedy i celý úsek mezi komentáři obsahující
platný identifikátor b. To můžeme vyřešit podobně jako u řetězců:
zakázat výskyt ukončovacího oddělovače uvnitř komentáře. Tady je to jen
trochu těžší v tom, že je dvouznakový. Dalo by se to udělat třeba takto:
sed -re 's#/\*([^*]|\*[^/])*\*+/# #g'
Nyní se zamysleme, co s víceřádkovými komentáři. Postup bude jednoduchý. Pro každý řádek opakujeme následující kroky, dokud se něco děje:
- Odstraň všechny ukončené komentáře.
- Dokud existuje neukončený komentář, smaž jeho obsah až do konce řádku a načti další řádek.
Do sedu to přeložíme takto:
sed -re '
: loop;
s#/\*([^*]|\*[^/])*\*+/# #g;
t reset
: reset
s#/\*.*$#/*#;
T;
N;
b loop;
'
Pokud neuspěje druhý příkaz s, znamená to, že na řádku
není neukončený komentář. Všechny ukončené komentáře byly již odstraněny,
takže s aktuálním řádkem jsme hotovi. Příkaz T v takovém případě skočí
na konec skriptu, což způsobí vypsání aktuálního obsahu pattern space
a přechod na další řádek. V opačném případě je příkazem N
přilepen následující řádek na konec aktuálního a celý proces se opakuje.
Pokud už jsme našli konec komentáře, odstraní se celý, jinak načítáme
další řádky.
Dát to vše dohromady a přidat odstranění jednořádkových komentářů a klíčových slov by již mělo být jednoduché cvičení.