How to test Interactive problems (using mkfifo and colorful output)

Правка en1, от recuraki, 2020-12-31 14:51:08

Interactive problems are rare problems in competitive programming. I think that interactive problems are hard to solve for many guys. Because, testing for your solution is too hard. When testing interactivity, it is necessary to understand the stdin/stdout on your system. In this article, we will cover the following topics,

  • Basic code for interactive problems. How to do printf debugging. How to do testing by sample file.
  • The mkfifo that you often see in CodeForces user articles. mkfifo does not work on WSL1 as it is, but we will make it work on WSL1 on Windows.
  • Colorful Result
  • (option) Use zsh + coproc to test without generating intermediate files.
  • The following examples are all in Python, but will work equally well in C++.

Similar articles can be found below.

eku's article Gassa's tool These two are introduction to useful tools (github) for interactive problems.

pikomikan's article The approach is similar to this article.

article by bartkaw This article describes how to call a solution function directly from an interactor program.

Terminology

In this article, we call it as follows

  • Solution: the program to submit
  • Interactor: the program that responds to the submitted program.

Preparation: Problems and examples to work with

This article use CodeForces problem for describing. It is a simple number guessing game. Guess the number $$$0 \leq n \leq 10^5$$$. When you enter a number(Solution send a number to Interactor), Interactor will return "<" or "$$$\geq$$$". You can use the result to find n(target number) and output "! n is output.

In many case, you have to write the Interactor for yourself. However, many interactive problems are simple to implement. (Maybe)

Implementing an interactor

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)

Implementing the solution

You can also use CodeForces example.

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 to a Solution

In some CodeForces posts, it is suggested to use mkfifo fifo; (. /solution < fifo) | (. /interactor > fifo) for Interactive problem testing. If you implement the Interactor and the Solution in separate code, the concept is the same in this article. Usually, when we run a single program, STDIN is sent to you program by input() and the print() output is sent to us (our terminal) as stdout. This is shown in the left figure below.

When testing the solution, we will connect the interactors and the stdin/stdout of the solution to each other to make sure it works well as the right figure above.

(Windows only) Problems using mkfifo

CodeForces and some google results articles use mkfifo, but when I try to run it on Windows WSL1 ubuntu, I get the following.

$ mkfifo fifo; (python3 49490_interactor.py < fifo) | (python3 49490_sol.py > fifo)            
mkfifo: > cannot create fifo 'fifo': Operation not permitted
// Same result when running as sudo(root)
````

Windows WSL has restrictions on where you can mkfifo (this command create a pipe file), so you can do this command with file path to `/tmp` or `/var/tmp` as following.

``shell
$ rm /tmp/fifo && mkfifo /tmp/fifo && (python3 49490_sol.py < /tmp/fifo) | python3 49490_interactor.py > /tmp/fifo
(Nothing is printed out. But the error is gone.)
````

# Using mkfifo and duplicating standard output
You got it! You can run the above command with mkfifo. But you won't know whether it succeeded or failed! How to solve it ?  This is because all STDOUT of the Interactor has been `moved (redirected) ` to the Solution by pipe(|) and redirect(<>) , and all STDOUT of the Solution has been moved to the Interactor. So you cannot see nothing output.

So you should use the shell feature `>&`. This allows you to `copy' the output. The image looks like this

! [image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/30938/4260e675-2cfe-e3b6-0f33-498c70411531.png)

Even if you use pipes or redirects for copying from STDOUT to STDERR, STDERR will still be displayed to the user (by default). `a>&b` can copy specify a file descriptor with `a=from, b=to`.
> file descriptor numbers
> 0: stdin
> 1: stdout
> 2: stderr

````shell
$ 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! You will see that each command has a `1>&2`, which means that STDOUT of both programs will be printed to STDOUT and STDERR(because STDOUT is mirrored to STDERR). Finally, you can see both conversations.

# How to do printf debug

Although it is possible to debug by viewing both conversations. Sometime, you want to see more detailed debug information Solution and Interactor. For example, you want to do the following printf debugging.

- In the Solution, we want to print the mid value every loop
- In the Interactor, we want to print the input number and answer number.

However, if you simply use print(), the debugging message will also be send to the other program, causing input errors in both programs. So, we will use STDERR. Let's try it.

while l ! = r: mid = (l+r+1)//2 print("new mid:", mid, file=sys.stderr) # NEW! ``!

If you are using C++, use std::cerr instead of std::cin.

Example run with ``shell:stderr'' output.

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 < ... (snip)... new mid: 11 11 < ! 10 OK! ````

As you can see, the user can see "new mid:11", but it is seen by only you, it wasn't seeng by the Interactor.

Automating the test

Next, we'll show you how to judge AC or WA' andreplace data in the Interactor'.

Judging AC or WA by shell

Use the return value of the Interactor program. In an interactor, you 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 $$$?
 > 0 should appear

If you connect commands with a pipe, shell will return only the return value of the command you executed for the last command. That is, the return value of python3 49490_interactor.py goes into $?.

Now, to make sure the return value is working properly, we will do WA manually.

$ python3 49490_interactor.py
! 11111
NG!
$$$ echo $$$?
20
20 ````

As you can see, the return value has changed(not 0). The success or failure of the result can be recognized by the shell or external programs by using this.

## Implementing the prepared test set
Now, when you solve problems, you want to use various data sets, and it is hard to rewrite the course code of the interactors every testcase. The Interactor need to be able to fetch testcase from the outside. There are several approaches to this, typically 1. enchance the Interactor and input data at program execution time 2. the Interacter open and read an external file. 

In this case, we will use `1`, which requires some change of the Interactor. First it will read lines of testcase as shown below. After that, it will read 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) ```` Here is an example of how it works manually.

$ python3 49490_interactor_custom.py
DEBUG:Interactor: input new ans
23
DEBUG:Interactor: new ans = 23
20
>=
! 23
OK!
````

OK. However, how do we load the data from testcase file? Create a test file 5.in that sets the answer to 5, as follows

5 ```

