Obcházení bludiště podél okraje

Tohle je rozehřívací úloha. Chceme, aby robot obešel vnější zeď bludiště – třeba proti směru hodinových ručiček, to je jedno.. Doufáme totiž, že někde na okraji je cíl.

V každém kroku robot stojí na pozici x, y a ví, kterým směrem se smí pohnout a kde naopak je zeď. Náš program musí určit, jakým směrem se má robot vydat.

Paměť

Když je robot v těsné chodbě, měl by nejdřív projít na konec, ujistit se, že tam není cíl, a pak se vrátit zpátky. Chodba je tak úzká, že při návratu robot musí projít přesně přes políčka, kde už byl. Náš program tedy zjevně jednou robotovi radí, aby pokračoval do chodby, a podruhé ho posílá pryč. To znamená, že si robot něco pamatuje a rozhoduje se podle toho, anebo že se chová náhodně. Náhodné chování v bludišti bývá dost nebezpečné, radši se tedy podívejme na tu paměť.

Aby robot správně našel cestu podél okraje, stačí mu úplně malý kousek paměti: musí vědět, ze kterého směru přišel. Náš program si tedy musí někam poznamenat svůj výsledek, aby se na něj v příštím kroku mohl podívat. Úlohu by šlo řešit mnoha jinými způsoby, ale málokterý je tak jednoduchý.

Rozhodování

Cesta podél okraje znamená, že položíme pravou ruku na zeď a jdeme dopředu. Když dojdeme na roh, zkusíme zatočit doprava. Pokud to nejde, zkusíme jít rovně, pak doleva a když ani to nejde, vrátíme se zpátky. Pojmy "doprava", "rovně", "doleva" a "zpátky" si musíme vypočítat na základě směru, ze kterého jsme přišli v předchozím tahu.

Než začneme psát kód, všimneme si, že směry zkoušíme v pořadí, jak jsou očíslované. Například, pokud jsme v předchozím tahu šli ve směru 1 (západ), vyzkoušíme postupně směr 0 (sever), pak 1 (západ), pak 2 (jih) a pokud i tam je zeď, vrátíme se směrem 3 (východ). Namísto spletitých podmínek if (...) else můžeme celý kód vyřešit jedním for cyklem, který postupně vyzkouší všechny čtyři možnosti. Protože navíc víme, že za zády zeď není, nemusíme ani počítat do čtyř. Prostě, začneme ve směru doprava, a dokud se díváme do zdi, otáčíme se směrem vlevo. Když před námi už zeď není, jdeme tím směrem.

Směr pohybu si uložíme třeba do proměnné stav.s. Na začátku tedy nastavíme stav = {s: 2}, aby robot začal směrem dolů. Samotný kód programu je velmi stručný:

Řešení. for (stav.s += 3; zdi[stav.s % 4]; stav.s++) {} return stav.s % 4;

Pamatujeme si jenom směr jízdy, žádná další proměnná není potřeba. Symbol procenta znamená dělení se zbytkem, a zajišťuje, aby vždycky vyšlo číslo od 0 do 3. Všimněte si, že otočku doprava neděláme odečtením jedničky (což by se nabízelo), ale přičtením tří: zbytek po dělení čtyřmi vyjde v obou případech stejný, ale kvůli zmatkům v Javascriptu nám bude pohodlné se vyhnout záporným číslům.

Vyzkoušejte si to.

Nejkratší cesta v bludišti

Tentokrát chceme najít cestu robota do cíle, který může být kdekoliv. Půjdeme na to oklikou: napíšeme funkci, která najde cestu přesně dané délky. Pak postupně vyzkoušíme, jak dlouhou cestu musíme dovolit, aby to začalo fungovat.

Protože tahle úloha je výrazně složitější, smíme se během plánování dívat kamkoliv do bludiště, nejen do okolí robota. (Jinak by řešení bylo zbytečně zamotané a nezajímavé.) Konkrétně v příkladu dostaneme funkci teren(x, y), kde x a y jsou souřadnice oproti levému hornímu rohu. Funkce vrací true, když na daném místě je zeď.

