Programovací jazyk F#, PRG049

Obsah semináře

Cílem semináře je zjistit, co to znamená programovat funkcionálně, jaké to přináší výhody a kdy se vyplatí to dělat. Nás konkrétně bude zajímat programovací jazyk F#, funkcionální jazyk z rodiny jazyků ML, který je součástí Visual Studia 2010 (ale lze ho použít i na Monu).

Seznámíme se s řadou technik funkcionálního programování, od základních až po pokročilé, a ukážeme si, jak nám mohou pomoci s vytvářením znovupoužitelného kódu nebo s s paralelním a asynchronním programováním.

Seminář nepožaduje žádné předchozí znalosti funkcionálního programování. Na druhou stranu je velmi dobré mít zkušenosti s programováním jako takovým.

Doba a místo konání

Seminář se koná v pondělí ve 12:20 na Malé Straně, v učebně SU1. První přednáška se koná až v pondělí 11. října.

Zápočet

Pro získání zápočtu je třeba získat 30 bodů. Body je možné získávat za domácí úkoly (těch bude vypsáno alespoň za 80 bodů), za referáty (předpokládám tak jeden dva) a za zápočtový program (je možné se domluvit na obtížnosti 1 až 30 bodů, pro zájemce i více :). Body se sčítají.

Kde sehnat F#

Překladač F# je součástí Visual Studia 2010, na které mají studenti MFF zdarma licenci (stačí zde vybrat "Log In" a použít přístupové údaje z CAS).

Případně je možné nainstalovat si z této stránky samotný F# 2.0. Pokud k němu chcete vývojové prostředí, ale nechcete celé Visual Studio, nainstalujte si ze stejné stránky nejprve Visual Studio 2010 Shell.

Mono

Překladač F# funguje výborně i s Mono. V tom případě vám stačí stáhnout si z této stránky F# 2.0 (zip) a rozbalit ho. Používám úspěšně Mono 2.4.3 a 2.6.7.

F# Powerpack

Tvůrci jazyka F# uvolnili i sadu dalších knihoven pro F# jako F# Powerpack. Z něj doporučuji hlavně fslex, fsyacc a fshtmldoc. Použité knihovny lze staticky zakompilovat do výsledných binárek, takže se nemusíte bát problémů s distribucí. Ve svých úkolech můžete tuto knihovnu používat.

Obsahy přednášek

11. října: seznámení s konceptem fukcionálního programování. Základní typy jazyka F#, let deklarace, vytvoření funkce fsharp01.fs, fsharp01.ps, fsharp01.pdf.
18. října: deklarace hodnot (a tedy i funkcí), rekurze, operátory. Deklarace typů (typová synonyma, výčty, recordy a algebraické datové typy), předdefinované typy option<'a> a list<'a> fsharp02.fs, fsharp02.ps, fsharp02.pdf.
25. října: přednáška odpadla. Místo ní je zde studijní text: fsharp03.fs, fsharp03.ps, fsharp03.pdf.
1. listopadu: přednáška odpadla. Místo ní je zde studijní text: fsharp04.fs, fsharp04.ps, fsharp04.pdf.
8. listopadu: složitost appendu a reasociace, procházení sekvencí, side effekty, skutečné proměnné (mutable) a odkazy, pole, value restriction: fsharp05.fs, fsharp05.ps, fsharp05.pdf.
15. listopadu: dokončení povídání o value restriction a typových funkcích, reasociace pomocí funkcí, rekurzivní datové typy a funkce, výjimky, líné seznamy: fsharp06.fs, fsharp06.ps, fsharp06.pdf.
22. listopadu: líné vyhodnocování, vlastní patterny pro pattern matching: fsharp07.fs, fsharp07.ps, fsharp07.pdf.
29. listopadu: moduly a signatury, viditelnost, parsování pomocí LALR(1) parserů a nástroje fslex a fsyacc: fsharp08.fs, fsharp08.ps, fsharp08.pdf.
6. prosince: objekty: fsharp09.fs, fsharp09.ps, fsharp09.pdf.
13. prosince: pokračování objektů, statically resolved types a eventy: fsharp10.fs, fsharp10.ps, fsharp10.pdf.
20. prosince: vlákna a threadpool v .NETu, asynchronní programování v .NETu, asynchronní programování v F#, typ Async<'T>, začátek computation expressions: fsharp11.fs, fsharp11.ps, fsharp11.pdf.
3. ledna: pokračování s computation expressions -- monády pfor, option, seq, parser, async: fsharp12.fs, fsharp12.ps, fsharp12.pdf.
10. ledna: Software transaction memory, MailboxProcessor, Continuation passing style fsharp13.fs, fsharp13.ps, fsharp13.pdf.

Domácí úkoly (29. 06. 2011)

Prosím posílejte úkoly jako textové přílohy mailu, nezabalujte je. Lépe se mi opravují.

Zadání domácích úkolů se může lehce změnit oproti tomu, které jsem zadával na hodině (když udělám nějakou chybu). Platná verze je vždy ta uvedená zde.

U některých úkolů je uvedená časová složitost potřebná k získání plného počtu bodů. Můžete ale poslat libovolné řešení s polynomiální složitostí, nějaké body za něj budou vždy. Můžete klidně poslat nejprve pomalé řešení a později poslat vylepšenou verzi.

