Zadanie

Ak máte akékoľvek otázky ohľadom tejto úlohy napíšte Mariánovi Horňákovi na alebo Michalovi Anderlemu na

Keď ste v prvej sérii pomohli pracovitým vedúcim KSP s donáškou kofoly, spohodlneli a stali sa z nich leniví vedúci KSP. Namiesto chodenia na prednášky sledovali pobehujúceho robota a zatiaľčo pili donesenú kofolu, na stoloch sa im kopili domáce úlohy z programovania.

A už ich je toľko, že ich vedúci nestíhajú urobiť sami. Je preto vašou morálnou povinnosťou im pomôcť. Je to predsa vaša chyba, že ste im pomohli prvýkrát a oni z toho zleniveli.

Našťastie, všetky domáce úlohy sa dajú transformovať na mapu pre robotíka Zerga, takže stačí, ak urobíte to, čo minule. A po skončení série môžete dať vedúcim poriadnu prednášku o tom, ako byť produktívny a neprokrastinovať.

Úloha

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äť.

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

Odovzdávanie a bodovanie

V súťažnej sérii bude 5 levelov, každý za 3 body. 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.

Poznámka na záver

Keďže sa vám v minulej sérii tak darilo (a navyše sa ľahké príklady minuli), úlohy v tejto sérii sú mierne obtiažnejšie. Ak sa vám nedarí vyriešiť nejakú úlohu, skúste si (znovu) prečítať vzorové riešenia minulej série. Nájdete tam veľa trikov, ktoré sa dajú znovu použiť. Alebo napíšte vedúcim, ktorí vám skúsia pomôcť.

No a keďže sú úlohy ťažšie, je veľmi náročné ich zoradiť podľa stúpajúcej náročnosti, ako tomu bolo v minulej sérii. To, čo my pokladáme za najťažšie, môže byť pre vás jednoduché a naopak. Pozrite si preto všetky levely a skúste sa nad nimi zamyslieť.

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, aby ste si prečítali vzorové riešenia k úlohám 4 a 5 z predošlej série Prasku, resp. k úlohe Z1 z predošlej série KSP (ak ste ich náhodou ešte nečítali).

1 - Tam a späť

Na prejdenie levelu stačí, aby robot chodil stále rovno a vždy, keď príde na rozsvietený prepínač, prepínač vypol a otočil sa. Napíšeme si teda funkciu, ktorá urobí jeden krok a v prípade potreby vypne prepínač a otočí robota. Túto funkciu potom robota necháme vykonávať dookola v nekonečnej rekurzii.

Narazíme však na drobný problém. Robot počas svojho pohybu chodí aj po už vypnutých prepínačoch, preto ak po vstupe na rozsvietený prepínač najprv prepínač vypneme, robot nemá ako zistiť, že sa má otáčať. To môžeme vyriešiť napríklad tak, že si napíšeme pomocnú funkciu, ktorá prepne prepínač a otočí robota. Túto funkciu potom zavoláme, keď vstúpime na rozsvietený prepínač. Tiež by fungovalo, keby sme robota po vstupe na rozsvietený prepínač najskôr otočili a až potom prepínač vypli.

Kód:

funkcia0

aha funkcia0:
krok
funkcia1 ak svieti
funkcia0

aha funkcia1:
prepni
dolava
dolava

2 - Tam, kde sa skrýval bazilisk

V tomto leveli sa najprv bolo treba trochu pohrať s prepínačmi a zistiť, ako fungujú. Keďže väčšina chodbičiek má dĺžku 3, určite sa nám zíde funkcia, ktorá urobí 3 kroky:

aha funkcia0:
krok
krok
krok

Po troche experimentovania nájdeme spôsob, ako level prejsť. Jednou z možností je obísť celú komnatu v smere hodinových ručičiek začnúc v juhovýchodnom rohu a cestou rozsvietiť všetky prepínače okrem prepínača v severovýchodnom rohu. Môžeme si všimnúť, že tri steny komnaty vyzerajú úplne rovnako, preto sa nám oplatí napísať si funkciu, ktorá začínajúc v rohu prepne prepínač v danom rohu, prejde popri jednej stene (cestou prepne aj prepínač “vo výklenku”) a skončí v ďalšom rohu. Aby sme túto funkciu mohli volať bezprostredne viackrát po sebe, v koncovom rohu sa ešte otočíme doprava:

