プログラムを書かずにプログラムコンテストを解いてみよう回

2015/8/2 に行われた YUHA presents C88 謎解き×競技プログラミング 『ある勇者の物語』 は謎解きとプログラムコンテストが組み合わさってできたコンテストです。
これ、ざっくり言うと前半の問題 A-E を解くプログラムを使って問題 F を解き、次に問題 G-I を解くプログラムを使って J を解く、というシステムになっているのですが、殊に前半部分は全くプログラムを書かなくても問題 F が解けるのではないか、ということでやってみました。

問題 F

問題文
入力用のデータファイルと何か枠が与えられるので、これをヒントに解きましょう。

α

解き方は分かると思うので、素直に手作業で解きましょう。数字が入っている枠が2文字目なので入力の2行目

BEGINNING OF RACCOON

だけ解ければいいです。その部分の答えは 4=R。

β

βは入力データすら見る必要がありません。出力が SEN か GO で対応する枠が 2 文字構成なので GO です。

γ

γはちょっと面倒ですが、出力が辞書順ということなので、まずは正直者かどうかを気にせず辞書順に名前を並べてみましょう。

CRISTO
HUNK
MARA
MCGORE
NARA
PRIMADONNA
TALOON
ZOMA

その上で枠を見ると、上から順に 6 文字、4 文字、4 文字、6 文字の構成になっているようです。上記のリストの部分列でその条件に当てはまるのは

CRISTO
HUNK
MARA
MCGORE

CRISTO
HUNK
NARA
TALOON

CRISTO
MARA
NARA
TALOON

の 3 パターンしかありません。ここで確定するのは CRISTO が正直者だということです。
では次に各人の発言を見てみましょう。すると正直者と確定している CRISTO が「HUNK は嘘つき」と言っているので、1 番目、2 番目のパターンはありえないということが分かります。ということで文字の対応は 0=A, 1=L, 6=T, 8=M となります。

δ

δの枠を見ると 3 文字、入力データの最後を見ると出発点が G、聖剣が H ということが分かっているので、移動形式は G→H→?→G、もしくは G→?→H→G のいずれかとなります。つまり、G と H の両方につながっている島の中で、辞書順で先頭になるものを探れば良いのです。
まずは両方に繋がっているという条件でデータを探ると I と J が候補に残ることが分かります。なので辞書順で若い I を選んで 2=G, 7=H, 5=I が確定します。

ε

この入力ファイルは普通に(人出で)処理するのは無理があります。が、最後の問題部分をよく見ると NEWS が書かれているだけなので、漢字部分をすっ飛ばしてこのアルファベットが入っている行だけ抜き出しましょう。
そしてアルファベット26文字のリストを用意し、矢印の方向に注意して候補に "出てこなかった" ものを消していくと S が残ります。

今までで分かった数字と文字の対応を並べると
ALGORITHMS
となります。

その他

感想

今ひとつ納得行かない感じがする。周りの人たち(チーム内外)が凄い人だらけなので「あー、ここまでしかできなかったか」感があるけど、随分初期ハードルが高いイメージ。ちなみに初期ハードルが高いランキングは 車(2010)＞Endo(2007)＞今回>>その他。
ハードルが高いイメージなのはいくつか理由があって、(1) 言語(GCC)がかなり難解、(2)シミュレータ実装が結構ヘビー、(3)GCC上でAI実装、(4)Spec があやふや、あたりが強い。
(4) に関しては、「発見された過去の資料」と「今回のコンテスト用の制限」が混ざってしまう事、微妙にコーナーケースに言及がない事、コンテストの最中結構頻繁に Update がある事、などが辛かった。Full Round でも一人プレイしか想定しない事って書かれてましたっけ?

ということで今回は私自身の好みとかけ離れた問題設定な事も相まって、過去参加した中で最下位なくらいな評価をしてしまう。(ちなみに Lambda-the-Gathering は参加以前に投げた。) どうも私は「正解」があるのが好きなようだ。

反省点とか

最悪、シミュレータは無くても良かったんじゃないかなー。Asumis コンパイラとかをもう少し早めに作ればよかった気がする。理想としてはコンパイル前の言語がシミュレータを書く言語かそのサブセットになっている感じだとデバグとか色々楽だったと思う。実際、コンパイル後のコードを Web の公式シミュレータに突っ込んだらエラーが出る…とか結構頻繁にあったし。

ざっくり日記

1日目 (21:00-24:00)

取り敢えず全員でザッと問題を読んで、分かる部分、分からない部分をシェアして解散。
家に帰ってリポジトリを見たら GCC VM のインタプリタがガシガシできてきていることに感動する。
折角なのでザックリとシミュレータ用の枠だけでも作っておくか…とクラスとかザックリ interface とかを作って寝る。

2日目

@nodchip さんが C++ 実装の似非 Lambda-Man を実装するっぽいので、昨日作っておいた枠を利用してシステムも作ってもらう。
私は暇なので何となく必要になりそうな GHC インタプリタをザックリ書いておくことに。(似非 Lambda-Man や似非 ghost は GCC/GHC を利用しない。)
@tzik さんと @ysks さんは GCC が分かりそうなので、拡張 GCC (チーム内では GDB と読んでいたが、G++ と名付けるべきだったのでは…？) を GCC に変換する translator を書きつつ GDB で関数定義し、ショボ AI を作る。

