Ninth annual ICFP Programming Contest 〜 HOMEWORK7 〜

ICFP

ちょっと前の話ですが、7/21-24ごろに
ICFPプログラミングコンテスト(http://icfpcontest.org/)
というものに今年も参加しておりました。
メンバーはいつもどおりMさん(http://d.hatena.ne.jp/nushio/)と二人です。


課題は去年、一昨年とはかなり変わって、
なにやらバイナリと、それの実行方法が与えられるので、
そのバイナリを実行して、画面の指示通りに課題をこなせば
得点がもらえるというものでした。


とりあえず、個人的な感触ですが、
この課題は
"the programming language of choice for discriminating hackers"
を決めるための課題としてはまったく不適当なのではではないかなぁと思いました。
少なくとも、今回これで選ばれた
「目利きのハッカーが選ぶ言語」
は到底認められません。


理由はいくつかあって、

  • VMの実装に利用可能な言語が極めて限られる

VMの機能が極めてミニマムなのに、その上に乗せられるプログラムがミニマムではない。
たとえば、論理演算がNANDしかない、
減算が無い、負の即値をロードできない、
これらの理由により、計算に必要なステップ数が増大し、
しかも、その上で走るプログラムが重いので、
必然的にVMの実行性能が要求される。
C言語で書かれたVMですら現在の標準的PCで動かした場合に
満足できる速度では無いので、
その一桁倍遅くなるような言語でVMを書いたときですら
使い物にならない。
実際のところ、うちのチームは最初にHaskellで書いたところ、
あとで書いたC++のVMの3〜5分の1の性能だったわけですが、
これでも重くて重くて使い物にならない。
Haskellですらこれなので、
Cの十倍、百倍重い言語は言わずもがな。
選択可能な言語は、
C/C++,D,OCaml/SMLぐらいに限られてしまうのではないか？

  • VMの実装が簡単かつ短時間

普通に書けばVMは一時間もあれば書けてしまう上に、内容も取るに足らない。
ここで言語間の差異は出ない。

おそらく、絶対必要なのはあみだ(後述)ソルバーのみ。
あとは、BALANCEのレジスタ割付をプログラムにやらせれば楽、程度。

  • 全体に渡って、実装が軽すぎる

VMはC++で100行クラス。
あみだはそれ以下。
これでは言語の能力差もなにもない。


逆に考えて、
たとえば、今年、Haskellじゃない言語が選ばれたとしましょう。
だとすると、例年言われていた、
Haskellが優秀なのか、Haskell使いが優秀なのか、
問題に終止符が打たれるわけなので、
つまり、Haskell使いが優秀なんではなくて、
Haskellが優秀だったということです。
そういうわけで、それはそれで見ものではあります。


とまぁ、こんなことをいうものの、
課題自体はパズルで楽しかったのですけどね。
しかし、なんといいますか、こう、
答えがあって、私たちがこう、答えを見つけて、よくやったねえ、
（とはあんまりですが…コードネームHOMEWORK7ですからね…）
というのは期待していたのと違うというか、
まぁ、ぶっちゃけて言えば、
私はこういうICPC的なのはそんなに得意じゃないので
もっというと、
今回のは人手があればあるほど有利になるような問題なので、
もとより二人で参加しようとしていた私たちには
勝ち目が無いというか、
旧来のICFPなら、
何人でもかかってこいや、人海戦術で勝てるもんなら勝ってみろ、
といわんばかりの懐の深さがあったのですが、
今回は本当にそれで勝ててしまうので、
人数制限が付いてしまって、そこも個人的に残念だったなぁと思います。


以下、せっかくなので、私たちの挑戦記録でも書いておきます。
参加していない人も、マテリアルは公開されているので、
今からやってみるのもいいかもしれません。
最低3日は遊べると思いますので…。

  • 22日1時

スタート

  • 1時過ぎ

HaskellでVMを書き始める。M氏手持ち無沙汰。
まだ何をやればいいのかさっぱり分かっておらず。

  • 2時過ぎ

VM完成
パスコードが通る。

  • 2時半ごろ

VMが遅いとの専らのうわさ。
実行したVMはわけの分からないものを吐き出し続けている。

  • 3時ごろ

30分かかってVMの生成物を収集完了。
いつ終わるかとも知れず不安と戦った。

  • 3時半ごろ

生成されたものは、VMのバイナリで最初に渡されたものは
自己解凍プログラムだと思われたので実行。
バイナリの編集作業に戸惑う。

  • 同刻

動かず。ここまで動いてVMが間違っているわけがない。
バイナリを見ると、0D0A…。アーッ。

  • 同刻

出力モードを切り替えて再ダンプ。
再び30分待つ。

  • 4時ごろ

ついに生成されたバイナリが動作した。
UMIXとかいうOSもどきのログイン画面が表示された。
なんじゃこりゃー。
まさかこんなしょぼい仕様のVMで
こんな本格的なプログラムを動かされるとは…。

  • 4時半ごろ

230点回収完了。
M氏就寝。

  • 5時ごろ

BASICでパスワードクラック。
コードは出来たのに、なぜかだれのパスも取れない。
サフィックスが無い人のパスは取れた。

  • 6時ごろ

ADVENTUREを動かしてみる。

  • 7時ごろ

2Dを動かしてみる。

  • 8時ごろ

M氏合流。今回の課題の趣旨を伝える。
BASICは後ろにつける数字二つはローマ数字なのでは？

  • 8時半頃

BASICをコンパイルするたびに数分かかる現状に辟易して、
ついにHaskellVMを捨てる決意をする。

  • 9時ごろ

C++版VMが完成。あまりの速さにショックが隠しきれない。

  • 9時半頃

BASICに再挑戦。
良く分からず。

  • 10時ごろ

私用により外出

  • 20時ごろ

帰宅。
M氏がアドベンチャーと2Dの簡単なやつを解いて
他のメンバーのパスワードを取得していた。
BASICを見直す。
よく見ると、メンバの一人を試すのを忘れていた。
一番最初のコードでクラックしてみると、
あっさりパスワードが取れてしまった。
今までの苦労は一体…。

  • 20時半ごろ

全員のパスワードが割れる。
それぞれの一番簡単な問題が大体M氏により解かれる。

  • 21時ごろ

情報をWikiで共有することに

  • 22時ごろ

情報収集完了

  • 23時ごろ

全課題を理解する

  • 23日2時ごろ

特に進展なし。
連続覚醒時間が30時間に近くなってきたので、
絶えられず就寝。

  • 10時ごろ

起床。
M氏も同じぐらいに起床。
BLACK（アミダくじ）を考える。
問題は、指定された対応関係+音がなるアミダくじを作れというもの。
どうしてここにきてもろICPCな問題を解かにゃならんのかと思いつつ…。
アイデアとしては、まず、位置だけあってるものを
バブルソートか何かで作って、
そのあと棒二つを任意のところに挿入して音を合わせようというもの。
グラフのマッチングぽいが、
その部分の有効な解法を思いつかず。

  • 11時ごろ

BALANCE(変態言語)をやってみることに。
簡単なやつだけ解けた。

  • 1時ごろ

CIRCS(回路)をM氏に聞く。
掛け算が解けてるなら、リバースは簡単じゃ？
M氏にやってもらう。
コンパイラを書くのがいいのかという話になったが、
これはコンパイラかいてる間にかけてしまうで、
という話になった(私がした)。
それに、二次元プログラムの最小化とか、
自動ではやりにくいで、とか。

  • 2時ごろ

ついで、CIRCSのレイトレーシングを考える。
二人でいろいろ考えているうちに、M氏にアイデアが生まれたようなので、
やってもらう。これが出来たらでかい。

  • 同刻

私はまだ解けていなかったADVISE(変態言語その2)を解くことにした。
数式の計算は、変換規則を8個ぐらい書いたら通った。
これに気をよくして、もう一つのXML変換の方を頑張り始める。

  • 3時

がんばっていた

  • 4時

まだがんばっていた

  • 5時

まだまだがんばっていた

  • 6時

ADVISEが、変換規則を50個ほど書いたところで
ようやく通る…。
もう、永遠に通らないと思った。
これでようやく泥沼から脱出。
しかし、変換規則をたくさん書きすぎたせいで、
あまりにも点が低かった。

  • 7時

M氏がレイトレーサを書き上げる。
そして、アクセプト。
一気に1000点以上入って、
順位がものすごく上がった。

  • 8時ごろ

K氏がちょっとだけ参加してもらえることになった。
ANTOM（蟻オートマトン）を考えてもらう。

  • 9時ごろ

ANTOMに重大なバグがあることをK氏が見つける。
(下2行を適当に書き換えても通ってしまう)
そして、あっという間に全部解き終わる。
400点追加。

  • 10時ごろ

アミダをみんなで考える。
結局良く分からず。

  • 24日1時ごろ

ぐだぐだ。
ANTOMの得点が剥奪。
デバッグされてANTWOに改名。ショック。
ANTWOをまともに考えるも、二つ目がいきなり難しい。

  • 同刻

K氏退場。
M氏就寝。
私も寝ようかと思ったところ、ANTWOのいくつかの解き方を同時に思いつく。

  • 2時ごろ

ANTWOを6つ片付けて就寝。

  • 10時ごろ

起床。
M氏もすこしして合流。
この時点でのこりは
BALANCE、BLACK、ANTWO、ADVの4つ。

  • 同刻

二人がかりでとっととBLACKを片付けようということに。
M氏がランダムアルゴリズムで40ぐらいまで解く。

  • 11時ごろ

いろいろ考えていると、急に天啓がひらめく。
貪欲解法でほとんどの場合が解けてしまうような気がしたので、
それを実装。1000の場合でも一瞬で答えが求まることを確認。

  • 12時ごろ

M氏のアミダ生成ルーチンと合成して答えを得る。
しかし、答えが巨大。1000にいたっては20MB以上。
とりあえず、400まで10分ぐらいかけてバリデータに通す。

  • 12時半ごろ

1000と500を並行的にバリデータに通す。

  • 2時ごろ

80分ぐらい走らせたところで
M氏がアミダを劇的に縮小する方法を思いつく。
大体数十分の1のサイズになった。

  • 3時ごろ

BLACKがようやく完全終了。1000点取得。
しかし、トップのスコアを見るとやる気をなくす…。
この時点でもうとっくに全ての課題を終了していたような気がする…。

  • 4時ごろ

残りは三つ。
私がANTWOとBALANCEをやって、
M氏がアドベンチャーにトライすることに。
アドベンチャーはオートソルバーを作るという方針で。

  • 5時ごろ

ANTWOが残り3つに。
スコアボードが凍結される。

  • 6時ごろ

ひたすらBALANCE。
難しいもの4個+1個残っている。

  • 7時ごろ

BALANCEの難しく無いやつが全部解ける。

  • 8時ごろ

BALANCEのメモリコピーを気合で解く。

  • 9時ごろ

BALANCEのレジスタコピーの驚愕の解法を思いついたので、
それを実装。

  • 10時ごろ

アドベンチャーはあまり進まない模様。
BALANCEのメモリフィルの解法を考えてみた。

  • 11時ごろ

メモリフィルが半分ぐらい出来た

  • 25日0時ごろ

メモリフィルの最後のループのレジスタ割り当てが出来ない。
ずっと考えても分からないので、
ついに自動計算プログラムを作ろうと試みる。

  • 0時半頃

プログラム完成。
でも、探索空間が広すぎて答えが出ない。
アドベンチャーの情報収集が完了した模様。

  • 1時

終了。
メモリフィル完成せず。
アドベンチャーもほとんど進まなかったらしい。


その後…。
アドバイスは自分で項を作れば、簡単に解けることを知らされてがっくり…。
アドベンチャーは隠しコマンドがいっぱいあったらしく、
英語をパージングしなくていいことがわかってがっくり…。
トップチームの驚愕のスコアにがっくり…。
すべての課題で最高得点って、勝ち目なし…。
しかもGoogle社員だなんて。
もはや完敗。


…というわけでした。
まぁ、これに懲りず来年もでようとは思いますが、
出来れば、言語の優位性が現れやすいもの、
しかも、少人数でも勝てるような課題にしてもらえると
ありがたいような、
そんなふうに思っておりますので
是非ともよろしくお願いいたします。