Děkujeme moc za hru! Připravit 27 úkolů, které by splnily očekávání programátorů, logiků i šifrátorů je ohromný kumšt:-) Takže i když některé úlohy třeba mají mouchy a vyřeší je jiný počet týmů, než se očekávalo, tak mě vždycky dostane ten vysoký počet vážně pěkných zadání. Letos namátkou Spirálová slova, Vyvážená, Zásobník na kafe, Nezvestná i ten nápad Systematické (ta má v sobě i minišpetku programátorství).

A pak výrazně potěšily rybičky Los Fillets! Vzpomněl jsem si na ty zoufalé měsíce, kdy jsem nemohl dohrát poslední kola tří větví originální hry:-)

Díky!

Tak já také přispěji svou špetkou do mlýna komentářů k programovacím úlohám :)

P5: Během hry se mi stále nedařilo vidět v tom ty správné stromy, ale ráno se jako obvykle ukázalo být moudřejší večera. Úloha se dá zjednodušit tak, že si domyslím další redukční pravidla, která zredukují KAFE na jeden finální znak. Pak stačí spočítat, kolik existuje redukčních stromů, které mají v kořeni tento znak. Pár-řádkové řešení dynamickým programováním najdete (příštích pár týdnů) zde: http://mj.ucw.cz/tmp/p5.c

Na P1 jsme si také napsali assembler s návěštími. Ze zadání P2 jsme dlouho byli zmatení, nakonec jsme našli několik interpretací, ovšem žádná neodpovídala té autorské. P3 byla mile jednoduchá (čekal jsem mnohem víc generací), P4 taktéž. P6 vypadala děsivě, ale když jsme viděli, jak málo řetězců je zadáno a jak málo se překrývají, napsali jsme backtrack, který doběhl za zlomek sekundy. P7 byla taková jednohubka. P8 nám dala zabrat kvůli zadání (kdo mohl tušit, že na řadu má přijít poslední los, nikoliv první?). P9 je milá hříčka, ale opět překvapilo, jak málo průchodů se provede.

Medvěd

Taky díky a taky přiložím moje řešení (smažou se, až k tomu přestanou lidi/roboti chodit), ať to tady máme ve víc různých jazycích. :-)

