How to test interactive problems in competitive programming (using mkfifo and coloring output)
In competitive programming, interactive questions are rarely asked. Interactive questions are difficult to test and give the impression that they are hard to come by. When doing interactive testing, you need to understand the stdin/stdout of your program. This article deals with the following topics:
--How to write code for manual testing of interactive problems and how to debug printf
--The mkfifo often seen in CodeForces user articles does not work on WSL1 as it is. Works on WSL1 on Windows
――Achieve dynamic testing and handle file descriptors well to color the output
-(option) zsh + coproc is used to realize the test without intermediate file generation.
- The following examples are all Python, but they work in C ++ as well
Similar articles include the following, which are compactly organized.
eku article Gassa Tools These two are the introduction of auxiliary tools (github) for interactive problems.
Article by pikomikan The approach is different, but it is written from a similar perspective to this article.
bartkaw article This article describes how to call a solution directly from an interactor.
the term
In this article, we call it:
--Solution: Program to submit --Interactor: A program that responds to the submitted program
Preparation: Problems and samples to deal with
Take CodeForces Issues (https://codeforces.com/gym/101021/problem/1) as an example.
It's a simple number guessing game. Guess the number of $ 0 \ leq n \ leq 10 ^ 5
In many cases, you have to write the interactor yourself. , but many interactive problems often require a simple implementation. (Citation needed)
Interactor implementation
49490_interactor.py
import sys
ans, qcount = 10, 0
while qcount < 26:
qcount += 1
s = input()
if s[0] == "!":
if int(s.split(" ")[1]) == ans: print("OK!"), sys.exit(0)
else: print("NG!"), sys.exit(20)
if ans < int(s): print("<")
else: print(">=")
print("GAMEOVER!")
sys.exit(10)
Solution implementation
You can also use CodeForces Example.
49490_sol.py
l, r = 1, 10**6
while l != r:
mid = (l+r+1)//2
print(mid, flush=True)
s = input()
if s[0] == "<": r = mid - 1
else: l = mid
print("!", l, flush=True)
The idea of connecting an interactor and a solution
Some CodeForces posts have introduced mkfifo fifo; (./solution <fifo) | (./interactor> fifo).
If you implement the interactor and solution in separate code, the concept is the same. Normally, when we run a single program, the input of stdin is passed to the program with input () and the output of print () is passed to us as stdout. This is shown in the figure on the left below.
When testing the solution, connect the interactor and the solution's stdin/stdout to each other to see if it works.
(Windows only) Problems using mkfifo
CodeForces and some google results articles use mkfifo, but when I try to run it on WSL ubuntu on Windows it looks like this:
$ mkfifo fifo; (python3 49490_interactor.py < fifo) | (python3 49490_sol.py > fifo)
mkfifo: > cannot create fifo 'fifo': Operation not permitted
// sudo(root)The same result will be obtained even if it is carried out in
In WSL of Windows, there is a restriction on the place where mkfifo can be created (the place where a pipe file can be created), and it can be executed by placing this file in / tmp or/var/tmp.
$ rm /tmp/fifo && mkfifo /tmp/fifo && (python3 49490_sol.py < /tmp/fifo) | python3 49490_interactor.py > /tmp/fifo
(Nothing is output. But the error is gone.)
Use of mkfifo and replication of standard output
Even if I run the above example with mkfifo, I don't know if it succeeded or failed. This is because pipes and redirects have all the standard output of the interactor'moved (redirected)'to the solution, and all the standard output of the solution has been moved to the interactor, so you can't see each output.
Therefore, use the shell function > &. This allows you to copy the output. The image is as follows.
Even if you use pipes or redirects, the standard error output (stderr) is still visible to the user (by default). Use > & as a> & b to specify the file descriptor of a = from, b = to.
Correspondence between file descriptor numbers and standard I / O 0: stdin 1: stdout 2: stderr
$ rm /tmp/fifo && mkfifo /tmp/fifo && (python3 49490_sol.py < /tmp/fifo) 1>&2 | python3 49490_interactor.py > /tmp/fifo 1>&2
500001
<
...(snip)..
! 10
OK!
It's done! Looking at the commands, each command is marked with 1> & 2, which causes the standard output of both programs to be printed to standard error as well as standard output. This allows you to see both conversations.
How to debug
You can debug by looking at both conversations, but you may want to see more detailed information. For example, let's say you want to debug printf like this:
--In the solution, I want to display the value of mid every time --In the interactor, I want to print the input numerical value and ans
However, if you simply print it, the debug message will also be input to the other program, resulting in an input error in both programs. Therefore, use standard error output. Let's try it.
Solution example
while l != r:
mid = (l+r+1)//2
print("new mid:", mid, file=sys.stderr) # NEW!
For Python, put file = sys.stderr. For C ++, use std :: cerr instead of std :: cin.
Execution example with stderr output
#The command is the same as before
$ rm /tmp/fifo && mkfifo /tmp/fifo && (python3 49490_sol.py < /tmp/fifo) 1>&2 | python3 49490_interactor.py > /tmp/fifo 1>&2
new mid: 500001 # NEW!
500001
<
...(snip)...
new mid: 11
11
<
! 10
OK!
Thus, the user sees "new mid: 11", but it has not been passed to the program.
Exam automation
Next, I will introduce the judgment of success and how to replace the data of the interactor.
Judgment of success
Use the return value of the interactor. Interactors should return 0 on success and non-zero on failure.
$ rm /tmp/fifo && mkfifo /tmp/fifo && (python3 49490_sol.py < /tmp/fifo) 1>&2 | python3 49490_interactor.py > /tmp/fifo 1>&2
(snip)
$ echo $?
>Should come out as 0
If you connect a command with a pipe, the shell will only return the return value of the command you executed for the last command. That is, the return value of python3 49490_interactor.py will be in$?. Now, try manually sending the wrong answer to make sure the return value is working.
$ python3 49490_interactor.py
! 11111
NG!
$ echo $?
20
In this way, the return value has changed. By using this, the success or failure of the result can be recognized by the shell or an external program.
Implementation of the prepared test set
Now, when solving a problem, we use various data sets, but it is difficult to rewrite the course code of the interactor every time. Allows you to pass information from the outside. There are several approaches to this, typically 1. extending the interactor and entering data at program execution 2. opening and reading an external file, but here we use 1 I will.
This requires rewriting the interactor. Let's accept the input first as follows. After that, it receives input from the solution.
import sys
ans, qcount = 10, 0
print("DEBUG:Interactor: input new ans", file=sys.stderr)
ans = int(input())
print("DEBUG:Interactor: new ans = ", ans, file=sys.stderr)
while qcount < 26:
qcount += 1
s = input()
if s[0] == "!":
if int(s.split(" ")[1]) == ans: print("OK!"), sys.exit(0)
else: print("NG!"), sys.exit(20)
if ans < int(s): print("<")
else: print(">=")
print("GAMEOVER!")
sys.exit(10)
An example of manual operation is shown below.
python3 49490_interactor_custom.py
DEBUG:Interactor: input new ans
23
DEBUG:Interactor: new ans = 23
20
>=
! 23
OK!
Then, how can we read the data prepared externally? Create a test file 5.in with an answer of 5 as shown below.
5.in
5
Execution is as follows.
rm /tmp/fifo && mkfifo /tmp/fifo && (cat 5.in ; python3 49490_sol.py < /tmp/fifo) 1>&2 | python3 49490_interactor_custom.py > /tmp/fifo 1>&2
DEBUG:Interactor: input new ans
DEBUG:Interactor: new ans = 5
(snip)
5
>=
! 5
OK!
It's done! The point here is cat 5.in; python3 49490_sol.py. This allows the cat results to be first entered into the interactor, and then the solution input is passed to the interactor.
Appendix: Make the output easier to read
By the way, it's a little hard to see when debugging, so I want to make it colorful. For example, I want to make it look like the figure on the right below.
This can be easily achieved by preparing a descriptor of $ other than $ 0,1,2. In zsh etc., you can pass the file descriptor to any command by executing exec n>. Write a command to decorate the escape sequence and the received string, and prepare the file descriptor $ 3,4,5,6 $ as shown below.
> 3: Interactor Stdout
> 4: Solution Stdout
> 5: Interactor StdError
> 6: Solution StdError
> 31m:red, 32m:green
> 0:stdin, 1:stdout, 2:stderr
Using this information as a reference, execute the command as follows.
zsh
exec 3> >(while read line; do stdbuf -i0 -o0 -e0 echo -e "\e[01;32mInt>> $line\e[0m" 1>&2; done)
exec 4> >(while read line; do stdbuf -i0 -o0 -e0 echo -e "\e[01;32mSol<< $line\e[0m" 1>&2; done)
exec 5> >(while read line; do stdbuf -i0 -o0 -e0 echo -e "\e[01;31m IntDEBUG>> $line\e[0m" 1>&2; done)
exec 6> >(while read line; do stdbuf -i0 -o0 -e0 echo -e "\e[01;31m SolDEBUG<< $line\e[0m" 1>&2; done)
rm /tmp/fifo && mkfifo /tmp/fifo && (cat 5 ; python3 49490_sol.py < /tmp/fifo) 1>&4 2>&6 | python3 49490_interactor_custom.py > /tmp/fifo 1>&3 2>&5
exec 3>/dev/tty # erase redirect setting
exec 4>/dev/tty
exec 5>/dev/tty
exec 6>/dev/tty
We were able to achieve the above output by mapping with 1> & 4 2> & 6 and 1> & 3 2> & 5 respectively.
Appendix: Using coproc (zsh)
With zsh and bash, you can flexibly redirect file descriptors between processes with shell functions without using mkfifo. Using coproc, you can achieve the following.
exec 3> >(while read line; do stdbuf -i0 -o0 -e0 echo -e "\e[01;32mInt>> $line\e[0m" 1>&2; done)
exec 4> >(while read line; do stdbuf -i0 -o0 -e0 echo -e "\e[01;32mSol<< $line\e[0m" 1>&2; done)
exec 5> >(while read line; do stdbuf -i0 -o0 -e0 echo -e "\e[01;31m IntDEBUG>> $line\e[0m" 1>&2; done)
exec 6> >(while read line; do stdbuf -i0 -o0 -e0 echo -e "\e[01;31m SolDEBUG<< $line\e[0m" 1>&2; done)
coproc python3 49490_interactor.py 1>&3 2>&5 ; python3 49490_sol.py <&p >&p 1>&4 2>&6
Q: Is it okay to submit with stderr out?
CodeForces are ok. https://codeforces.com/gym/101021/submission/102884952
Reference: CF Good Bye 2019 D. Strange Device
We will introduce the implementation example and execution example of the interactor and solution of this Interactive problem.
https://codeforces.com/contest/1270/problem/D
Interactor
import sys
import random
n, k, m = map(int, input().split())
l = list(map(int, input().split()))
print("server: n,k,m,l",n,k,m,l,file=sys.stderr)
print(n,k)
l = list(enumerate(l))
while True:
s = list(input().split())
if s[0] == "!":
if m == int(s[1]): print("OK", file=sys.stderr), sys.exit(0)
else: print("NG", file=sys.stderr), sys.exit(-1)
elif s[0] == "?":
dat = map(int, s[1:])
buf = []
for x in dat: buf.append(l[x - 1])
buf.sort(key=lambda x: x[1])
print(buf[m-1][0]+1, buf[m-1][1])
solution
import sys
n, k = map(int, input().split())
buf = []
for i in range(1, k + 2):
query = []
for j in range(1, k + 2):
if i != j:
query.append(str(j))
print("? " + " ".join(query), flush=True)
sys.stdout.flush()
a, b = map(int, input().split())
buf.append(b)
print("! ", buf.count(max(buf)), flush=True)
sys.stdout.flush()
sys.exit(0)
1270_d_sample.in
4 3 3
2 0 1 9 3 4
Execution example
$ rm /tmp/fifo && mkfifo /tmp/fifo && (cat 1270_d_sample.in ; python3 1270_d.py < /tmp/fifo) 1>&4 2>&6 | python3 1270_d_interact.py > /tmp/fifo 1>&3 2>&5
Sol<< 4 3 3
Sol<< 2 0 1 9 3 4
Int>> 4 3
Sol<< ? 2 3 4
Int>> 4 9
Sol<< ? 1 3 4
Int>> 4 9
Sol<< ? 1 2 4
Int>> 4 9
Sol<< ? 1 2 3
Int>> 1 2
Sol<< ! 3
$ echo $?
> 0
reference
Permanently color standard error output (https://tmsanrinsha.net/post/2012/10/%E6%B0%B8%E7%B6%9A%E7%9A%84%E3%81%AB%E6%A8%99%E6%BA%96%E3%82%A8%E3%83%A9%E3%83%BC%E5%87%BA%E5%8A%9B%E3%81%AB%E8%89%B2%E3%82%92%E3%81%A4%E3%81%91%E3%82%8B%E6%9C%AA%E5%AE%8C/) Shell Redirection Note About zshML: coproc Coproc in various shells
Recommended Posts