Pokročilé techniky funkcionálního programování, PRG040


Doba a místo konání

Konají se dvě paralelky, jedna v úterý v 15:40 v S8, druhá hned potom v úterý v 17:20 taktéž v S8 (nenechte se zmást SISem). Můžete je libovolně mixovat, na obou se bude probírat to samé.

Zápočet

Zápočet je možné získat za zápočtový program nebo za alespoň 30 bodů z domácích úkolů, úkolů bude vypsáno za alespoň 100 bodů. Úkoly odevzdávejte na můj mail a to pouze do následující přednášky (u některých úkolů budu ukazovat řešení; později se objeví nejspíš i dlouhodobější úkoly). A prosím neopisujte. Možná bude možné si místo zápočťáku ke konci semestru připravit referát, ale uvidíme, jak to naše dvě paralelky zvládnou (nic neslibuji:)

Obsahy přednášek

Budoucí přednášky:

Referáty

6. květnaQuickCheck - Peter Bašista - 45m
Haskore - Tomáš Kraut - 45m
13. květnaFunctional reactive programming - Tomáš Petříček - 90m
20. květnaPan - Jiří Kunčar - 45m
HRay - Čestmír Houška - 45m
Referáty je třeba říct v obou paralelkách. Budete na ně mít projektor, ale notebook si prosím doneste sami. Můžu zkusit sehnat i fakultní, ale nezaručuji se za jeho hardwarový ani softwarový stav :) Odměnou za referát vám budiž zápočet bez potřeby dělání dalších domácích úkolů.

Domácí úkoly (28. 06. 2010)

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

Všechny domácí úkoly by měly být spustitelné na hugsu i na ghci, byť můžete používat vcelku libovolná rozšíření oproti Haskellu 98, která jsou v obou interpreterech.

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.
Datum
cvičení
IDBodyPopis
26. únorawc2Napište skript, který přečte standardní vstup a na výstup vypíše jednu řádku (podobně jako wc bez parametrů až na nemezerové znaky):
počet_řádek počet_slov počet_nemezerových_znaků
Je vhodné použít main = interact w, kde w::String->String
cat-n2Napište skript, který se chová jako cat -n, tj. čte standardní vstup a každý řádek očísluje stylem printf("%6d\t%s, číslo_řádku, text_řádku)
 Pro další tři úlohy ji zadefinujte binární strom, který má hodnoty typu a v každém vrcholu, tj. BinTree a = ....
l2t2Napište funkci, která dostane setřídění seznam a vytvoří z něj perfektní binární vyhledávací strom. Perfektní znamená, že v každém vrcholu je velikost podstromu levého syna rovna velikosti podstromu pravého syna až na plus minus 1.
perf1Vytvořte funkci, které zadáte mocninu dvojky n=2k a ona vytvoří úplný binární strom s k hladinami. V každém vrcholu je číslo 1. Optimalizujte na časovou složitost...
onepass2Napište funkci, které dáte binární strom s Inty a ona vytvoří strom stejného tvaru, taktéž s Inty, který má v každém vrcholu uložený celočíselný průměr všech hodnot vrcholů původního stromu. Pozor, původní strom můžete projít jenom jednou a ten nový nemůžete procházet vůbec (jenom ho vytvořit)!
4. březnashow1Máte dáno data Tree a = Empty | Tree a [Tree a]. Napište ručně instanci instance Show (Tree a), aby fungovala v lineárním čase.
n2351.5Napište funkci, která bude vracet nekonečný seznam rostoucích čísel, která nemají jiné prvočíselné dělitele než dvojku, trojku a pětku, tj. čísel tvaru 2i * 3j * 5k. Složitost získání prvních K prvků musí být O(K).
lcs1.5Napište funkci, která pro dva zadané seznamy spočítá délku jejich nejdelšího společného souvislého podseznamu (za nesouvislý je bonus). Časová složitost by měla být nejvíc O(součin délek těchto seznamů).
deriv2Napište jednoduché derivovátko::String->String, derivuje se podle x. Musí umět alespoň + * ^ sin cos log x a čísla. Operátory musí jít zadávat infixově a musí funovat priority + * ^, takže 3 + 4 * 5 ^ 2 je 3 + (4 * (5^2)). Snažte si co nejvíc ulehčit práci pomocí třídy Read.Třída Read bohužel neumí parsovat operátory podle asociativity a ještě je ohavně pomalá, ale pro získání bodů z tohoto úkolu stačí, tj. nemusíte umět naparsovat 5 + 5 + 5. Lepší parsery se naučíme používat / psát časem :–)
 Na následující úložky smíte použít -fglasgow-exts (v Hugsu -98). Uvědomte si, že (->) je typový konstruktor.
