tcframe Documentation¶
Note
tcframe 1.x has been released! Check out 1.0.0 release notes for migration guide from 0.x.
Welcome to the official documentation of tcframe, a competitive programming test cases generator framework! This documentation is organized into several sections:
Introduction¶
General information of tcframe project. Contains some code examples. Start here to grasp general understanding of this framework.
Getting Started¶
After getting the high-level concept of the framework, why not actually start writing a test cases generator? This section will guide you to install and write your very first generator.
Topic Guides¶
Now that you got your hand wet with your first generator, master each of tcframe‘s key concepts in more details here.
Tutorials¶
Tutorials, case studies, and best practices in writing generators for real competitive programming problems.
API Reference¶
Finally, this is an API documentation of all tcframe features that you will be looking up often when writing your generator.
Introduction¶
tcframe is a C++ framework for generating test cases of competitive programming problems. This framework helps problem writers prepare test cases in a structured manner and ensures that the generated test cases are valid according to the specified constraints.
At a very high level, with some details omitted, it works as follows:
You specify input/output variables.
int A, B; int sum;
You specify input/output formats.
void InputFormat() { LINE(A, B); // A line containing space-separated A and B } void OutputFormat() { LINE(sum); }
You specify the grading configuration.
void GradingConfig() { TimeLimit(2); MemoryLimit(64); }
You specify the constraints.
void Constraints() { CONS(1 <= A && A <= 1000); CONS(1 <= B && B <= 1000); }
You specify the sample test cases.
void SampleTestCase1() { Input({ "2 8" }); Output({ "10" }); } void SampleTestCase2() { Input({ "42 100" }); Output({ "142" }); }
You specify the official test cases. Random number generator is available.
void TestCases() { CASE(A = 1, B = 1); CASE(A = 77, B = 99); CASE(A = rnd.nextInt(1, 1000), B = rnd.nextInt(1, 1000)); }
You write the official solution to this problem, using any programming language you wish. Of course, it is the infamous A+B problem.
#include <iostream> using namespace std; int main() { int A, B; cin >> A >> B; cout << (A + B) << endl; }
You run the generator. Actual test cases (
.in
and.out
files) will be generated. Profit!If you ever specified an invalid test case, such as
CASE(A = 0, B = 1)
, you will get a nice error message:sum_4: FAILED Description: A = 0, B = 1 Reasons: * Does not satisfy constraints, on: - 1 <= A && A <= 1000
Features¶
tcframe supports:
- Standard batch problems; i.e., problems which requires the solution to read from stdin and print to stdout.
- Constraints specified in IOI-style subtasks.
- ICPC-style multiple test cases per file.
- Simple local grading of solutions against generated test cases.
- Specifying time and memory limits.
- Basic random number generation helper.
Requirements¶
tcframe requires:
- Linux/OS X. Windows is currently not supported yet
- GCC ≥ 4.8. tcframe relies heavily on C++11 features
Motivations¶
Why do we even need to write a generator for test cases, in the first place?
- That’s primarily because writing test cases manually is error-prone and time-consuming.
- To enable distributing the test cases as a single, small generator file. No need to send 20 MB
testcases.zip
over email anymore. - During problem development, constraints often change. Using a generator, we can easily fix the constraint and just run the generator again.
OK. But why do we need a framework for that?
- The main problem is that not all people know how to write a good test cases generator.
- To avoid writing repetitive and boring tasks. For example: creating test case files with correct suffixes (
foo_1.in
,foo_1.out
), running official solution against the test case input files, etc. - To make all problems in a contest have test cases generator with consistent format.
Credits¶
tcframe is based on a paper submitted to IOI conference in 2015: Introducing tcframe: A Simple and Robust Test Cases Generation Framework, written by Ashar Fuadi.
tcframe was mainly inspired from testlib, written by Mike Mirzayanov et al.
Getting Started¶
In tcframe world, a problem is defined by a problem package, which consists of a spec file and one or more solution files. The spec file is then compiled into a runner program. The runner program together with the compiled solution files can then generate test cases for the problem.
Let’s write our first problem package! We are going to write a package for the following infamous “A+B” problem:
4 6
10
Note
This starter guide will just demonstrate the basic features of tcframe. For more advanced features, please consult the Topic Guides afterwards.
Installation¶
Firstly, we must get tcframe on our system. It consists of C++ header files and a few helper scripts.
Download the latest tcframe here. Extract the zip file somewhere on your system; for example, ~/tcframe
. We will call this directory “tcframe home”. Confirm that you extracted it correctly by verifying that the directory include
exists directly inside tcframe home.
Then, add the following lines to your ~/.bashrc
. This will set the environment variable TCFRAME_HOME
to our tcframe home directory, and make tcframe
command available everywhere.
export TCFRAME_HOME=~/tcframe
alias tcframe=$TCFRAME_HOME/scripts/tcframe
Restart your terminal session. Now, if you run
tcframe version
You should see the following output
usage: tcframe <command>
Available commands:
build Compile spec file into runner program
version Print tcframe version
You’re good to go!
Preparing package directory¶
Create a directory called sum
somewhere. This will be our package directory for this A+B problem. Store all the files you will be creating on this guide in this directory.
Writing solution file¶
In order to be able to generate the test case output files, a reference solution must be available. For the purpose of this guide, call the solution file solution.cpp
. Example solution:
#include <iostream>
using namespace std;
int main() {
int A, B;
cin >> A >> B;
cout << (A + B) << endl;
}
Then, compile it to solution
executable, for example:
g++ -o solution solution.cpp
Writing spec file¶
A spec file contains problem spec and test spec.
Create a C++ source file called spec.cpp
. Copy-paste the following code to the file:
#include <tcframe/spec.hpp>
using namespace tcframe;
class ProblemSpec : public BaseProblemSpec {
protected:
int A, B;
int sum;
void InputFormat() {
LINE(A, B);
}
void OutputFormat() {
LINE(sum);
}
void GradingConfig() {
TimeLimit(1);
MemoryLimit(64);
}
void Constraints() {
CONS(1 <= A && A <= 1000);
CONS(1 <= B && B <= 1000);
}
};
class TestSpec : public BaseTestSpec<ProblemSpec> {
protected:
void SampleTestCase1() {
Input({
"4 6"
});
Output({
"10"
});
}
void TestCases() {
CASE(A = 1, B = 1);
CASE(A = 1000, B = 1000);
CASE(A = 42, B = 100);
CASE(A = rnd.nextInt(1, 1000), B = rnd.nextInt(1, 1000));
}
};
We will explain this spec file in more details later – keep going!
Building runner program¶
Next, we will compile this spec file into what we call a runner program. We will use the tcframe
command. Simply run this in the sum
directory:
tcframe build
This will compile spec.cpp
into runner
. Make sure that it compiles before continuing this getting started guide!
Finally, run the runner program:
./runner
If everything is OK, you should get the following output:
Generating test cases...
[ SAMPLE TEST CASES ]
sum_sample_1: OK
[ OFFICIAL TEST CASES ]
sum_1: OK
sum_2: OK
sum_3: OK
sum_4: OK
Generation finished. All test cases OK.
Congratulations, you have just written your first problem package using tcframe framework! Now, check out your sum/tc
directory – it will contain the generated test case files.
Inspecting problem package¶
We will now examine each component of a problem package in more details.
Slug¶
A slug is a unique name/codename/identifier for the problem. It is taken from name of the problem package directory. Since we call our problem package directory sum
, the slug of our example problem is sum
.
Spec file¶
A spec file is a C++ source file called spec.cpp
that lives inside the problem package directory.
tcframe header¶
#include <tcframe/spec.hpp>
using namespace tcframe;
tcframe/spec.hpp
is the main tcframe‘s header file for spec files. Each component of tcframe lives in the tcframe
namespace, just like the STL functions that live in the std
namespace. By importing the namespace, we don’t have to explicitly prefix each class/object we want to use with tcframe::
.
Problem spec class¶
class ProblemSpec : public BaseProblemSpec {
protected:
...
};
A problem spec class is where we define the I/O formats, constraints, and some configurations of our problem. This class must inherit tcframe::BaseProblemSpec
, and must be called ProblemSpec
.
All required members of this class must go in the protected section.
Grading configuration¶
void GradingConfig() {
TimeLimit(1);
MemoryLimit(64);
}
Quite self-explanatory. This has actually no effect during test cases generation, and will affect local grading as explained in later section of this guide. If not specified, the default time limit is 2 seconds, and the default memory limit is 64 megabytes.
Input/output variables and formats¶
int A, B;
int sum;
void InputFormat() {
LINE(A, B);
}
void OutputFormat() {
LINE(sum);
}
Next, we defined the input and output variables and formats. The input consists of two values: A and B. The output consists of one value; let’s call it sum. We must declare a variable for each of those values, and then tell tcframe how to format them in the input/output files.
Here, we declared two integers A
and B
as input variables, and an integer sum
as an output variable. InputFormat()
and OutputFormat()
methods specify the input/output formats in terms of the input/output variables. The LINE()
macro here specifies a line consisting of space-separated values of the given arguments.
Constraints¶
void Constraints() {
CONS(1 <= A && A <= 1000);
CONS(1 <= B && B <= 1000);
}
The last part of a problem spec is constraints specification.
A constraint must depend on input variables only. Each constraint can be specified as a boolean predicate inside the CONS()
macro.
Here, we have two constraints, which are just direct translations of what we have in the problem statement.
We now have a formal specification of our A+B problem. The next part is writing a test spec that specifies test cases which conform to the problem spec.
Test spec class¶
class TestSpec : public BaseTestSpec<ProblemSpec> {
protected:
...
};
A test spec is a class that inherits tcframe::BaseTestSpec<T>
, where T
is the problem spec class. It must be called TestSpec
.
This is where we actually write the test case definitions.
Test case definitions¶
void SampleTestCase1() {
Input({
"4 6"
});
Output({
"10"
});
}
void TestCases() {
CASE(A = 1, B = 1);
CASE(A = 1000, B = 1000);
CASE(A = 42, B = 100);
CASE(A = rnd.nextInt(1, 1000), B = rnd.nextInt(1, 1000));
}
Here, we finally defined the test cases (yeay!). For the purpose of this guide, we defined four test cases: 3 hand-made and 1 randomized. We also defined one sample test case that match with the one in the actual problem statement.
In tcframe, sample test cases, if any, are defined in the SampleTestCaseX()
methods, where X
is the sample test case number. Each sample test case is defined as line-by-line verbatim strings in the Input()
and Output()
methods. Sample test cases must conform to the input format, or tcframe will complain.
Test cases are defined in the TestCases()
method. Each test case is defined by listing input variable assignments the CASE()
macro, separated by commas. Here, we just defined a min case, max case, random hand-made case, and a randomized case. The last one is achieved using tcframe::rnd
, a simple random number generator provided by tcframe.
Note
Yes, you can access the input variables directly inside the test spec, even though they are declared in the problem spec class!
We’ve covered each component of our problem package in more details. Next, let’s play around with our runner program.
Trying out invalid test cases¶
What happens when we specify invalid test cases? Let’s just try. Add this test case to our test spec:
CASE(A = 0, B = 1);
and this sample test case:
void SampleTestCase2() {
Input({
"1",
"2"
});
Output({
"3"
});
}
Recompile (by running tcframe build
) and rerun the runner program. You should now get the following output instead:
Generating test cases...
[ SAMPLE TEST CASES ]
sum_sample_1: OK
sum_sample_2: FAILED
Reasons:
* Expected: <space> after variable `A`
[ OFFICIAL TEST CASES ]
sum_1: OK
sum_2: OK
sum_3: OK
sum_4: OK
sum_5: FAILED
Description: A = 0, B = 1
Reasons:
* Does not satisfy constraints, on:
- 1 <= A && A <= 1000
Generation finished. Some test cases FAILED.
Sweet! If we ever have invalid test cases, tcframe will tell us in human-readable message.
Remove the invalid test cases and move on to the next section.
Local grading¶
When preparing a problem, it’s ideal if we have at least another solution as an alternative/secondary solution. tcframe lets you “grade” another solution using the main solution as the reference. The time and memory limits from GradingConfig() as explained previously will be taken into consideration.
First, fix our spec file and re-run it to get back the correct test cases (important!). Then, write an alternate solution that deliberately behaves incorrectly on some test cases. Write the following as solution_alt.cpp
:
#include <iostream>
using namespace std;
int main() {
int A, B;
cin >> A >> B;
if (A == 1) {
cout << 3 << endl;
} else if (A == 1000) {
while (true);
} else if (A == 42) {
return 1 / 0;
} else {
cout << (A + B) << endl;
}
}
Compile the solution into solution_alt
executable, and then run the following command:
./runner grade --solution=./solution_alt
The above command tells tcframe to run the specified alternate solution command against the output files previously produced by the main solution.
You should get the following output:
Grading...
[ SAMPLE TEST CASES ]
sum_sample_1: Accepted
[ OFFICIAL TEST CASES ]
sum_1: Wrong Answer
* Diff:
(expected) [line 01] 2
(received) [line 01] 3
sum_2: Time Limit Exceeded
sum_3: Runtime Error
* Execution of submission failed:
- Floating point exception: 8
sum_4: Accepted
[ RESULT ]
Time Limit Exceeded
We get a detailed verdict of each test case. Nice, isn’t it? The final result here is Time Limit Exceeded, which is the “worst” verdict among all test case verdicts.
We’ve covered the basics of tcframe. At this point, continue reading Topic Guides for more in-depth explanation of tcframe features.
Topic Guides¶
In this guide, we will learn each aspect of tcframe more thoroughly. Each section may have notes at the end, explaining the current limitations and future plans of the corresponding aspect.
Problem package¶
A problem package is the unit of work in tcframe that defines a problem and its test data. It is a directory that consists of all files related to the problem, particularly a spec file and one or more solution files. It is identified by a unique name called slug.
Slug¶
A slug can be considered as the codename of a problem. For example, if your problem name is “Counting Tree”, the slug could be tree
or counting-tree
or whatever you like, as long as it consists of one or more characters a
-z
, A
-Z
, 0
-9
, and -
. The produced test case files will have the slug as the prefix, for example: tree_1.in
.
The slug will be taken from the name of the problem package’s directory. For example, if your problem package directory is /home/fushar/my-contest/tree/
, then the slug would be tree
.
It is also possible to prepend the slug with some metadata string, separated by an underscore (_
). For example, if tree
if your third problem in your contest, you might want to call your problem package directory /home/fushar/my-contest/c_tree/
. In this case, the slug would be still tree
.
Spec and runner¶
The core activity when preparing test cases using tcframe is writing spec files. A spec file, along with a reference solution program, completely define the test cases of a single problem. A spec file is compilable into a single executable called runner program, which generates the test cases when executed.
To write a spec file, create a C++ source file called spec.cpp
in the problem package directory, and include the following header:
#include <tcframe/spec.hpp>
Every component of tcframe falls under tcframe
namespace, so you might want to import it for convenience:
using namespace tcframe;
In this file, you will be writing two classes: ProblemSpec
and TestSpec
.
Problem spec¶
A problem spec is a formal representation of a problem statement/description. It is the first step and the source of truth of the entire preparation of a problem. Once a problem spec is finalized, the corresponding test spec and a reference solution can then be developed.
In tcframe, a problem spec is implemented as a class called ProblemSpec
that inherits tcframe::BaseProblemSpec
.
class ProblemSpec : public BaseProblemSpec {
protected:
...
};
All members of this class must go into the protected section, except for private helper methods.
- I/O variables
- Member variables which compose the I/O formats.
- I/O formats
- How I/O variables are arranged in actual test case files.
- Constraints
- Conditions that I/O variables must satisfy.
- Subtasks
- Set of constraints in subproblems.
Test spec¶
A test spec defines the actual test cases for a particular problem spec. For problems with subtasks, it also defines how the test cases are distributed to the subtasks.
In tcframe, a problem spec is implemented as a class called TestSpec
that inherits tcframe::BaseTestSpec<T>
, where T
is the problem spec class (which should be ProblemSpec
).
class TestSpec : public BaseTestSpec<ProblemSpec> {
protected:
...
};
All members of this class must go in the protected section, except for private helper methods.
- Test cases
- Particular set of values of input variables.
- Test groups
- Set of test cases which conform to the same set of subtasks
Compiling spec file¶
You must have g++ at least version 4.8 to compile a spec file.
A spec file is compiled into a runner program using the following tcframe command:
tcframe build
The above command will compile spec.cpp
into an executable runner
program in the problem package directory.
Runner program¶
A runner program is an ordinary executable program. By executing the runner program, the test cases will be generated. By default, the produced test cases will be output to tc
directory inside problem package directory.
./runner
See the API reference for more details on supported command-line options, such as specifying which solution to run for producing the output files.
A runner program can also be used for performing local grading.
I/O variables¶
Input variables are C++ variables whose values compose test cases input files. They are are direct translations from variables mentioned in the problem statement’s input format section into C++ variables. For example, given the following description:
The first line contains two integers N and K. The second line contains N space-separated integers A[1], A[2], ..., A[N].
we will have three input variables: int N
, int K
, and vector<int> A
.
Input variables are the basic units of computation in tcframe. For example, they are manipulated in three different places:
- Input format definition in problem spec. It determines the layout of test case input files.
- Constraint definitions in problem spec. They determine whether the values of input variables are valid.
- Test case definitions in test spec. Each of them determines the content of a single test case input file.
Output variables are defined in a similar way, the only difference being that they are just manipulated in output format definition. Also, usually they consist of just a single variable without name in the problem statement’s output format. We can just name them result
or something similar.
I/O variables are defined as protected member variables in the problem spec class. For example:
class ProblemSpec : public BaseProblemSpec {
protected:
int N, K;
vector<int> A;
string result;
// the rest of problem spec components follow
};
Supported I/O variable types¶
tcframe supports three types of I/O variables as follows.
- Scalar
- Variables of built-in integral types (
int
,long long
,char
, etc.), built-in floating-point types (float
,double
), andstd::string
. - Vector
std::vector<T>
, whereT
is a scalar type as defined above.- Matrix
std::vector<std::vector<T>>
, whereT
is a scalar type as defined above.
Other types are not supported as I/O variables. tcframe prefers STL types whenever possible. For example, char*
is not supported as strings. Also, regular arrays (T[]
) and 2D arrays (T[][]
) are not supported.
I/O formats¶
Input format specifies two things at the same time:
- How the input variable values should be printed to official test case input files.
- How the sample test case input files should be parsed into input variables, as they are specified as literal strings. If some sample sample test cases can’t be parsed, it means that you have written invalid sample test cases, and the whole generation will fail.
Output format specifies how the output files should be parsed into output variables. If the output files can’t be parsed, it means that you have written invalid solution program, and the whole generation will fail.
Each of the I/O formats is defined as a list of I/O segments in InputFormat()
and OutputFormat()
methods of the problem specification class, respectively, as follows.
void InputFormat() {
// list of input segments
}
void OutputFormat() {
// list of output segments
}
Each I/O segment is specified by a function-like C++ macro. The I/O segments are specified one-by-one, each as a statement that calls the macro. For example:
void InputFormat() {
LINE(N, M);
EMPTY_LINE();
LINE(A % SIZE(N));
}
Supported I/O segments¶
The list of supported segments is given below. In all segments, it must be noted that:
- The terms scalar, vector, and matrix below refer to the I/O variable types described in the previous chapter.
- Vectors and matrices will have 0-based indexing. This is strict and there is no way to enforce 1-based indexing.
There are two categories of I/O segments: raw segments and tokenized segments.
Raw segments¶
These segments do not do any special formatting to the value of the variables; they will print/parse them as-is.
- Empty line
- Specified by the macro
EMPTY_LINE()
. Represents a single, empty line. - Raw line
Specified by the macro
RAW_LINE(...)
. Represent a line of the string given as the only argument. The argument must be ofstd::string
type.For example: ”... the next line consists of a sentence containing arbitrary printable ASCII characters S” can be specified by
RAW_LINE(S)
(whereS
is a string).- Multiple raw lines
Specified by the macro
RAW_LINES(...) % SIZE(<size>)
. Represent lines of string given as the only argument. The argument must be ofstd::vector<std::string>
type.For example: ”... each of the next N lines consists of a sentence containing arbitrary printable ASCII characters S” can be specified by
RAW_LINES(S) % SIZE(N)
(whereS
is a vector of strings).The size can also be omitted, as long as this is the last segment.
Tokenized segments¶
These segments do some formatting to the value of the variables. For example, the elements of a vector variable in a line will be printed space-separated.
Note
In tokenized segments, string variables cannot have whitespaces. For example, hello, world!
is considered to have two string variables: hello,
and world!
. Use raw segments if you want to work with strings containing whitespaces.
- Single line
Specified by the macro
LINE(...)
. Represents space-separated values in a single line.The macro accepts one or more I/O variables as arguments. The value of the variables will be space-separated. For example: ”... the first line consists of two space-separated integers N and M” can be specified by
LINE(N, M)
.Besides scalars, the arguments can be vectors, too. You need to specify the number of elements using
% SIZE(<size>)
syntax after each vector. For example: ”... the next line consists of N space-separated integers A[0], A[1], ... A[N-1]” can be specified byLINE(A % SIZE(N))
. The size can be a constant as well; for example,LINE(B % SIZE(3))
.You can freely combine scalars and vectors in
LINE()
; for example,LINE(N, A % SIZE(N), C % SIZE(2))
would represent a line consisting ofN A[0] A[1] ... A[N-1] C[0] C[1]
.Lastly, you can specify a vector without fixed size, as long as it is the last argument. For example: ”... the input consists an integer X followed by space-separated integers” can be specified by
LINE(X, A)
(whereA
is a vector).- Multiple lines
Specified by the macro
LINES(...) % SIZE(<size>)
. Represents multiple lines, each containing an element of a vector given as the argument.For example: ”... each of the next N lines contains an integer X[i]” can be specified by
LINES(X) % SIZE(N)
.There could be more than one vector as well. For example: ”... the next N lines each contains space-separated integers X[i] and Y[i]” can be specified by
LINES(X, Y) % SIZE(N)
. If there are multiple vectors, they all must have the same number of elements.You also could specify jagged vector as the last argument. This is useful for input format like, ”... then M lines follow. Each line begins with a string op. If op is
UPDATE
, then it is followed by two integers x y. If it isQUERY
, then it is followed by a single integer z”. This can be specified byLINES(op, data)
whereop
is avector<string>
anddata
is avector<vector<int>>
. Then,data[i]
represents a vector of integers in the i-th line, which can consist of one or two elements.Lastly, the size can also be omitted, as long as this is the last segment.
- Grid
Specified by the macro
GRID(...) % SIZE(<row>, <column>)
. Represents a grid containing elements of a matrix given as the only argument, laid out in a grid.For example: ”... each fo the next R lines contain C integers G[i][j]” can be specified by
GRID(G) % SIZE(R, C)
.If the matrix is of type
char
, the elements in each row is not space-separated, otherwise they are space-separated.
For more details, consult the API reference for I/O formats.
Notes¶
Unfortunately, the following are not supported (yet):
- Constants in I/O segments
For example: ”... the first line will always consist of the string
BEGIN
.” Everything must be wrapped in variables.As a workaround, just create an input variable and initialize it to
BEGIN
.- Complex conditional I/O format that can’t be handled by jagged vectors
There is NO known general workaround yet. We’re still working on designing how to handle complex format.
However, there are workarounds for simple cases, for example:
“Output the required sum, or the string
IMPOSSIBLE
if there is no solution.”In this case, you can just use a string as the output variable. The downside is that it is not type-safe; for example, the generation won’t fail if the reference solution mistakenly output an invalid string such as
123abc
.
However, a last resort for a workaround does exist for output format. If you have complex output format, you can just omit the method OutputFormat()
altogether and your solution’s output won’t be checked at all for validity.
Constraints¶
Constraints are conditions that must be satisfied by the input variables. The conditions will be verified on each test case. If any of the constraints is not satisfied, then the generation is considered to fail on that test case. There will be a nice error message explaining which constraints are not satisfied.
The truth value of a constraint must depend only on the values of the input variables in order for it to be a semantically correct constraint.
Constraints can be specified in the Constraints()
method of the problem spec class.
void Constraints() {
// list of constraint definitions
}
Constraint definitions¶
Constraints are specified as a list of constraint definitions. Each constraint definition is a boolean predicate of some property of the input variables. The predicate is passed as an argument to the CONS()
macro. The macros are then called one-by-one as method calls:
void Constraints() {
CONS(<predicate 1>);
CONS(<predicate 2>);
...
}
The constraint definition can be pulled directly from the constraints section in the actual problem description. For example: “1 ≤ A ≤ 1,000” can be specified by CONS(1 <= A && A <= 1000)
. “1 ≤ A, B ≤ 1,000” translates into two specifications: CONS(1 <= A && A <= 1000)
and CONS(1 <= B && B <= 1000)
. “1 ≤ A ≤ B ≤ 1,000” translates into CONS(1 <= A && A <= B && B <= 1000)
.
How about more complex predicates, such as “1 ≤ A[i] ≤ 1,000”? You can write a private method for this purpose. For example, it can be translated into CONS(eachElementBetween(A, 1, 1000))
and a private method as follows:
bool eachElementBetween(const vector<int>& X, int lo, int hi) {
for (int x : X) {
if (x < lo || x > hi) {
return false;
}
}
return true;
}
This also applies to even more complex predicates, such as “It is guaranteed that the given graph is a tree”. This can be translated to CONS(graphIsTree())
and define the appropriate private boolean method.
Notes¶
It is tedious to write eachElementBetween()
predicate over and over again as it is very common in problems. We are working on providing such helper methods as core part of tcframe in the next versions.
Subtasks¶
The concept of subtasks was first formally introduced in IOI 2010. The idea is basically to split a problem into two or more smaller problems with gradually increasing difficulty, and assign them different points.
For example:
In this type type of problem, you won’t be writing a Constraints()
method. Instead, you will be writing SubtaskX()
methods, where X
is the subtask number.
Note
As of this version, you can define up to 25 subtasks: Subtask1() .. Subtask25().
Subtask definitions¶
A subtask is basically just a set of constraints. It can be specified by the method SubtaskX()
, where X
is the subtask number. Inside the method, the constraint specifications are given, similar to what you usually do in the Constraints()
method.
Thus, the above example can be implemented as:
void Subtask1() {
CONS(N == 1);
CONS(1 <= K && K <= 100);
}
void Subtask2() {
CONS(1 <= N && N <= 100);
CONS(K == 1);
}
void Subtask3() {
CONS(1 <= N && N <= 100);
CONS(1 <= K && K <= 100);
}
Test groups¶
If your problem has subtasks, you will be writing test groups, not test cases.
Notes¶
Currently, tcframe does not provide a way to specify subtask points. It is up to the grader to implement the scoring.
Test cases¶
Technically, a test case is a particular state of input variables, with the corresponding correct values for the output variables. If the values of the input variables conform to each of the specified constraints, then the test case is considered valid, otherwise it is invalid.
Test cases are defined in the TestCases()
method of the test spec class.
void TestCases() {
// list of test case definitions
}
A sample test case is similar to a test case, except that it is not secret and appears in the problem statement. Sample test cases are defined in the SampleTestCaseX()
methods of the test spec class, where X is the sample test case number.
void SampleTestCase1() {
// sample test case I/O definitions
}
Test case definition¶
Test cases are specified as a list of test case definitions. Each test case definition is a comma-separated list of input variable assignments. The list is passed as the argument to the CASE()
macro. The macros are then called one-by-one as method calls:
void TestCases() {
CASE(<assignments list 1>);
CASE(<assignments list 2>);
...
}
For example, a valid test case definition is CASE(N = 100, M = 75)
. Vectors and matrices can be assigned conveniently using braces; for example, CASE(V = {1, 2, 3}, M = {{1, 2}, {3, 4}})
.
For more complex assignment, such as constructing a tree, create a private void
method that constructs the tree, and call it in CASE()
. For example, CASE(N = 100, linearTree())
and having this private method:
/* Constructs a linear tree */
void linearTree() {
for (int i = 0; i < N; i++) {
parent.push_back(i-1);
}
}
Note
The values of input variables before each test case are undefined, and may contain leftover computation from previous test cases. See Test case lifecycle on how to initialize them.
You can also use for-loop construct for assigning some input variables. This is usually done if you want to exhaust all valid possibilities of some input variables. For example:
void TestCases() {
for (int i = 1; i <= 10; i++) {
CASE(N = i);
}
}
We recommend not using this style unless absolutely necessary.
Each test case definition will be realized as a pair of input/output files, with the following filenames: <slug>_<case-number>.in
and <slug>_<case-number>.out
. For example, sum_1.in
, sum_1.out
.
Sample test case definition¶
Note
As of this version, you can define up to 25 sample test casses: SampleTestCase1() .. SampleTestCase25().
Unlike test cases, sample test cases are specified as literal strings, exactly as they appear in problem statement. This way, you can be visually sure that you are typing sample test cases in problem statement correctly.
The literal strings are passed line-by-line to the Input()
and Output()
calls as follows (note the {}
braces):
void SampleTestCase1() {
Input({
"<line 1>",
"<line 2>",
...
});
Output({
"<line 1>",
"<line 2>",
...
});
}
The supplied output must match with the actual output produced by the solution program.
For example, this sample test case:
Input:
3 4
1 2 3
Output:
2
100
200
can be translated to:
void SampleTestCase1() {
Input({
"3 4",
"1 2 3"
});
Output({
"2",
"100",
"200"
});
}
Note
The Output()
part of a sample test case definition is optional, and if not present, the solution will be run to produce the output. However, it is only for easier migration from tcframe 0.x. You should always specify both input and output, so that you are sure you are typing the output correctly in the problem statement by only looking at the spec file (no need to check with the actual produced output file).
If your problem has subtasks, you also need to assign each sample test case to a set of subtasks, by calling Subtasks()
at the beginning of each SampleTestCaseX()
with the set of subtask numbers, as follows.
void SampleTestCase1() {
Subtasks({2, 3});
Input({
"3 4",
"1 2 3"
});
Output({
"2",
"100",
"200"
});
}
Each sample test case will be realized as a pair of input/output files, with the following filenames: <slug>_sample_<case-number>.in
and <slug>_sample_<case-number>.out
. For example, sum_sample_1.in
, sum_sample_1.out
.
Random number generator¶
tcframe provides a simple random number generator object, tcframe::rnd
. For example, you can use it to generate a random array: CASE(N = 100, randomArray())
where randomArray()
is defined as follows.
void randomArray() {
for (int i = 0; i < N; i++) {
A.push_back(rnd.nextInt(1000000));
}
}
For more details, consult the API reference for random number generator.
Test case lifecycle¶
Note
This section only applies to official test cases. It is not applicable to sample test cases.
tcframe declares two methods that you can implement in the test spec class: BeforeTestCase()
and AfterTestCase()
to hook up additional logic to run during a test case generation. For each test case, the following things will happen in order:
BeforeTestCase()
is executed.- The assignments/method calls inside
CASE()
are executed. AfterTestCase()
is executed.- Input variable values are printed according to the input format.
BeforeTestCase()¶
This method can be implemented to initialize input variables. For example, if you have vectors as input variables, you will want to initialize them first before calling e.g. randomArray()
inside CASE()
macro.
void BeforeTestCase() {
parent.clear();
A.clear();
}
AfterTestCase()¶
You may want to manipulate input variables with a different representation from what is defined in the input format section. For example, suppose that you want to have a tree as an input. In the input format (in problem spec class), you specify the tree as a list of edges (U[i], V[i]) as follows:
void InputFormat() {
LINE(N);
LINES(U, V) % SIZE(N - 1);
}
and you want to manipulate the tree as a vector P[], where P[i] is the parent of node i. (I.e., you have private variable vector<int> P
in the test spec class.)
This can be achieved by implementing AfterTestCase()
, transforming the vector P[] into a pair of vectors (U[], V[]) there.
void AfterTestCase() {
U.clear();
P.clear();
for (int i = 0; i < N; i++) {
if (P[i] != -1) {
U.push_back(i);
V.push_back(P[i]);
}
}
}
Test groups¶
A test group is a set of test cases that are assigned/included to the same set of subtasks. If your problem has subtasks, then instead of writing TestCases()
method, you will be writing TestGroupX()
methods instead, where X
is the test group number.
For the whole test cases to be strong, a test case should be assigned in multiple subtasks if possible. In other words, several subtasks may share some test cases. In tcframe, a test case must be assigned to a subtask if (and only if) it satisfies the constraints of that subtask.
Designing test groups¶
In this example, we will use this subtasking scheme:
Our advice on designing test groups is as follows.
First, create a Venn diagram denoting the valid test cases for all subtasks. For this problem, the diagram will be like this:
In order to have a strong set of test cases, we should create a test group for each closed region in the Venn diagram. In this case, we will have four test groups as follows:
- Test group 1: consists of only one test case N = K = 1. Assign it to subtasks {1, 2, 3}.
- Test group 2: generate test cases that satisfy N = 1; 2 ≤ K ≤ 100. Assign them to subtasks {1, 3}.
- Test group 3: generate test cases that satisfy 2 ≤ N ≤ 100; K = 1. Assign them to subtasks {2, 3}.
- Test group 4: generate test cases that satisfy 2 ≤ N, K ≤ 100. Assign them to subtasks {3}.
Test group definitions¶
To define test groups, write each of the methods TestGroupX()
, where X
is a positive integer denoting the test group number, starting from 1. Then, call the Subtasks(S)
method as the first statement, where S
is a set of subtask numbers. The remaining bodies of test group methods are test case definitions. For the above example:
void TestGroup1() {
Subtasks({1, 2, 3});
// CASE() calls follow
}
void TestGroup2() {
Subtasks({1, 3});
// CASE() calls follow
}
void TestGroup3() {
Subtasks({2, 3});
// CASE() calls follow
}
void TestGroup4() {
Subtasks({3});
// CASE() calls follow
}
Note
As of this version, you can define up to 25 test groups: TestGroup1() .. TestGroup25().
Each test case definition will be realized as a pair of input/output files, with the following filenames: <slug>_<group-number>_<case-number>.in
and <slug>_<group-number>_<case-number>.out
. For example, sum_2_3.in
, sum_2_3.out
.
Notes¶
Although a test group may be assigned to several subtasks, tcframe will produce the test case files according to their test group and test case number as defined above. It is up to the implementation of the grader on how to choose which test cases to grade for a subtask. For example, if your grader only accepts a set of test cases for each subtask, you can duplicate each test case for every subtask it is assigned to.
For tcframe‘s local grading feature, each test case will be executed only once. The result is shared for every subtask it is assigned to.
Multiple test cases per file¶
tcframe supports ICPC-style test cases, where there are multiple test cases in a single file, which preceded by a single line containing the test case count.
The following is how tcframe will combine multiple test cases into individual files:
- All sample test cases in
SampleTestCaseX()
methods will be combined into<slug>_sample.{in,out}
. - All test cases in
TestCases()
method will be combined into<slug>.{in,out}
. - All test cases in each of the
TestGroupX()
method will be combined into<slug>_<X>.{in,out}
.
You need to apply the following changes in order to make a spec file ICPC-style.
Problem spec class¶
Add the following as members of ProblemSpec
:
Input variable counter¶
Declare an integer input variable (e.g., T
) that will hold the number of test cases in a single file.
protected:
int T;
...
Then, write a method MultipleTestCasesConfig()
, and call the Counter()
method with T
as the argument.
void MultipleTestCasesConfig() {
Counter(T);
}
Output prefix¶
You can also specify the prefix to be prepended before the output of each test case in a file. For example, in ICPC, usually each test case in the output must be prepended by Case #X:
, where X
is the test case number in that file. This can be achieved by calling OutputPrefix()
method in MultipleTestCasesConfig()
, with the prefix string as the argument. The string may contain %d
which will be replaced with the actual test case number. For example:
void MultipleTestCasesConfig() {
Counter(T);
OutputPrefix("Case #%d: ");
}
Input format¶
The input format should not contain T
. It should specify the format of a single test case only. The number of test cases will be automatically prepended in the final combined test case input file.
Constraints¶
Constraints can be imposed on T
, by writing the MultipleTestCasesConstraints()
method and defining its constraints there.
void MultipleTestCasesConstraints() {
CONS(1 <= T && T <= 20);
}
Test spec class¶
No changes are necessary. You also don’t need to prepend the output prefix in sample test case outputs. Write the sample test cases as if they are not combined into a single file.
Solution program¶
Although the input/output format only specifies a single test case, you must write the solution as if the test cases are already combined. In other words, the solution will read the number of test cases in the first line, then that many of test cases, and must output the answer of each test case.
Example¶
Here is our sample sum
problem in ICPC-style.
#include <tcframe/spec.hpp>
using namespace tcframe;
class ProblemSpec : public BaseProblemSpec {
protected:
int T;
int A, B;
int sum;
void InputFormat() {
LINE(A, B);
}
void OutputFormat() {
LINE(sum);
}
void GradingConfig() {
TimeLimit(1);
MemoryLimit(64);
}
void MultipleTestCasesConfig() {
Counter(T);
OutputPrefix("Case #%d: ");
}
void MultipleTestCasesConstraints() {
CONS(1 <= T && T <= 20);
}
void Constraints() {
CONS(1 <= A && A <= 1000);
CONS(1 <= B && B <= 1000);
}
};
class TestSpec : public BaseTestSpec<ProblemSpec> {
protected:
void SampleTestCase1() {
Input({
"4 6"
});
Output({
"10"
});
}
void TestCases() {
CASE(A = 1, B = 1);
CASE(A = 1000, B = 1000);
CASE(A = 42, B = 100);
CASE(A = rnd.nextInt(1, 1000), B = rnd.nextInt(1, 1000));
}
};
Local grading¶
tcframe allows you to grade solutions locally, on your machine.
Before grading a solution, you must have already generated the test cases:
./runner
Then, you can “grade” a solution, by executing:
./runner grade [--solution=<solution-command>]
where <solution-command>
is the command for executing the solution. If it is omitted, the default is ./solution
.
For example, suppose you have written a problem package for a problem. Your friend also has written an alternate solution to the problem, and he wants to check whether his solution agrees with yours. Let’s assume that his solution file is alt_solution.cpp
. Compile it into alt_solution
, place it in the problem package, and then run
./runner grade --solution=./alt_solution
The verdict of each test case will be shown. The verdict will be one of the following:
- Accepted (AC)
- The output produced by the solution matches.
- Wrong Answer (WA)
- The output produced by the solution does not match. The diff will be shown, truncated to the first 10 lines.
- Runtime Error (RTE)
- The solution crashed or used memory above the limit, if specified.
- Time Limit Exceeded (TLE)
- The solution did not stop within the time limit, if specified.
The verdict of each subtask will be also shown. The verdict of a subtask is the worst verdict of all verdicts of test cases that are assigned to it. Here, RTE is worse than WA, and WA is worse than AC.
Here is a sample output of a local grading for problems with subtasks.
Grading...
[ SAMPLE TEST CASES ]
k-product_sample_1: Accepted
[ TEST GROUP 1 ]
k-product_1_1: Accepted
[ TEST GROUP 2 ]
k-product_2_1: Accepted
k-product_2_2: Accepted
k-product_2_3: Accepted
[ TEST GROUP 3 ]
k-product_3_1: Accepted
k-product_3_2: Wrong Answer
* Diff:
(expected) [line 01] 11
(received) [line 01] 12
k-product_3_3: Accepted
[ TEST GROUP 4 ]
k-product_4_1: Accepted
k-product_4_2: Accepted
k-product_4_3: Accepted
k-product_4_4: Accepted
k-product_4_5: Accepted
k-product_4_6: Runtime Error
* Execution of submission failed:
- Exit code: 1
- Standard error:
[ RESULT ]
Subtask 1: Accepted
Subtask 2: Wrong Answer
Subtask 3: Runtime Error
and here is for problems without subtasks
Grading...
[ SAMPLE TEST CASES ]
k-product_sample_1: Accepted
[ OFFICIAL TEST CASES ]
k-product_1: Accepted
k-product_2: Accepted
k-product_3: Accepted
k-product_4: Wrong Answer
* Diff:
(expected) [line 01] 11
(received) [line 01] 12
[ RESULT ]
Wrong Answer
This local grading feature is useful for creating “unit tests” for your test cases. For each problem, you can write many solutions with different intended results. For example, solution_123.cpp
should pass subtasks 1 - 3; solution_12.cpp
should pass subtasks 1 and 2 but not subtask 3, etc.
Notes¶
Internally, tcframe uses ulimit
to limit the time and memory used when running the solution. Unfortunately, there is no easy way to restrict memory limit on OS X, so the memory limit will be always ignored when using this feature on OS X.
Tutorials¶
Here, you can find case studies and best practices on how to write your spec files. It is expected that you have already read the getting started guide before reading through the tutorials.
Tutorial 1: Best Pair¶
In this tutorial, you will learn how to write a generator for a simple yet tricky problem, called Best Pair. We will focus on the general idea of how to come up with a strong set of test cases.
Here is the complete problem statement:
4
4 -2 3 1
12
Cool, let’s now start writing generator for this problem. The conventional steps to do this are:
- Prepare the problem package.
- Write the solution.
- Write the problem spec.
- Write the test spec.
We will tackle each step in more details below.
Note
The complete source files for this tutorial can also be found here.
Preparing problem package¶
First, we need to come up with a slug for this problem. Let’s call it best-pair
.
Now, create a directory best-pair
in your system. For example, create it in your home directory (~/best-pair
). We will then store all files related to this problem there.
Writing solution¶
Although the solution can actually be written any time during this process, we recommend doing it before writing the spec. Why? Sometimes, after (trying) to write the solution, you will realize that:
- Some constraints make the problem impossible to solve.
- You find a much simpler solution that makes the problem too easy and not suitable for you contest.
- The problem is actually impossible to solve.
Thus, you will save your time from writing the spec if the problem is actually invalid as explained above.
Anyway, let’s now solve this problem. The solution is simple: it is the maximum of the following:
- product of two largest non-negative elements
- product of two smallest negative elements
- (tricky) product of the largest negative element and the smallest positive element
Here is a sample C++ implementation of the above idea. It is not the fastest solution, but should suffice for the purposes of this tutorial.
best-pair/solution.cpp
:
#include <bits/stdc++.h>
using namespace std;
int N;
vector<long long> pos;
vector<long long> neg;
int main() {
cin >> N;
for (int i = 0; i < N; i++) {
long long x;
cin >> x;
if (x >= 0) {
pos.push_back(x);
} else {
neg.push_back(x);
}
}
sort(pos.begin(), pos.end());
sort(neg.begin(), neg.end());
long long res = LLONG_MIN;
if (pos.size() >= 2) {
res = max(res, pos[pos.size()-1] * pos[pos.size()-2]);
}
if (neg.size() >= 2) {
res = max(res, neg[0] * neg[1]);
}
if (!neg.empty() && !pos.empty()) {
res = max(res, neg[neg.size()-1] * pos[0]);
}
cout << res << endl;
}
Writing problem spec¶
The following is a problem spec that is derived directly from the problem statement. Note that we are using a private method eachElementBetween()
to represent the constraint -1,000,000 ≤ A[i] ≤ 1,000,000. Everything else should be straightforward.
best-pair/spec.cpp
:
#include <bits/stdc++.h>
#include <tcframe/spec.hpp>
using namespace std;
using namespace tcframe;
class ProblemSpec : public BaseProblemSpec {
protected:
int N;
vector<long long> A;
long long res;
void InputFormat() {
LINE(N);
LINE(A % SIZE(N));
}
void OutputFormat() {
LINE(res);
}
void GradingConfig() {
TimeLimit(1);
MemoryLimit(64);
}
void Constraints() {
CONS(2 <= N && N <= 100000);
CONS(eachElementBetween(A, -1000000, 1000000));
}
private:
bool eachElementBetween(const vector<long long>& v, long long lo, long long hi) {
for (long long x : v) {
if (x < lo || x > hi) {
return false;
}
}
return true;
}
};
Writing test spec¶
This is the most challenging part!
First, write the sample test cases as written in the problem statement as follows. As an advice, sample test cases should not reveal all trickiness of the problem. In the sample below, the answer is the most obvious case: the product of two largest non-negative elements of A.
best-pair/spec.cpp
(continued):
class TestSpec : public BaseTestSpec<ProblemSpec> {
protected:
void SampleTestCase1() {
Input({
"4",
"4 -2 3 1"
});
Output({
"12"
});
}
};
Then, let’s move on to the actual, official test cases. Firstly, we will implement the BeforeTestCase()
method to initialize the vector A before every test case, as follows.
void BeforeTestCase() {
A.clear();
}
Next, the actual test cases. We should come up with a good set of test cases that does both the following:
- accepting correct solutions, and
- rejecting incorrect solutions (important!)
Recall that the solution we’ve written above considers 3 different cases. Let’s write a test case that covers each case.
- The answer is the product of two largest non-negative elements
CASE(N = 5, A = {-2, -1, 2, 3, 0});
- The answer is the product of two smallest negative elements
CASE(N = 5, A = {3, 4, -1, -3, -5});
- The answer is the product of the largest negative element and the smallest positive element
CASE(N = 2, A = {2, -1});
Note that the above case is only possible with N = 2.
There are also several cases for which the answer has some interesting properties, as follows.
- The answer is 0
This is the case when everything but one is zero, or everything is zero.
CASE(N = 4, A = {0, 2, 0, 0});
CASE(N = 4, A = {0, 0, 0, 0});
- The answer is the maximum possible answer
This will reject solutions that do not use 64-bit integers.
CASE(N = 3, A = {1000000, -1, 1000000});
- The answer is the minimum possible answer
This will reject solutions that do not use 64-bit integers as well.
CASE(N = 2, A = {-1000000, 1000000});
Note that (3) and (6) will reject solutions which initialize the answer to 0 (instead of a very small negative integer).
So far, we have considered various cases for which the answer has some properties. Let’s now consider cases for which the input itself has some interesting properties.
- All elements are positive/negative
This will reject solutions which do not properly handle empty collections for positive/negative elements.
CASE(N = 4, A = {1, 2, 3, 4});
CASE(N = 4, A = {-1, -2, -3, -4});
- All elements are zero
This can probably reject solutions which separate zeroes for some reasons (it’s actually unnecessary).
This is already covered by (4).
- N = 2
This is the smallest possible value for N. Already covered by (3) and (6).
- Random values for elements of A
It’s always good idea to include randomized input to the test data when the input space is very large (which should be true for most problems).
The randomized elements of A can be generated using a private function, as follows:
void randomElements() { for (int i = 0; i < N; i++) { A.push_back(rnd.nextInt(-1000000, 1000000)); } }
(Note that at the beginning of the above method, N will have been set to a value from
CASE()
, and A will have been cleared byBeforeTestCase()
.)The above is good enough for this problem. However, it is nicer if we can somehow “tune” some properties of the randomization. For example, we can have parameters denoting the number of desired positive and negative numbers in A:
void randomElements(int numPos, int numNeg) { assert(numPos + numNeg <= N); for (int i = 0; i < numPos; i++) { A.push_back(rnd.nextInt(1, 1000000)); } for (int i = 0; i < numNeg; i++) { A.push_back(rnd.nextInt(-1000000, -1)); } for (int i = 0; i < N-numPos-numNeg; i++) { A.push_back(0); } rnd.shuffle(A.begin(), A.end()); }
Again, the above tuning is not really necessary for this problem, as most tricky cases have been covered by previous hand-made test cases. However, for the purpose of learning, we will still use the tuning.
It is not the only tuning that we can do. Other options include:
- Tuning the range of possible values of the randomized element. For example, if we want the elements to be randomized between just 1 and 100.
- Same as above, but also tuning the percentage of the tuned range. For example, if we want the elements to be totally randomized, except a quarter of them, which should be between 1 and 100.
- etc.
All right, now use this function in
CASE()
, with various arguments to it (and various values for N), for example as follows.CASE(N = 10, randomElements(5, 5));
CASE(N = 100, randomElements(20, 50));
CASE(N = 1000, randomElements(300, 300));
CASE(N = 10000, randomElements(2500, 6000));
- N = 100000
The maximum value of N. This will reject solutions that use array with size less than 100,000.
CASE(N = 100000, randomElements(50000, 50000));
CASE(N = 100000, randomElements(10000, 80000));
CASE(N = 100000, randomElements(80000, 10000));
There are possibly some other cases that we can explore, but for now, this set of test cases should be strong enough for our problem!
Putting it all together¶
Here is the complete spec file for our Best Pair problem.
#include <bits/stdc++.h>
#include <tcframe/spec.hpp>
using namespace std;
using namespace tcframe;
class ProblemSpec : public BaseProblemSpec {
protected:
int N;
vector<long long> A;
long long res;
void InputFormat() {
LINE(N);
LINE(A % SIZE(N));
}
void OutputFormat() {
LINE(res);
}
void GradingConfig() {
TimeLimit(1);
MemoryLimit(64);
}
void Constraints() {
CONS(1 <= N && N <= 100000);
CONS(eachElementBetween(A, -1000000, 1000000));
}
private:
bool eachElementBetween(const vector<long long>& v, long long lo, long long hi) {
for (long long x : v) {
if (x < lo || x > hi) {
return false;
}
}
return true;
}
};
class TestSpec : public BaseTestSpec<ProblemSpec> {
protected:
void SampleTestCase1() {
Input({
"4",
"4 -2 3 1"
});
Output({
"12"
});
}
void BeforeTestCase() {
A.clear();
}
void TestCases() {
// The answer is the product of two largest non-negative elements
CASE(N = 5, A = {-2, -1, 2, 3, 0});
// The answer is the product of two smallest negative elements
// The smallest possible value for N
CASE(N = 5, A = {3, 4, -1, -3, -5});
// The answer is the product of the largest negative element and the smallest positive element
CASE(N = 2, A = {2, -1});
// The answer is 0
CASE(N = 4, A = {0, 2, 0, 0});
CASE(N = 4, A = {0, 0, 0, 0});
// The answer is the maximum possible answer
CASE(N = 3, A = {1000000, -1, 1000000});
// The answer is the minimum possible answer
CASE(N = 2, A = {-1000000, 1000000});
// All elements are positive/negative
CASE(N = 4, A = {1, 2, 3, 4});
CASE(N = 4, A = {-1, -2, -3, -4});
// Random values for elements of A
CASE(N = 10, randomElements(5, 5));
CASE(N = 100, randomElements(20, 50));
CASE(N = 1000, randomElements(300, 300));
CASE(N = 10000, randomElements(2500, 6000));
// The maximum value of N
CASE(N = 100000, randomElements(50000, 50000));
CASE(N = 100000, randomElements(10000, 80000));
CASE(N = 100000, randomElements(80000, 10000));
}
private:
void randomElements(int numPos, int numNeg) {
assert(numPos + numNeg <= N);
for (int i = 0; i < numPos; i++) {
A.push_back(rnd.nextInt(1, 1000000));
}
for (int i = 0; i < numNeg; i++) {
A.push_back(rnd.nextInt(-1000000, -1));
}
for (int i = 0; i < N-numPos-numNeg; i++) {
A.push_back(0);
}
rnd.shuffle(A.begin(), A.end());
}
};
That’s it! The complete source files for this tutorial can also be found here.
API Reference¶
Problem spec¶
ProblemSpec
must inherit tcframe::BaseProblemSpec
:
class ProblemSpec : public BaseProblemSpec {};
Except for private helper functions, every member of ProblemSpec
listed below must be protected
.
Input/output variables¶
Defined as instance member variables of ProblemSpec
, which will be referenced in other methods of ProblemSpec
and TestSpec
.
There are three supported types of variables:
- Scalar
- Variables of built-in integral types (
int
,long long
,char
, etc.), built-in floating-point types (float
,double
), andstd::string
. - Vector
std::vector<T>
, whereT
is a scalar type as defined above. Arrays (T[]
) are not supported.- Matrix
std::vector<std::vector<T>>
, whereT
is a scalar type as defined above. 2D arrays (T[][]
) are not supported.
Example:
class ProblemSpec : public BaseProblemSpec {
protected:
int A, B;
vector<int> parent;
vector<vector<int>> values;
};
Input/output formats¶
virtual void InputFormat() = 0;
Defines the input format. It is mandatory.
virtual void OutputFormat() {}
Defines the output format. It is optional; if not implemented, then the output will not be validated.
Defining format
The following macros are exposed to define input/output formats:
-
EMPTY_LINE
()¶ Defines an empty line.
-
RAW_LINE
(string variable name)¶ Defines a line of raw string. The variable must be of
std::string
type.Example:
void InputFormat() { RAW_LINE(S); }
With S = “Hello, world!”, the above format will produce:
Hello, world!
-
RAW_LINES
(vector of string variable name)¶ -
RAW_LINES
(vector of string variable name) % SIZE(number of elements) Defines multiple lines, each consisting of raw string. The variable must be of
std::vector<std::string>
type.If the size is not given, then this must be the last segment in the I/O format.
Example:
void InputFormat() { RAW_LINES(X) % SIZE(2); RAW_LINES(Y); }
With X = {“Hello, world!”, “Happy new year.”}, Y = {“lorem”, “ipsum”, “dolor sit amet”}, the above format will produce:
Hello, world! Happy new year. lorem ipsum dolor sit amet
-
LINE
(comma-separated elements)¶ Defines a single line containing space-separated scalar or vector variables. In case of vector variables, the elements are separated by spaces as well.
element is one of:
- <scalar variable name>.
- <vector variable name> % SIZE(<number of elements>). The number of elements can be a constant or a scalar variable.
- <vector variable name>. Here, the number of elements is unspecified. This kind of element must occur last in a line segment, if any. Elements will be considered until new line is found.
Example:
void InputFormat() { LINE(N); LINE(A % SIZE(3), B); LINE(M, C % SIZE(M)); }
With N = 2, A = {1, 2, 3}, B = {100, 200, 300, 400}, M = 2, C = {7, 8}, the above format will produce:
2 1 2 3 100 200 300 400 2 7 8
-
LINES
(comma-separated vector/matrix variable names)¶ -
LINES
(comma-separated vector/matrix variable names) % SIZE(number of elements) Defines multiple lines, each consisting of space-separated elements of given vector/matrix variables.
If the size is not given, this must be the last segment in the I/O format.
Example:
void InputFormat() { LINES(V) % SIZE(2); LINES(X, Y) % SIZE(N); LINES(Z); }
With V = {1, 2}, X = {100, 110, 120}, Y = {200, 210, 220} N = 3, Z = {1, 2, 3, 4} the above format will produce:
1 2 100 200 110 210 120 220 1 2 3 4
If a matrix variable is given, it must occur as the last argument, and the number of rows must match with the number of elements of the other vector variables (if any). It is not required that each row of the matrix consists of the same number of columns.
Example:
void InputFormat() { LINES(op, data) % SIZE(2); }
With op = {“UPDATE”, “QUERY”}, data = {{3, 5}, {7}}, the above format will produce:
UPDATE 3 5 QUERY 7
-
GRID
(matrix variable name) % SIZE(number of rows, number of columns)¶ Defines a grid consisting elements of a given matrix variable. If the given matrix variable is of type
char
, the elements in each row is not space-separated, otherwise they are space-separated.Example:
void InputFormat() { GRID(G) % SIZE(2, 2); GRID(H) % SIZE(R, C); }
With G = {{‘a’, ‘b’}, {‘c’, ‘d’}}, H = {{1, 2, 3}, {4, 5, 6}}, R = 2, C = 3, the above format will produce:
ab cd 1 2 3 4 5 6
Constraints and subtasks¶
virtual void MultipleTestCasesConstraints() {}
Defines the constraints to be imposed to the multiple test cases counter.
virtual void Constraints() {}
Defines the constraints to be imposed to the input/output variables.
virtual void Subtask1() {}
virtual void Subtask2() {}
// ...
virtual void Subtask25() {}
Defines the constraints to be imposed to the input/output variables for each subtask (up to 25).
Defining constraints
The following macro is exposed to define constraints:
-
CONS
(predicate)¶ Defines a constraint. predicate is a boolean expression, whose value must be completely determined by the values of the input variables (only).
Example:
void Subtask1() { CONS(A <= B && B <= 1000); CONS(graphDoesNotHaveCycles()); }
Multiple test cases config¶
virtual void MultipleTestCasesConfig() {}
Defines the config for multiple test cases per file problems. The following methods are exposed:
-
Counter
(int &var)¶ Sets the input variable that will hold the number of test cases in a file.
-
OutputPrefix
(std::string prefix)¶ Sets the prefix to be prepended to the output of each test case. It can include
%d
, which will be replaced by the actual test case number (1-based).
Example:
void MultipleTestCasesConfig() {
Counter(T);
OutputPrefix("Case #%d: ");
}
Grading config¶
virtual void GradingConfig() {}
Defines the config for local grading. The following methods are exposed:
-
TimeLimit
(int timeLimitInSeconds)¶ Sets the time limit in seconds. If not specified, the default value is 2 seconds.
-
MemoryLimit
(int memoryLimitInMegabytes)¶ Sets the memory limit in MB. If not specified, the default value is 64 MB.
Example:
void GradingConfig() {
TimeLimit(3);
MemoryLimit(256);
}
Test spec¶
TestSpec
must inherit tcframe::BaseTestSpec<ProblemSpec>
:
class TestSpec : public BaseTestSpec<ProblemSpec> {};
Except for private helper functions, every member of TestSpec
listed below must be protected
.
Sample test cases¶
virtual void SampleTestCase1() {}
virtual void SampleTestCase2() {}
// ...
virtual void SampleTestCase25() {}
Defines the sample test cases (up to 25). The following methods are exposed:
-
Subtasks
(std::set<int> subtaskNumbers)¶ Assigns the current sample test case to a set of subtasks, if the problem has subtasks. If used, this should be the first call in a sample test case.
-
Input
(std::vector<std::string> lines)¶ Defines the input as exact literal string, given as list of lines.
-
Output
(std::vector<std::string> lines)¶ Defines the input as exact literal string, given as list of lines. It is optional; if not specified, the solution will be run against the sample input to produce the corresponding sample output.
Example:
void SampleTestCase1() {
Input({
"4 6",
"a b c"
});
Output({
"10"
});
}
Test cases and test groups¶
virtual void TestCases() {}
Defines the test cases.
virtual void TestGroup1() {}
virtual void TestGroup2() {}
// ...
virtual void TestGroup25() {}
Defines the test cases on each test group (up to 25). The following method is exposed:
-
Subtasks
(std::set<int> subtaskNumbers)¶ Assigns the current test group to a set of subtasks. This should be the first call in a test group.
void TestGroup1() { Subtasks({1, 3}); // test case definitions follow }
Defining test cases
The following macro is exposed to define test cases:
-
CASE
(comma-separated statements)¶ Defines a test case.
statement should be one of:
- assignment to an input variables
- private method call that assigns values to one or more input variables
Example:
void TestCases() { CASE(N = 42, M = 100, randomArray()); CASE(N = 1000, M = 1000, randomArray()); CASE(randomEqualNandM(), randomArray()); }
Test case lifecycle¶
virtual void BeforeTestCase() {}
virtual void AfterTestCase() {}
Hook up additional logic to run during in a test case lifecycle.
For each test case, the following things will happen in order:
BeforeTestCase()
is executed.- The assignments/method calls inside
CASE()
are executed. AfterTestCase()
is executed.- Input variable values are printed according to the input format.
Random number generator¶
BaseTestSpec
exposes a random number generator object rnd
that can be utilized to define test cases. The following methods are available on it:
-
int
nextInt
(int minNum, int maxNum)¶ Returns a uniformly distributed random integer (int) between minNum and maxNum, inclusive.
-
int
nextInt
(int maxNumEx)¶ Returns a uniformly distributed random integer (int) between 0 and maxNumEx - 1, inclusive.
-
long long
nextLongLong
(long long minNum, long long maxNum)¶ Returns a uniformly distributed random integer (long long) between minNum and maxNum, inclusive.
-
long long
nextLongLong
(long long maxNumEx)¶ Returns a uniformly distributed random integer (long long) between 0 and maxNumEx - 1, inclusive.
-
double
nextDouble
(double minNum, double maxNum)¶ Returns a uniformly distributed random real number (double) between minNum and maxNum, inclusive.
-
double
nextDouble
(double maxNum)¶ Returns a uniformly distributed random real number (double) between 0 and maxNum, inclusive.
-
void
shuffle
(std::RandomAccessIterator first, std::RandomAccessIterator last)¶ Randomly shuffles the elements in [first, last). Use this instead of
std::random_shuffle()
.
Runner program¶
A runner is the compiled version of a spec file, and is capable of two things:
Test cases generation¶
./runner [options]
-
--output=<dir>
The output directory to which the test cases will be generated. Default:
tc
.
-
--solution=<command>
The solution command to use for generating output files. Default:
./solution
.
-
--seed=<seed>
The seed for random number generator
rnd
in the test spec. Default:0
.
Local grading¶
./runner grade [options]
-
--output=<dir>
The output directory from which the generated test cases will be read. Default:
tc
.
-
--solution=<command>
The solution command to grade. Default:
./solution
.
-
--time-limit=<time-limit-in-seconds>
Overrides the time limit specified by
TimeLimit()
in grading config.
-
--memory-limit=<memory-limit-in-megabytes>
Overrides the memory limit specified by
MemoryLimit()
in grading config.
-
--no-time-limit
Unsets the time limit specified by
TimeLimit()
in grading config.
-
--no-memory-limit
Unsets the memory limit specified by
MemoryLimit()
in grading config.
Release Notes¶
1.1.0¶
December 4, 2016
New features¶
- It is now possible to omit
SIZE()
for aLINES()
segment, as long as it is the last segment in an I/O format. - Brand new segments:
RAW_LINE()
andRAW_LINES()
, which accept strings containing whitespaces.
Enhancements¶
I/O format errors after a vector/matrix now have the last indices reported in the error message. For example,
Before:
Expected: <newline> after 'D'
Now:
Expected: <newline> after 'D[1]'
1.0.1¶
November 28, 2016
Bugfixes¶
- Fixed a regression when I/O format segments do not pick up correct sizes taken from I/O variables.
- Fixed a regression when
std::string
cannot be used as variable type.
1.0.0¶
November 27, 2016
Note
See the migration guide from 0.x at the bottom of this page.
First stable release. Almost a complete rewrite from 0.x. Focusing on syntax improvements and conceptual refinements.
BREAKING CHANGES¶
- Minimum GCC version is now 4.8.
- The source file of a runner program is now conceptually called “spec file”, and is called
spec.cpp
instead ofrunner.cpp
. - A spec file now includes
<tcframe/spec.hpp>
instead of<tcframe/runner.hpp>
. main()
function in a spec file is not needed and must be removed.- Problem specification is now called a “problem spec”, and its class is
ProblemSpec
instead ofProblem
. It now inheritsBaseProblemSpec
. - Generator specification is now called a “test spec”, and its class is
TestSpec
instead ofGenerator
. It now inheritsBaseTestSpec
. - The container directory of a spec file is now conceptually called “problem package directory”.
- The slug for a problem is now taken from the name of the problem package directory, and cannot be overridden via problem spec or command-line option.
Config()
in test spec is removed, so it is not possible to e.g. specify the solution command and test cases output directory in test spec.Config()
in problem spec is split intoGradingConfig()
andMultipleTestCasesConfig()
.setTimeLimit()
andsetMemoryLimit
in problem spec’sConfig()
are nowTimeLimit()
andMemoryLimit()
inGradingConfig()
.setMultipleTestCasesCount()
in problem spec’sConfig()
is nowCounter()
inMultipleTestCasesConfig()
.assignToSubtasks()
in test groups is nowSubtasks()
.- Individual sample test cases now live in their own methods,
SampleTestCaseX()
where X is sample test case number. SAMPLE_CASE()
is split into multiple calls:Subtasks()
,Input()
, andOutput()
.FinalizeInput()
is renamed toAfterTestCase()
.- “Submission simulation” is now conceptually called “local grading”.
./runner submit
is now./runner grade
.--brief
option for local grading is removed until there is clear use case for it.--slug
option is removed.--solution-command
option is simplified to--solution
.--tc-dir
option is renamed to--output
.
New features¶
tcframe
helper script is introduced. It currently has 2 commands:tcframe build
, which compile a spec file into a runner program, andtcframe version
, which prints current tcframe version.- A summary is printed after generation/grading, which shows whether or not there are failing test cases.
- It is now possible to specify the literal output for sample test cases, by calling
Output()
insideSampleTestCaseX()
. BeforeTestCase()
to complement the newAfterTestCase()
, which can be used to initialize input variables before each test case.- For problems with subtasks,
Constraints()
can be used to specify global constraints that apply to every subtask. - In ICPC-style multiple test cases in a file problems, it is now possible to specify a prefix that will be prepended to every output, by calling
OutputPrefix()
(e.g.OutputPrefix("Case #%d ");
).
Enhancements¶
- Maximum X for
TestGroupX()
,SubtaskX()
(and the newSampleTestCaseX()
) is now 25. - If there are errors in I/O format, previously the error was shown in every test case, resulting in spammy output. Now, it is reported only once before the test cases are evaluated.
Bugfixes¶
- When using multiple test groups in ICPC-style multiple test cases in a file problems, it was erroneously required to call
assignToSubtasks({-1})
. Now, it is not required. - In e.g. this input segment
LINE(A % SIZE(3), B)
, whenB
is not a supported type, tcframe reported the error asVariable type of `%` unsatisfied...
due to a tokenization bug. It is now fixed.
Project development¶
- Repository moved to https://github.com/tcframe/tcframe.
- (Almost) every class now lives on its own file.
- Rewrite almost everything with better testability in mind. Now, we have decent unit tests.
- Use Google Test and Google Mock for unit tests.
- Add basic end-to-end tests for generation and local grading.
MIGRATION GUIDE¶
First, “install” the tcframe
CLI utility; see Installation for more details.
Then, apply the following for each runner.cpp
you want to migrate.
spec.cpp¶
Rename
runner.cpp
tospec.cpp
.Include
<tcframe/spec.hpp>
instead of"tcframe/runner.hpp"
.Completely remove
main()
function.Change the following two classes
class Problem : public BaseProblem {}; class Generator : public BaseGenerator<Problem> {};
to:
class ProblemSpec : public BaseProblemSpec {}; class TestSpec : public BaseTestSpec<ProblemSpec> {};
ProblemSpec¶
Remove
setSlug()
fromConfig()
. The slug is now inferred from the containing (problem package) directory. See Problem package for more details.Change the following:
void Config() { setMultipleTestCasesCount(T); setTimeLimit(2); setMemoryLimit(64); }
to:
void MultipleTestCasesConfig() { Counter(T); } void GradingConfig() { TimeLimit(2); MemoryLimit(64); }
TestSpec¶
- Completely remove
Config()
– the options in it should now be specified via command-line options instead. - Change
assignToSubtasks()
toSubtasks()
. - Change
FinalizeInput()
toAfterTestCase()
. - Split
SampleTestCases()
into multipleSampleTestCaseX()
. See Test cases for more details.
After migration¶
You should now be able to run tcframe build
to compile your new spec file into runner program.
The following are new in 1.0.0 that are recommended to do:
- Put all input variable initializations in
BeforeTestCase()
instead of repeating them in private helper methods. See Test case lifecycle for more details. - Put all global problem constraints in
Constraints()
instead of repeating them in allSubtaskX()
s, if your problem has subtasks. - Include
Output()
in sample test case definitions, so that you are sure you are typing the output correctly in the problem statement by only looking at the spec file (no need to check with the actual produced output file).
0.7.0¶
March 9, 2016
New features¶
- Allow omitting
OutputFormat()
and disable output format checking. - Support jagged vector as the last input variable in a
LINES()
segment.
Project development¶
- Use shields.io for service badges.
- Restructure documentation based on https://jacobian.org/writing/great-documentation/.
0.6.0¶
February 8, 2016
BREAKING CHANGES¶
- Rename
--porcelain
to--brief
.
New features¶
- Support vector of any length as input/output format.
Project development¶
- Ignore build files in .gitignore.
0.5.0¶
August 4, 2015
New features¶
- Implement simple random number generator convenient wrapper.
- Support ICPC-style problem (multiple test cases per file).
Project development¶
- Change code coverage service from Coveralls to Codecov.
- Add .gitignore.
0.4.0¶
June 28, 2015
Focusing on submission simulation feature and code refactor.
New features¶
- Submission simulation feature. One can test submitting solution without online judge.
- Time limit + memory limit for submission simulation. Uses
ulimit
.
Bugfixes¶
- Porcelain output in submission feature sometimes always true.
- Solution/submission killed by signal prints the signal message in wrong place.
0.3.0¶
March 29, 2015
Focusing on output variables/format and clearer docs.
New features¶
- Support output variables and format.
- I/O format methods are now called before every test case, in preparation for supporting more complex formats.
- Lower down GCC version. Now the minimum version is 4.7.
Project development¶
- Apply MIT license.
- Add quite neat API reference.
0.2.0¶
March 13, 2015
This version contains most of the functionalities required for generating test cases in real world.
New features¶
- Support scalar variables of types other than
int
(char
,long long
,std::string
, etc.). - Support vector and matrix variables.
- Support for lines and grid segments.
- Implement convenience macros for specifying I/O segments.
- Support sample test cases as literal lines of strings.
- Check and report invalid input format.
- Check and report failed solution execution.
- Add intermediate method that can modify input variables before being output.
- Increase limit of subtasks and test groups to 10.
Project development¶
- Host documentation at Read the Docs.
- Change build system to CMake.
- Change extensions of header files to .hpp.
- Add code coverage reporting using Coveralls.io.
0.1.0¶
February 8, 2015
Initial prototype version. This version contains only the core functionalities of the framework.
Initial features¶
- Can declare input variables. Only integers are supported at the moment.
- Can specify input format. Only single-line variables are supported at the moment.
- Can specify constraints, with or without subtasks.
- Can specify test cases, with or without test groups. Sample test cases are not supported yet.
- Can check each test case whether it satisfies the constraints/subtasks it is assigned to.
- Can generate input files.
- Can run solution on the generated input files for producing output files.