Zadanie

Pracovitým KSP vedúcim študujúcim na Matfyze, počas písania nových zadaní poriadne vysmädlo. Avšak, sú príliš zaneprázdnení na to, aby si šli kúpiť kofolu. Postavili si preto robota, ktorý kofolu prinesie namiesto nich.

Matfyz je ale miesto veľmi zradné1. Niekedy na kľukatých chodbách z podlahy šľahá oheň (to je bežné, tak sa tam totiž kúri) a preto robot prechádzajúci takým miestom musí najskôr kúrenie pomocou tlačítka vypnúť. Vieš im pomôcť tohoto robota naprogramovať?

Úloha

Táto úloha je viac hra ako úloha, budete sa hrať s robotom a snažiť sa ho navigovať naprieč Matfyzom.

Dostanete prístup k programovaciemu rozhraniu robota, spolu s náhľadom na level. V tomto rozhraní môžete pomocou jednoduchého programovacieho jazyka napísať pre robota program. Po napísaní si program môžete hneď aj spustiť, a uvidíte ako sa robot vďaka nemu pohybuje.

Vašou úlohou bude napísať program, pomocou ktorého robot bez ujmy na obvodoch prejde bludiskom. Samozrejme mu musí vydržať batéria a stačiť pamäť.

Hra má niekoľko sérií, jednou z nich je aj Tutoriál. Ten je pre riešiteľov KSP-Z nebodovaný, ale odporúčame si ho prejsť, pomôže zžiť sa s jazykom :).

Celý návod k hre ako aj k programovaciemu jazyku nájdete v hlavnom menu hry, kliknutím na tlačítko Návod.

Odovzdávanie a bodovanie

Hra má dve súťažné série po 5 levelov. Za každý level v sérii Prask 1.4 dostanete 1 bod a za každý level v sérii Prask 1.5 dostanete 2 body. Levely môžete riešiť v ľubovoľnom poradí. Akonáhle spustíte správny program a robot sa s jeho pomocou dostane do cieľa, budú vám automaticky pripísané body za daný príklad. To znamená, že k tejto úlohe nie je nutné odovzdávať žiaden popis alebo tradičným spôsobom odovzdávať program.

Hru nájdete na stránke https://www.ksp.sk/specialne/ksp/32/3/1/.


  1. Balkóny dvojnásobne

1 - Komnata

Tu stačilo robota odnavigovať na správne tlačidlo, prepnúť ho a odnavigovať do cieľa. To, ktoré tlačidlo je správne, sa dalo zistiť napríklad tak, že ste postupne vyskúšali všetky. Bolo to tretie tlačidlo zdola.

Kód:

doprava
krok
krok
doprava
krok
prepni
doprava
krok
krok
doprava
krok
krok
krok

2 - Učko

V tomto leveli je na prvý pohľad jasné, čo má robot urobiť. Problém ale je, že nemá dosť pamäte na všetky príkazy. Môžeme si však všimnúť, že U-čko sa skladá z troch rovnakých častí. Napíšeme si teda funkciu, ktorá nám prejde jednu časť U-čka a túto funkciu potom zavoláme trikrát zasebou. Treba si však dať pozor, aby bol robot po dokončení jedného ramena U-čka správne otočený, na konci funkcie ho preto otočíme doprava.

Kód:

funkcia0
funkcia0
funkcia0

aha funkcia0:
krok
prepni
krok
krok
doprava

3 - Schody

Potrebujeme prejsť veľa rovnakých schodov, preto sa nám oplatí napísať si funkciu na prejdenie jedného schodu:

aha funkcia0:
krok
doprava
krok
dolava

Teraz však narazíme na problém: môžeme použiť už iba dva príkazy a schodov je oveľa viac, než dva.

Použijeme preto jeden zaujímavý trik: napíšeme funkciu, ktorá prejde jeden schod a potom zavolá sama seba. Keď sa táto funkcia začne vykonávať, prejde jeden schod a sama sa zavolá znovu. Opäť prejde jeden schod a znovu sa zavolá. A takto bude náš program pokračovať až donekonečna, resp. kým robotovi nedôjde batéria, alebo nepríde do cieľa.

Kód:

funkcia0

aha funkcia0:
krok
doprava
krok
dolava
funkcia0

Ako už viete zo študijného textu, tento princíp sa volá rekurzia. V našom prípade ide o nekonečnú rekurziu, čo pekne vystihuje Obr. 4. Na našu funkciu0 sa môžeme pozerať tak, že je to funkcia, ktorá prejde nekonečne veľa schodov. Urobí to tak, že najprv prejde jeden schod (prvé 4 príkazy) a potom ešte nekonečne veľa ďalších (posledný príkaz).

4 - Šachovnica

Najjednoduchšie asi bude ísť po riadkoch a cestou prepnúť správne políčka.

Zamýšľaná trajektória

Zamýšľaná trajektória

Existuje viacero spôsobov, ako prejsť takúto cestu. Jednou z možností je napísať si štyri funkcie, ktoré sa navzájom volajú v nekonečnej rekurzii. My si ale vystačíme aj s niečím jednoduchším.