Za první odevzdanou z následujících třech úloh dostanete dva body, za druhou a třetí odevzdanou jeden bod (jsou si navzájem docela podobné).
sumall1-2Napište funkci sumall, která dostane libovolný nezáporný počet Intů a vrátí jejich součet.
maxall1-2Napište funkci maxall, která dostane libovolný kladný počet porovnatelných prvků a vrátí jejich maximum. Všechny parametry musí být stejného typu, ale ten typ je libovolný porovnatelný.
mulall1-2Navrhněte funkci mulAll, které jako první parametr nějak zadáte počet a ona pak vynásobí tolik parametrů typu Integer. Takže typ mulAll "dva" musí být Integer->Integer->Integer. Tu "dvojku" nemůžete zadat číslem ani stringem, ale nějak jinak (klidně to může být unárně).
11. březnapyth1.5Napište funkci pyth::[(Int,Int,Int)], která bude vracet všechny pythagorejské trojice, tj. trojice kladných přirozených čísel, že a2+b2=c2. Tato funkce by měla vracet všechny takové trojice a přitom každou právě jednou ((3,4,5) a (4,3,5) jsou stejné trojice).
ls2Napište příkaz ls, který dostane na příkazové řádce několik adresářů, každý z nich rekurzivně projde a vypíše.
diff3Napište příkaz diff, který dostane na příkazové řádce dva soubory (pokud jeden chybí, tak je to standardní vstup) a najde diff, tj. nejmenší počet řádek, které je třeba odstranit či přidat, aby se z prvního souboru stal druhý. Na výstup (jako diff -u) vypište nezměněné řádky s mezerou na začátku, odstraněné s - na začátku a přidané s + na začátku.
mstop2Rozšiřte monádu z Eval2.hs tak, aby podporovala funkci stop. Této funkci předáte string. Tato funkce přeruší výpočet v monádě a vrátí (uvnitř té monády samozřejmě) onen string a zbytek výpočtu. Uživatel může zbytek výpočtu kdykoliv spustit. Proveďte to tak, že přidáte třídu MonadStop, která obsahuje funkci stop::String->m (). Samozřejmě je třeba upravit typ Result a její monádové instance (Monad i MonadStop).
wrap2Vytvořte funkci wrap::f->IO () která dostane libovolnou funkci. Všechny potřebné parametry funkce f načte wrap ze standardního vstupu (každý parametr na jedné řádce) a výstup funkce f vypíše wrap na standardní výstup. Načítat a vypisovat musíte umět Int, [Int] (na jedné řádce oddělené mezerami) a String (celá řádka i s mezerami).
18. březnabala1-2Napište funkci balanced::[Int]->Int, která dostane seznam nul a jedniček a vrátí délku nejdelší souvislé podposloupnosti, ve které je stejně nul a jedniček. Body dostanete podle časové složitosti, O(N^2) za bod, O(N) za dva.
usek1-2Napište funkci usek::[Int]->Int, která dostane posloupnost a vrátí délku její nejdelší souvislé podposloupnosti, která má nezáporný součet svých členů. Body dostanete podle časové složitosti, O(N^2) za bod, O(N) za dva body.
demo2Napište funkce demorse::String->String, která dekóduje vstup v morseovce. 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ů jenom za složitost lineární s velikostí vstupu plus s velikostí abecedy.
calc3Napište jednoduchou kalkulačku pro čísla s libovolnou přesností. Čtěte standardní vstup, každá řádka je jeden výraz, spočtěte ho a výsledek vypište. Výraz je klasický aritmetický výraz s operacemi + - * / % ^ (mínus jenom binární), závorkami, čísly a speciální proměnnou "last", ve které je uložen výsledek předchozího výrazu (a nula, pokud jde o první výraz nebo se minulý výraz nepovedlo naparsovat nebo vyhodnotit). Na parsování výrazu si napište parser typu toho z přednášky (výsledky parseru ukládejte do Maybe monády). Vše počítejte v Integerech. Složitost by měla být lineární s velikostí vstupu.
 Následuje úložka pro monadické šílence.