Datum
cvičení ID Body Popis
25. října 2010 Úkoly můžete odevzdávat do 08. listopadu 2010, 12:20.
sum 0.5 Napište funkci sum : list<int> -> int, která sečte daný seznam intů a potřebuje k tomu jen konstantně prostoru na zásobníku.
rev 1 Napište funkci rev : list<'a> -> list<'a>, která vrátí daný seznam v opačném pořadí a potřebuje k tomu jen konstantně prostoru na zásobníku.
flatten 1 Napište funkci flatten : Tree<'a> -> list<'a>, která vrátí prvky daného stromu v pořadí od nejlevějšího po nejpravější.
25. října 2010 Úkoly můžete odevzdávat do 22. listopadu 2010, 12:20.
235 2.5 Napište funkci seq235 : seq<bigint>, která vrátí sekvenci všech rostoucích čísel tvaru 2ⁱ3^j5^k. Pár prvních prvků je 1, 2, 3, 4, 5, 6, 8, ....
Plný počet bodů jenom za řešení, které potřebuje konstantní čas k nalezení dalšího prvku posloupnosti.
minfree 2.5 Napište funkci minfree :: list<uint> -> uint, která dostane seznam neopakujících se nezáporných čísel a vrátí nejmenší, které v tom seznamu není. Pokud chápete daný seznam jako nějaké použité identifikátory, minfree vrátí první nepoužitý.
Plný počet bodů jenom za řešení v lineárním čase bez použití pole, mutable či odkazů.
01. listopadu 2010 Úkoly můžete odevzdávat do 15. listopadu 2010, 12:20.
fldrev 0.5 Napište funkci List.rev pomocí nějaké funkce z rodiny fold.
fldchs 0.5 Napište funkci List.choose pomocí nějaké funkce z rodiny fold.
fldcol 0.5 Napište funkci List.collect pomocí nějaké funkce z rodiny fold. Nepoužívejte jiné funkce z modulu List.
fld2fld 1.5 Napište funkci fold pomocí List.foldBack a naopak funkci foldBack pomocí List.fold. Nepoužívejte další funkce z modulu List ani Array. Můžete použít fun v definici funkce pro List.foldBack. Mělo by to vypadat jako let fold f z xs = List.foldBack (fun ...) .... Opravdu to jde :-)
01. listopadu 2010 Úkoly můžete odevzdávat do 29. listopadu 2010, 12:20.
ssum 2 Napište funkci ssum : int -> list<int> -> option<list<int>>, která zjistí, ze v daném seznamu nachází souvislý úsek daného součtu. Pokud ano, vraťte ho. Plný počet bodů za složitost Ο(N log N).
clen 1.5 Vytvořte funkci clen : seq<int> -> int, která dostane nekonečnou sekvenci. Tato sekvence má následující vlastnost: pokud za prvkem a jednou následoval prvek b, za každým prvkem a následuje prvek b. Jinak řečeno, prvek je vždy jednoznačne určen předchozím.
Protože je sekvence nekonečná a int ne, musí být od nějaké doby periodická. Vaším úkolem je pomocí konstantní paměti spočítat délku této periody.
Příklad: délka periody sekvence {1; 2; 3; 4; 3; 4; 3; ... } je 2.
coll 1 Tuto úlohu můžete řešit až tehdy, když vyřešíte clen.
Vytvořte funkci coll : (int -> int) -> int * int, která dostane deterministickou funkci f, o které ví, že nekonečná posloupnost f(0), f(f(0)), f(f(f(0))),... neobsahuje nulu. (Tedy sekvence Seq.initInfinite f by splňovala podmínky zadání úlohy clen.)
Pomocí konstantní paměti vraťte dvě různé hodnoty x a y, že f(x) = f(y).
Varianta tohoto se někdy používá pro hledání kolizí hashovacích funkcí.
08. listopadu 2010 Úkoly můžete odevzdávat do 22. listopadu 2010, 12:20.
mintree 1 Předpokládejme typ type tree<'a> = Leaf of 'a | Node of tree<'a> * tree<'a>. Napište funkci mintree : list<'a> -> tree<a'>, která dostane seznam prvků a vytvoří z nich strom obsahující dané prvky jako listy v pořadí zleva doprava, čili aby platilo xs = (xs |> mintree |> flatten). Tento strom navíc musí mít co nejmenší hloubku. Nepoužívejte při řešení žádná pole ani mutable. Plný počet bodů za řešení v Ο(N).
huff 1.5 Předpokládejme typ type tree<'a> = Leaf of 'a | Node of tree<'a> * tree<'a>. Napište funkci huff : list<tree<'a>> -> tree<'a>, která dostane seznam stromů a vytvoří z nich (spojováním pomocí Node) jeden strom (dané podstromy může obsahovat v libovolném pořadí). Tento strom musí mít minimální možnou hloubku. Plný počet bodů za složitost Ο(N log N + S), kde N je počet stromů na vstupu a S je součet prvků v těchto stromech.
Hint: Vždy chcete spojit přes Node dva stromy nejmenší hloubky.
bala 1 Napište funkci balanced : list<bool> -> list<bool>, která dostane seznam boolů a vrátí nejdelší souvislou podposloupnost, ve kterých je stejně hodnot true i false. Mělo by fungovat v lineárním čase.
Za řešení bez polí a mutable nabízím další bod.
08. listopadu 2010 Úkoly můžete odevzdávat do 06. prosince 2010, 12:20.
lcs 2.5 Napište funkci lcs : list<'a> -> list<'a> -> list<'a>, která vrátí nejdelší společný (ne nutně souvislý) podseznam dvou daných seznamů. Složitost pro plný počet bodů je Ο(délka prvního seznamu * délka druhého seznamu). Používejte jenom seznamy, žádné mutable, odkazy ani pole.
t2min 3 Předpokládejme typ type tree<'a> = Leaf of 'a | Node of tree<'a> * tree<'a>. Napište funkci t2min : list<tree<'a>> -> tree<'a>, která dostane seznam stromů a vytvoří z nich (spojováním pomocí Node) jeden strom, který obsahuje dané podstromy v zadaném pořadí, čili aby platilo List.collect flatten xs = flatten (t2min xs). Tento strom navíc musí mít co nejmenší hloubku. Nepoužívejte při řešení žádná pole ani mutable.
Jen pro ty, co se nudí.
15. listopadu 2010 Úkoly můžete odevzdávat do 29. listopadu 2010, 12:20.
saddle 2 Naprogramujte funkci saddle : (z : int) -> (f : int -> int -> int) -> list<int * int>. Funkce saddle dostane funkci f, která souřadnicím x:int a y:int přiřazuje nějakou hodnotu typu int a víte, že tato funkce je ostře rostoucí v obou souřadnicích, tj. x < X => f x y < f X y a také y < Y => f x y < f x Y. Kromě této funkce dostanete hodnotu z : int a máte vrátit seznam všech dvojic x, y, že x≥0, y≥0 a f x y = z.
maxpath 2 Mějme obecné stromy typu type tree<'a> = Nil | Node of 'a * list<tree<'a>>. Napište funkci maxpath : tree<'a> -> list<'a>, která dostane strom a vrátí jednu z nejdelších cest v tomto stromě. Cestu vraťte jako seznam hodnot typu 'a.
15. listopadu 2010 Úkoly můžete odevzdávat do 13. prosince 2010, 12:20.
zs 1-4 Mějme čísla x₁, x₂, ..., x_N a definujme hodnoty z_i jako součin všech x_j kromě x_i, takže z_i = Π_j<>i x_j. Vaším úkolem bude spočítat všechny z_i, přičemž nesmíte používat žádné jiné operace než násobení (speciálně ne dělení). Napište tedy funkci zs : int [] -> seq<int>. Tato funkce dostane na vstupu hodnoty x_i a vytvoří sekvenci, která vrátí postupně hodnoty z₁, z₂, ..., z_N. Vaším úkolem je co nejvíce šetřit časem a pamětí, přičemž uvažujeme časovou a paměťovou složitost pro spočtení všech z_i.
Čas Ο(N) a paměť Ο(N): 1 bod
Čas Ο(N) a paměť Ο(√N): +1 bod
Čas Ο(N log N) a paměť Ο(log N): +2 body
Řešení můžete poslat několik a body se sčítají podle toho, co splníte. Všimněte si, že pokud splníte druhou variantu, splnili jste automaticky i první variantu.
15. listopadu 2010 Úkoly můžete odevzdávat do 30. září 2011, 23:59.
diff 8 Napište program, který se bude chovat jako diff -u. Tedy program dostane na příkazové řádce jména dvou souborů. Jméno jednoho z těchto souborů může být -, což znamená standardní vstup. Na standardní výstup vypište diff těchto souborů ve formátu unified diff. Stejně jako diff -u je velikost kontextu 3, ale pokud uživatel zadá na začátku příkazové řádky -U num, změní se velikost kontextu na num (tedy -U 3 je implicitní). Složitost musí být Ο(počet řádek v obou souborech * velikost diffu), paměťová stačí Ο(velikost diffu na druhou), viz tento článek.
22. listopadu 2010 Úkoly můžete odevzdávat do 06. prosince 2010, 12:20.
demorse 2 Napište funkci demorse : string -> option<string>, která dekóduje vstup v morseovce, pokud je korektní. Tečka je tečka, čárka je pomlčka, oddělovač znaků je svislítko a oddělovač slov jsou dvě svislítka. Ostatní znaky ignorujte. Plný počet bodů za složitost lineární s velikostí vstupu, tj. každou tečku a čárku ze vstupu byste měli zpracovat jednou.
primes 2.5 Napište funkci primes : seq<int>, která vrací sekvenci všech prvočísel. Plný počet bodů za složitost Ο(N log log N) pro získání prvočísel mezi 1..N, což je shodou okolností složitost Eratosthenova síta :–) Jen na rozdíl od Eratosthenova síta nevíte předem hranici, do které budete chtít prvocísla najít.
Za řešení v čase Ο(N √N) je jeden bod.
cenzor 2.5 Napište funkci cenzor : string -> string -> string, která ze druhého zadaného slova vymaže všechny výskyty prvního slova. Pozor na to, že smazáním jednoho slova může vzniknout další zakázané slovo, třeba cenzor "bug" "bububuggg" = "". Nepoužívejte knihovní funkce (jako třeba String.IndexOf), mělo by to být o implementaci vyhledávacího automatu. Plný počet bodů za lineární řešení.
Hint: KMP (http://mj.ucw.cz/vyuka/0708/ads2/ads2.ps strana 26) a po smazání slov se "vrátit" o dost zpět.
22. listopadu 2010 Úkoly můžete odevzdávat do 20. prosince 2010, 12:20.
maxima 2.5 Napište funkci maxima : int -> list<'a> -> list<'a> when 'a : comparable, která dostane na vstupu číslo k a seznam x₁, x₂, ..., x_N. Vytvořte seznam délky N-k+1, jehož i-tý prvek je maximum z prvků x_i, x_i+1, ..., x_i+k-1. Řečeno slovy, spočtěte maxima všech souvislých úseků délky k. Plný počet bodů za řešení v lineárním čase.
useky 3 Napište funkci useky : list<'a> -> list<list<'a>> when 'a : comparable, která dostane na vstupu seznam, který rozloží na co nejmenší počet ostře rostoucích (ne nutně souvislých) podseznamů. Jinak řečeno, rozdělte prvky vstupního seznamu na co nejméně skupin, aby prvky v každé skupině byly ostře rostoucí. Plný počet bodů za řešení v čase Ο(N log N).
Příklad: useky [1..4] = [[1..4]]; useky [4..1] = [[4]; [3]; [2]; [1]]; useky [1; 1; 1] = [[1]; [1]; [1]]
29. listopadu 2010 Úkoly můžete odevzdávat do 13. prosince 2010, 12:20.
wild 2 Napište funkci wild : string -> string -> bool, která dostane na vstupu wildcard a text a odpoví, zda celý tento text danému wildcardu odpovídá. Wildcard může obsahovat znaky:

? – odpovídá právě jednomu znaku
* – odpovídá libovolně mnoha znakům
cokoliv jiného – odpovídá právě tomuto znaku.
Tedy wildcardu a?b* odpovídá acb, aabbb, ale ne ab ani aaab. Plný počet bodů za řešení v čase Ο(délka wildcardu * délka textu).
29. listopadu 2010 Úkoly můžete odevzdávat do 20. prosince 2010, 12:20.
calc1 1 Napište funkci calc : string -> option<float>, která vyhodnotí dodaný aritmetický výraz a vrátí výsledek, pokud bylo vše v pořádku. Ve výrazu lze používat operátory + - * / ^ ( ) s běžnými prioritami, a desetinná čísla typu float. Mezerové znaky ignorujte. Plný počet bodů za řešení v lineárním čase.
calc2 1 Tento úkol můžete řešit až po vyřešení calc1. Ve výrazu se mohou být i následující funkce: abs() sqrt() sin() cos() min() max(), přičemž funkce min a max mohou dostat libovolný nenulový počet argumentů, které jsou odděleny čárkami. Tedy například min(abs((0 - 3) ^ 5), sin(4.4), sqrt(123)).
calc3 1 Tento úkol můžete řešit až po vyřešení calc2. Před výrazem k vyhodnocení může být ještě několik přiřazení, každé ukončené středníkem. Přiřazení vypadá jako proměnná = výraz;, přičemž v následujících výrazech můžete používat výraz proměnná. Funguje to tedy podobně jako let proměnná = výraz. Příklad: x = 3; x = x + 1; y = abs(x); z = x * y 3; x + y + z
calc4 1 Tento úkol můžete řešit až po vyřešení calc3. Kromě proměnných můžete definovat i funkce, tj. přiřazení může vypadat jako funkce a1 a2 ... = výraz;. Tím definujete funkci s daným počtem argumentů a tedy výraz je může používat. Navíc následující výrazy mohou používat i funkci funkce se správným počtem argumentů. Chová se to tedy podobně jako let funkce a1 a2 ... = výraz. Příklad: x = 3; f y = x + y; g a b c = f(a) + f(b) + f(c); h x = g(x, f(x), f(f(x))); h 5
29. listopadu 2010 Úkoly můžete odevzdávat do 03. ledna 2011, 12:20.
spacify 2.5 Napište funkci spacify : (maxlen : int) -> (isWord : seq<char> -> bool) -> list<char> -> list<list<char>>. Tato funkce dostane na vstupu text bez mezer a jejím úkolem je přidat do textu mezery, aby všechna takováto vzniklá slova byla smysluplná. Dostanete tedy ještě maximální délku slova maxlen a funkci isWord, která pro slovo (sekvenci znaků) určí, zda je to smysluplné slovo jazyka. Pokud je takových rozdělení na slova víc, najděte to, které používá co nejméně slov. Plný počet bodů za složitost Ο(délka textu * maximální délka slova * složitost isWord).
29. listopadu 2010 Úkoly můžete odevzdávat do 30. září 2011, 23:59.
logo 8 Naimplementujte simulátor loga podle tohoto zadání, a to včetně všech rozšíření. Pokud chcete, můžete podporovat hodnoty typu float místo int, dává to větší smysl :–) Pro testování můžete použít tato testovací data, jsou rozdělena podle jednotlivých rozšíření, ale vám musí fungovat stejně všechno.
logosrv 2 Pokud jste vyřešili předchozí úlohu, naimplementujte k ní http rozhraní. Tedy naimplementujte malý standalone http server (nejspíš běžící na uživatelsky definovaném portu), který zobrazuje stránku, na které je možné zadat kód pro Krunimíra a počet tahů. Po odeslání zobrazte navíc i obrázek s Krunimírovy tahy (nikam ho neukládejte, generujte ho on-the-fly).
13. prosince 2010 Úkoly můžete odevzdávat do 20. prosince 2010, 12:20.
cops 1.5 Ulice města si představte jako strom. Chcete každou ulici nechat hlídat policií. K tomu účelu na některé křižovatky (tj. vrcholy stromu) umístíte policisty. Ulice je hlídaná, když je policista umístěn na alespoň jednom konci této ulice. Protože je rozpočet policie tradičně mizerný, je třeba zaměstnat co nejméně policistů.
Napište metodu cops : tree<'a> -> list<'a>, která dostane strom města a vrátí nejmenší množinu vrcholů takovou, že pro každou ulici je v této množině alespoň jeden její konec. Strom je definován jako type tree<'a> = Node of 'a * list<tree<'a>>.
median 2 Napište funkci median : list<'a> -> 'a when 'a : comparison, která vrací medián dané posloupnosti. Za Ο(N) v nejhorším případě jsou dva body, za Ο(N) v průměru je bod.
Hint: http://mj.ucw.cz/vyuka/0607/ads1/ads.ps strana 14.
13. prosince 2010 Úkoly můžete odevzdávat do 03. ledna 2011, 12:20.
tiso 2 Stromy jsou definované jako type BinTree<'a> = Nil | Node of BinTree<'a> * 'a * BinTree<'a>. Napište funkci, která dostane dva stromy, a zjistí, jestli jsou stejné, pokud nezáleží na pořadí synů. Tedy Node (Nil, 1, Node (Nil, 2, Nil)) je až na pořadí synů shodný s Node (Node (Nil, 2, Nil), 1, Nil). Plný počet bodů za řešení rychlejší než Ο(N²), kde N je počet vrcholů většího ze stromů.
blud 2 Na standardním vstupu dostanete bludiště. Všechny řádky standardního vstupu mají stejnou délku a obsahují znaky

