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 . When you enter a number, "<" or " \ geq $" will be returned, so ask for an answer based on the result and output "! Correct number".

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.

image.png

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

How to test interactive problems in competitive programming (using mkfifo and coloring output)
How to test each version of IE using Selenium in modan.IE (VM)
How to use Google Test in C
How to use is and == in Python
[Python] How to name table data and output it in csv (to_csv method)
How to count the number of elements in Django and output to a template
How to generate permutations in Python and C ++
How to get help in an interactive shell
How to output "Ketsumaimo" as standard output in Python
How to write async and await in Vue.js
How to plot autocorrelation and partial autocorrelation in python
How to unit test a function containing the current time using freezegun in python
20th Offline Real-time How to Write Problems in Python
I tried using google test and CMake in C
How to define Decorator and Decomaker in one function
How to install Google Test / Google Mock in Visual Studio 2019
How to eliminate garbled characters in matplotlib output image
How to make an interactive CLI tool in Golang
How to right click using keyboard input in RPA?
[Python] How to sort dict in list and instance in list
How to exit when using Python in Terminal (Mac)
How to use Decorator in Django and how to make it
How to retrieve multiple arrays using slice in python.
How to execute a command using subprocess in Python
Output a binary dump in binary and revert to a binary file
[Python] How to output the list values in order
How to get RGB and HSV histograms in OpenCV
Try to make it using GUI and PyQt in Python
How to output a document in pdf format with Sphinx
How to swap elements in an array in Python, and how to reverse an array.
How to use pyenv and pyenv-virtualenv in your own way
[Introduction to Udemy Python 3 + Application] 36. How to use In and Not
How to add new data (lines and plots) using matplotlib
How to create and use static / dynamic libraries in C
How to generate a query using the IN operator in Django
I tried programming the chi-square test in Python and Java.
Comparison of how to use higher-order functions in Python 2 and 3
How to get all the keys and values in the dictionary
[Blender] How to handle mouse and keyboard events in Blender scripts
[TF] How to load / save Model and Parameter in Keras
13th Offline Real-time How to Solve Writing Problems in Python
How to execute external shell scripts and commands in python
How to create dataframes and mess with elements in pandas
How to log in to AtCoder with Python and submit automatically
[Python] How to scrape a local html file and output it as CSV using Beautiful Soup