aha funkcia1:
prepni
funkcia0
dolava
krok
prepni
dolava
dolava
krok
dolava
funkcia0
doprava

S pomocou tejto funkcie potom ľahko napíšeme celý program:

Hlavný kód:

funkcia0
doprava
funkcia0
doprava
funkcia1
funkcia1
funkcia1
funkcia0
dolava
funkcia0
krok

3 - Komprimácia

Najprv si spočítame, že rovné úseky majú postupne dĺžky 9, 4, 7, 13, 4, 6, 15, 6 a 12 krokov. Keďže medzi týmito dĺžkami je dosť veľa násobkov trojky, zíde sa nám funkcia, ktorá urobí 3 kroky. Tiež sa nám tam dvakrát opakuje štvorka, preto si definujeme aj funkciu na urobenie 4 krokov (samozrejme s využitím funkcie pre 3 kroky). S pomocou týchto dvoch funkcií budeme vedieť urobiť 7 krokov na dva príkazy. Keďže máme dva úseky dlhé 6, oplatí sa nám napísať si aj funkciu na 6 krokov. Nakoniec sa nám zíde aj funkcia na 9 krokov – nielenže máme úsek dlhý 9, ale skombinovaním deväť- a štvorkrokovej funkcie vieme na dva príkazy urobiť 13 krokov a skombinovaním deväť- a šesťkrokovej vieme urobiť 15 krokov. Pri definícii každej z týchto funkcií môžeme, samozrejme, využívať tie predchádzajúce. Naše funkcie teda vyzerajú takto:

aha funkcia3:
krok
krok
krok

aha funkcia4:
funkcia3
krok

aha funkcia6:
funkcia3
funkcia3

aha funkcia9:
funkcia6
funkcia3

S pomocou takýchto funkcií vieme ľahko napísať program, ktorý prejde level a spolu s definíciami funkcií má presne 30 príkazov, teda sa akurát zmestí do limitu. Rovné úseky z našich funkcií poskladáme ako 9, 4, \(4+3\), \(9+4\), 4, 6, \(9+6\), 6 a \(9+3\). Toto riešenie sa však dá ešte zlepšiť. Môžeme si totiž všimnúť, že po všetkých úsekoch, kde sme použili funkciu4, nasledovala zákruta doprava. Preto môžeme príkaz doprava pridať na koniec funkcie4 a túto funkciu vždy volať až na konci úseku. Podobne po každom úseku obsahujúcom funkciu6 nasleduje zákruta doľava, preto môžeme príkaz dolava pridať na koniec funkcie6. Tým si ale pokazíme funkciu9 (keďže tá vo svojej definícii používa funkciu6), preto ju musíme prepísať, napríklad takto:

aha funkcia9:
funkcia3
funkcia3
funkcia3

S pomocou takýchto funkcií potom vieme napísať program, ktorý má spolu s definíciami iba 26 príkazov:

Hlavný kód:

funkcia9
dolava

funkcia4

funkcia3
funkcia4

funkcia9
funkcia4

funkcia4

funkcia6

funkcia9
funkcia6

funkcia6

funkcia9
funkcia3

4 - Svetielka

Potrebujeme rozsvietiť 5 prepínačov na východnom konci chodby a zhasnúť 5 prepínačov na západnom konci chodby. Celé to môžeme urobiť napríklad takto:

  1. Najprv prepneme prvých 5 prepínačov.
  2. Potom pôjdeme rovno, až kým nenarazíme na stenu, pričom cestou budeme vypínať všetky svietiace prepínače.
  3. Pri stene sa otočíme.
  4. Pôjdeme až do konca levelu iba rovno.

Prvý bod urobíme veľmi jednoducho: napíšeme si funkciu, ktorá prepne prepínač a urobí krok, túto funkciu potom zavoláme päťkrát.

aha funkcia0:
prepni
krok

Na druhú časť si napíšeme takúto funkciu:

aha funkcia1:
krok
prepni ak svieti
funkcia1 ak nie je stena vpredu

Kým pred robotom nebude stena, táto funkcia sa bude rekurzívne volať dookola. Po príchode k stene sa volať prestane a všetky jej zavolania postupne skončia.

