Генераторы — это такие вспомогательные программы в задаче по программированию, которые выводят тесты. Далеко не всегда ручные тесты в задаче достаточно маленькие, чтобы обойтись только ими. В этом случае на помощь и приходят генераторы. Если вы пишите генератор на С++, то использование testlib.h — хороший выбор.
Виды генераторов
Есть два вида генераторов: обычные и мультигенераторы.
- Первые за один свой запуск выводят ровно один тест. Обычно, чтобы сгенерировать несколько тестов, такой генератор надо запустить несколько раз с разными параметрами командной строки. Такие генераторы выводят тест в стандартный вывод (на экран).
- Мультигенераторы за один запуск выводят сразу много тестов. Такие генераторы выводят тесты в файлы (один файл — один тест).
Пример просто обычного генератора на testlib.h
Выводит пару чисел от 1 до n, где n переданный параметр запуска генератора.
#include "testlib.h"
#include <iostream>
using namespace std;
int main(int argc, char* argv[])
{
registerGen(argc, argv, 1);
int n = atoi(argv[1]);
cout << rnd.next(1, n) << " " << rnd.next(1, n) << endl;
}
Зачем testlib.h?
При невнимательном взгляде кажется, что testlib.h почти не нужен для написания генератора. На самом деле это неправда. Почти в каждом генераторе нужна возможность получать случайные значений, и есть большое искушение использовать rand()
. Не делайте этого. Основной принцип написания генератора: генератор должен выводить один и тот же тест при компиляции любым компилятором на любой платформе, если он запущен одинаковым способом. При использовании rand()
или классов C++11 вроде mt19937/uniform_int_distribution
ваша программа будет выводить разные тесты после компиляции разными компиляторами.
Генератор случайных значений в testlib.h гарантирует, что будет сгенерировано одно и тоже независимо от генератора и платформы. Кроме того, в testlib.h есть разные удобности для генерации тестов, например, rnd.next("[a-z]{1,10}")
вернет случайное слово длины от 1 до 10 из букв от a
до z
.
Что есть у testlib.h?
Чтобы инициализировать testlib-генератор, первая его строка должна иметь вид registerGen(argc, argv, 1);
(где 1 — это версия используемого генератора случайных чисел). После этого можно будет пользоваться объектом rnd
, который будет проинициализирован хешем от всех аргументов командной строки. Таким образом, результат вывода g 100
и g.exe "100"
будет одинаков, а у g 100 0
будет отличаться.
Объект rnd
имеет тип random_t
, то есть вы можете создать и свой генератор, но обычно это не нужно.
У объекта rnd
есть много полезных членов-функций. Вот примеры:
Вызов | Что делает |
---|---|
rnd.next(4) | равновероятное целое случайное число от 0 до 3 включительно |
rnd.next(4, 100) | равновероятное целое случайное число от 4 до 100 включительно |
rnd.next(10.0) | равновероятное вещественное случайное число в полуинтервале [0,10) |
rnd.next("one|two|three") | равновероятное случайное одно слово из трех one, two и three |
rnd.next("[1-9][0-9]{99}") | равновероятное случайное 100-значное число в виде строки |
rnd.wnext(4,t) | wnext — это способ получения неравновероятного распределения (со смещенным матожиданием), параметр t обозначает количество вызовов операции "максимум" для аналогичных вызовов next, например rnd.wnext(3, 1) эквивалентен max(rnd.next(3), rnd.next(3)), а rnd.wnext(4, 2) эквивалентен max(rnd.next(4), max(rnd.next(4), rnd.next(4))). Если t < 0, то - t будет найден минимум. Если t = 0, то wnext эквивалентен next. |
rnd.any(container) | вернет случайный элемент контейнера container (с произвольным доступом по итератору), например, работает для std::vector и std::string |
Кроме того, не надо использовать std::random_shuffle
, используйте shuffle
из testlib. Он так же принимает два итератора, но работает, используя rnd
.
Пример: генерация неориентированного дерева
Ниже основной код генератора неориентированного дерева, который принимает два параметра — количество вершин и степень его вытянутости. Например, при n = 10, t = 1000 наверняка будет сгенерирована цепь, а при n = 10, t = - 1000 наверняка будет сгенерирована ромашка (звездочка).
registerGen(argc, argv, 1);
int n = atoi(argv[1]);
int t = atoi(argv[2]);
vector<int> p(n);
/* setup parents for vertices 1..n-1 */
forn(i, n)
if (i > 0)
p[i] = rnd.wnext(i, t);
printf("%d\n", n);
/* shuffle vertices 1..n-1 */
vector<int> perm(n);
forn(i, n)
perm[i] = i;
shuffle(perm.begin() + 1, perm.end());
/* put edges considering shuffled vertices */
vector<pair<int,int> > edges;
for (int i = 1; i < n; i++)
if (rnd.next(2))
edges.push_back(make_pair(perm[i], perm[p[i]]));
else
edges.push_back(make_pair(perm[p[i]], perm[i]));
/* shuffle edges */
shuffle(edges.begin(), edges.end());
for (int i = 0; i + 1 < n; i++)
printf("%d %d\n", edges[i].first + 1, edges[i].second + 1);
Как написать мультигенератор?
Мультигенератор за одно исполнение может вывести более одного теста. Тесты таким генератором выводятся с файлы. В генераторе на testlib.h достаточно перед выводом теста написать startTest(test_index)
. Это приведет к переоткрытию (freopen) потока стандартного вывода на файл с именем test_index
. Обратите внимание, что в системе Polygon в таком случае в скрипте надо писать что-то вроде multigen a b c > {4-10}
(если предполагается, что запуск мультигенератора вернет тесты 4, 5, 6, 7, 8, 9 и 10).
На что еще обратить внимание?
- Строго следуйте формату теста — пробелы, переводы строк должны быть идеально соблюдены. Тест должен заканчиваться переводом строки. Например, если в тест состоит из единственного числа, то выводите его как
cout << rnd.next(1, n) << endl;
— с переводом строки в конце. - Если выводимый тест может быть довольно большим, то предпочитайте
printf
(а неcout
) — это улучшит производительность. - Лучше выводите
long long
черезcout
, но если хотите printf, то используйте константу I64 (например,printf(I64, x);
).
Еще примеры
Примеры генераторов можно найти в дистрибутиве или непосредственно в репозитории.