Problem Set 3: Karel allows variables

Objectives

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

Git

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

Task

От вашего практикующего получите номер задания в мире Робота Карла.

Предложите решение для полученной задачи. Не забудьте, что теперь можно использовать локальные переменные. Задание сдайте на git не позднее 12.11.2018. Подробной описание сдачи приведено ниже.

При написании программы не забудьте указать в функции turnOn() файл карты ps3.kw.

Список заданий находится в конце странице.

Minimal Requirements to Succeed

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

Project Submission

Проект загрузите не позднее 12.11.2018. Последние тесты пройдут в полночь этого дня.

Задание сдаётся с помощью системы контроля версий Git на сервере git.kpi.fei.tuke.sk.

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

В проекте должна быть сохранена следующая иерархия файлов и папок:

.
├── ps3
│   ├── README
│   └── ps3.c
└── README

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

  • README или README.md - Файл, в котором должен быть указан номер группы, которую вы посещаете:
GROUP : C1
  • /ps3/ps3.c - Программный код для решения поставленной задачи (номер задачи вам выдал ваш практикующий).

Warning

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

Comment

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

Warning

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

Comment

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

Assessment and Testing

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

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

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

gcc -std=c11 -Werror -Wall -lkarel -lcurses -lm

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

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

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

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

Problems to be Solved

01: Фреймы

Допустим, у нас есть 5 фреймов:

. . . . . . . . | . . . . . . . . | . . . . . . . . | . . . . . . . . | . 1 1 1 . . . .
                |                 |                 |                 |
3 3 3 3 3 3 . . | . . . . . . . . | . . . . . . . . | . . 2 2 2 2 . . | . 1 . 1 . . . .
                |                 |                 |                 |
3 . . . . 3 . . | 5 5 5 5 5 5 . . | . . . . . . . . | . . 2 . . 2 . . | . 1 . 1 . . . .
                |                 |                 |                 |
3 . . . . 3 . . | 5 . . . . 5 . . | . . . . . . . . | . . 2 . . 2 . . | . 1 1 1 . . . .
                |                 |                 |                 |
3 . . . . 3 . . | 5 . . . . 5 . . | . . . . 4 4 4 4 | . . 2 . . 2 . . | . . . . . . . .
                |                 |                 |                 |
3 . . . . 3 . . | 5 . . . . 5 . . | . . . . 4 . . 4 | . . 2 2 2 2 . . | . . . . . . . .
                |                 |                 |                 |
3 . . . . 3 . . | 5 5 5 5 5 5 . . | . . . . 4 . . 4 | . . . . . . . . | . . . . . . . .
                |                 |                 |                 |
3 . . . . 3 . . | . . . . . . . . | . . . . 4 4 4 4 | . . . . . . . . | . . . . . . . .
                |                 |                 |                 |
3 3 3 3 3 3 . . | . . . . . . . . | . . . . . . . . | . . . . . . . . | . . . . . . . .
                |                 |                 |                 |
. . . . . . . . | . . . . . . . . | . . . . . . . . | . . . . . . . . | . . . . . . . .

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

 .   1   1   1   .   .   .   .

 3   1   2   1   2   2   .   .

 5   1   2   1   5   2   .   .

 5   1   1   1   .   2   .   .

 5   .   2   .   4   2   4   4

 5   .   2   2   2   2   .   4

 5   5   5   5   4   5   .   4

 3   .   .   .   4   4   4   4

 3   3   3   3   3   3   .   .

 .   .   .   .   .   .   .   .

В каком порядке разложены фреймы? Ответ: 3 5 4 2 1.

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

  • Фреймы всегда включают в себя или квадрат, или прямоугольник
  • Грань фреймы всегда >= 3 позиций
  • Фреймы обозначаются числами в виде значков на карте
  • Ни один из двух фреймов не обозначается одинаково
  • Всегда видно хотя бы одну позицию грани каждого фрейма
  • В мире находится от 1 до 5 фреймов

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

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

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

 CORNER  FACING  BEEP-BAG  BEEP-CORNER
 (1, 1)   EAST      30         0
