Hatena::ブログ(Diary)

sshi.Continual このページをアンテナに追加 RSSフィード

プロフィール

sshi

SFと映画と小説とRuby信者(最近はhaskellびいき)です。

 

2010-06-27 Sun

ICFPコンテストに参加しました ICFPのコンテストに参加しました を含むブックマーク

http://icfpcontest.org/2010/

一週間遅れですが、簡単なレポートを。ここに書くのほぼ一年ぶりか…

今年は流れで某Mくんと2人でチームを組んで参加。チーム名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〜

悩みながらなかなか寝られなかったりしたので、起きたら夜だった。ひどい生活。

寝てる間に、M君がゲートが2つの回路を自動生成して出力を収集してくれていた。まるっきり同じ出力をする回路とかでてきて、なかなかおもしろい結果に。それらを眺めつつ、悩んでいたら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ゲートを越える回路になりそうで、かつ似た構造を2つ重ねたものだったので、まず手書きする気は起こらない。こういうのは自動生成だろうと思って、ちょっとだけ書くのが楽な、回路を生成するためのDSLもどきをrubyで実装しはじめる。

2:00〜

このへんで簡単に回路を合成できるような機能までを含めて回路自動生成コードができてた。その上で「0を出力する回路」ができたので、それを元に1を出力するもの、2を出力するものを作ってライブラリ化。この時点では「これを作ったからといって"the key"の生成になにも寄与してないじゃないか むきー!」という気分になっていたのだが、実はこの蓄積が最後の最後にちょっとだけ役立った。

あと本大会目的が勝ち負け関係なしの「なんとか得点を得ること」というものに下方修正されたのもこのあたり。

それ以降どうしてたかちょっと覚えていない。たまに「マルドゥックスクランブル」を読みかえして勇気をふるいたたせつつ、回路の内容がさっぱりわからないのでヒントを求めて問題に書いてある回路を解析しはじめてすぐに絶望的な気分になったりする。

7:00〜

問題に書いてあるサンプル回路の解析、などという無茶なことをはじめたせいで、回路の左出力は引き算であること、回路自体は遅延する線の数だけ変数を持つ漸化式で表現できること、などなどには気がつくがそれ以上のことはわからず、何もすすまない。絶望して寝た。回路の夢を見た気がする。

15:00〜

こんどは夕方には起きたが全く進展なし。相方とも時間があわず1人絶望をかかえて愚痴twitterに吐き散らしたりする。「全然やった気がしない!」とか叫んだ。

三日目

月曜日仕事を休めなかったので実質日曜の深夜までがタイムリミット。

6月20日(日) 21:00〜

相方M君と話して「やっぱり入力関係なく数値を出力する回路を作るしかない」という方針を再確認。再確認したところで、希望入力を出力するためには、多段に遅延する回路を作るしかないよなあ、というところに戻って、今度はイメージが消えないうちに真面目に考えはじめる。

最初は、任意の数値が出せるような構造が思いつかなかったので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〜

風呂からあがったらスコアボード上で得点が増えていた。MくんがCarFuel構造おかまいなしで、"the key"に適当数字をくっつけてsubmitするのを試しており、"the key"に"1111"をくっつけただけのやつでも最初のほうのかなりの数のCarパスすることを発見していた。最後に訪れたsubmit祭り

とはいえ僕はもう得点にあんまり興味がなくなっていたのとサーバ無茶苦茶重くなっていたので、CarFuelエンコーディングのところの問題を読みなおしたりしながらじっとsubmit祭りをみまもる感じに。ちょっと難しそうなCarにsubmitしてもらってそのエラーメッセージを見たりしていたが実質的にはもう何もせず。

3:00〜

結局25台のCarにsubmitを通したところで疲れたり満足したりタイムリミットだったりして終了。

score: 7.124
others' cars solved: 25
cars submitted: 0

まとめ

以上終わり。自動生成して都合のよい回路を探索するようコードは一行も書かなかった。というか回路を育てていくアルゴリズムがぱっと思いつかなかったので、思いっきスルーしてた。もうちょっとそっち方面の勘を養っとくべきかもなあ。

今回は「回路の構成のしかたがわからん」ということにつきる。最後にぎりぎり「Carに合うFuelを生成したり、Fuelが生成しにくいCarを作る」という今回のお題の入口には立てたものの、「他のプレイヤーとのコミュニケーション」はさっぱりできませんでした。エンコーディングの推測は楽しそうだったので、まだ余裕があるうちにそれが役立つ局面までは辿りつきたかった。残念。

2009-07-19 Sun

RubyKaigi2009 三日目  RubyKaigi2009 三日目を含むブックマーク

三日目だけ行ってきました。

土曜日行けなかった上に今日もかなり寝過したのでセッションはほとんど見れなかったけど、ふつうコンパイラ先行販売で手にいれたのと、某動画信者の方と会えたのでよし。

今年もReject Kaigiのテンションはすごかったのでそれもよし。オフレコのLTって…

