10. неделя

Problem Set 4: Ball Sort Puzzle & Connect Four

Цели

  1. Создать собственные функции согласно спецификации.
  2. Работать с двумерными массивами и строками.
  3. Использовать массив в качестве входного и выходного параметра функции.
  4. Использовать генератор случайных чисел.

Ball Sort Puzzle

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

Ball Sort Puzzle.
Рис. 1: Ball Sort Puzzle.

Наша же игра будет проходить следующим образом:

  1. Игрок получит поле со случайно разбросанными символами.
  2. Далее шаг за шагом он будет перемещает символы на подходящие для них места.
  3. Если всё рассортировано правильно, игрок выигрывает.

Цветные шарики определённо смотрелись бы лучше в нашем решении, но нам будет достаточно и консольного интерфейса. Вместо них, как упоминалось ранее, будут использованы различные символы.

Вашей задачей будет запрограммировать пять функций:

  • void generator(const int rows, const int columns, char field[rows][columns]) - Генерация игрового поля в виде двумерного массива.
  • void down_possible(const int rows, const int columns, char field[rows][columns], int x, int y) - Перемещает выбранный символ в другой столбец при условии, что верхний символ этого столбца идентичен вышеназванному.
  • bool check(const int rows, const int columns, char field[rows][columns]) - Проверка собранных столбцов.
  • void game_field(const int rows, const int columns, char field[rows][columns]) - "Рисование" игрового поля.
  • ball_sort_puzzle() - Функционал самой игры.

Все 5 функций будут находиться в файле ballsortpuzzle.c. Объявление каждой находится в заголовочном файле ballsortpuzzle.h. Основной код программы содержится в main.c.

Помимо необходимых функций, вы также можете создавать свои собственные. Однако ни одна из них не должна быть объявлена в ballsortpuzzle.h.

Task 1: Генерация игрового поля

Запрограммируйте функцию void generator(const int rows, const int columns, char field[rows][columns]) со следующими параметрами:

  • const int rows - Количество рядков в массиве
  • const int columns - Количество столбцов в массиве
  • char field[rows][columns] - Двумерный массив, в котором будут храниться символы

Функция ничего не возвращает.

Задача данной функции - генерировать двумерный массив с символами. При её выполнении обязательны следующие условия:

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

Пример 1:

         FOREGROUND                           BACKGROUND               SOME INDEXES
 1 | @ | * |   |   | + | + |    [0]: {'@', '*', ' ', ' ', '+', '+'}    [0][4]: '+'
 2 | * | + |   |   | * | + |    [1]: {'*', '+', ' ', ' ', '*', '+'}    [1][2]: ' '
 3 | @ | ^ |   |   | ^ | @ |    [2]: {'@', '^', ' ', ' ', '^', '@'}    [2][4]: '^'
 4 | ^ | ^ |   |   | @ | * |    [3]: {'^', '^', ' ', ' ', '@', '*'}    [3][5]: '*'
    --- --- --- --- --- ---
     1   2   3   4   5   6            [0]  [1]  [2]  [3]  [4]  [5]

Пример 2:

         FOREGROUND                           BACKGROUND               SOME INDEXES
 1 | * | @ |   | * |   | ^ |    [0]: {'*', '@', ' ', '*', ' ', '^'}    [0][3]: '*'
 2 | * | @ |   | + |   | ^ |    [1]: {'*', '@', ' ', '+', ' ', '^'}    [1][3]: '+'
 3 | * | + |   | @ |   | ^ |    [2]: {'*', '+', ' ', '@', ' ', '^'}    [2][3]: '@'
 4 | ^ | @ |   | + |   | + |    [3]: {'^', '@', ' ', '+', ' ', '+'}    [3][3]: '+'
    --- --- --- --- --- ---
     1   2   3   4   5   6            [0]  [1]  [2]  [3]  [4]  [5]

Assessment

За задание можно получить макс. 2 балла. Будет проверено автоматически.

Task 2: Перемещение символов по игровому полю

Запрограммируйте функцию void down_possible(const int rows, const int columns, char field[rows][columns], int x, int y) со следующими параметрами:

  • const int rows - Количество рядков в массиве
  • const int columns - Количество столбцов в массиве
  • char field[rows][columns] - Массив, в котором содержатся символы
  • int x - Номер столбца, с которого мы хотим передвинуть символ
  • int y - Номер столбца, куда мы хотим передвинуть символ

Функция ничего не возвращает.

