Interactors with testlib.h

Правка en5, от PrinceOfPersia, 2015-06-10 16:34:00

Interactive problems are problems in which solution talks to the judge. For example, 100553G - Gomoku. We don't see interactive problems much in ACM-ICPC style problems. Most of them are Olympiad style(IOI and CEOI). Unfortunately using interactive in Codeforces contests is not allowed, but you can see some of them in Gym. Also Polygon handles such problems(there's a checkbox Interactive in general info of the problem). When we don't wanna handle the judge manually, we should use a code named interactor to talk to code instead of a person. With testlib.h, we can write interactors as simple as checkers and validators.

In an interactive problem, you may use also a checker. To connect this programs together(generator, validator, solution, checker and interactor), you can use teslib input streams. An input stream, is a structure that reads data from a specific file using some pre-implemented methods. Input streams you can use with testlib.h:

  1. inf: It's the input generated by generator or manually (In polygon, manual tests and output of generators, based on how the input file of the current testcase was generated).
  2. ouf: It's the output produced by the solution you're working on.
  3. ans: Output produced by your correct solution.

Also there's and input/output stream for interactive tasks named tout. It's a log file, you can write some information to it with interactor and later, check the information written in it with checker(and determine the verdict). For writing in it, you can use style of C++ cout, like tout << n << endl;.

Methods you can use for input streams(including tout):

Method What it does
char readChar() Returns current character and moves pointer one character forward.
char readChar(char c) Same as readChar() but ensures that the readCharacter is 'c'.
char readSpace() Same as readChar(' ').
void unreadChar(char c) Puts back character c to input stream.
string readToken() Reads a new token, i.e. a word that doesn't contain any whitespaces (like space, tab, EOLN and etc).
string readToken(string regex) Same as readToken() but ensures that it matches given regex.
string readWord() Same as readToken()
string readWord(string regex) Same as readToken(string regex)
long long readLong() Reads a long (long long in C/C++ and long in Java)
long long readLong(int L, int R) Same as readLong() but ensures that the value is in range [L, R] (inclusively)
int readInt(),
int readInteger()
Reads an integer (int type in both Java and C/C++)
int readInt(int L, int R),
int readInteger(L, R)
Same as readInt() but ensures that the value is in range [L, R] (inclusively)
double readReal(),
double readDouble()
Reads a double.
double readReal(double L, double R),
double readDouble(double L, double R)
Same as readReal(), readDouble() but ensures that the value is in range [L, R].
double readStrictReal(double L, double R, int minPrecision, int maxPrecision),
double readStrictDouble(double L, double R, int minPrecision, int maxPrecision)
Same as readReal(L, R), readDouble(L, R), but additionally ensures that the number of digits after decimal point is between [minPrecision, maxPrecision]. Doesn't allow exponential or any other non-standard form.
string readString(),
string readLine()
Reads a line from current position to EOLN. Moves input stream pointer to first character of new line (if exists).
string readString(string regex),
string readLine(string regex)
Same as readString() and readLine(), but ensures that the string matches given regex.
void readEoln() Reads EOLN or fails. Note that this method magically works on both Windows and Linux. On Windows it reads #13#10 and on Linux it reads #10.
void readEof() Reads EOF or fails.

Note:

Some methods have "regex" feature. It is not a full-featured regex as you may have used in many programming languages. It is a very simple version, which supports the following:

  • Set of character, e.g: [a-z] is a lowercase latin letter, [^a-z] matches anything but a lowercase latin letter.
  • Range, e.g. [a-z]{1,5} is a string of length 1 to 5 consists of only lowercase latin letter.
  • Or operator, e.g. mike|john is either mike or john.
  • Optional character, e.g. -?[1-9][0-9]{0,3} will match non-zero integers from -9999 to 9999 (note the optional minus sign).
  • Repetition, e.g. [0-9]* will match sequences (empty or non-empty) of digits, and [0-9]+ will match non-empty sequences of digits.
  • Also regarding regex, very simple greedy algorithm is used. For example, pattern [0-9]?1 will not match 1, because of greedy nature of matching.

In interactor, you read the information about the current testcase from inf, write what needs to be given to the solution you're checking and the correct solution using stdout (online), read the output produces by the solution you're checking using ouf (online), read the output produces by your correct solution using ans (online) and write log to tout if you want.

If at anytime, some with methods of input streams used in interactor goes wrong(fails), verdict will be Wrong Answer.

Also, you can determine the verdict in interactor. There are much useful methods in teslib you can use in interactors for assert-like checking, ensuring and determining the verdict. Like:

Method Description
void quit(TResult verdict, string message);
void quit(TResult verdict, const char* message);
void quitf(TResult verdict, const char* message, ...);
Finishes the interactor with a given verdict and comment.
void quitif(bool condition, TResult verdict, const char* message, ...); if condition is true then performs quitf(verdict, message, ...)
void ensuref(bool condition, const char* message, ...); An equivalent of assert. Checks that condition is true, otherwise finishes with _fail verdict. Useful for debugging interactors.|

Possible values for TResult verdict are:

Verdict testlib macro meaning
Ok _ok The output is correct, follows the output format and represents an optimal answer (if applicable in this problem).
Wrong Answer _wa The output is wrong or incorrect.
Presentation Error _pe The output doesn't follow output format specification of the task. Although, on Codeforces this verdict is being replaced by Wrong Answer since it's usually hard to distinguish Presentation Error and Wrong Answer
Partially Correct _pc(score) If there is a partial scoring in the task, this verdict should be used in situation when solution is partially correct or to give solution some number of points. Here score should be an integer between 0 and 200 where 0 represents the lowest mark (no points) and 200 represents the highest mark (maximum possible number of points)
Fail _fail This verdict means that interactor has encountered a critical internal error or that the jury's answer is incorrect or that contestant found the more optimal answer than jury. This verdict means that something wrong has happened and it requires a special investigation from jury.

If verdict determined by interactor's ok, then it will be ensured by chacker (checker which uses tout) if there's any.

How to use interactor program ?

Simple:

Windows:
interactor.exe <Input_File> <Output_File> [<Answer_File> [<Result_File> [-appes]]],
Reads test from inf (mapped to args[1]), writes result to tout (mapped to argv[2],
can be judged by checker later), reads program output from ouf (mapped to stdin),
writes output to program via stdout (use cout, printf, etc).

Linux:

./interactor.out <Input_File> <Output_File> [<Answer_File> [<Result_File> [-appes]]],
Reads test from inf (mapped to args[1]), writes result to tout (mapped to argv[2],
can be judged by checker later), reads program output from ouf (mapped to stdin),
writes output to program via stdout (use cout, printf, etc).

Sample Interactive Problem

I(judge) choose an integer in the interval [1, 109] and you should write a code to guess it. You can ask me at most 50 questions. In each question, you tell me a number in the interval [1, 109], and I tell you:

  • 1 if it is equal to answer(the chosen number), and your program should stop asking after that.
  • 0 if it is smaller than answer.
  • 2 if it is greater than answer.

Sample interactor for this problem:

Note: Like checkers and validators and generator, you should first initialize your interactor with registerInteraction(argc, argv).

Please note that in this problem, we can determine the verdict without using the correct solution and ans because we don't care about it's product. But in some problems, we'll have to compare it with the product of the correct solution using ans.

int main(int argc, char ** argv){
	registerInteraction(argc, argv);
	int n = inf.readInt();	// chosen integer
	cout << n << endl;
	cout.flush();	// to make sure output doesn't stuck in some buffer
	int left = 50;
	bool found = false;
	while(left > 0 && !found){
		left --;
		int a = ouf.readInt(1, 1000000000);	// the number you tell me
		if(a < n)
			cout << 0 << endl;
		else if(a > n)
			cout << 2 << endl;
		else
			cout << 1 << endl, found = true;
		cout.flush();
	}
	if(!found)
		quitf(_wa, "couldn't guess the number with 50 questions");
	ouf.readEof();
	quitf(_ok, "guessed the number with %d questions!", 50 - left);

}

Resources: Checkers, validators and my personal experience from reading one of MikeMirzayanov's interactors.

Теги testlib, interactive, interactor

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en8 Английский Xellos 2016-07-21 23:50:51 152 edited tout info; possibly outdated or incorrect, but I was only able to read from tout with ouf:: methods in the checker
en7 Английский PrinceOfPersia 2015-06-12 10:52:14 21 Tiny change: 'ger\n cout << n << endl;\n cout.fl' -> 'ger\n cout.fl'
en6 Английский PrinceOfPersia 2015-06-10 17:35:45 6595
en5 Английский PrinceOfPersia 2015-06-10 16:34:00 0 (published)
en4 Английский PrinceOfPersia 2015-06-10 16:31:53 20
en3 Английский PrinceOfPersia 2015-06-10 16:30:07 631
en2 Английский PrinceOfPersia 2015-06-10 16:13:28 1471
en1 Английский PrinceOfPersia 2015-06-10 14:09:52 8040 Initial revision (saved to drafts)