3. týždeň

Problem Set 1: Karel the Robot

Ciele

  1. Ukázať, ako ste si osvojili algoritmické zmýšľanie a prácu s robotom Karlom.
  2. Naučiť sa systematicky vytvárať návrh programu, program a komentáre.
  3. Osvojiť si prácu so systémom na správu verzií git .

Git

Predtým, než začnete pracovať na zadaní, zoznámte sa so systémom Git, pomocou ktorého prebehne odovzdanie tohto zadania (a neskôr aj odovzdanie ďalších zadaní). K dispozícii máte krátke cvičenie, v rámci ktorého nastavíte systém Git: Version Control.

Upozornenie

Vytvorte si v GitLab-e nový projekt prostredníctvom aplikácie ZAP Gitlab Classroom podľa postupu uvedeného tu: Version Control.

Úloha 1: Orientačný beh

Robot Karel sa rozhodol zúčastniť ďalšej disciplíny na olympiáde. Aj tentokrát pobeží cez prekážky, ktoré sú rôzne vysoké, rôzne široké a rôzne od seba vzdialené. Avšak keď nájde značku, zodvihne ju a cez prekážky sa vráti naspäť na svoju východziu pozíciu.

Nezabudnite, že v rámci celého tohto zadania nie je povolené používať premenné.

Pri odovzdaní Vášho programu použite vo funkcii turn_on() názov mapy task_1.kw.

Počiatočná situácia

Na začiatku sa robot Karel nachádza niekde na prekážkovej trati, otočený smerom na východ.

 CORNER  FACING  BEEP-BAG  BEEP-CORNER
 (1, 1)   EAST       1         0
ST.+---------------------------------------+
 6 | .   .   .   .   .   .   .   .   .   . |
   |                   +                   |
 5 | .   .   .   .   . | .   .   .   .   . |
   |                   |   +-------+	   |
 4 | .   .   .   .   . | . | .   . | .   . |
   |                   |   |	   |	   |
 3 | .   .   .   .   . | . | .   . | .   . |
   |   +-----------+   |   |	   |   +   |
 2 | . | .   .   . | . | . | .   . | . | . |
   |   |           |   |   |	   |   |   |
 1 | > | .   .   . | . | . | .   . | 1 | . |
   +---------------------------------------+
     1   2   3   4   5   6   7   8   9   10  AVE.

Koncová situácia

Na konci sa robot Karel nachádza na svojej pôvodnej pozícii, avšak tentokrát je otočený smerom na západ. V batohu má značku, pre ktorú utekal, t.j. v batohu má o jednu značku viac, než na začiatku programu.

 CORNER  FACING  BEEP-BAG  BEEP-CORNER
 (1, 1)   WEST       2         0
ST.+---------------------------------------+
 6 | .   .   .   .   .   .   .   .   .   . |
   |                   +                   |
 5 | .   .   .   .   . | .   .   .   .   . |
   |                   |   +-------+	   |
 4 | .   .   .   .   . | . | .   . | .   . |
   |                   |   |	   |	   |
 3 | .   .   .   .   . | . | .   . | .   . |
   |   +-----------+   |   |	   |   +   |
 2 | . | .   .   . | . | . | .   . | . | . |
   |   |           |   |   |	   |   |   |
 1 | < | .   .   . | . | . | .   . | . | . |
   +---------------------------------------+
     1   2   3   4   5   6   7   8   9   10  AVE.

Hodnotenie

Táto úloha je za max. 1 bod. Jej riešenie teda nie je komplexné, ale kladie dôraz na úplne iné záležitosti:

  • Aby ste si osvojili prácu so systémom na správu verzií git.
  • Aby ste si otestovali rozličné podoby počiatočnej a koncovej situácie pri odovzdávaní zadania.

Upozornenie

Pri hodnotení sa ráta každá jedna značka, pozícia aj smer robota.

Upozornenie

Pri odovzdaní Vášho programu použite vo funkcii turn_on() názov mapy task_1.kw.

Úloha 2: Poklad v tuneli

Robot Karel dostal za úlohu hľadať poklad v tuneli. Pre svet robota platí, že tunel je v tvare špirály a cesta sa postupne otáča smerom doľava. Poklad je nájdený vtedy, keď robot nájde značku. Poklad (značka) nemusí byť na konci tunela, ale môže sa nachádzať aj v strede uličky, Karel sa po nájdení pokladu vráti na začiatok tunela na jeho východziu pozíciu.

