Генераторы на testlib.h

Revision ru11, by MikeMirzayanov, 2015-06-03 02:48:03

Генераторы — это такие вспомогательные программы в задаче по программированию, которые выводят тесты. Далеко не всегда ручные тесты в задаче достаточно маленькие, чтобы обойтись только ими. В этом случае на помощь и приходят генераторы.

Виды генераторов

Есть два вида генераторов: обычные и мультигенераторы.

  1. Первые за один свой запуск выводят ровно один тест. Обычно, чтобы сгенерировать несколько тестов, такой генератор надо запустить несколько раз с разными параметрами командной строки. Такие генераторы выводят тест в стандартный вывод (на экран).
  2. Мультигенераторы за один запуск выводят сразу много тестов. Такие генераторы выводят тесты в файлы (один файл — один тест).

Пример просто обычного генератора на 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);
forn(i, n)
    if (i > 0)
        p[i] = rnd.wnext(i, t);

printf("%d\n", n);
vector<int> perm(n);
forn(i, n)
    perm[i] = i;
shuffle(perm.begin() + 1, perm.end());
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.begin(), edges.end());

for (int i = 0; i + 1 < n; i++)
    printf("%d %d\n", edges[i].first + 1, edges[i].second + 1);

На что еще обратить внимание?

  • Строго следуйте формату теста — пробелы, переводы строк должны быть идеально соблюдены. Тест должен заканчиваться переводом строки. Например, если в тест состоит из единственного числа, то выводите его как `cout << rnd.next(1, n) << endl;`` — с переводом строки в конце.
Tags testlib, генератор, генераторы, generator, generators, polygon, полигон

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English MikeMirzayanov 2022-05-19 13:20:41 72
en3 English dalex 2019-08-26 18:43:06 1 everybody can edit this post :) [small english fix]
en2 English adamant 2019-08-26 17:48:50 16422 translation
en1 English MikeMirzayanov 2015-06-10 03:08:08 6755 Initial revision for English translation
ru23 Russian elena 2015-06-08 11:57:40 61 мелкие правки (опечатки вида
ru22 Russian PavelKunyavskiy 2015-06-08 11:32:18 241 Undefined behavior fix
ru21 Russian adamant 2015-06-08 02:37:18 0 Возвращено к ru19
ru20 Russian adamant 2015-06-08 02:15:53 0 Так и задумано, что я могу без каких-либо препятствий редактировать любой текст в секции?
ru19 Russian MikeMirzayanov 2015-06-08 01:29:30 0 (опубликовано)
ru18 Russian MikeMirzayanov 2015-06-03 13:34:59 128
ru17 Russian MikeMirzayanov 2015-06-03 13:33:27 227
ru16 Russian MikeMirzayanov 2015-06-03 11:17:55 544
ru15 Russian MikeMirzayanov 2015-06-03 02:53:46 148
ru14 Russian MikeMirzayanov 2015-06-03 02:51:20 257
ru13 Russian MikeMirzayanov 2015-06-03 02:48:32 2 Мелкая правка: ') << endl;' &mdash; с' -> ') << endl;` &mdash; с'
ru12 Russian MikeMirzayanov 2015-06-03 02:48:17 3
ru11 Russian MikeMirzayanov 2015-06-03 02:48:03 324
ru10 Russian MikeMirzayanov 2015-06-03 02:46:04 9 Мелкая правка: 'а\n\nНиже код генер' -> 'а\n\nНиже основной код генер'
ru9 Russian MikeMirzayanov 2015-06-03 02:45:38 84
ru8 Russian MikeMirzayanov 2015-06-03 02:45:11 1046
ru7 Russian MikeMirzayanov 2015-06-03 02:40:57 156
ru6 Russian MikeMirzayanov 2015-06-03 02:38:56 157
ru5 Russian MikeMirzayanov 2015-06-03 02:35:55 438
ru4 Russian MikeMirzayanov 2015-06-03 02:25:26 1 Мелкая правка: '.next("one|two|three' -> '.next("one\|two|three'
ru3 Russian MikeMirzayanov 2015-06-03 02:25:11 1 Мелкая правка: '.next("one|two|three' -> '.next("one\|two|three'
ru2 Russian MikeMirzayanov 2015-06-03 02:24:56 631
ru1 Russian MikeMirzayanov 2015-06-03 02:16:23 2499 Первая редакция