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

Tento vzorák bude používať mnohé pojmy a techniky vysvetlené vo vzoráku k predošlej sérii, preto pred jeho čítaním odporúčam prečítať si vzorové riešenia k prvým úlohám z predošlých troch sérií.

1 - Svietiaca cesta

Napíšeme si funkciu, ktorá urobí krok správnym smerom a potom zavolá sama seba. Ako urobiť krok správnym smerom? Jednoducho vyskúšame všetky tri možné smery. Najprv urobíme krok dopredu a skontrolujeme, či sme na svietiacom prepínači. Ak áno, potom to bol krok správnym smerom a môžeme znovu zavolať našu funkciu. V opačnom prípade sa vrátime naspäť a skúsime nejaký iný smer, napríklad doľava (vzhľadom na smer, ktorým sme boli otočení na začiatku volania funkcie). Ak ani tým smerom nebude svietiaci prepínač, vrátime sa a pôjdeme posledným možným smerom, teda doprava. Keďže používame nekonečnú rekurziu, funkcia sa vždy vykoná iba po miesto, kde prvý raz zavolá sama seba, teda sa nám nemôže stať, že by po prvom zavolaní urobila ešte nejaké nežiadúce príkazy navyše. Keďže sa na viacerých miestach programu budeme chcieť vrátiť na políčko, odkiaľ sme prišli, môžeme si na to napísať pomocnú funkciu.

Kód:

funkcia0

aha funkcia0:
krok
funkcia0 ak svieti
funkcia1
doprava
krok
funkcia0 ak svieti
funkcia1
krok
funkcia0

aha funkcia1:
dolava
dolava
krok

2 - Rozsvecovanie

Najjednoduchší spôsob ako zaručene nájsť všetky stĺpy, je prehľadať celú mapu. Skúsme teda najprv napísať program, ktorý by po riadkoch prešiel po celom plániku (podobne ako v leveli 4-Šachovnica z úlohy Prask 1.4 z predošlej série), ak by tam neboli stĺpy. Robotovu cestu môžeme rozdeliť na 4 druhy úsekov: úseky, keď ide na východ, úseky, keď ide na západ, otáčanie pri východnom okraji miestnosti a otáčanie pri západnom okraji miestnosti. Pre každý z týchto druhov si napíšeme jednu funkciu a tieto štyri funkcie vhodným spôsobom necháme volať sa navzájom v nekonečnej rekurzii:

funkcia0

aha funkcia0:
krok
funkcia0 ak nie je stena vpredu
funkcia2

aha funkcia1:
krok
funkcia1 ak nie je stena vpredu
funkcia3

aha funkcia2:
doprava
krok
doprava
funkcia1

aha funkcia3:
dolava
krok
dolava
funkcia0

funkcia0 slúži na cestu na východ: táto funkcia bude hýbať robotom dopredu a volať sama seba dookola, až kým robot nepríde k stene. Potom zavolá funkciu2, ktorá robota otočí (a posunie do ďalšieho riadku) a následne zavolá funkciu1, ktorá slúži na cestu na západ. funkcia1 podobným spôsobom dovedie robota k západnému okraju miestnosti a zavolá funkciu3, ktorá robota otočí (a posunie o jedno políčko na juh) a zavolá opäť funkciu0. Takto sa budú tieto štyri funkcie volať dookola, až kým robot nepríde na spodok mapy.

To je síce všetko pekné, ale na mape sú aj stĺpy, okolo ktorých potrebujeme rozsvietiť prepínače. Najprv, samozrejme, budeme potrebovať vedieť rozoznať stĺpy od okrajov miestnosti. Na to môžeme využiť, že stĺpy sa, na rozdiel od okrajov miestnosti, dajú obísť. Napíšme si teda funkciu, ktorá obíde jeden stĺp:

aha funkcia4:
doprava
krok
dolava
krok
krok
dolava
krok
doprava

Všimnime si, že ak by sme túto funkciu zavolali, keď je tesne pred robotom okraj miestnosti, robot by sa počas jej vykonávania chvíľu pokúšal ísť do steny a nakoniec by skončil tam, kde začal, otočený rovnakým smerom, ako na začiatku (okrem niektorých prípadov, keď robot začínal v rohu miestnosti).

funkciu0 teraz môžeme upraviť nasledovne:

1. Kým pred robotom nie je stena, budeme ním hýbať dopredu.

