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

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

• Termín série: 30. března 2015 8:00
• Termín CodExové úlohy: 31. března 2015 8:00
• Odevzdávání: elektronicky přes Odevzdávátko
• Jak sepsat řešení: viz Návod na teoretické úlohy
• Dotazy ohledně zadání: posílejte na ksp@mff.cuni.cz, nebo se ptejte na Discordu KSP.

• Odměna série: Řešitelům, kteří vyřeší tři úlohy této série alespoň na jedenáct bodů, pošleme čokoládu.

Zadání ú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ů (10 bodů)

Ve FirstEnergy je přesně určena organizační struktura. Každý zaměstnanec v pozici vedoucího má právě dva podřízené (kteří mohou, ale nemusí být vedoucími), ostatní zaměstnanci na nikoho nedohlížejí. Jeden zaměstnanec může mít více nadřízených, v celém schématu však existuje právě jeden ředitel. Ředitel je vedoucí, který nemá žádné nadřízené a všichni ostatní zaměstnanci mu jsou (alespoň nepřímo) podřízeni. Hierarchii bychom tedy mohli označit jako souvislý acyklický hranově orientovaný graf (DAG).

Pouze ředitel může zadávat úkoly, každý úkol předá jednomu ze svých podřízených. Ten, pokud není vedoucím, musí úkol provést, jinak jej opět předá jednomu ze svých podřízených, a tak dále. Aby byly úkoly rozdělovány rovnoměrně, každý vedoucí (ředitele nevyjímaje) je musí předávat střídavě jednomu a pak druhému podřízenému.

O každém vedoucím víte, kterému ze svých dvou podřízených předá první úkol, který k němu dorazí. Ředitel zadá celkový počet N úkolů, které jsou postupně předávány celou hierarchií. Váš úkol se týká momentu, kdy jsou všechny tyto úkoly vykonány. Určete pro každého vedoucího, kterému ze svých podřízených by předal další úkol, který by k němu dorazil. Pokuste se, aby vaše řešení bylo efektivní i pro velké hodnoty N (velkou hodnotou myslíme například bilión).

Na obrázcích vidíte příklad takové hierarchie. Šipky vyznačují, komu bude nový úkol předán. Na prvním obrázku je znázorněna výchozí situace, na tom druhém stav po 99 zadaných úkolech:

Lehčí varianta (za 5 bodů): Navrhněte řešení pro případ, kdy má každý zaměstnanec jen jednoho nadřízeného (grafem hierarchie je tedy strom).

Řešení

27-4-2 Čtverce v síti (11 bodů)

Projektanti rozvodné soustavy se rozhodují mezi několika návrhy rozmístění vedení. Aby určili míru spolehlivosti návrhu, potřebují zjistit, kolik se v něm dá najít různých čtverců, které jsou složené z vodičů.

Navrhněte algoritmus, jenž na vstupu obdrží přímky představující vedení, zadané v některém z běžných tvarů (např. obecnou rovnicí, případně pomocí dvou bodů), a určí, kolik navzájem různých čtverců tyto přímky tvoří.

Počítáme i vzájemně se překrývající čtverce, tudíž přímky na obrázku tvoří celkem osm čtverců.

Řešení

27-4-3 Vysoké napětí (11 bodů)

Pracovníci dispečinku potřebují zjistit, jaké napětí se vyskytuje na různých bodech sítě. Sice ví, že v uzlových bodech soustavy se vyskytují jen tři různé hladiny napětí – 0, 100 a 200 kilovoltů, ale informace mají pouze ze senzorů na vodičích, které tyto body spojují a které měří rozdíl napětí mezi koncovými body (nevíme však, kde je napětí větší, jinými slovy, ze senzorů vyčteme pouze absolutní hodnotu rozdílu).

K dispozici jsme dostali mapu sítě (tvořenou uzlovými body a vodiči – jinde než v bodech se vodiče nekříží) a pro každý vodič hodnotu rozdílu napětí mezi uzly, které spojuje (buď 0, 100, nebo 200 kV). Máme za úkol určit hodnoty napětí na koncových bodech, aby rozdíly na vodičích odpovídaly (pokud je více možných řešení, stačí nalézt jedno z nich), nebo zjistit, že došlo k chybě a žádné takové řešení neexistuje.

Příklad: Vrcholům grafu na obrázku (hodnoty jsou ve stovkách kilovoltů) napětí přiřadit lze. Jedno možné přiřazení napětí vrcholům je zakreslené přímo do obrázku.

Lehčí varianta (za 7 bodů): Vyřešte úlohu pro dvě napěťové hladiny v bodech, 0 a 100 kV.

Řešení

27-4-4 NP-úplný hlavolam (11 bodů)

Hlavolam, se kterým si budeme hrát v této úloze, sestává z R ×S políček uspořádaných do mřížky s R řádky a S sloupci. Některá z políček jsou průhledná, ostatní jsou neprůhledná.

Pod sloupce mřížky můžeme zasouvat barevné proužky. Zasuneme-li proužek pod zvolený sloupec, pak všechna průhledná políčka tohoto sloupce uvidíme nyní jako barevná. U každého řádku je číslo – nula nebo jednička, které udává, kolik barevných políček má být v tomto řádku vidět.

Na následujícím obrázku vidíte dva hlavolamy. Průhledná políčka jsou znázorněna bíle, neprůhledná políčka šedivě. Řešením prvního hlavolamu je zasunutí proužků do druhého, třetího a pátého sloupce. Druhý hlavolam řešení nemá.

Po vás však nechceme návod na řešení hlavolamu. Raději dokažte, že úloha rozhodování toho, zda má zadaný hlavolam řešení, je NP-úplná. Pokud se vám to nebude dařit, dokažte alespoň NP-úplnost této úlohy pro obecnější hlavolamy, kdy u každého řádku může být požadován libovolný počet barevných políček, nikoliv pouze nula nebo jedna.

Řešení

27-4-5 Večeře pro opraváře (12 bodů)

Elektrotechnik Larry strávil celé odpoledne zjišťováním poruch vedení ve městě, a jelikož mu je jasné, že se práce dnes protáhnou do pozdních nočních hodin, chce se na takový úkol pořádně navečeřet. Do zjednodušené mapy Manhattanu (čtvercová síť s vyznačenými budovami, policisty na křižovatkách a ostatními věcmi, které nelze procházet; všechna ostatní pole ano) si proto zakreslil hospody, restaurace, ba i zmrzlinářství, kde se chce najíst. Je mu ale jasné, že času není nazbyt a že zásoby jídla nejsou bezedné.

Proto by potřeboval najít nejkratší trasu chůze po Manhattanu, během níž všechny zakreslené podniky navštíví. Můžete předpokládat, že podniků nebude více než dvacet. A pospěšte si, zmrzlina už teče!

Toto je praktická open-data úloha. V odevzdávátku si necháte vygenerovat vstupy a odevzdáte příslušné výstupy. Záleží jen na vás, jak výstupy vyrobíte.