3日目

この日は TOEIC があったため、私は遅刻して参加。

@ysks さんがいつの間にか Lisp っぽい言語→GDB のコンパイラを作っていたらしいので、今後はこの言語 (Asumis と命名) を使って AI を書くことに。
@ysks さんと @tzik さんは Asumis で AI を実装していく担当。たまにコンパイラに新しい機能を追加していっている。
@nodchip さんは相変わらず似非 Lambda-Man を(C++ のまま)更新していく。
私は Asumis コンパイラをメンテしていくだけ。

4日目 (-21:00)

基本的には昨日とやっていることは同じ。最終的に @nodchip さんが C++ 実装した手法を @ysks さんが Asumis に手動変換し、コンパイルしたものを提出。

反省点

  • 異なるプログラムを連結させる場合は全入出力をファイル化して、問題ごとに纏めておくべきだった。このシステムができたのは 60h くらい経った頃。遅すぎる。
  • 1 問の中は並列化するけど、問題ごとに見れば 1 問 1 問順に解いていく形だったので、CPU がネックになっている問題を解いている最中はネットワークが空いていた。他の非力マシンを使ってでも解いていくべきだったかもしれない。
  • どうせ 5 分ギリギリ (4'30" とか) に解けることなんてそうそう無いんだから 1 問あたりの制限時間は 2-3 min にしておくべきだったと思う。
  • 自分たちのチームだけでも状況を常に把握できるスクリプトというかそんなの欲しい。大きなモニタに映せるとモチベーションアップできる。
  • 少しでも test 書けるようにはしたほうが良かった気がする。問題解くルーチンは C++ で書くのがチーム内で確定しつつあるっぽいから class だけ作るといいかも。ファイルを分けるのが難しいかもしれない。

技術的に感心した事

この辺はまた使えるなー、他のチームとは違うかもなーというポイントを幾つか。大体 @tzik さんの作品。

  • ソルバーの詳細は @nodchip さんの blog 参照
  • HTTP Request は全部 wget 経由。標準入力を POST して返ってきた Body を標準出力に出す bash を作成。
    • path と同じ名前のシンボリックリンクを作って path の違いを吸収させる。
    • 変な status code だったら body を標準エラーに吐いた上で retry する…という形で 5 req / 20 sec をクリア。
  • 半自動化 script (bash) は 62h 経った頃に作成。timeout コマンドを利用して 5 min の時間制限も確認。
  • 終盤変な挙動が見られたが、入出力セットなどから @tzik さんが解析し、ソルバーと全体を回す python の両方にバグが有るのを発見、デバグ。その頃、ソルバーを実質一人で作ってた @nodchip さんは所用のため帰っていたのでした。

ざっとやってた流れ

1日目

  • 開始時間。問題を読む読む。tfold よくわからない…。@tzik さんが問題文の概訳を書いてくれてた。
  • @nodchip さんがソルバーを書き出す。まずは fold 無視。
  • wget を直接叩いたりしながらサーバとのやりとりを確認。/eval しちゃダメ。
  • ソルバーv0.1 完成。完成後に入力フォーマットを言われ、テストデータ作成プログラムを書く。
  • この辺で wget wrapper が作られている。auth token がハードコードされてるから便利。
  • 問題状況を確認するために spreadsheet 作成。
  • /train で作った小さなケースで確認。計算時間的には 10 くらいが限界じゃないかなーくらい。
  • tfold の意味がようやく分かる。
  • 結局 lightning では size 3,4,5 だけ /guess して 120 点。

2 日目

  • 昨日 /eval → ソルバー(シングル版) → /guess のやりとりが面倒だったので python で wrap する。
  • fold や tfold の対応が実装される。
  • ついでに mismatch だった場合に反例を付け加えてソルバー再起動する形を作る。夕方。
  • eval に渡す値を 256 個から 512 個へ倍増。1 問あたり /eval /eval /guess の 3 request 以上になる。
  • @nodchip さんが高速化を頑張ってるので、そこにつけ込んで得点を取るタンポポワークを淡々とこなす。5 req/20 sec 対策のため手動でやっている。

3 日目

  • @nodchip さんは並列化のために親子プロセスを分け、@tzik さんは wrapper を並列化させる。
  • その間私は single 版で淡々と得点を取るタンポポワーク。そろそろ全問題チャレンジできるか不安になり始める。
  • 並列化システムでデバグがしにくくなる。I/O の全ログを取るシステムをようやく作る。
  • CPU がネックになる問題を解いてる隙を突いて自動化システムを作成する。
  • 19:00 @nodchip さん帰宅。
  • 20:00 @tzik さん、解を見つけられなかったログからフィードバック部分にバグを発見＆修正。
  • 23:00 @tzik さん、ソルバー周りでバグ発見＆修正。この時点になってようやくソルバーのコードを真っ当に見始めている。
  • 24:00 半自動化システムに残り問題の情報を与えて帰宅。

4 日目

  • 8:00 に起きて進み具合を確認。ついでに家マシンでちょっとチャレンジさせて 2 点増やすなど。
  • 9:30 何か form に色々入力する。ここでようやく auth token がどこから取得できるか知る。