Данная функция будет отвечать за перемещение символов по игровому полю. Помимо этого, функция также должна пресекать любые попытки игрока поставить неодинаковые символы вместе.

Также стоит обратить внимание и на ситуацию, в которой символ перемещается в самый конец пустого столбца.

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

При перемещении символа обязательно убедитесь, что он займёт позицию над каким-либо элементом, а не останется парить в воздухе.

Игрок не может указать одинаковые столбцы для перемещения, к примеру, со второго на второй.

Пример перехода с первого столбца на второй:

 1 | * |   | ^ | @ | @ |   |    1 |   |   | ^ | @ | @ |   |
 2 | + |   | ^ | @ | ^ |   |    2 | + |   | ^ | @ | ^ |   |
 3 | + |   | * | + | + |   |    3 | + |   | * | + | + |   |
 4 | * |   | * | @ | ^ |   |    4 | * | * | * | @ | ^ |   |
    --- --- --- --- --- ---        --- --- --- --- --- ---
     1   2   3   4   5   6          1   2   3   4   5   6

Пример перехода с шестого столбца на четвёртый:

 1 |   |   | ^ |   |   |   |    1 |   |   | ^ | @ |   |   |
 2 | + |   | ^ | @ | ^ |   |    2 | + |   | ^ | @ | ^ |   |
 3 | + |   | * | + | + | @ |    3 | + |   | * | + | + |   |
 4 | * | * | * | @ | ^ | @ |    4 | * | * | * | @ | ^ | @ |
    --- --- --- --- --- ---        --- --- --- --- --- ---
     1   2   3   4   5   6          1   2   3   4   5   6

Assessment

За задание можно получить макс. 2 балла. Будет проверено автоматически.

Task 3: Проверка собранных столбцов

Запрограммируйте функцию bool check(const int rows, const int columns, char field[rows][columns]) со следующими параметрами:

  • const int rows - Количество рядков в массиве
  • const int columns - Количество столбцов в массиве
  • char field[rows][columns] - Массив, в котором содержатся символы

Функция возвратит значение true, если все символы во всех столбцах одинаковы. В противном случае функция возвратит значение false. Помните, что практически пустой столбец с двумя одинаковыми знаками ещё не является собранным.

Функция возвратит false:

 1 |   |   | ^ |   |   |   |
 2 | + |   | ^ | @ | ^ |   |
 3 | + |   | * | + | + | @ |
 4 | * | * | * | @ | ^ | @ |
    --- --- --- --- --- ---
     1   2   3   4   5   6

Функция возвратит true:

 1 |   | @ | + | * |   | ^ |
 2 |   | @ | + | * |   | ^ |
 3 |   | @ | + | * |   | ^ |
 4 |   | @ | + | * |   | ^ |
    --- --- --- --- --- ---
     1   2   3   4   5   6

Assessment

За задание можно получить макс. 2 балла. Будет проверено автоматически.

Task 4: Игровое поле

Запрограммируйте функцию void game_field(const int rows, const int columns, char field[rows][columns]) со следующими параметрами:

  • const int rows - Количество рядков в массиве
  • const int columns - Количество столбцов в массиве
  • char field[rows][columns] - Массив, в котором содержатся символы

Функция ничего не возвращает.

Программирование данной функции полностью за вами. Она нам послужит для "рисования" игрового поля. Чем креативнее, тем лучше. Для написания функции можете использовать библиотеку curses.h.

Assessment

За задание можно получить макс. 2 балла. Оно будет оценено Вашим преподавателем. Сделайте скриншот и загрузите его вместе с проектом под названием task_4.png.

Task 5: Игра

Запрограммируйте функцию void ball_sort_puzzle(), отвечающую за работу всей игры.

Функция ничего не возвращает.

В этой функции Вам предстоит использовать все ранее созданные: bool check(), void down_possible(), void generator() и void game_field().

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

В первую очерень спросите у игрока номер столбца, откуда он хотел бы передвинуть символ, после чего место, куда выбранный элемент должен отправиться. Полученную информацию предоставляем функции void down_possible() в качестве аргумента. Также после каждого перемещения было бы неплохо проверить состояние игрового поля функцией bool check(). То, как игра закончится, можете решить сами. К примеру, по окончании игры программа может вывести следующее сообщение: Congratulations! You won!

Пример хода игры 1:

$ ./ballsortpuzzle
 1 | * | @ |   |   |   |   |
 2 | * | @ |   |   |   | ^ |
 3 | + | @ |   | + | * | ^ |
 4 | ^ | @ | + | * | + | ^ |
    --- --- --- --- --- ---
     1   2   3   4   5   6

 Enter what: 4

 Enter where: 2
 MUST BE SAME

 1 | * | @ |   |   |   |   |
 2 | * | @ |   |   |   | ^ |
 3 | + | @ |   | + | * | ^ |
 4 | ^ | @ | + | * | + | ^ |
    --- --- --- --- --- ---
     1   2   3   4   5   6

 Enter what: 4

 Enter where: 3

 1 | * | @ |   |   |   |   |
 2 | * | @ |   |   |   | ^ |
 3 | + | @ | + |   | * | ^ |
 4 | ^ | @ | + | * | + | ^ |
    --- --- --- --- --- ---
     1   2   3   4   5   6

Пример хода игры 2:

$ ./ballsortpuzzle
 1 |   | @ |   | * |   |   |
 2 |   | @ | + | * |   | ^ |
 3 | + | @ | + | * |   | ^ |
 4 | ^ | @ | + | * |   | ^ |
    --- --- --- --- --- ---
     1   2   3   4   5   6

 Enter what: 1

 Enter where: 3

 1 |   | @ | + | * |   |   |
 2 |   | @ | + | * |   | ^ |
 3 |   | @ | + | * |   | ^ |
 4 | ^ | @ | + | * |   | ^ |
    --- --- --- --- --- ---
     1   2   3   4   5   6

 Enter what: 1

 Enter where: 6

 1 |   | @ | + | * |   | ^ |
 2 |   | @ | + | * |   | ^ |
 3 |   | @ | + | * |   | ^ |
 4 |   | @ | + | * |   | ^ |
    --- --- --- --- --- ---
     1   2   3   4   5   6

 YOU WON

Assessment

За задание можно получить макс. 2 балла. Оно будет оценено Вашим преподавателем. Сделайте скриншот и загрузите его вместе с проектом под названием task_5.png.

Connect Four

Игра Connect Four, рассчитанная на двух игроков, действует по принципу, аналогичному игре в хрестики нолики. Выигрывает тот, кто первым выстроит свои четыре фишки в горизонтальный, вертикальный или диагональный ряд.

Размер игрового поля должен быть не менее 4x4. Игрок меняется после каждого хода. Игра начинается на пустом игровом поле. Первый игрок помещает свою фишку в любой столбец. Игра заканчивается вничью, если все игровое поле заполнено или у одного из игроков есть 4 кольца, выстроенные по вертикали, горизонтали или диагонали.

В нашем случае игровое поле будет представлено двумерным массивом символов, у игрока номер 1 фишка будет представлена символом X, а у игрока номер 2 символом O.

Ваша задача - запрограммировать 6 функций:

  • void initialize_board(int rows, int cols, char board[rows][cols]) - Функция инициализирует пустое игровое поле
  • void print_board(int rows, int cols, const char board[rows][cols]) - Функция выводит в стандартный вывод текущее состояние игрового поля
  • int is_valid_move(int rows, int cols, const char board[rows][cols], int col) - Функция проверяет, можно ли выполнить этот ход
  • int drop_piece(int rows, int cols, char board[rows][cols], int col, char player_piece) - Функция помещает фишку игрока в заданный столбец
  • int check_win(int rows, int cols, const char board[rows][cols], int row, int col, char player_piece) - Функция проверяет наличие выигрыша по каждому из направлений
  • int is_board_full(int rows, int cols, const char board[rows][cols]) - Функция определяет, заполнено ли уже игровое поле, и, следовательно, происходит ли ничья

Все 6 функций будут находиться в файле c4.c. Их объявления перечислены в файле c4.h. Основная программа находится в файле main.c.

В дополнение к необходимым функциям можно создавать и свои собственные. Однако они будут являться приватными для вашего модуля (они не будут объявлены в заголовочном файле c4.h и не будут видны в других модулях).

Task 6: Инициализация поля

Создайте функцию void initialize_board(int rows, int cols, char board[rows][cols]), которая предназначена для инициализации игрового поля с тремя параметрами:

  • int rows - количество рядов игрового поля
  • int cols - количество столбцов игрового поля
  • char board[rows][cols] - массив символов, представляющих игровое поле

Функция не возвращает никаких значений.

Это задание оценивается в макс. 0,5 балла. Оно будет проверено автоматической тестировкой.

Task 7: Визуализация игрового поля

