Домашнее задание для 2 семестра алгоритмов и структур данных

Для удобства можно пользоваться папкой lib, все файлы из этой папки будут подключаться к любой задаче

Можно получить дополнительные баллы, если добавить интересные текстовые задачи. Необходимы текст задачи, решение и тесты. Каждая задача отдельный ПР, полчуть дополнительные баллы можно только если пулл реквест замержен в основную ветку.

Можно получить дополнительные баллы, если добавить теорию в папку doc. Делается в отдельном ПР, полчуть дополнительные баллы можно только если пулл реквест замержен в основную ветку.

Код должен быть отформатирован clang-format'ом со стилем Google

Карта проекта

• doc - теория, которую добавляет преподаватель или студенты
• lib - папка для ваших структур, которые вы используете во множестве задач
• additional tasks - сюда обычно оформляются особые задания от преподавателя (как дополнительная теория, или личные задания)

Каждое задание выглядит так:

• task_N
  • src
    • main.cpp - нужен для вашего личного тестирования результата. Для проверки он не используется
    • test.cpp - здесь в должны написать тестирование вашего алгоритма с помощью <gtest/gtest.h>
  • CMakeLists.txt
  • README.md - тут описано задание и требования к используемому алгоритму

Инструкция для работы с репозиторием

1. Создайте fork этого репозитория
2. Перейдите в него, и найдите зеленую кнопку Code
3. В открывающемся списке выберите левую вкладку Codespaces
4. Создайте новое окружение (метка "+") или откройте старое

Готово!

Советы при работе с codespaces

• При работе с заданиями желательно создавать файлы .hpp и .cpp с заданием, причем .hpp - именно заголовочный файл, который будет импортироваться вами в test.cpp для тестирования
• Если вы работаете через VS Code, то чтобы поменять цель сборки, нажмите Ctrl+p, и введите >CMake: Set Launch/Debug Target
• Если при запуске тестов консоль остается пустой, проверьте что int main() внутри main.cpp соответствующего задания пуст
• Если вся среда неожиданно зависла и очень долго пытается соединиться с сервером - попробуйте выключить интернет на 10 секунд и включить снова. Если не помогает - ищите более надежную сеть(
• При ошибке ./googletest/src/gtest-internal-inl.h:685:: Condition !original_working_dir_.IsEmpty() failed проверьте что структура задания не нарушена: main.cpp, test.cpp

Шаблон теста:

#include <gtest/gtest.h>

Test(test_name, test_number) {
    /* code */
    ASSERT_EQ(expected_value, real_value); // лучше сравнивать что то простое, например bool и int
}

Скрипт для проверки решений (run_cases.py)

В репозитории есть скрипт scripts/run_cases.py, который запускает собранные исполняемые файлы задач и сравнивает их вывод с эталонами.

Как подготовить тесты (по умолчанию — внутри папки задачи):

task_01/
  src/
  tests/
    case1.in
    case1.out
    case2.in
    case2.out

Запуск проверок для одной или нескольких задач:

python3 scripts/run_cases.py --tasks task_01
# или несколько задач
python3 scripts/run_cases.py --tasks task_01 task_02

Полезные флаги:

• --tests-layout in-task|central — где лежат тесты (по умолчанию in-task).
• --tests-dir <path> — путь к центральной папке тестов (если --tests-layout=central).
• --timeout <sec> — таймаут на тест (по умолчанию 2.0).
• --time-limit <sec> — мягкий лимит времени на кейс. Если превышен, кейс помечается как SLOW.
• --fail-on-slow — завершать с ошибкой, если есть SLOW кейсы (используйте вместе с --time-limit).
• --report-slowest N — вывести N самых медленных кейсов в конце отчёта.
• --mem-limit-mb <MB> — мягкий лимит памяти на кейс. Если превышен, помечается как MEM_EXCEEDED.
• --fail-on-mem — завершать с ошибкой, если есть MEM_EXCEEDED (используйте вместе с --mem-limit-mb).
• --report-memtop N — вывести N кейсов с наибольшим использованием памяти.
• --normalize strip|keep|lines — нормализация вывода при сравнении (по умолчанию strip).
• --write-missing — если .out отсутствует, записать текущий вывод как эталон.
• --update-expected — перезаписать существующие .out текущим выводом.
• --save-actual — при несовпадении сохранить фактический вывод в <case>.out.actual.

Примечание: в CI пока настроен только запуск скрипта для task_01 (см. .github/workflows/ci.yml).

Статусы результатов:

• OK: вывод совпал с эталоном.
• FAIL: вывод отличается от эталона (при --save-actual сохранится <case>.out.actual).
• TIMEOUT: программа превысила лимит времени (--timeout).
• SLOW: программа превысила мягкий лимит времени (--time-limit). Можно сделать критичным флагом --fail-on-slow.
• MEM_EXCEEDED: программа превысила мягкий лимит памяти (--mem-limit-mb). Можно сделать критичным флагом --fail-on-mem.
• NO_EXPECTED: отсутствует файл эталона .out для кейса (можно создать через --write-missing).
• EXEC_MISSING: не найден исполняемый файл задачи в build/<task>/<task>.