Diskuze: Předvánoční speciál machra - Santova hádanka
Zdeněk Pavlátka:25.11.2013 18:17
Tohle je hádanka, kterou vymyslel Einstein. 
Tohle je samozřejmě
upravená verze. Měli jsme to řešit při jedné hodině matematiky, když
nám chyběla učitelka.
Jan Vargovský:25.11.2013 19:07
To pak není ono, musíš to hned algoritmovat 
Neaktivní uživatel:25.11.2013 19:08
To bych nedal, skoro jsem to nedal ani na papíře.
Neaktivní uživatel:25.11.2013 19:22
Teď mi to došlo spolu s chybou, co jsem našel.
![]:>](images/img/smileys/evil.png)
Jan Vargovský:25.11.2013 19:52
Mi se to právě nechce dělat na papíře vůbec, tak to programuji 
Neaktivní uživatel:25.11.2013 19:53
Mě by se to zase nechtělo programovat. Ani nevím vodkaď začít.
Silvinios:25.11.2013 21:29
Výborná připomínka. Na první pohled by se mohlo zdát, že je zadání příliš nepřesné...
Pokud má program pouze vyřešit jedno konkrétní zadání, stačí si vzít tužka a papír, úlohu během několika minut vyřešit a pak napsat program, který vypíše jméno dítěte.
Pokud je cílem vytvořit program, který vyřeší libovolné zadání, chybí specifikace toho, co může a nemůže v zadání být.
V reálném světě bychom na sdraca nejspíše poslali analytika a
pořádně ho vyzpovídali
Protože jsme ale na devbooku, není těžké si domyslet, oč jde. Čím obecnější a propracovanější řešení, tím lépe. Viděl bych to tak, že zadání přepíšu do textového souboru v nějakém vhodném formátu, který můj program při spuštění načte. Pokud se zadání trochu změní, opravím jen vstupní soubor, ale program zůstane stejný.
Zdravím všechny účastníky soutěže, soudě podle vašich ohlasů vás hádanka zaujala, což nás moc těší.
Jak píše nuz15, Einstein by se mohl zdát být autorem hádanky. Letos je
to ovšem jinak - autorem je Santa. A protože mám v zadání také prsty, odpovím na vaše
dotazy.
Q: Jak zjistím, které dítě zlobí?
A: Doporučuji být pečlivější při čtení zadání: A protože jedno z
dětí celý rok jenom zlobilo, dostane k vánocům pouze
uhlí!
Q: Jak je to s dárky? Aneb, to, že si to přeju neznamená, že to
dostanu... ?
A: Zbylé děti byly hodné, a proto opravdu dostanou to, co si
přejí. Možná, že vás zmátly ty ponožky jako dárek, ale co my
víme?
Q: Jak moc má být algoritmus univerzální? Nebo naopak jak moc nesmí být
specializovaný?
A: Tak moc, jak to dokážete. Nemusíte chodit s kanónem na vrabce, ale
jednoduché a obecné řešení má své výhody. Když hodnotím řešení,
rád mu trochu změním vstupní hodnoty (klidně i nesmyslně), abych viděl,
jak se chová. Vaše programy by měly nějakým způsobem zvládnout i to.
Nemusíte rovnou psát vlastní parser, který z textového souboru načte
zadání, porozumí mu a použitím vyšší inteligence ho vyřeší... ale
samozřejmě platí, že čím lepší program, tím větší šance na výhru.
Q: Sdraco, ty už jsi to vyřešil algoritmem?
A: Dovolím si odpovědět za Sdraca. Tahle soutěž je o vás a pro vás! Máme
své řešení, kterým jsme ověřili správnost zadání, ale více se
těšíme na ta vaše.
Silvinios má určitě pravdu v jedné věci - jsme na Devbooku, kde jsou úlohy, hádanky a programování denním chlebem. Cílem je se pobavit a něco naučit.
coells:26.11.2013 12:55
Tím myslím, že mohu dát Aničku do pátého domu a uvidím, jak si s tím
program poradí. Nebo také mohu do pátého domu dát všechny děti
Klíčové ovšem je správně vyřešit původní zadání.
Zadání mě trochu popletlo, ale jinak na papíře hotovo Mám ještě dotaz. Máme
nějaký univerzální vstup nebo můžu mít vlastní formát zadání (je
možné, že se někdo ptal)
Jan Vargovský:26.11.2013 21:17
Ano. Btw zkouším to natvrdo a počítá to už 4 hodiny 
Jan Vargovský:26.11.2013 21:24
Neměl by. Vypínat to nebudu, jestli to nevypočítá do 2 rána, tak to
kašlu
Michael Olšavský:26.11.2013 21:28
Vždyť řešení je jen 3125 (55) jestli se nepletu ne?
EDIT: Řešení je jen jedno, možností je 5, při výpočtu KOMPLETNÍ TABULKY je zde 55
Michael Olšavský:26.11.2013 21:44
Pravda pravda. S tím jsem nějak nepočítal Tak už to chápu
coells:5.12.2013 22:00
Nevadí, po skončení soutěže uvidíš řešení ostatních a třeba to
příště vyjde
Je to veľmi zaujímavý príklad , ostáva mi pridať poslednú podmienku do programu a modlím sa
nech to potom funguje
Původně jsem se tím nechtěl zabývat. Tenhle typ hádanek je
poměrně známý a není tam kromě pečlivosti asi co řešit.
Včera večer mě ale napadlo, že by bylo zajímavé udělat
poloautomat, který by neřešil ani tak výsledek, jako spíš
by u každé položky shromažďoval podmínky a v reálném čase
ukazoval možná platná umístění. Řešení pak lze snadno najít
postupným pokládáním platných položek.
Mám to hotovo v gml a mám i řešení takto získané.
Splácal jsem to celkem narychlo, takže faktické provedení
není tak univerzální, jako původní idea a trochu jsem
zneužil fakt, že zadání není příliš složité.
Podmínky jsou vlastně jen ve třech typech:
Fixní poloha, Relativní poloha a Sousedství.
Jednoduchý editor, který jsem si napsal, nechá vytvořit
položku, přiřadit podmínky a vysvítí platné volby.
Zároveň vypisuje vazby na jiné položky, takže je snadné
najít jejich pozici i když je vazeb víc.
Během používání jsem zjistil, že by se systém ještě zlepšil,
kdybych připsal zámek polohy pro relativní a sousedské vztahy.
S tím už jsem se ale nepatlal, když řešení mám.
Úloha by se velice ztížila, kdyby obsahovala relativní odkazy
vyššího řádu. Např.: Petřík by žil vedle toho, který
sousedí s tím, kdo pije coca-colu.
Taky by bylo zajímavé, kdyby byly i negativní podmínky,
Např.: Kdyby byla Anička nechovala to, co chová,
mohl by obyvatel bílého domu dostat uhlí nebo ponožky.
Je to velice variabilní záležitost a skýtá spoustu zábavy.
Včera mi coells poslal finální výsledky soutěže, dnes je sem dáme,
říkal jsem si, že by bylo lepší, kdyby to sem napsal přímo on
Přeji příjemné nedělní poledne a přináším horké vyhlášení vánočního speciálu machra. Tak tedy k výsledkům.
Juraj Mlich - 60 bodů
Juraj se ve svém řešení snaží přes dosud známá fakta vyloučit ostatní možnosti. Program je tak trochu šitý horkou jehlou a rozložení hlavního výpočtu na řadu malých metod by mu jenom prospělo. Výpočet také obsahuje nápovědy, které nejsou v zadání (umístění modrého a zeleného domu). I přesto by se stále jednalo o hezké řešení, kdyby ... kdyby výsledek nebyl chybný. Ale protože hodnotíme nejen výsledek, ale i postup, placku si zaslouží.
Jan Vargovský - 80 bodů
P4koo odevzdal postupně několik řešení a prozradím na něj, že rozdíl v kvalitě mezi první a finální verzí je obrovský. Program prochází všechny permutace a testuje, zda je zadaná konfigurace možná. Kvůli rychlosti p4koo chytře proházel testování podmínek. Program tedy není příliš generický a kód by mohl být trochu čitelnější. I přesto si myslím, že p4koo předvedl úžasný pokrok v duchu Devbooku, naučil se nové věci a vydal ze sebe to nejlepší. Za to ode mě dostal o 10 bodů více.
Petr Gürth - 80 bodů
Petr napsal program, který nejen řeší úlohu, ale usměvavý Santa vás navíc také rozesměje. Petrovo řešení je šité na míru a programu trochu napovídá - některé věci, které program "ví", nebyly v zadání, ačkoliv je kód mazaně ukrytý v pořadí prováděných pravidel. Jako takové plus a mínus bych ohodnotil komentáře. Ano, komentáře tam jsou, ale moc mi při čtení nepomohly více než názvy metod. Body jsou přesto zasloužené.
Hartrik - 95 bodů
Hartrik vytvořil asi nejhezčí řešení. Bohatě stylovaná aplikace, vlastní parser pro české zadání je zajímavý nápad a řešení algoritmu je dostatečně generické a stále deterministické. Kód je navíc pěkně navržený a rozmyšlený a hlavně - okomentovaný! V závěrečném rozhodování tak musely rozhodovat maličkosti. Hartrikovo řešení má totiž jednu chybu - pro výpočet řešení používá 50 cyklů a pokud hodnotu přesáhne, skončí. To lze udělat jinak a lépe. Nicméně stále se jedná o favorizované řešení, které byste si měli prostudovat. Takhle má vypadat soutěžní řešení.
Silvinios - 98 bodů
Když Silvinios dostane za úkol postavit na jezero vor, postaví si za chatou válečný křižník. Asi takhle bych charakterizoval jeho řešení. Vlastní deklarativní jazyk, generické definice relací a domény, deterministické hledání výsledku. Programu bych vytknul zbytečnou složitost na úrovni tříd - méně je někdy více. Také některé metody by si zasloužily rozdělit na více částí nebo alespoň okomentovat. Rozluštit, jak přesně funguje tenhle křižník, mi chvíli trvalo a autor se mi to nesnažil zjednodušit, za to šly symbolické 2 body dolů.
Malé zklamání je v tom, že ani jedno z řešení nepředvedlo, jak
počítač "uvažuje" - jaká pravidla použil, mezivýsledky nebo kolik kroků
potřeboval. V případě hádanky je přece vždycky dobré vědět, jak se
dojde k řešení. Přesto mám z dodaných řešení velikou radost a těším
se zase za rok
Finální hodnocení
I když Hartrikovo řešení je přesně takové, jak bych si představoval, absolutním vítězem se stal Silvinios. Jeho řešení bylo jediné, do kterého jsem si velice snadno napsal úplně jinou hádanku - a dostal jsem správný výsledek. Gratulujeme!
V rámci vánočního machra se navíc David Čápka rozhodl ocenit plackou všechna řešení! Jemu chci také poděkovat, že mi pomohl zorganizovat tuhle soutěž. Byla to opravdu zábava.
Všem děkujeme za účast, vítězové nechť publikují výtvory a napíší x jako obvykle.
Juraj Mlich:8.12.2013 14:04
Ja som to tak pôvodne mal, len sa tam vyskytla mala chyba a nevedel som ako
to riešiť. Tak som to nakoniec o 21:00 celé vymazal a spravil nanovo
Petr Gürth:8.12.2013 15:18
Já jsem to dal k publikaci. Snad nevadí, že jsem byl třetí
Zobrazeno 74 zpráv z 74.