Třetí série patnáctého ročníku KSP

Zadání úloh

15-3-1 Potrubí (11 bodů)

Za patero stohy dopisů, třemi poštovními schránkami a známkovým mořem leží Postánie. V Postánii si velmi libují v zasílání různých dopisů, pohledů či korespondenčních lístků, a protože standardní způsob přepravy zásilek je příliš pomalý, často se k doručování využívá potrubní pošta. Zásilka potrubní poštou putuje tak, že je na jedné poště vložena do potrubí a vypadne na druhém konci potrubí na jiné poště. Tam je opět vložena do nějakého potrubí (to se samozřejmě zvolí podle cílové pošty) a putuje takto dále, dokud nedojde na cílovou poštu. Udržování systému potrubí je ale poměrně nákladná záležitost, a tak vrchní poštmistr přemýšlel, jak zminimalizovat potřebný počet potrubí. Přitom by ale nechtěl snížit úroveň služeb zákazníkům. Po nějaké době zjistil, že to není vůbec jednoduché, a proto vás požádal o pomoc.

Vaším úkolem je napsat program, který dostane na vstupu počet poštovních stanic N a počet potrubí mezi stanicemi M. Dále dostane popis oněch M potrubí – každé potrubí je jednoznačně určeno číslem poštovní stanice, ze které vychází, a číslem poštovní stanice, do které vede (stanice číslujeme od 1 do N). Potrubí jsou jednosměrná, ale mezi dvěma stanicemi mohou vést klidně dvě potrubí – každým směrem jedno. Na výstup má váš program vypsat nejkratší možný seznam potrubí, která je třeba zachovat (nová potrubí nesmíte vytvářet) pro zajištění služeb zákazníkům. Tedy pokud dříve mohla dojít zásilka z pošty A na poštu B, tak tam může dojít i po redukci potrubí. Pokud je možných seznamů více, stačí vypsat libovolný z nich.

Příklad: Pro 6 poštovních stanic a 8 potrubí (2, 1), (2, 3), (3, 4), (4, 2), (4, 1), (6, 5), (5, 4), (6, 4) je jedním z možných řešení zachovat potrubí (2, 3), (3, 4), (4, 2), (2, 1), (6, 5), (5, 4) (místo potrubí (2, 1) bychom též mohli zachovat potrubí (4, 1)).

Řešení

15-3-2 Permutace (9 bodů)

Permutace P čísel 1,… ,N je libovolné prosté zobrazení množiny čísel {1,… ,N} na sebe. Permutace tedy přiřazuje každému i∈{1,… ,N} nějaké číslo P[i]∈{1,… ,N} a tato čísla jsou pro různá i různá. k-té složení permutace P je permutace Pk s vlastností:

Pk[i] = P[P[ … P[i]]], ∀i∈{1,… ,N}
k-krát

Napište program, který dostane na vstupu N, k, a dále N čísel popisujících permutaci P (i-té číslo je hodnota P[i]) a na výstup vypíše k-té složení permutace (ve stejném formátu, jako na vstupu). Snažte se, aby program pracoval co nejrychleji a předpokládejte, že k může být o hodně větší než N.

Příklad: Pátým složením permutace na číslech 1,… ,5 tvaru (2,1,4,5,3) je permutace (2,1,5,3,4).

Řešení

15-3-3 Tajemný obraz (10 bodů)

V Chile objevili archeologové tajemný obraz z předkolumbovské doby. Obraz vypadá jako několik bodů rozmístěných na pomyslné kružnici, přičemž každé dva body jsou spojeny rovnou čarou. Každá z čar je buď žlutá nebo červená. Archeologové dlouho hledali smysl této malby, ale žádný nemohli nalézt. Až amatérský archeolog a dobrodruh Erik von Kaetzinken po dlouhém pátrání vyslovil hypotézu, že obrazec je poselstvím dávných Inků. Počet jednobarevných trojúhelníků s vrcholy na pomyslné kružnici prý udává počet dní od namalování obrazce, po nichž mají na Zemi opět přistát mimozemšťané. Protože obrazec je poměrně velký, rozhodl se Erik určit počet těchto jednobarevných trojúhelníků pomocí počítače.

