えびちゃんの日記

えびちゃん（競プロ）の日記です。

インタラクティブ問題のデバッグに関してなど

インタラクティブ問題は手元でのデバッグが面倒がちなので、いやだと思っている人が多そうです。 coproc というシェルの機能を使えばそこそこ簡単にできないかな？と思ったので、書いてみます。

まえおき

簡単とは言っても、以下のものは自分で書く or 生成する必要があります*1。

ジャッジについては、次のような仕様を満たしていてほしいです。

  • 入力データのファイル名をコマンド引数で受け取る
    • あるいは、ジャッジがランダムで生成してもよいです、ここはよしなに。
    • 標準入力はクエリとのやりとり用にしたいので使えません。
  • クエリを標準入力から受け取る
  • 返答を標準出力に書き出す
  • デバッグ用の出力を標準エラー出力に出してもよい
  • AC ならステータス 0 で終了、そうでなければ 1 などで終了*2
    • 要するに、return ac? 0: 1; みたいなことをしてほしい。

やります

さて、解答のプログラム ./sol とジャッジのプログラム ./judge と入力ファイル infile を用意できたとします。 このとき、次のようにできます。シェルによって違うので、各々説明します。

Bash

実行例：

bash-5.1$ coproc ./sol
[1] 27352
bash-5.1$ ./judge infile <&${COPROC[0]} >&${COPROC[1]}
AC: ok
[1]+  Done                    coproc COPROC ./sol

実行例なので出力も混ざっていますが、実際に書く必要があるのは次の部分だけです。

coproc ./sol
./judge infile <&${COPROC[0]} >&${COPROC[1]}

coproc をつけてコマンドを実行すると、標準入出力以外と入出力をやりとりするものとして開始されます（パイプと呼ばれる機構とやりとりします）。 入力先のパイプは file descriptor*3 の形で教えられ、その値は ${COPROC[1]} に入っています。出力先も同様で、${COPROC[0]} です。

file descriptor が fd のものにリダイレクトしたいときは、<&fd や >&fd の形を使えばよいです。 標準エラー出力を標準出力にまとめるときに 2>&1 というのを見たことがある人もいると思いますが、標準出力の file descriptor が 1 なので、こういう感じの書き方になっているわけですね。 標準入力は 0、標準エラー出力は 2 です。

coproc をつけて実行したコマンドにとっての入力先は ${COPROC[1]} に入っていますが、それに対して書き込む（入力を与える）コマンドにとっては ${COPROC[1]} は出力先なので、標準出力の番号に対応する 1 に値が入っていると考えるとよさそうです。若干ややこしいですね。

AC: ok は標準エラー出力に対する書き込みです。実際には、次のような内容があると便利かもしれません。

  • どういうクエリを受け取ったか
  • どういう返答をしたか
  • QLE や WA であればその詳細

Zsh

実行例：

% coproc ./sol
[1] 27741

% ./judge infile <&p >&p
[1]  + done       ./sol
AC: ok

書く必要がある部分：

coproc ./sol
./judge infile <&p >&p

こっちの方が短いですね。Zsh では、coproc で作ったコマンドに対してリダイレクトしたいときは <&p や >&p が使えるとのことなので、それを使えばよいです。 他は Bash と同様です。

そのほか

IDE とかを使っていてシェルと仲よくない人もいるらしいです？ よしなにがんばってほしいです...

あと fish-shell の人もよしなにがんばってほしいです。

そうなんだけど

github.com

oj っていうツールがあるんですが、次のようなことができます。

% oj t/r -c ./sol './judge infile'

おまけ

macOS にデフォルトで入っている Bash のバージョンは化石であることで有名です。

bash-3.2$ coproc
bash: coproc: command not found

brew install bash とかをするとよいです。

おわり

結局、ジャッジを書くのが面倒という問題からは逃れられないので困ります（これは構築などのスペシャルジャッジが必要な問題についてもそう）。 ジャッジを書くパートさえできたら、解答とジャッジのやりとりパートはわりと簡単じゃんというお話でした。

ジャッジを書くパートは面倒で、特に adaptive/adversarial な問題では、厳しく書くのは大変です。 これは、クエリのやりとりに矛盾しない入力データであれば、ジャッジ側が "後出し" できるといった問題設定のことです。

それはそれとして、interactive や reactive などの表記揺れ（表記というか表現というか）があって、どれを使うべきなんだろう〜と思っています。

*1:やっぱり面倒じゃん、解散。←？

*2:ステータスを -1 などの負数にする人がよくいますが、これは予約された値であり、よくなかった気がします。文献は見失いました。

*3:ここでは、単にファイルやパイプを特定するための表し方の一つ、くらいに認識しておけばいい気がします。