Pri odovzdaní Vášho programu použite vo funkcii turn_on() názov mapy task_2.kw.

Počiatočná situácia

Na začiatku sa robot Karel nachádza na vstupe do tunela, otočený smerom na východ.

 CORNER  FACING  BEEP-BAG  BEEP-CORNER
 (1, 1)   EAST       0         0
ST.+-------------------------------+
 8 | .   .   .   .   .   .   .   . |
   |   +-----------------------+   |
 7 | . | .   .   .   .   .   . | . |
   |   |   +---------------+   |   |
 6 | . | . | .   .   .   . | . | . |
   |   |   |   +-------+   |   |   |
 5 | . | . | . | 1   . | . | . | . |
   |   |   |   +----   |   |   |   |
 4 | . | . | .   .   . | . | . | . |
   |   |   +-----------+   |   |   |
 3 | . | .   .   .   .   . | . | . |
   |   +-------------------+   |   |
 2 | .   .   .   .   .   .   . | . |
   |---------------------------+   |
 1 | >   .   .   .   .   .   .   . |
   +-------------------------------+
     1   2   3   4   5   6   7   8   AVE.

Koncová situácia

Na konci sa robot Karel nachádza na svojej pôvodnej pozícii. V batohu má značku, pre ktorú utekal, t.j. v batohu má o jednu značku viac, než na začiatku programu. Na otočení robota nezáleží.

 CORNER  FACING  BEEP-BAG  BEEP-CORNER
 (1, 1)   NORTH      1         0
ST.+-------------------------------+
 8 | .   .   .   .   .   .   .   . |
   |   +-----------------------+   |
 7 | . | .   .   .   .   .   . | . |
   |   |   +---------------+   |   |
 6 | . | . | .   .   .   . | . | . |
   |   |   |   +-------+   |   |   |
 5 | . | . | . | .   . | . | . | . |
   |   |   |   +----   |   |   |   |
 4 | . | . | .   .   . | . | . | . |
   |   |   +-----------+   |   |   |
 3 | . | .   .   .   .   . | . | . |
   |   +-------------------+   |   |
 2 | .   .   .   .   .   .   . | . |
   |---------------------------+   |
 1 | ^   .   .   .   .   .   .   . |
   +-------------------------------+
     1   2   3   4   5   6   7   8   AVE.

Hodnotenie

Táto úloha je za max. 1 bod.

Upozornenie

Pri hodnotení sa ráta každá jedna značka aj pozícia robota.

Upozornenie

Pri odovzdaní Vášho programu použite vo funkcii turn_on() názov mapy task_2.kw.

Úloha 3: Upratovanie v šatníku

Karel bol upozornený svojou manželkou, aby si spravil poriadok v šatníku. V stĺpcoch mapy visia kusy oblečenia, ktoré sú zavesené na vešiaku. Karel má za úlohu urovnať si veci v šatníku tak, aby viseli od najdlhších po najkratšie v smere sprava doľava. Veci môžu visieť iba na vešiaku, pričom šatník môže obsahovať deliace priečky, ktoré môžu vešiak rozdeliť na viac častí. Karel sa po úspešnom prataní vracia na svoju pôvodnú pozíciu.

Pri odovzdaní Vášho programu použite vo funkcii turn_on() názov mapy task_3.kw.

Počiatočná situácia

Karel sa na začiatku nachádza na začiatku toho riadku, na ktorom visia značky a v batohu nemá žiadne značky.

 CORNER  FACING  BEEP-BAG  BEEP-CORNER
 (1, 6)   EAST       0         0
ST.+-----------------------------------+
 7 | .   .   .   .   .   .   .   .   . |
   |   +-------+   +-----------+   +---|
 6 | >   .   1   .   1   1   1   .   1 |
   |                                   |
 5 | .   .   1   .   1   1   1   .   1 |
   |                                   |
 4 | .   .   1   .   .   .   1   .   1 |
   |                                   |
 3 | .   .   1   .   .   .   1   .   . |
   |                                   |
 2 | .   .   .   .   .   .   1   .   . |
   |                                   |
 1 | .   .   .   .   .   .   .   .   . |
   +-----------------------------------+
     1   2   3   4   5   6   7   8   9   AVE.

