První série třináctého ročníku KSP

Zadání úloh

13-1-1 Logické výrazy (10 bodů)

Firma Paleologic se rozhodla uvést na trh svůj nový kalkulátor pracující mimo jiné i s logickými výrazy. Protože doba uvedení na trh se blíží a modul pracující s výrazy dosud nebyl vytvořen, požádali vás vývojáři této renomované společnosti o pomoc.

Na vstupu váš program dostane logický výraz a nemá udělat nic složitějšího, než na výstup vypsat jeho výsledek. Zadaný logický výraz (pro jednoduchost předpokládejte, že je korektní) se skládá z čísel ve dvojkové soustavě, operátorů (!, &, |, ^) a závorek (( a )). Operátor ! je unární a má nejvyšší prioritu ze všech operátorů. Ostatní operátory jsou binární, přičemž & má vyšší prioritu než | a ten má vyšší prioritu než ^.

Jednotlivé operátory jsou definované pro dvojice bitů resp. pro jeden bit v případě ! (na definiční tabulky jednotlivých operátorů se můžete podívat na konci tohoto zadání). Na čísla se pak aplikují po bitech. Tedy např. 1100 & 0101 je 0100.

Příklad: 101|0010&!(111^011) = 111

Tabulky operátorů:

AB&|^
00000
01011
10011
11110
A!
01
10

Řešení

13-1-2 Centrum (10 bodů)

V Railetánii se rozhodli vybudovat nové ředitelství drah. Aby úředníci nemuseli jezdit moc daleko, je třeba ho vybudovat někde „uprostřed“ železniční sítě. Takové místo je ovšem těžké najít. Situaci naštěstí zjednodušuje fakt, že v Railetánii mezi každými dvěma zastávkami vede právě jedna cesta po kolejích.

Váš program dostane na vstupu počet zastávek N. Zastávky si budeme číslovat od jedné do N. Dále dostane seznam tratí mezi zastávkami. Každá trať je charakterizována čísly dvou zastávek, které propojuje. Předpokládáme, že trati se mezi zastávkami nekříží. Jako vzdálenost dvou zastávek pak vezmeme počet tratí, po kterých je nutné projet, abychom se dostali z jedné zastávky do druhé. Vaším úkolem je nalézt takovou zastávku, že k ní nejvzdálenější zastávka je co nejblíže (tedy má minimální maximum ze vzdáleností z ní do ostatních zastávek). Pokud je takových zastávek více, stačí vrátit libovolnou z nich.

Řešení

13-1-3 Stabilní úsek (11 bodů)

Strýček Skrblík se jednoho dne rozhodl, že budova plná mincí je již přeci jen trochu staromódní způsob uchovávání majetku, a že své peníze tedy investuje do akcií. Nechce ovšem pochopitelně o žádné peníze přijít, a tak potřebuje najít akcie, které jsou dostatečně důvěryhodné. Nakonec se rozhodl, že důvěryhodnost akcií bude posuzovat podle stability jejich ceny. Čím déle má (nebo měla) nějaká akcie stabilní cenu, tím je důvěryhodnější. Nyní, když už pan Skrblík oddřel všechno myšlení, obrátil se na vás (protože s vámi má již dobré zkušenosti z minulého ročníku) s takovým triviálním problémem. Pro každou akcii spočítat, jak nejdéle byla stabilní.

Na vstupu váš program dostane dvě čísla D a N a pak posloupnost celých čísel a1, a2… aN. Jeho úkolem je nalézt nejdelší úsek v posloupnosti takový, že žádné dva prvky v něm se neliší o více jak D (formálně tedy hledáme taková i, j, 1≤ i≤ j≤ N, že pro každé k, l∈{i… j} platí -D≤ ak-al≤ D a j-i je maximální možné).

Řešení

13-1-4 Stoky (10 bodů)

V jednom městě, které raději nebudeme jmenovat, měli složitý systém odvádění odpadních vod. Po letech přestaveb nakonec vedlo potrubí z každého sběrného místa do každého. Za ta léta ovšem dělníci také zapomněli, ve kterém sběrném místě je vlastně vývod z celého kanalizačního systému do blízké čističky odpadních vod, a nyní by to potřebovali zjistit. Vaším úkolem je napsat program, který jim ono místo pomůže nalézt.

Program na vstupu dostane počet sběrných míst N. Může pak klást dělníkům dotazy, zda teče voda mezi dvěma sběrnými místy daným směrem. Výtok ze systému je v takovém sběrném místě, že ze všech ostatních míst teče voda do něj. Protože počítač správy kanalizací má dosti omezenou paměť a počet sběrných míst je velký, není možné si pamatovat nějakou informaci pro každé sběrné místo (odborně řečeno: vaše programy by měli mít lepší než lineární paměťovou složitost).

