Tento týden jsme pro vás připravili velkou předvánoční
programátorskou soutěž!
A protože se vánoce kvapem blíží, bude tentokrát nejlepší dílko
oceněno nejen plackou, ale i knihou, která by neměla chybět v knihovně
žádného programátora.
Jedná se o "Umění programování - 1. díl" od D.E. Knutha, otce a de facto
zakladatele moderní analýzy algoritmů. http://neoluxor.cz/…-dil--15741/
Co bude vaším úkolem?
Musíte napsat program, který pomůže vyřešit velkou Santovu vánoční
hádanku.
Mějte však na paměti, že snadné řešení nemusí být to, které získá
hlavní cenu.
Váš program může být v libovolném jazyce, pokud je volně dostupný
interpret nebo kompilátor.
Program by také neměl mít k dispozici žádné další informace kromě
těch, které jsou přímo v zadání.
Body navíc můžete získat za hezké a elegantní řešení.
Body dolů půjdou za chyby v kódu, dlouhou dobu výpočtu nebo specializovaná
řešení, která se zhroutí při malé změně zadání.
Svá řešení posílejte jako soukromou zprávu na účet
coells
Poslední termín na odevzdání řešení je 6.12.2013.
A teď už k samotné úloze - napište program, který vyřeší
následující úlohu:
Santova hádanka
Santa má z vánoc velkou hlavu.
Od té doby, co má svůj seznam dětí uložený v počítači, to jde od
deseti k pěti.
Zrovna tenhle týden se počítač zhroutil a Santovi skřítci-administrátoři
zachránili pouze část dat.
Santa ví, že:
V ulici je pět domů, každý dům má jinou barvu.
V každém z pěti domů je dítě, které se jmenuje jinak než
ostatní.
Každé dítě má svůj oblíbený nápoj, vlastní jiného mazlíčka a k
vánocům dostane jiný dárek.
A protože jedno z dětí celý rok jenom zlobilo, dostane k vánocům pouze
uhlí!
Otázka: Které z dětí tak moc zlobilo?
Data, která se podařilo zachránit, obsahují:
Tonda žije v bílém domě
Maruska si k vánocům přeje počítačovou hru
Pepík nejraději pije fantu
Žlutý dům stojí hned nalevo od zeleného
Dítě ve žlutém domě pořád pije pepsi
Dítě, které chová hada, chce k vánocům kopací míč
Dítě v červeném domě chová psa
Dítě žijící v prostředním domě pije sprite
Anička žije v prvním domě
Dítě, které chová křečka, žije vedle dítěte, které si přeje
stavebnici
Dítě, které dostane ponožky, žije vedle dítěte, které chová
psa
Dítě, které chová rybičky, nejraději pije džus
Petřík chová kočku
Anička žije vedle modrého domu
Dítě, které chová křečka, žije vedle dítěte, které pije jenom
coca-colu
Autoři správných řešení získávají placku a samolepky, jak je u
soutěží zvykem. Autor nejlepšího řešení navíc získává slavnou knihu
Umění programování. Dokážete hádanku vyřešit?
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.
....při malé změně zadání. Čo myslia pod tým zadaním? to do programu
napíšu tie všetky otázky a podla toho to ma program vypisat? alebo ako? tie
otazky sa nejako zmenia ?
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.
Napísal si: " Když hodnotím řešení, rád mu trochu změním vstupní
hodnoty (klidně i nesmyslně)..."
Chcem sa spýtať, či sa môže zmeniť aj počet domov(5) a počet
vlastností(5*5), alebo len samotné vlastnosti?
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)
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.
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ží.
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 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 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í.
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.
Já bych chtěl poděkovat za celý devbook coellsovi, že
zorganizoval zajímavou soutěž, která všem zúčastněným jistě hodně
dala a hlavně že věnoval knihu za 1000 korun jako cenu. Jsem rád, že tu
jsou lidi jako ty, vždycky mě nakopnete k další aktivitě a k tomu, abych se
o síť dál staral.
Princip mého řešení není složitý. Z tabulek všech možných
kombinací se postupně vyškrtávají možnosti, které jsou nepřípustné.
Stejným způsobem bych řešil úlohu na papíře.
Nejtěžší pro mě bylo vymyslet, jak si poradit s informacemi typu:
Anička žije vedle modrého domu. Hodně úsilí mě stálo program
odladit.
Uvažoval jsem, že by program vypisoval své myšlenkové pochody, jak
píše coells, ale nakonec jsem to zavrhl. Připadalo mi to příliš pracné.
Jednotlivých logických kroků bylo docela dost.
Komentáře jsem do kódu nepsal žádné, abych ušetřil čas.
Ak by čiste náhodou zaujímalo ako šialene som to skúšal ja, nech sa
páči: https://www.dropbox.com/…aHadanka.zip
Mám tam len logiku umiestnenia presných daných hádanky, teda:
8. Dítě žijící v prostředním domě pije sprite
9. Anička žije v prvním domě
14. Anička žije vedle modrého domu
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.