競技プログラミングのインタラクティブ問題のテストの仕方(mkfifoの利用と出力への色付け)

競技プログラミングでは稀にインタラクティブ問題が出題されます。インタラクティブ問題はテストがしにくく、手が出しにくい印象があります。
インタラクティブのテストを行う際には、プログラムのstdin/stdoutを理解する必要があります。この記事では以下の話題を扱います。

• インタラクティブ問題の手動テストのコードの書き方とprintfデバッグの仕方をします
• CodeForcesのユーザ記事でよく目にするmkfifoはWSL1上でそのままでは動きません。WindowsのWSL1でも動作させます
• 動的なテストを実現し、ファイルディスクリプタを上手く扱うことで、出力に色付けを行います
• (option) zsh + coprocを使うことで、中間ファイル生成なしのテストを実現します。
• 以下の例はすべてPythonですが、C++でも同様に動作します

類似した記事は以下のものがあり、コンパクトにまとまっています。

ekuの記事
Gassaのツール
この２つはインタラクティブ問題向けの補助ツール(github)の紹介です。

pikomikanさんの記事
アプローチは違いますが、この記事に似た視点で書かれています。

bartkawの記事
この記事ではインタラクタからソリューションを直接呼ぶ方法が述べられています。

用語

この記事では以下のように呼びます。

• ソリューション: 提出するプログラム
• インタラクタ: 提出したプログラムの応答を行うプログラム

準備: 扱う問題とサンプル

CodeForcesの問題を例にとります。
シンプルな数当てゲームです。$0 \leq n \leq 10^5$の数を当てます。数値を入力すると、"<"か"$\geq$"が返ってくるので、その結果をもとに答えを求めて"! 正解の数字"を出力します。

多くのケース場合、インタラクタは自分で書かないとなりません。が、インタラクティブ問題の多くはシンプルな実装で済むことが多いです。(要出典)

インタラクタの実装

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)

ソリューションの実装

CodeForcesの例を使ってもよいです。

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)

インタラクタとソリューションを接続する考え方

いくつかのCodeForcesのポストでは、mkfifo fifo; (./solution < fifo) | (./interactor > fifo)が紹介されています。
インタラクタとソリューションを別々のコードで実装する場合、コンセプトは同じです。通常、私たちが、単一のプログラムを実行すると、stdinの入力がinput()でプログラムに渡され、print()の出力がstdoutとして私たちに渡されます。この様子を以下の左図に示します。

ソリューションをテストする際には、インタラクタとソリューションのstdin/stdoutを互いに繋いでやり、うまく動作するかを確認します。

(Windowsのみ)mkfifoを使った問題点

CodeForcesやいくつかのgoogle結果の記事ではmkfifoが用いられていますが、WindowsのWSL ubuntuで実行しようとすると以下のようになります。

$ mkfifo fifo; (python3 49490_interactor.py < fifo) | (python3 49490_sol.py > fifo)            
mkfifo: > cannot create fifo 'fifo': Operation not permitted
// sudo(root)で実施しても同じ結果となる

WindowsのWSLではmkfifoできる場所(パイプファイルを作れる場所)の制約があり、/tmpや/var/tmpなどにこのファイルを置くことで実行可能です。

$ rm /tmp/fifo && mkfifo /tmp/fifo && (python3 49490_sol.py < /tmp/fifo) | python3 49490_interactor.py > /tmp/fifo
(なにも出力されない。だが、エラーはなくなった。)

mkfifoの利用と標準出力の複製

mkfifoで上記の例の実行をしても、成功したのか失敗したのか分かりません。これは、パイプとリダイレクトにより、インタラクタの標準出力はすべてソリューションに移動(リダイレクト)され、ソリューションの標準出力はすべてインタラクタに移動されてしまったため、それぞれの出力を見ることができないからです。

そこで、シェルの機能の>&を使います。これは、出力をコピーできるものです。イメージとしては以下のようになります。

パイプやリダイレクトを使用しても、(デフォルトでは)標準エラー出力(stderr)はユーザに表示されます。>&はa>&bとして使い、a=from, b=toのファイルディスクリプタを指定します。

ファイルディスクリプタの番号と標準入出力の対応
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!

