4. týždeň

Problem Set 1: Карл

Objectives

  • Показать, насколько хорошо вы освоили алгоритмическое мышление и работу c роботом Карлом.
  • Научиться систематически составлять каркас и логику программы, саму программу и добавлять комментарии к ней.
  • Освоиться в системе контроля версий git.

Git

Прежде чем вы перейдете к самому заданию, ознакомьтесь с системой Git, благодаря которой будет осуществляться сдача вашего текущего задания (позднее, и других). В вашем распоряжении короткая лабораторная работа, в рамках которой вы сможете настроить систему Git: Version Control (RU).

Task 1: Ориентированный забег

Карл решил снова принять участие в олимпиаде. И в этот раз ему предстоит бег с препятствиями, барьеры на котором разноширокие и разновысокие, расположены на случайном расстоянии друг от друга. Теперь-то ему придется подбирать значки по дороге, вернувшись на изначальную позицию, снова преодолев полосу препятствий на обратном пути.

Также не забывайте, что по-прежнему нельзя использовать переменные.

При сдаче не забудьте, что вам следует указать файл карты task_1.kw в функции turn_on().

Начальная позиция

Изначально Карл находится где-то на полосе с препятствиями и смотрит на восток.

 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.

Конечная позиция

Свое движение робот заканчивает на той же позиции, где был изначально, но теперь он смотрит на запад. В рюкзаке у него окажется значок, за которым он и бегал, т.е. на один значок больше, чем у него было изначально.

 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.

Assessment

Это задание оценивается макс. 1 б. Его несложно выполнить, но оно заставляет задуматься о совершенно других вещах:

  • как освоить работу в системе контроля версий git.
  • проверка решений на разнообразных позициях, как изначальных, так и конечных.

Warning

Оценивается каждый значок, позиция и направление робота.

Warning

Сдавая код, не забудьте указать корректный файл карты task_1.kw в turn_on().

Task 2: Сокровище в туннеле

Роботу Карлу предстоит найти клад в туннеле. Карлу известно, что туннель всегда имеет форму спирали, т.е. дорога каждый раз уходит налево. Сокровищем является значок, который может найтись на любом участке пути - спустя пару шагов или даже в конце туннеля! Найдя значок, Карл должен вернуться на исходную позицию - в начало туннеля.

При сдаче не забудьте, что вам следует указать файл карты task_2.kw в функции turn_on().

Начальная позиция

Вначале робот смотрит на восток, находясь на входе в туннель.

 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.

Конечная позиция

В конце Карл должен находиться на своей изначальной позиции. В рюкзаке у него найденное сокровище (значок), т.е. в рюкзаке у него на один значок больше, чем в начале выполнения программы. Конечное направление робота роли не играет.

 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.

Assessment

Это задание оценивается макс. 1 б.

Warning

Оценивается каждый значок и позиция робота.

Warning

Сдавая код, не забудьте указать корректный файл карты task_2.kw в turn_on().

Task 3: Уборка в гардеробе

Карл получил выговор от своей жены. Провинившемуся нужно убраться в шкафу. В столбцах карты висит одежда, которая висит на перекладине. Задача робота состоит развесить вещи в правильном порядке: от самых длинных до самых коротких справа налево. Одежда может висеть только на перекладине, при этом в шкафу возможны разделяющие стеночки, которые могут в свою очередь разделять перекладину на несколько частей. После уборки Карл вернётся на начальную позицию.

При сдаче не забудьте, что вам следует указать файл карты task_3.kw в функции turn_on().

Начальная позиция

Изначально робот Карл находится в начале ряда, на котором висят значки. В рюкзаке у него значков нет.

 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.

Конечная позиция

После уборки робот вернётся на изначальную позицию.

 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.

Assessment

Это задание оценивается макс. 1 б.

Warning

Оценивается каждый значок, позиция и направление робота.

Warning

Сдавая код, не забудьте указать корректный файл карты task_3.kw в turn_on().

Task 4: Ремонт замка Чудесная Горка

