1. Prastarý nález 3 vzorové riešenie

1 - Riedke bludisko

Jeden z možných spôsobov, ako dôjsť do cieľa, je ísť vždy čo najdlhšie rovno a keď prídeme ku stene, otočiť sa doprava. To vieme s pomocou nekonečnej rekurzie (Obr. 4 v študijnom texte o rekurzii) zapísať napríklad takto:

funkcia0

aha funkcia0:
doprava ak je stena vpredu
krok
funkcia0

2 - Hrebeň

Keďže tlačidlá sú v rôznych zuboch hrebeňa rôzne ďaleko, budeme potrebovať funkciu, ktorá robotom pohne po najbližšie zapnuté tlačidlo. Tá môže vyzerať takto:

aha funkcia0:
krok
funkcia0 ak nesvieti

Táto funkcia sa teda bude volať a hýbať robotom, až kým nestúpi na tlačidlo. V tom okamihu nebude platiť podmienka ak nesvieti, teda funkcia sa už znovu nezavolá a robot zastane. Takýto druh rekurzie sa nazýva chvostová rekurzia. Podobne si môžeme napísať funkciu, ktorá robotom pohne po najbližšiu stenu:

aha funkcia1:
krok
funkcia1 ak nie je stena vpredu

S pomocou týchto dvoch funkcií už ľahko napíšeme funkciu, ktorá vstúpi do zubu, nájde tlačidlo, stlačí ho, otočí sa a presunie sa k spodnej stene, kde sa rekurzívne zavolá. Musíme si však dať pozor, aby bol robot pri rekurzívnom volaní v takej istej situácii ako na začiatku, čo bude znamenať, že musí skončiť postavený na (teraz už vypnutom) JetTorch-i otočený doprava.

aha funkcia2:
krok
dolava
funkcia0
prepni
dolava
dolava
funkcia1
dolava
krok
funkcia2

V hlavnom programe nám stačí zavolať funkcia2.

3 - Zeleno-modrá cesta 2

Pred čítaním tohto riešenia vám odporúčam prečítať si vzorové riešenie levelu Zeleno-modrá cesta (posledný level v predošlej úlohe).

Podobne ako pri prvej zeleno-modrej ceste platí, že stav prepínača určuje, ktorým smerom z neho máme ísť:

• Z vypnutého tlačidla treba ísť dva kroky na sever.
• Zo zapnutého tlačidla treba ísť dva kroky smerom na východ.
• Z ukradnutého tlačidla (miesto, kde by malo byť tlačidlo, ale nie je) treba ísť dva kroky smerom na juh.

Podobne ako v zeleno-modrej ceste si snapíšeme funkciu, ktorá urobí dva kroky správnym smerom, otočí sa na východ a potom zavolá sama seba.

Tu ale narazíme na problém: ako vieme rozlíšiť ukradnuté tlačidlo od vypnutého, keď pre obe platí, že nesvietia? Jednoducho tak, že sa ho pokúsime prepnúť. Ak je po prepnutí zapnuté, znamená to, že bolo iba vypnuté. Ak stále nie je zapnuté, znamená to, že je ukradnuté. Kód by teda vyzeral takto:

funkcia0

aha funkcia0:
funkcia1 ak svieti
prepni
funkcia2 ak svieti
funkcia3 ak nesvieti
funkcia0

aha funkcia1:
krok
krok

aha funkcia2:
dolava
krok
krok
doprava

aha funkcia3:
doprava
krok
krok
dolava

Tu ale príde ďalší problém: môže sa stať, že sa v jednom volaní funkcia0 zavolá funkcia2 a potom aj funkcia3 (ak sa vykonaním funkcia2 robot dostane na nesvietiace políčko). Pri volaní funkcia3 pritom už nemusí platiť, že robot je na ukradnutom vypínači, keďže môže byť aj na vypnutom. A naozaj sa to aj stane, už pri treťom vypínači. Preto zaručíme, aby sa v jednom volaní funkcia0 zavolala vždy iba jedna z funkcií 1,2,3. To urobíme tak, že aj na konci každej z funkcií 1,2,3 zavoláme funkcia0 (volanie funkcia0 na konci funkcia0 sa tým pádom stane zbytočným).