Koncová situácia

Po upratovaní sa Karel presunie späť na svoju východziu pozíciu.

 CORNER  FACING  BEEP-BAG  BEEP-CORNER
 (1, 6)   EAST       0         0
ST.+-----------------------------------+
 7 | .   .   .   .   .   .   .   .   . |
   |   +-------+   +-----------+   +---+
 6 | >   .   1   .   1   1   1   .   1 |
   |                                   |
 5 | .   .   1   .   1   1   1   .   1 |
   |                                   |
 4 | .   .   .   .   .   1   1   .   1 |
   |                                   |
 3 | .   .   .   .   .   .   1   .   1 |
   |                                   |
 2 | .   .   .   .   .   .   .   .   1 |
   |                                   |
 1 | .   .   .   .   .   .   .   .   . |
   +-----------------------------------+
     1   2   3   4   5   6   7   8   9   AVE.

Hodnotenie

Táto úloha je za max. 1 bod.

Upozornenie

Pri hodnotení sa ráta každá jedna značka, pozícia aj smer robota.

Upozornenie

Pri odovzdaní Vášho programu použite vo funkcii turn_on() názov mapy task_3.kw.

Úloha 4: Oprava Krásnej Hôrky

Karel bol najatý, aby pomohol opraviť škody spôsobené na hrade Krásna Hôrka. Karel má teda opraviť sadu kamenných pilierov (samozrejme reprezentovaných značkami), v ktorých niektoré kamene chýbajú. Po skončení opráv budú všetky chýbajúce diery v stĺpoch opäť zaplnené. Stĺpy sú rôzne vysoké a sú od seba rôzne vzdialené.

Pri odovzdaní Vášho programu použite vo funkcii turn_on() názov mapy task_4.kw.

Počiatočná situácia

Karel začína v juhozápadnom rohu sveta otočený smerom na východ.

 CORNER  FACING  BEEP-BAG  BEEP-CORNER
 (1, 1)   EAST      99         1
ST.+-------------------------------------------+
 8 | .   .   .   .   .   .   .   .   .   .   . |
   |       +---+                       +---+   |
 7 | .   . | . | .   .   .   .   .   . | . | . |
   |   +---+   +---+   +-------+   +---+   +---|
 6 | . | .   .   . | . | .   . | . | .   .   1 |
   |---+           +---+       +---+           |
 5 | 1   .   .   .   .   .   .   1   .   .   1 |
   |                                           |
 4 | .   .   .   .   1   .   .   .   .   .   . |
   |                                           |
 3 | .   .   .   .   .   .   .   1   .   .   1 |
   |                                           |
 2 | .   .   .   .   1   .   .   .   .   .   . |
   |                                           |
 1 | >   .   .   .   1   .   .   .   .   .   1 |
   +-------------------------------------------+
     1   2   3   4   5   6   7   8   9   10  11  AVE.

Koncová situácia

Karel končí v juhovýchodnom rohu sveta otočený smerom na východ.

 CORNER  FACING  BEEP-BAG  BEEP-CORNER
 (11, 1)  EAST      89         1
ST.+-------------------------------------------+
 8 | .   .   .   .   .   .   .   .   .   .   . |
   |       +---+                       +---+   |
 7 | .   . | . | .   .   .   .   .   . | . | . |
   |   +---+   +---+   +-------+   +---+   +---|
 6 | . | .   .   . | . | .   . | . | .   .   1 |
   |---+           +---+       +---+           |
 5 | 1   .   .   .   1   .   .   1   .   .   1 |
   |                                           |
 4 | 1   .   .   .   1   .   .   1   .   .   1 |
   |                                           |
 3 | 1   .   .   .   1   .   .   1   .   .   1 |
   |                                           |
 2 | 1   .   .   .   1   .   .   1   .   .   1 |
   |                                           |
 1 | 1   .   .   .   1   .   .   1   .   .   > |
   +-------------------------------------------+
     1   2   3   4   5   6   7   8   9   10  11  AVE.

Hodnotenie

Táto úloha je za max. 1 bod.

Upozornenie

Pri hodnotení sa ráta každá jedna značka, pozícia aj smer robota.

Upozornenie