Карла наняли для того, чтобы он помог отремонтировать ущерб, нанесённый замку Чудесная Горка. В данном случае, роботу следует исправить набор каменных колонн (конечно же представленных значками), в которых не хватает камней. После ремонтных работ должны все дыры быть заполнены значками. Колонны сами по себе разновысокие и находятся друг от друга на случайном расстоянии.

При сдаче не забудьте, что вам следует указать файл карты task_4.kw в функции turn_on().

Начальная позиция

Карл начинает работу в юго-западном углу карты, обращенный на восток.

 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.

Конечная позиция

Карл сдаёт работу, находясь в юго-восточном углу, также смотря на восток.

 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.

Assessment

Это задание оценивается макс. 1 б.

Warning

Оценивается каждый значок, позиция и направление робота.

Warning

Сдавая код, не забудьте указать корректный файл карты task_4.kw в turn_on().

Task 5: Картинная рамка

Роботу Карлу нужно поместить картину в рамку. Конкретнее, робот должен поместить значки на каждую из граничных стен. Более того, выполнив задание, Карл должен находиться в центре карты.

При сдаче не забудьте, что вам следует указать файл карты task_5.kw в функции turn_on().

Начальная позиция

В начале выполнения программы робот Карл может иметь любую позицию, ровно как и направление. В рюкзаке у него всегда достаточное количество значков на выполнение задания. Параметры картины (карты) всегда непарные, т.е. как минимум, 3x3.

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

Конечная позиция

Карл закончит выполнение задания, находясь в середины карты, смотря на север. Картина обрела рамку.

 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.

Assessment

Это задание оценивается макс. 2 б.

Warning

Оценивается каждый значок, позиция и направление робота.

Warning

Сдавая код, не забудьте указать корректный файл карты task_5.kw в turn_on().

Task 6: Найди клад!

Роботу предстоят поиски клада! На этот раз у него в распоряжении карта с указаниями, точнее, с числами. Правила игры:

  • Карл никогда не меняет направление своего движения просто так
  • Направление меняется в случае, если робот наткнется на число, каждое из которых:
    • 1 означает изменение направления на север
    • 2 означает изменение направления на запад
    • 3 означает изменение направления на юг
    • 4 означает изменение направления на восток
    • 5 означает искомый клад
  • По пути Карл должен собирать данные ему указания - значки
  • Когда робот найдёт клад, ему следует его поднять и остановиться.

При сдаче не забудьте, что вам следует указать файл карты task_6.kw в функции turn_on().

Начальная позиция

В начале выполнения программы робот Карл может иметь любую позицию, ровно как и направление. В рюкзаке у него всегда достаточное количество значков на выполнение задания. Параметры картины (карты) всегда непарные, т.е. как минимум, 3x3.

 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.

Конечная позиция

Последняя позиция робота - на месте нахождения клада, при этом все значки (указания и сам клад) собраны ему в рюкзак. Направление Карла в конце роли не играет.

 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.

Assessment

Это задание оценивается макс. 2 б.

Warning

Оценивается каждый значок и позиция робота.

Warning

Сдавая код, не забудьте указать корректный файл карты task_6.kw в turn_on().

Task 7: Склад

Карл устроился на подработку на склад. Сначала ему дали довольно легкое задание - ему нужно проверить, какие из старых складских помещений всё еще можно использовать по назначению. Склад сам по себе большой и имеет много старых помещений внутри. Безопасным помещением считается такое помещение, в котором только один вход и всё оно ограничено крепкой стеной. Если в помещении находятся другие потенциальные выходы, нужно такое помещение обозначить как подлежащее к ремонту, поскольку безопасным его считать нельзя. Напишите программу, с помощью которой робот Карл проведёт инспекцию доступных помещений склада.

При сдаче не забудьте, что вам следует указать файл карты task_7.kw в функции turn_on().

Начальная позиция

