Hello, codeforces!

I have created a tool for testing interactive problems. If you do not know what it is, I recommend you to read Interactive Problems Guide before/instead of reading this blog. It is important to understand that this tool does not help, in any way, to solve interactive (and all other types of) problems, where by "solve" I mean "come up with the solution". Today's June Lunchtime introduced an interactive problem called XOR, The Detective, where I used my tool and it helped me to debug my solution, so I would like to use this chance to show the tool in work. With all of this out of the way, let's begin.

Debugging interactive solutions in general

I can't say about everyone, but for me personally debugging a solution to an interactive problem is much harder than to a non-interactive one. First of all, basic testing on samples is already non-trivial: while usually I copy-paste the sample into a file, which I then read from, it does not work this way with interactive problems. I don't know which queries my solution is going to ask, and hence what to respond; so I can't write all the answers into the file, as I don't know them in advance. And even if I have tested the solution by manually entering the correct responses, and then I want to test it on the same test again (say, I fixed a minor bug), I cannot simply select all text and paste it into the input file, because I need to separate the queries from the responses.

Moreover, calculating the responses itself requires visualizing things in my head or calculating xors or something, which takes time and efforts.

So what one usually does to (stress-)test an interactive problem is the following: comment the parts of the code which read stuff and replace them by internally calculating the answer with some chosen input. For example, instead of:

int ask(int x) {
    cout << "? " << x << endl;
    int res;
    cin >> res;
    return res;
}

one can use something like:

int ask(int x) {
//  cout << "? " << x << endl;
//  int res;
//  cin >> res;
//  return res;
    return calculate_answer(x);
}

If one doesn't want to comment/uncomment stuff before each submission, they can use macros, for example:

int ask(int x) {
#ifdef TEST
    return calculate_answer(x);
#else
    cout << "? " << x << endl;
    int res;
    cin >> res;
    return res;
#endif
}

Then the only change that needs to be done before submission is commenting the line with #define TEST (or even nothing, if you compile your code with -DTEST).

Personally I like this way, because it is quite fast, convenient, and automatically allows you to use internal implemented stuff when answering a query (for example, if your solution calculates the depth of every vertex in a rooted tree anyway, you can use it to return the distance between two vertices).

So what does this tool do?

The tool works in the following way: you write an interactor and then run something like interact ./solution ./interactor, where solution and interactor are your executables. Some advantages in comparison with the first method:

• You don't need to change your code before submission;
• Usually it is easier and faster to write the interactor from scratch (arguable, but it is certainly almost never longer or more difficult);
• You see the colored interaction protocol, where it is also easy to see which line was printed by which program.

For example, in the problem I mentioned, when I finished implementing my solution, to test it, I wrote the following simple interactor:

#include <bits/stdc++.h>

using namespace std;

inline int nxt() {
	int x;
	cin >> x;
	return x;
}

const int L = 29;

void interact() {
	int q = 30;
	cout << q << endl;
	int a = 0, b = 0;
	for (int i = 0; i < L; ++i) {
		a |= (rand() % 2) << i;
		b |= (rand() % 2) << i;
	}
	if (a > b) {
		swap(a, b);
	}
	++q;
	while (q--) {
		string type;
		cin >> type;
		if (type == "?") {
			int x = nxt();
			assert(x < (1 << (L + 1)));
			cout << ((a + x) ^ (b + x)) << endl;
		} else if (type == "!") {
			int ga = nxt(), gb = nxt();
			if (ga == a && gb == b) {
				return;
			}
			cerr << "wrong, I guessed " << bitset<L>(a) << " and " << bitset<L>(b) << ", got " << bitset<L>(ga) << " and " << bitset<L>(gb) << "\n";
			exit(1);
		} else {
			cerr << "expected ?/!, got " << type << "\n";
			exit(3);
		}
	}
	cerr << "qle\n";
	exit(2);
}

int main() {
	int t = 10;
	cout << t << endl;
	while (t--) {
		interact();
	}

	return 0;
}

When I ran interact ./qwe ./int, I saw this:

Because of this report, I found that my code didn't manage to properly restore the bits where two numbers differ, so I knew which part of my code was faulty. And indeed, after fixing a bug I got this:

After I submitted my code, it passed all the tests.

Installation and usage

The script can be downloaded from my github. To use it, one simply runs python3 interact.py <args>. It is probably more convenient to setup the following workflow, though:

• Create a directory for such scripts (optional);
• Move the script in such a directory (or in any other);
• If you use Linux, you may make this file executable using chmod +x interact.py;
• If you use Linux + Terminal, add the following line in your .bashrc or .zshrc: alias interact="python3 <path-to-script> --color". In my case, it is alias interact="$HOME/misc/interact.py --color" (I omit python3 because I made the script executable). To use it immediately after this, you may need to relaunch the terminal or run source ~/.bashrc (source ~/.zshrc and similar);
• If you use Windows, you may want to add the directory containing this script in the path variable. Probably, you also need something to make the script executable, I don't know anything about this.

After these steps you should be able to run the script from anywhere using the interact command. How to use it, though?

If you run interact -h you will see the following message:

usage: interact.py [-h] [-c] [--no-stderr] [--hang-timeout HANG_TIMEOUT] <solution exec> <interactor exec>

Make two programs interact with each other.

positional arguments:
  <solution exec>       Executable file of the solution to test
  <interactor exec>     Executable file of the interactor to test your solution against.

optional arguments:
  -h, --help            show this help message and exit
  -c, --color           Colored frames
  --no-stderr           Disable stderr printing
  --hang-timeout HANG_TIMEOUT
                        The number of seconds to wait for the solution to exit after the interactor has finished

I think it is self-explanatory. One note: you need the solution and interactor executables to be single-file commands. For example, if you write the solution in python and run it with python3 sol.py, you can't specify this two words command as <solution exec>. It is easy to fix, though; maybe I'll do it.

I haven't tested it much, so feel free to report bugs or something. I also want to emphasize that this tool doesn't do anything useful except neat visualization of the interacting process; and is probably not going to be in need of frequently. Also, as far as I remember, this script should not require any additional libraries, but if it does, just install what it requires.