ST.+---------------------------------------+
10 | 1   1   1   1   5   5   5   5   1   1 |
   |                                       |
 9 | 1   .   .   .   5   4   4   5   4   1 |
   |                                       |
 8 | 2   2   2   2   5   5   5   5   4   1 |
   |                                       |
 7 | 2   .   .   3   3   4   3   3   4   1 |
   |                                       |
 6 | 2   .   .   3   .   4   .   3   4   1 |
   |                                       |
 5 | 2   .   .   3   3   4   3   3   4   1 |
   |                                       |
 4 | 2   2   2   2   .   4   .   .   4   1 |
   |                                       |
 3 | 1   .   .   .   .   4   4   4   4   1 |
   |                                       |
 2 | 1   1   1   1   1   1   1   1   1   1 |
   |                                       |
 1 | >   .   .   .   .   .   .   .   .   . |
   +---------------------------------------+
     1   2   3   4   5   6   7   8   9   10  AVE.
Конечная позиция

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

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

02: Переводы

Создайте программу, с помощью которой робот Карл научиться переводить десятичные числа в двоичную систему. Каждое число, которое нужно перевести, представлено в виде последовательности значков идущих один за другим на одном ряду, при этом соответствующее число в разряде представлено количеством значков на позиции. Таким образом, если хотим записать число 123, на карте будут соответственно на первой позиции 1 значок, на второй позиции 2, а на третьей - 3. Результат перевода числа в двоичную систему исчисления роботу следует записать таким же способом. В конце на карте должны быть 2 ряда с числами: число в десятичной системе и ответ в двоичной системе.

Десятичное число не содержит 0. Ширина карты всегда достаточна для того, чтобы поместить все 0 и 1 бинарного вида числа.

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

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

Робот Карл сначала будет находится лицом к числу, подлежащее к переводу.

 CORNER  FACING  BEEP-BAG  BEEP-CORNER
 (1, 5)   EAST      99         0
ST.+-----------------------------------+
 6 | .   .   .   .   .   .   .   .   . |
   |                                   |
 5 | >   1   2   3   .   .   .   .   . |
   |                                   |
 4 | .   .   .   .   .   .   .   .   . |
   |                                   |
 3 | .   .   .   .   .   .   .   .   . |
   |                                   |
 2 | .   .   .   .   .   .   .   .   . |
   |                                   |
 1 | .   .   .   .   .   .   .   .   . |
   +-----------------------------------+
     1   2   3   4   5   6   7   8   9   AVE.
Конечная позиция

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

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

03: Бинарное дерево

У робота Карла в распоряжении карта, в которой находятся значки, создающие бинарное дерево. Его задача - узнать, существует ли такой путь от корня к листу, в котором сумма узлов дерева ровна конкретному значению (см. Бинарное дерево). Например, у дерева на картинке ровно 4 пути от корня к листу. Их суммы: 27, 22, 26 и 18.

Бинарное дерево
Obr. 1: Бинарное дерево

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

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

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

 CORNER  FACING  BEEP-BAG  BEEP-CORNER
 (2, 5)   WEST       0         0
ST.+-----------------------------------------------------------+
 5 | 22  <   .   .   .   .   .   .   .   .   .   .   .   .   . |
   |                                                           |
 4 | .   .   .   .   .   .   .   5   .   .   .   .   .   .   . |
   |                                                           |
 3 | .   .   .   4   .   .   .   .   .   .   .   8   .   .   . |
   |                                                           |
 2 | .   11  .   .   .   .   .   .   .   13  .   .   .   4   . |
   |                                                           |
 1 | 7   .   2   .   .   .   .   .   .   .   .   .   .   .   1 |
   +-----------------------------------------------------------+
     1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  AVE.
Конечная позиция

Если путь с нужной суммой действительно существует, Карл должен остановиться в верхнем левом углу карты, если нет - в верхнем правом углу.

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

04: Треугольники

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

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

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

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

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

 CORNER  FACING  BEEP-BAG  BEEP-CORNER
 (1, 4)   EAST      100        35
ST.+-----------+
 4 | >   .   . |
   |           |
 3 | .   .   . |
   |           |
 2 | .   .   . |
   |           |
 1 | .   .   . |
   +-----------+
     1   2   3   AVE.
