Я преподаю в университете дисциплину «Алгоритмы и структуры данных». Как и многие преподаватели программирования, значительную часть практических заданий я проверяю автоматически. Долгое время для этого использовал Stepik. Создавал собственные задания, готовил тестовые наборы, настраивал проверку решений и затем использовал всё это при проведении лабораторных работ.
В целом такой подход меня устраивал. Студенты могли отправлять свои решения на Python или R и практически сразу получать результат проверки. Мне же не приходилось вручную запускать десятки программ и сравнивать полученные ответы с эталонными. Однако недавно ситуация изменилась.
После инцидента, затронувшего инфраструктуру Яндекса, возникли серьёзные проблемы с доступностью ряда сервисов. Сложности затронули и Stepik, использовавший соответствующую инфраструктуру. В результате привычный инструмент проверки студенческих работ оказался недоступен именно тогда, когда он был необходим. Разумеется, можно было временно вернуться к ручной проверке. Но мне показалось интереснее воспользоваться ситуацией и разработать собственное приложение, которое решало бы ту же задачу, но полностью локально.
Так появился Algorithm Judge – небольшое настольное приложение для автоматизированной проверки решений алгоритмических задач на Python и R.
Почему не ограничиться обычным набором тестов?
При разработке я решил не просто воспроизвести привычную функциональность Stepik, а немного пересмотреть сам подход к проверке алгоритмических задач. Классическая система автоматической проверки обычно работает следующим образом: имеется заранее подготовленный набор входных данных и правильных ответов. Программа студента запускается на каждом тесте, после чего результаты сравниваются.
Но у этого подхода есть ограничения. Во-первых, необходимо заранее подготовить достаточно качественный набор тестов. Причём не только очевидные примеры, но и разнообразные граничные ситуации. Во-вторых, некоторые алгоритмические задачи допускают несколько правильных ответов. Например, для одного ориентированного ациклического графа может существовать сразу несколько корректных топологических порядков. Простое сравнение вывода программы с единственным эталонным ответом в таком случае не подходит. В-третьих, сообщение Wrong Answer практически ничего не говорит о характере ошибки. При проверке лабораторных работ преподавателю зачастую приходится самостоятельно искать входные данные, на которых решение работает неправильно, а затем разбираться в причине.
Поэтому в Algorithm Judge я решил реализовать несколько дополнительных возможностей.
Программная генерация тестов
Одна из основных идей приложения — автоматическое создание входных данных для проверки решений.
Вместо того чтобы вручную формировать десятки или сотни тестов, программа самостоятельно генерирует графы с различными характеристиками.
Например, при проверке алгоритма Дейкстры это могут быть:
графы с изолированными вершинами;
графы с несколькими альтернативными маршрутами;
графы с большими весами рёбер;
ситуации, когда прямое ребро оказывается значительно дороже обходного пути;
большие графы для проверки производительности.
А для топологической сортировки – графы с несколькими допустимыми порядками, независимыми вершинами, длинными цепочками зависимостей и циклами. При этом генерация не ограничивается исключительно случайными графами. Для каждого задания предусмотрены специальные категории тестов, направленные на проверку характерных граничных ситуаций и распространённых ошибок реализации. В приложении доступны несколько режимов тестирования: быстрая проверка, стандартная и углублённая. При необходимости можно самостоятельно задать количество тестов.
Ещё одна полезная возможность – воспроизводимость генерации. Используя один и тот же seed, можно повторно проверить программу на идентичных входных данных. Для преподавателя это особенно удобно: если решение работает неправильно, всегда можно вернуться к конкретному тестовому набору после исправления кода.
Проверка математической корректности результата
Ещё одна интересная особенность – поддержка семантической проверки. Возьмём ту же топологическую сортировку. Пусть у нас есть ориентированный граф со следующими рёбрами:
1 3 2 3 3 4
Для него допустимы как минимум два топологических порядка:
1 2 3 4
и
2 1 3 4
Оба являются математически корректными. Если условие требует вывести любой правильный топологический порядок, система должна принять оба результата. Поэтому вместо обычного сравнения строк проверяется, что каждая вершина присутствует ровно один раз, а для каждого ребра u → v вершина u расположена раньше v. Аналогичная ситуация возникает при восстановлении кратчайшего пути, построении минимального остовного дерева или поиске максимального паросочетания.
В таких задачах гораздо правильнее проверять математические свойства результата, чем сравнивать его с единственным заранее подготовленным ответом. Конечно, если в условии явно требуется, например, лексикографически минимальный порядок, проверка должна учитывать и это ограничение.
Диагностика ошибок
Отдельное внимание я уделил информативности результатов проверки. Вместо одного сообщения о неправильном ответе преподаватель получает информацию о конкретном тесте, на котором возникла ошибка. Можно посмотреть входные данные, ожидаемый результат и фактический вывод студенческой программы.
Например, рассмотрим следующий граф для алгоритма Дейкстры:
4 4 1 1 2 10 1 3 2 3 2 3 2 4 1
Правильные расстояния от первой вершины:
0 5 2 6
Но если программа неправильно обновляет расстояния, она может вывести:
0 10 2 11
По такому примеру уже можно понять, в каком направлении искать проблему: путь из первой вершины во вторую через третью оказывается короче прямого ребра. Преподавателю гораздо проще объяснить ошибку на конкретном тесте, чем пытаться восстановить её по исходному коду. Кроме того, при тестировании можно использовать большие наборы данных, позволяющие выявлять проблемы с производительностью алгоритмов.
Поддержка Python и R
Поскольку в преподавании я использую оба языка программирования, приложение поддерживает проверку решений как на Python, так и на R. Я сознательно не стал усложнять интерфейс системой загрузки и автоматического распознавания студенческих файлов.
Работа организована максимально просто:
Выбирается лабораторная работа и конкретное задание.
В интерфейсе отображается полное условие задачи.
Выбирается язык программирования — Python или R.
В редактор вставляется программный код.
Запускается тестирование.
Преподаватель получает подробный результат проверки.
Если в файле студента находятся решения нескольких заданий, я самостоятельно выбираю нужную функцию для запуска.
Это именно тот сценарий, который мне необходим при проверке лабораторных работ.
При этом преподавателю не требуется отдельно подготавливать входные данные — система генерирует их самостоятельно.
Какие алгоритмы поддерживаются?
Первоначально приложение разрабатывалось под второй модуль моей дисциплины, посвящённый алгоритмам на графах.
В него входят восемь лабораторных работ, объединяющих 38 заданий.
№ | Лабораторная работа | Количество заданий |
|---|---|---|
1 | Основы теории графов и их представление в памяти | 6 |
2 | Обходы графов: DFS и BFS | 6 |
3 | Топологическая сортировка и работа с DAG | 8 |
4 | Алгоритм Дейкстры | 3 |
5 | Алгоритмы Беллмана–Форда и Флойда–Уоршелла | 5 |
6 | Минимальные остовные деревья | 6 |
7 | Алгоритмы на потоках в сетях | 2 |
8 | Максимальное паросочетание | 2 |
Всего | 38 |
Среди рассматриваемых алгоритмов – поиск в глубину и ширину, алгоритмы Кана и Демукрона, Дейкстры, Беллмана–Форда, Флойда–Уоршелла, Крускала, Прима, Форда–Фалкерсона, Эдмондса–Карпа и Куна.
Для каждого задания подготовлены условия, механизмы генерации входных данных и проверки результатов. В дальнейшем планирую расширить систему и на первый модуль дисциплины, в котором рассматриваются другие алгоритмы и структуры данных.
Немного о технической реализации
Приложение разработано на Python с использованием PySide6 (Qt) для графического интерфейса. Я выбрал формат настольной программы, поскольку мне не требуется полноценная серверная инфраструктура, управление пользователями или организация онлайн-проверки.
Главная задача — иметь под рукой автономный инструмент, который можно запустить непосредственно на компьютере преподавателя.
Внутри приложение объединяет несколько основных компонентов:
Генераторы тестов создают входные данные с учётом условий и ограничений конкретной задачи.
Эталонные алгоритмы вычисляют правильные результаты.
Валидаторы определяют корректность вывода студенческой программы.
Исполняющий модуль запускает код на Python или R и получает результаты выполнения.
Графический интерфейс позволяет выбирать задания, редактировать код и анализировать ошибки.
Сам проверяемый код выполняется в отдельных процессах, с ограничениями времени выполнения. При этом приложение не использует Docker. Стоит учитывать, что такой механизм не обеспечивает полноценной изоляции от потенциально вредоносного кода. В моём случае программа предназначена для локальной проверки учебных решений, а не для публичного запуска произвольных программ из интернета. Для работы используются собственные интерпретаторы Python и R, включённые в поставку приложения. Таким образом, пользователю не требуется отдельно устанавливать и настраивать программное окружение.
Автоматизация сборок
Ещё одна задача, которую пришлось решить, – распространение приложения для разных операционных систем. Основная разработка ведётся у меня на macOS с процессором Apple Silicon, но хотелось обеспечить возможность работы и на Windows.
Для этого я использовал GitHub Actions, позволяющий автоматически собирать приложение на виртуальных машинах соответствующих операционных систем.
В результате предусмотрены две версии:
macOS ARM64 — приложение в формате .app, распространяемое через .dmg.
Windows x64 — автономный исполняемый файл .exe.
Для Windows я отдельно поставил требование распространять программу одним файлом, без необходимости копировать рядом папки с библиотеками и интерпретаторами. Для упаковки используется PyInstaller.
Следует понимать, что в режиме onefile необходимые компоненты при запуске распаковываются во временную директорию. Тем не менее пользователю достаточно одного EXE-файла. Использование GitHub Actions избавляет меня от необходимости поддерживать отдельный Windows-компьютер исключительно ради сборки приложения.
Почему именно локальное приложение?
Главной причиной разработки стала необходимость снизить зависимость учебного процесса от доступности внешних сервисов. Но постепенно обнаружились и дополнительные преимущества.
Во-первых, я могу полностью контролировать алгоритмы генерации тестов и правила проверки решений.
Во-вторых, могу изменять количество тестов и проверять нестандартные ситуации без необходимости вручную загружать новые наборы данных на образовательную платформу.
В-третьих, приложение позволяет более подробно анализировать ошибки и использовать результаты непосредственно в процессе объяснения материала студентам.
Наконец, всё это работает локально и не требует постоянного подключения к интернету. Разумеется, Algorithm Judge не является полноценной заменой Stepik. В нём нет системы дистанционного обучения, управления группами, электронного журнала или других возможностей образовательной платформы. Но такой задачи и не ставилось.
Мне нужен был инструмент, позволяющий открыть программу, вставить код студента, выбрать задание и получить результат достаточно глубокой автоматизированной проверки. Именно эту задачу я и решал.
Что дальше?
Изначально Algorithm Judge создавался как решение конкретной проблемы, возникшей при проведении лабораторных работ. Однако в процессе разработки стало понятно, что подобный инструмент может оказаться полезен и другим преподавателям программирования. Особенно интересным мне кажется сочетание трёх подходов: автоматической генерации тестов, проверки математических свойств ответа и подробной диагностики ошибок.
В дальнейшем планирую добавить первый модуль дисциплины, расширить перечень поддерживаемых алгоритмов и продолжить совершенствование проверяющих механизмов. Кроме того, было бы интересно развивать приложение не только как инструмент преподавателя, но и как средство самостоятельной проверки алгоритмических решений.
Где можно получить Algorithm Judge?
Я подготовил отдельную публикацию на Boosty, где подробнее описал приложение и разместил сборки для macOS и Windows.
Algorithm Judge — описание проекта и готовые сборки на Boosty
Буду рад обратной связи от преподавателей программирования и разработчиков подобных систем.