4 - Bludisko

Na vyriešenie tohto levelu použijeme algoritmus, ktorý sa nazýva pravidlo pravej ruky a slúži na prehľadávanie bludísk. Je veľmi jednoduchý: na začiatku sa pravou rukou chytíme múru a celý čas ideme pozdĺž neho bez toho, aby sme sa ho pustili. Takýmto spôsobom prejdeme po celom obvode bludiska a buď sa vrátime späť tam, kde sme začali, alebo cestou nájdeme nejaký iný východ z bludiska (čo sa v našom prípade nestane, keďže bludisko iný východ nemá). Všimnime si, že všetky políčka nášho bludiska sa nachádzajú po jeho obvode, teda pravidlom pravej ruky prejdeme cez všetky prepínače.

Pre nášho robota to bude znamenať, že vždy, keď vojde na nové políčko, sa bude snažiť ísť čo najviac doprava. To znamená, že ak vpravo nie je stena, tak pôjde doprava, ak je vpravo stena, tak pôjde rovno, ak je stena aj vpredu, tak pôjde doľava a ak je stena aj vľavo, tak sa vráti, odkiaľ prišiel.

Kód:

funkcia0

aha funkcia0:
krok
prepni ak nesvieti
doprava ak nie je stena vpravo
dolava ak je stena vpredu
dolava ak je stena vpredu
funkcia0

Po tom, čo robot prepne všetky vypínače, pôjde ďalej pozdĺž múru, až kým príde do cieľa.

5 - JetTorchové peklo

Cesta obsahuje štyri rovné úseky, pričom prvý a tretí sú “bezpečné”, keďže sú zakončené stenou, kým druhý a štvrtý sú “nebezpečné”, keďže za nimi nasleduje JetTorch. Kľúčovým pozorovaním tohto levelu je, že každý nebezpečný úsek je rovnako dlhý ako bezpečný úsek pred ním.

Napíšme si teda funkciu, ktorá pôjde po najbližšiu stenu, potom sa otočí doľava a urobí rovnako veľa krokov, ako urobila cestou k stene. Ako začiatok si môžeme zobrať funkciu z levelu 2, ktorá ide po najbližšiu stenu:

aha funkcia0:
krok
funkcia0 ak nie je stena vpredu

Po tom, čo robot príde k stene, sa má otočiť doľava, preto doplníme jeden príkaz:

aha funkcia0:
krok
funkcia0 ak nie je stena vpredu
dolava ak je stena vpredu

Všimnime si, že táto funkcia sa zavolá presne toľkokrát, koľko krokov urobí robot cestou k stene. A to je presne toľko, koľko má urobiť cestou od steny. Tiež si môžeme všimnúť, že žiadne volanie funkcie sa neskončí, kým robot nepríde k stene. To znamená, že ak by robot v každom zavolaní funkcie urobil ešte jeden krok po tom, ako sa otočí pri stene, urobil by presne to, čo potrebujeme. Odporúčam si pozrieť obrázok 5 zo študijného textu. Ak si nakreslíte, ako sa budú vykonávať príkazy, bude vám to oveľa jasnejšie.

Funkcia teda bude vyzerať takto:

aha funkcia0:
krok
funkcia0 ak nie je stena vpredu
dolava ak je stena vpredu
krok

Ak sa vám toto zdalo nezrozumiteľné, môžeme sa na našu funkciu pozrieť aj ako na vysvetľovanie významu slova pomocou toho istého slova. Príkaz “choď rovno po najbližšiu stenu, potom sa otoč doľava a choď rovnako dlho rovno” vieme totiž popísať nasledovne:

1. Najprv urob krok
2. • Ak je už pred tebou stena, otoč sa doľava a urob ešte jeden krok (kvôli kroku, ktorý si urobil v bode 1).
   • V opačnom prípade choď rovno po najbližšiu stenu, potom sa otoč doľava a choď rovno rovnako dlho. Nakoniec urob ešte jeden krok (za krok, ktorý si urobil v bode 1).

A presne to naša funkcia robí.

S touto funkciou bude hlavný kód jednoduchý:

funkcia0
dolava
funkcia0
dolava
krok