Конечная позиция

Карл стоит в правом верхнем углу карты.

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

05: Мины

У робота Карла в распоряжении мир, в котором находятся значки в количестве 0-8. Значки представляют, сколько мин находятся на соседних позициях на карте. Задачей робота Карла является обозначить местонахождения мин, положив на места мин по 10 значков.

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

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

Карл приступает к выполнению задания в левом верхнем углу карты.

 CORNER  FACING  BEEP-BAG  BEEP-CORNER
 (1, 16   EAST      50         1
ST.+---------------------------+
 6 | >   1   .   .   .   .   . |
   |                           |
 5 | .   2   1   1   .   .   . |
   |                           |
 4 | 2   3   .   2   1   1   . |
   |                           |
 3 | 1   .   2   2   .   1   . |
   |                           |
 2 | 1   1   1   1   1   1   . |
   |                           |
 1 | .   .   .   .   .   .   . |
   +---------------------------+
     1   2   3   4   5   6   7   AVE.
Конечная позиция

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

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

06: Панорама

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

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

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

Карл оказывается на случайной позиции на карте.

 CORNER  FACING  BEEP-BAG  BEEP-CORNER
 (1, 1)   NORTH      0         0
ST.+-----------------------------------------------------------+
10 | .   .   .   .   .   .   .   .   .   .   .   .   .   .   . |
   |                                                           |
 9 | .   .   .   .   .   .   .   .   .   1   1   1   .   .   . |
   |                                                           |
 8 | .   .   .   .   .   .   .   .   .   1   .   1   .   .   . |
   |                                                           |
 7 | .   .   .   .   .   .   .   .   .   1   .   1   .   .   . |
   |                                                           |
 6 | .   .   .   .   1   1   1   1   .   1   .   1   .   .   . |
   |                                                           |
 5 | .   .   .   .   1   .   .   1   .   1   .   1   .   .   . |
   |                                                           |
 4 | .   1   1   1   1   .   .   1   .   1   1   1   1   1   . |
   |                                                           |
 3 | .   1   .   1   1   1   1   1   .   1   1   1   .   1   . |
   |                                                           |
 2 | .   1   .   1   1   .   1   1   .   1   1   1   .   1   . |
   |                                                           |
 1 | ^   1   .   1   1   .   1   1   .   1   1   1   .   1   . |
   +-----------------------------------------------------------+
     1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  AVE.
Конечная позиция

Карл заканчивает в правом нижнем углу карты.

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

07: Iagno

Iagno это игра (см. Iagno), в которую играют два игрока на карте с розмерами 8x8 одним значком для первого игрока и двумя значками для второго. Игроки по очереди помещают значки на свободные места на карте таким образом, чтобы настоящий игрок замкнул хотя бы один ряд, принадлежащий другому игроку. Ряд считается замкнутым, если в его горизонтальной, вертикальной или диагональной линии с обеих сторон находятся ряды другого игрока. В таком случае количество значков на всех рядах, которые стали замкнутыми, изменится на количество значков соответсвующий игроку, которые ряды замкнул.

Робот Карл - игрок №1. Его задачей является положить по 3 значка на все позиции на карте, где можно выполнить следующий ход против игрока №2 (см. начальную и конечную ситуации).

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

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

Робот Карл может оказаться на любой позиции карты.

 CORNER  FACING  BEEP-BAG  BEEP-CORNER
 (1, 1)   NORTH      100        0
ST.+-------------------------------+
 8 | .   .   .   .   .   .   .   . |
   |                               |
 7 | .   .   .   .   .   .   .   . |
   |                               |
 6 | .   .   .   2   .   .   1   . |
   |                               |
 5 | .   .   .   2   2   2   .   . |
   |                               |
 4 | .   .   1   2   1   1   .   . |
   |                               |
 3 | .   .   1   1   2   1   .   . |
   |                               |
 2 | .   .   1   .   .   .   .   . |
   |                               |
 1 | ^   .   .   .   .   .   .   . |
   +-------------------------------+
     1   2   3   4   5   6   7   8  AVE.
Конечная позиция

Карл находится в правом нижнем углу карты.

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

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