Pri odovzdaní Vášho programu použite vo funkcii turn_on() názov mapy task_4.kw.

Úloha 5: Rám s obrazom

Robot Karel dostal za úlohu zarámovať obraz. To je možné dosiahnuť tak, že robot označkuje všetky štyri hraničné steny sveta. Navyše, po splnení úlohy sa Karel premiestni do stredu sveta.

Pri odovzdaní Vášho programu použite vo funkcii turn_on() názov mapy task_5.kw.

Počiatočná situácia

Robot Karel začína na ľubovoľnej pozícii, ľubovoľne otočený, a v batohu má dostatočný počet značiek. Rozmery sveta sú vždy nepárne, najmenšia veľkosť sveta je 3x3.

 CORNER  FACING  BEEP-BAG  BEEP-CORNER
 (3, 1)   NORTH     100         0
ST.+-----------+
 5 | .   .   . |
   |           |
 4 | .   .   . |
   |           |
 3 | .   .   . |
   |           |
 2 | .   .   . |
   |           |
 1 | .   .   ^ |
   +-----------+
     1   2   3   AVE.

Koncová situácia

Karel končí v strede sveta, otočený smerom na sever. Hranice sveta sú označkované.

 CORNER  FACING  BEEP-BAG  BEEP-CORNER
 (2, 3)   NORTH     88         0
ST.+-----------+
 5 | 1   1   1 |
   |           |
 4 | 1   .   1 |
   |           |
 3 | 1   ^   1 |
   |           |
 2 | 1   .   1 |
   |           |
 1 | 1   1   1 |
   +-----------+
     1   2   3   AVE.

Hodnotenie

Táto úloha je za max. 1 bod.

Upozornenie

Pri hodnotení sa ráta každá jedna značka, pozícia aj smer robota.

Upozornenie

Pri odovzdaní Vášho programu použite vo funkcii turn_on() názov mapy task_5.kw.

Úloha 6: Poklad na mape

Robot Karel sa opäť vybral hľadať poklad. Tentokrát má k dispozícii slepú mapu s číslami. Pravidlá su nasledovné:

  • Karel ide stále rovno v smere jeho otočenia
  • Karel zmení smer, ak nájde značku/značky:
    • 1 znamená otočenie na sever
    • 2 znamená otočenie na západ
    • 3 znamená otočenie na juh
    • 4 znamená otočenie na východ
    • 5 znamená poklad
  • Karel cestou zbiera všetky značky, ktoré nájde
  • Ak Karel nájde poklad, zodvihne ho a zastaví sa

Pri odovzdaní Vášho programu použite vo funkcii turn_on() názov mapy task_6.kw.

Počiatočná situácia

Robot Karel začína na ľubovoľnej pozícii, otočený smerom k prvej indícii.

 CORNER  FACING  BEEP-BAG  BEEP-CORNER
 (2, 2)   NORTH      0         0
ST.+---------------------------------------+
 8 | .   .   .   .   .   .   .   .   .   . |
   |                                       |
 7 | .   4   .   .   .   3   .   .   .   . |
   |                                       |
 6 | .   .   .   .   .   .   .   .   .   . |
   |                                       |
 5 | .   .   .   .   .   .   .   .   .   . |
   |                                       |
 4 | .   .   .   5   .   .   .   .   2   . |
   |                                       |
 3 | .   .   .   .   .   .   .   .   .   . |
   |                                       |
 2 | .   ^   .   .   .   4   .   .   1   . |
   |                                       |
 1 | .   .   .   .   .   .   .   .   .   . |
   +---------------------------------------+
     1   2   3   4   5   6   7   8   9   10  AVE.

Koncová situácia

Karel končí na pozícii, kde sa nachádzal poklad. Na jeho otočení nezáleží. V batohu má všetky pozbierané značky.

 CORNER  FACING  BEEP-BAG  BEEP-CORNER
 (4, 4)   EAST      19         0
ST.+---------------------------------------+
 8 | .   .   .   .   .   .   .   .   .   . |
   |                                       |
 7 | .   .   .   .   .   .   .   .   .   . |
   |                                       |
 6 | .   .   .   .   .   .   .   .   .   . |
   |                                       |
 5 | .   .   .   .   .   .   .   .   .   . |
   |                                       |
 4 | .   .   .   >   .   .   .   .   .   . |
   |                                       |
 3 | .   .   .   .   .   .   .   .   .   . |
   |                                       |
 2 | .   .   .   .   .   .   .   .   .   . |
   |                                       |
 1 | .   .   .   .   .   .   .   .   .   . |
   +---------------------------------------+
     1   2   3   4   5   6   7   8   9   10  AVE.