Formát vstupu: Na prvním řádku naleznete mezerou oddělená čísla R a S udávající počet řádků a sloupců mapy. Na každém z následujících R řádků vstupu se nalézá S znaků popisujících jeden řádek mapy. Startovní políčko je označeno písmenem S, podniky jsou značeny písmenem o, volná pole značíme jako . a neprůchodná pole jako #.

Omezení vstupu: Ve všech vstupech platí R ≤ 50 a S ≤ 50. Políček označených symbolem o je nejvýše dvacet.

Formát výstupu: Na jediný řádek výstupu vypište jediné číslo – délku nejkratší trasy začínající v políčku označeném písmenem S, která navštíví každé políčko označené znakem o alespoň jednou. Přesouvat se lze pouze na políčka sousedící celou stranou, na políčka označená symbolem # vstupovat nelze. Trasa může končit kdekoliv. Pokud žádná taková trasa neexistuje, vypište jediné slovo neexistuje.

5 6
S...#o
..o##.
o..o..
#####.
o.....

20

5 6
S...#o
..o##.
o..o..
######
o.....

neexistuje

Řešení

27-4-6 Stěhování pásek (11 bodů)

Pásky s důležitými daty jsou namotány na ploché kotouče, které však mají různý průměr. Ve FirstEnergy se k ukládání záznamů používá poměrně malá místnost, kde jsou kotouče položeny na sebe a seřazeny takovým způsobem, že ten největší je vespod a ten nejmenší navrchu.

Problém takovéhoto věžovitého uspořádání spočívá v obtížném stěhování. Před několika týdny museli pracovníci všechny kotouče přesunout, aby se do skladu vešla i část firemního archivu. Aby se pásky nepoškodily, museli postupovat podle striktních pravidel: v jedné chvíli mohli přesouvat pouze jeden kotouč (pokud je víc kotoučů na sobě, mohou přesunout pouze ten, který je navrchu), a aby se věž složená z kotoučů nezhroutila, nesměli položit kotouč s větším průměrem na kotouč s průměrem menším.

Protože je sklad skutečně stísněný, kromě místa označeného A, kde se kotouče vyskytovaly nejdříve, a místa B, kam byly přesunuty, mohli pracovníci kotouče odkládat pouze na jedno další místo C – všude je však museli skládat na sebe za dodržení uvedených pravidel.

Vyšetřovatel získal fotografie vzniklé při tomto stěhování a chce se ujistit, že během něj nedošlo k manipulaci s daty. Na vstupu dostanete každou fotografii popsanou jako řetězec znaků A, B a C, kde k-tý znak určuje polohu k-tého nejmenšího disku na fotce (protože jsou na každém místě disky seřazeny od největšího po nejmenší, je tím jejich poloha určena jednoznačně). Na obrázku vidíte rozmístění kotoučů odpovídající řetězci BACB a také rozmístění odpovídající řetězci AACB, které vzniklo z prvního rozmístění přesunutím nejmenšího kotouče na místo A.

Víme, že pracovníci přemístili všechny kotouče z místa A na místo B způsobem, při kterém byl počet přesunů kotoučů mezi místy nejmenší možný. Seřaďte zadané fotografie podle času jejich pořízení.

CCA
CCB
BCA
AAA

AAA
BCA
CCA
CCB

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í

27-4-7 Nástroj pro zpracování textu (14 bodů)

Již v prvním dílu jsme si řekli, že Unix byl zpočátku z politických důvodů oficiálně vyvíjen jako „nástroj pro zpracování textu“. Je pomalu načase představit si jeho schopnosti v této oblasti. Ale nejprve motivační příklad.

Příklad: Počasí

Svého času bývalo populární nechat si zobrazovat na ploše různé aktuální informace: například o počasí. Samozřejmě existovala spousta programů (zvláště na Windows), která dělala právě tohle: zobrazila na ploše informace o počasí. To je sice užitečné, ale jen omezeně. Co když si vedle toho chcete zobrazit aktuální zprávy, čas do odjezdu nejbližšího autobusu, aktuálně přehrávanou písničku, čas východu a západu slunce, kurz dánské koruny nebo cokoli jiného? A co když tyhle všechny věci chcete naopak zobrazit někde jinde, řekněme třeba na nástěnných hodinách?

Určitě chápete, že na každou z takovýchto věcí vám samostatný program nikdo nenapíše. Unixový svět se k tomu postavil trochu jinak. V něm najdeme programy, které umí zobrazit na ploše cokoliv (Třeba prográmek jménem conky. Ten sice počasí už umí zobrazovat sám, ale i tak je zajímavé cvičení ho to naučit po svém.), a jak asi tušíte, tím cokoliv je v tomto případě výstup nějakého jiného programu či skriptu. To nám nabízí poměrně bohaté možnosti, neb na rozdíl od programu kreslícího na plochu, je snadné vytvořit shellový skript, který něco vypíše.

Zkusme si právě to: napsat skript, který na svůj výstup vypíše aktuální teplotu v nějakém městě. Pokud bydlíte v Praze, dobrým zdrojem informací o počasí je meteostanice Planetária ve Stromovce. Relevantní kousek HTML kódu této stránky vypadá následovně:

<TD VALIGN="top" WIDTH="200"> <FONT [...]>aktuální teplota vzduchu</FONT> </TD> <TD VALIGN="top" WIDTH="150"> <FONT [...]>-2.3°C</FONT> </TD>

Pokud jste nikdy o HTML neslyšeli, zkonzultujte např. Wikipedii. Pro účely seriálu bude stačit vědět, že každá webová stránka je ve skutečnosti textový soubor, který popisuje, co se má uživateli zobrazit, a právě tento textový soubor vám curl zmíněný níže vypíše.

Podtržený je údaj o teplotě, který bychom rádi získali, [...] jsou vynechané nezajímavé části. Jen vás upozorníme na obtíž se zpracováním speciálních znaků (závislých například na kódování, jako jsou diakritická písmenka, nebo třeba znak stupňů). Až s nimi budeme pracovat dále v různých příkazech, budou typicky nahrazeny otazníky.

Potřebovali bychom stránku stáhnout, vybrat z ní správný řádek a z něj oddělit číselnou hodnotu teploty. A nepříliš překvapivě na každou z činností poslouží jiný nástroj.

Všechny ty internety…

Již známe spoustu zajímavých unixových nástrojů pro zpracování informací (a na konci tohoto dílu budeme znát ještě víc), ale zatím jediné, s čím umí pracovat, jsou soubory na našem disku. Kdybychom jim tak dokázali „podstrčit“ data získaná z Internetu, otevře se nám nepřeberné množství nových možností, stále s těmi stejnými nástroji.