mstep4Napište (nebo zkopírujte z minulých úloh) parser, který načítá aritmetický výraz s + - * / % ^, závorkami a čísly typu Integer. Výraz si uložte ve stromové struktuře, ale zatím nevyhodnocujte. Implementujte monádu, která umožní vyhodnotit výraz, přičemž smí spotřebovat nanejvýš zadaný počet kroků. Na vyhodnocení + - je třeba 1 krok, na vyhodnocení * / % je třeba 7 kroků, na vyhodnocení ^ je třeba 13 kroků (vyhodnocení čísla a závorky je zdarma). Pokud lze výpočet provést v zadaném počtu kroků, vrátí se výsledek, pokud ne, vrátí se zbývající výpočet (co ještě nebylo uděláno). Také napište instanci MonadPlus, která umožní provádět dva výpočty paralelně, tj. vrátí výsledek toho, který skončí v menším počtu kroků. Detaily, které zde nejsou, si můžete domyslet. Složitost musí být libovolná polynomiálním, plný počet za řešení, které se mi nebude hnusit (a bonusy za řešení, které se mi budou líbit).
25. březnablud2Na vstupu dostanete bludiště: dostanete čísla N,M a dále Mřádek, každá obsahuje N nemezerových znaků. Velké X je zeď, tečka je volno, M je matfyzák, který je v bludišti právě jeden, a m je matfyzačka, která je v bludišti také právě jedna. Najděte a zobrazte nejkratší cestu mezi matfyzačkou a matfyzákem. Vypište bludiště ve stejném formátu, jenom zavináčem označte políčka, která leží na nejkratší cestě. Chci O(MN) nebo O(MN log(MN)).
coll2Vytvořte funkci collision::(Integer->Integer)->(Integer,Integer), která dostane funkci f, o které ví, že nekonečná posloupnost f(0), f(f(0)), f(f(f(0))),... neobsahuje nulu a skládá se pouze z konečného počtu různých čísel (čili je od nějaké doby periodická). Najděte co nejrychleji a s pomocí co nejméně paměti dvě různé hodnoty x,y, aby f(x)=f(y).
subw2.5Dostanete řetězec délky N a dále celé číslo K. Vaším úkolem je nalézt nejčastější souvislý podřetězec délky K. Plný počet jenom za řešení v čase O(NK) a lepší.
ppow2.5Vytvořte funkci perfpowers::[Integer], která vrací setříděný seznam všech perfektních mocnin. Perfektní mocnina je číslo větší než jedna tvaru prvočíslo na itou. Prvních pár členů tedy je [2,3,4,5,7,8,9,11,...]. Časová složitost získání prvních N členů musí být nejvýše O(N log2N) na plný počet bodů, ale každé polynomiální řešení dostane alespoň nějaké body.
tiso2Stromy jsou definované jako BinTree a = N | V (BinTree a) a (BinTree a). Napište funkci, která dostane dva stromy, a zjistí, jestli jsou stejné až na pořadí synů. Tedy V N 1 (V N 2 N) je až na pořadí synů shodný s V (V N 2 N) 1 N. Plný počet bodů jenom za řešení rychlejší než O(N2), kde N je počet vrcholů většího ze stromů.
 Úložka pro monadické šílence zůstala z minula.
