先日から、競技プログラミング「AtCoder」に挑戦しています！
↓こちらの記事でも書きましたが、B – Interactive Sortingがなかなか解けません。(^^;;
「5個を7回で並び替える」のが難しいです。。
ソートの方式を何種類か変えてみましたが、いまだに比較回数が超過しているようです。 いよいよ手詰まり状態になってきたため、実際に超過しているテストケースを使って実験したくなりました。
そこで、インタラクティブ問題を実験するためのプログラムを書いてみましたが、いろいろ勉強になりましたので、まとめてみました！
構想
便宜上、問題を出してテストする側のプログラムを「問題プログラム」、解答として提出するプログラムを「解答プログラム」と呼ぶことにします。それぞれの役割は以下の通りです。
- 標準出力で問題を出す
- 標準入力でクエリを受け取る
- クエリの結果を標準出力で返す
- 解答を標準入力で受け取って正解かどうかを判断
- 標準入力で問題を受け取る
- 標準出力でクエリを出す
- クエリの結果を標準入力として受け取る
- 計算結果を標準出力
いずれのプログラムも、クエリ関係の処理はインタラクティブ問題固有です。
あとは、問題プログラムと解答プログラムの標準入出力をパイプで繋いでやるだけです！
言うだけは簡単なのですが、実際この形でできるとシンプルで美しいですね。(^^;;
問題プログラム
B – Interactive Sortingのテストセット3: N(個数) = 5, Q(クエリ上限) = 7 の内容に従っています。
5個の並び方のパターンは 5 × 4 × 3 × 2 × 1 = 120 通りありますが、1回の実行で1種類の問題を出力するように、コマンドラインの引数に問題番号を渡すものとしました。
標準入出力を使って、クエリを受けて応答したり、解答を受けてチェックしたりするのは、解答プログラム側と同様な作りです。
お勉強も兼ねて、Pythonで書いてみました(B_question.py)。こちらに置いてあります。
解答プログラム
こちらは、B – Interactive Sortingの解答として提出するコードです。
なお、実行できる状態である必要があるので、C言語などのソースコードの場合は事前にコンパイルが必要です。
パイプライン処理
さて、問題プログラムと解答プログラムをパイプで繋ぐことを考えます。
通常のパイプを使えるか？
LinuxやMacなどのターミナル(コマンドライン)上でパイプはよく使います。
例えば、以下の通りです。
$ ls -l | grep hoge | lessこの例だと、データの流れ（ストリーム）は一方向です。
lsコマンドの標準出力を、次の grepコマンドの標準入力として渡し、さらに grepコマンドの標準出力をその次の lessコマンドの標準入力として渡します。
一方、今回の問題プログラムと解答プログラムはインタラクティブにデータをやり取りするため、上の例のようなパイプでは表現できません。
では、どうしたらよいのでしょう。
名前付きパイプを使う方法
MacやLinux上で、もう少し複雑なことができるパイプとして、名前付きパイプがあります。
以下のように生成できます。
$ mkfifo aaaそれを使って、以下のように記述してみます。
$ python B_question.py 55 < aaa | hogehoge > aaa処理フローは以下の通りです。
- 問題プログラムの標準出力(出題 or クエリへの応答)を、「|」を使って、解答プログラム(hogehoge)の標準入力に渡す
- 解答プログラムからの標準出力(クエリ or 解答)を、一旦、名前付きパイプ(aaa)に渡す
- 名前付きパイプから、問題プログラムの標準入力へ渡す
- 先頭へ戻る
こうすることで、二つのプログラムの間で標準入出力を使ってインタラクティブに通信することが可能となります！
ちなみに、以下のように tee を挟んでやると、通信内容をファイルにも落とせます。
$ python B_question.py 5 < aaa | tee Q.log | hogehoge | tee A.log > aaa以下が実行例です。 a.outはB_msort.cをコンパイルしたものです。
- 標準エラー出力(問題と解答の両方)
$ python B_question.py 5 < aaa | tee Q.log | ./a.out | tee A.log > aaa B_question: [a, b, c, d, e] = 0 1 4 3 2 B_question: Query A B Query: A < B B_question: Query A C Query: A < C B_question: Query B C Query: B < C B_question: Query D E Query: D > E B_question: Query A E Query: A < E B_question: Query B E Query: B < E B_question: Query C E Query: C > E B_question: Query C D Query: C > D B_question: Ans ABEDC B_question: Query count over... count= 8 - 解答プログラムからの標準出力
$ cat A.log ? A B ? A C ? B C ? D E ? A E ? B E ? C E ? C D ! ABEDC - 問題プログラムからの標準出力
$ cat Q.log 5 7 < < < > < < > >
UNIXの思想通り、シンプルで美しいですね！
subprocess.PIPEを使う方法
前述の方法は、シェル上で実現する方法ですが、Pythonの機能を使ってプログラム上でパイプを使う方法です。
問題プログラムと解答プログラムをそれぞれ子プロセスとしてオープンする際にパイプを指定します。
import subprocess
proc1 = subprocess.Popen(cmd1.split(), stdin=subprocess.PIPE, stdout=subprocess.PIPE)
proc2 = subprocess.Popen(cmd2.split(), stdin=subprocess.PIPE, stdout=subprocess.PIPE)実際にプロセス間通信を行う処理は以下の通りです。
# cmd1の標準出力をcmd2の標準入力へ
line = proc1.stdout.readline()
proc2.stdin.write(line)
proc2.stdin.flush()
# cmd2の標準出力をcmd1の標準入力へ
line = proc2.stdout.readline()
proc1.stdin.write(line)
proc1.stdin.flush()これをストリームが終わるまでループで回してやれば期待通りのことができました！
コードは以下に置いてあります。
まとめ
AtCoderのインタラクティブ問題 B – Interactive Sortingが解けないため、今回、テスト用のプログラムを書いてみました。問題と解答の二つのプログラムを、双方向にパイプで繋いでやると期待通りに実行することができました。双方向のパイプとしては、MacやLinuxなどの名前付きパイプを使う方法と、Pythonのsubprocessを使った方法で確認することができました。
これで、インタラクティブ問題の実験ができるようになりましたし、引き続き、最適解を求められるよう頑張ります。
最後までお読みいただきありがとうございました！
