Komentáře poroty k řešením z 2. kola
Omlouváme se za delší prodlevy, snažili jsme se, aby výsledky byly co nejdříve, ale kromě soutěže máme mnoho práce s předěláváním VbNetu, do toho přišly nemoci a další problémy, takže výsledky druhého kola publikujeme až nyní. Chápeme, že díky těmto prodlevám jste právem nervózní, je nám to líto. Pokusíme se další kola vyhodnotit co nejdříve, abyste ceny mohli dostat pod stromeček. Účast daleko předčila nače očekávání, i když byla ve 2. kole nižší, než v tom prvním. Soutěžní práce se nám moc líbily, většina byla opravdu na vysoké úrovni.
Během opravování se nám mohlo stát, že jsme nějakou funkci přehlédli, nevšimli si něčeho, nebo jsme z kódu nepochopili, jak to funguje (dobrý nápad je přiložit alespoň krátké readme, jak program funguje a jaký algoritmus byl zvolen, stačí dvě tři věty, usnadní nám to hodně práce a předejde možným omylům). Pokud máte pocit, že jste za nějakou věc nedostali tolik bodů, kolik si zasloužíte, určitě napište (dáme limit 14 dnů, aby si někdo nevzpomněl za rok, že tam to či ono měl), podíváme se na řešení ještě jednou. Snažili jsme se hodnotit všechny faktory, jak algoritmus, tak uživatelské rozhraní, tak objektový návrh a celkový dojem, případně dokumentaci, pokud byla.
Výsledková listina 2. kola
Lehká úloha – Pexeso
Zadání a výsledková listina úlohy
Pexeso by se mohlo zdát jako velmi jednoduchá úloha, na jejímž zpracování se toho moc vymyslet nedá. Opak je pravdou. Při procházení řešení jsme byli překvapeni širokou škálou způsobů grafického zpracování, objektového návrhu i herní logiky. Něktěří využili klasického návrhu známého ze starších Visuak Basiců (moduly obsahující neobjektovou logiku) a ostatní zase řešili problém pomocí silného objektového modelu. Musím říct, že na tak drobnou aplikaci nelze 100% říct, že je silný objektový model lepší než procedurální programování.
Co se týče grafického zpracování, viděli jsme nejčastěji GDI+, avšak v jednom případě i XNA Framework a v několika dalších Windows Presentation Foundation. V některých řešeních doplnil komfort hry i zvuk. Při hodnocení jsme se koukali na celkový vzhled aplikace a eleganci řešení problému, proto nelze říct, že silnější technologie bude "lepší" než třeba obyčejné GDI+.
Pokud se podíváme na aplikace čistě z pohledu hráče, tak zistíme, že i velmi jednoduchým rozhraním můžeme získat intuitivní a efektivní (tedy i příjemné) ovládání. Dalším podstatným prvkem je volba obrázků, které odkrýváme. Nejlepší řešení dovolili volbu zadní i přední strany a dokonce hrací plochy. Bohužel několik soutěžících udělali zásadní chybu v podobě nepřidání obrázků do archivu, který nám zaslali a tak i prvotní nefunkčností, čímž přišli zbytečně o několik bodů.
Nikdo se nepokusil o implementaci síťové hry. Zato prakticky každý implementovat počítačového protihráče. Pravděpodobně úplně nejsprávnější řešení bylo vytvoření pole, kde by se udávalo jak dobře si počítač zapamatoval různá políčka. S určitou pravděpodobností by pak spletl obrázek úplně a s další pravděpodobností by jen udělal při výběru odchylku například o 1 políčko doleva. Čím víc by se to které pole odkrývalo, tím víc by si počítač pamatoval s jistotou. Zároveň i úroveň zapamatování by měla být náhodná (občas se stane, že si obrázek pamatujeme při prvním odkrytí a občas i po několikátém znovuodkrytí tápeme).
Těžká úloha – parsovač matematických výrazů
Zadání a výsledková listina úlohy
Parsování matematických výrazů má více různých řešení, která jsou různě efektivní a rychlá. Většina soutěžících si prostě zadanoý výraz vzala, našla v něm nejvnitřnější závorku, tu vyhodnotila, a provedla náhradu v celém výrazu, což se opakovalo, dokud nezůstalo jediné číslo. To je samozřejmě správné řešení, které vyprodukuje korektní výsledek, dá se podle něj i pěkně vypsat postup a průběh výpočtu. Má jen jedinou vadu – opakovaně procházíte celý řetězec a načítáte celý výraz znovu, než v něm nejvnitřnější závorku najdete, a samotné nahrazování také není zadarmo.
Stringy jsou v .NETu ošemetná záležitost. Jakmile je jednou vytvoříte, nelze je změnit. Pokud tedy nahrazujete něco ve výrazu, bude se celý string kopírovat. Tento problém částečně řeší třída StringBuilder, která umí stringy skládat a nahrazovat rychle, tu ale nikdo nepoužil (ono totiž často nebylo jak). Při opravování jsme zkusili předat programům výraz, který měl na délku asi 5MB, a tam se to na rychlosti docela projevilo. Do celkového hodnocení jsme nezahrnovali, jestli aplikace na tak dlouhém výrazu padá či ne (některé už spadly), ale bylo tam krásně vidět, kdo jaký algoritmus zvolil a proč opakované procházení řetězce je sice správně, ale není to rychlé. Lepší algoritmy jsou dva, popíšu zde oba dva, protože se v odevzdaných pracích vyskytly.
Dva zásobníky
První možnost je udělat si dva zásobníky – jeden na čísla, druhý na operátory. Postupně načítáme výraz, čísla dáváme do zásobníku na čísla, operátory do zásobníku na operátory. Protože násobení a dělení má největší prioritu, jakmile přečteme hvězdičku nebo lomítko, načteme další číslo, musíme násobení/dělení provést hned. Vezmeme tedy ze zásobníku čísel dvě poslední hodnoty, spočítáme je, a výsledek do tohoto zásobníku zase vložíme. Nesmíme zapomenout odebrat znaménko ze zásobníku operátorů. Tím jsme jednoduché násobení nebo dělení vypočítali.
V okamžiku, kdy načteme otevírací závorku, přidáme ji pouze do zásobníku na operátory a pokračujeme dál. Jakmile narazíme na uzavřenou závorku, postupně vyhodnocujeme výrazy, dokud nenarazíme na otevírací závorku. Protože násobení a dělení jsme už prováděli hned, mohlo nám v závorce zbýt pouze sčítání a odčítání. Opět tedy pro každý operátor v závorce načteme ze zásobníku čísel poslední dva prvky, provedeme operaci, a hodíme tam výsledek.
Jakmile dosáhneme konce výrazu, projdeme zbývající operátory v zásobníku operátorů a postupně provedeme všechny operace. Pokud byl výraz zadán správně, zůstane nám v zásobníku čísel jediná hodnota – výsledek. Pokud nám to někde během výpočtu spadlo, byla zjevně chyba ve výrazu, ohlásíme tedy špatné zadání.
Strom výrazu
Druhá možnost, kterou použilo docela dost lidí (variantu se dvěma zásobníky použil jeden soutěžící), je o dost obecnější a snadno se do ní přidávají další operátory. Výraz se čte opět jen jednou a během čtení se staví tzv. strom výrazu. Ten pro výraz 3 / (4 * 5 – 17) vypadá takto:
Jak takový strom reprezentovat v paměti? Jednoduše – stačí udělat třídu pojmenovanou např. TreeNode, která má dvě proměnné též typu TreeNode (ideálně zapouzdřené pomocí vlastností). Každý TreeNode má buď znaménko a další dva potomky, nebo má jen číselnou hodnotu (někteří to řešili třeba pomocí dědičnosti).
Ideální je udělat do třídy TreeNode metodu Evaluate, která spočítá hodnotu v daném podstromu. Číselné vrcholy pouze vrátí svoji hodnotu, znaménkové si zavolají Evaluate na svých potomcích (kteří svoji hodnotu zjistí stejným způsobem), a z výsledků, které dostanou, spočítají svoji hodnotu. Celý výraz tedy vypočítáme tak, že na kořenové položce zavoláme Evaluate.
Sestavení tohoto stromu dá trochu práce, ale není na něm nic světoborného. Místo postupu výpočtu stačilo vykreslit právě tento strom výrazu, což je velmi přehledné, a mnoho soutěžících to tak také udělalo.
Uživatelské rozhraní
Téměř všichna odevzdaná řešení nějak vypisovala průběh výpočtu. Ideálním řešením bylo vykreslit strom – s tím se dalo dost vyhrát a výsledek je přehledný. Textové výpisy také splní svoji úlohu, ale musí být přehledné, alespoň výsledky jednodlivých podvýrazů to chce vytáhnout tučně nebo barevně, jinak je to téměř k ničemu.
Dva experti použili pro vyhodnocování výrazu kompilátor C# – prostě vygenerovali kód malé třídy, do nějž dosadili výraz, a pustili na to kompilátor. Funguje to, ale je to hrozně pomalé a nevytřískáte z toho postup výpočtu. Je to ale originální řešení.
Jeden soutěžící použil vestavěnou .NETí třídu Expression, která je pro práci se stromy výrazu určena, toto řešení bylo velmi hezké. Pár lidí použilo relativně složité frameworky pro práci s výrazy pravděpodobně generované nějakými nástroji typu yacc, antlr atd., i to je velmi pěkné řešení, které je rozšiřitelné a robustní.
Závěrem
Na závěr bychom rádi poděkovali všem zúčastněným. Viděli jsme jednak úlohy slepené za chvilku, ale i profesionálně vyhlížející a propracované aplikace, které si svůj vysoký počet bodů právem zaslouží. Děkujeme proto všem, kteří si našli čas a této soutěži ho obětovali.