. – volné pole
X – zeď
@ – hrdina, je v bludišti právě jeden
$ – poklad, je v bludišti právě jeden
Vaším úkolem je najít a zobrazit nejkratší cestu hrdiny k pokladu (vypište bludiště ve stejném formátu, a políčka na nejkratší cestě vypište jako *), nebo říct, že neexistuje. Plný počet bodů za řešení v lineárním čase.
krumpac 1.5 Tato úloha rozšiřuje úlohu předchozí. Na vstupu je bludiště zadané ve stejném formátu. Hrdina si ale do bludiště přinesl krumpáč a v případě nouze může prokopat libovolnou stěnu. To je ale velmi náročný úkol – najděte proto cestu od hrdiny k pokladu, na které je třeba rozbít krumpáčem co nejméně stěn. Ze všech takových cest najděte tu nejkratší. Vypište libovolnou takovou cestu, políčka na ní vypište jako * a rozbité zdi jako #. Plný počet bodů za řešení v lineárním čase.
13. prosince 2010 Úkoly můžete odevzdávat do 30. září 2011, 23:59.
karel 6 Napište simulátor robota Karla. Na začátku stojí robot Karel na nějakém políčku šachovnice o rozměrech 10 x 10. Některá políčka šachovnice jsou volná, na jiných jsou zdi.
Napište program, který očekává na příkazové řádce jména dvou souborů – první obsahuje šachovnici, ta se skládá z deseti řádek, každá o deseti znacích, buď . (volné políčko), _ (volné políčko se značkou) nebo X (zeď). Na právě jednom políčku je robot Karel, jako znak >, <, v, ^, který určuje jeho orientaci. Druhý zadaný soubor obsahuje program pro Karla v této syntaxi. Pokud je vstup v pořádku, proveďte proceduru main, která musí být definována. Odsimulujte program pro Karla a na standardní výstup vypište šachovnici po ukončení procedury main. Pokud výpočet trvá moc dlouho (například milion kroků), ukončete ho a vypište o tom zprávu.
20. prosince 2010 Úkoly můžete odevzdávat do 03. ledna 2011, 12:20.
zisk 2 Napište funkci zisk : list<int> -> list<int>, která dostane seznam celých čísel a najde nejdelší souvislý úsek, který má nezáporný součet (nejdelší období bez ztrát). Plný počet bodů za řešení v lineárním čase.
grep 1.5 Napište program grep, který dostane na standardním vstupu jako parametr regulérní výraz. Dále načítá standardní vstup a na výstup vypíše jenom řádky, které tomuto regulérnímu výrazu vyhovují. Pokud je parametru s regulérním výrazem předchází parametr -v, vypište naopak řádky, které danému výrazu nevyhovují.
Hint: http://msdn.microsoft.com/en-us/library/system.text.regularexpressions.regex.aspx
20. prosince 2010 Úkoly můžete odevzdávat do 30. září 2011, 23:59.
chats 3 Napište jednoduchý chat server. Server poslouchá na (na příkazové řádce) zadaném portu. Připojit se může libovolný počet lidí. Když se někdo připojí, tak na první řádce napíše svůj nickname. Každá dalšá řádka od něj se pošle všem ostatním připojeným (těm, kteří už poslali nickname) ve formátu "nickname: řádka".
chatc 2 Napište jednoduchý konzolový chat klient. Klient se připojí na (na příkazové řádce) zadaný port. Jednotlivé zadané řádky se pošlou serveru. Kdykoliv přijde řádka od serveru, vypíše se "nad" rozepsanou editovanou řádku.
color6 1.5 Napište funkci color6 : list<int>[] -> int[], která dostane rovinný graf a vrátí jeho obarvení šesti barvami (1..6). Graf na vstupu dostanete jako pole vrcholů, každý vrchol je reprezentován jako seznam jeho sousedů (čísluje se od nuly). Obarvení vraťte jako pole s prvky 1..6. Plný počet bodů za řešení v lineárním čase.
color5 2.5 Napište funkci color5 : list<int>[] -> int[], která má stejný vstup jako color6, jenom počítá obarvení rovinného grafu pěti barvami. Plný počet bodů za složitost lepší než Ο(N²), za Ο(N²) je 1.5 bodu.
03. ledna 2011 Úkoly můžete odevzdávat do 30. září 2011, 23:59.
withlog 2.5 Navrhněte výpočet, který si kromě výsledku pamatuje ještě log průběhu výpočtu:

vytvořte typ WithLog<'a>, který reprezentuje výpočet vracející typ 'a, zároveň s jeho logem,
vytvořte metodu res : WithLog<'a> -> 'a, která extrahuje výsledek výpočtu,
vytvořte metodu log : WithLog<'a> -> list<string>, která extrahuje log výpočtu (jednotlivé zprávy v pořadí, v jakém byly do logu přidány),
vytvořte withlog, která definuje computation expression pracující s typem WithLog<'a>, definujte Zero, Return a Bind,
vytvořte metodu write : string -> WithLog<unit>, která loguje daný řetězec. Používá se uvnitř computation expression jako do! write "message".
Mělo by tedy fungovat
let compute = withlog { do! write "a" do! write "b" return 5 }
přičemž res compute = 5 a log compute = ["a"; "b"]. Pozor na to, že Bind by měl fungovat v konstantním čase a že s WithLog<'a> lze dál pracovat v několika pokračování, takže použít StringBuilder je špatně.
withenv 2.5 Navrhněte výpočet, který si udržuje environment (pro zjednodušení je environment mapování řetězce na řetězec):

vytvořte typ Env, který reprezentuje environment,
vytvořte typ WithEnv<'a>, který reprezentuje výpočet, který si udržuje environment. Pozor na to, že výpočet může environment i měnit,
vytvořte metodu run : seq<string*string> -> WithEnv<'a> -> 'a, která spustí výpočet s daným environmentem (zadaným jako posloupnost klíč-hodnota),
vytvořte withenv, která definuje computation expression pracující s typem WithEnv<'a>, definujte Zero, Return a Bind,
vytvořte metodu get : string -> WithEnv<string>, která vrátí z environmentu hodnotu s daným klíčem, nebo null, pokud neexistuje. Používá se uvnitř computation expression jako let! value = get "name",
vytvořte metodu set : string -> string -> WithEnv<unit>, která do environmentu zapíše pod daný klíč danou hodnotu (pokud už existuje, přepište ji). Používá se uvnitř computation expression jako do! set "name" "Petr".
Mělo by tedy fungovat
let compute = withenv { let! oldname = get "name" do! set "name" "Jarda" return oldname } printfn "%A" (run ["name", "Petr"] compute)
a po spuštění vypsat "Petr. Pozor na to, že s WithEnv<'a> lze dál pracovat v několika pokračování, které každé může jinak měnit Env.
stoppable 2.5 Navrhněte výpočet, který je možné v průběhu přerušit:

vytvořte typ Stoppable<'a>, který reprezentuje výpočet vracející typ 'a, který ale může být přerušen,
vytvořte metodu res : Stoppable<'a> -> option<'a>, která vrátí výsledek, pokud výpočet není přerušen,
vytvořte metodu step : Stoppable<'a> -> Stoppable<'a>, která pokud dostane přerušený výpočet, provádí ho do dalšího přerušení,
vytvořte stoppable, která definuje computation expression pracující s typem Stoppable<'a>, definujte Zero, Return a Bind,
vytvořte metodu stop : Stoppable<unit>, která přeruší probíhající výpočet. Používá se uvnitř computation expression jako do! stop
Mělo by tedy fungovat
let compute = stoppable { printfn "Pred" do! stop printfn "Po" return 5 } printfn "%A" (res compute) printfn "%A" (res (step compute))
a po spuštění vypsat
Pred <null> Po Some 5

sudoku 4 Napište sudoku solver. Na standardním vstupu dostane popis sudoku – všímejte si jenom znaků . (tečka) a 0-9, ostatní ignorujte (včetně znaků nové řádky) – tím budete umět načíst skoro všechny používané formáty. Dané sudoku vyřešte a vypište vyřešené na standardní výstup. Plný počet bodů, pokud to na většinu sudoku bude fungovat v rozumném čase (v řádu vteřin).
10. ledna 2011 Úkoly můžete odevzdávat do 30. září 2011, 23:59.
par 2.5 Navrhněte výpočet, který bude paralelně vyhodnocovat alternativní větve v různých vláknech:

vytvořte typ Par<'a>, který reprezentuje výpočet, který bude počítat výsledek typu 'a několika alternativními způsoby, a ty se budou provádět paralelně,
vytvořte metodu run : Par<'a> -> 'a, která spustí výpočet, alternativní způsoby budou prováděny paralelně,
vytvořte par, která definuje computation expression pracující s typem Par<'a>, definujte Zero, Return, Bind a Combine. Metoda Combine funguje tak, že dvě alternativy vyhodnocuje paralelně.
Mělo by tedy fungovat
let twoalts = par { return (List.length [1..1000000]) return (Seq.length <| Seq.collect (fun i -> {1..1000}) {1..1000}) } let fouralts = par { return! twoalts return! twoalts } run fouralts
přičemž výpočet bude probíhat ve 4 vláknech a které nejdřív skončí, vrátí výsledek, a ostatní vlákna budou ukončena.