Vaším úkolem je napsat program, který dostane na vstupu počet bodů nakreslených na obrazci N, 3≤ N a dále seznam dvojic čísel bodů (body si očíslujeme od jedné do N), které jsou propojeny červenou čarou (zbylé dvojice bodů jsou tedy propojeny žlutou). Na výstup program vypíše počet jednobarevných trojúhelníků v zadaném obrazci (tzn. takových trojúhelníků, jejichž všechny tři vrcholy leží v bodech vyznačených na kružnici a jsou spojeny čarami téže barvy).

Příklad: V obrazci s pěti body a červenými čarami mezi body (1,2), (2,3), (3,4) a (2,4) jsou tři jednobarevné trojúhelníky (jeden červený a dva žluté). Červený trojúhelník má vrcholy v bodech 2,3,4 a žluté trojúhelníky v bodech 1,3,5 a 1,4,5.

Řešení

15-3-4 Výsadek (10 bodů)

Krtci se jednoho krásného dne rozhodli provést výsadek (nebo možná přesněji výhrabek) na zahradě strýčka Pompa. Zahrada strýčka Pompa je ale dosti členitá a rozlehlá a když se takový krtek někde vyhrabe ze země, má velké problémy zjistit, zda je v zahradě či nikoliv (obvzláště proto, že zrak nepatří zrovna silným vlastnostem krtků). Centrální velitelství krtčích výhrabkových sil (CVKVS) proto každého krtka vybavilo navigačním systémem GPS, takže když se krtek vyhrabe, zná přesně svou polohu (do té doby ji nezná, protože GPS pochopitelně nefunguje pod zemí). Nyní by ale CVKVS ještě potřebovalo program pro svůj počítač, který z polohy krtka určí, zda je v zahradě či nikoliv. A to je již úkol pro vás.

Napište program, který dostane na vstupu popis zahrady strýčka Pompa (zahrada strýčka Pompa je nekonvexní N-úhelník) – tedy počet sloupků v plotu zahrady N a dále jejich souřadnice (tedy N dvojic čísel). Souřadnice sloupků jsou zadávány v tom pořadí, v jakém jsou sloupky na obvodu zahrady. Po předzpracování popisu zahrady má váš program co nejrychleji odpovídat na dotazy, zda zadané souřadnice leží nebo neleží uvnitř zahrady. Při řešení se snažte, aby doba předzpracování byla rozumná (polynomiální), ale důležitá je hlavně rychlost odpovědi na dotaz.

Příklad: Pro zahradu o pěti sloupcích se souřadnicemi (0,5), (3.2, 5), (2.2, 3.1), (4.2, 1), (0, 0) by měl program odpovědět na dotaz (1, 1) kladně (krtek je v zahradě) a na bod (5, 4) záporně (krtek není v zahradě).

Řešení

15-3-5 Haskell (10 bodů)

V minulé sérii jsme se zabývali psaním obecných funkcí; nicméně jejich obecnost byla poměrně omezeného druhu – víceméně šlo pouze o omezení se na (pro danou úlohu) relevantní vlastnosti objektu. V této sérii se podíváme ještě o úroveň výše, na prostředky umožňující nám vyjádřit ještě abstraktnější obecně používané postupy.

Typickým použitím je vyjádření sekvencionality nějakých procesů. Podívejme se například na následující situaci: nechť se naše úloha skládá z nějakých akcí, které mohou selhat, a selže-li jedna z nich, chceme přestat provádět ostatní akce a vrátit chybu. Navíc některé z těchto akcí mohou záviset na předchozích výsledcích. Konkrétně se může jednat třeba o načtení několika hodnot z databáze a zápis výsledku na nich založeného výpočtu; kterákoliv akce s databází může kvůli nějaké chybě selhat. Jak toto budeme realizovat?

Samotné funkce pro práci s databází budou mít tyto typy:

