Библиотека testlib.h

Здесь пойдет речь о библиотеке testlib.h, которая была написана мной достаточно давно — году в 2005-ом. Незадолго до этого было объявлено об отказе на финале ACM-ICPC от использования Pascal, популярность набирал TopCoder (где так же нет Pascal/Delphi). Все это приводило к мыслям, что писать чекеры на Pascal вечно невозможно, да и не всегда достаточно удобно, да и кроссплатформенным этот вариант назвать трудно — по-моему далеко не все testlib.pas (которых несколько разновидностей) компилируются free pascal.

Про чекеры

Так как не все читатели являются авторами задач, то давайте проясним смысл этого слова. Чекером называется программа, которая читает входной файл (тест), вывод проверяемой программы, предполагаемый ответ и выводит вердикт относительно корректности вывода проверяемой программы. Обычно, бывают следующие вердикты: OK (ответ верен, представлен один из правильных ответов), WA (ответ неверен), PE (формат вывода не верен, я этот вердикт не люблю), FL (произошел epic fail — например, чекер выяснил, что решение участника вывело более оптимальный ответ, чем авторское решение). Конечно, при тестировании подготовленных задач не должен появляться FL, но о нем мы расскажем чуть позже.

Конечно, в большинстве задач не требуется "интеллектуальный" чекер, так как условие задачи однозначно определяет вывод участника. Более того, на многих соревнованиях по техническим причинам (TopCoder) или в силу традиций (большое количество ACM-ICPC regionals) это стало правилом. С другой стороны, даже при однозначном выводе могут быть тонкости — на сколько позволять участникам не соблюдать формат. Возможны следующие моменты (и не только они):

• вывод перевода строки или его отсутствие в конце последней строки файла;
• вывод лишних пробелов, особенно в задачах со всякими "Case: 12" или завершающий пробел в конце последовательности чисел;
• вывод вещественных чисел — вообще, отдельная песня, так как надо определяться сколько нужно знаков (ровно столько? не меньше?), да и округлиться 0.34999999 может как угодно.

Все это приводит к заключению, что даже в задачах с однозначным выводом проверка вывода дело тонкое. Обычно, если в условии задачи не написано четко про пробелы, то следует допускать их произвольное расположение в выводе. Лояльность относительно заключительного перевода строки тоже, я думаю, правило хорошего тона. Так как в разных задачах оказывается, что требуется немного разное "точное" сравнение, то и в таких задачах применяют чекеры, просто их не пишут каждый раз, а используют готовые (написанные заранее).

Обычно, чекер компилируется в исполняемый файл, который принимает три (опционально два) аргумента командной строки: входной-файл, файл-вывода, файл-ответа. В англоязычной терминологии это input, output и answer. Возвращает значение чекер обычно через exit-codes выполняемого процесса. За исключением ejudge тестирующие системы обычно используют:

• код возврата 0 для обозначения OK;
• код возврата 1 для обозначения WA;
• код возврата 2 для обозначения PE;
• код возврата 3 для обозначения FL.

Что очень важно хороший чекер выведет в stdout вердикт и его причину в виде короткой фразы на английском языке (иногда для русскоязычных школьных соревнований используется русский язык). Стоит помнить, что вывод должен быть информативен и не очень громоздким. Примеры хороших выводов: "ok n=10, m=13, answer=34", "ok No solution", "wrong answer Expected -1, found 4294967295". Примеры плохих выводов "ok OK", "wrong answer Palevo!".

Чекеры и testlib.h

Писать чекеры — с одной стороны просто, с другой стороны в этом много подводных камней. Что может быть проще написать программу для сравнивания двух целых чисел? Однако вдруг оказывается, что scanf("%d", &a) (да и многие другие стандартные способы считать целое число во многих языках) при считывании 4294967295 не просигнализирует об ошибке, и будет уверен, что прочел -1. Отделить PE и WA при чтении целого числа тоже отдельная задачка.

По этой причине еще в лохматые 90-е Антоном Сухановым и Романом Елизаровым на был написан testlib для Pascal, который верой и правдой служил на многих NEERC и в модифицированном виде активно используется до сих пор. Иногда возникают проблемы обратной несовместимости версий этой библиотеки или около того (модуль symbols). Заметим, что эта библиотека была переписана Андреем Лопатиным и Николаем Дуровым и другой вариант активно используется на многих контестах СпбГУ и по сей день. На сколько я понимаю, библиотеки эти не совсем совместимы.

Библиотека testlib.h была написана мной в 2005-м году по образу и подобию тестлибов для Pascal. Это позволило упростить переход на нее тем многим, кто уже успел поработать с testlib.pas. Достаточно быстро testlib.h стал использоваться не только на саратовских соревнованиях. Одним из первых широкомасштабных использований стала Всероссийская олимпиада школьников года примерно 2006-го. С тех пор, testlib.h стал де-факто стандартом для написания чекеров на С++ и применяется на совсем разных контестах.

