Po drátě 3: Řešení úlohy č. 10

Při prvním zadání prakticky čehokoliv zjistíme, že mašinka generuje velkou tabulku s různými symboly. Při bližším pohledu si všimneme dvou věcí: obrázku v levém horním políčku a samotné podoby tohoto políčka.

Pokud nejsme schopni identifikovat obrázek na první pohled (což zejména dříve narození jsou, protože nezačínali na PHP, ale právě na tomto jazyku), podíváme se do zdrojáku stránky a všimneme si, že obrázek se jmenuje robot-karel.png. Případným optáním se strejdy Googla zjistíme, že jde o programovací jazyk Karel. A také jeho základní princip: robot Karel se nachází v mřížce, přičemž se po mřížce umí pohybovat směrem, jakým se dívá, a umí se otáčet.

Náš Karel měl poněkud jinou instrukční sadu než ten originální, přesto na příkazy vpravo, vlevo a krok (případně jejich anglické ekvivalenty) šlo přijít poměrně snadno.

Druhá věc, které jsme si všimli už na začátku (a pokud ne, pak po chvíli pokusů o chození s Karlem už ano), je to, že některé okraje políček jsou obtažené černou čárou a někeré ne. Ano, chudák Karel se nachází v bludišti.

V bludišti je jedno políčko označené vykřičníkem. Zdá se to být cíl. Pokud podnikneme pokus dojít s Karlem k tomuto políčko, zjistíme, že to jde překvapivě snadno a jen s malým blouděním. Dojdeme tedy až na ono políčko, ale místo očekávaného hesla dostáváme jen nápovědu:

Seznam příkazů:
jestart
jezed
konec
krok
nenistart
nenized
vlevo
vpravo
znovu

Co teď? Evidentně je třeba najít nějaké jiné, neoznačené políčko. Nezbývá nám tedy, než projít celé bludiště.

Po chvíli experimentování s instrukční sadou zjistíme, že podmínky (jezed, nenistart, apod.) se vztahují vždy jen k jedné následující instrukci, větve else to evidentně vůbec nezná. Cyklus máme k dispozici jen jeden, a to skok na začátek programu, který ve spojení s některou s podmínek umíme změnit v podmíněný.

Instrukční sada Karla se tedy zdá být poměrně omezená, na jednodušší program by to však mohlo stačit. Největším handicapem je absence zásobníku, nebo vůbec jakékoliv proměnné. Projít tedy bludištěm pomocí backtrackingu nepůjde. Pokud však budeme doufat, že bludiště neobsahuje smyčky (co nám taky jiného zbývá), můžeme použít pravidlo levé ruky. To už naprogramovat lze, například takto:

vlevo
jezed vpravo
jezed vpravo
jezed vpravo
krok
nenistart znovu

Karel sice nenarazil na žádné políčko, které by vypsalo heslo, ale po proběhnutí bludištěm zjišťujeme, že některé části plochy nejsou vůbec dostupné. Tyto části tvoří graficky písmena, která udávají heslo "fyzik".

Komentář

Zdaleka ne všichni řešili úlohu takto přímočaře. Už testeři odhalili, že pokušení řešit úlohu hrubou silou je lákavé. Zde zafungovala jedna ze zabudovaných pojistek: příliš dlouhý program mašinka odmítla vykonávat. I přesto šlo úlohu hrubou silou vyřešit, bylo však potřeba vygenerovat více různých programů, které se rozhodovaly na křižovatkách různě, a tím odkrývaly různé části bludiště. Pak samozřejmě bylo potřeba tyto části bludiště slepit.

Tento postup jsme nechtěli zakazovat, už proto, že dá neskonale více práce než vymyslet program pro Karla. Měli jsme však strach, že nám bruteforcovací skripty přetíží server. Problém byl nakonec vyřešen přepsáním mašinky z PHP do Céčka.

K přepisování mašinky se váže zajímavá historka: Luboš, který úlohu testoval a vyřešil ji hrubou silou, prosazoval, aby byla možnost řešení hrubou silou zachována (jako jedno z možných opatření proti přetížení serveru totiž bylo zvažováno znemožnění takového postupu nastavením šibeničně krátkého limitu na délku programu). Tvrdil, že pokud je potřeba, aby kvůli tomu někdo přepsal mašinku z PHP do něčeho rozumnějšího, že to udělá a přepíše ji do C++. Na to reagovala Anička a v orgovském mailing listu se strhl zajímavý flamedebata, jestli bude rychlejší mašinka přepsaná do C nebo do C++. Vyvrcholilo to sázkou, kterou nakonec nikdo nevyhrál, protože Anička s Martinem přepsali mašinku do C, než se k tomu vůbec Luboš stačil dostat. Protože Lubošův cíl byl splněn (řešení hrubou silou bylo tímto umožněno), mašinka v C++ nikdy nevznikla. Tomu se říká manipulace :-) Debata na mailing listu se následně zvrhla v diskuzi na téma, jak se vlastně liší program v C a program v C++, který nepoužívá objekty. Následovalo hledání nejkratšího céčkového programu, který nejde přeložit cépluspluskovým kompilátorem. My jsme se dostali na 2 znaky, co vy? ;-)

Další pojistkou zabudovanou do mašinky byl čítač kroků, který při příliš dlouhé době běhu programu mašinku zastavil a byla vypsána jen chybová hláška bez zobrazení aktuálního stavu pole. To byla pojistka proti nekonečným smyčkám v programech předhazovaných mašince - nutili jsme vás tím, aby byly vaše programy napsané slušně.

Většina hesel, která mailový robůtek obdržel, byla správná. Pár jich však dávalo tušit, že dotyční zkoušeli hrubou sílu, ale narazili na limit délky programu, takže neměli odkryté celé bludiště a jen hádali:

11:felix
11:fnuk
11:fuck

Autorem úlohy je Jirka Benc, který se s ní docela vyřádil. Během tvorby ho napadly další zajímavé mašinky, takže se máte příště na co těšit :-)

Kdybyste si chtěli prohlédnout, jak mašinka funguje uvnitř, můžete si stáhnout zdroják.