To můžeme zařídit prográmkem curl, který na spoustě unixových systémů najdeme ve výchozí instalaci, případně si jej lze snadno doinstalovat (i v Cygwinu). Jeho použití je přímočaré: jako parametr dostane URL webové stránky (či stáhnutelného souboru) a na standardní výstup vypíše její obsah (HTML kód). Odtud jej můžeme přesměrovat do souboru či poslat kamkoli rourou, jak jsme zvyklí.

Zkuste si spustit například

curl http://ksp.mff.cuni.cz/ | wc -c

Ve skutečnosti má každý proces kromě svého standardního vstupu (též stdin) a výstupu (stdout) ještě třetí „datový kanál“, takzvaný standardní chybový výstup (stderr). Ten směřuje na terminál, i když je výstup příkazu přesměrován do souboru či roury. Jak již název napovídá, slouží k tomu, že když za běhu příkazu nastane chyba, uvidí ji uživatel namísto toho, aby se zapsala doprostřed výstupního souboru. Ale nepoužívá se jen pro chyby a varování, nýbrž i pro informace o stavu a průběhu programu. A právě curl na něj vypisuje informace o průběhu stahování, díky čemuž když stahujete velký soubor příkazem curl http://adresa >soubor, vidíte, kolik již je staženo a kolik času ještě zbývá.

Naše pipeline (tímto pojmem se označuje řada příkazů pospojovaných rourami) ve skutečnosti z pohledu operačního systému vypadá takto:

Teď už je jasné, kudy se ona hlášení na terminál dostanou. I stderr se dá přesměrovat, a to operátorem 2>. Nejčastěji se to používá k umlčení všech hlášení, například takto: curl http://... 2>/dev/null | wc -c. O speciálním souboru /dev/null byla řeč v minulém díle. Je třeba dávat pozor, ke kterému příkazu přesměrování patří. Pokud byste ho napsali na konec, kýženého efektu nedosáhnete, neb přesměrujete stderr procesu wc, nikoli curl. V případě curl-u ale přesměrování používat nemusíte, neboť nabízí přepínač -s, který stavové zprávy utiší.

Na závěr dodáme, že ke stejnému účelu jako curl lze použít i příkaz wget, který ovšem ve výchozím nastavení ukládá staženou stránku do souboru. K vypisování na stdout ho přimějete parametrem -O -, hlášení o průběhu umlčíte -q. Více v manuálové stránce.

Filtrování řádek: grep

Občas by se nám hodilo z textového souboru vybrat řádky splňující nějaké kritérium. Nejjednodušším nástrojem, který takovou věc dělá, je grep. Ten jako parametr přijímá slovo (kus textu), čte postupně řádky ze svého vstupu a na výstup vypisuje jen ty, které zadané slovo obsahují (myšleno obsahují jako podřetězec, nemusí být oddělené mezerami). S parametrem -v (inVert) naopak vypisuje jen řádky neobsahující dané slovo. Pokud hledané slovo obsahuje nějaké „divné“ znaky, je třeba grep-u dát ještě parametr -F. Které přesně znaky jsou divné a proč, si vysvětlíme později, prozatím můžete za bezpečná považovat písmena a číslice. S parametrem -i ignoruje grep při hledání slova velikost písmen (v závislosti na nastavení systému nemusí fungovat pro české znaky).

Pokud dáte grep-u víc parametrů, další jsou brány jako názvy souborů, ve kterých se má hledat. Tedy grep slovo soubor1 soubor2 se chová podobně jako cat soubor1 soubor2 | grep slovo, s tím rozdílem, že pokud je soubor víc než jeden, grep před každý vyhovující řádek napíše název souboru, ze kterého pochází (to se dá vypnout přepínačem -h). Například kdybych chtěl zjistit, zda jsme v některém díle seriálu zmiňovali proměnnou $RANDOM, použiji:

$ grep -F '$RANDOM' serial*
serial3.tex:X=$(($RANDOM % 100))
[...]

a vidím, že to bylo ve třetí sérii. Pokud nás zajímají jen názvy souborů, ve kterých se slovo vyskytuje, můžeme použít přepínač -l (dobře se pamatuje podle ls, které taky vypisuje názvy souborů), případně -L pro opačnou operaci (výpis souborů neobsahujících ani jednou dané slovo). S přepínačem -r můžeme grep-u předávat za parametry i názvy adresářů; v těch pak prohledá všechny soubory rekurzivně. grep -lr bagr ~ najde v domovském adresáři všechny soubory obsahující slovo bagr. Takovéto hledání může chvíli trvat.

Přepínačem -C K (Context) řeknete grep-u, že má kromě vyhovujících řádek vypsat i K řádek okolo každé z nich. Pokud místo -C použijete -B (Before) či -A (After), bude vypsán jen kontext jednostranný (K řádek před, resp. za každým vyhovujícím). Pokud by se kontexty překrývaly, jsou slity do jednoho bloku, žádný vstupní řádek se na výstupu neobjeví dvakrát. Tedy např. grep -C 999 : na /etc/passwd vypíše to samé, co cat. Pokud na sebe sousední kontexty nenavazují, jsou odděleny řádkem s dvěma pomlčkami pro snazší vizuální orientaci.

Pokud používáte grep ručně, mohl by vás zajímat přepínač --color, který výskyty hledaného slova barevně zvýrazní. Ve skriptech by se vám naopak mohl hodit přepínač -q, který způsobí, že se na výstup nevypíše nic (jako >/dev/null). K čemu je taková věc dobrá? Zatím jsme vám zatajili, že grep vrací nulovou návratovou hodnotu, pokud našel alespoň jeden vyhovující řádek, jinak nenulovou. Takže můžete použít if grep -q slovo soubor pro test, zda je v souboru obsaženo slovo.

Teď už máme asi vše potřebné k výběru správného řádku:

$ curl -s ... | grep -a -A 3 "teplota vzduchu" \
              | head -n 4 | tail -n 1
<FONT COLOR="#FFFF00" FACE="Arial">0.4?C</FONT>

Od začátku psaní se trochu oteplilo. ;-)

První head je potřeba, protože se text na stránce vyskytuje vícekrát (a kvůli podivně kódovaným českým znakům nemůžeme hledat slovo „aktuální“). Přepínač -a slouží k tomu, aby grep vypsal obvyklý výstup, i pokud považuje soubor za binární (obsahuje nějaké neobvyklé znaky).

Ještě snad dodejme, že zpětné lomítko na konci prvního řádku znamená, že příkaz pokračuje na řádku následujícím. Do skriptu to můžete napsat přesně takto, jen je třeba dát si pozor, aby za lomítkem nebyla žádná mezera. Pokud byste chtěli příkaz spustit v terminálu, je lepší napsat vše na jeden řádek (a lomítko vynechat).

Sekání a slepování řádek: cut, paste a spol.