Приведем пример простейшего чекера на testlib.h, который сравнивает answer и output, ожидая в каждом из них по одному 32-х битному целому числу.

#include "testlib.h"

int main(int argc, char * argv[])
{
   setName("compare two signed int32 numbers");
   registerTestlibCmd(argc, argv);

   int ja = ans.readInt();
   int pa = ouf.readInt();

   if (ja != pa)
       quitf(_wa, "expected %d, found %d", ja, pa);

   quitf(_ok, "answer is %d", ja);
}

Я думаю код достаточно понятен. Отмечу, что программе доступны три потока inf, ouf, ans — потоки входных, выходных данных и поток с ответом. Для потоков есть удобные функции чтения, которые позволяют читать разнообразные данные. Ошибки чтения трактуются по разному для разных потоков. Например, если невозможно прочитать число с помощью ouf.readInt(), то будет PE, но если использовался inf.readInt() или ans.readInt() то будет FL. Об этом не надо особенно задумываться при разработке — здесь все вполне логично и естественно. Еще немного примеров (подразумевается чтение из ouf, для inf и ans в случае ошибок будут FL).

• readInt(1, 100, "n") — попытается прочесть целое от 1 до 100, вернет WA (для версий 0.7+, иначе PE) если число не в заданных границах. Текст вывода будет примерно таким: Integer n violates the range [1, 100].
• readInt(1, 100) — тоже самое, но вывод об ошибке немного другой (без указания имени переменной).
• readLong() — читает знаковое 64-х битное число.
• readToken() — читает очередной токен (последовательность непробельных символов), пропускает если надо все whitespaces перед чтением токена.
• readWord() — тоже самое, что и readToken().
• readWord("[a-z]{1,100}") — читает токен и удостоверяется, что это последовательность малых латинских букв длины от 1 до 100, вернет WA (для версий 0.7+, иначе PE) если токен не соответствует паттерну.
• seekEof() — пропускает все whitespaces и возвращает true если больше ничего нет в потоке.
• readLine() — читает текущую строку до конца.

Это далеко не все возможности, следует посмотреть testlib.h (строки около 950) чтобы ознакомиться со списком всех возможностей.

Задачи с сертификатом, чекеры

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

    n = inf.readInt();

    int ja = readAnswer(ans, _fail, _fail);
    int pa = readAnswer(ouf, _wa, _pe);

    if (ja < pa)
        quitf(_wa, "Jury has better answer: %d < %d", ja, pa);

    if (ja > pa)
        quitf(_fail, "Participant has better answer: %d < %d", pa, ja);

    quitf(_ok, "n=%d, m=%d, result=%d", n, m, ja);

Здесь функция readAnswer читает ответ (вывод) из заданного потока, удостоверяется в его корректности и возвращает значение целевой функции оптимизации. Второй и третий параметры функции нужны для того, чтобы использовать их в функции quitf(), это обеспечит FL на ошибках потока ответа и WA/PE на ошибках потока вывода.

Как написать чекер

Приведу список шагов по написанию чекера.

1. Если у вас нет неоднозначности в выводе в задаче, то используйте один из стандартных чекеров. Не бойтесь быть слишком лояльными — пусть лучше ваш чекер игнорирует какие-нибудь лишние пробелы, чем будет слишком строг и испортит участникам контест.
2. Если в задаче предполагается вывод сертификата, то пишите чекер в соответствии с паттерном в предыдущем разделе. Всегда стоит рассмотреть возможность изменения задачи, чтобы она требовала вывод сертификата. Обычно это делает задачу чуть более программистской, что неплохо.
3. Когда пишите чекер, то учтите, что он будет компилироваться на произвольной платформе. В частности, не используйте %I64d/%lld. В testlib.h есть функция vtos(value), которая возвращает строковое представление аргумента value.
4. Старайтесь писать максимально надежно. Есть вероятность переполнения — пишите все в long long, и так далее.
5. Старайтесь писать все просто и прямо. Не используйте хитрый и неочевидный код.
6. Перепрочтите условие задачи и обратите внимание на то, что вы проверяете все требования, изложенные в задаче.
7. Будьте аккуратны с WA/PE. Например, если в задаче требуют вывести число или "No solution", то вывод "No solution", не должен приводить к PE.
8. Убедиться, что при любом выводе участника чекер не выведет сверхдлинный комментарий. Например, выводя строки их лучше оборачивать в __testlib_part(s). Стандартные чекеры делают именно так, можно почитать их код для уточнения деталей.
9. Тщательно потестируйте ваш чекер на предмет его адекватной работы в каждом из возможных вариантов исхода.

Пожалуй все. Пишите в комментариях замечания и предложения. Наверняка, я что-то забыл/упустил.
MikeMirzayanov

P.S. Немного ссылок:

1. Официальный сайт testlib.h
2. Issue (bug) tracker для testlib.h
3. testlib.pas by SPb IFMO CTD Development Team