cti :: Databaze -> Klic -> Maybe Hodnota
pis :: Databaze -> Klic -> Hodnota -> Maybe Databaze
  - - pis musí vracet novou databázi, protože v Haskellu nelze změnit hodnotu
  - - proměnné (nemáme přesně definováno pořadí vyhodnocování operací, takže
  - - bychom jinak nebyli schopni rozhodnout, zda přistupujeme k nové či staré
  - - databázi)

Připomeňme definici typu Maybe:

data Maybe a = Just a |
               Nothing

Hodnotu Nothing budeme používat pro návrat chyby. Náš program by tedy vypadal asi takto:

uprava :: Databaze -> Maybe Databaze
uprava databaze =
  case cti databaze klic1 of
    Nothing -> Nothing                               - - chyba
    Just hodnota1 ->
      case cti databaze klic2 of
        Nothing -> Nothing                           - - chyba
	Just hodnota2 ->
	  let vysledek = vypocet hodnota1 hodnota2 in
	  case pis databaze klic3 vysledek of
            Nothing -> Nothing                       - - chyba
	    Just databaze' -> Just databaze'         - - hurá, všechno je OK

Tento program je samozřejmě velmi nepřehledný, při jeho psaní jsme se mohli snadno splést a zbytečně opakujeme pořád stejnou práci - - to nás vede k myšlence společné úseky schovat do nějaké funkce, která by vypadala třeba takto:

(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
  - - kvuli jednoduššímu používání si nadefinujeme operátor (funguje to úplně
  - - stejně jako definice funkce)
Nothing >>= f = Nothing
  - - předchozí výpočet selhal --> konec
Just r >>= f =
  - - máme výsledek přechozího výpočtu, provedeme ten následující:
  let rf = f r in
  case rf of
    Nothing -> Nothing    - - chyba
    Just r1 -> Just r1    - - OK

Přidáme si ještě jednu konstrukci běžnou pro funkcionální jazyky – anonymní funkce. Výraz \x -> x + x je funkce s jedním parametrem, která provede naznačený výpočet (zdvojnásobení x). To je užitečné například pokud někde potřebujeme jednoduchou funkci, kterou nepoužíváme nikde jinde; třeba map (\x -> x + 1) s zvětší hodnotu všech prvků v seznamu s o 1. Pravá strana -> sahá vždy tak daleko, jak je to jen možné; v následujícím příkladu tedy až ke konci definice funkce uprava.

Nyní můžeme výše uvedenou funkci napsat mnohem elegantněji:

uprava :: Databaze -> Maybe Databaze
uprava databaze =
  cti databaze klic1 >>= \hodnota1 ->
  cti databaze klic2 >>= \hodnota2 ->
  let vysledek = vypocet hodnota1 hodnota2 in
  pis databaze klic3 vysledek >>= \databaze' ->
  Just databaze'

Povšimněte si podobnosti s následujícím imperativním programem (ve skutečnosti je toto také program v Haskellu; zde popisovaná technika je natolik důležitá, že pro ni byla zavedena tato zkrácená forma zápisu):

uprava databaze =
  do
   hodnota1 <- cti databaze klic1
   hodnota2 <- cti databaze klic2
   let vysledek = vypocet hodnota1 hodnota2
   databaze' <- pis databaze klic3 vysledek
   return databaze'

Podobnost samozřejmě není náhodná – naším záměrem bylo popsat sekvenční vyhodnocování, což je základní rys imperativních jazyku.

Tohle by ještě nebylo až tak zajímavé; nicméně existuje mnoho dalších aplikací podobné myšlenky (uveďme třeba konstrukci parseru, přenášení stavu mezi výpočty, distribuci náhodných čísel, simulaci nedeterministických výpočtů, vstup a výstup, …). Jejich společné vlastnosti zachycuje následující standardní třída Monad:

class Monad m where
 (>>=) :: m a -> (a -> m b) -> m b
 return :: a -> m a
 fail :: String -> m a

Povšimněme si toho, že m v této definici je „funkce“ nad typy – instancemi této třídy jsou typové konstruktory, jako například Maybe, [], nikoliv typy Maybe a, [a]. Konkrétní příklad instance:

instance Monad Maybe where
 (>>=) = ...                 - - viz výše
 return x = Just x
 fail s = Nothing

Samotný typ Monad m => m a je potřeba chápat jako „akci (program, proces, výpočet), určený typem m, vracející hodnotu typu a“. >>= je pak zřetězení takových dvou akcí (přičemž ta druhá má k dispozici výsledek první), return a je prázdná akce, vracející a, a fail označuje chybu (parametr je chybová hláška, v našem případě je prostě ignorována – nemáme ji kam uložit).

Proč jsou monády tak důležité?

Na poslední bod se nyní podívejme trochu blíže. Vstup a výstup v čistém funkcionálním jazyce je problém – vše mají být funkce, tedy nesmí mít žádné vedlejší efekty, což interakce s okolím rozhodně je. I když bychom dovolili výjimky, máme problém:

Řešením je monáda IO. IO a je akce, zahrnující případné vstupy a výstupy a jako výsledek vracející hodnotu typu a. K dispozici máme funkce jako getChar::IO Char (akce, která načte a vrátí znak) a putChar::Char->IO () (funkce, která pro každý znak vrátí akci, která tento znak vypíše). Co je důležité, v Haskellu neexistuje funkce, která by takovou akci vyhodnotila. Jediný zpusob, jak příslušnou akci provést, je přiřadit ji jako definici konstanty (tedy funkce bez paramentru) main::IO ().

Samotný typ IO a by mohl vypadat (ve skutečnosti je to abstraktní typ, tj. jeho vnitřní struktura může být jakákoliv a nemůžeme s ním přímo pracovat) zhruba takto:

data IO a = IO (Svet -> (Svet, a))
            - - funkce, která vezme stav světa, aplikuje na něj nějaké vstupně-výstupní operace
	    - - a vrátí nový upravený svět a výsledek

(Svet je typ, který (teoreticky) obsahuje stav celého světa. To řeší problém vedlejších efektů – žádné nejsou, protože není žádné „vedle“. Práce IO monády spočívá v tom, že nám se Svetem znemožňuje dělat věci typu kopírování, vrácení se ke starší verzi a podobně). Operace >>= by pak byla definována zřejmým způsobem:

IO akce1 >>= f = IO akce
 where
   akce svet =
     let (svet1,vysledek1) = akce1 svet
         IO akce2          = f vysledek1
      in akce2 svet1

Tolik teorie. Samotný program pak vypadá třeba takto:

main :: IO ()
main = 
 do
  l <- getLine             - - načti řádku
  let rev = reverse l      - - obrať ji
  putLine rev              - - a vypiš
  return ()

Hezké je, že předchozí program může napsat kdokoliv, bez jakýchkoliv vědomostí o tom, jak věci skutečně fungují.

Úloha:

Mějme funkci

page :: String -> String -> String
page stav dotaz = "Stav: " ++ stav ++ "; " ++ dotaz ++ "?"

Napište monádu CGI a dále dvě funkce 

runCGI :: CGI () -> String -> String -> String
cgiPage :: String -> CGI String
pro které tento program 
cgi :: CGI ()
cgi =
 do
   r1 <- cgiPage "Dotaz 1"
   r2 <- cgiPage "Dotaz 2"
   r3 <- cgiPage ("Dotaz 3 (vase predchozi odpoved byla " ++ r2)
   return ()

bude fungovat takto:

> runCgi cgi "" ""
"Stav: q=0; Dotaz 1?"
 
> runCgi cgi "q=0" "odpoved1"
"Stav: q=1,o1=odpoved1; Dotaz 2?"
 
> runCgi cgi "q=1,o1=odpoved1" "odpoved2"
"Stav: q=2,o1=odpoved1,o2=odpoved2; Dotaz 3 (vase predchozi odpoved byla odpoved2)?"
 
> runCgi cgi "q=2,o1=odpoved1,o2=odpoved2" "odpoved3"
""

Řešení