Zadanie

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

A už ich je toľko, že ich vedúci nestíhajú spraviť sami. Je preto vašou morálnou povinosť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 spraví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

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 :). Ak ste si nepreriešili úlohy minulých sérií, môžete si prejsť aj tie.

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 2.4 dostanete 1 bod a za každý level v sérii Prask 2.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 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ť.

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 ú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

 

 

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

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