Создайте функцию void print_board(int rows, int cols, const char board[rows][cols]), принимающую три параметра для отображения текущего состояния игрового поля:

  • int rows - количество рядов игрового поля
  • int cols - количество столбцов игрового поля
  • char board[rows][cols] - массив символов, представляющих игровое поле

Функция не возвращает никаких значений.

Это задание рассматривается как часть задания 12 - Графический интерфейс. Оно будет оцениваться вашим преподавателем.

Пример использования функций:

    int rows = 4;
    int cols = 5;
    char board[rows][cols];

    initialize_board(rows, cols, board);

    int player_turn = 1; 

    print_board(rows, cols, board);

    //prints

/*  | . | . | . | . | . |
    | . | . | . | . | . |
    | . | . | . | . | . |
    | . | . | . | . | . |
    ---------------------
    1   2   3   4   5       */

Task 8: Validácia ťahu

Создайте функцию int is_valid_move(int rows, int cols, const char board[rows][cols], int col), которая проверяет, можно ли делать этот ход, с помощью четырех параметров:

  • int rows - количество рядов игрового поля
  • int cols - количество столбцов игрового поля
  • char board[rows][cols] - массив символов, представляющих игровое поле
  • int col - порядковый номер столбца, в который вкладывается фишка

Функция возвращает 1, если ход может быть выполнен, иначе возвращает 0.

Это задание оценивается в макс. 0,75 балла. Оно будет проверено автоматической тестировкой.

Task 9: Размещение фишки

Создайте функцию int drop_piece(int rows, int cols, char board[rows][cols], int col, char player_piece), которая помещает фишку текущего игрока в массив и имеет пять параметров:

  • int rows - количество рядов игрового поля
  • int cols - количество столбцов игрового поля
  • char board[rows][cols] - массив символов, представляющих игровое поле
  • int col - порядковый номер столбца, в который вкладывается фишка
  • char player_piece - фишка текущего игрока

Функция размещает фишку и возвращает значение 1, если фишка была успешно размещена, в противном случае возвращается значение -1.

Это задание оценивается в макс. 0,75 балла. Оно будет проверено автоматической тестировкой.

Task 10: Проверка выигрыша

Создайте функцию int check_win(int rows, int cols, const char board[rows][cols], int row, int col, char player_piece), которая проверяет победу текущего игрока в каждом направлении при помощи шести параметров:

  • int rows - количество рядов игрового поля
  • int cols - количество столбцов игрового поля
  • char board[rows][cols] - массив символов, представляющих игровое поле
  • int row - порядковый номер проверяемого ряда
  • int col - порядковый номер проверяемого столбца
  • char player_piece - фишка текущего игрока

Функция возвращает 1, если текущий игрок выиграл, иначе она возвращает 0.

Это задание оценивается в макс. 0,5 балла. Оно будет проверено автоматической тестировкой.

Task 11: Проверка на ничью

Создайте функцию int is_board_full(int rows, int cols, const char board[rows][cols]), которая проверяет, заполнено ли игровое поле и следовательно, является ли это ничьей используя три параметра:

  • int rows - количество рядов игрового поля
  • int cols - количество столбцов игрового поля
  • char board[rows][cols] - массив символов, представляющих игровое поле

Функция возвращает 1, если массив заполнен, в противном случае она возвращает 0.

Это задание оценивается в макс. 0,5 балла. Оно будет проверено автоматической тестировкой.

