ICFPのコンテストに参加しました
http://icfpcontest.org/2010/
一週間遅れですが、簡単なレポートを。ここに書くのほぼ一年ぶりか…
今年は流れで某Mくんと２人でチームを組んで参加。チーム名tokorobashi。名前の由来は近いうちに明らかになるかもならないかも。最終結果は7点。
今年は特にサーバへのsubmitとかを便利にしてくれるインフラ整備をがんばる余地がいっぱいあったので、もうちょっと人数多くないと戦えてなかったかもしれない。でも結局、「本番」に到達できなかったのであんまり関係なかった。
大会の詳細はどっか他のサイトを見てください。(http://d.hatena.ne.jp/mr_konn/20100618/icfp2010taskあたりがわかりやすいか?)
一日目
6月18日(金) 21:00〜
開始。最初はサーバが重くてチーム登録ができなかったので、とりあえず英文よむよむよむ。結局、サーバの調子をみてチーム登録をやりながら、気分を落ち着けるために和訳文作成をはじめてしまって日付が変わるくらいまでその作業をしてた。Mくんはそんな僕をしりめに最初の回路構造を考えてたぽい。
6月19日(土) 0:00〜
日付が変わったころに、だいたいの問題を理解してなにはなくとも「回路」を生成しないと話にならないことに気がつく。で、問題にのっているサンプル回路を眺めてフォーマットを想像する。一つのゲートが二入力二出力なので、1行が1ゲートをあらわしていて、入出力の先が書いてあるんだろうなあ、くらいの想像はついた。最初の行と最後の行の意味がわからず1ゲートの回路(と思われるもの)をいくつかsubmitしてテスト。最初はエラーばっかし。
ログを見返してみたらもうこの時点で「これ入力も推測せなあかんのか?それとも定数を出力するような回路が組めるのか?」と結構本質的なことをしゃべってる。もっと早い時点で後者だと信じて突き進むべきだったよ。
1:00〜
1時間くらい試したところでM君の「最初と最後はXの場所っぽいよな」という発言で回路記法をようやく理解。ただしこの時点では、遅延する線としない線の法則がわかっていなかった。
記法がわかったので、1ゲートのいろんなバリエーションを入力して出力を収集。1ゲートは4パターンしかないので、それぞれに名前をつけて共有したりしてた。そうこうしてるうちに、ゲートを通過させなければサーバの入力が取れるなと気がついて、全部の出力が自分自身の入力になっているゲート一個だけの回路を入れてみる。こんなの。
X: 0R0L0#0R0L: X
無事にとおってサーバ入力がとれた。これがとおってから「X::X」で充分だったことに気がつく。で、実はここでゲートの入出力表を作成するのには充分な情報が得られているらしいのだが、「遅延」のセマンティクスがまったくわかっていなかったので、そこでつまづいてしばし悩むことになる。あとで聞いてみたら、会社の先輩も同じところでつまっていた。
2:00〜
どういう線が「遅延」されるのかさっぱり理解できていなかったので延々悩む。「右出力は常に遅延されるのでは?」などという頓珍漢な仮定を僕がだしてしまったので余計迷宮入り。このへん良く覚えてないが、4:00くらいまで悩んで、わからないなりにも回路シミュレータをrubyで実装したりしていた。気がついたら次の日の昼頃になってた気がするが良く覚えていない。
19:00〜
悩みながらなかなか寝られなかったりしたので、起きたら夜だった。ひどい生活。
寝てる間に、Ｍ君がゲートが２つの回路を自動生成して出力を収集してくれていた。まるっきり同じ出力をする回路とかでてきて、なかなかおもしろい結果に。それらを眺めつつ、悩んでいたら2時間くらいたっていて… そしてやっと遅延のセマンティクスに気がつく。
二日目
6月19日(土) 21:00〜
単純に、「自分より前かあるいは自分のゲートに出力されている線が遅延される」ということにやっと気がついた。配線のトポロジは同じでもゲートの順番が違う回路をちゃんと試していたらもっと早く気がついていたかもしれない。
なんにせよここで、配線の初期値(後ろのゲートの出力が入力になっている場合の、初回の値)の推定を含めて入出力表を求める作業にはいれることになった。回路シミュレータを改造して、いままでの回路と既知の出力値をぶちこんで入出力表を埋めていくプログラムを組んだ。
人間が解くように、「確定できるところだけ表を埋めていく」ようなコードにしてしまったので、1ゲートの回路だけじゃ求まらなかった。が、M君が収集してくれた2ゲートの回路の結果もいれたら動いた。2、3バグを直したらすぱーんとそれっぽい表ができて喜ぶ。初期値も0以外では成立しないという結果もでた。
「ありうる表を全て試して、まずいことが起こった表は捨てる」という方法だと1ゲートの回路だけで表がでたみたい。どうも僕は全探索への苦手意識がありすぎる。ちゃんと全探索でいける計算量を見積って探索できるようにならなきゃだめだな。
で、回路シミュレータがようやくまともに動くようになったので、サンプルの回路を動かして"the key"を得た。そしてまたもや途方にくれる。
23:00〜
"the key"はわかったものの、それを出力する回路をどう構成すればいいか全くわからない。たまーに、入力したい段数分遅延させたらいいんじゃないかなあというぼんやりしたイメージは浮かんだものの、具体的な構成方法が全くわからないので、その発想はすぐ消えてしまうのであった。
しっかりした目標がさっぱり立たないので、まず「入力にかかわらずに決まった値を出力する1入力1出力の回路」を考えはじめる。そういえばgraphvizでの回路の図示も実装してみたが、左右の出力がちゃんと左右に配置されなくてあんまりわかりやすいものにはならなかった。
6月20日(日) 0:00〜
ノートに回路を殴り書きしながらうーんうーんと頭をしぼって、ようやく「任意の入力を受けとって0を出力する」回路の構造の概要を思いつく。が、ちゃんと作ると10ゲートを越える回路になりそうで、かつ似た構造を２つ重ねたものだったので、まず手書きする気は起こらない。こういうのは自動生成だろうと思って、ちょっとだけ書くのが楽な、回路を生成するためのDSLもどきをrubyで実装しはじめる。
2:00〜
このへんで簡単に回路を合成できるような機能までを含めて回路自動生成コードができてた。その上で「0を出力する回路」ができたので、それを元に1を出力するもの、2を出力するものを作ってライブラリ化。この時点では「これを作ったからといって"the key"の生成になにも寄与してないじゃないか むきー！」という気分になっていたのだが、実はこの蓄積が最後の最後にちょっとだけ役立った。
あと本大会の目的が勝ち負け関係なしの「なんとか得点を得ること」というものに下方修正されたのもこのあたり。
それ以降どうしてたかちょっと覚えていない。たまに「マルドゥックスクランブル」を読みかえして勇気をふるいたたせつつ、回路の内容がさっぱりわからないのでヒントを求めて問題に書いてある回路を解析しはじめてすぐに絶望的な気分になったりする。
7:00〜
問題に書いてあるサンプル回路の解析、などという無茶なことをはじめたせいで、回路の左出力は引き算であること、回路自体は遅延する線の数だけ変数を持つ漸化式で表現できること、などなどには気がつくがそれ以上のことはわからず、何もすすまない。絶望して寝た。回路の夢を見た気がする。
15:00〜
こんどは夕方には起きたが全く進展なし。相方とも時間があわず１人絶望をかかえて愚痴をtwitterに吐き散らしたりする。「全然やった気がしない!」とか叫んだ。
三日目
月曜日は仕事を休めなかったので実質日曜の深夜までがタイムリミット。
6月20日(日) 21:00〜
相方Ｍ君と話して「やっぱり入力関係なく数値を出力する回路を作るしかない」という方針を再確認。再確認したところで、希望の入力を出力するためには、多段に遅延する回路を作るしかないよなあ、というところに戻って、今度はイメージが消えないうちに真面目に考えはじめる。
最初は、任意の数値が出せるような構造が思いつかなかったのでadhocに1番目に1を出す回路、それに加えて2番目に1を出す回路、、というふうにインクリメンタルに手で回路を考えはじめる。回路生成プログラム上でコーディングしながら回路シミュレータで結果を確認して試行錯誤。入力がなんであれ先頭から「11」を出力する回路はできたが、3番目でややこしくなりすぎて途方にくれる。
23:30〜
一段ずつ手で回路の構造を考えるのは複雑になりすぎたので、一定の形式で任意の数列が出力できるような構造に思いをめぐらせる。そしてここでようやく思いつく。
入力によらず0,1,2を出力し続ける"定数回路"は既に手にはいっているので、左に入力された値に対して、右入力に繋げる"定数回路"を適切に選んでやれば、左出力の出力の値は完全にコントロールできる。こういうゲートを逆向きにN段繋ぐと、入力によらずN個の数字を出力する回路ができあがる。いわば、出力したい値を各定数回路にエンコードした回路を構成できる。ただし"定数回路"のゲート数はそれだけで10や20はあるものだったので、回路規模は10n 〜 20nくらいの大きなものになる。
とはいえ、この時点では回路のサイズなんて知ったこっちゃないので、そのまま急いで「指定した出力を行う回路生成プログラム」をコーディング。定数回路のライブラリが既にあったのでほぼそれを繋ぎあわせるだけで実装完了。30分かからなかった。
6月21日(月) 0:00〜
コーディングが完了したので,"the key"を出力する回路(確か260ゲートくらい)を生成して、どきどきしながらsubmit。
circuit output starts with
11021210112101221
this is a legal prefix
Congratulations.
You have submitted a circuit that produces the key prefix.とおった!長かったー！
本当はここからが本番のはずなのだが、もうタイムリミットと言える時間だったし、任意の数列を吐ける回路生成ツールができたのである程度満足してしまう。Mくんにツール群を託して風呂へ。
1:30〜
風呂からあがったらスコアボード上で得点が増えていた。ＭくんがCarとFuelの構造おかまいなしで、"the key"に適当に数字をくっつけてsubmitするのを試しており、"the key"に"1111"をくっつけただけのやつでも最初のほうのかなりの数のCarにパスすることを発見していた。最後に訪れたsubmit祭り。
とはいえ僕はもう得点にあんまり興味がなくなっていたのとサーバが無茶苦茶重くなっていたので、CarとFuelのエンコーディングのところの問題を読みなおしたりしながらじっとsubmit祭りをみまもる感じに。ちょっと難しそうなCarにsubmitしてもらってそのエラーメッセージを見たりしていたが実質的にはもう何もせず。
3:00〜
結局25台のCarにsubmitを通したところで疲れたり満足したりタイムリミットだったりして終了。
score: 7.124 others' cars solved: 25 cars submitted: 0
ジェネラル・ルージュの凱旋
見ました。ない。これはない。
わかりやすくキャラ付けされた田口と白鳥が、原作の派手めのイベントの継ぎ接ぎをなぞっていく構成になってて、無理な皺寄せがいろんなところに波及していて目もあてられない。途中から半泣きになりながら見てました。キャラ付けはあれはあれでいい気もするけど、構成はもうちょっとなんとかならなかったんだろうか。
特に主役の速水。堺雅人が演じる本編の主役であるはずの速水の姿を楽しみにしていたのだけれども…あの格好よい速水はどこへいった？速水の葛藤や、その脇をかためるべき黒崎や佐藤の思いはどこへいった？泣ける。
これは「大事故発生してめでたしボム発動」と言われてしまってもしょうがないなあ。原作でもそういうイベントはあるけども、確かにボム発動でうやむやになった面もあるけれども、あそこまで全てを消しさる安直なボムではなかったと思う。
バチスタはもうすこしまともだったような気がするんだけどなあ。こんなもんでしたっけ？
428 〜封鎖された渋谷で〜
428 ~封鎖された渋谷で~(初回入荷分) 特典 スペシャルDVD「SHIBUYA 60DAYS ~Making 428~」付き - Wii
- 出版社/メーカー: セガ
- 発売日: 2008/12/04
- メディア: Video Game
- 購入: 4人 クリック: 38回
- この商品を含むブログ (129件) を見る
セガ・チュンプロジェクトのWiiゲー「428」を買ってひととおりクリアした。おもしろかった。これはおもしろかった。
「428」は5人の主人公が交錯しつつ4月28日の10時から20時までの10時間の物語を進めていくサウンドノベル。むかしなつかしい「街」システムで、ある主人公の選択が他の主人公の展開に影響を与えたりする。
実写をベースにした静止画だった街とは違って、たまに動画がはいったり、静止画でも微妙に動き(スクロール)がついてたり、音楽もよくなってる。地味にバージョンアップ。システム的に街とちょっとだけ違うのは、全体の話の区切りの単位。各人の行動が他の人に影響するのが1時間の単位で閉じている。全員の1時間をうまく経過させられると、そこで次の1時間がはじまる。街だと1日だったっけ？単位が短めになってるので、テンポよく進められるし、次の1時間に進めるところではいる予告の煽りっぷりもなかなかよし。
あと、「街」ではそれぞれの主人公がそれぞれの目的を持って動いてた感じだけど*1、今回のは誘拐事件を発端にしたひとつの大事件へと話が集約されていく。解決に辿りつくにはそれぞれの立場で正解ルートを選ばないといけないんだけど、それも各人が解決に向けてちょっとずつ努力して影響をおよぼした結果に感じられてプレイ感もよし。
正直なとこ、「街」だとおもしろい話もあればつまんない話もあって、全体の話をすすめるために嫌々消化してた話もあったりしたけど、今回はメインの事件に対する重要な役割がそれぞれの主人公に順番にまわってくる感じで、つまらないパートはひとつもなかった。特に、しだいに事件の全貌が見えだしてそれぞれの人の話が噛み合いだす昼以降の展開の加速っぷりは異常。ハリウッド映画的な話の転がりかた。そういうの結構好きなんです。
序盤は丁寧なチュートリアルがついてるし、チュンソフ党な人じゃなくても、サウンドノベルに抵抗のないWiiユーザーはみんな買えばいいと思うよ。
ただ、二つ目のボーナストラックは…個人的には本編を台無しにしてると思うので、それだけは見なかったことにしたい。なんで付けちゃったのかね。
*1:やったのはかなり昔なんでもしかしたら違うかもしんない
容疑者Xの献身
映画は予想外に良かった。
何がよかったか、というと、犯人である数学者・石神を演じる堤真一さんの演技があまりにすばらしかったのだ。
数学の道が閉ざされるとき - hiroyukikojimaの日記
そうそうそうそうそう。すっかり忘れていたが容疑者Xの献身の映画を見たんだった。映画のキャストをはじめて聞いた時は、「え？原作ではがっちり体型で頭薄の石神役が堤真一？全然キャラ違うじゃんどうするつもりだ」と内心あきらめておったのですが、堤真一がちゃんと夢を断たれた失意の数学者に見えたので、それだけで満足してしまったのだった。(原作にはまだでてきてなかった)内海薫も映画だからといって妙なことをしでかすことなく、ほとんど何もしなかったのもよかった。
原作は地味な地味な話なので、映画では派手な脚色やら設定の変更やらいろいろ追加されてたけどそれは気にしない方向で。松雪泰子もよかったし。うん。
wcコマンドの実装を通してArrowの気持ちを推し量ってみた
"モナドの一般化"なんていう敷居がやたら高いふれこみのArrowをちょろっと調べてみた。
主に、ha-tanさんのサイト(http://d.hatena.ne.jp/ha-tan/20070810/1186744818)と、そこから参照されているページをひととおり読んだ。
モナドがわかる人には多分、
3分で解るHaskellのArrowの基本メモ - よくわかりません
- Monadは、値をからくり箱に入れたもの。からくり箱は基本的に(ヘンな)値。
- Arrowは、関数をからくり箱に入れたもの。からくり箱は基本的に(ヘンな)関数。
という説明でなんとなく通じるかなあ。
Monadが型クラスなようにArrowも型クラス。でもって、Arrowの場合はからくり箱の中身が関数なので、型情報によって処理をふりわけるっていう性質がモナドより強い(気がする)。ストリームファンクションはそのよい例で、関数の型を、Arrowのインスタンス型のどの型だと推論/定義するかで、関数自体の定義は全く変えずに関数の対象が値からリストにがらっと代わる*1。
まだ試してないけど、Arrowとして定義されている関数には、Arrowのインスタンスの型を後付けしてやることによっていろんな処理ができるんじゃないかなあ。多分、関数の返り値を全部ログに取る、なんてのも書ける気がする。無理かな。書けなかったらごめんなさい。
で、http://d.hatena.ne.jp/ha-tan/20070814/1187046533を参考にwcコマンドの実装をしてみた。確かにタプルでパターンマッチさせるのはいまいちだな、と思ったのでさらに、http://d.hatena.ne.jp/takkan_m/20070814/1187102348を参考にパターンマッチをほんのりラップしつつ、自分なりにArrowの気持ちが一番わかりやすい形で組みたててみた。
import Control.Arrow wc :: (Arrow a) => a String (Int,(Int,Int)) wc = count_lines &&& count_words &&& count_chars where count_words = arr (words >>> length) count_lines = arr (lines >>> length) count_chars = arr length a3_show :: (Arrow a,Show b) => a (b,(b,b)) String a3_show = arr (show *** show *** show) >>> join where join = second join_tab >>> join_tab join_tab :: (Arrow a) => a (String,String) String join_tab = arr (\(a,b) -> a ++ "\t" ++ b) main = runKleisli (Kleisli (const getContents) >>> wc >>> a3_show >>> Kleisli putStrLn) ()
"Kleisli"というのはモナドを内部に含むようなArrowのインスタンス型であり、かつ、"Kleisli m"型のデータ構築子でもある。"runKleisli"というのが、Kleisli型の値からモナドな関数をひきだす関数で、"Kleisli m a b -> a -> m b"という型を持っている。この場合は、"Kleisli putStrLn"等々からIOモナドを含むKeisli IO型の値を生成し、そこから"runKleisli"を使って"a -> IO ()"型の関数を引きだしているので、mainの型は"IO ()"となって、型の整合性はとれている。
見てのとおり、wcやa3_showにはモナドのことは一言も書いてないけど、">>>"を使ってArrowとして結合してあるので勝手にArrowのインスタンスである"KLeisli IO"型に推論されていて整合性がとれる、と。これは地味に嬉しい。
あと、wcとa3_showには、うざったい型宣言が書いてあるが、これは省略してもちゃんと動く。なんで書いてあるかというと、型宣言を省略すると、mainの部分にひっぱられてwcが"wc :: Kleisli IO String (Int, (Int, Int))"と推論されてしまうから。"Kleisli IO"はArrowのインスタンス型で、つまり、省略すると本来はArrowという型クラスでいいはずの型が具体的な型に推論されてしまう。
さっきも書いたけど、多分Arrowのうまみは(多分)型情報によって処理を切りかえるところなので、具体的な型になってしまうとそのうまみがなくなっちゃうと思う。例えば、上のように型宣言しておいたソースをGHCiで読みこむと、
Main> wc "one two\three" (1,(3,12))
なんていうのも動作する。実は、普通の関数の型 "->"もArrowのインスタンスとして定義されているので、この場合はwcが普通の関数 "String -> (Int,(Int,Int))"と推論されて動作してるわけだ。wcの型が具体的な"Kleisli IO ..."と推論されてしまっているとこのコードは型エラーで動かない。
乱暴にまとめると、Arrowはモナドみたいにシーケンシャルな結合だけじゃなくて、分岐や(ここでは使ってないけど)繰り返しを表現する演算子を使って結合させることができて組み立ての自由度が高い。さらにArrowな演算子で実装した関数は(ちゃんとArrowな型宣言を書いておいてやると)いろんなArrowのインスタンス型と整合してくれる。上のコードの中ではwcを一行も書きかえることなく、IOモナドな関数および普通の関数として動作してくれる。Arrowをうまく使うと非常に再利用性が高い関数群が定義できるはず。
ということは、Arrowの使いこなす上で鍵になるのは、Arrowのインスタンス型をいかに上手く定義できるか、ということになるような気がするんだけど、他に典型的なArrowのインスタンスってどんなのがあるのかな。次はそのへんかなー。
*1:http://d.hatena.ne.jp/propella/20070807/p2にでてくるSFがその例