2. Keď robot príde k stene, pokúsime sa ju obísť (zavoláme funkciu4). Ak to bol stĺp, potom sa nám ho podarilo obísť a teraz už pred robotom nie je stena (tu využívame, že žiaden stĺp nemá dve políčka na východ od seba ďalší stĺp, ani okraj mapy. Ak to bol okraj miestnosti, potom sa nám ho nepodarilo obísť, teda je pred robotom stále stena.

   • Ak je teda pred robotom stena, znamená to, že sme pri východnom okraji mapy, teda môžeme zavolať funkciu2.
   • Ak pred robotom nie je stena, znamená to, že sme práve obišli stĺp. Rozsvietime teda štyri políčka okolo tohto stĺpu a pokračujeme ďalej smerom na východ (znovu zavoláme funkciu0).

Obdobným spôsobom upravíme aj funkciu1. Na rozsvecovanie štyroch políčok okolo stĺpu, pri ktorom stojíme, si môžeme pre lepšiu prehľadnosť kódu napísať pomocnú funkciu. Tú môžeme rozpísať príkaz po príkaze alebo môžeme použiť stručnejšiu verziu využívajúcu chvostovú rekurziu.

aha funkcia0:
krok
funkcia0 ak nie je stena vpredu
funkcia4
funkcia2 ak je stena vpredu
dolava
funkcia5
doprava
funkcia0

aha funkcia1:
krok
funkcia1 ak nie je stena vpredu
funkcia4
funkcia3 ak je stena vpredu
dolava
funkcia5
doprava
funkcia1

aha funkcia5:
prepni
krok
dolava
krok
funkcia5 ak nesvieti

V hlavnom programe nám potom stačí iba zavolať funkciu0.

3 - XOR

Hlavným problémom pri riešení tohto levelu je, že na určenie hodnoty jedného políčka si potrebujeme zapamätať hodnoty z až dvoch iných políčok. Robot si pritom dokáže pamätať iba to, aké funkcie sú práve zavolané (a v akom poradí) a pokiaľ už boli vykonané. A presne to využijeme – informáciu o políčkach budeme kódovať do toho, akú funkciu robot práve vykonáva.

Podobne ako pri predošlom leveli, aj teraz si napíšeme niekoľko funkcií, ktoré sa budú navzájom volať v nekonečnej rekurzii.

Na začiatok budeme chcieť funkciu, ktorá, keď je robot v spodnom riadku, vyvedie ho do horného riadku a zavolá vhodnú nasledujúcu funkciu v závislosti od toho, či políčko v hornom riadku svieti:

aha funkcia0:
dolava
krok
krok
doprava
doprava
funkcia1 ak svieti
funkcia2

Táto funkcia predpokladá, že robot je na začiatku otočený smerom na východ a na konci ho otočí smerom na juh. Potom zavolá buď funkciu1, alebo funkciu2. Nikdy sa nestane, že by sa z jedného volania funkcie0 najprv zavolala funkcia1 a potom aj funkcia2, pretože používame nekonečnú rekurziu a teda funkcia1 (ak ju zavoláme) nikdy neskončí.

Funkciu1 teda voláme v situácii, keď je robot v hornom riadku a stojí na svietiacom políčku. V takom prípade potrebujeme zísť do stredného riadku a zavolať vhodnú nasledujúcu funkciu:

aha funkcia1:
krok
funkcia3 ak svieti
funkcia4

funkciu3 voláme v situácii, keď sme v strednom riadku a obe políčka svietia. V takom prípade políčko v spodnom riadku rozsvietiť netreba, teda sa môžeme presunúť do ďalšieho stĺpca a tam znovu zavolať funkciu0. Funkcia4 sa má správať podobne, s tým rozdielom, že políčko v spodnom riadku rozsvietiť treba.

aha funkcia3:
krok
dolava
krok
funkcia0

aha funkcia4:
krok
prepni
dolava
krok
funkcia0

Funkciu2 by sme mohli napísať rovnako, ako funkciu1, s tým rozdielom, že by volala nejakú funkciu5, ak políčko v strednom riadku svieti a funkciu6, ak nesvieti. Funkcia5 by ale potom vyzerala úplne rovnako ako funkcia4 a funkcia6 by vyzerala rovnako ako funkcia3, preto môžeme rovno využiť tieto dve funkcie:

aha funkcia2:
krok
funkcia4 ak svieti
funkcia3

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

4 - Bludisko s bicyklom

V tomto labyrinte nám, na rozdiel od toho minulého (level 4-Bludisko z úlohy Prask 1.5 z predošlej série), pravidlo pravej ruky stačiť nebude. Namiesto toho použijeme iný algoritmus s názvom prehľadávanie do hĺbky (často sa označuje aj skratkou DFS odvodenou z anglického názvu depth-first search). Tento algoritmus robí presne to, čo potrebujeme: rozsvieti súvislú oblasť nerozsvietených políčok, na ktorej robot práve stojí, pričom na konci nám robota nechá na rovnakom políčku, ako bol na začiatku. Ako to celé funguje? Znovu použijeme princíp vysvetľovania významu slova pomocou toho istého slova:

Ako rozsvietiť súvislú oblasť nerozsvietených políčok, na ktorej práve stojíme (a skončiť pri tom na rovnakom políčku, na akom začíname):

1. Najprv rozsvietime políčko, na ktorom práve stojíme.
2. Ak je pred nami nerozsvietené políčko, vojdeme naň a rozsvietime súvislú oblasť nerozsvietených políčok obsahujúcu toto políčko. Potom sa vrátime naspäť (a otočíme sa rovnakým smerom, ako na začiatku).
3. Ak je teraz naľavo od nás nerozsvietené políčko, vojdeme aj na toto a tiež rozsvietime súvislú oblasť obsahujúcu toto políčko. Potom sa opäť vrátime.
4. Podobne, ak je teraz napravo od nás nerozsvietené políčko.
5. Nakoniec by sme sa ešte mali pozrieť dozadu. Ak však vieme, že odtiaľ sme prišli a teda tam určite nie je nerozsvietený prepínač, tak sa tam pozerať nemusíme.

Pri programovaní tohto algoritmu si treba dať pozor na dve veci:

1. Pri kontrolovaní susedných políčok budeme najprv kontrolovať, či je na danom políčku stena. V prípade, že nie je, budeme potrebovať vykonať sériu príkazov (ísť na dané políčko, skontrolovať, či svieti, atď.). Nemôžeme však každý z týchto príkazov podmieniť tým, či je pred robotom stena, keďže to sa môže už vykonaním prvého z nich zmeniť. Namiesto toho si na celú túto sériu napíšeme pomocnú funkciu, ktorú v prípade potreby zavoláme (a teda sa zaručene vykonajú všetky potrebné príkazy).

2. Musíme si dať pozor, aby sme sa nestratili v tom, ktorým smerom je robot práve otočený. Najjednoduchšie preto bude napísať obe funkcie tak, aby robota vždy vrátili otočeného rovnako, ako ho dostali.

Kód:

krok
funkcia0
dolava
dolava
krok
doprava
krok
krok

aha funkcia0:
prepni
funkcia1 ak nie je stena vpredu
dolava
funkcia1 ak nie je stena vpredu
dolava
dolava
funkcia1 ak nie je stena vpredu
dolava

aha funkcia1:
krok
funkcia0 ak nesvieti
dolava
dolava
krok
dolava
dolava

Dobre, ale prečo to celé funguje?

Nemôže sa stať, že sa funkcie budú volať donekonečna? Nemôže. Všimnime si totiž, že funkciu0 voláme vždy iba na nerozsvietených políčkach, pričom hneď na jej začiatku dané políčko rozsvietime. Políčka nikdy nezhasíname, teda funkciu0 zavoláme najviac toľkokrát, koľko je na začiatku nerozsvietených políčok. Funkciu1 voláme iba z funkcie0, najviac trikrát za jedno volanie funkcie0, teda ju tiež zavoláme iba konečne veľa krát.

Nemôže sa stať, že by sme nejaké políčko nerozsvietili? Nemôže. Predstavme si, že by sa niečo také stalo, teda že by sme nejaké políčko \(X\) nerozsvietili. Vieme, že políčko, na ktorom sme prvý raz zavolali funkciu0 (označme ho \(S\)), sme určite rozsvietili. Predstavme si, že by sme išli z \(S\) do \(X\). Začali sme na svietiacom políčku a skončili sme na nerozsvietenom, teda niekedy cestou sme určite prešli z rozsvieteného políčka na nerozsvietené. Toto svietiace políčko označme \(A\) a susedné nerozsvietené označme \(B\). Keďže \(A\) svieti, určite sme niekedy zavolali funkciu0 stojac na \(A\) (lebo mimo funkcie0 sme nič nerozsvecovali). Počas tohto zavolania sa však robot musel pozrieť aj na políčko \(B\) (ak z neho priamo neprišiel), teda ho určite buď rozsvietil, alebo bolo rozsvietené už predtým. Dostali sme teda nezmysel (políčko \(B\) zároveň svieti aj nesvieti), čiže sa nemôže stať, že by sme nejaké políčko zabudli rozsvietiť.

5 - Ďalšie jet torchové peklo

Vidíme, že budeme potrebovať vypnúť prepínač v severozápadnom rohu. Na to budeme potrebovať povypínať všetky prepínače v strednom rade. Tým si ale pokazíme jet torche v spodnom rade, preto po tom, čo vypneme prepínač v severozápadnom rohu, budeme musieť prepínače v strednom rade uviesť do pôvodného stavu. Potrebujeme si teda nejako zapamätať, v akom stave tieto prepínač boli. Táto informácia je príliš zložitá na to, aby sme ju mohli zakódovať iba do toho, ktorá funkcia bola zavolaná ako posledná. Môžeme však využiť, že robot si pamätá všetky funkcie, ktoré boli zavolané a ešte neskončili. Napíšeme si teda dve funkcie, ktoré sa budú navzájom volať – jednu budeme volať na svietiacich prepínačoch a druhú na zhasnutých. Nepoužijeme však nekonečnú rekurziu, ale chvostovú a pri vynáraní sa z nej budeme prepínače uvádzať do pôvodného stavu.

Ako to bude vyzerať v praxi? Opäť využijeme, že môžeme vysvetľovať slovo pomocou toho istého slova. Od našich dvoch funkcií budeme chcieť, aby sa správali takto:

funkcia0: Za predpokladu, že robot stojí na zhasnutom prepínači \(X\) v strednom rade a pozerá sa na východ, táto funkcia najprv pozhasína všetky políčka od \(X\) na východ, potom pôjde zhasnúť políčko v severozápadnom rohu a následne robota vráti na políčko \(X\), pričom všetky vypínače od \(X\) na východ vráti do pôvodného stavu. Na konci nechá robota otočeného na západ.

funkcia1: Bude robiť v podstate to isté, čo funkcia0, s tým rozdielom, že funkciu1 budeme volať, keď je robot na svietiacom políčku.

A naprogramujeme ich takto:

funkcia0: Najprv urobíme krok dopredu. Potom môžu nastať tri prípady:

1. Ak sme už na východnom konci stredného radu (teda pred nami je stena), potom pôjdeme vypnúť vypínač v
   severozápadnom rohu a vrátime sa naspäť (na toto si napíšeme pomocnú `funkciu2`. Tú napíšeme tak, aby
   po jej skončení robot smeroval na západ).
2. Ak sme na zhasnutom prepínači, môžeme zavolať `funkciu0`. Tá za nás urobí skoro všetkú prácu.
3. Ak sme na rozsvietenom prepínači, môžeme zavolať `funkciu1`.

Nakoniec musíme vo všetkých troch prípadoch urobiť ešte jeden krok, aby sme skončili na rovnakom políčku,
na akom sme začínali.

Keďže už nepoužívame nekonečnú rekurziu, musíme si dať pozor, aby sme naozaj vždy vykonali iba jednu z
týchto troch možností a nie viac po sebe. Preto musíme šikovne nastaviť podmienky:

    aha funkcia0:
    krok
    funkcia2 ak je stena vpredu
    funkcia0 ak nesvieti a nie je stena vzadu
    funkcia1 ak svieti a nie je stena vzadu
    krok

funkcia1: Najprv musíme vypnúť prepínač, na ktorom stojíme. Potom urobíme presne to, čo vo funkcii0. Dokonca ju môžeme priamo zavolať. Úplne nakoniec ešte zapneme prepínač, ktorý sme na začiatku zhasli (keďže máme prepínače vrátiť v pôvodnom stave).

    aha funkcia1:
    prepni
    funkcia0
    prepni

Chýba nám ešte funkcia2. Od tej by sme chceli, aby išla, až kým nepríde na svietiaci prepínač, potom tento prepínač zhasla, robota otočila a vrátila sa o rovnaký počet krokov naspäť. Niečo také sme už robili v leveli 5-Jet torchové peklo z úlohy Prask 1.5 z predošlej série. S tým rozdielom, že vtedy sme sa otáčali, keď bola pred nami stena. Úplne rovnakým spôsobom to urobíme aj teraz. Nesmieme však zabúdať na to, že na ceste máme zákrutu. Cestou tam teda robota pred každým krokom v prípade potreby otočíme doľava a cestou späť ho po každom kroku v prípade možnosti otočíme doprava (takáto formulácia nám zároveň zaručí, že robot bude nakoniec otočený na západ).

aha funkcia2:
dolava ak je stena vpredu
krok
funkcia2 ak nesvieti
funkcia3 ak svieti
krok
doprava ak nie je stena vpravo

aha funkcia3:
prepni
dolava
dolava

V hlavnom programe na začiatku zavoláme funkciu0, po ktorej skončení bude robot na rovnakom políčku ako na začiatku, ale otočený na západ a prepínač v severozápadnom rohu bude vypnutý. Ostatné prepínače budú v pôvodnom stave, teda nám stačí už len odnavigovať robota do cieľa. To je v porovnaní so zvyškom levelu už iba jednoduché cvičenie:

aha funkcia4:
doprava ak je stena vpredu
krok
funkcia4

Hlavný kód teda bude vyzerať takto:

Kód:

funkcia0
funkcia4