mstep4Napište (nebo zkopírujte z minulých úloh) parser, který načítá aritmetický výraz s + - * / % ^, závorkami a čísly typu Integer. Výraz si uložte ve stromové struktuře, ale zatím nevyhodnocujte. Implementujte monádu, která umožní vyhodnotit výraz, přičemž smí spotřebovat nanejvýš zadaný počet kroků. Na vyhodnocení + - je třeba 1 krok, na vyhodnocení * / % je třeba 7 kroků, na vyhodnocení ^ je třeba 13 kroků (vyhodnocení čísla a závorky je zdarma). Pokud lze výpočet provést v zadaném počtu kroků, vrátí se výsledek, pokud ne, vrátí se zbývající výpočet (co ještě nebylo uděláno). Také napište instanci MonadPlus, která umožní provádět dva výpočty paralelně, tj. vrátí výsledek toho, který skončí v menším počtu kroků. Detaily, které zde nejsou, si můžete domyslet. Složitost musí být libovolná polynomiálním, plný počet za řešení, které se mi nebude hnusit (a bonusy za řešení, které se mi budou líbit).
1. dubnaacc3Napište funkci acc::(a->a->a)->[a]->a nebo acc::(a->a->a)->[a]->IO a. Pokud spustíte acc f [x1,...,xn], je vaším úkolem vrátit hodotu x1 `f` x2 `f` ... `f` xn . Funkce f je asociativní a komutativní, takže je jedno v jakém pořadí ji budete aplikovat. Předpokládejte, že máte n procesorů, takže výpočet co nejvíce zparalelizujte - měl by doběhnout v čase O(n)+log n*O(čas vyhodnocení f) (pokud mátě oněch n procesorů).
rost3Napište funkci rost::(Ord a)=>[a]->[a], která vrátí nejdelší rostoucí podposloupnost (souvislou nebo nesouvislou) zadané posloupnosti. Plný počet bodů jenom za O(N log N), za O(N2) jsou body dva.
fft2Naprogramujte v Haskellu funkci FFT::Int->[Float]->[Complex Float]. Tato funkce použitá jako FFT n seznam_2n_floatů provede FFT na daných hodnotách. Složitost algoritmu musí být O(N log N).
  Následuje bušící úložka, která je spíše technická než náročná. Bude na ní čas dva týdny místo jednoho.
chats4Napište v Haskellu jednoduchý chatovací server. Pro síťovou komunikaci použijte standardní modul Network. Pokud ho nemáte nainstalovaný, najdete ho tady. Server by měl poslouchat na 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".
chatc2Napište k serveru chatovací klient. Na příkazové řádce dostane adresu a port serveru a nickname uživatele. Zkusí se připojit a pak každou zadanou řádku pošle na server. Zprávy od serveru zobrazujte nějak průběžně (nemusíte je zobrazovat když zrovna uživatel píše zprávu). Za použití readline a možnosti přijímat zprávy od ostatních i při psaní zprávy můžete dostat až dvoubodový bonus.
8. dubna  Z minula:
rost3Napište funkci rost::(Ord a)=>[a]->[a], která vrátí nejdelší rostoucí podposloupnost (souvislou nebo nesouvislou) zadané posloupnosti. Plný počet bodů jenom za O(N log N), za O(N2) jsou body dva.
chats4Napište v Haskellu jednoduchý chatovací server. Pro síťovou komunikaci použijte standardní modul Network. Pokud ho nemáte nainstalovaný, najdete ho tady. Server by měl poslouchat na 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".
chatc2Napište k serveru chatovací klient. Na příkazové řádce dostane adresu a port serveru a nickname uživatele. Zkusí se připojit a pak každou zadanou řádku pošle na server. Zprávy od serveru zobrazujte nějak průběžně (nemusíte je zobrazovat když zrovna uživatel píše zprávu). Za použití readline a možnosti přijímat zprávy od ostatních i při psaní zprávy můžete dostat až dvoubodový bonus.
  Nové:
inst2Napište funkci insert::String->ExpQ pro Template Haskell. Když ji použijete jako $(insert "a.txt"), tak se při kompilaci najde soubor a.txt a ten se jako řetězec vloží tam, kde bylo insert zavoláno.
2tup1Napište funkci totup::Int->ExpQ pro Template Haskell, že když $(totup 5) dostane neprázdný seznam, vrátí jako pětici jeho prvních 5 prvků. Pokud jich seznam měl méně, tak je opakujte. Tj. $(totup 5) [1,2] vrátí (1,2,1,2,1).
sqrt3Napište funkci odmocni::Int->Int->ExpQ pro Template Haskell, že $(odmocni 2 100)$ se nahradí za odmocninu ze dvou na sto desetinných míst. Musíte se tedy nahradit číslem typu Rational, jehož jmenovatel bude 10^100 a jehož čitatel bude takový, aby to byla požadovaná odmocnina. Časová složitost $(odmocni k n) musí být nejvýš O(n*(násobení čísel o (n+log k) bitech)).
web4Napište jednoduchý webserver. Webserveru při spuštění dáte port a adresář, ze kterého má obsluhovat. Webserver pak sedí na daném portu. Když se ho někdo zeptá, obslouží ho, a obsluhovat zvládne libovolně lidí najednou. Implementujte HTTP 0.9, přičemž byste měli v adresách umět dekódovat "%xy", viz zde. Mělo by to fungovat natolik, aby se se serverem dokázaly mé prohlížeče (Opera, Firefox) bavit.
15. dubna  Z minula:
inst2Napište funkci insert::String->ExpQ pro Template Haskell. Když ji použijete jako $(insert "a.txt"), tak se při kompilaci najde soubor a.txt a ten se jako řetězec vloží tam, kde bylo insert zavoláno.
2tup1Napište funkci totup::Int->ExpQ pro Template Haskell, že když $(totup 5) dostane neprázdný seznam, vrátí jako pětici jeho prvních 5 prvků. Pokud jich seznam měl méně, tak je opakujte. Tj. $(totup 5) [1,2] vrátí (1,2,1,2,1).
sqrt3Napište funkci odmocni::Int->Int->ExpQ pro Template Haskell, že $(odmocni 2 100)$ se nahradí za odmocninu ze dvou na sto desetinných míst. Musíte se tedy nahradit číslem typu Rational, jehož jmenovatel bude 10^100 a jehož čitatel bude takový, aby to byla požadovaná odmocnina. Časová složitost $(odmocni k n) musí být nejvýš O(n*(násobení čísel o (n+log k) bitech)).
web4Napište jednoduchý webserver. Webserveru při spuštění dáte port a adresář, ze kterého má obsluhovat. Webserver pak sedí na daném portu. Když se ho někdo zeptá, obslouží ho, a obsluhovat zvládne libovolně lidí najednou. Implementujte HTTP 0.9, přičemž byste měli v adresách umět dekódovat "%xy", viz zde. Mělo by to fungovat natolik, aby se se serverem dokázaly mé prohlížeče (Opera, Firefox) bavit.
psrt3.5Napište funkci psort::(Ord a)=>[a]->[a], která setřídí danou posloupnost. Předpokládejte, že posloupnost je skoro setříděná v tom smyslu, že každý prvek je nejvýš o k pozic mimo (tedy pro každý prvek je rozdíl jeho indexů v zadané a setříděné posloupnosti nejvýš k). Optimalizujte časovou složitost, tj. O(n log k) za tři a půl bodu, O(nk) za dva a zbytek jako O(n log n) a horší za jeden.
logo8Implementujte jednoduchou variantu Loga v Haskellu. Vaše implementace musí být jeden modul, který definuje abstraktní typ Program, a dále exportuje primitiva forward::Int->Program (posune želvičku o daný počet kroků/pixelů), left::Int->Program (otočí želvičku doleva o daný počet stupňů), pen::Bool->Program (zda odteď želvička kreslí nebo ne) a color::Color->Program (barva pera, typ Color si navrhněte jak chcete).
Dále musíte umět tato primitiva nejak spojovat. Osobně vám doporučuji, abyste si vytvořili modádu ProgramM a a pak zadefinovali type Program=ProgramM (). Pak můžete psát programy pro želvičku jako
		spirala delka uhel = do forward delka
					left uhel
					when (delka<100) $ spirala (delka+2) uhel