Budeme potrebovať, aby robot prepol prepínač na každom druhom políčku, cez ktoré prejde. Napíšme si teda funkciu, ktorá prejde dve políčka, pričom to, na ktoré stúpi skôr, prepne:

aha funkcia0:
krok
prepni
krok

S jej pomocou si môžeme napísať funkciu, ktorá prejde jeden riadok šachovnice a prepne pri tom potrebné políčka za predpokladu, že štartujeme na tom konci riadka, ktorý nemá byť zapnutý:

aha funkcia1:
funkcia0
funkcia0
funkcia0
funkcia0

Všimnime si, že táto funkcia sa po zapnutí posledného prepínača v riadku bude snažiť urobiť ešte jeden krok. To nám ale neprekáža, robot sa iba pokúsi urobiť krok do steny (alebo na JetTorch, ktorý už v tom čase bude vypnutý).

Aj na prejdenie ľavotočivej a pravotočivej zákruty si môžeme napísať funkcie:

aha funkcia2:
dolava
krok
dolava

aha funkcia3:
doprava
krok
doprava

Na ceste, po ktorej má robot prejsť, sa striedajú rovné úseky a zákruty, pričom zákruty sú striedavo ľavotočivé a pravotočivé. Napíšme si teda funkciu, ktorá nám prejde dva rovné úseky a zákruty nasledujúce po nich:

aha funkcia4:
funkcia1
funkcia2
funkcia1
funkcia3

Keď túto funkciu zavoláme štyrikrát po sebe, robot by mal prejsť celú šachovnicu. Problém ale je, že po prejdení posledného riadka sa bude snažiť prejsť ešte jednu pravotočivú zákrutu. Preto ju radšej zavoláme iba trikrát a posledné dva rovné úseky (aj so zákrutou medzi nimi) rozpíšeme. Robot by potom skončil na políčku s JetTorchom (nezabúdajte, že funkcia1 sa po prejdení riadka snaží urobiť ešte jeden krok), preto na koniec pridáme ešte jeden krok.

Hlavný kód:

funkcia4
funkcia4
funkcia4
funkcia1
funkcia2
funkcia1
krok

5 - Zeleno modrá cesta

Kľúčovým pozorovaním v tomto leveli je to, že po zapnutom tlačidle treba ísť najbližšie dva kroky smerom na juh a po vypnutom prepínači treba ísť najbližšie dva kroky smerom na východ. Po urobení dvoch krokov správnym smerom sa bude robot nachádzať na nasledujúcom prepínači.

Tiež si môžeme všimnúť, že máme povolených iba veľmi málo príkazov. Preto opäť využijeme nekonečnú rekurziu: napíšeme si funkciu, ktorá (za predpokladu, že robot stojí na prepínači) urobí dva kroky správnym smerom, a potom sa zavolá znovu.

Tu ale narazíme na jeden problém: robot nevie zistiť, ktorým smerom je práve otočený, teda nebude vedieť, ktorým smerom je východ a ktorým smerom je juh. To môžeme vyriešiť tak, že vždy potom, čo robot prejde na ďalší vypínač, sa otočí na východ (teda ak išiel na juh, otočí sa doľava a ak išiel na východ, ostane tak, ako je). Na to si ale bude musieť pamätať, či bolo predošlé tlačidlo stlačené alebo nie. To docielime tak, že namiesto toho, aby sa robot na tlačidle iba otočil alebo neotočil (podľa toho, či je zapnuté) a potom urobil dva kroky, sa na tlačidle zavolá buď funkcia, ktorá urobí dva kroky smerom na východ, alebo funkcia, ktorá urobí dva kroky smerom na juh a potom sa otočí na východ.

Kód:

funkcia0

aha funkcia0:
funkcia1 ak svieti
funkcia2 ak nesvieti
funkcia0

aha funkcia1:
doprava
krok
krok
dolava

aha funkcia2:
krok
krok

Počas behu programu si môžeme všimnúť, že niekedy sa v jednom volaní funkcie0 zavolá aj funkcia1 aj funkcia2 (nastane to vtedy, keď je robot na zapnutom tlačidle ale po vykonaní funkcie1 sa ocitne na vypnutom tlačidle). To nám v našom prípade neškodí, ale keby sme chceli, aby sa v jednom volaní funkcie0 zavolala vždy iba jedna z funkcií 1 a 2, mohli by sme to docieliť napríklad tak, že by sme funkciu0 zavolali aj na konci funkcie1, teda v prípade, že tlačidlo bolo zapnuté, by sa ani netestovalo, či sa má spustiť funkcia2.

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á vsúpi do zubu, nájde tlačítko, 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) JetTorchi otočený doprava.

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

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

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, napíšeme si 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í funkcie0 zavolá funkcia2 a potom aj funkcia3 (ak sa vykonaním funkcie2 robot dostane na nesvietiace políčko). Pri volaní funkcie3 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í funkcie0 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 funkciu0 (volanie funkcie0 na konci funkcie0 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 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ú pri 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, bude sa 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ž 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ľko krá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
    • 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

Ak vás zaujíma viac o rekurzii, prečítajte si študijný text o nej na strane 7 vzorových riešení Prasku, ktoré nájdete na adrese prask.ksp.sk/ulohy/solutions_pdf/6.

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.