Čtvrtá série dvacátého třetího ročníku KSP

Termín odeslání Vašich řešení této série jest určen na 28. března 2011 8:00. Řešení můžete odevzdávat jak elektronicky, tak klasickou poštou na známou adresu.

Dotazy ohledně zadání můžete posílat na adresu ksp@mff.cuni.cz, nebo se ptát přímo na diskusním fóru KSP.

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ů)


Jednoduchá úlohaDva 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ů)


Praktická CodExová úlohaKdyž 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.inpocet.out
3 13
25 32
12 47
60 40
81 60

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ů)


SeriálTento 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í (19). 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í