Už umíme vybírat ze souboru celé řádky. Občas by se nám mohlo hodit získat i jejich části. K tomu nám poslouží příkaz cut. Ten se nejčastěji používá se soubory „tabulkového“ charakteru (např. /etc/passwd), kde každý řádek je rozdělen na několik „sloupečků“ nějakým oddělovačem (v Unixu typicky dvojtečka či libovolná posloupnost bílých znaků – s tou si ale cut neporadí). Důležité přepínače jsou -d, který nastavuje oddělovač (musí být jednoznakový) a -f, jenž říká, které sloupečky chceme na výstupu. Jeho parametrem může být jedno číslo, rozsah čísel (3-5), případně seznam čísel a rozsahů oddělených čárkami (1,3,5-10). Sloupečky jsou číslovány od jedničky.

Kombinací příkazů cut a grep můžeme nyní třeba zjistit ID uživatele hroch:

$ grep hroch /etc/passwd | cut -d: -f3
4242

cut má ještě alternativní režim, kdy místo sloupečků vysekává z řádků jednotlivé znaky, např. cut -c 1-3 vybere z každého řádku první tři znaky.

Inverzní operací ke cut je paste, který dostane za parametry několik souborů, které považuje za jednotlivé sloupečky. Pak vezme první řádek z každého souboru a všechny spojí zadaným oddělovačem (-d), čímž vznikne první řádek výstupu. A tak dále pro další řádky. S ním bychom mohli, byť trochu neobratně, zařídit například zmiňované prohození sloupečků:

$ cut -d: -f1 /etc/passwd >jmena
$ cut -d: -f3 /etc/passwd >uid
$ paste -d: uid jmena
0:root
4242:hroch
[...]

Formát „sloupečků“ oddělených dvojtečkami je sice příjemný pro strojové zpracování, ale člověku se čte o dost hůře než opravdové sloupečky, kde jsou odpovídající si hodnoty zarovnané pod sebou. Takovýto oku přívětivý formát lze vyrobit programem column.

Ten pracuje ve dvou režimech. Prvním z nich je tabulkový (column -t -s oddělovač), ten načte ze vstupu soubor v „oddělovačovém“ formátu a na výstup ho vypíše jako hezkou tabulku:

cut -d: -f 1-4 /etc/passwd | column -s: -t
root   x  0     0
hroch  x  4242  4242
[...]

Sloupcový režim očekává na vstupu jednoduchý seznam položek, které vypíše na výstup ve vícesloupcové sazbě, podobně, jako to dělá ls. Tím se dá šetřit místo na obrazovce, pokud jednotlivé vstupní řádky jsou krátké. Například kdybychom chtěli vypsat seznam všech uživatelských jmen v systému:

$ cut -d: -f1 /etc/passwd | column
root     hrosik   hacker
hroch    guest    nobody

Počet sloupců je zvolen automaticky, dá se ovlivnit přepínači, stejně jako se dá zařídit, aby se hodnoty vyplňovaly po řádkách namísto po sloupcích (používejte jen pokud víte, co děláte, čte se to hrozně).

Nahrazování znaků: tr

V nejjednodušším použití tr nahradí všechny výskyty jednoho znaku (určeného prvním parametrem) na svém vstupu za jiný (druhý parametr) a výsledek vypíše na výstup. Každý z parametrů může být i celým seznamem znaků, zadaným buď vyjmenováním těsně za sebou, rozsahem (např. a-z) nebo kombinací obojího. Pak platí, že každý výskyt nějakého znaku z prvního seznamu se nahradí za odpovídající znak z druhého seznamu.

Například tr a-z A-Z převede svůj vstup na velká písmena (funguje jen pro znaky anglické abecedy, ostatní nechá beze změny), tr a-zA-Z A-Za-z prohodí velikost písmen (z velkých udělá malá a z malých velká). Pokud některý ze seznamů je kratší, je doplněn zopakováním posledního znaku. Např. tr aeiouy e nahradí všechny (malé) samohlásky v textu za e.

S přepínačem -d očekává tr jen jeden seznam znaků a všechny znaky na tomto seznamu ze vstupu smaže. Přepínač -c vezme místo prvního seznamu znaků jeho doplněk. Nejčastěji se používá spolu s -d pro smazání všech znaků kromě zvolených nebo s jednoznakovým pravým seznamem. tr -c a-zA-Z _ nahradí všechny znaky kromě písmen za podtržítka.

Řešení: Počasí

Nyní už máme všechny střípky k vyřešení našeho úvodního příkladu:

$ curl -s \
  http://www.planetarium.cz/meteo/PL_meteo.htm \
        | grep -a -A 3 "teplota vzduchu" \
        | head -n 4 | tail -n 1 \
        | cut -d'>' -f2 |cut -d'<' -f1 \
        | tr -cd '0-9.-'
-0.7

Takovéto číslo si pak můžeme nejen nechat někde zobrazit, ale také s ním libovolně dál pracovat. Například by nebylo těžké napsat skript, který se před vypnutím počítače podívá na aktuální teplotu, a pokud je méně než 15, zobrazí upozornění „Vezmi si bundu!“

Rest: seq

Při povídání o for-cyklech jsme vám zatajili velmi užitečný příkaz seq. seq A B na svůj výstup vypíše všechna čísla od A po B (obojí včetně, A lze vynechat, pak se vypisuje od jedničky), každé na samostatný řádek. Spolu s for-em se dá použít pro zopakování nějakých příkazů n-krát.

Přeuspořádání řádků: sort, shuf, tac

Představíme si skupinu programů, která nějakým způsobem mění pořadí řádků na svém vstupu. Nejdůležitějším z nich je sort, který setřídí vstup či soubor dle zadaných kritérií. Ve výchozím nastavení třídí řádky abecedně vzestupně. Můžeme použít přepínače -r pro sestupné třídění, -f pro ignorování velikosti písmen, -n pro číselné porovnávání (abecedně by se zatřídila „100“ před „11“) a -k pro třídění podle některého sloupečku (ve stejném významu jako u cut-u, oddělovač se nastavuje -t, výchozím oddělovačem je whitespace, tedy libovolná posloupnost bílých znaků). Například sort -t: -k3 -n /etc/passwd setřídí záznamy v /etc/passwd podle ID uživatele.

S parametrem -R sort místo třídění vstupní řádky náhodně zamíchá. To samé dělá shuf, jen nabízí nějaké parametry navíc, například vybrat ze vstupu náhodně jen K řádek (-n K) nebo povolit vybrat jeden řádek vícekrát (-r).

Například pokud byste byli učitel a měli v nějakém souboru uloženou hromadu otázek, ze kterých chcete vygenerovat 30 náhodných písemek po 10 otázkách, můžete napsat:

for i in `seq 30`; do
    shuf -n 10 otazky.txt >pisemka-$i.txt
done

tac vypíše řádky vstupního souboru v opačném pořadí (od posledního po první) a uvádíme jej zde hlavně, abyste se taky mohli těšit z kreativity, kterou do názvů příkazů raní unixoví programátoři vložili ;-) Tak trochu duálním příkazem k tac je rev, který pořadí řádků nemění, ale zato každý z nich napíše pozpátku. Takže pokud byste chtěli obrátit celý soubor (od posledního znaku po první), tac | rev zařídí přesně to.