Пример использования функций:

    if (check_win(rows, cols, board, row, column - 1, (player_turn == 1) ? 'X' : 'O')) {
        //...
        printf("Player %d wins!\n", player_turn);
        //....

    if (is_board_full(rows, cols, board)) {
        //....
        printf("It's a draw!\n");
        //...

Пример геймплея

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

Player 1, enter your move (1-5): 1

| . | . | . | . | . |
| . | . | . | . | . |
| . | . | . | . | . |
| X | . | . | . | . |
---------------------
  1   2   3   4   5 

Player 2, enter your move (1-5): 2

| . | . | . | . | . |
| . | . | . | . | . |
| . | . | . | . | . |
| X | O | . | . | . |
---------------------
  1   2   3   4   5 

Player 1, enter your move (1-5): 1

| . | . | . | . | . |
| . | . | . | . | . |
| X | . | . | . | . |
| X | O | . | . | . |
---------------------
  1   2   3   4   5 

Player 2, enter your move (1-5): 2

| . | . | . | . | . |
| . | . | . | . | . |
| X | O | . | . | . |
| X | O | . | . | . |
---------------------
  1   2   3   4   5 

Player 1, enter your move (1-5): 2

| . | . | . | . | . |
| . | X | . | . | . |
| X | O | . | . | . |
| X | O | . | . | . |
---------------------
  1   2   3   4   5 

Player 2, enter your move (1-5): 3

| . | . | . | . | . |
| . | X | . | . | . |
| X | O | . | . | . |
| X | O | O | . | . |
---------------------
  1   2   3   4   5 

Player 1, enter your move (1-5): 1

| . | . | . | . | . |
| X | X | . | . | . |
| X | O | . | . | . |
| X | O | O | . | . |
---------------------
  1   2   3   4   5 

Player 2, enter your move (1-5): 2

| . | O | . | . | . |
| X | X | . | . | . |
| X | O | . | . | . |
| X | O | O | . | . |
---------------------
  1   2   3   4   5 

Player 1, enter your move (1-5): 1

| X | O | . | . | . |
| X | X | . | . | . |
| X | O | . | . | . |
| X | O | O | . | . |
---------------------
  1   2   3   4   5 

Player 1 wins!

Task 12: Графический интерфейс

Созданные функии обработайте в игровой цикл и реализуйте удобный для пользователя графический интерфейс.

За графический дизайн можно получить 2 балла. Графический дизайн будет оцениваться вашим преподавателем. Загрузите скриншот экрана task_12.png в папку задания.

Project Submission

Задание необходимо сдать до 05.12.2024 (четверг). Последние тесты будут запущены в полночь этой даты.

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

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

Иерархия файлов и директорий обязана быть именно такой, как это изображено ниже:

.
├── ps4
│   ├── ballsortpuzzle.c
│   ├── ballsortpuzzle.h
│   ├── c4.c
│   ├── c4.h
│   ├── main.c
│   ├── task_4.png
│   ├── task_5.png
│   ├── task_12.png
└── README

Значение отдельных файлов:

  • README - файл, в котором указывается группа, посещаемая Вами на практиках. Она должна быть строго в формате:
GROUP : C1
  • /ps4/ballsortpuzzle.c - Исходный код библиотеки для игры ball sort puzzle.
  • /ps4/ballsortpuzzle.h - Заголовочный файл библиотеки ball sort puzzle.
  • /ps4/main.c - Исходный код, содержащий функцию main().
  • /ps4/task_4.png - Скриншот для задания под номером 4.
  • /ps4/task_5.png - Скриншот для задания под номером 5.
  • /ps4/task_12.png - Скриншот графического интерфейса Connect Four.
  • /ps4/c4.c - Исходный код библиотеки для игры c4.
  • /ps4/c4.h - Заголовочный файл библиотеки c4.

Предупреждение

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

Предупреждение

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

Комментарий

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

Предупреждение

Используя утилиту Makefile, не забывайте, что компиляция происходит при помощи команды make all.

Project Skeleton

По следующей ссылке скачайте архив ballsortpuzzle.zip, содержащий скелет проекта. Данный архив содержит следующие файлы:

  • ballsortpuzzle.h - Заголовочный файл, в котором содержатся объявления всех требуемых функций.
  • ballsortpuzzle.c - Исходный файл, в котором будет находится реализованый Вами функционал.

Для загрузки файла в среде OS Linux можете использовать wget в следующем виде:

wget http://kurzy.kpi.fei.tuke.sk/zap/resources/ballsortpuzzle.zip

Затем по указанной ссылке загрузите файл connectfour.zip, содержащий скелет проекта Connect Four. Этот пакет содержит следующие файлы:

  • c4.c - Исходный файл, в котором будет находится реализованый вами функционал.
  • c4.h - Заголовочный файл, содержащий объявления всех необходимых функций для игры Connect Four.

В среде OS Linux можно использовать команду wget в следующем виде:

wget http://kurzy.kpi.fei.tuke.sk/zap/resources/connectfour.zip

Assessment and Testing

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

  • Иерархия файлов (находятся ли в репозитории все нужные файлы).
  • Функционал вашей реализации.

Последние задания будут проверены Вашим преподавателем. Не забудьте загрузить скриншоты вместе с пректом.

Ваш код будет компилироваться командой gcc со следующими опциями:

gcc -std=c11 -Werror -Wall -Wno-vla-parameter -lcurses

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

  • Использование глобальной переменной.
  • Ошибки во время компиляции (предупреждения трактуются как ошибки).
  • Если ваша реализация не пройдёт какие-то из тестов.

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

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