Tretia časť je jednoduchá a na štvrtú časť nám stačí funkcia, ktorá bude v nekonečnej rekurzii robiť kroky:

aha funkcia2:
krok
funkcia2

Hlavný program teda bude vyzerať nasledovne:

Hlavný kód:

funkcia0
funkcia0
funkcia0
funkcia0
funkcia0
funkcia1
dolava
dolava
funkcia2

5 - Tajná kombinácia

Keďže o tajnej kombinácii nič nevieme, nezostáva nám nič iné, ako začať postupne skúšať všetky možné kombinácie. Nemusíme to však skúšať ručne. Namiesto toho si môžeme napísať program, ktorý na hracom pláne postupne vytvorí všetky možné kombinácie, tento program spustiť a potom sa už len pozerať, pri ktorej kombinácii sa jet torch vypne.

Napíšme si funkciu0, ktorá za predpokladu, že je robot otočený smerom na východ, vytvorí na prepínačoch, ktoré sú medzi robotom a východným koncom chodby (vrátane prepínača, na ktorom robotom práve stojí) postupne všetky možné kombinácie, pričom na konci nechá vypínače v rovnakom stave ako boli na začiatku a robot bude stáť na rovnakom políčku ako na začiatku, ale otočený na západ. Tento popis sa vám môže zdať trochu krkolomný, ale neskôr sa nám zíde. Pri programovaní tejto funkcie využijeme princíp vysvetľovania významu slova pomocou toho istého slova.

Ako by takáto funkcia mala vyzerať?

  • V prípade, že je robot na začiatku volania funkcie na východnom konci chodby, je to jednoduché. Máme vytvoriť všetky možné kombinácie na prepínači, na ktorom robot práve stojí. Takéto kombinácie sú iba dve – buď je prepínač vypnutý alebo je zapnutý. V jednom z týchto stavov je na začiatku a do druhého ho jednoducho prepneme. Chceme, aby robot skončil otočený smerom na západ a aby prepínače boli v pôvodnom stave, preto robota ešte otočíme a prepínač prepneme naspäť.
   prepni
   dolava
   dolava
   prepni
  • Prípad, keď robot na začiatku volania funkcie nie je na východnom konci chodby, je trochu zložitejší, keďže sa musíme postarať o väčší úsek prepínačov a teda musíme vytvoriť viac kombinácií. Počet prepínačov navyše dopredu nevieme. Všetky kombinácie však môžeme rozdeliť na dve skupiny: tie, pri ktorých je prepínač, na ktorom robot práve stojí, zhasnutý a tie, pri ktorých je rozsvietený. Najprv vytvoríme všetky kombinácie z prvej skupiny: posunieme robota o jeden krok na východ a zavoláme funkciu0. Tým sa na všetkých prepínačoch východne od začiatočného vytvoria všetky možné kombinácie, teda sme vytvorili všetky kombinácie, pri ktorých je začiatočný prepínač vypnutý. Následne sa vrátime na políčko, kde sme začínali, rozsvietime ho a podobným spôsobom vytvoríme všetky kombinácie, pri ktorých je toto políčko rozsvietené. Nakoniec sa vrátime na začiatočné políčko a opäť ho zhasneme, aby boli na konci volania funkcie políčka v pôvodnom stave.
   krok
   funkcia0
   krok
   prepni
   dolava
   dolava
   krok
   funkcia0
   krok
   prepni

Ešte nejako potrebujeme docieliť, aby sa vždy vykonala tá správna z týchto dvoch možností. To vieme urobiť napríklad tak, že každú z týchto možností dáme do inej pomocnej funkcie a vo funkcii0 sa iba rozhodneme, ktorú z týchto dvoch funkcií zavoláme. Pritom si, samozrejme, musíme dať pozor, aby sa nám nestalo, že po zavolaní prvej (a s tým súvisiacej zmene situácie) sa zavolá aj druhá.

Kód:

funkcia0

aha funkcia0:
funkcia1 ak je stena vpredu
funkcia2 ak je stena vlavo

aha funkcia1:
prepni
dolava
dolava
prepni

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

Po tom, čo nájdeme správnu kombináciu, je už riešenie jednoduché:

Kód:

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

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ť.