Třídit soubory nemusíme jen z vlastního zájmu, ale také proto, že některé příkazy svůj vstup setříděný vyžadují. Jedním z nich je uniq, který ze vstupu vyhodí duplicitní řádky, ale pouze, pokud leží všechny duplikáty vedle sebe (což zařídíte právě setříděním). uniq má spoustu zajímavých přepínačů, jako např. -c, který před každý výstupní řádek napíše, kolikrát se vyskytl na vstupu. Třeba pokud máme dlouhý seznam jmen uživatelů a chtěli bychom vědět, která křestní jména se u nich vyskytují nejčastěji, můžeme použít:

$ sort jmena.txt | cut -d' ' -f 1 \
  | uniq -c | sort -nr | head -n 3
     64 Jan
     51 Martin
     42 Kateřina

Porovnávání souborů: comm, cmp, diff

Dalším příkazem, kterému se hodí setříděný vstup, je comm. Slouží pro porovnání dvou množin reprezentovaných řádky setříděných souborů. Ve výchozím nastavení vypíše výstup do tří sloupečků: v prvním jsou řádky obsažené pouze v prvním souboru, v druhém řádky unikátní pro druhý soubor a ve třetím řádky oběma souborům společné. To je hezké pro vizuální porovnání, ale ve skriptech víceméně nepoužitelné. Vhodným nastavením parametrů můžeme zajistit vypsání jen jednoho z těchto sloupečků, ale syntaxe není příliš intuitivní: parametrem -n říkáme, že n-tý sloupeček nechceme zobrazit. Takže typické použití je např. comm -12 soubor1 soubor2 pro zobrazení řádků vyskytujících se v obou souborech.

Pokud chceme dva soubory jen porovnat na shodnost (pro to už pochopitelně nemusí být setříděné), můžeme použít příkaz cmp. Ten skončí s nulovou návratovou hodnotou, pokud je obsah souborů shodný, jinak s nenulovou (dá se tedy použít v rámci příkazu if). Při použití ve skriptech doporučujeme přidat parametr -s, aby se při neshodě nevypisovalo informativní hlášení.

Dalším nástrojem pro porovnávání souborů je diff, který umí zobrazit „v čem“ se dva soubory liší. Nejčastěji se používá pro porovnání dvou verzí téhož souboru, například když přemýšlíme, proč stará verze našeho programu fungovala a nová už ne. Doporučujeme používat přepínač -u (zapne trochu smysluplnější výstupní formát). S -N -r lze porovnávat rekurzivně celé adresáře. Zkuste si s ním pohrát.

Výstupu programu diff se obvykle říká buď „diff“ (mezi nějakou verzí a nějakou jinou), nebo „patch“. Druhé označení je odvozeno od příkazu patch, který s diff-em úzce souvisí. Vstupem příkazu patch je stará verze souboru a diff mezi starou a novou verzí, výstupem pak zrekonstruovaná nová verze. Například po spuštění

diff -u A B >AB.diff
patch -o C A AB.diff

Ještě větší výhodou je to, že patch lze obvykle aplikovat, i když se mezitím původní soubor (A v našem příkladu) změnil. Tohle umožňuje několika lidem nezávisle na sobě změnit nějaký soubor a poté všechny změny automaticky sloučit. Stačí, když každý vyrobí patch mezi společnou původní verzí a svou upravenou verzí a nakonec se všechny tyto patche na soubor postupně aplikují. Problém nastane pouze v případě, že se dva lidé pokusí změnit stejnou část souboru; v takovém případě dojde k takzvanému konfliktu, který je třeba vyřešit ručně. Ale to se stává překvapivě málo často.

Na tomto principu je založen vývoj mnoha open source projektů. Přispěvatelé si lokálně program mění a testují, a hotové změny posílají autorům ve formě patchů. Ale i vytváření a aplikování patchů a udržování historie vývoje je spousta ruční práce, pročež se tyto procesy snaží automatizovat takzvané verzovací systémy, jako např. git.

Příklad: Spam

Někteří jste si již možná všimli, že v KSPčku většinu hromadných mailů posíláme každému s vlastním oslovením, včetně správně vyskloňovaných tvarů slov dle pohlaví adresáta. Jak to děláme? Obvykle k mailu vytvoříme šablonu, prostý textový soubor, který může vypadat třeba takto:

Mil[ý|á] $osloveni,

byl[a] jsi vybrán[a] jako $co na soustředění...

kc@example.net:Květoslave Čeňku:M:náhradník
po@example.net:Pokusná Osobo:F:účastník
hroch@example.net:Hrochu:M:maskot

Potřebovali bychom umět v textu nahradit všechny řetězce v nějakém tvaru (např. [něco|něco]) za jiné řetězce, a ještě k tomu v náhradě použít nějaké části řetězce původního.

Regexy

Regex alias regulární výraz je řada písmenek a speciálních znaků, která právě dokáže popsat „řetězce nějakého tvaru“, jako v příkladu výše. O libovolném řetězci lze rozhodnout, jestli danému výrazu vyhovuje (má správný tvar), nebo nikoli. Regex tak vlastně popisuje nějakou (potenciálně nekonečnou) množinu řetězců. S něčím podobným jsme se již setkali: byly to wildcardy. Například nahrazovaný řetězec z příkladu výše bychom se mohli pokusit popsat wildcardem \apl{\tt *\|*\]. Ale možnosti wildcardů jsou poměrně omezené; s regexy se dají dělat mnohem zajímavější věci.

Níže najdete seznam konstrukcí použitelných v regexech. Literál je libovolná posloupnost znaků, které nemají speciální význam (nejsou použity v prvním sloupečku tabulky).

Kulaté závorky lze vynechat tam, kde by se v nich nacházel jediný znak nebo jiný nedělitelný element (např. množina), v případě alternativ, když by měly být kolem celého regexu.

Pár příkladů:

• [a-zA-Z_}[a-zA-Z0-9_]* vyhovuje platný identifikátor, jak je definován většinou programovacích jazyků – tedy neprázdná posloupnost písmen, číslic a podtržítek nezačínající číslicí.
• ([01]?[0-9]|2[0-3]):[0-5][0-9] vyhovuje čas zapsaný v 24-hodinovém formátu (např. 0:42).

Podrobnější úvod do regexů najdete v seriálu 23. ročníku či v desítkách internetových tutoriálů.

Nepleťte si regexy s wildcardy! Sice řeší podobný problém (popis množiny řetězců), ale jinak spolu nemají nic společného. Například pozor na to, že * v regexech je kvantifikátor, který značí opakování toho, co stojí před ní, samostatně stojící * nemá smysl. Obdobou wildcardové hvězdičky je regex .*. Liší se také použitím: wildcardy interpretuje shell a dají se použít pouze pro hledání názvů souborů, regexy se obvykle předávají nějakým pomocným utilitám a používají se pro hledání kusů textu.