Příklad:

N = 5
Dotazy:
2->5: Ne
1->5: Ne
2->4: Ano
1->3: Ano
2->3: Ano
4->3: Ano
5->3: Ano
Odtok je v místě 3.

Řešení

13-1-5 LISP (10 bodů)

V tomto ročníku jsme se rozhodli ukázat vám trochu netradiční přístup k programování, kterému se říká programování funkcionální (mějte s námi chvilku strpení, za chvíli dospějeme i k tomu, proč má takový podivný název), a tak v každé letošní sérii bude jedna úloha věnována jazyku Lisp.

Lisp je jazykem mnoha dialektů – existuje totiž ohromné množství různých interpreterů a aplikačních programů, které dávají uživateli možnost si dodefinovat své vlastní příkazy právě v Lispu (například známý Unixový textový editor Emacs), a jak už to tak bývá, každý, kdo si programoval svůj interpretr, se rozhodl, že si do jazyka přidá to, co mu tam chybí a že upraví věci, o kterých si myslí, že by se daly udělat lépe. Naštěstí všechny tyto dialekty mají mnoho společného, a tak si tu nadefinujeme náš vlastní velice jednoduchý dialekt, který bude obsahovat více méně jenom ono společné „jádro jazyka“, a nazveme ho Ksp-Lisp. Od září si budete moci z našeho archívu na Internetu stáhnout kompletní interpreter Ksp-Lispu (viz URL KSPáckých stránek v úvodu).

Veškerá data jsou v Ksp-Lispu uložena jako objekty. Každý objekt má svůj typ a svoji hodnotu (což může být i odkaz na nějaký jiný objekt, jak uvidíme za chvíli). Typů existuje jen několik málo:

Symboly se často používají jako proměnné: místo toho, abyste si do proměnné (tedy vlastně pojmenovaného místa v paměti) uložili nějakou hodnotu, v Lispu necháte nějaký symbol ukazovat na vaši hodnotu (jinými slovy nepojmenováváte místa v paměti, ale samotné hodnoty; díky tomu také nejsou přiřazeny typy proměnným, nýbrž objektům).

Páry a nil se používají k tvoření seznamů. Prázdný seznam se vždy vyjadřuje objektem nil, neprázdný seznam pak párem, jehož a ukazuje na první prvek seznamu a b na zbytek seznamu. Seznamy se obvykle zapisují jako posloupnosti objektů uzavřené v závorkách, přičemž jednotlivé objekty jsou odděleny libovolnou posloupností mezer, tabulátorů a konců řádků – tak například (+ 1 (2)) je tříprvkový seznam, jehož prvním prvkem je symbol +, druhým číslo 1 a třetím seznam obsahující jako svůj jediný prvek číslo 2. Tato struktura bude reprezentována párem, jehož a bude ukazovat na symbol + a b na druhý pár, jeho a bude ukazovat na integerový objekt 1, b na třetí pár, který bude mít v a uložen odkaz na čtvrtý pár (a ukazuje na integer 2, b na nil) a v b odkaz na nil. () je jen jiný název pro nil.