Nakonec exportujte z modulu funkci runLogo::Int->Program->IO (), která dostane uživatelem definovaný program a ten spustí (otevře okno, provede ho a nechá okno otevřené než ho uživatel zavře). Obrázek zobrazujte průběžně. První parametr funkce je počet ms, jak dlouho se čeká po provedení left, forward, pen, color. Pro grafiku můžete použít co se vám zlíbí, třeba HGL, gtk2hs, wxHaskell, Glut+OpenGL, GLFW+OpenGL, SDL,...
logo23Rozšiřte předchozí úlohu o funkci run2Logos::Int->Program->Program->IO (), která dostane program dvou želviček a bude je provádět paralelně (provádí jeden program, poté, co on zavolá jednu z funkcí forward,left,pen,color počká daný počet ms (první parametr), pak tento program přeruší a provádí druhý program,...).
zkouškové  Tyto úkoly je možné odevzdávat do konce školního roku, tj. do konce září.
sqrt3Napište funkci odmocni::Int->Int->ExpQ pro Template Haskell, že $(odmocni 2 100)$ se nahradí za odmocninu ze dvou na sto desetinných míst. Musíte se tedy nahradit číslem typu Rational, jehož jmenovatel bude 10^100 a jehož čitatel bude takový, aby to byla požadovaná odmocnina. Časová složitost $(odmocni k n) musí být nejvýš O(n*(násobení čísel o (n+log k) bitech)).
web4Napište jednoduchý webserver. Webserveru při spuštění dáte port a adresář, ze kterého má obsluhovat. Webserver pak sedí na daném portu. Když se ho někdo zeptá, obslouží ho, a obsluhovat zvládne libovolně lidí najednou. Implementujte HTTP 0.9, přičemž byste měli v adresách umět dekódovat "%xy", viz zde. Mělo by to fungovat natolik, aby se se serverem dokázaly mé prohlížeče (Opera, Firefox) bavit.
psrt3.5Napište funkci psort::(Ord a)=>[a]->[a], která setřídí danou posloupnost. Předpokládejte, že posloupnost je skoro setříděná v tom smyslu, že každý prvek je nejvýš o k pozic mimo (tedy pro každý prvek je rozdíl jeho indexů v zadané a setříděné posloupnosti nejvýš k). Optimalizujte časovou složitost, tj. O(n log k) za tři a půl bodu, O(nk) za dva a zbytek jako O(n log n) a horší za jeden.
logo8Implementujte jednoduchou variantu Loga v Haskellu. Vaše implementace musí být jeden modul, který definuje abstraktní typ Program, a dále exportuje primitiva forward::Int->Program (posune želvičku o daný počet kroků/pixelů), left::Int->Program (otočí želvičku doleva o daný počet stupňů), pen::Bool->Program (zda odteď želvička kreslí nebo ne) a color::Color->Program (barva pera, typ Color si navrhněte jak chcete).
Dále musíte umět tato primitiva nejak spojovat. Osobně vám doporučuji, abyste si vytvořili modádu ProgramM a a pak zadefinovali type Program=ProgramM (). Pak můžete psát programy pro želvičku jako
		spirala delka uhel = do forward delka
					left uhel
					when (delka<100) $ spirala (delka+2) uhel