Карл находится в левом нижним углу в начале коридора, который нужно проверить, лицом на восток. Коридор прямой и проходит от западной стены к восточной. Севернее коридора находятся сами складские помещения. Планировка помещений не должна всегда быть представлена прямоугольником. У железного работника в рюкзаке достаточное количество значков для того, чтобы помечать помещения.

 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.

Конечная позиция

Карл закончит данное ему поручение в конце коридора, обращенный на восток. Не должно остаться ни одного непроверенного помещения. Небезопасные помещения он решил помечать значком в дверях (препятствием).

 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.

Assessment

Это задание оценивается макс. 2 б.

Warning

Оценивается каждый значок, позиция и направление робота.

Warning

Сдавая код, не забудьте указать корректный файл карты task_7.kw в turn_on().

Minimal Requirements to Succeed

  • Проект должен быть сдан и загружен в репозиторий на git git.kpi.fei.tuke.sk (см. ниже).
  • Во время компиляции любые ошибки недопустимы. Сборка проекта будет осуществляться компилятором gcc со следующими параметрами:
gcc -std=c11 -Werror -Wall -lsuperkarel -lcurses
  • В конечном решении не могут использоваться переменные.
  • Сдавая код, не забудьте указать корректный файл карты task_1.kw, task_2.kw ... task_7.kw в turn_on().

Project Submission

Имплементацию задания сдайте до 27.10.2019. Последний тесты пройдут в полночь.

Задание сдаётся в системе котороля версий Git на сервере git.kpi.fei.tuke.sk. Перед тем, как перейти к выполнению задания, вам следует ознакомиться с работой на git. Для этого пройдите краткую лабораторную работу: Version Control (RU).

Название вашего проекта в репозитории должно быть в формате: zap-2019.

Папки и файлы в проекте должны иметь соответствующую структуру:

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

У каждого из файлов своё значение:

  • README или же README.md - файл, в котором будет указана группа, которую вы посещаете:
GROUP : C1
  • /ps1/task_1.c - Код программы для первой задачи - Ориентированный забег.
  • /ps1/task_2.c - Код программы для второй задачи - Сокровище в туннеле.
  • /ps1/task_3.c - Код программы для второй задачи - Уборка в гардеробе.
  • /ps1/task_4.c - Код программы для второй задачи - Ремонт замка Чудесная Горка.
  • /ps1/task_5.c - Код программы для второй задачи - Картинная рамка.
  • /ps1/task_6.c - Код программы для второй задачи - Найди клад.
  • /ps1/task_7.c - Код программы для второй задачи - Склад.

Warning

Важно помнить, что ваши файлы должны не нарушать иерархию файлов. Если какой-то из файлов находится в репозитории находится в другом каталоге, это будет считаться ошибкой, таким образом проект не будет считаться правильным.

Comment

Если в прокте будут находиться сторонние файлы, это не будет считаться ошибкой.

Warning

Имена файлов, каталогов, также содержание README или же README.md чувствительны к регистру

Comment

Имя файла с номером задания может быть README или README.md. При этом в одном каталоге может находиться только один из них!

Assessment and Testing

Задание оценивается макс. 10 баллами, из которых все пойдут не в счёт зачёта, а в счёт экзамена. Количество баллов которые вы получите будет обусловлено результатами тестов, которые будет выполнены над вашим заданием. Будут проверяться:

  • Иерархия файлов (все ли обязательные файлы находятся в проекте).
  • Работоспособность вашей имплементации.

Проект будет собран с помощью компилятора gcc со следующими параметрами:

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

Ошибкой будет считаться:

  • Использование переменных.
  • Появление ошибок во время компиляции (любой warning интерпретируется как ошибка).
  • Любой failed test.

Тесты будут запускаться каждые 3 часа, а именно: 0300, 0600, 0900, 1200, 1500, 1800, 2100 и 2400.

Код будет испытан на оригинальность. Потому при выполнении заданий придерживайтесь этического кодекса! Выявление плагиата повлечет за собой исключение с предмета!

Additional Resources

  1. Karl Language Reference
  2. Version Control (RU)
  3. Here you can find the original library of Karel the Robot, including the library installation instructions