Mimo `klasických' seznamů můžete vytvářet i složitější struktury – „nekonečné“ cyklické seznamy (stačí, aby b posledního prvku ukazovalo na některý z prvků předchozích) nebo třeba binární stromy (listy reprezentujeme čísly nebo symboly, vnitřní vrcholy pak páry, jejichž a se bude odkazovat na levý podstrom a b na podstrom pravý).

Důležitým rozdílem oproti klasickým procedurálním jazykům je, že v Lispu nikdy přímo nealokujete paměť (a tím pádem ani neuvolňujete) – jakmile jakýkoliv objekt vznikne, interpreter pro něj sám nějaký kousek paměti přidělí a když už objekt nebude přístupný (to znamená, že se k němu nepůjde nijak dostat pomocí symbolů a odkazů mezi objekty), automaticky paměť uvolní k dalšímu použití (tomuto procesu se říká garbage collection [sbírání smetí]).

A jak se v Lispu programuje? Inu, je to funkcionální jazyk, takže se všechny programy skládají z funkcí. Každá funkce dostává své parametry (což jsou vlastně jen odkazy na objekty), vrací nějakou hodnotu (opět odkaz) a případně způsobí nějaký postranní efekt (side-effect), tedy založí, zruší čí změní nějaké globálně viditelné objekty nebo třeba něco vypíše do výstupu. Každé volání funkce se zapíše jako seznam typu (f 1 2 3), tedy prvním prvkem je funkce, která se má zavolat (obvykle symbol ukazující na nějaký seznam, jenž je definicí funkce) a všechny ostatní prvky se vyhodnotí jako parametry této funkce (mohou to být třeba opět volání funkcí popsaná seznamy).

Každý interpreter Lispu má dva módy – mód interaktivní (v tom přímo zadáváte funkce a on je vyhodnocuje a obratem vypisuje výsledky; velice šikovné pro ladění programů) a mód dávkový (tomu předáte nějaký soubor a on jej zpracuje, jako by byl řádek po řádku zadán interaktivně; tak se spouští již hotové programy). Nastartujete-li interpreter Ksp-Lispu, objeví se vám prompt oznamující, že se s vámi komunikuje interaktivně. Když pak zadáte (+ 1 2), Ksp-Lisp to pochopí jako volání funkce + s parametry 1 a 2 a jelikož funkce +, jak již název napovídá, slouží ke sčítání celých čísel, vypíše vám obratem výsledek 3. (Přesněji: nejprve se vyhodnotil symbol + a zjistilo se, že ukazuje na funkci, té se předaly odkazy na objekty 1 a 2, funkce jako výsledek vrátila odkaz na objekt 3, který byl vzápětí vypsán.) Seznam (* (+ 1 2) (+ 3 4)) by způsobil zavolání již několika funkcí a výsledkem, jak asi čekáte, by bylo číslo 21.

A takhle vypadají v Lispu všechny programy, i podmínky jsou totiž funkce (lépe řečeno speciální formy, jak uvidíme za chvilku, protože jejich argumenty se samočinně nevyhodnocují před tím, než jsou předány) – (if p q r) způsobí nejprve vyhodnocení podmínky p a poté, pokud je splněna (to znamená vyšlo-li něco jiného než nil), vyhodnotí se q, jinak r a vrátí se jeho hodnota. Místo cyklů se obvykle používají rekurzivně se volající funkce.

A teď již konečně prozradíme přesná pravidla pro vyhodnocování výrazů, tedy vlastně pro provádění programů. Vyhodnocení je proces, jehož vstupem je nějaký objekt x a výstupem nějaký jiný objekt y, který nazveme hodnotou objektu původního. Vyhodnocování probíhá takto:

Vyhodnocování si ukážeme na jednoduchém příkladu: (max 0 (+ 1 2)) zpracujeme tak, že nejprve zjistíme, že max je symbol, který ukazuje na definici funkce max, poté vyhodnotíme rekurzivně její argumenty: 0 se vyhodnotí na sebe samu, druhý parametr pak jako volání primitiva pojmenovaného symbolem + s parametry 1 a 2. Nakonec zavoláme funkci max, předáme jí výsledky (objekty 0 a 3) a výsledek posledního objektu v její definici vrátíme jako výsledek našeho vyhodnocování.

Mimo to ještě existují funkce s proměnným počtem argumentů – v jejich definici je místo úplného seznamu parametrů jen seznam končící symbolem &rest následovaným ještě jedním symbolem, kterému se přiřadí všechny zbývající argumenty jako seznam.

Následuje úplný seznam Ksp-Lispových primitiv a jejich parametrů. (Uvědomte si ovšem, že primitiva samotná jsou objekty, takže i když to není dobrým zvykem, si je můžete přejmenovat, jak chcete. Pod zde uvedenými jmény jsou dostupná při startu interpreteru.) Latinkou budeme označovat jména primitiv a argumenty speciálních forem, které se samočinně nevyhodnocují, kurzívou pak argumenty funkcí, `…' značí, že funkce může mít argumentů libovolně mnoho.

(+ x …) vrátí součet zadaných přirozených čísel. Analogicky - (s jedním parametrem se chová jako unární minus, jinak od prvního čísla odečte druhé, od výsledku třetí atd.), * a /.

(= x y) porovná dvě čísla, vrátí t pokud jsou stejná, nil pokud nejsou. Analogicky <, >, <=, >= a <>.

(eq x y) vrátí symbol t, pokud jak x, tak y ukazují na tentýž objekt, jinak nil. Pozor, to, že dva objekty stejně vypadají (například jsou-li to dva seznamy se stejným obsahem), ještě nemusí znamenat, že jsou opravdu stejné. Každému číslu odpovídá vždy právě jeden objekt, takže se pro čísla eq chová přesně jako =.

(not x) vrátí t pokud x je nil, jinak nil.

(block x …) vrátí poslední ze svých argumentů

(cons x y) vrátí odkaz na nově vyrobený pár, jehož první složkou bude x a druhou y

(list x …) vrátí odkaz na nově vyrobený seznam obsahující zadané prvky

(geta x) vrátí složku a páru x, analogicky getb

(seta x y) nastaví složku a páru x na y, analogicky setb

(get s) vrátí, na co ukazuje symbol s. Pokud na nic neukazoval, dojde k běhové chybě.