Nakonec exportujte z modulu funkci runLogo::Int->Program->IO (), která dostane uživatelem definovaný program a ten spustí (otevře okno, provede ho a nechá okno otevřené než ho uživatel zavře). Obrázek zobrazujte průběžně. První parametr funkce je počet ms, jak dlouho se čeká po provedení left, forward, pen, color. Pro grafiku můžete použít co se vám zlíbí, třeba HGL, gtk2hs, wxHaskell, Glut+OpenGL, GLFW+OpenGL, SDL,...
logo23Rozšiřte předchozí úlohu o funkci run2Logos::Int->Program->Program->IO (), která dostane program dvou želviček a bude je provádět paralelně (provádí jeden program, poté, co on zavolá jednu z funkcí forward,left,pen,color počká daný počet ms (první parametr), pak tento program přeruší a provádí druhý program,...).
quad2Na vstupu je černobílý obrázek v rozlišení 2n x 2n zadaný následujícím kódováním:
  • kód celého černého obrázku je 0,
  • kód celého bílého obrázku je 1,
  • není-li obrázek jednobarevnký, reprezentuje ho kód 2k1k2k3k4, kde ki jsou kódy čtvrtin obrázku v pořadí vlevo nahoře, vpravo nahoře, vlevo dole, vpravo dole. Napište funkci, která dostane kód obrázku a vrátí kód obrázku, který vznikne otočením doleva o 90o. Na plný počet bodů musí být časová složitost lineární.
abcd4Abeceda ztraceného národa Atlantiďanů se skládala z nějaké podmnožiny Unicode znaků. Bohužel už není známo uspořádání těchto znaků, ale víte, že bylo lineární. Získali jste kus slovníku, tedy několik slov, které jsou lexikograficky setříděné. Předpokládejte, že písmena těchto slov jsou celá atlantidská abeceda. Vaším úkolem je nalézt lineární uspořádání písmen v abecedě, případně říct, že ho z daných slov nejde stanovit.
Napište tedy funkci abcd::[String]->Maybe [Char], která dostane lexikograficky setříděná slova a pokud je možné určit jednoznačné lineární uspořádání všech písmen v těchto slovech, vrátí ho, jinak vrátí Nothing. Můžete předpokládat, že data jsou konzistentní.

Stav (28. 06. 2010)

