notes.md

Предыстория

Характерная черта некоторых соревнований по программированию (речь не про какие-нибудь хакатоны, скорее про что-то в стиле ACM ICPC) — автоматическая система проверки. Если участник (команда) думает, что у него есть готовое решение по задаче, он отправляет его в специальную тестирующую систему и, в зависимости от того, как его код работает на разных заранее подготовленных тестах, получает какой-то результат. Такое подход позволяет относительно легко взять готовые задачи из архивов каких-нибудь старых олимпиад и устроить на их основе тренировочное соревнование, или использовать архивы с большим количеством задач для обучения. Серверы железные, что им сделается.

Проверка решения как правило представляет из себя полностью автоматизированный и зачастую формализованный процесс: что-то вроде «решение считается верным, если на каждом тесте отработало, уложилось в заранее заданные ограничения по времени и памяти, выдало верный ответ»). Однако, подготовка задач — процесс творческий. Но мало того, что «придумать задачу, разработать тесты» — ожидаемо работа для человека, оказывается, что и «взять задачу из какого-нибудь архива и переиспользовать её» — тоже плохо автоматизируемое действие. Дело в том, что нет какого-либо общепринятого (хотя бы неформального) стандарта о том, что же такое задача для соревнования по программированию.

Бывают задачи с необычной системой оценки или необычным методом запуска (интерактивные, «грейдеры», возможны ещё варианты). Бывают архивы, в которых лежат файлы с готовыми тестами (и те называются по-разному в разных архивах), бывают генераторы, которые для получения тестов предполагается каким-то образом запускать. Бывает, что ответ в задаче достаточно побайтово сравнить с эталоном, бывает что для проверки нужно использовать специальную программу.

Тем не менее, даже со старыми задачами порой хочется что-то сделать: добавить в тренировку, добавить тестов, каких-нибудь дополнительных утилит (валидатор чтобы убедиться, что все тесты корректны, визуализатор чтобы на них наглядно позалипать, что-нибудь ещё), позапускать решения (например, посмотреть на время работы). Утилита t.py — попытка автоматизировать базовую работу с задачами разных типов и из разных источников. Она использует различные эвристики и соглашения чтобы выцепить параметры запуска решений, команды генерации тестов и прочее.

Происхождение

Утилита t.py исторически появилась как клон некой «TEST TOOL» (также известной как t.cmd, авторства Романа Елизарова, позднее ещё и Георгия Корнеева), которая использовалась в ИТМО для разработки задач и интегрирования их в PCMS2.

К сожалению, TEST TOOL суть пакетный файл для Windows. В 2009-м году в жюри четвертьфинала (NEERC, Nothern Subregional) появились линуксоиды (например, в лице @burunduk3), которые сделали t.sh — урезанный клон t.cmd, написанный на bash. Позднее его переписали на python3.

Общее

Утилита t.py предполагает, что вся нужная информация доступна локально в файлах и как-то сгруппирована. Работа с задачами вне локальной файловой системы (например, в системе polygon) пока не поддерживается, но предполагается в будущих версиях.

Для каждого теста существует «эталонный ответ». Обычно это ответ, который выводит авторское решение, но это не догма: теоретически в файле с эталонным ответом может быть любая вспомогательная информация для проверки ответа участника.

Определения

Валидатор (validator) — программа, проверяющая корректность теста.

Задача (problem) — директория, содержимое которой соответствует хотя бы одному формату задачи.

Генератор (generator) — программа (зачастую скрипт, вызывающий в том числе другие программы), генерирующая тесты (один или несколько). По умолчанию генератором называется та из них, которая генерирует все тесты к задаче.

Интерактор (interactor) — программа, используемая для запуска интерактивных решений (очередные входные данные предоставляются только после вывода участника и могут от него зависеть).

Чекер (checker, также проверяющая программа) — программа, используемая для проверки корректности ответов участников.

Соглашения

Интерактор

Принимает два параметра: имя входного файла и имя выходного.

Чекер

Принимает три параметра: имя файла с тестом, с ответом и с эталонным ответов, возвращает 0 если ответ корректный, 1 если ответ неверный, 2 если ответ не подходит под формат, 3 и более в остальных случаях (например, оказался некорректным ответ жюри). Возможны варианты.

Форматы

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

Во многих случаях исходный код программы может быть написан на одном из множества языков, в таком случае имя файла, например, source/validate.* означает, что имя файла начинается на source/validate., а дальше идёт суффикс, который принято использовать в именах файлов на каком-либо языке программирования.

problem.properties, используемый на NEERC и рядом

Описание составлено на основе p.py, доступной в архивах NEERC.

Директория считается задачей, если:

• в ней есть файл problem.properties
• или в ней есть поддиректория tests
• или в ней нашлась программа-генератор Tests.*

Параметры по умолчанию:

• ограничение по времени: две секунды
• ограничение по астрономическому времени: десять секунд (изменить невозможно)
• ограничение по пямяти: 512 мебибайт
• директория для тестов: tests
• техническое название задачи (далее <problem_id>): имя директории с задачей
• полное название задачи: «??»
• название задачи в контесте: первый символ <problem_id>, приведённый к верхнему регистру
• short-id: первый символ <problem_id>
• имя программы-генератора: Tests.* или doall.*
• имя программы-чекера: Check.* (изменить невозможно)
• имя программы-валидатора: Validate.* (изменить невозможно)
• имя программы-интерактора: Interact.* (изменить невозможно)
• имя входного файла: <problem_id>.in
• имя выходного файла: <problem_id>.out
• имя эталонного файла: <problem_id>.ans
• имя файла с логом: <problem_id>.log
• формат названия файлов с тестами: «##» (имена файлов с тестами состоят из двух цифр)
• эталонное решение: ищется по <problem_id>
• инициалы автора чекера: те же, что у автора тестов
• прочие инициалы: «??»

Параметры контеста:

• name-1 первая строка названия
• name-2 вторая строка названия
• location третья строка названия, как правило — место проведения
• date четвёртая строка названия, как правило — дата проведения
• timelimit ограничение по времени для решений
• memorylimit ограничение по памяти для решений
• problem-prefix префикс названий задач для PCMS2
• testsdir директория для тестов

Параметры задачи:

• id техническое название задачи
• name полное название задачи
• alias название задачи в контесте, как правило буква
• short-id
• source эталонное решение
• log
• testsdir имя директории для тестов
• tests формат файлов с тестами: «##» либо «###»
• timelimit ограничение по времени для решений
• memorytimit ограничение по памяти для решений
• input имя входного файла, «*» означает стандартный ввод
• output имя выходного файла, «*» означает стандартный вывод
• answer имя эталонного файла, «*» означает стандартный ???
• solution инициалы автора эталонного решения
• testset инициалы автора тестов
• checker инициалы автора программы-чекера

Формат .properties-файла:

• текстовый файл
• строки, начинающиеся с «#» игнорируются
• пустые строки, а также строки только из пробельных символов игнорируются
• строки должны иметь вид «<key>=<value>», возможно с пробельными символами вокруг ключа и значения.

Порядок поиска решения:

• <solution>.*
• <problem_id>_<solution>.*

Порядок сборки задачи:

• если нашёлся Tests.*, то это генератор и его надо запустить, предварительно создав директорию для тестов
• иначе если в диретории для тестов нашёлся doall.*, го это генератор и его надо запустить (из директории для тестов)
• иначе тесты генерируются по одному из файлов do<тест>.* (предполагается, что генератор теста выводит тест в stdout) в директории для тестов, при этом часть тестоы может быть без генератора.
• после генерации тестов к ним генерируются ответы, для этого запускается эталонное решение

Дополнительно в файле tests.sha256 хранятся sha256-хеши тестов. По умолчанию при сборке задачи следует проверять по этому файлу, что тесты получились ровно такие, как указано, но утилита (p.py или другая, которая предполагает работу с задачами в этом формате) в специальном режиме перезаписывает хеши тестов.

Возможности формата, которые были замечены ранее, но сейчас, похоже, не поддерживаются:

• чекер мог называться «check.*», а не только «Check.*»

Чекеры и валидаторы на java предполагают использование testlib4j, на c++ — testlib.

tools.sh Ивана Казменко

Описание составлено по архивам Чемпионатов СПбГУ.

В задаче есть директория с исходниками src, а также файл src/problem.sh. Технически src/problem.sh — скрипт на bash, но он не делает никаких активных действий, зато проставляует параметры задачи:

• IO_FILES используется ли файловый ввод/вывод в решениях
• USE_GRADERS используются ли грейдеры
• PROBLEM техническое название задачи
• AUTHOR инициалы (токен) автора задачи, часто используется для построения SOLUTION
• SUFFIX дополнетельный токен, используется для построения SOLUTION
• LANGUAGE язык (суффикс имени файла), используется для построения SOLUTION
• SOLUTION модельное решение (часто имеет вид «../solutions/$PROBLEM\_$AUTHOR$SUFFIX.$LANGUAGE»)
• GENERATOR генератор тестов: генерирует тесты (но не ответы к ним) прямо в директории src
• VALIDATOR валидатор
• CHECKER чекер
• TEST_PATTERN шаблон имён файлов тестов (как правило «[0-9][0-9]» или «[0-9][0-9][0-9]»)
• DO_CHECK надо ли проверять ответы при сборке задачи
• DO_CLEAN надо ли удалить временные файлы после сборки задачи
• CUSTOM_WIPE скрипт для удаления сгенерированных файлов

Прочие особенности:

• пути в src/problem.sh указываются относительно src
• решения как правило лежат в директории solutions

Также в src есть вспомогательные файлы и скрипты:

• скрипт src/doall.sh генерирует и проверяет тесты, кладёт их в tests
• скрипты src/clean.sh и src/wipe.sh удаляет временные и сгенерированные файлы
• скриптом src/testsol.sh можно проверить решение на всех тестах
• файл source/tools.sh — не самостоятельный скрипт, но библиотека для всех вышеуказанных

makefile Павла Кунявского

Описание составлено по архивам Чемпионатов СПбГУ.

