ICFP Programming Contest
実に楽しかったです。とりあえず結果は 2761 てん。スコアボードと比べると結構増えてるんですが、それまでカラだった BLNCE ができるようになったからだと思います。点数的には今回はまぁグループ有利なんでしょうね。まぁどうせ上の方行けないので別にいいですが。
感想としては、まず第一にこのシステムすげーーーということ。まず UM の仕様とその UM 上で動くプログラムが公開されていて、それを実行するとまたプログラムが出力され、それを実行すると UMIX なるシステムが UM 上で動き、その上で色々なパズルが楽しめる、と。この中に言語処理系が 4つも (私が発見できなかっただけで5つ目があるとのこと)入っててまぁそれはそれはすごいなぁと。
そんでパズルは発見したものは自由に選べるので、ある程度自分の好みの問題を選んだりと、レベルに応じて楽しめる感じで、毎回まんなかあたりでぼんやりしてる私にはとても嬉しい仕様でした。
さて思い出。
まず全然 UM が動きませんでした。割とすぐに UMIX のプログラム自体は出てきたんですが、 Allocation の仕様の英語が読めてなくてえらい時間がかかりました。普通に実装したら良かったんだなぁと…この間はなんか楽しげな問題がありそうなふうの ICFP からのメールとかが来てるなか、何があるのかすらわかってなくてつらかったです。
- INTRO
- UM が動いたらログインしたりメールを見たりすると得点がもらえました。こうやって得点ゲットしていくんだなぁとわかります。メールによると、パスワードを置いてある謎 BASIC をコンパイルしてクラックせよとのこと。そのへんでファイルの転送の仕方が学べました。まぁこの BASIC に感動したのですが、行番号を含めた数字が全て
アラビア数字(それはローマ数字だろ！とのこと。ご指摘感謝)なのでした。遊び心満載というか。最初に置いてある BASIC コードは foobar のような文字列を試すだけなのですが、 foobar42 のような定型のパスワードに2ケタの数字つけたものをクラックすると良いよーとコメントが書いてあるのでそれは自分で実装することになります。 words(i)+j とかいうふうにして、あれークラックできないなーとずっと思ってたんですが、これを PRINT してみると foobarXII とかになってて、うあーすげーと思いました。正解は words(i)+CHR(j+XLVII)+CHR(k+XLVII) みたいなかんじ。
- ADVTR
- それでまずアドベンチャーゲームが置いてあるアカウントをクラックできたと思います。このアドベンチャーは実にひどいもので、 A の上に B が置いてあって B の上に C その上に D …というぐあいになってるのですが、このゲームでは捨てるコマンドが使えないらしく、不要なアイテムは焼き捨てることになります。アイテムは壊れてるものが多くて、壊れたアイテムは組み合わせることによって復活するのですが、まぁこの組み合わせがイヤがらせのようになっていて、 antenna のついてない radio でないとダメ、とか、組み合わせの順序が決まってたりとか、まぁ大変でした。私は最後の方になってやっと最初の部分だけやりました。その後はなんかもっと悲惨な世界で、たぶんプログラム書いて自動的に解かせろとかいう意図だったんじゃないかなと思います。まぁ最初の部分が終わるとアカウントが拾えたのですぐやめました。
- BLACK
- 次におもちゃを作るパズルをやったと思います。簡単なルールに従って音が鳴るもので、仕様にあったおもちゃを作れという問題。普通に探索したらすぐ指数爆発して、ちょっと枝刈りしたらほんの少しは解けたのですが、難しいおもちゃは全然作れませんでした。 GA とかでいけるかなーと思って保留して後で再チャレンジしたのですが、全然ダメでした。みんな割と 1000 てん取ってるし私も後で考えたらできるだろーと思ってたのにできなかったのは悲しかったです。まぁこの手の問題は一人でやってる身としては先行きが不安すぎてやる気が起きにくいです。
- CIRCS
- 次に 2D プログラミング言語で仕様にあったプログラムを書くというお題でした。具体的にはこんなの。
,...................|....................., :mult v : : *=============* *===============*: : !case N of S,E!->!send[(Inr(),E)]!- : *=============* *===============*: : *=================*| : ->!send[(W,E),(W,S)]!#----------+ : : *=================*v v : : | *========* *=====* : : +------->!use mult!->!use p!----- : *========* *=====* : ,.........................................,
こんなもののパーサとか書くのは普通でも大変だろうに、このシステム作った人はホントすばらしいなぁと思いました。必死こいてえらい長い時間かけてやったら一応問題は解けました。これは小さなコードを書いた方がいいというお題で、なかなか PKU チックで楽しかったです。 "a professional programmer knows that shorter code is better code" という文は色々素晴らしいなぁと思いました。
- ANTWO
- 次はアリのシミュレータみたいなのに従って、アリがエサにたどりつける戦略を考えてあげるというもの。これも探索系のプログラム書くのかなぁと思ったのですが、これも先行きが不明ですし、ちょっとやってすぐやめました。他の人見る限りあまり得点取れてないようでしたし。
- ADVIS
- 今度はマクロ言語。変換ルールを記述しておいて題意にあう結果を出すコードを書きます。 CIRCS もそうですが、すごく実用性のない言語なので、なかなかにマゾプログラミングが楽しめて良かったです。しかしできるものは足し算とかかけ算とかなので浮かばれない。苦労しましたけど解けたようです。これをやってる最中に UMIX が更新されて、最新の UM は微妙に最適化したせいで動かなくなってるとかで困りました。さらにその時に変なメモリ確保しまくりバグを入れてしまったのでその後はとても苦労しました。
- BLNCE
- 最後の方にやっと発見できた問題で、かつなんか極めつけという感じの変態的なもので、 VM の上にまた実装されてる VM でした。これもご多分に漏れず実用性皆無の VM で、命令が 4 つしかありません。「レジスタの値をメモリに代入せよ」とかが問題になるくらい使えない物体でした。これはかけ算とメモリを埋めるもの以外はできました。かけ算は 1 が無いのにどうやって実装するのかなぁ…と思いつつ終わった感じでした。
個人的には今年はとても楽しかったです。妙にイヤげなトラブルだのヘンな勘違いだのが多かったのはしんどかったですが。今年は特に、チームじゃなくても、他の人が近くにいると他の雰囲気とかつかめてラクなんだろうなぁと思いました。1人で暗中模索というのもなかなか雰囲気にもあって、良いものでしたけど。あとまぁ、関数型言語の素養とかがあると有利なんですかね。今回は Haskell 風味な問題が多かったような気がするのですが、関数型よーわからんのでわかりません。
どうでもいいけど終わってみると得点はほとんどマゾプログラミング系だけでした…
主催者に感謝。たぶんスーパーハカーな人が膨大な労力を払ってたんだろうなぁと思います…他の参加者のかたはおつかれさまでした。
ぐへー… UM で動く UM …自分自身を永久に呼び出し続けて下さい…
http://icfpcontest.org/task.shtml#materials
追記。
http://www.kmonos.net/wlog/63.html#_0214060725
あー kuma- とかいるけど情報理工のおかしい連中(言うまでもなく誉め言葉)じゃねーとか思ってたらやはりというか。少なくとも単身じゃないのは安心というか。トップ3つくらいはチームじゃなきゃビビるというか。 BLACK とか ANTWO とかどう解くもんなんだろう、とか、 BLNCE のかけ算どうするねんとか気になりますが、そんなことより第5の言語処理系が楽しいというお話はもったいないことをしたなと。無駄な時間はたくさんあったので ADVTR やっておけば良かったです…とりあえず解説は読まずに、暇な時にやってみようと思います。
UM で動く UM とか見てると UMIX のソース配って欲しいなぁとか思いますね。もちろん UM 上で動くコンパイラでコンパイルできるソースを。あと JS で UM 実装しておくと 3年もすればブラウザ上でできるかもね、とか。夢ひろがるなぁ。こういう、クロスプラットホーム/マルチ言語を実現するためにまず VM を定義しちゃうっていう思考は面白いよなぁとか。今流行ってる種類の VM は言語をだいたい特定しちゃってるのはアレなのかもとか。 MS Excel とかそんな感じで動いてるとかでしたっけ。最近はそういうの流行らないのかな。私のコードはバイナリ配布ですが、 NES バイナリなのでクロスプラットホームです！ iPod でも動くぜ hehehe... とかどうだろう。
一応、上のは個人的な感想なので、せっかくだから説明足りてない部分について、すばらしい問題群の紹介を簡単にしておきます。興味を持ったかたは来年の参加を検討されると良いです。
- ADVTR
emacs で遊べるアレみたいなものです。テキストベースでメッセージが出てて、取れるコマンドを入力する、と。
There is a bolt here. Underneath the bolt, there is a spring. Underneath the spring, there is a button. Underneath the button, there is a (broken) processor. Underneath the processor, there is a red pill. Underneath the pill, there is a (broken) radio. Underneath the radio, there is a cache. Underneath the cache, there is a blue transistor. Underneath the transistor, there is an antenna. Underneath the antenna, there is a screw. Underneath the screw, there is a (broken) motherboard. Underneath the motherboard, there is a (broken) A-1920-IXB. Underneath the A-1920-IXB, there is a red transistor. Underneath the transistor, there is a (broken) keypad. Underneath the keypad, there is some trash.
などと積み上がってるアイテムは、6個までしか手元に持てないため、必要でないものは焼き捨て、必要なものはうまく合成して数を減らしつつ keypad の修復に必要なものをそろえます。「もっと悲惨な世界」ではさらにたくさんの、無機質な名前のアイテムがたくさんあって辟易してやめちゃったのでした。
- BLACK
音の鳴るおもちゃを組む問題です。パイプが何本かある、そのてっぺんからボールを入れると、アミダ状にボールが動いて出てくる、その時に右に動く時は音が鳴る。各パイプにボールを入れた時に出てくる場所と、音の回数が与えられているので、それを満たすおもちゃを考えろ、とのこと。
0 -> (3,4) 1 -> (2,3) 2 -> (0,1) 3 -> (1,1)
みたいな仕様に対して、
><|| |><| ><|| |><| ||>< |><| ||>< ><|| ><||
みたなものを作ってやれば OK 。 >< がアミダの交叉する部分です。このサイズは手でも作れますが、大きくなると大変です、というか解けませんでした。
- CIRCS
上の図がだいたい全てをあらわしています。この言語、アルゴリズム考えてから実際に書くまでがとても大変で、専用のエディタとか作った方が良かったなぁと思いました。トップの方の人はきっとサイズ最適化機能つきコンバータとか書いてるんじゃないかなぁと思ってたのですが、真相は不明。他もそうですけど、基本的にプログラムは再帰ばっかりって感じで、関数型関数型してる感じかもです。
- ANTWO
Puzzle 1: Simple NNNNNNN NNNWENN 8 8 - - - - - - - - -0>0< - - - - - - - - - - # - - - - - - - - - - - - - - - - $ - - - - -0v - - - -1^ - -0^ - - - - - - - - - - -
図をはってみたものの、全然やってないし思い入れないので説明むずかしい…特定のルールで動くアリに対して、行動の方針と初期配置を決められるので、うまくエサを取らせてあげましょう…と。行動のルールはだいたい決まってるのですが、アリとアリが衝突した場合の方針は指示できます。それが NNNNENN とか書いてあるところです。
- ADVIS
Add Z y => y; Add (S x) y => S (Add x y);
ルールベースの置換を連続させて計算をさせる、マクロ言語？みたいなもの。上記のコードはサンプルにあった足し算です。 Z が 0 、 (S Z) が 1 、 (S S Z) が 2 ... というルールで、足し算を実装しています。
Add (S S Z) (S S Z) -> S (Add (S Z) (S S Z)) -> S (S (Add Z (S S Z))) -> S S S S Z で 2+2=4 が計算されることがわかるかと思います。たぶんこの言語の肝は、ルールの適用は、先頭しか見てくれないことだと思います。上記定義ではたぶん Add (Add x y) z みたいなのは動かないと思います。
そこを根性でなんとかするという話なのですが、私は中から計算するために、外にある関数はとりあえずマークをつけて後ろにやっておき、中を計算してから戻してくる、っていう方針でやりました。マークをつけるとかはモナドとかと関係があったりするかもしれませんがよくわかりません。
- BLNCE
パズルとしか言いようがない言語というか VM でした。私的にはこれが一番楽しかったような気がします。命令が 4 つしか無いというのがなんとも素晴らしいです。そしてこれらの命令は妙な挙動をします。たとえば MATH という命令は、
M[ dR[D+1] ] <- M[ sR[S1+1] ] - M[ sR[S2+1] ] M[ dR[D] ] <- M[ sR[S1] ] + M[ sR[S2] ]
と記述されている通り、足し算と引き算を同時に行う命令です。あとは AND と XOR を同時に行う LOGIC 、特定条件でプログラムカウンタの動作速度を変更する SCIENCE (これが if とか goto とかを兼任しています、動作速度を変更するだけなので、色々妙なコード短縮ができそうで面白そうでした)、レジスタに即値を加算しつつレジスタを即値の値に応じたルールでローテーションさせる PHYSICS 、とどうしようもなくクセだらけの 4命令です。こんなわけのわからない命令セットでプログラムが書けるというのはなかなか驚きでした。というか私は LOGIC 使わないまま問題解いてたので、実質 3 命令です…
たとえばメモリの内容をレジスタにコピーしろ、という問題があったのです。まず mov みたいなのは無いですし、そもそもメモリ→レジスタの方向で干渉できる命令が存在しません。しょうがないのでループ回してメモリの内容をデクリメントしつつ、レジスタを 1 ずつ増やしていくことになるのですが、レジスタは加算するとすぐに場所が変わってしまいますし、メモリ内の引き算をする副作用の足し算が起きるので、それが大事なメモリを破壊しないようにしつつ…などとパズルなことを考えなければなりません。
メモリ内にある a*b を計算しろという問題があったのですが、どこにも 1 が無いので、えーとどうやってかけ算実装するのかなぁ、と考えてる間に終わりました。真相は闇気味です。 LOGIC うまく使うのかしら…
- と、
まぁこんな感じでした。よくわからんばかり言ってますが。書いたコード群の記念撮影。名前が不適切なのが多くてひどいですけど。
i@u wrk/icfpc/2006> wc *.d *.cc *.rb *.sh *.ant *.adv *.bal *.2d~README.2d Makefile
64 209 1877 asm.d
21 56 450 disasm.d
338 1048 9627 ga.d
17 59 451 mkultra.d
184 519 4319 raytest.d
167 471 4048 raytest2.d
5 16 106 test.d
315 936 6750 toy.d
493 1324 11144 um.d
477 1284 10598 um_stable.d
78 217 1377 umutil.d
226 654 4569 toy.cc
15 29 214 asm.rb
9 16 146 convgoal.rb
7 12 132 cutgif.rb
14 35 226 dumpimg.rb
7 20 204 rayparse.rb
32 72 667 umixsh.rb
4 5 39 brute.sh
2 11 65 toyparse.sh
12 66 173 pz1.ant
20 504 1086 pz2.ant
15 98 251 pz5.ant
34 216 790 mult.adv
27 213 647 xml.adv
37 339 1048 xml2.adv
35 333 1098 xml3.adv
27 253 766 xml4.adv
32 277 855 xml5.adv
47 450 1433 xml_.adv
1 1 9 addmem.bal
1 1 17 addmem2.bal
1 1 19 clearreg.bal
1 1 36 copymem.bal
1 1 37 copymem_.bal
1 1 37 copyreg.bal
1 1 37 copyreg_.bal
0 1 2 dummy.bal
1 1 5 stop.bal
1 1 5 stop1.bal
1 1 5 stop127.bal
1 1 5 stop128.bal
1 1 13 swapmem.bal
1 1 7 swapreg.bal
0 1 60 swapreg2.bal
25 83 1061 mul.2d
88 328 5701 mult.2d
29 105 1848 plus.2d
29 106 2004 plus2.2d
149 777 12451 ray.2d
393 2369 36426 ray_.2d
150 777 12450 ray_last2.2d
26 77 1466 raytest.2d
42 100 1583 rayu.2d
24 80 930 rev.2d
17 48 287 Makefile
3746 14607 141657 合計