JménoOdevzdané úkolyBody
Peter Bašistapyth(1.5), coll(2), tiso(1), fft(2), referat(23.5)30
Anička Bernáthováwc(2), cat-n(2), l2t(2), perf(1), onepass(2), show(1), n235(1.5), lcs(1.5), sumall(2), ls(2), pyth(3), diff(1.5), wrap(1), demo(2), bala(2), web(4)30.5
Kateřina Böhmováwc(2), cat-n(2), l2t(1), perf(1), onepass(1), pyth(1.5), bala(2), usek(1), demo(2), coll(2), ppow(1.5), rost(2.5), fft(1.5), quad(1.5), psrt(3), abcd(4), dluh(0.5)30
Ondra Bílkawc(2), cat-n(2), l2t(2), perf(1), onepass(2), lcs(1), show(1), n235(1.5), deriv(2), sumall(), ls(2), diff(3), pyth(1), demo(2), usek(1), bala(0.5), ppow(2.5), coll(2), rost(2)30.5
Martin "next_ghost" Douchawc(2), cat-n(2), l2t(2), perf(1), onepass(2), sumall(2), lcs(1.5), n235(1.5), maxall(1), show(1), deriv(1.5), ls(1.5), pyth(1.5), wrap(2), diff(3), bala(2), usek(2), demo(2), coll(1)32.5
Tomáš "gavento" Gavenčiakwc(2), cat-n(2), l2t(2), perf(1), onepass(2), show(1), sumall(2), maxall(1), mulall(1), ls(2), wrap(2), demo(2), bala(2), usek(1.5), coll(1.5), subw(2.5), ppow(2), acc(2)31.5
Čestmír Houškawc(2), cat-n(1), l2t(1), perf(1), onepass(0.5), lcs(2), show(1), ls(1.5), pyth(1), fft(1)12
Mirek Kratochvílls(2), pyth(1), demo(2), bala(0.5), usek(0.5), acc(2.5), fft(3), web(4), psrt(2)17.5
Petr Kratochvílwc(2), cat-n(2), l2t(2), perf(1), onepass(2), deriv(2), n235(1.5)12.5
Tomáš Krautwc(2), cat-n(1.5), perf(1), n235(1.5), lcs(1), pyth(1.5), demo(1), ppow(1.5), coll(1), referat(18)30
Jana Kravalováwc(2), cat-n(2), l2t(2), perf(1), onepass(2), show(1), lcs(2.5), deriv(1.5), pyth(1.5), ls(2), bala(2), ppow(1.5), subw(1.5), rost(2), chats(4), chatc(2)30.5
Martin Kupecwc(2), cat-n(2), n235(1.5), lcs(1.5), coll(1), ppow(1)9
Jiří Kunčarlcs(0.5), n235(1.5), demo(1.5), bala(2), tiso(1), sumw(1.5), ppow(1.5), acc(2), fft(1), chats(4), chatc(2)18.5
Jakub Melkawc(2), cat-n(1.5), l2t(1), perf(0.5), show(1), lcs(2.5), n235(1), deriv(2), ls(1.5), pyth(1.5), diff(3), bala(1), demo(2), usek(1), calc(3), coll(1), tiso(1), subw(1.5), ppow(1.5), rost(2)31.5
Jan Návratwc(1), cat-n(1), perf(1), lcs(1.5), sumall(0.5), ls(0.5), pyth(1)6.5
Adam Nohejlwc(2), cat-n(2), l2t(2), perf(1), onepass(1), wrap(1.5), ls(2), pyth(1.5), diff(3), demo(2), bala(2), usek(1), coll(1), acc(3), 2tup(1), inst(2), rost(2)30
Michal Pavelčíkwc(2), cat-n(2), l2t(1), perf(1), onepass(2), n235(1.5), deriv(2), lcs(1.5), ls(2), wrap(2), pyth(1.5), bala(2), usek(2), demo(2), calc(2), ppow(2.5), blud(2), coll(2), rost(2), acc(3)38
Matúš "ziman" Tejiščákwc(2), cat-n(2), l2t(1), perf(0.5), onepass(1), show(1), lcs(1.5), deriv(2), n235(1.5), ls(2), pyth(1.5), diff(3), wrap(2), demo(2), usek(2), bala(2), blud(2), ppow(2), subw(2.5), rost(3), web(4)40.5
Michal "vorner" Vanerwc(2), cat-n(2), l2t(2), perf(1), onepass(2), show(1), lcs(1.5), n235(1.5), sumall(2), maxall(1), wrap(2), pyth(1.5), ls(2), demo(2), calc(3), coll(1), ppow(1.5), acc(2.5), chats(4), chatc(4)39.5
Maria Vamošovál2t(1), perf(0.5), onepass(0.5)2
Jan Volecwc(2), cat-n(1.5)3.5
Hujerwc(2), cat-n(2), l2t(2), perf(1), onepass(2), show(1), n235(1.5), lcs(1.5), deriv(2), sumall(2), maxall(1), mulall(1), pyth(1.5), ls(2), diff(3), mstop(2), wrap(2), bala(2), usek(2), demo(2), calc(3), mstep(4), blud(2), coll(2), subw(2.5), ppow(2.5), tiso(2), acc(3), rost(3), fft(2), chats(4), chatc(4), inst(2), 2tup(1), sqrt(3), web(4), psrt(3.5), logo(8), logo2(3), quad(2), abcd(4)100

Zpět