Generator

Generator, that is, a data generator. When the data is so large that manually creating it would be exhausting, we need it to help us generate the data automatically.

A Simple Example

Generate two integers in the range $[1,n]$:

// clang-format off

#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;
}

Why Use Testlib?

Some people say that generators do not need Testlib and that it is of no use here. This is actually incorrect. A good generator should satisfy the following condition: for the same input, it produces the same output in any environment. Writing a generator inevitably involves generating random values. The output of rand() or C++11's mt19937/uniform_int_distribution, which we usually use, may differ when the operating system differs, when compiled with different compilers, or when run at different times (this is obvious for the very common srand(time(nullptr))), and this introduces uncertainty into data generation.

Note that once Testlib is used, standard-library random-number functions such as srand() and rand() can no longer be used, or a compilation error will occur. Therefore, make sure that all random-related functions use Testlib rather than those provided by the standard library.

The random-value generation functions in Testlib guarantee that the same calls produce the same values, independently of the generator itself or the platform. In addition, they make it very convenient to generate random values meeting various requirements. For example, rnd.next("[a-z]{1,10}") generates a string with length in $[1,10]$, where each character is from a to z; convenient, right?

What Can Testlib Do?

Before anything else, execute registerGen(argc, argv, 1) to initialize Testlib (where 1 is the generator version and normally remains unchanged). We can then use the rnd object to generate random values. The random seed is taken from the hash of the command-line arguments. For a generator g.cpp, g 100 (Unix-like) and g.exe "100" (Windows) produce the same output, while g 100 0 produces a different output.

The type of the rnd object is random_t. You can create a new random-value generation object, but normally you do not need to do so.

This object has many useful member functions; the following are some examples:

For reference, the formal definition of rnd.wnext(i,t) is:

$$\operatorname{wnext}(i,t)= \begin{cases} \operatorname{next}(i) & t=0 \\ \max(\operatorname{next}(i),\operatorname{wnext}(i,t-1)) & t>0 \\ \min(\operatorname{next}(i),\operatorname{wnext}(i,t+1)) & t<0 \end{cases}$$

In addition, do not use std::random_shuffle(); use Testlib's shuffle(), which also accepts a pair of iterators. It uses rnd to shuffle the sequence, thus satisfying the requirements of a “good generator” described above.

Example: Generating a Tree

The following is the main code for generating a tree. It accepts two parameters—the number of vertices and the stretch. For example, when $n=10,t=1000$, it may generate a chain; when $n=10,t=-1000$, it may generate a star.

#define forn(i, n) for (int i = 0; i < int(n); i++)

registerGen(argc, argv, 1);

int n = atoi(argv[1]);
int t = atoi(argv[2]);

vector<int> p(n);

/* Set parents for nodes 1..n-1 */
forn(i, n) if (i > 0) p[i] = rnd.wnext(i, t);

printf("%d\n", n);

/* Shuffle nodes 1..n-1 */
vector<int> perm(n);
forn(i, n) perm[i] = i;
shuffle(perm.begin() + 1, perm.end());

/* Add edges according to the shuffled node order */
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 the 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);

Generating Multiple Test Cases at Once

As when writing without Testlib, simply redirect the output stream before each output. However, Testlib provides a helper function startTest(test_index), which redirects the output stream to the test_index file.

Some Precautions

• Strictly follow the format requirements of the problem, such as spaces and line breaks, and note that the file should end with a newline.
• For large data, prefer printf over cout to improve performance. (It is not recommended to disable stream synchronization when using Testlib.)
• Do not use UB (Undefined Behavior), such as in the example at the beginning of this article. If the output is written as cout << rnd.next(1, n) << " " << rnd.next(1, n) << endl;, the order of calls to rnd.next() is undefined.

New Feature: Parsing Command-Line Arguments

Previously, we usually used code such as int n = atoi(argv[3]);, but this is not good. There are several reasons:

• It is unsafe when the third command-line argument does not exist;
• The third command-line argument may not be a valid 32-bit integer.

Now, you can write int n = opt<int>(3). At the same time, you can also use int64_t m = opt<int64_t>(1);, bool t = opt<bool>(2);, and string s = opt(4);.

In addition, testlib also supports named arguments. If there are many arguments, g 10 20000 a true is less readable than g -n10 -m200000 -t=a -increment.

In this case, you can now use the following code in a generator:

int n = opt<int>("n");
long long n = opt<long long>("m");
string t = opt("t");
bool increment = opt<bool>("increment");

You can freely mix reading arguments by index and by name.

The following schemes are supported for writing named arguments:

• --key=value or -key=value;
• --key value or -key value—if value is not the beginning of a new argument (it does not begin with a hyphen -, or no letter follows one or two hyphens);
• --k12345 or -k12345—if the key k is a letter followed by a number;
• -prop or --prop—enable a bool property.

Here are some examples:

g1 -n1
g2 --len=4 --s=oops
g3 -inc -shuffle -n=5
g4 --length 5 --total 21 -ord

More Examples

They can be found on GitHub.

This article was mainly translated from Генераторы на testlib.h - Codeforces. The new features were translated from Testlib: Opts—parsing command line options. The GitHub repository for testlib.h is MikeMirzayanov/testlib.

Footnotes

1. In fact, when i is a floating-point number, rnd.wnext(i, t) follows the Beta distribution on $[0,i)$: when $t>0$, it follows $i\cdot \mathrm{Beta}(t+1,1)$; when $t<0$, it follows $i\cdot \mathrm{Beta}(1,t+1)$. ↩