В задаче есть файл makefile. Он как правило небольшой, содержит параметры задачи и подключения чего-нибудь вроде makefile.main (большой файл, замена скриптам и утилитам). В результате в задаче можно использовать утилиту make (GNU Make), цель по-умолчанию — сборка тестов, есть и другие полезные. Например, make clean удаляет сгенерированные файлы, а make problemInfo выводит параметры задачи, в том числе вычисленные по умолчанию.

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

Особенности утилиты

Директория считается директорией с задачей, если выполнено хотя бы одно из следующих условий:

• в директории есть файл problem.properties
• в директории есть файл problem.xml и это конфиг задачи из Полигона
• в директории есть хотя бы одна из следующих поддиректорий: tests, source, src

Директория с исходниками для задачи (далее <source-directory>) ищется следующим образом (в указанном порядке):

• если есть поддиректория source, то это она
• если есть поддиректория src, то это она
• если есть поддиректория tests, то это она
• иначе это директория с задачей

Генератор ищется следующим образом:

• если нашёлся <source-directory>/doall.*, то это он
• иначе используется генерация по тестам

Предполагается, что генератор следует запускать прямо из <source-directory>, он создаст директорию для тестов, запишет туда тесты и, возможно, эталонные ответы к ним. Директория для тестов всегда test (далее <tests-directory>)

Валидатор ищется следующим образом:

• если нашёлся <source-directory>/validate.*, то это он

Генерация по тестам работает следующим образом:

• имя теста может быть двуми или тремя цифрами, далее <test>
• если есть файл <source-directory>/<test>.manual, то он считается тестом и копируется в <tests-directory>/<test>
• если есть файл <source-directory>/<test>.hand, то он считается тестом и копируется в <tests-directory>/<test>
• если нашёлся файл <source-directory>/do<test>.*, то он считается генератором теста

Если генератор делает тесты, но не эталонные ответы (или не все), то недостающие ответы генерируются при помощи эталонного решения, которое должно быть указано в конфигурации. Ответ для теста <tests-directory>/<test> должен лежать в файле <tests-directory>/<test>.a.

Чекер ищется следующим образом (заметьте, что в директории задачи, а не в <source-driectory>):

• если нашёлся check.*, то это он
• если нашёлся checker.*, то это он
• если нашёлся check_<problem-id>.*, то это он
• если нашёлся Check.*, то это он

Команды

t.py build — основное действие с задачей: сгенерировать тесты и эталонные ответы к ним, проверить корректность (тесты должны проходить валидацию, авторское решение должно работать верно). Если генератор не генерирует ответ хотя бы на один тест, а авторское решение не указано, то сборка задачи завершится неудачно.

t.py check [<solutions>…] — проверить на всех тестах указанные решения (по умолчанию проверяется эталонное). В качестве решения можно указывать его имя (относительно директории с задачей), допускается указывать без суффикса, а также указывать токен, тогда в качестве решения будет использован файл source/<problem_id>_<токен>.*.

t.py clean — удаляет (если повезёт, то) все сгенерированные файлы: тесты, логи, скомпилированные программы, временные файлы. Если есть отдельная директория с исходниками, также удаляет директорию с тестами. Используйте эту команду на свой страх и риск (также рекомендуется закоммитить все файлы в репозиторий, если есть такая возможность), потому что для выбора файлов, которые будут удалены, она использует различные эвристики, и может иногда не угадывать (в обе стороны).

Опции

--recursive (-r) — искать задачи рекурсивно в поддиректориях и работать с каждой из них. В директории с задачей делать указанное действие, в остальных рекурсивно вызываться из поддиректорий.

--keep-going (-k) — при проверке решение запускать на всех тестах, а не до первого неудачного.

--keep-tests (-t) — при очистке (clean) удаляет только временные файлы, не тесты. Обратите внимание, что, как правило, этого не достаточно для работы с задачей в тестирующей системе — ей нужен ещё и чекер, причём скомпилированный, причём под ту систему, которая используется для запуска, а не под ту, под которой работает разработчик задачи (и, соответственно, утилита t.py). Например, ejduge работает под linux (зато сам собирает чекеры), а testsys — под виндой, и сам собирать не умеет.

TODO

• вернуть генерацию по тестам (кажется, после очередного рефакторинга она не выжила)
• пост-обработка тестов: если тест — текстовый файл, делать dos2unix/unix2dos или хотя бы проверять, всё ли в порядке (по идее должно быть, если используются генераторы и хорошо настроены vcs)
• build.log, check.log
• указывать явно список тестов для работы
• архивация, экспорт
• ограничения по времени для компиляторов, генераторов, чекеров и прочего
• переопределять опции при запуске: чекер вроде уже можно, надо ещё эталонное решение, лимиты, имена файлов
• при компиляции переопределять target_name (непонятно, где это нужно снаружи, но может пригодиться для работы под виндой)
• проверять при поиске файлов (если ещё нет) что случайно не попалась директория
• удалять временные файлы сразу после запуска решения на тесте
• проверять ответ сразу при генерации эталонных