Napíšeme funkci najdi(x, y, vzdalenost), která hledá cestu délky vzdalenost. Můžou nastat čtyři varianty:

  1. už jsme v cíli, není kam hledat cestu. Funkce vrátí cokoliv optimistického, třeba true;
  2. nejsme v cíli, ale hledáme cestu vzdálenosti 0. Funkce vrátí false, jako že selhala;
  3. vzdálenost je 1 nebo vyšší. Funkce zkusí najít o jedno políčko kratší cestu postupně ze všech sousedních polí, a pokud se to někde povede, vrátí kód toho směru;
  4. předchozí krok se nepovedl, ani jedno ze sousedních polí nevede do cíle. Funkce vrátí false, jako že selhala.
Varianta (3) používá rekurzi – funkce se na řešení zeptá sama sebe. Ostatní varianty vlastně jen zajišťují, aby se rekurze neutrhla z uzdy.

Řešení. function najdi(x, y, vzdalenost) { if (x == cx && y == cy) { return true; // (1) } else if (vzdalenost == 0) { return false; // (2) } for (var i=0; i<4; i++) { var nx = x + [0, -1, 0, 1][i], ny = y + [-1, 0, 1, 0][i]; if (!teren(nx, ny) && najdi(nx, ny, vzdalenost - 1) !== false) { return i; // (3) } } return false; // (4) } for (var vzdalenost=0; ; vzdalenost++) { var vysledek = najdi(x, y, vzdalenost); if (vysledek !== false) { return vysledek; } }

Cache

Když výše popsaný program zkusíte použít na hledání cesty dlouhé třeba 15 kroků, potrvá to už odporně dlouho. Problém je v tom, že každým krokem se počet zkoumaných možností čtvernásobí, takže po patnácti krocích už je to přes milion variant k prozkoumání. Tolik možností samozřejmě nemá smysl zkoušet. Když hledáme cestu délky 20 v bludišti 50 × 50, můžeme funkci najdi volat nanejvýš 5000 různými způsoby, a to je bez potíží zvladatelné číslo. Stačí si zavést paměť, a vyhnout se tomu, abychom tentýž výsledek počítali podruhé znovu.

Drobný technický zádrhel spočívá v tom, že javascriptové slovníky (objekty) se indexují číslem nebo řetězcem, ale nejdou indexovat třemi čísly, jak by se nám hodilo. Je víc způsobů, jak z toho vykličkovat. Pro stručnost zvolíme ten následující: tři čísla zabalíme do řetězce a napíšeme mezi ně čárku. Takhle:

var k = x + "," + y + "," + vzdalenost;

Původní funkci přejmenujeme na najdi_pomalu, abychom ji nespustili omylem. Napíšeme místo ní funkci najdi, která si bude pamatovat výsledky z dřívějška, a jenom když výsledek nezná, zeptá se původní funkce najdi_pomalu. V rekurzivním volání i v cyklu pro nejmenší vzdálenost tedy má zůstat funkce najdi, aby program běžel rychle.

Řešení. function najdi(x, y, vzdalenost) { var k = x + "," + y + "," + vzdalenost; if (stav[k] === undefined) { stav[k] = najdi_pomalu(x, y, vzdalenost); } return stav[k]; }

Nezapomeňte ještě nastavit při každé změně bludiště stav = {}, aby se vám nepletly výsledky z dřívějška. Můžete to dopsat třeba na začátek funkce vyrob_teren.

Tenhle fígl se dá použít v mnoha jiných případech. Velmi obecně řečeno, koupili jsme si rychlost výpočtu výměnou za místo v paměti. Patří se ještě rýpnout, že to byl obchod dost neuvážený, protože program by mohl běžet mnohem rychleji a paměť šetřit.