To run it, do the following

rm /tmp/fifo && mkfifo /tmp/fifo && (cat 5 ; 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
(snip >= !
````

It's done! The key here is `cat 5.in ; python3 49490_sol.py`. This means that the result of cat is first input to the Interactor, and then the input of the Solution is send to the interactor.

# Appendix: Making the output easier to read(Colorful Output)
By the way, output lines are a little hard to see when debugging, so we want to make it colorful. For example, I want it to look like the following figure on the right.

<img src=https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/30938/fde11fb1-9317-3104-43fc-ad90edeca968.png width=50%><img src=https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/30938/3f139b3d-fce4-6de1-bf96-4a9237c82540.png width=33%>

This can be easily achieved by providing descriptors other than $$$0,1,2$$$. zsh and other programs allow you to send file descriptors to any command by executing `exec n>`. Write an escape sequence and commands to decorate the received string, and prepare file descriptors $$$3,4,5,6$$$ as follows.

<img src=https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/30938/116a2b9b-2a59-cb36-e508-d73d73077a15.png width=50%>
> 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 guide, run the command as follows

````shell: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
exec 6>/dev/tty

With 1>&4 2>&6 and 1>&3 2>&5, we were able to map and achieve the above output.

Appendix: Using coproc (zsh)

In zsh and bash, you can use shell functions to flexibly redirect file descriptors between processes without using mkfifo. Using coproc, you can achieve the following. This means temporary file is not necessary by pipe.

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 ok to submit with stderr out?

CodeForces is fine. https://mirror.codeforces.com/gym/101021/submission/102884952

Ref: CF Good Bye 2019 D. Strange Device

Here is an example implementation of the interactor and solution for this Interactive problem, as well as an execution example.

https://mirror.codeforces.com/contest/1270/problem/D

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])
````

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) ````

4 3 3
2 0 1 9 3 4

Link

How to get Colorful STDERR shell リダイレクトのメモ zshML: coprocについて 様々なshellでのcoproc

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en20 Английский recuraki 2020-12-31 18:48:44 0 publish (published)
en19 Английский recuraki 2020-12-31 18:47:02 92
en18 Английский recuraki 2020-12-31 18:41:49 81
en17 Английский recuraki 2020-12-31 18:34:30 198
en16 Английский recuraki 2020-12-31 17:22:41 17 Tiny change: 'ntry/57290]) and [too' -> 'ntry/57290?#comment-409348) and [too'
en15 Английский recuraki 2020-12-31 17:21:51 85
en14 Английский recuraki 2020-12-31 17:13:06 2
en13 Английский recuraki 2020-12-31 17:12:34 27 Tiny change: 'as follows\n\n> 5\n\' -> 'as follows(this file has only 1 line)\n\n> 5\n\'
en12 Английский recuraki 2020-12-31 17:11:28 3 Tiny change: ' && (cat 5 ; python3' -> ' && (cat 5.in ; python3'
en11 Английский recuraki 2020-12-31 17:10:19 297 Tiny change: 'ful STDERR(https://t' -> 'ful STDERR](https://t'
en10 Английский recuraki 2020-12-31 17:04:45 351 Tiny change: ' work on WSL1 on Windows.\n- Color' -> ' work on Windows with WSL1.\n- Color'
en9 Английский recuraki 2020-12-31 15:57:52 1163 Tiny change: '1\n~~~~~\n<spoiler' -> '1\n~~~~~\noutput:\n<spoiler'
en8 Английский recuraki 2020-12-31 15:48:06 155
en7 Английский recuraki 2020-12-31 15:40:15 36
en6 Английский recuraki 2020-12-31 15:35:41 36
en5 Английский recuraki 2020-12-31 15:34:54 41
en4 Английский recuraki 2020-12-31 15:34:10 383
en3 Английский recuraki 2020-12-31 15:27:18 26
en2 Английский recuraki 2020-12-31 15:25:28 538
en1 Английский recuraki 2020-12-31 14:51:08 14447 Initial revision (saved to drafts)