Hodnotenie

Táto úloha je za max. 1 bod.

Upozornenie

Pri hodnotení sa ráta každá jedna značka aj pozícia robota.

Upozornenie

Pri odovzdaní Vášho programu použite vo funkcii turn_on() názov mapy task_6.kw.

Úloha 7: Skladisko

Karel začal brigádovať v skladisku. Na začiatok dostal pomerne jednoduchú úlohu - preskúmať staré priestory skladiska a rozhodnúť, ktoré z nich je možné ešte stále použiť na skladovanie. Skladisko je totiž veľké a obsahuje mnoho starých priestorov. Za bezpečný priestor sa považuje taký objekt, ktorý má len jeden vchod a celý je ohraničený pevnou stenou. Ak sa v objekte nachádzajú aj ďalšie potenciálne vchody, je potrebné daný priestor označiť pre budúce zabezpečenie, pretože aktuálne nie je považovaný za bezpečný. Vytvorte program, pomocou ktorého robot Karel overí dostupné priestory skladiska.

Pri odovzdaní Vášho programu použite vo funkcii turn_on() názov mapy task_7.kw.

Počiatočná situácia

Karel sa nachádza na pozícii vľavo dole na začiatku chodby, ktorú treba preskúmať, otočený smerom na východ. Chodba je rovná a vedie od západnej steny po východnú. Na sever od chodby sa nachádzajú skladové priestory, ktoré je potrebné preskúmať. Tieto priestory nemusia mať vždy obdĺžnikový tvar. Karel má dostatočný počet značiek na označenie priestorov skladiska.

 CORNER  FACING  BEEP-BAG  BEEP-CORNER
 (1, 1)   EAST      99         0
ST.+-----------------------------------+
 5 | .   .   . | .   .   . | . | .   . |
   |       |   +---+   +---+   |   |   |
 4 | .   . | .   . | . | .   . | . | . |
   |   +---+       |   |       |   |   |
 3 | . | .   .   . | . | .   . | .   . |
   |   |           |   |       |   |   |
 2 | . | . | . | . | . | . | . | . | . |
   |   +---+   +---+   +---+   |   |   |
 1 | >   .   .   .   .   .   .   .   . |
   +-----------------------------------+
     1   2   3   4   5   6   7   8   9   AVE.

Koncová situácia

Karel sa nachádza na konci chodby otočený smerom na východ. Všetky skladiskové priestory sú overené a tie, ktoré nie sú považované za bezpečné, sú označkované značkou vo dverách (prekážkou).

 CORNER  FACING  BEEP-BAG  BEEP-CORNER
 (9, 1)   EAST      95         0
ST.+-----------------------------------+
 5 | .   .   . | .   .   . | . | .   . |
   |       |   +---+   +---+   |   |   |
 4 | .   . | .   . | . | .   . | . | . |
   |   +---+       |   |       |   |   |
 3 | . | .   .   . | . | .   . | .   . |
   |   |           |   |       |   |   |
 2 | 1 | . | 1 | . | . | . | . | 1 | 1 |
   |   +---+   +---+   +---+   |   |   |
 1 | .   .   .   .   .   .   .   .   > |
   +-----------------------------------+
     1   2   3   4   5   6   7   8   9   AVE.

Hodnotenie

Táto úloha je za max. 2 body.

Upozornenie

Pri hodnotení sa ráta každá jedna značka, pozícia aj smer robota.

Upozornenie

Pri odovzdaní Vášho programu použite vo funkcii turn_on() názov mapy task_7.kw.

Požiadavky pre úspešné odovzdanie zadania

  • Projekt musí byť odovzdaný včas v git repozitári na adrese git.kpi.fei.tuke.sk (viď nižšie).
  • Počas prekladu nemôže dôjsť ku žiadnej chybe! Projekt sa bude prekladať prekladačom gcc pomocou nasledovných prepínačov:
gcc -std=c11 -Werror -Wall -lsuperkarel -lcurses
  • Vo výslednej implementácii sa nemôže nachádzať žiadna premenná.
  • Pri odovzdaní Vášich programov použite vo funkcii turn_on() názov mapy task_1.kw, task_2.kw ... task_7.kw.

Odovzdávanie projektu

Zadanie odovzdajte do 24.10.2024 (štvrtok). Posledné testovanie prebehne v tento deň o polnoci.

Zadanie sa odovzdáva prostredníctvom systému na správu verzií Git na serveri git.kpi.fei.tuke.sk. Predtým, než začnete pracovať na zadaní, zoznámte sa so systémom Git, pomocou ktorého prebehne odovzdanie tohto zadania. K dispozícii máte krátke cvičenie, v rámci ktorého nastavíte systém Git: Version Control.

Upozornenie

Vytvorte si v GitLab-e nový projekt prostredníctvom aplikácie ZAP Gitlab Classroom podľa postupu uvedeného tu: Version Control.

Názov Vášho projektu musí byť v tvare: zap-2024-id.

Projekt musí mať nasledujúcu štruktúru priečinkov a súborov:

.
├── ps1
│   ├── task_1.c
│   └── task_2.c
│   └── task_3.c
│   └── task_4.c
│   └── task_5.c
│   └── task_6.c
│   └── task_7.c
└── README

Význam jednotlivých súborov je nasledovný:

  • README - Súbor, v ktorom bude uvedená Vaša skupina, ktorú navštevujete na cvičeniach:
GROUP : C1
  • /ps1/task_1.c - Zdrojový kód riešenia úlohy - Orientačný beh.
  • /ps1/task_2.c - Zdrojový kód riešenia úlohy - Poklad v tuneli.
  • /ps1/task_3.c - Zdrojový kód riešenia úlohy - Upratovanie v šatníku.
  • /ps1/task_4.c - Zdrojový kód riešenia úlohy - Oprava Krásnej Hôrky.
  • /ps1/task_5.c - Zdrojový kód riešenia úlohy - Rám s obrazom.
  • /ps1/task_6.c - Zdrojový kód riešenia úlohy - Poklad na mape.
  • /ps1/task_7.c - Zdrojový kód riešenia úlohy - Skladisko.

Upozornenie

Je dôležité, aby Vaše súbory zachovali uvedenú štruktúru. Ak sa niektorý zo súborov síce v repozitári nachádza, ale v inom priečinku, bude to považované za chybu a takýto projekt nebude považovaný za správny.

Poznámka

Ak sa vo Vašom projekte budú nachádzať ďalšie súbory okrem požadovaných, ich existencia nebude považovaná za chybu.

Upozornenie

Pri názvoch priečinkov, súborov a obsahu súboru README záleží na veľkosti písmen!

Hodnotenie a testovanie

Za zadanie môžete získať max. 8 bodov, z toho max. 0 bodov do zápočtu a max. 8 bodov do skúšky. Počet získaných bodov sa bude odrážať od výsledku testov, ktorými Vaše zadanie úspešne prejde. Overovať sa bude:

  • Štruktúra Vášho projektu (či sa v ňom nachádzajú všetky potrebné súbory).
  • Funkčnosť Vašej implementácie.

Váš kód sa bude prekladať prekladačom gcc s nasledovnými prepínačmi:

gcc -std=c11 -Werror -Wall -lsuperkarel -lcurses

Za chybu sa bude považovať:

  • Ak vo Vašej implementácii použijete premennú.
  • Ak počas prekladu dôjde ku chybe (upozornenia sú priamo konvertované na chyby).
  • Ak Vaša implementácia neprejde niektorým z testov.

Testovanie Vašich riešení sa bude vykonávať automaticky každé 3 hodiny a to konkrétne o 0300, 0600, 0900, 1200, 1500, 1800, 2100 a 2400.

Vaše riešenia prejdú kontrolou originality. Preto sa pri práci na Vašom zadaní správajte podľa pravidiel etického kódexu! V prípade, že odovzdáte zadanie, ktoré nie je Vaše, môžete byť vylúčení z predmetu!

Doplňujúce zdroje

  1. Karel Language Reference
  2. Version Control
  3. Tu nájdete knižnicu robota Karla, vrátane návodu na inštaláciu knižnice