(defined? s) vrátí t, pokud symbol s na něco ukazuje, jinak nil

(set s x) nastaví symbol s, aby ukazoval na objekt x

(number? x) vrátí t, pokud x je číslo, jinak nil. Obdobné funkce existují i pro ostatní typy: pair?, symbol?, nil? a primitive?

(eval x) seznam x vyhodnotí podle popsaných vyhodnocovacích pravidel. Umožňuje za běhu programu vytvořit funkci a pak ji provést.

(if c t f) je speciální forma sloužící k větvení výpočtu. Nejprve vyhodnotí c, pokud vyjde nil, vyhodnotí f a vrátí jeho výsledek, jinak vyhodnotí t a vrátí jeho výsledek.

(and x…) je speciální forma sloužící jako booleovské and. Vyhodnocuje se tak, že se nejprve vyhodnotí první argument, je-li nil, skončí vyhodnocování celého andu s výsledkem nil, jinak se pokračuje dalším argumentem ve stejném duchu. Pokud ani poslední argument není nil, vrátí se jeho hodnota jako výsledek.

(or x…) je obdobná speciální forma, tentokráte fungující jako logický součet. Opět se postupně vyhodnocují argumenty a vrací se první výsledek, který není nil, pokud žádný takový není, vrátí se nil.

(quote x) je speciální forma, která vrátí svůj první argument. Často se používá k zamezení vyhodnocení nějakého argumentu (uvědomte si, že argumenty speciálních forem se nevyhodnocují, takže uvedete-li před nějaký argument funkce volání quote, jediným důsledkem je, že argument „propadne“ skrz quote nezměněný a nevyhodnocený. Například výsledkem (quote (1 2)) je seznam (1 2). Mezi list a quote je jeden podstatný rozdíl: list vám dá pokaždé nový seznam, kdežto quote vrací odkaz na stále tentýž. Výrazy typu (quote (...)) lze rovněž zkracovat jako '(...).

(define (f a…) y…) je zkratka, která ušetří spoustu práce při jinak zdlouhavém definování funkcí. Nadefinuje funkci f s parametry a… a tělem y, jinými slovy sestrojí seznam (lambda (a…) y…) a přiřadí symbolu f odkaz na tento seznam. Pokud použijete define se symbolem místo seznamu jako druhým parametrem, výsledkem bude pouze nastavení tohoto symbolu, aby ukazoval na objekt y (jinými slovy define pak bude fungovat stejně jako set, pouze bude své parametry automaticky quotovat).

(let ((l1 v1) (l2 v2)…) x…) je speciální forma, která nejprve uloží obsah symbolů l1, l2 atd., načež začne vyhodnocovat výrazy v1, v2 atd. a jejich výsledky přiřazovat těmto symbolům. Poté vyhodnotí posloupnost výrazů x… a nakonec obnoví původní význam symbolů a vrátí jako výsledek hodnotu posledního z uvedených výrazů. Tato lokální definice symbolů se často používá podobně jako lokální proměnné v procedurálních jazycích, pouze je nutné si dát pozor na to, že pomocí let symbolům přiřazené objekty jsou viditelné i ve funkcích zevnitř let zavolaných.

A nyní si na jednoduchém příkladu ukážeme, jak v Ksp-Lispu něco jednoduchého naprogramovat – bude to funkce length, jejíž hodnotou bude délka zadaného seznamu:

(define (length x)
  (if x
    (+ 1 (length (getb x)))
    0)
)
Délku počítáme rekurzivně: nejprve otestujeme, zda je seznam neprázdný (podmínka u if je nesplněna jen tehdy, je-li x objekt nil), pokud ano, vrátíme o jedničku zvětšenou délku jeho zbytku (bez prvního prvku), jinak vrátíme nulu jakožto délku prázdného seznamu.

Naším druhým příkladem bude funkce reverse, která pro zadaný seznam vrátí jiný seznam, jenž bude obsahovat tytéž prvky v opačném pořadí (bylo by také možné použitím seta a setb změnit pořadí prvků v seznamu původním, ale to my nechceme):

(define (rev2 x y)
  (if x
    (rev2 (getb x)
          (cons (geta x) y))
    y)
)
(define (reverse x)
  (rev2 x nil)
)
V řešení jsme si nadefinovali obecnější funkci rev2, která vrátí seznam, jenž vznikne připojením seznamu y za obrácení seznamu x. Taková funkce se dá snadno naprogramovat rekurzivně a reverse je vlastně rev2 s y=nil.

Soutěžní úlohy: Naprogramujte v Ksp-Lispu:

Pokud si své programy chcete vyzkoušet, můžete si stáhnout interpret Ksp-Lispu (tar, ZIP).

Řešení