Použití regexů: hledání a nahrazování

Kde lze regexy v Unixu použít? Například v nám dobře známém příkazu grep. Pokud mu místo přepínače -F (Fixed, hledej pevný řetězec) dáme -E, hledá řetězec vyhovující nějakému regexu. E znamená Extended a zapíná takzvanou rozšířenou syntaxi regexů (tu jsme si vysvětlili v předchozí kapitole). Existuje ještě „základní“ syntaxe (starší), která se používá, pokud grep-u nedáte žádný přepínač. Ta je ale matoucí a nekonzistentní, tak ji raději nepoužívejte. Za grep -E existuje zkratka egrep.

Nezapomeňte, že grep hledá řádky obsahující řetězec vyhovující regexu, ne řádky celé vyhovující regexu. Například řádek abcd nevyhovuje regexu [a-z], ale obsahuje a, které mu vyhovuje, a tedy echo abcd | grep -E '[a-z]' jej vypíše. Pokud bychom chtěli hledat řádky celé vyhovující regexu, stačí použít ^regex$.

Slíbili jsme spolehlivější zjištění ID uživatele hroch, zde je:

grep -E '^hroch:' /etc/passwd | cut -d: -f3

Tady hledáme slovo hroch pouze na začátku řádku a následované dvojtečkou, nezmate nás tedy uživatel druhyhroch či hrochodlak, ani někdo, kdo si nastaví jako shell /bin/hrochsh.

grep má ještě jeden přepínač, který je užitečný až s regexy: -o. Ten zajišťuje, že se nevypisují celé vyhovující řádky, nýbrž jen nalezené výskyty regexu. Pokud je na jednom řádku více výskytů, každý se vypíše na samostatný výstupní řádek. Například takto bychom mohli najít seznam všech identifikátorů (názvů funkcí, proměnných apod.) použitých v nějakém programu:

grep -Eio '[a-z_][a-z0-9_]*' program.c | sort -u

Pro plnou funkčnost bychom ještě museli odfiltrovat komentáře, stringové literály a klíčová slova. K tomu by nám mohl pomoci nástroj, který si představíme za chvíli.

Zamysleme se ještě nad jednou věcí. Pokud je v programu například identifikátor bagr, nachází se uvnitř něj i další platné identifikátory, jako např. ag. grep -o v takovém případě udělá to, co téměř vždy chceme: z každé množiny překrývajících se výskytů vypíše pouze ten nejlevější a nejdelší (což bude přesně odpovídat identifikátorům v programu doopravdy použitým).

Při předávání regexů jako parametrů příkazům je třeba dát si velký pozor na to, že mnoho regexových speciálních znaků má zvláštní význam i pro shell, a tedy pokud chceme, aby se např. ke grep-u dostaly nezměněné, musíme je před shellem zaescapovat. Nejjednodušším řešením je psát všechny regexy do apostrofů, kde se nic escapovat nemusí.

Pokud přece jen z nějakého důvodu escapovat budeme, je třeba si uvědomit, že máme co do činění se dvěma úrovněmi escapování. Například pokud napíšeme grep ^\\\* soubor, nejprve dostane řetězec do rukou shell, který ví, že \\ ve skutečnosti znamená \ atp., všechny escapy odstraní a grep-u předá jako první parametr řetězec ^\*. grep zase ví, že \* znamená literál „*“, tedy tento příkaz tedy vybere ze souboru řádky začínající hvězdičkou.

Když už umíme výskyty regexů v textu hledat, hodilo by se také umět je nahrazovat něčím jiným. Řešení si představíme zatím jen jako zaklínadlo sed -re 's/regex/náhrada/g'. Nebojte, za chvíli si ho vysvětlíme.

Jak jsme slibovali na začátku, v textu náhrady se lze odkazovat na části původního textu: přesněji na obsah libovolné kulaté závorky. Obalit závorkou můžeme cokoliv, aniž by se tím změnil význam regexu. Počítají se všechny závorky, včetně těch vynucených např. kvůli ohraničení skupiny alternativ. Obsah závorky do náhrady vložíme speciální sekvencí \číslo, kde číslo je pořadové číslo závorky (přesněji řečeno, páry závorek se číslují od jedničky v pořadí jejich otevíracích závorek). To mimo jiné znamená, že i v náhradě musíme escapovat zpětná lomítka, pokud je tam chceme vložit doslovně.

Například pokud chceme v textu nahradit slovo bagr ve všech tvarech za slovo kombajn, můžeme použít příkaz

sed -re 's/bagr(|u|em|y|ů|ům|ech)/kombajn\1/g'

Řešení: Spam

Nyní už máme téměř vše, co potřebujeme k řešení spamovacího příkladu. Můžeme si jej zkusit načrtnout. Předpokládejme, že v shellových proměnných $osloveni, $pohlavi a $co máme příslušné údaje k vyplnění.

tvar=$(echo $pohlavi | tr MF 23)
<sablona sed -re "s/\\\$osloveni/$osloveni/g" \
   | sed -re "s/\\\$co/$co/g" \
   | sed -re 's/\apl{\tt ((.*)\|)?(.*)\]/\'$tvar/g
}

Jak to funguje?
První dva \verb.sed.-y jsou přímočaré nahrazení jednoho řetězce za jiný,
jen pozor na escapování dolarů (od shellu i regexu). Poslední regex
hledá řetězce tvaru \hbox{\verb+[+{\it něco}\verb+|+{\it něco}\verb+}+

s/\apl{\tt ((.*)\|)?(.*)\]/\3/g}
První část
(\uv{\hbox{{\it něco}\verb+|+}}) je nepovinná, pokud mužský tvar není
uveden, předpokládá se prázdný.