P1: Hezká úloha, vyplatilo se napsat si assembler s labelama (http://store.lisk.in/tmp/asm.pl) a přeložit tím program: http://store.lisk.in/tmp/p1.txt P2: Od pohledu haluz, odložil jsem na neurčito a už se k tomu nedostal. P3: Jasné a hezké zadání, trochu času jsem ztratil na zkoumání, proč mi to vychází jinak, čemuž by možná pomohlo říct, kde jsou nízké a kde vysoké bity. http://store.lisk.in/tmp/p3.hs P4: Pro mě jednoznačně nejjednodušší úloha z těch, co jsem dělal: http://store.lisk.in/tmp/p4.hs P5: Špatně jsem si spočítal, kolik to má stavů, takže jsem doufal, že se to dopočítá i hloupě, a nedopočítalo. P6: No a tady jsem si zase myslel, že to nemůžu dělat surově, takže jsem ztratil zbytečně hodně času přemýšlením a Googlením „longests paths“. Nakonec mě cosi navedlo to přece jenom zkusit hloupě: http://store.lisk.in/tmp/p6.hs

P7-P9 dělal kolega. Nachomítl jsem se ještě k S3, u toho se počítač taky dost hodil.

Děkujeme za hru a gratulujeme vítězům. K úspěšnému řešení P5 nám chyběla tak odhadem čtvrthodina. Z toho co jsem viděl přikládám řešení tak, jak mi to odpadlo od klávesnice (po pár týdnech se smaže):

P1 – pěkná exkurze do assembleru až strojáku a nutnosti přepočítávat adresy při každé úpravě kódu. https://www.fi.muni.cz/~kas/tmp/p1.txt

P2 – tady jsme četli zadání několikrát, a pak jsme si řekli, že jsme asi už příliš staří, že už ani nerozumíme, co přesně chce zadání říct (nějaký ten spor order versus ten příklad, už si to moc nepamatuju, prostě nám to nedávalo smysl).

P4 – přímočaré, namapovatelné na regulární výrazy. https://www.fi.muni.cz/…mp/p4.pl.txt

P5 – základní algoritmus jednoduše stanovitelný, problém byl prořezat to nějak tak, aby to bylo upočítatelné. Náš přístup byl brát celý vstup jako načtený, a někam do toho rozmisťovat redukce tak, aby se určitý podřetězec ze začátku redukoval na K, a pak další na další písmena. V tom jsme měli chybu, že určité akce jsme uvažovali chybně víckrát. https://www.fi.muni.cz/…5-bad.pl.txt

P8 – toto měl Honza naprogramované, nemohli jsme v tom najít chybu, tak jsem to ještě jednou naprogramoval já, vycházelo to stejně. Tak jsme přemýšleli co s tím. Ještě se do toho pletly DOSové konce řádků – wc -l říkalo, že je 350 losů (+ hlavička) ale 349 akcí. Po delší době přemýšlení nás napadlo přehodit směr fronty. Povídám „počkej s tím, já se ještě podívám do diskuse“, a fakt tam bylo to, co jsme se zrovna snažili vyzkoušet. https://www.fi.muni.cz/…mp/p8.pl.txt

P9 – poměrně přímočaré, až na ty dvě chyby v zadání. https://www.fi.muni.cz/…mp/p9.pl.txt

S2 – 24 výsečí x 7 okruhů jasně navádělo na hodiny a týden, ale furt to k ničemu nevedlo. Tak to nakonec Honza zkusil seskládat na sebe tak, aby se to nepřekrývalo. Ale teda za mě trojan jaxviňa.

Celkově jsme bohužel strávili ne vlastní vinou na P8 a P9 dost času, který pak programátorské části týmu chyběl. No ale jinak dobrý. Ještě se musím podívat na ostatní úlohy.

PPPPPPPPPost mortem. Jako tradičně jsem ne-P úlohy viděl jen v antidepresivních přestávkách mezi řešením P úloh…

P1: Pro mne cool nový typ úlohy, kde AFAICT ideální řešení zahrnovalo naprogramování vlastního minijazyka. Můj vlastně měl jen jednu zásadní fíčuru – pojmenovaná návěští, která si při ‚kompilaci‘ do jazyka ze zadání sám přepočítal na posuny. Taky jsem uvítal, že testování správnosti bylo nezávislé na zadávání řešení. Ne, že by tak měly vypadat všechny programátorské úlohy, ale občas je to vhodný prvek.

P2: Zadání jsem se poctivě pokusil pochopit, ale asi jako většině mi přišlo, že vkládat čas do tohohle nebude efektivní. Ani na to nemám vyhraněný názor, prostě to tak nějak znělo stylem ‚a v půlce se pak zaseknu, protože neznám nějaký teorém z teorie grafů‘.

P3: Spíš lehká úloha, ale strukturou podle mne jedna z nejlepších. Zamyslet se nad zadáním, zjistit, že jsem vlastně dostal jen idiotsky zadanou permutaci a mám udělat inverzní, a pak už napsat poměrně jednoduchý program, který to správně redukuje a udělá – to mi přišlo jako dobrý poměr mezi analytickou a programovací částí.

P4: Opět lehká, ale opět pěkně založená na zamyšlení, co jsem dostal – a že chci mnohem raději řešit inverzní problém (expandovat abecedu a dívat se, zda nevyjde něco ze zadání), než to rozebírat.

P5: Oceňuji kafe (kdo chodí na TMOU, ví), ale de facto jsem se ani nepokoušel řešit.

P6: Vyřešil jsem tak nějak bez pochopení, co je na ní zajímavého. Poté, co program přesal generovat nekonečný řetězec efkil-lage (protože se nemělo recyklovat), tak prostě vypsal řešení. Čekal jsem, že budu muset vymýšlet efektivní algoritmus, ale nejidiotštější postup, kterým jsem začal, byla dostatečný.

P7: Předpokládám cíleno jako úloha, kterou si může vyřešit každý. Jedna je asi OK.

P8: Největší zklamání. Jako asi řada dalších si myslím, že jsem správně vyřešil, co bylo zadáno – akorát akorát to nějak nebylo, co si autor představoval, že máme dělat. Po přečtení řešení uznávám, že zadání šlo chápat i takhle, ale nepřijde mi napsáno s cílem, aby bylo takhle pochopeno. Abych nebyl jen negativní, jako pěkný twist kontrolující poctivost čtení zadání hodnotím požadavek zadat první jméno, nikoli celé jméno. Ale zase to prosím v tomto směru nepřehánět.

P9: Charakterem asi OK úloha, ale zklamání z toho, že se nic zajímavého nedělo. Těšil jsem se na nějaké zajímavé sekvence a když to po třech číslech skončilo, pojal jsem podezření, že je v programu chyba – a marně ji hledal (ale aspoň přitom našel chybu v zadání :o)

(Yeti)

P7-P9 byla tedy velmi zlá sestava. V podstatě jen „naprogramuj přesně co je v zadání“. Teda s výjimkou toho, že ta zadání jsou povětšinou napsána velmi krypticky až chybně.

Děkujeme za hru! Přijde mi ale trochu smutné, že hned dvě z programovacích úloh měly zásadní chyby v zadání (P2 nebyla podle zadání řešitelná vůbec, v P8 bylo potřeba uhodnout, že pořadí ve frontě je opačné, než pořadí v souboru).

Interlosi afterparty je prave ted v Brne u Drevaka, pridejte se! :)

Kdy bude funkční řešení L1?

P2: proč vzorové řešení spouětí BFS z vrcholu 2 a ne 0? (řádek 86)