Výsledky 2. kola .NET Challenge

Tomáš Herceg       25. 11. 2008       Offtopic       6922 zobrazení

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:

Strom výrazu

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.

 

hodnocení článku

1 bodů / 1 hlasů       Hodnotit mohou jen registrované uživatelé.

 

Nový příspěvek

 

Diskuse: Výsledky 2. kola .NET Challenge

Budou, prosím, zase zveřejněna vzorová řešení úloh? Např. u lehké by bylo například zajímavé řešení v XNA :-)

nahlásit spamnahlásit spam 0 odpovědětodpovědět

Až budeme mít trochu času, napíšeme zase soutěžícím, jestli úlohy můžeme zveřejnit.

nahlásit spamnahlásit spam 0 odpovědětodpovědět

Ahoj, když se dívám na pravidla a konkrétně bod 8. tak se tam přímo zmiňuje, že budou zveřejněna s výsledkovou listinou i odevzdaná řešení. Už při prvním dotazu na možnost zveřejnění jsem se chtěl ozvat, ale jelikož toto není první případ, kdy by obdobná vzorová řešení bylo vhodné mít zveřejněna, jsem pro, aby byla zveřejněna všechna řešení. Neboť k tomu soutěžící dali souhlas již odevzdáním.

Nechť je to zveřejněno jen pod nějakou studijní licencí s možností kontaktu autora pro svolení k dalšímu šíření.

--J.

nahlásit spamnahlásit spam 1 / 1 odpovědětodpovědět

Ano, to by bylo dobré. Pokud by to někomu vadilo, měl by ale dostat možnost odstranění svých programů z výsledkové listiny.

nahlásit spamnahlásit spam 0 odpovědětodpovědět

V pravidlech to sice je, ale na druhou stranu nechtěli jsme zveřejňovat něčí zdrojáky bez jeho výslovného souhlasu, proto jsme se radši ještě zeptali. V současné době pracujeme na hodnocení 3. a 4. kola, výsledky se pokusíme zveřejnit co nejdříve a autory nejlepších prací pak požádáme o svolení ke zveřejnění pro všechny 3 zbylá kola najednou.

nahlásit spamnahlásit spam 0 odpovědětodpovědět

Diskuse: Výsledky 2. kola .NET Challenge

V jakém jmenném prostoru se nachází ta Expression? Vyhledáváním v Object Browseru se mi nic nepodařilo najít.

Jinak díky za výsledky. Musí to bejt fuška, opravovat necelých 50 programů a ještě takhle kvalitně.

nahlásit spamnahlásit spam 0 odpovědětodpovědět

Ahoj, třída Expression je ve jmenném prostoru System.Linq.Expressions.

--J.

nahlásit spamnahlásit spam 1 / 1 odpovědětodpovědět

no tak to som skoncil s VS 2005 :)

nahlásit spamnahlásit spam 0 odpovědětodpovědět

Diskuse: Výsledky 2. kola .NET Challenge

Tak na to, že mi je 14 a v těžké úloze jsem 12., tak to vidím jako dobrý start :)

nahlásit spamnahlásit spam 1 / 1 odpovědětodpovědět

17rokov (o 2 dni), 11 v tazkej ulohe. Ale ASP.NET ulohy som odflakol a posledne 2 ani nezacal z dovodu nedostatku casu.

nahlásit spamnahlásit spam 0 odpovědětodpovědět

Diskuse: Výsledky 2. kola .NET Challenge

Bylo by možné uveřejnit onen 5MB testovací výraz? Docela by mě zajímalo nejen jak vypadá, ale jak si s ním poradí vyhodnocovač výrazů, jakožto i výsledný strom. Díky

--J.

nahlásit spamnahlásit spam 0 odpovědětodpovědět

Byl velmi jednoduchý: (1+(1+(1+(1+...)))), jedniček bylo 1 250 000.

nahlásit spamnahlásit spam 0 odpovědětodpovědět

Diskuse: Výsledky 2. kola .NET Challenge

Tohle řešení mě napadlo také, ale právě kvůli nemožnosti zjištění průběhu výpočtu jsem to zavrhl :)

nahlásit spamnahlásit spam 0 odpovědětodpovědět
                       
Nadpis:
Antispam: Komu se občas házejí perly?
Příspěvek bude publikován pod identitou   anonym.

Nyní zakládáte pod článkem nové diskusní vlákno.
Pokud chcete reagovat na jiný příspěvek, klikněte na tlačítko "Odpovědět" u některého diskusního příspěvku.

Nyní odpovídáte na příspěvek pod článkem. Nebo chcete raději založit nové vlákno?

 

  • Administrátoři si vyhrazují právo komentáře upravovat či mazat bez udání důvodu.
    Mazány budou zejména komentáře obsahující vulgarity nebo porušující pravidla publikování.
  • Pokud nejste zaregistrováni, Vaše IP adresa bude zveřejněna. Pokud s tímto nesouhlasíte, příspěvek neodesílejte.

přihlásit pomocí externího účtu

přihlásit pomocí jména a hesla

Uživatel:  
Heslo:  

zapomenuté heslo

 

založit nový uživatelský účet

zaregistrujte se

 
zavřít

Nahlásit spam

Opravdu chcete tento příspěvek nahlásit pro porušování pravidel fóra?

Nahlásit Zrušit

Chyba

zavřít

feedback