Toto řešení skoro funguje, ale ještě ne úplně. Zapomněli jsme totiž
upozornit na jednu věc: regexy jsou {\I žravé}. To znamená, že při
hledání vždy vyberou nejdelší kus textu, který jim vyhovuje. Tedy
například pro text \verb+Mil[ý|á

Nyní už to opravdu dělá, co má. Celý rozesílací skript by mohl vypadat takto:

cat adresati \
| while IFS=: read mail osloveni pohlavi co; do
t=$(echo $pohlavi |tr MF 23)
<sablona sed -re "s/\\\$osloveni/$osloveni/g" \
 | sed -re "s/\\\$co/$co/g" \
 | sed -re 's/\apl{\tt (([^}|]*)\|)?([^]|]*)\]/\'$t/g
 | mail -s "Pozvánka na soustředění" "$mail"
done

sed pro pokročilé

Je na čase naše sedové zaklínadlo rozklíčovat. sed ve skutečnosti dostane text a aplikuje na něj posloupnost příkazů. Tu mu můžeme předat buď jako parametr s použitím přepínače -e příkaz, nebo načíst ze souboru parametrem -f soubor (hodí se pro delší a složitější příkazy; v souboru nemusíme řešit shellové escapování). Jednotlivé příkazy se oddělují středníkem nebo koncem řádku. Též můžeme více příkazů zadat několikanásobným použitím příkazu -e.

Přepínač -r zapíná rozšířenou syntaxi regexů, podobně jako u grep-u -E. Doporučujeme používat v podstatě vždy.

Všechny příkazy mají jednoznakový název. My jsme dosud používali příkaz s (substitute) sloužící k nahrazování. Ten má tvar s/regex/náhrada/modifikátory. Místo lomítek můžeme použít jakýkoli jiný znak (kromě písmen). Můžeme se tak vyhnout problémům s regexy obsahujícími lomítka. Oblíbenými volbami jsou např. | či # pro svou vizuální výraznost. Modifikátor g (global) znamená nahrazení všech výskytů na řádku (jinak by se na každém řádku nahradil jen první). Dalším zajímavým modifikátorem i (ignoruj velikost písmen).

sed zpracovává vstup po řádcích a na každém z nich zvlášť provede všechny příkazy v pořadí, ve kterém jsou zapsány. Ve skutečnosti se každý řádek načte do řetězcové proměnné, které se říká pattern space, na ní se provádějí jednotlivé příkazy a po jejich skončení je výsledná hodnota pattern space vypsána na výstup, není-li sed spuštěn s parametrem -n („nevypisovat“).

Před většinu příkazů lze napsat takzvanou adresu a tím určit, že se budou provádět jen na některém řádku či řádcích. Adresou může být například:

• číslo – Této adrese vyhovuje právě tolikátý řádek vstupu, počítáno od jedničky.
• $ – Poslední řádek.
• /regex/ – Řádek obsahující výskyt regexu. Chceme-li použít místo lomítka jiný oddělovač, musíme na začátek napsat backslash, např. \#/dev/null# adresuje řádky obsahující řetězec „/dev/null“.
• adresa! – Negace adresy, vyhovují řádky nevyhovující původní adrese.

Nyní už má smysl vysvětlit si některé další příkazy, které bez adresování nejsou příliš užitečné:

• p – vypíše aktuální obsah pattern space na výstup. Nejčastěji se používá spolu s parametrem -n pro selektivní vypisování řádků. Například sed -nre '/regex/ p' je to samé, jako grep -E 'regex'. Kombinací s/^.*$/text/ a p můžeme na výstup vypsat libovolný text.
• d – „smaže“ řádek (zabrání jeho vypsání a skočí na další). Tedy sed -re '/regex/ d' funguje jako grep -vE.
• y/znaky/znaky/ – nahradí znaky z jednoho seznamu za odpovídající znaky z druhého, stejně jako tr, včetně stejného zápisu výčtů a rozsahů.

Příkazu můžeme dát místo jedné adresy také dvojici adres oddělených čárkami. Tím zadáváme rozsah – příkaz se provádí na všech řádcích od první adresy po druhou. Přesněji řečeno kdykoli se narazí na řádek vyhovující první adrese, příkaz se začne provádět a když se narazí na řádek vyhovující druhé adrese, zase se provádět přestane. Rozsah vždy zahrnuje oba krajní řádky (vyhovující příslušným adresám). Takto se může příkaz provést i pro několik bloků řádek, pokud každý z nich začíná řádkem vyhovujícím první adrese a končí řádkem vyhovujícím druhé.

Některé formáty (například e-mailové zprávy) mají takovou strukturu, že obsahují nejprve hlavičky (s informacemi jako odesilatel, předmět atp.), potom prázdný řádek, a teprve za ním tělo (text zprávy). Pokud bychom chtěli blok hlaviček odstranit, můžeme použít příkaz:

sed -re '1,/^$/ d'

Ukázky, jak pomocí sed-u nahradit grep, nebyly samoúčelné. sed totiž oproti grep-u má jednu velkou výhodu, totiž přepínač -i (inplace). Již v prvním díle jsme se bavili o tom, že nemůžeme z jednoho souboru zároveň načítat a zároveň do něj zapisovat (grep slovo <soubor >soubor neudělá to, co byste chtěli). sed -i tohle umí zařídit. Jen mu dáte jako parametr (tedy nikoli shellové přesměrování) název souboru, a on z něj načte vstup a do toho samého souboru uloží svůj výstup. Interně to dělá tak, že vytvoří dočasný soubor, do kterého výstup zapisuje, a po svém skončení s ním nahradí (pomocí ekvivalentu příkazu mv) atomicky původní soubor. Tedy sed -i -re ... soubor je ekvivalentní posloupnosti příkazů:

sed -re ... <soubor >soubor.tmp
mv soubor.tmp soubor

Toto je velmi častý unixový idiom, který je dobré si zapamatovat. Hodí se nejen když chceme zapisovat do stejného souboru, ze kterého čteme, ale víceméně kdykoli nahrazujeme či vytváříme nějaký soubor. Tím, že data zapisujeme do nějakého dočasného souboru, který kromě nás nikdo jiný nepoužívá, a teprve když je „hotový“, jej přesuneme na cílové místo, se nemůže stát, že se nějaká jiná aplikace pokusí číst soubor v průběhu vytváření, kdy ještě neobsahuje smysluplná data. Také pokud můžeme snadno zajistit (bashovým operátorem &&), že pokud náš příkaz modifikující nějaký soubor selže, mv se neprovede a zůstane zachovaná původní verze.

sed pro šílence

Se sed-em se dají dělat i větší šílenosti. Jeho příkazy tvoří vlastně jednoduchý programovací jazyk (Je turingovsky úplný, ale asi v podobném smyslu, jako Brainfuck. Dá se najít implementace Turingova stroje v sed-u. Nebo Sokoban. Zagooglete si.). Kromě pattern space máte k dispozici ještě druhou(!) stringovou proměnnou, které se říká hold space. Pomocí příkazů h a H můžete aktuální obsah pattern space zapsat do hold space, resp. připojit na jeho konec. g a G dělají to samé opačným směrem. Při připojování je nový obsah od původního oddělen znakem konce řádku (\n). Příkazem x lze prohodit obsah pattern a hold space.

Pokud bychom si chtěli řídit načítání řádek nějak přesněji, než že pro každý řádek je náš program spuštěn znovu od začátku, můžeme. K tomu slouží příkazy n, který do pattern space další řádek (původní zahodí) a N, který připojí další řádek na konec pattern space (oddělený \n, podobně jako G). To vše se děje stále v rámci jedné iterace našeho skriptu. Pokud doběhne na konec, sed automaticky načte první ještě nenačtený řádek do pattern space a spustí náš program znovu od začátku. Tyto příkazy nám umožňují nezpracovávat jednotlivé řádky jen nezávisle, ale dělat i nějaké složitější úpravy napříč řádky.

Proměnné už máme, ale správný programovací jazyk ještě potřebuje nějaké řídící konstrukce. sed nabízí návěští (: název), skoky (b název) a podmíněné skoky (t název). Podmíněný skok se provede, pokud od posledního podmíněného na tomto řádku vstupu došlo k alespoň jednomu úspěšnému nahrazení příkazem s (existuje i verze T, která má podmínku invertovanou).

Pokud chceme testovat, zda uspěl jeden konkrétní nahrazovací příkaz, musíme si nejdřív případné dřívější úspěchy na daném vstupním řádku „vyresetovat“ prostřednictvím příkazu t:

t reset; : reset; s/regex/náhrada/; t cil;

Nechceme-li nic nahrazovat a rádi bychom jen skákali podle toho, zda pattern space vyhovuje nějakému regexu, můžeme použít příkaz b podmíněný adresou: /regex/ b.

Všechny verze skoku při vynechání argumentu skáčou za poslední příkaz. q a Q ukončí celý sed s vypsáním aktuálního pattern space, resp. bez něj. Umí nastavit návratovou hodnotu. Dále existují příkazy r a w pro čtení/zápis z/do pomocných souborů. Příkazy [qQT] jsou rozšířením GNU sed-u (nejběžněji se vyskytující verze) a nemusí být dostupné v jiných verzích.

Zkusme si například napsat skript, který spojuje příkazy rozdělené na několik řádek pomocí zpětných lomítek do jednoho řádku:

sed -re ': loop; s/\\$//; T; N; s/\n//; t loop'

prvni
dr\
uh\
y

prvni
druhy

Další nástroje

Posledním významným nástrojem, který jsme nezmínili, je awk. To by nejspíš vydalo na samostatný díl. Slouží primárně k složitější práci s tabulkovými soubory. Na rozdíl od cut-u umí používat složitější než jednoznakové oddělovače, např. libovolnou posloupnost bílých znaků (ta je u awk dokonce výchozím oddělovačem). To se hodí při práci se soubory, jako je /etc/fstab. Program v awk je podobně jako v sed-u posloupnost příkazů, která se spouští pro každý řádek a příkazům lze předřadit podmínku omezující, na kterých řádcích běží. Jazyk awk má daleko blíže k plnohodnotnému programovacímu jazyku než sed: má pojmenované proměnné, asociativní pole a další vychytávky.

Uvedeme jen několik málo příkladů použití, měly by být zčásti samovysvětlující, zčásti interpretovatelné s pomocí manuálové stránky:

• Vyseknutí sloupečku odděleného obecnou posloupností bílých znaků z tabulky:

    awk '{print $2}' /etc/fstab
  

• Nalezení uživatele s daným ID:

    awk -F: '($3 == 0) { print $1 }' /etc/passwd
  

• Sečtení všech (číselných) řádků v souboru:

    awk '{ sum += $1 } END { print sum }'
  

Postavení awk na půli cesty mezi jednoduchou utilitkou a plnohodnotným programovacím jazykem z něj činí trochu zvláštní nástroj. Někdy je lepší použít místo něj cut či sed, jindy naopak opravdový programovací jazyk. Na zpracování textu nejlépe poslouží Perl, který má bohatou podporu pro regexy a spoustu syntaktických zkratek, jež v něm umožňují většinu jednoduchých věcí napsat podobně krátce jako v jednoúčelových nástrojích.

Jakou malou ochutnávku Perlu vám ukážeme skript, který z HTML dokumentu vypíše titulky všech hypertextových odkazů:

perl -0777 -ne 'for (m{<a.*?>.*?</a>}gcs) {
    s/<.*?>//g; s/(^\s+|\s+$)//g;
    print "$_\n" if $_;
}'