2009-03-18 Wed

[] ジェネラル・ルージュ凱旋  ジェネラル・ルージュの凱旋を含むブックマーク

見ました。ない。これはない。

わかりやすくキャラ付けされた田口白鳥が、原作の派手めのイベントの継ぎ接ぎをなぞっていく構成になってて、無理な皺寄せがいろんなところに波及していて目もあてられない。途中から半泣きになりながら見てました。キャラ付けはあれはあれでいい気もするけど、構成はもうちょっとなんとかならなかったんだろうか。

特に主役の速水。堺雅人が演じる本編の主役であるはずの速水の姿を楽しみにしていたのだけれども…あの格好よい速水はどこへいった?速水の葛藤や、その脇をかためるべき黒崎佐藤の思いはどこへいった?泣ける。

これは「大事故発生してめでたしボム発動」と言われてしまってもしょうがないなあ。原作でもそういうイベントはあるけども、確かにボム発動でうやむやになった面もあるけれども、あそこまで全てを消しさる安直ボムではなかったと思う。

バチスタはもうすこしまともだったような気がするんだけどなあ。こんなもんでしたっけ?

トラックバック - http://d.hatena.ne.jp/sshi/20090318

2008-12-07 Sun

428 〜封鎖された渋谷で〜  428 〜封鎖された渋谷で〜を含むブックマーク

http://chun.sega.jp/428/

セガ・チュンプロジェクトWiiゲー「428」を買ってひととおりクリアした。おもしろかった。これはおもしろかった。

「428」は5人の主人公が交錯しつつ4月28日の10時から20時までの10時間物語を進めていくサウンドノベル。むかしなつかしい「街」システムで、ある主人公の選択が他の主人公の展開に影響を与えたりする。

実写をベースにした静止画だった街とは違って、たまに動画がはいったり、静止画でも微妙に動き(スクロール)がついてたり、音楽もよくなってる。地味にバージョンアップシステム的に街とちょっとだけ違うのは、全体の話の区切りの単位。各人の行動が他の人に影響するのが1時間単位で閉じている。全員の1時間をうまく経過させられると、そこで次の1時間がはじまる。街だと1日だったっけ?単位が短めになってるので、テンポよく進められるし、次の1時間に進めるところではいる予告の煽りっぷりもなかなかよし

あと、「街」ではそれぞれの主人公がそれぞれの目的を持って動いてた感じだけど*1、今回のは誘拐事件を発端にしたひとつの大事件へと話が集約されていく。解決に辿りつくにはそれぞれの立場で正解ルートを選ばないといけないんだけど、それも各人が解決に向けてちょっとずつ努力して影響をおよぼした結果に感じられてプレイ感もよし。

正直なとこ、「街」だとおもしろい話もあればつまんない話もあって、全体の話をすすめるために嫌々消化してた話もあったりしたけど、今回はメインの事件に対する重要な役割がそれぞれの主人公に順番にまわってくる感じで、つまらないパートはひとつもなかった。特に、しだいに事件の全貌が見えだしてそれぞれの人の話が噛み合いだす昼以降の展開の加速っぷりは異常。ハリウッド映画的な話の転がりかた。そういうの結構好きなんです。

序盤は丁寧なチュートリアルがついてるし、チュンソフ党な人じゃなくても、サウンドノベルに抵抗のないWiiユーザーはみんな買えばいいと思うよ。

ただ、二つ目ボーナストラックは…個人的には本編を台無しにしてると思うので、それだけは見なかったことにしたい。なんで付けちゃったのかね。

*1:やったのはかなり昔なんでもしかしたら違うかもしんない

トラックバック - http://d.hatena.ne.jp/sshi/20081207

2008-12-03 Wed

[] 容疑者Xの献身  容疑者Xの献身を含むブックマーク

映画は予想外に良かった。

 何がよかったか、というと、犯人である数学者・石神を演じる堤真一さんの演技があまりにすばらしかったのだ。

数学の道が閉ざされるとき - hiroyukikojimaの日記

うそうそうそうそう。すっかり忘れていたが容疑者Xの献身映画を見たんだった。映画キャストをはじめて聞いた時は、「え?原作ではがっちり体型で頭薄の石神役が堤真一?全然キャラ違うじゃんどうするつもりだ」と内心あきらめておったのですが、堤真一がちゃんと夢を断たれた失意の数学者に見えたので、それだけで満足してしまったのだった。(原作にはまだでてきてなかった)内海薫も映画だからといって妙なことをしでかすことなく、ほとんど何もしなかったのもよかった。

原作は地味な地味な話なので、映画では派手な脚色やら設定の変更やらいろいろ追加されてたけどそれは気にしない方向で。松雪泰子もよかったし。うん。

トラックバック - http://d.hatena.ne.jp/sshi/20081203
 

あわせて読みたい
sshi.Continual 890876 なかのひと RSS feed meter for http://d.hatena.ne.jp/sshi/