頑張りはしたんですが、正直もっとやれたんじゃないかとくやしい。最後まで有効なソルバ書けなかったって感じですし…
コードはこのへん。こいうのって tgz とかよりディレクトリ置いとく方が面白いかなーと思ってそうした。 tern.rb あたりがひどい感じ。結果は 2002 台解いて 17 位。結果は悪くないんだよなぁ。
http://shinh.skr.jp/dat_dir/icfpc-2010/
問題の内容は…略。作業の記憶をリプレイだけ。
まず最後にヒントとして key prefix というのを作る回路を作れと書いてあるので、それを頑張る。頑張ります。ゲートの推測とかどうやったか忘れた。1ゲートだけの回路を置いてみてどうなるかーとかで回路の特性を理解したんだと思う。ただこの段階では明確な規則は深く考えなかったし、自分の作った真理値表が正しいか自信なくてドキドキだった。
で、回路の特性がわかったら17個の入力をなんか適当に推測したんだと思う。自信無いドキドキ状態のまま1ゲート4種類の出力内容から入力を guess していく。4種類あるので error correcting にもなって、かつどうも自分の真理値表あってるらしいねと。で key prefix をゲットしてやりましたという感じだった。こいう紙を大量に消費してゴリゴリみたいなのは比較的得意。このへんまでは4時間弱とかそのくらい。これで得点入るなーと思ったら甘かったのだった。
しかしその後がまだかなり大変だと気付いたのだった。任意の出力を出せるようにしたい。まずは simulation しつつ都合のいいのを足していく…みたいなのを書いてる途中で、ああ左っかわは入力を調整すれば好きなの出せるんだなぁとか気付いたんだと思う。
でまぁじゃあ左っかわの入力を固定しよう、とか思って、 0 と 1 と 2 をそれぞれ確定的に出力するゲートを作って、これで任意の数字が出せるようになった。あとこのへんで回路を手書きやすくする書式を作ったりもしたと思う。入力だけ指定したら出力は勝手に作ってくれるだけですが。このへんで朝6時。
そしたらまぁいくつかの問題を解こうと思ったんだけどまぁ寝たんだと思う。いやあ覚えてない。
起きたらクソ車がたくさん投稿されてるなーと思って解いていった記憶がある。その様を見てさっさと自動投稿書くかと思って書いた。 2 とかを入れるだけで解ける車とか結構あってひどい話です。
で、 ternary encoding を理解していったと思う。理解はなかなか進まなくて、大変だった。ていうか ternary encoding はよくわかってないまま適当にそれなりに思ったものに近いものが出るからいいやー的な感じでやってた気がする。
あとこのへんで 0 とかの固定出力する回路を縮めた気がする。いやどうだったか…
でなんかあたふたしてる間に lightning 終わったんだと思う。何かしらまだ良くて、 8 位とかにいたらしい。一人だとどうしてもスタート遅れる関係で、初日 8 位って今までを考えても結構悪くなかったんじゃないかなぁ。しかし内容はあまり誉められた感じではなかった。
二日目から、理解してないことが多すぎるとか作業量多すぎ的な意味で、こう焦りはじめる。僕はやりたいこと一通りできるんだろうかという恐怖があった。であんま寝る気が起きなくなって、寝た方が良かったなぁと後から考えると思う。マイペース重要。
えーとダメだ作業記録とか書けない。色んなことを並列でやってたと思う。まるで普段の仕事みたいだ。やったことを書いていく。
まず回路について。固定入力とか別に必要じゃなくて、当初やろうとしたみたいに軽く回路を走らせてやれば、すぐに欲しい入力くらいは計算できるよねーというのは気付いてはいたけど車解くことを優先してたので、とりあえずそのへんはやった。
それでだいぶ縮んだのだけど、さらに必ず 2 が出てる場所があるのでそれを次の回路で生かして、余った 2 出力は返す、ってアイデアを思いついて、これもどっかのタイミングで実装しようとした。 4-5 時間実装したりデバッグしたりした後で、余った出力返しちゃうと前の回路が要求すべき数値を決められないなーと気付く。これはすごいガッカリした。
しかしその副作用で、回路に遊びがあるから適当にひっくり返したりすると短くなったりして、要は一番コストのかかる 1 が必要になった回数とかがたまたま減ったりすると短くなることに気付いた。だから乱数をコードに入れて、 1 のための回路と 2 のための回路の、ひっくり返せるところは適当にひっくり返す感じにして、何度か実行して一番良かったのを採用するみたいなことをやってみた。これが結構短くなったので、まぁ 4-5 時間は完全に無駄とは言えなかったのが救いだった。
今朝もう一歩考えたところによると、たぶん必要コストは 1-3-2 から 1-2-1 に減らせると思うので、もう一歩考えれば良かったなぁと思った。個人的にこういう部分が一番好きな部分ですしね。回路についてはまた書き直してみて確認したいと思います。
自動 submit するスクリプトは適当に、どのソルバが解いたか、とか、ソルバは解けてると判断したけどサバにはダメって言われたとか、 180 chambers あって 6 tanks 使う車は 21/73 解けてますよーとか、まぁそいう情報を必要最低限出せるようにはしていた。
3進数は、えーとなんかきちんと再帰で表現できるんだろうなーと思いつつも、どうにもきちんと考えるのがめんどうで、「今くらいの数値の幅を表現できたらいいだろー」→「うわーでかいリスト持った車来た」→「適当に拡張したからもう大丈夫だろうー」→「ぎゃー」→「いくらなんでも」→「ぎゃー 2^600 とか必要じゃんこのくるまー」みたいな感じで時間の無駄感があって素晴らしかったです。これはがっかりするくらい無駄なところだったと思う。
さて一番重要なソルバなんですが、これはなんというか、イマイチだったと思う。 ICFPC 2003 とかダメな時のマラソンのような感じで、つまりこうアレコレとイマイチなアイデアを思いついては、他にいい方法も思いつかないし、得点増えない不安感がつもるし、という感じで、書いてしまう。焼きなましとかもこいう問題にいいのかなーとチラっと思ったりもしたんだけど、どうもこれ人間が恣意的に車作ってる中、そういうランダム的なアプローチでうまく行くのかなぁ…というのが疑問で実装してみれなかった。
でまぁ実際に使っていたソルバは主に 4 種類あったと思う。
1種類目は単純に 1 次元のタンクを仮定して、 2 とか 1 から始めて適当に不等式満たせてないところを増やしていく、っていうもの。これ単純なのにクソ車が多かったおかげで、 720 台はこれで解いた。 Ruby 。
2種類目は2次元行列を考えて、 0 と 1 の組み合わせでありえるものを全探索するというもの。これもまぁ結構解けて 390 台はこれで解いたらしい。速度が欲しかったので C++ 。行列ってむつかしいなぁと思ったので blitz++ とか使ってみた。 overkill もいいところだった。あと3次元行列とかでも小さいものに対しては計算できたので、オプションで計算できるようにしてたんだけど、後半はその存在を忘れていたので使わなかった。使ってればもうちょい解けたかもね…
そうそうこれを書いてるあたりでは、問題の車のエンジンの仕様の理解があっているという確信が全然無かったのだった。なんでかというと、たぶん ternary encoding の理解があやしかったせいでヘンな入力を送っていたんだと思うんだけど、サーバのレスポンスが僕の理解と違う感じの時が結構あったから。こういう不安感というのは途方もない恐怖なわけで、こいうのはチームと一人の大きな差じゃないかなーと予想してます。まぁ僕はマゾなのでそういうのも楽しいわけですが。
kik さんが書いてたけどまさにこんな感じ。いやあ自分がすごいと思う人に誉めてもらうと嬉しいですね: http://twitter.com/kikx/status/16681708106
3種類目は、その総探索をちょっといじって、いわゆる最急降下法というのをやってみた。なんかたいていのケースで2種類目が解けるヤツは解けるかも、ってくらいで、だいたいわけわからんローカルミニマムに落ち込んじゃうのでいけてない感じだった。で存在を忘れられた。しかしまぁ少しは解けてる問題もあった気がするので、これもちゃんと走らせてあげるべきだったなぁ。なん
今気付いたけど、このローカルミニマムどう避けるかなーって考えて、そもそもこっち系のアプローチは問題が恣意的に作られてる以上…とか思ってしまって諦めてしまったのでした。焼きなましとかここで思いつけたら、どうだったのかなーと思うけど、まぁやったこと無い、しかも経験則とか重要そうなアルゴリズムをここでやってもイマイチだったんじゃないかと思う。
4種類目はたぶん結構ユニークな子で、最初に Ruby で実装して、色々改善をしようと思って C++ で書きなおしたけどその改善はやりきれなかったという感じ。なんというか自分が解く時に考えることをそのままコードに落としたかった感じの物体。
具体的な手順はこんな感じ:
- まず main chamber の upper 側にあって、 lower 側に存在しない tank の順列を探します。この時 lower 側の最後に使われてる tank はなるべく順列の最初に使わないようにして、 lower の最初に使われてる tank はなるべく順列の最後に使わないようにします。
- で、その順列を通ると、 0 番目の気体が 1 番目に変わって、次のとこで 2 番目に変わって、…という感じで、ぐるっと回って 0 番目にかえってくるようにします。
- 例えば upper にしかない順列が タンク1 => タンク2 => タンク3 というものだったら、タンク1は気体0を1にして、タンク2は気体1を2にして、タンク3は気体2を0にする、という感じ。これで 0 番目の気体はとにかく 1 より増える。
- 同じ順列は lower には無いので、これによって 0 番目が lower に途中で現われることはない。
- 厄介なケースは lower の最初で入力気体を順列の一部の回路が拾ってしまって気体 0 にしてしまうことと、 lower の最後で順列の一部の回路を使って気体 0 を他の気体にしてしまうこと。
- このへんは適当に調整を入れたり retry したりとかいうことがしたかった。それなりにはしたんだけど時間がなくて完全とはほど遠いくらいしかできなかった。
- 調整は具体的には、 lower の入力の最初で例えば気体 4 が 0 になっちゃうなら、同じ chamber の upper 側の最初の tank で同じ変換が起きるようにして量をそろえる。ただこれは気体 4 から 0 の変換が起きるタンクを増やしてしまうことになるので、他の chamber で同じことが起きてしまうことがあって、うざい。
- 出力の方は深刻度がいくらか少なくて、 lower 側の最後のタンクで例えば気体 0 から 3 への変換が起きてしまっているなら、対応する upper 側の最後の tank でなるべくなら気体 0 以外で量が 1 以上になってるところから適当に変換してやる。気体 0 以外で量が増えてる場所があればそこを使えるので、問題が増幅する可能性はやや少ない。
- あと、 lower に無い順列を upper 側から拾ってくるというのはいくらでもやり方はあるので、色々やり直すことも適当にやりたかった。
- それともう一つの問題点としては順列が長すぎて、巨大な行列が出てきて submit できない系のもあった。
私はこういうなんかダメなんだけどあんま他の人がやらないけどやっぱダメだからやってないだけやろ的なアプローチを取っちゃうことが多いなぁと思う。 ICFPC で言うと 2004 年のアリとかまさにそんな感じだった。他の人の走らせてみて自分と全然違って笑った。
まぁそうは言っても終わってみるとこれが私の主力のソルバだったようでした。 Ruby の方は 795 台、 C++ にしたバージョンは追加で 96 台を解いたようです。この数字は他のソルバで解けなかったもの、という数字なので、まぁ意外と悪くはなかったのかもです。
あとは最後の submit 祭りですが、 50 台程度ローカルで解いたのに submit できなかったものがあって、これは少し残念だった。
感想としては運営おつかれですという感じでした。まず問題はすごく良かったと思う。色んな要素がバランス良く入ってたように思います。フォーマットの謎解きと、回路パズルと、回路ゴルフと、 scraper やら何やらといった実際的なコードと、エンジン作るマラソン的な問題と、あと車を作って出題者側にも周るというような。みんな評価してないえど、特に scraper とかみたいな実際的な要素は結構面白いと思うんだけどなぁ。今回程度の量だと誰がやっても変わらないですけど。あ、ただ最初の敷居は高すぎでしたね。実際的な要素みたいなのを最初に持って来れたらとっつきやすかったんじゃないかなと思うけど、どうすればそんなことになるのかは知らない。
あとはサーバは特に最後の投稿ラッシュを耐えたのは立派だったと思う。途中多少ダウンタイムがあったけど、まぁ問題のあるような長さではなかったと思う。