できました！コマンドを見てみると、それぞれのコマンドに1>&2が付いており、これにより、両方のプログラムの標準出力は標準出力と同時に標準エラー出力にも出力されます。これにより、両方の会話を見ることができます。

デバッグの方法

両方の会話を見ることでデバッグは可能ですが、さらに細かい情報を見たいことがあります。例えば、以下のようなprintfデバッグをしたいとしましょう。

• ソリューションでは、毎回midの値を表示したい
• インタラクタでは入力された数値とansをprintしたい

しかし、単純にprintしてしまうと、デバッグメッセージも相手のプログラムに入力されてしまい、両プログラムで入力エラーになってしまいます。そこで、標準エラー出力を使います。それではやってみます。

ソリューションの例

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

のように、Pythonならfile=sys.stderrを入れます。C++ならば、std::cinの代わりにstd::cerrを使ってください。

stderr出力を入れた実行例

# コマンドは先ほどと同じ
$ 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!

このように、ユーザは"new mid:11"を見えますが、プログラムには渡されていません。

試験の自動化

次に、成功したかの判定とインタラクタのデータの入れ替え方を紹介します。

成功の判定

インタラクタの戻り値を利用します。インタラクタでは、成功したときreturn 0し、失敗なら0以外を返すようにしましょう。

$ 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 と出るはず

パイプでコマンドを接続した場合、shellには最後のコマンドに実行したコマンドの戻り値のみが返ります。つまり、python3 49490_interactor.pyの戻り値が$?に入ります。ここで、戻り値がちゃんと動作しているか確認するため、手動で誤った答えを送信してみます。

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

このように、戻り値が変わりました。これを用いることで、結果の成否をシェルや外部のプログラムで認識できます。

用意したテストセットの実施

さて、問題を解く際には、いろいろなデータセットを用いますが、毎回インタラクタのコースコードを書き換えるのは大変です。外部からの情報を渡せるようにします。これにはいくつかのアプローチがあり、代表的には1. インタラクタを拡張し、プログラム実行時にデータを入力する 2. 外部のファイルをopenし読み込む の2つがありますが、ここでは1を用います。

これにはインタラクタを書き換える必要があります。以下のように、最初に入力を受け付けるようにしましょう。そのあとはソリューションからの入力を受け取ります。

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)

以下に、手動での動作例を示します。

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

それでは、外部に用意したデータを読み込むにはどうすればいいでしょうか？以下のように答えを5にするテストファイル5.inを作ります。

5.in

5

実行は以下のように行います。

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!

できました！ここでのポイントは、cat 5.in ; python3 49490_sol.pyです。これにより、catの結果がまず、インタラクタに入力された後、ソリューションの入力がインタラクタに渡されます。

付録: 出力を見やすくする

ところで、デバッグしていると少し見にくいので、カラフルにしたいです。例えば、以下の右の図のようにしたいです。

これは、$0,1,2以外$のディスクリプタを用意することで簡単に実現できます。zshなどではexec n>と実行することで、ファイルディスクリプタを任意のコマンドに渡すことができます。エスケープシーケンスや受け取った文字列をデコレーションするコマンドを書き、以下のようにファイルディスクリプタ$3,4,5,6$を用意します。

> 3: Interactor Stdout > 4: Solution Stdout > 5: Interactor StdError > 6: Solution StdError > 31m:red, 32m:green > 0:stdin, 1:stdout, 2:stderr

この情報を参考にしながら、以下のようにコマンドを実行します。

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

1>&4 2>&6と1>&3 2>&5でそれぞれ、マッピングを行い、上記の出力を実現することができました。

付録: coprocの利用(zsh)

zshやbashではmkfifoを使わずに、シェルの機能でプロセス間の柔軟なファイルディスクリプタのリダイレクトなどが行えます。coprocを使うと以下のように実現できます。

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: stderrを出したまま提出しても大丈夫？

CodeForcesは大丈夫です。
https://codeforces.com/gym/101021/submission/102884952

参考: CF Good Bye 2019 D. Strange Device

このInteractive問題のインタラクタとソリューションの実装例及び、実行例を紹介します。

インタラクタ

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)

1270_d_sample.in

4 3 3
2 0 1 9 3 4

実行例

$ 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

参考

永続的に標準エラー出力に色をつける
shell リダイレクトのメモ
zshML: coprocについて
様々なshellでのcoproc