あつい…。
Blender用COLLADA Exporterのページを超放置してしまったので2.49b用のパッチを上げました。ごめんなさい。
あとrsdlのページも超放置してしまっていて、だいぶ前にknuさんがgemを作ってくれてrubygems.orgにもとっくの昔に上がっていたのにそれを全然書いてなかったのでちゃんと書きました。ほんとごめんなさい。
今年もICFPコンテストだよー。チームarekumaでやってます。
とりあえず一日目。日本時間では金曜の21時から。丁度いい時間だね。
ルールを読み始める。今回は車と燃料を設計してお金を稼ぐ対戦ゲーム的な物なようだ。おもしろそうだね！
車とそれにあった燃料を送信するとスコア加算されるんだけども、車は送信と同時に他の参加者にも公開され、他人の車の燃料を設計してお金を稼ぐこともできる。
車1種類に対するポイントは一定で、それ用の燃料を作った参加者で分配されるんだけど、同じ車でも効率のいい燃料の方が高いスコアが分配されるので、なるべく燃料を作るのが難しい車を作りつつ、他人の車にはさらによい燃料を作っていくのが良いとのこと。
読んでる途中で既に読み終わった人からそんな所より最後がひどいから早く先を読めと言われる。まあそんなに急かすなって。
じゃあ設計はどうすりゃいいのかと、車の設計を見てたらなんか難しくなった。よくわからんがあとでもう一回ちゃんと読もう。
とりあえず車の設計によって動く燃料が決まるからその係数を出してあげればいいのねなるほどねとか。
じゃあどういったデータを送ればいいんだろうというところまで読んで何で先を読めと言っていたのか分かった。
車設計のデータフォーマットは秘密です。サーバの出力から推測してやってください。だってさ。なにこのくそげー！！
とりあえずサンプルデータは書いてあるんだけど単なる3進値列なのでさっぱりだぜ。
で、さらに。
燃料を作るには、燃料のデータじゃなくて、燃料を作る工場の回路設計をしてそのデータを送る必要があります。でも回路データのフォーマットも秘密です。…この問題作った奴ぶっこわれてるな！
ということで、まずは一番簡単な車0番用の燃料用の工場を作りましょうって書いてあったのでやってみる。
あれ。サーバに車0番無いんですけど。詰んだ。と思ったら219番になってた。ICFPではよくあること。
サンプルをぶち込んだら文法エラーはなく、しかしながら出力された燃料のデータフォーマットが違うよと言われる。これはこれで正しい。ここから文法を探るのか。
サンプルをそれっぽい所で区切って整形し、しばらく眺めてたらなんとなく理解。というかすぐ理解できた。1ゲートの回路を組んでみて文法エラー出ずに通ったようなので間違ってないね。
しかしどうにも冗長な書式なのはひっかけなんだろうか。入力と出力は必ず一対一でつながるから両方書く必要無いと思うんだが、そこちょっとばかし悩んでしまったじゃねぇか。
ここからどうすりゃいいんだ。
まず書式が分かっただけで、入力列がわからん。あとゲートの仕様がわからん。正しい出力もわからん。こまったね。
ところで1ゲートの回路が書けたんだけど、0ゲートの回路はだめだろうなとX::Xをぶちこんでみたら出力されちまった！これで最初の入力列は分かったわけだ。
じゃあゲートの仕様を探るか。
ゲートは2入力2出力で外部からの入力は1つ、出力も1つ。全部の端子は1つずつ接続されていないといけないので、絶対どこかでループができるはめになるんだよな。
さてこまったな。ループしてる部分の初期値もわからんのか。
とりあえず1ゲートをいろいろ接続して、どの入力でどう出力されるのか調べたけど1ゲートでは全部調べるのは無理だな。すげーめんどい。
この辺で困ってるあたりでもう1時とかで眠くて頭がまわらなくなったので1日目終了。一昨年みたいに無理して体壊すのは怖いのでね。
土曜日はちょっとだけ仕事に出る必要もあったので夜からやるね。朝にちょっと考えてみたんだけど、入力列と出力列は分かってるし、3値論理とはいえ1ゲートの演算パターンなんてたかが知れてるので力技求めてもいいかもな。
0段目と1段目の演算が違うとか言われたら終わるけどそこまで鬼ではないでしょう。
とりあえず上位を狙うとか無理ゲーすぎるから、ほんのちょびっとでもスコアが入ることを目標にしたい。
続いて2日目。2日目っつーか土曜日だけど。
昼間はいろいろやってたのと仕事でちょっぴりでかけてたりしてたら遅くなって、20時くらいから開始。
とりあえずゲートの演算パターンを総当たりしちゃおう！というので書いてたんだけど結構パターンありますね…。
9の9乗オーダじゃねぇか。多いけどそれほどでもないか。
ということで考えるのが面倒になって脅威の九重ループを組んで施行。うーん、Rubyではちょっと遅いかな…。フィードバックしてる所の初期値を0と仮定しちゃってるけど、違ったらまたやらないといけないし。
じゃあC++で書くか。とやってたら途中でRuby版で答えが出来てしまった。試してみたが、1つの接続方法に対してしかチェックしてなかったので間違った答えが出たようだ。じゃあC++版はチェックを増やすか。
C++版が出来たのでデバッグしつつ動かしてみるがRubyよりちょっと速いくらいに見える。あれ、思ったより遅いな？
あ、最適化付けるの忘れてた、と-O3を付けたらものすごい速さで実行してくれて、ちょっとの間ぼけっと見てると論理表を出してくれた。最適化…おそろしい子！
あとは論理表を見ながらゲートの仕様をなんとなく計算。左出力は左入力-右入力、右出力が左入力*右入力-1のようだ。まあ分かったところで表使いますけど。
これで回路のシミュレータ作れるねー、って作った。動いた。やたー。
サンプル回路も動かしてkey prefixをゲット。これで入出力するべきデータが判明したので、回路を組もう。
回路を組もう。
どうやって？
その前に、今までフィードバックを適当に0番ゲートから処理してってその時点で値が不定なものは0と処理してたんだけど、フィードバックは外部端子がつながってるところからちゃんと辿らないと駄目じゃないかと言われたので、やっぱりそうかーと思って書き直し。
だがどうも上手く動いてくれなくて、結局0番ゲートから順番に処理する方法であってたというのが判明。なんか動いてるからいいやー的に作ってたんだがあってたのか。勘こわい。
それから回路組み方をいろいろ考えたんだけど1時くらいをまわってるのもあって頭が働かない。寝よう。 2日目はここまで。
3日目というか俺的3日目なだけで、つまり日曜日。期間的には2日目から3日目にかけてだ。
昨日あんまりできなかったので昼過ぎから始める。
回路を考えるのめんどいから遺伝的アルゴリズムでやっちまおうとする。
やってみた。しばらくいじってみた。投げすてた。
まあ近似解を出すアルゴリズムでぴったり一致する解を求めようとするのがおかしいよね。いや、正解は一つじゃないからそうでもないか。しかしそう上手くもいかん。遺伝子の作り方がけっこう適当なのも悪いだろうな。あとパラメータのいじりかた分かんねーよ。
これでもう18時くらい。それから真面目に考えてみたんだけどわからんので19時前に一旦飯休憩。
今年の目標が点数取ることだったけど、明日仕事だからいつまでもやるわけにもいかねーし無理じゃねぇのこれ？
20時から再開してわかんねーとだらだら言いながら回路を考えてたら、ゲートのフィードバックを重ねていくと入力に関係なく一定の値列を出力できるのに気付いた。おー。おー？これでどうすんだ？
そしたら超でっかくなるけどひたすら0とか2とか1だけ出力できるわー、と思ったんだけど使い途がねぇよそんなの。
固定の値列を出す回路としばらくにらめっこすると、各ゲートの初期値が変形されながら遅延してくる回路てのが分かった。じゃあ変形されることを見越した初期値を生成してやれば、好きな値の列が出せるんじゃねーの？
手で計算するのはむずいので回路を組むプログラムを書いてみた。めんどくさそうだなぁと思ったがそれほどでもなくなんとか23時半くらいには完成。手元で実行してみたら上手くkey prefix吐いてくれたよ！！
それをサーバになげるフォーマットで吐いてあげて、超重くなってるサーバにドキドキしながらポストしてあげると…
Congratulationsきた！！目標達成した！！ぎりぎり0時前に打開しました！！！
ということでめでたしめでたしで終了。本当は車作るところまで行きたかったけどこのペースだと月曜休んでも怪しかったかもねぇ。
先に数台の車解いてた人に聞いたら、簡単な車はフォーマットわからなくても適当な燃料つっこむだけでとおっちゃったりするらしい。それで何台かは解けたけどフォーマットはさっぱりわからんとか。そんなもんなのか。
反省。やっぱ地力が足りん。あとやる気。
去年はさっぱりだったが、一昨年頑張りすぎてその後4日寝込んだ思い出があるので、怖くて頑張れなかった。あと仕事で出掛ける必要があったりしたからね。まああんまり頑張ると体調本当に崩すから気をつけたのは良かったと思う。
地力は足りないね。回路組もうとした時にさてさっぱりわからんとなるのはなんとも。これはもっといろいろなアルゴリズム知っておく必要があるなぁと再確認させられていい感じだった。
今回の問題はもうちょっと点数取れるまで早くて良かったんじゃないかなぁ。これ車作れる所までいったらあとは最適化戦争になるだけしか無いと思うんだけど、そこまではほとんど点数取れないっつーのはどうなのよと。
いやむしろ対戦ゲームと見せかけてゲーム始めるまでが本当のゲームってのはどうかと。面白かったけどね。