Если вы используете C++, пожалуйста, выберите в качестве компилятора при отправке решения: C++14 (GCC 6-32) или C++17 (GCC 7-32). ×

Автор MikeMirzayanov, история, 9 лет назад, По-русски

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

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

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

  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) << " ";
    cout << 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);).
  • Необходимо не забывать о различных случаях неопределенного поведения языка C++. Например, в приведенном выше примере генератора нельзя объединять две команды cout в одну, т.к. тогда порядок вызовов функций rnd.next не определен.

Еще примеры

Примеры генераторов можно найти в дистрибутиве или непосредственно в репозитории.

  • Проголосовать: нравится
  • +79
  • Проголосовать: не нравится

»
9 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

thanks a lot, but this post is in Russian not English!

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

При использовании rand() или классов C++11 вроде mt19937/uniform_int_distribution ваша программа будет выводить разные тесты после компиляции разными компиляторами.

Последнее не верно. Поведение mt19937 и прочих рандомов c++11 полностью стандартизировано.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Генератора — стандартизировано, а вот преобразования — нет, как минимум, по факту.

    Например, вот такой вот код у меня выводит разное второе число вот на этом сайте:

    #include <random>
    #include <iostream>
    
    using namespace std;
    
    int main() {
      mt19937 gen;
      uniform_int_distribution<int> dist(0, 239017);
      cout << gen() << "\n";
      cout << dist(gen) << "\n";
      return 0;
    }
    

    Под GCC:

    3499211612
    32381
    

    Под Visual Studio 2015:

    3499211612
    99490
    

    Под Clang:

    3499211612
    171766
    
»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

del

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

не могу загрузить/отредактировать даже генератор, который ничего не делает, выдаёт ошибку cc1plus.exe: out of memory allocating X bytes, где X как минимум 65536.

»
5 лет назад, # |
  Проголосовать: нравится +37 Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by adamant (previous revision, new revision, compare).

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by dalex (previous revision, new revision, compare).

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The link to problems with rand() seems to be broken. If you could fix it, that would be very much appreciated.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can you please update this blog with the new command line parsing? It can be confusing for polygon users who haven't seen the new blog.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

генератор должен выводить один и тот же тест при компиляции любым компилятором на любой платформе, если он запущен одинаковым способом

Не могу понять, что происходит, но у меня это не выполняется. Запускаю следующий код у себя на компьютере и в полигоне:

Генератор

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

Если на моем компьютере запускать с командой ./gen 10 10 10, то получается следующий вывод:

Тест

А если в полигоне командой gen 10 10 10 > $, то получается следующее:

Тест

Как видно, тесты разные. На самом деле эта проблема встречалась у меня и раньше, но в этом случае я могу свободно выкладывать генератор в общий доступ. Тогда мы перестали использовать функцию rnd.any(), и тесты начали генерироваться одинаково, так что я подозреваю, что проблема в ней.

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The two Further examples links are broken