Datum cvičení	ID	Body	Popis
25. října 2010	Úkoly můžete odevzdávat do 08. listopadu 2010, 12:20.
sum	0.5	Napište funkci `sum : list<int> -> int`, která sečte daný seznam intů a potřebuje k tomu jen konstantně prostoru na zásobníku.
rev	1	Napište funkci `rev : list<'a> -> list<'a>`, která vrátí daný seznam v opačném pořadí a potřebuje k tomu jen konstantně prostoru na zásobníku.
flatten	1	Napište funkci `flatten : Tree<'a> -> list<'a>`, která vrátí prvky daného stromu v pořadí od nejlevějšího po nejpravější.
25. října 2010	Úkoly můžete odevzdávat do 22. listopadu 2010, 12:20.
235	2.5	Napište funkci `seq235 : seq<bigint>`, která vrátí sekvenci všech rostoucích čísel tvaru 2ⁱ3^j5^k. Pár prvních prvků je 1, 2, 3, 4, 5, 6, 8, .... Plný počet bodů jenom za řešení, které potřebuje konstantní čas k nalezení dalšího prvku posloupnosti.
minfree	2.5	Napište funkci `minfree :: list<uint> -> uint`, která dostane seznam neopakujících se nezáporných čísel a vrátí nejmenší, které v tom seznamu není. Pokud chápete daný seznam jako nějaké použité identifikátory, `minfree` vrátí první nepoužitý. Plný počet bodů jenom za řešení v lineárním čase bez použití pole, `mutable` či odkazů.
01. listopadu 2010	Úkoly můžete odevzdávat do 15. listopadu 2010, 12:20.
fldrev	0.5	Napište funkci `List.rev` pomocí nějaké funkce z rodiny `fold`.
fldchs	0.5	Napište funkci `List.choose` pomocí nějaké funkce z rodiny `fold`.
fldcol	0.5	Napište funkci `List.collect` pomocí nějaké funkce z rodiny `fold`. Nepoužívejte jiné funkce z modulu `List`.
fld2fld	1.5	Napište funkci `fold` pomocí `List.foldBack` a naopak funkci `foldBack` pomocí `List.fold`. Nepoužívejte další funkce z modulu `List` ani `Array`. Můžete použít `fun` v definici funkce pro `List.foldBack`. Mělo by to vypadat jako `let fold f z xs = List.foldBack (fun ...) ...`. Opravdu to jde :-)
01. listopadu 2010	Úkoly můžete odevzdávat do 29. listopadu 2010, 12:20.
ssum	2	Napište funkci `ssum : int -> list<int> -> option<list<int>>`, která zjistí, ze v daném seznamu nachází souvislý úsek daného součtu. Pokud ano, vraťte ho. Plný počet bodů za složitost Ο(N log N).
clen	1.5	Vytvořte funkci `clen : seq<int> -> int`, která dostane nekonečnou sekvenci. Tato sekvence má následující vlastnost: pokud za prvkem a jednou následoval prvek b, za každým prvkem a následuje prvek b. Jinak řečeno, prvek je vždy jednoznačne určen předchozím. Protože je sekvence nekonečná a `int` ne, musí být od nějaké doby periodická. Vaším úkolem je pomocí konstantní paměti spočítat délku této periody. `Příklad:` délka periody sekvence {1; 2; 3; 4; 3; 4; 3; ... } je 2.
coll	1	Tuto úlohu můžete řešit až tehdy, když vyřešíte `clen`. Vytvořte funkci `coll : (int -> int) -> int * int`, která dostane deterministickou funkci f, o které ví, že nekonečná posloupnost f(0), f(f(0)), f(f(f(0))),... neobsahuje nulu. (Tedy sekvence `Seq.initInfinite f` by splňovala podmínky zadání úlohy `clen`.) Pomocí konstantní paměti vraťte dvě různé hodnoty x a y, že f(x) = f(y). Varianta tohoto se někdy používá pro hledání kolizí hashovacích funkcí.
08. listopadu 2010	Úkoly můžete odevzdávat do 22. listopadu 2010, 12:20.
mintree	1	Předpokládejme typ `type tree<'a> = Leaf of 'a \| Node of tree<'a> * tree<'a>`. Napište funkci `mintree : list<'a> -> tree<a'>`, která dostane seznam prvků a vytvoří z nich strom obsahující dané prvky jako listy v pořadí zleva doprava, čili aby platilo `xs = (xs \|> mintree \|> flatten)`. Tento strom navíc musí mít co nejmenší hloubku. Nepoužívejte při řešení žádná pole ani `mutable`. Plný počet bodů za řešení v Ο(N).
huff	1.5	Předpokládejme typ `type tree<'a> = Leaf of 'a \| Node of tree<'a> * tree<'a>`. Napište funkci `huff : list<tree<'a>> -> tree<'a>`, která dostane seznam stromů a vytvoří z nich (spojováním pomocí `Node`) jeden strom (dané podstromy může obsahovat v libovolném pořadí). Tento strom musí mít minimální možnou hloubku. Plný počet bodů za složitost Ο(N log N + S), kde N je počet stromů na vstupu a S je součet prvků v těchto stromech. Hint: Vždy chcete spojit přes `Node` dva stromy nejmenší hloubky.
bala	1	Napište funkci `balanced : list<bool> -> list<bool>`, která dostane seznam `bool`ů a vrátí nejdelší souvislou podposloupnost, ve kterých je stejně hodnot `true` i `false`. Mělo by fungovat v lineárním čase. Za řešení bez polí a mutable nabízím další bod.
08. listopadu 2010	Úkoly můžete odevzdávat do 06. prosince 2010, 12:20.
lcs	2.5	Napište funkci `lcs : list<'a> -> list<'a> -> list<'a>`, která vrátí nejdelší společný (ne nutně souvislý) podseznam dvou daných seznamů. Složitost pro plný počet bodů je Ο(délka prvního seznamu délka druhého seznamu)*. Používejte jenom seznamy, žádné `mutable`, odkazy ani pole.
t2min	3	Předpokládejme typ `type tree<'a> = Leaf of 'a \| Node of tree<'a> * tree<'a>`. Napište funkci `t2min : list<tree<'a>> -> tree<'a>`, která dostane seznam stromů a vytvoří z nich (spojováním pomocí `Node`) jeden strom, který obsahuje dané podstromy v zadaném pořadí, čili aby platilo `List.collect flatten xs = flatten (t2min xs)`. Tento strom navíc musí mít co nejmenší hloubku. Nepoužívejte při řešení žádná pole ani `mutable`. Jen pro ty, co se nudí.
15. listopadu 2010	Úkoly můžete odevzdávat do 29. listopadu 2010, 12:20.
saddle	2	Naprogramujte funkci `saddle : (z : int) -> (f : int -> int -> int) -> list<int * int>`. Funkce `saddle` dostane funkci f, která souřadnicím `x:int` a `y:int` přiřazuje nějakou hodnotu typu `int` a víte, že tato funkce je ostře rostoucí v obou souřadnicích, tj. x < X => f x y < f X y a také y < Y => f x y < f x Y. Kromě této funkce dostanete hodnotu `z : int` a máte vrátit seznam všech dvojic x, y, že x≥0, y≥0 a f x y = z.
maxpath	2	Mějme obecné stromy typu `type tree<'a> = Nil \| Node of 'a * list<tree<'a>>`. Napište funkci `maxpath : tree<'a> -> list<'a>`, která dostane strom a vrátí jednu z nejdelších cest v tomto stromě. Cestu vraťte jako seznam hodnot typu `'a`.
15. listopadu 2010	Úkoly můžete odevzdávat do 13. prosince 2010, 12:20.
zs	1-4	Mějme čísla x₁, x₂, ..., x_N a definujme hodnoty z_i jako součin všech x_j kromě x_i, takže z_i = Π_j<>i x_j. Vaším úkolem bude spočítat všechny z_i, přičemž nesmíte používat žádné jiné operace než násobení (speciálně ne dělení). Napište tedy funkci `zs : int [] -> seq<int>`. Tato funkce dostane na vstupu hodnoty x_i a vytvoří sekvenci, která vrátí postupně hodnoty z₁, z₂, ..., z_N. Vaším úkolem je co nejvíce šetřit časem a pamětí, přičemž uvažujeme časovou a paměťovou složitost pro spočtení všech z_i. Čas Ο(N) a paměť Ο(N): 1 bod Čas Ο(N) a paměť Ο(√N): +1 bod Čas Ο(N log N) a paměť Ο(log N): +2 body Řešení můžete poslat několik a body se sčítají podle toho, co splníte. Všimněte si, že pokud splníte druhou variantu, splnili jste automaticky i první variantu.
15. listopadu 2010	Úkoly můžete odevzdávat do 30. září 2011, 23:59.
diff	8	Napište program, který se bude chovat jako `diff -u`. Tedy program dostane na příkazové řádce jména dvou souborů. Jméno jednoho z těchto souborů může být `-`, což znamená standardní vstup. Na standardní výstup vypište diff těchto souborů ve formátu unified diff. Stejně jako `diff -u` je velikost kontextu 3, ale pokud uživatel zadá na začátku příkazové řádky `-U num`, změní se velikost kontextu na `num` (tedy `-U 3` je implicitní). Složitost musí být Ο(počet řádek v obou souborech velikost diffu), paměťová stačí Ο(velikost diffu na druhou)*, viz tento článek.
22. listopadu 2010	Úkoly můžete odevzdávat do 06. prosince 2010, 12:20.
demorse	2	Napište funkci `demorse : string -> option<string>`, která dekóduje vstup v morseovce, pokud je korektní. Tečka je tečka, čárka je pomlčka, oddělovač znaků je svislítko a oddělovač slov jsou dvě svislítka. Ostatní znaky ignorujte. Plný počet bodů za složitost lineární s velikostí vstupu, tj. každou tečku a čárku ze vstupu byste měli zpracovat jednou.
primes	2.5	Napište funkci `primes : seq<int>`, která vrací sekvenci všech prvočísel. Plný počet bodů za složitost Ο(N log log N) pro získání prvočísel mezi 1..N, což je shodou okolností složitost Eratosthenova síta :–) Jen na rozdíl od Eratosthenova síta nevíte předem hranici, do které budete chtít prvocísla najít. Za řešení v čase Ο(N √N) je jeden bod.
cenzor	2.5	Napište funkci `cenzor : string -> string -> string`, která ze druhého zadaného slova vymaže všechny výskyty prvního slova. Pozor na to, že smazáním jednoho slova může vzniknout další zakázané slovo, třeba `cenzor "bug" "bububuggg" = ""`. Nepoužívejte knihovní funkce (jako třeba `String.IndexOf`), mělo by to být o implementaci vyhledávacího automatu. Plný počet bodů za lineární řešení. Hint: KMP (http://mj.ucw.cz/vyuka/0708/ads2/ads2.ps strana 26) a po smazání slov se "vrátit" o dost zpět.
22. listopadu 2010	Úkoly můžete odevzdávat do 20. prosince 2010, 12:20.
maxima	2.5	Napište funkci `maxima : int -> list<'a> -> list<'a> when 'a : comparable`, která dostane na vstupu číslo k a seznam x₁, x₂, ..., x_N. Vytvořte seznam délky N-k+1, jehož i-tý prvek je maximum z prvků x_i, x_i+1, ..., x_i+k-1. Řečeno slovy, spočtěte maxima všech souvislých úseků délky k. Plný počet bodů za řešení v lineárním čase.
useky	3	Napište funkci `useky : list<'a> -> list<list<'a>> when 'a : comparable`, která dostane na vstupu seznam, který rozloží na co nejmenší počet ostře rostoucích (ne nutně souvislých) podseznamů. Jinak řečeno, rozdělte prvky vstupního seznamu na co nejméně skupin, aby prvky v každé skupině byly ostře rostoucí. Plný počet bodů za řešení v čase Ο(N log N). Příklad: `useky [1..4] = [[1..4]];` `useky [4..1] = [[4]; [3]; [2]; [1]];` `useky [1; 1; 1] = [[1]; [1]; [1]]`
29. listopadu 2010	Úkoly můžete odevzdávat do 13. prosince 2010, 12:20.
wild	2	Napište funkci `wild : string -> string -> bool`, která dostane na vstupu wildcard a text a odpoví, zda celý tento text danému wildcardu odpovídá. Wildcard může obsahovat znaky: `?` – odpovídá právě jednomu znaku `` – odpovídá libovolně mnoha znakům cokoliv jiného – odpovídá právě tomuto znaku. Tedy wildcardu `a?b` odpovídá `acb`, `aabbb`, ale ne `ab` ani `aaab`. Plný počet bodů za řešení v čase Ο(délka wildcardu délka textu)*.
29. listopadu 2010	Úkoly můžete odevzdávat do 20. prosince 2010, 12:20.
calc1	1	Napište funkci `calc : string -> option<float>`, která vyhodnotí dodaný aritmetický výraz a vrátí výsledek, pokud bylo vše v pořádku. Ve výrazu lze používat operátory `+ - * / ^ ( )` s běžnými prioritami, a desetinná čísla typu `float`. Mezerové znaky ignorujte. Plný počet bodů za řešení v lineárním čase.
calc2	1	Tento úkol můžete řešit až po vyřešení `calc1`. Ve výrazu se mohou být i následující funkce: `abs() sqrt() sin() cos() min() max()`, přičemž funkce `min` a `max` mohou dostat libovolný nenulový počet argumentů, které jsou odděleny čárkami. Tedy například `min(abs((0 - 3) ^ 5), sin(4.4), sqrt(123))`.
calc3	1	Tento úkol můžete řešit až po vyřešení `calc2`. Před výrazem k vyhodnocení může být ještě několik přiřazení, každé ukončené středníkem. Přiřazení vypadá jako `proměnná = výraz;`, přičemž v následujících výrazech můžete používat výraz `proměnná`. Funguje to tedy podobně jako `let proměnná = výraz`. Příklad: `x = 3; x = x + 1; y = abs(x); z = x * y 3; x + y + z`
calc4	1	Tento úkol můžete řešit až po vyřešení `calc3`. Kromě proměnných můžete definovat i funkce, tj. přiřazení může vypadat jako `funkce a1 a2 ... = výraz;`. Tím definujete funkci s daným počtem argumentů a tedy `výraz` je může používat. Navíc následující výrazy mohou používat i funkci `funkce` se správným počtem argumentů. Chová se to tedy podobně jako `let funkce a1 a2 ... = výraz`. Příklad: `x = 3; f y = x + y; g a b c = f(a) + f(b) + f(c); h x = g(x, f(x), f(f(x))); h 5`
29. listopadu 2010	Úkoly můžete odevzdávat do 03. ledna 2011, 12:20.
spacify	2.5	Napište funkci `spacify : (maxlen : int) -> (isWord : seq<char> -> bool) -> list<char> -> list<list<char>>`. Tato funkce dostane na vstupu text bez mezer a jejím úkolem je přidat do textu mezery, aby všechna takováto vzniklá slova byla smysluplná. Dostanete tedy ještě maximální délku slova `maxlen` a funkci `isWord`, která pro slovo (sekvenci znaků) určí, zda je to smysluplné slovo jazyka. Pokud je takových rozdělení na slova víc, najděte to, které používá co nejméně slov. Plný počet bodů za složitost Ο(délka textu maximální délka slova * složitost `isWord`)*.
29. listopadu 2010	Úkoly můžete odevzdávat do 30. září 2011, 23:59.
logo	8	Naimplementujte simulátor loga podle tohoto zadání, a to včetně všech rozšíření. Pokud chcete, můžete podporovat hodnoty typu `float` místo `int`, dává to větší smysl :–) Pro testování můžete použít tato testovací data, jsou rozdělena podle jednotlivých rozšíření, ale vám musí fungovat stejně všechno.
logosrv	2	Pokud jste vyřešili předchozí úlohu, naimplementujte k ní http rozhraní. Tedy naimplementujte malý standalone http server (nejspíš běžící na uživatelsky definovaném portu), který zobrazuje stránku, na které je možné zadat kód pro Krunimíra a počet tahů. Po odeslání zobrazte navíc i obrázek s Krunimírovy tahy (nikam ho neukládejte, generujte ho on-the-fly).
13. prosince 2010	Úkoly můžete odevzdávat do 20. prosince 2010, 12:20.
cops	1.5	Ulice města si představte jako strom. Chcete každou ulici nechat hlídat policií. K tomu účelu na některé křižovatky (tj. vrcholy stromu) umístíte policisty. Ulice je hlídaná, když je policista umístěn na alespoň jednom konci této ulice. Protože je rozpočet policie tradičně mizerný, je třeba zaměstnat co nejméně policistů. Napište metodu `cops : tree<'a> -> list<'a>`, která dostane strom města a vrátí nejmenší množinu vrcholů takovou, že pro každou ulici je v této množině alespoň jeden její konec. Strom je definován jako `type tree<'a> = Node of 'a * list<tree<'a>>`.
median	2	Napište funkci `median : list<'a> -> 'a when 'a : comparison`, která vrací medián dané posloupnosti. Za Ο(N) v nejhorším případě jsou dva body, za Ο(N) v průměru je bod. Hint: http://mj.ucw.cz/vyuka/0607/ads1/ads.ps strana 14.
13. prosince 2010	Úkoly můžete odevzdávat do 03. ledna 2011, 12:20.
tiso	2	Stromy jsou definované jako `type BinTree<'a> = Nil \| Node of BinTree<'a> * 'a * BinTree<'a>`. Napište funkci, která dostane dva stromy, a zjistí, jestli jsou stejné, pokud nezáleží na pořadí synů. Tedy `Node (Nil, 1, Node (Nil, 2, Nil))` je až na pořadí synů shodný s `Node (Node (Nil, 2, Nil), 1, Nil)`. Plný počet bodů za řešení rychlejší než Ο(N²), kde N je počet vrcholů většího ze stromů.
blud	2	Na standardním vstupu dostanete bludiště. Všechny řádky standardního vstupu mají stejnou délku a obsahují znaky `.` – volné pole `X` – zeď @ – hrdina, je v bludišti právě jeden $ – poklad, je v bludišti právě jeden Vaším úkolem je najít a zobrazit nejkratší cestu hrdiny k pokladu (vypište bludiště ve stejném formátu, a políčka na nejkratší cestě vypište jako `*`), nebo říct, že neexistuje. Plný počet bodů za řešení v lineárním čase.
krumpac	1.5	Tato úloha rozšiřuje úlohu předchozí. Na vstupu je bludiště zadané ve stejném formátu. Hrdina si ale do bludiště přinesl krumpáč a v případě nouze může prokopat libovolnou stěnu. To je ale velmi náročný úkol – najděte proto cestu od hrdiny k pokladu, na které je třeba rozbít krumpáčem co nejméně stěn. Ze všech takových cest najděte tu nejkratší. Vypište libovolnou takovou cestu, políčka na ní vypište jako `*` a rozbité zdi jako `#`. Plný počet bodů za řešení v lineárním čase.
13. prosince 2010	Úkoly můžete odevzdávat do 30. září 2011, 23:59.
karel	6	Napište simulátor robota Karla. Na začátku stojí robot Karel na nějakém políčku šachovnice o rozměrech 10 x 10. Některá políčka šachovnice jsou volná, na jiných jsou zdi. Napište program, který očekává na příkazové řádce jména dvou souborů – první obsahuje šachovnici, ta se skládá z deseti řádek, každá o deseti znacích, buď `.` (volné políčko), `_` (volné políčko se značkou) nebo `X` (zeď). Na právě jednom políčku je robot Karel, jako znak `>`, `<`, `v`, `^`, který určuje jeho orientaci. Druhý zadaný soubor obsahuje program pro Karla v této syntaxi. Pokud je vstup v pořádku, proveďte proceduru `main`, která musí být definována. Odsimulujte program pro Karla a na standardní výstup vypište šachovnici po ukončení procedury `main`. Pokud výpočet trvá moc dlouho (například milion kroků), ukončete ho a vypište o tom zprávu.
20. prosince 2010	Úkoly můžete odevzdávat do 03. ledna 2011, 12:20.
zisk	2	Napište funkci `zisk : list<int> -> list<int>`, která dostane seznam celých čísel a najde nejdelší souvislý úsek, který má nezáporný součet (nejdelší období bez ztrát). Plný počet bodů za řešení v lineárním čase.
grep	1.5	Napište program `grep`, který dostane na standardním vstupu jako parametr regulérní výraz. Dále načítá standardní vstup a na výstup vypíše jenom řádky, které tomuto regulérnímu výrazu vyhovují. Pokud je parametru s regulérním výrazem předchází parametr `-v`, vypište naopak řádky, které danému výrazu nevyhovují. Hint: http://msdn.microsoft.com/en-us/library/system.text.regularexpressions.regex.aspx
20. prosince 2010	Úkoly můžete odevzdávat do 30. září 2011, 23:59.
chats	3	Napište jednoduchý chat server. Server poslouchá na (na příkazové řádce) zadaném portu. Připojit se může libovolný počet lidí. Když se někdo připojí, tak na první řádce napíše svůj nickname. Každá dalšá řádka od něj se pošle všem ostatním připojeným (těm, kteří už poslali nickname) ve formátu "nickname: řádka".
chatc	2	Napište jednoduchý konzolový chat klient. Klient se připojí na (na příkazové řádce) zadaný port. Jednotlivé zadané řádky se pošlou serveru. Kdykoliv přijde řádka od serveru, vypíše se "nad" rozepsanou editovanou řádku.
color6	1.5	Napište funkci `color6 : list<int>[] -> int[]`, která dostane rovinný graf a vrátí jeho obarvení šesti barvami (1..6). Graf na vstupu dostanete jako pole vrcholů, každý vrchol je reprezentován jako seznam jeho sousedů (čísluje se od nuly). Obarvení vraťte jako pole s prvky 1..6. Plný počet bodů za řešení v lineárním čase.
color5	2.5	Napište funkci `color5 : list<int>[] -> int[]`, která má stejný vstup jako `color6`, jenom počítá obarvení rovinného grafu pěti barvami. Plný počet bodů za složitost lepší než Ο(N²), za Ο(N²) je 1.5 bodu.
03. ledna 2011	Úkoly můžete odevzdávat do 30. září 2011, 23:59.
withlog	2.5	Navrhněte výpočet, který si kromě výsledku pamatuje ještě log průběhu výpočtu: vytvořte typ `WithLog<'a>`, který reprezentuje výpočet vracející typ `'a`, zároveň s jeho logem, vytvořte metodu `res : WithLog<'a> -> 'a`, která extrahuje výsledek výpočtu, vytvořte metodu `log : WithLog<'a> -> list<string>`, která extrahuje log výpočtu (jednotlivé zprávy v pořadí, v jakém byly do logu přidány), vytvořte `withlog`, která definuje computation expression pracující s typem `WithLog<'a>`, definujte `Zero`, `Return` a `Bind`, vytvořte metodu `write : string -> WithLog<unit>`, která loguje daný řetězec. Používá se uvnitř computation expression jako `do! write "message"`. Mělo by tedy fungovat let compute = withlog { do! write "a" do! write "b" return 5 } přičemž `res compute = 5` a `log compute = ["a"; "b"]`. Pozor na to, že `Bind` by měl fungovat v konstantním čase a že s `WithLog<'a>` lze dál pracovat v několika pokračování, takže použít `StringBuilder` je špatně.
withenv	2.5	Navrhněte výpočet, který si udržuje environment (pro zjednodušení je environment mapování řetězce na řetězec): vytvořte typ `Env`, který reprezentuje environment, vytvořte typ `WithEnv<'a>`, který reprezentuje výpočet, který si udržuje environment. Pozor na to, že výpočet může environment i měnit, vytvořte metodu `run : seq<string*string> -> WithEnv<'a> -> 'a`, která spustí výpočet s daným environmentem (zadaným jako posloupnost klíč-hodnota), vytvořte `withenv`, která definuje computation expression pracující s typem `WithEnv<'a>`, definujte `Zero`, `Return` a `Bind`, vytvořte metodu `get : string -> WithEnv<string>`, která vrátí z environmentu hodnotu s daným klíčem, nebo `null`, pokud neexistuje. Používá se uvnitř computation expression jako `let! value = get "name"`, vytvořte metodu `set : string -> string -> WithEnv<unit>`, která do environmentu zapíše pod daný klíč danou hodnotu (pokud už existuje, přepište ji). Používá se uvnitř computation expression jako `do! set "name" "Petr"`. Mělo by tedy fungovat let compute = withenv { let! oldname = get "name" do! set "name" "Jarda" return oldname } printfn "%A" (run ["name", "Petr"] compute) a po spuštění vypsat `"Petr`. Pozor na to, že s `WithEnv<'a>` lze dál pracovat v několika pokračování, které každé může jinak měnit `Env`.
stoppable	2.5	Navrhněte výpočet, který je možné v průběhu přerušit: vytvořte typ `Stoppable<'a>`, který reprezentuje výpočet vracející typ `'a`, který ale může být přerušen, vytvořte metodu `res : Stoppable<'a> -> option<'a>`, která vrátí výsledek, pokud výpočet není přerušen, vytvořte metodu `step : Stoppable<'a> -> Stoppable<'a>`, která pokud dostane přerušený výpočet, provádí ho do dalšího přerušení, vytvořte `stoppable`, která definuje computation expression pracující s typem `Stoppable<'a>`, definujte `Zero`, `Return` a `Bind`, vytvořte metodu `stop : Stoppable<unit>`, která přeruší probíhající výpočet. Používá se uvnitř computation expression jako `do! stop` Mělo by tedy fungovat let compute = stoppable { printfn "Pred" do! stop printfn "Po" return 5 } printfn "%A" (res compute) printfn "%A" (res (step compute)) a po spuštění vypsat Pred <null> Po Some 5
sudoku	4	Napište sudoku solver. Na standardním vstupu dostane popis sudoku – všímejte si jenom znaků `.` (tečka) a `0-9`, ostatní ignorujte (včetně znaků nové řádky) – tím budete umět načíst skoro všechny používané formáty. Dané sudoku vyřešte a vypište vyřešené na standardní výstup. Plný počet bodů, pokud to na většinu sudoku bude fungovat v rozumném čase (v řádu vteřin).
10. ledna 2011	Úkoly můžete odevzdávat do 30. září 2011, 23:59.
par	2.5	Navrhněte výpočet, který bude paralelně vyhodnocovat alternativní větve v různých vláknech: vytvořte typ `Par<'a>`, který reprezentuje výpočet, který bude počítat výsledek typu `'a` několika alternativními způsoby, a ty se budou provádět paralelně, vytvořte metodu `run : Par<'a> -> 'a`, která spustí výpočet, alternativní způsoby budou prováděny paralelně, vytvořte `par`, která definuje computation expression pracující s typem `Par<'a>`, definujte `Zero`, `Return`, `Bind` a `Combine`. Metoda `Combine` funguje tak, že dvě alternativy vyhodnocuje paralelně. Mělo by tedy fungovat let twoalts = par { return (List.length [1..1000000]) return (Seq.length <\| Seq.collect (fun i -> {1..1000}) {1..1000}) } let fouralts = par { return! twoalts return! twoalts } run fouralts přičemž výpočet bude probíhat ve 4 vláknech a které nejdřív skončí, vrátí výsledek, a ostatní vlákna budou ukončena.

Stav (25. 05. 2018)

Jméno	Odevzdané úkoly	Body

Zpět