💻 Tech-радар: Algorithm Judge: как проблемы с доступностью Stepik подтолкнули меня к созданию собственной системы проверки алгоритмов
Преподаватель университета, ведущий дисциплину «Алгоритмы и структуры данных», столкнулся с недоступностью сервиса Stepik, который он долгое время использовал для автоматической проверки практических заданий. После инцидента, затронувшего инфраструктуру Яндекса, возникли серьёзные проблемы с доступностью ряда сервисов, и сложности коснулись Stepik, использовавшего эту инфраструктуру. Привычный инструмент проверки студенческих работ оказался недоступен именно тогда, когда был необходим. Вместо возврата к ручной проверке преподаватель разработал собственное приложение — Algorithm Judge.
Algorithm Judge — небольшое настольное приложение для автоматизированной проверки решений алгоритмических задач на Python и R, работающее полностью локально. Ранее преподаватель создавал задания в Stepik, готовил тестовые наборы, настраивал проверку решений и использовал всё это на лабораторных работах: студенты отправляли решения на Python или R и практически сразу получали результат, а преподавателю не приходилось вручную запускать десятки программ и сравнивать ответы с эталонными.
При разработке автор решил пересмотреть сам подход к проверке. Классическая схема предполагает заранее подготовленный набор входных данных и правильных ответов, с которыми сравнивается вывод программы студента, но у неё есть ограничения: нужен качественный набор тестов, включая граничные ситуации; некоторые задачи допускают несколько правильных ответов, как в случае ориентированного ациклического графа с несколькими корректными топологическими порядками; а сообщение Wrong Answer почти ничего не говорит о характере ошибки. Поэтому в Algorithm Judge реализовано автоматическое создание входных данных: программа сама генерирует графы с различными характеристиками. Для алгоритма Дейкстры это, например, ситуации, когда прямое ребро оказывается значительно дороже обходного пути, а для топологической сортировки — графы с несколькими допустимыми порядками, независимыми вершинами, длинными цепочками зависимостей и циклами. Предусмотрены специальные категории тестов на характерные граничные ситуации и распространённые ошибки реализации, а также режимы быстрой, стандартной и углублённой проверки с возможностью задать количество тестов вручную.
Отдельная особенность — воспроизводимость генерации: при одном и том же seed программу можно повторно проверить на идентичных входных данных, что удобно преподавателю, если решение работает неправильно и нужно вернуться к конкретному тестовому набору после исправления кода. Кроме того, поддерживается семантическая проверка. В задаче топологической сортировки вместо сравнения строк система проверяет, что каждая вершина присутствует ровно один раз, а для каждого ребра u → v вершина u расположена раньше v, поэтому оба математически корректных порядка принимаются. Аналогичный подход применим при восстановлении кратчайшего пути, построении минимального остовного дерева или поиске максимального паросочетания: правильнее проверять математические свойства результата, чем сравнивать его с единственным заранее подготовленным ответом. Если же в условии явно требуется, например, лексикографически минимальный порядок, проверка должна учитывать и это ограничение.
Для преподавателей, проверяющих лабораторные работы по алгоритмам, такой инструмент означает меньшую зависимость от внешних сервисов и меньше ручной работы при разборе ошибок, а для студентов — быстрый результат проверки решений на Python и R. Локальный формат приложения позволяет решать задачу автоматической проверки даже тогда, когда сторонние платформы недоступны.
Категория: Технологии
Теги: #Технологии #Tech #IT #Искра