Čtvrtá série dvacátého třetího ročníku KSP
Celý leták, který posíláme také papírově, v PDF.
Zadání úloh
Jen výjimečně se najdou lidé píšící programy s dokumentací obsáhlejší než
samotný kód a provádějící veškerou činnost s obdivuhodnou pečlivostí. V této
sérii si představíme osobnost, pro niž je psaní dobře okomentovaných programů
takřka denním chlebem a která povýšila programování na umění programování.
Možná už tušíte, že se jedná o Donalda Ervina Knutha, a vybavilo se vám jeho
dílo Umění programování (v originále The Art of Computer Programming),
obsahující mnohé znalosti informatiky, popisy základních algoritmů a jejich
matematickou analýzu. Výjimečnost tohoto muže potvrzuje i titul emeritního
profesora (plným názvem Professor Emeritus of The Art of Computer Programming)
na Stanfordově univerzitě v USA.
Emeritní znamená, že odešel z profesionálního života, nicméně mu zůstal čestný
profesorský titul. Knuth se totiž rozhodl opustit univerzitu, aby se mohl plně
věnovat práci na Umění programování. Chce-li napsat o nějakém tématu,
hluboko se do něho ponoří, přečte o něm spoustu článků, z nichž vybere pro
čtenáře nejpřínosnější poznatky, každý algoritmus si naprogramuje…
Proto také jeho práce na Umění programování trvá již od roku 1962, nyní jsou
napsány tři svazky (Základní algoritmy, Seminumerické algoritmy, Vyhledávání a
třídění), čtvrtý (Kombinatorické algoritmy) se dokončuje, ale v plánu jsou
ještě další tři.
Celkem by tedy mělo vyjít sedm svazků.
23-4-1 Studenti a profesoři (12 bodů)
Jedna z věcí, jež ho na univerzitě
zaměstnávala (a tedy mu ubírala čas od psaní), bylo vedení vědeckých prací
studentů (např. psaní článků do odborných časopisů).
Studenti na Stanfordově univerzitě se chtějí prosadit a napsat co nejvíce
článků, přičemž každý z nich má vytipováno několik profesorů, pod jejichž
vedením by chtěl článek psát. S jinými profesory spolupracovat nechce a nebude.
Studenti jsou schopni psát maximálně K článků najednou. Leč čas profesorů je
omezený, každý z nich je totiž ochoten spolupracovat maximálně s K studenty,
přičemž je jim jedno, kteří to budou.
Vaším úkolem je najít algoritmus, který zjistí, jestli je možné, aby každý
student psal právě K článků a každý profesor spolupracoval právě s K
studenty, a pokud ano, tak vypsat, který student bude spolupracovat s kterým
profesorem.
Můžete předpokládat, že profesorů i studentů je stejně, totiž N, a nemusíte
uvažovat situaci, že by student chtěl psát u jednoho profesora více článků.
Příklady: pro vstup N = 4, K = 2, student S1 chce psát článek s profesory
P1 a P2, student S2 s P1, P2, P3, P4, student S3 s P2, P3, P4 a student S4
s profesory P3, P4, jsou řešením tyto páry student–profesor: S1–P1, S1–P2,
S2–P1, S2–P3, S3–P2, S3–P4, S4–P3, S4–P4.
Pro vstup N = 5, K = 2, studenti S1 a S2 chtějí psát u profesorů P1, P2,
P3, student S3 u P3, P4, P5 a studenti S4, S5 u P4, P5, řešení neexistuje.
Existovalo by, kdyby bylo K = 1, ale to už je zase jiný vstup.
Řešení
Aby byl Knuth při své práci co nejméně vyrušován, zrušil si 1. ledna 1990
e-mailovou adresu. Jak píše na svém webu, cítí se nyní šťastnější, protože mu už
nechodí nevyžádaná pošta. I přesto výhod elektronické komunikace a internetu
stále využívá, ale většinu e-mailů za něj vyřizuje jeho sekretářka.
23-4-2 Paralelní profesoři (10 bodů)
Na chvíli si představme, že neexistuje nic
jako e-mail, internet, ba dokonce obyčejná „šnečí“ pošta. Jak by si takoví
profesoři sdělovali své poznatky?
Na univerzitě pracuje N profesorů. Na začátku dne má každý svůj unikátní nový
objev, který chce sdělit všem ostatním.
Jelikož však ve skupince třech a více profesorů je vzájemné sdělování poznatků
nemožné kvůli překřikování, pořádají profesoři během dne občas sezení. Během
nich utvoří dvojice (ne nutně všichni jsou ve dvojici) a ve dvojicích si vymění
všechny objevy, které mají (tedy i objevy získané dříve od jiných profesorů).
Během sezení se dvojice nemění.
Jaký je pro různá N minimální počet sezení, která musí proběhnout, aby každý
profesor znal objevy všech svých kolegů?
Třeba pro N = 2 stačí jedno sezení, pro N = 4 jsou potřeba dvě (nejdřív A–B a
C–D a potom A–C a B–D).
Řešení
Jak D. E. Knuth nedávno v jednom rozhovoru poznamenal, mnohdy naráží na odborné
texty, jejichž jediným cílem je překonat tajuplnými metodami jednodušší
algoritmy, ale pouze, když bude velikost vstupu větší než počet protonů
ve vesmíru. Ve svých knihách proto předkládá jednodušší, ale stále efektivní
metody.
Jak však ukáže následující úloha, ne vždy jsou jednoduché a rychlé metody
dobré.
23-4-3 Zabugovaný program (8 bodů)
Dva zlatokopové objevili bohaté ložisko zlata a společně vykopali velké
množství nugetů. Chtějí se o ně rozdělit rovným dílem, na což si napsali
program. Každý nuget má svoji zadanou cenu (přirozené číslo), seznam nugetů
program dostane na vstupu, na výstup vypíše, jak si je mají rozdělit, nebo
oznámí, že řešení neexistuje.
Například pro nugety o hodnotách 3, 3, 5, 5 dostanou oba nugety s cenou 3, 5;
pro sadu nugetů 3, 3, 5 řešení neexistuje.
Co čert (nebo spíš zlatokop) nechtěl, v programu je chyba a ne malá, nehledejte
tedy zapomenutý středník, chybu v použití knihovní funkce jako qsort
nebo neošetření čtení vstupu. Zlatokopové špatně vymysleli celý algoritmus a
program by si zasloužil od základu přepsat.
To však nechte na nich, ať se pocvičí v algoritmizaci, vaším úkolem bude
pouze přesvědčit je, že program napsali špatně – najít jim vstup, na němž
vypíše špatný výsledek, a určit pro tento vstup správný výsledek. Bonusové body
neminou řešitele, kteří najdou nejmenší takový vstup co do počtu předmětů nebo
celkové ceny.
Zadání (Python)
Zadání (C)
Řešení
Zmiňme ještě trochu biografických údajů. Donald Ervin Knuth se narodil v roce 1938
ve Wisconsinu. Už od mládí vykazoval vysokou inteligenci, když v 8 letech
dokázal složit z písmen „Ziegler's Giant Bar“ 4500 anglických slov do jedné
soutěže, přestože porota měla jen 2500 slov. V roce 1956 nastoupil na Case
Institute of Technology na fyziku, ale byl záhy přesvědčen, aby se věnoval
matematice.
K informatice se dostal v podstatě náhodou při své letní práci, když narazil na
počítač IBM 650. Zaujal ho natolik, že u něj strávil dlouhé hodiny jeho
zkoumáním. Ve 20 letech napsal program na analýzu výkonnosti univerzitního
basketbalového týmu, který mu vynesl trochu slávy. Tomuto počítači dokonce
později věnoval jednu svoji práci slovy „na památku mnohých příjemných
odpolední“.
S pracemi na Umění programování začal již v roce 1962 (tedy 6 let po nástupu na
vysokou školu) a první tři svazky vyšly v letech 1968, 1969 a 1973. Poté byl
však zklamán změnou techniky sazby jeho knih, protože se změnilo písmo a
snížila kvalita. Rozhodl se proto vyvinout vlastní systém pro sazbu textů, a
tak vznikly jeho dva další známé počiny: TeX jako nový systém pro sázení textů
a METAFONT pro tvorbu fontů.
Dotáhl sazbu a propracovanost svých knih dokonce tak daleko, že se rozhodl
vyplatit 0x$1.00 (jeden hexadecimální dolar, tedy $2.56) každému, kdo najde
v nějaké jeho knize chybu. Na svých stránkách má seznam odměněných, který dnes
čítá bezmála 400 jmen.
23-4-4 Závorky v TeXu (10 bodů)
V TeXu se hojně využívají složené závorky
(např. v definicích či voláních maker) a lze je i libovolně vnořovat. Občas se
ale stane, že se člověk překlepne a místo { napíše } nebo naopak.
Vymyslete algoritmus, který na vstupu dostane posloupnost (řetězec) N
složených otevíracích a zavíracích závorek (bez dalších jiných znaků) a nalezne
minimální počet změn znaku { na znak } nebo naopak, aby byl řetězec
správně uzávorkovaný. Žádné jiné změny, kromě přepsání jednoho znaku na druhý,
nejsou povoleny.
Správně uzávorkovaný znamená, že ke každé otevírací závorce existuje
odpovídající uzavírací, která je od ní napravo, a podobně ke každé uzavírací
existuje odpovídající otevírací, jež je od ní nalevo.
Nepůjde-li posloupnost závorek žádným způsobem změnit na správně uzávorkovaný
řetězec, měl by to být váš algoritmus schopen rozpoznat.
Příklad: pro vstup {{}{}}}{{} je jedním z možných nejkratších
postupů ke správnému uzávorkování tento:
{{}{}}}{{}
↓
{{}{{}}{{}
↓
{{}{{}}}{}
Výsledek je tedy 2.
Řešení
Jak je uvedeno na začátku, Knuth píše dobře dokumentované programy. V 70.
letech, kdy vznikal TeX, si vymyslel dokonce vlastní styl programování,
v originále nazvaný literate programming (česky by se dalo přeložit jako
„kultivované programování“), který se snaží programování více přiblížit myšlení
člověka a ne potřebám strojů.
Ve zdrojovém kódu se míchá dokumentace a samotný kód (např. v Pascalu či C),
přičemž Knuth si naprogramoval utility na vyextrahování čistého zdrojového kódu
pro účely kompilace a programátorské dokumentace v TeXu.
O tom, že Knuth není žádný suchar a rád si hraje s čísly, vypovídá několik
věcí. Už jako středoškolský student odeslal do soutěže vědeckých talentů svůj
první matematický článek o číselných soustavách se záporným či dokonce
komplexním základem. Vymyslel soustavu o základu 2i, jejíž speciální
vlastností je, že každé komplexní číslo může být reprezentováno pouze číslicemi
0, 1, 2 a 3 a bez znaménka.
Zvláštní je také systém číslování verzí TeXu a METAFONTu. Jak se TeX stává
dokonalejším, jeho verze se stále více blíží číslu π. Prohlásil, že po jeho
smrti se číslo verze programu TeX s definitivní platností ustálí na π a
všechny zbývající bugy se stanou vlastnostmi programu. Podobně se verze
METAFONTu blíží základu přirozeného logaritmu, číslu e, a po jeho smrti bude
provedena podobná změna jako u TeXu.
23-4-5 Palindromnásobky (11 bodů)
Když už jsme u těch čísel, naprogramujeme si jednu zajímavou úlohu z této
oblasti. Víte, co je zajímavé na roce 1991? Když ho vydělíte 11, získáte 181,
přičemž všechna tato tři čísla jsou palindromy. (Palindrom je takový řetězec,
který se stejně čte zleva i zprava.)
Vaším úkolem bude napsat program, který na vstupu dostane čísla K a D a na
výstup vypíše počet násobků čísla K, jež mají délku D a jsou palindromy
(všechno v desítkovém zápise). 1 < K < 1 000 a D < 20.
Zdá-li se vám, že takových čísel musí být hrozně málo, tak vězte, že pro každé
K nedělitelné 10 existuje nekonečně mnoho jeho palindromických násobků. Číslo
dělitelné 10 takový násobek nemá, protože se nuly na začátku nepíší.
Formát vstupu a výstupu: v souboru vstup.in jsou na prvním řádku
dvě přirozená čísla K a D oddělená mezerou. Do souboru pocet.out
vypište na první řádku počet násobků K délky D, které jsou palindromy.
Příklady:
| vstup.in | pocet.out |
| 3 1 | 3 |
| 25 3 | 2 |
| 12 4 | 7 |
| 60 4 | 0 |
| 81 6 | 0 |
Tato úloha je praktická a řeší se ve vyhodnocovacím systému
CodEx.
Přesný formát vstupu a výstupu, povolené jazyky a další technické informace
jsou uvedeny v CodExu přímo u úlohy.
Řešení
Veškerý svůj čas však Don Knuth nevěnuje jen informatice. Se svou ženou Jill mají doma
například vlastní varhany s 812 píšťalami.
Další zajímavou zálibou je focení kosočtverečných dopravních značek, které se
vyskytují např. v USA, Kanadě a Austrálii. Na svých stránkách má slušnou sbírku
1069 fotek různých dopravních značek,
včetně kuriozit jako značky s nápisem „Anti-icing spray system“.
23-4-6 Knuthovy cesty po státech (9 bodů)
Knuth si během jedné cesty po státech, při níž fotil značky, při průjezdu
křižovatkou vždy zapsal její číslo. On si je totiž předem očísloval. Zajímalo
by ho, jakou největší souvislou část cesty (podle počtu křižovatek)
neprošel žádnou křižovatkou více než jednou.
Například pro posloupnost křižovatek
3, 4, 1, 2, 4, 8, 7, 2, 3, 8, 2, 9, 1, 4
je správným řešením posloupnost
3, 8, 2, 9, 1, 4.
Řešení
Jako třešničku na informatickém dortu si uvedeme citát z jednoho jeho dopisu:
„Beware of bugs in the above code; I have only proved it correct, not tried
it.“ („Pozor na chyby ve výše uvedeném kódu; pouze jsem dokázal jeho správnost,
ale nezkoušel jsem ho.“)
I přes stáří 73 let používá Knuth moderní prostředky.
Své internetové stránky
často aktualizuje a pracuje na dvou počítačích: má Mac na vytváření grafiky a
přístup k internetu a notebook s Linuxem na práci. Je tedy možné, že používá i
některé z utilit zmíněných v dalším díle seriálu (ačkoliv píše v editoru Emacs
a ne ve Vimu).
23-4-7 Bratrstvo Seda a Grepa (16 bodů)
Tento text volně navazuje na předchozí tři série, některé pasáže nemusí
být lehce pochopitelné bez jejich znalosti.
Ukážeme si, jak regulární výrazy používáme v praxi. Programy, které nás budou
zajímat, jsou UNIXové nástroje sed, grep a případně světoznámý
editor Vim. Jsou snad v každé distribuci Linuxu, na Windows je možné použít
balík Cygwin.
Na vyhledávání v textu se používá program grep. Není to žádná aplikace
s klikacím frontendem, používá se trapně v terminálu. O to je však rychlejší.
Základní použití je egrep <regex>, kdy program čte standardní vstup (to,
co mu píšete na klávesnici) a vypisuje na standardní výstup (terminál).
Vypisuje ty řádky, na kterých našel podřetězec vyhovující zadanému regexu.
Možná si říkáte – proč egrep? Pohled do manuálu (man grep)
napoví, že existovaly starší regexy, které toho uměly méně a mají trochu
jinou syntaxi. Kvůli zpětné kompatibilitě starých skriptů byla tedy přidána tato
varianta programu grep. Ze stejného důvodu budeme později u programu
sed používat přepínač -r.
Když si tedy pustíme egrep 'ba*gr+', tak na vstup
grbagr
baagrr
rgba
bbarg
rbgrbgg
dostaneme výstup
grbagr
baagrr
rbgrbgg
Můžeme chtít, aby grep četl vstup ze souboru. Za zadaný regex můžeme
napsat libovolně mnoho jmen souborů, které má číst (oddělené mezerami).
Pokud čte jeden, vypíše prostě vhodné řádky. Když jich je víc, vypíše na
začátku každého řádku ještě jméno souboru, ve kterém jej našel. Toto chování se dá
regulovat volbami -h (bez jmen) a -H (vypiš jméno, i když je soubor
sám), které můžete napsat před výraz.
Takže například
egrep -h Kája jmena prijmeni archiv
vyhledá
všechny řádky ze souborů
jmena, prijmeni a archiv,
které
obsahují výraz Kája. Volba -h potlačila výpis jmen souborů.
Ještě existuje zajímavá volba -v, která logicky obrátí výpis (vypisuje
jen ty řádky, které hledaný výraz neobsahují). Například když hledáte, jak
často k vám na web chodí lidé z jiných prohlížečů než IE a FF, tak ze záznamů
prostě vyřadíte řádky odpovídající IE a FF…
Programy za sebe můžete řetězit znakem | – vezme standardní výstup
prvního programu a nevypisuje ho na terminál, ale předhodí ho druhému programu
na standardním vstupu. Například egrep ba+gr|egrep -v baaagr. Někdy je
jednodušší programy zřetězit než psát jeden dlouhý výraz, který pojme všechno.
Tento znak se také označuje jako „roura“ (pipe), protože to dávným
programátorům připadalo, jako by mezi programy prostě natahovali potrubí.
Složitější výrazy se hodí psát mezi apostrofy: '(\(|\))', jinak je může
interpretovat ještě terminál samotný a z a* udělat seznam souborů,
které začínají a, což rozhodně nechcete, a to je to nejmenší, můžou se
stát daleko horší věci…
Dosud jsme regulárními výrazy pouze vyhledávali. Jde však o daleko mocnější
zbraň, výrazně větší kladivo. Jak bylo zmíněno už v prvním dílu, regexy často
používáme k systematickému nahrazování v textu.
Na nahrazování se hodí program sed. Jeho základní použití je podobné
jako u programu grep.
Jak ale vypadá nahrazovací výraz? Začíná písmenkem s, pak následuje
oddělovač (typicky / nebo #, ale může to být libovolný znak,
klidně písmenko), pak hledaný řetězec, potom znovu stejný oddělovač, potom
řetězec k nahrazení, a nakonec zase oddělovač. Například nahrazovací výraz
s/ahoj/nazdar/ nahrazuje slovo ahoj za nazdar.
Oddělovač se potom stává speciálním znakem a pokud jej chcete použít v původním
významu, je potřeba to říct – obackslashovat jej. (\/, \#)
Jak to funguje jako příkaz? Když pustíte příkaz
sed -r 's/ahoj/nazdar/',
čte standardní vstup po řádkách, na každém řádku hledá výraz ahoj, jeho
první nalezený výskyt změní na nazdar a změněný řádek vypíše na výstup.
Takže pokud vstup
moskyto@atrey.karlin.mff.cuni.cz
bagr
ksp@mff.cuni.cz bait@uu.ucw.cz
kombajn
proženeme třeba příkazem sed -r 's/@/ (at) /', dostaneme výstup
moskyto (at) atrey.karlin.mff.cuni.cz
bagr
ksp (at) mff.cuni.cz bait@uu.ucw.cz
kombajn
Všimněte si na třetím řádku zbylého zavináče. Kdybyste potřebovali nahrazovat
všechny výskyty, ne jen ten první, tak musíte za výraz ještě připsat g
(od „globally“):
sed -r 's/@/ (at) /g'
Pokud potřebujete „přišpendlit“ celý výraz na začátek nebo na konec
řetězce, uveďte stříšku ^ na jeho úplném začátku nebo dolar $ na jeho konci. To funguje jak pro sed, tak pro grep.
Úkol 1 [1b]
Napište nahrazovací výraz, který smaže všechny „trailing spaces“ –
bílé znaky na koncích řádků (stačí asi mezera, \t a \r).
Jenom takhle by to ale bylo trapné. Co když potřebujeme z řádku jenom něco
vytáhnout? Pak opravdu můžeme „najít“ třeba celý řádek jedním výrazem a
vybrat si z něj jenom tu část, kterou potřebujeme.
sed -r 's/^.*"(.*)".*$/\1/' z celého řádku nechá jen řetězec v uvozovkách.
Takže vstup vlevo se přepíše na výstup vpravo.
"
bagr
b"ag"r
b"a"g"r
"
bagr
ag
g
Když tedy kus řetězce uzávorkujete, můžete se na tyto závorky pak odkazovat
pomocí znaku zpětné lomítko (\) následovaného číslicí (1 – 9). Závorky jsou číslovány zleva
doprava podle své otevírací závorky. Takže třeba sed -r 's/(.)(.)/\2\1/'
na každém řádku prohodí první dva znaky.
Pamatujte si, že pokud sed na řádku nenajde žádný výskyt hledaného
výrazu, vypíše řádek beze změny.
Také je potřeba si uvědomit „žravost“ některých operací. Znaky * i
+ jsou „nenažrané“. To znamená, že pokud by si sed měl vybrat
mezi více podřetězci, které by přiřadil do oné hvězdičky, tak vybere ten
nejdelší z nich. Přednost ve žravosti má dřívější */+. Toho si
můžete všimnout na čtvrtém řádku, kde byly troje uvozovky, že ty první byly
polknuty do .* na začátku.
Podobně je žravý i výběr z více možností – bere první variantu, která se na
dané místo hodí, takže (.|..) vždy uloží do \1 jeden znak
(a druhá půlka závorky je tedy zbytečná), kdežto (..|.) uloží do
\1 dva znaky, pokud to jenom trochu jde.
Pravidlo číslování u otevírací závorky se hodí u vnořených závorek:
sed -r 's/^(ab*cd(ef|gh)i+j)$/\1: \2/'
připíše za každý řádek, pokud je v onom poměrně složitém tvaru, dvojtečku a
ef nebo gh…
Úkol 2 [4b]
V češtině je typografickou chybou napsat na konec řádku jednopísmennou
předložku nebo spojku, výjimkou je spojka a, pokud se před ní
nevyskytuje nějaké interpunkční znaménko (tečka, čárka, závorka, …).
Různé programy to řeší různě, v TeXu se za předložku místo mezery
vkládá vlnka (~). Napište výraz pro sed, který zařídí
korektní „ovlnkování textu“ (případ, kdy je předložka/spojka přímo na
začátku nebo na konci řádku, řešit nemusíte).
Tyhle „odkazy zpátky“ (backreferences) můžeme ale používat i ve
vyhledávaném výrazu. s/^(.*)\1$/\1/ tedy najde všechny řádky, na kterých je řetězec dvakrát za sebou, a nahradí
tyto výskyty jen jedním opakováním řetězce. Na vstup
aa
ab
abeceda
bagrbagr
odpoví
a
ab
abeceda
bagr
Mimochodem, například také slova sentence, sequence nebo
statement jsou nahrazovacími výrazy…
Úkol 3 [4b]
Napište vyhledávací výraz, který ze slovníku „vygrepuje“ všechna
slova, která jsou validními nahrazovacími výrazy pro sed. I grep
umí backreference (stejně jako sed). Bonusové 4 body dostane ten, kdo
vyrobí takový výraz bez backreferencí (Chuck Norris je má jisté).
Výraz musí být samozřejmě nezávislý na použité abecedě, takže není správným
řešením vygenerovat pro každý možný oddělovač separátní výraz…
Ve slovníku je na každém řádku právě jedno slovo (a vlevo a vpravo od něj
nejsou žádné mezery).
Místo jednoho výrazu můžete použít až tři volání příkazu grep spojená za
sebou rourou.
Nyní si zavedeme fiktivní programovací jazyk, budeme mu říkat třeba
„ReProg“. Programem v ReProgu bude posloupnost nahrazovacích výrazů pro
sed.
Nad vstupními daty se postupně spustí každý z výrazů. Když program doběhne na
konec, zjistí ReProg, jestli nějaký z výrazů měnil data. Pokud ano, spustí se
celý program od začátku znovu; pokud ne, data se prohlásí za výstup a program
skončí.
Takový vzorový program je třeba
statement
sentence
samaria
Když mu předhodíme sebe sama jako vstup, pak po prvním průběhu budeme mít
steriencement
sencence
serienmaria
Po druhém průchodu máme
steriencerienc
sencence
serienriemenria
a tak dále, až pátý průchod data nezmění a výstupem je
steriencerienc
sencence
serienrierienrierien
Úkol 4 [7b]
Napište program pro ReProg, který na vstupu na každém řádku dostane
dvě přirozená čísla ve dvojkovém zápisu oddělená mezerou a na výstupu bude na
každém řádku to větší z nich. Například pro jednořádkový vstup 1011 110
bude výstup 1011.
Za zmínku ještě stojí, že i sed podobné iterování umí, byť na jiném
principu a s trochu jinou syntaxí. To už je ale trochu jiný příběh, třeba na
nějakou soustředkovou přednášku.
A kdybyste se báli, že se na soustředko nedostanete, přečtěte si třeba
manuálovou stránku (man sed), nebo dosti obsáhlou
dokumentaci na internetu.
To je pro tentokrát vše, v závěrečném dílu si ukážeme temnou a mocnou sílu
jedné zajímavé mutace regexů – těch v Perlu. Prý se v nich dá napsat výraz,
který nahradí dvojici čísel na vstupu za jejich podíl…
Řešení