Úkoly

V řešení se nebojte používat pomocné soubory, kde je to na místě, klidně pro jednoduchost s pevnými jmény. Můžete používat vše, co jsme se naučili, a další utilitky podobného ražení, můžete používat awk. Perl ani jiné „velké“ programovací jazyky nepoužívejte.

Úkol 1 [2b]

Ve vstupním souboru máte seznam jmen (sudý počet, jedno na řádek). Napište skript, který z nich vytvoří náhodné dvojice a vypíše je na výstup ve formátu první osoba:druhá osoba.

A
B
C
D

C:A
B:D

Úkol 2 [4b]

Napište skript řešící úlohu 27-Z3-2. Ve vstupním souboru dostanete slovník (jedno slovo na řádku), na výstup vypište nejdelší slovo, které má ve slovníku i svou verzi napsanou pozpátku.

kecup
ves
vrabec
pucek
sev

kecup

Řešení s pomocí bashových cyklů je nudné, pro plný počet bodů to zkuste bez nich. Mohlo by se vám hodit awk a jeho funkce length.

Úkol 3 [4b]

V nějakém adresáři máte staženou spoustu dílů svého oblíbeného seriálu (z legálních zdrojů, pochopitelně). A jak už to tak u legálních zdrojů chodí, soubory jsou pojmenované naprosto neuspořádaně. Jediné, čím si můžete být jisti, je, že název obsahuje číslo série a číslo epizody v tomto pořadí, mezi nimi je alespoň jeden nečíselný znak a pro jednoduchost název žádné jiné číslice neobsahuje.

Napište skript, který stáhne z Wikipedie (či jiného příhodného zdroje) názvy dílů a všechny soubory přejmenuje tak, aby v jednotném formátu obsahovaly číslo série a číslo a název epizody. Chcete-li, můžete předpokládat, že všechny soubory jsou ze stejné série.

Možná se vám snáz než HTML bude parsovat zdrojový wikitext, který získáte připojením ?action=raw na konec URL článku.

Úkol 4 [4b]

Vylepšete příklad vypisující všechny identifikátory v Céčkovém programu tak, aby ignoroval obsah řetězců a komentářů, případně základní klíčová slova. Pro plný počet bodů by měl zvládnout jednořádkové (// ...) i víceřádkové (/* ... */) komentáře a neměl by se nechat zmást escapovanými uvozovkami a zpětnými lomítky v řetězcích. Ale určitě má smysl poslat i jednoduché či částečné řešení. Obskurnosti jako komentář uvnitř řetězce (nebo naopak) ošetřovat nemusíte, pokud vyloženě nechcete. Předpokládejte samozřejmě, že program je syntakticky správný.

/* print a greeting
   with quoted name */
printf("Hello, \"%s\"",
       name);

  name
  printf

Pokud si s Céčkem nerozumíte, můžete si vybrat nějaký jiný srovnatelně složitý (tedy třeba by měl ideálně mít víceřádkové komentáře či řetězce) programovací jazyk – třeba Python nebo Pascal.

Z cvičných důvodů zkuste nenačítat celý vstupní soubor do paměti najednou. Ano, bylo by to jednodušší a pro praktické účely možná nejlepší řešení, ale tolik se toho na něm nenaučíte.

Filip Štědronský

Řešení