やったことをまとめておきます。 まあ問題の意図を盛大に勘違いして別のゲームを遊んでいた （与えられたシナリオファイルを最適に解くだけじゃなくて、 もっとジェネラルな自動ソルバを作らなければいけなかったらしいorz） のでスコアは問題外な感じですが、 面白かったのでよしとしよう。
今回は、地球の周りを飛んでる人工衛星に命令を送って他の人工衛星やデブリと接触できたらスコア＋＋、 という、(仮想の)人工衛星制御プログラムを作るコンテストでした。 → shinhさん にならって自前ビジュアライザを 動画にするとこんな感じ。
2003年 や 2008年 の問題に結構近いものがありますが、 今回はとにかく、燃料の許す限り速度変化 ΔV を自由に与えられるという仕様が （自動でやるにしろ手動でやるにしろ） 素晴らしかった。 例えば「隣を飛んでる別の衛星と同じ速度になりたい」と思ったら1命令でそうできる。 2003 や 2008 のようなアクセル踏む/ブレーキ踏むだけの操作でコントロールするのは、正直、ストレスがたまる…。
問題読む → よくわからんがVM作ればいいのか → 後のことは読まず（ここら辺が伏線）にとりあえず作ろう → D言語で → 今までの経験上、VMが速くて困るわけはないが「もっと速ければいいのに」と思う事は確実にある → 速度重要 → インタプリタよりコンパイラ！ → バイナリをDのソースに変換するトランスレータを書く → もちろんCTFE+mixinで → できた → DMD(D言語のコンパイラ)が落ちる!! → mixinやめて普通のコード生成にしてもダメだなあ → 250行越える関数があると落ちる… → やむを得ん、Cだ。gccならこういう機械生成コードは慣れてるでしょう → できた → ポートI/Oは標準入出力 → この子をサーバと見立ててクライアント書く形でソルバーを書けばいいな
ソルバーはどの言語で書くか → とっさにC++でpopen的な関数で標準入出力両方開くやり方 思い出せなかった＆自分が即座にグラフィック扱えるのJavaだけだ＆チームメイトがJava使い → ここはJavaで → 書いた → 色々バグってる → 仕様書も色々バグってるらしい → 色々直したらそれっぽくなった → じゃあとりあえず100x用のビジュアライザ書いて → 一応解くべき問題の概略把握して → 寝る
起きた → 100xは、仕様書のAppendixに書いてあったタイミングで2回噴射すればいいらしい → 色々試行錯誤でやってみる → チームの人が Hohmann transfer orbit を見つけてきた → この式で一発だ！ → 全部式一つで解けるようになりましたバンザイ → 式一つにしている間に、仕様のsx sy: relative to earthを逆向きに解釈している、 ビジュアライザのy軸の向きが逆などのありがちなミスをせっせこ修正
ところで思ったのですが、CとJavaで標準入力でやりとりするくらいなら、 最初からVMもJavaに落として直接メソッド呼び出しでやりとりする方が速いのでは → 100倍速かった → そりゃそうですね
200xは、出発するタイミングを合わる段階が加わるだけであとは100xと同じ問題 → ホーマン軌道に乗るタイミングを手動だったり自動だったりの二分探索でみつけて100xと同じ式。全部解けた → 300xは楕円軌道らしい → 理屈はまったくわかってないけど、近日点と遠日点なら真円軌道と同じ場合のホーマン軌道の式で動けたり… → しばらく無駄にループして近日点と遠日点を観測した後ホーマン軌道発動、でそれっぽい動きをするのができた → さてどうやってターゲット衛星とランデブーするか。わからん → とか考えている内にチームメイトがだいたい解いてた。どうやったのかは理解してない
ところで3003だけ、手元では通るけどサブミットするとtimed outになるらしい → えー？VMのバグなら他のケースでもずれそうなもんだけど… → 3003だけものすごい長い軌道だから、誤差が積もるということかなあ → でも+-*/とsqrtと比較で誤差なんて…一応strictfpつけておいたりするか…ダメだ… → (数時間後)VMのコード生成時に、「doubleを10進数リテラルで埋めると誤差るからここは16進リテラルを使うぜ！」 ということは考慮していたのに16進リテラルを精度6桁しか出してないことが判明！俺はアホか！ 全桁出すようにしたら直った。バンザイ
さて、400x。 → 400x (4002以外) は、月の影響だとかあんまり気にせず 200xの解き方を多段に繰り返して次々ホーマン軌道を使ってランデブーを繰り返す → 1sec隣接すればいいので完全に相手の軌道に乗らなくてもいいし、こう、適当に。300xよりかなり簡単 → 近場のは回収できるようになった → ただ遠くはやっぱりずれすぎるなあ。4002は自分はわからないので人任せ。 僕は今回は裏方に徹するので、遊べる環境・ツールを作る作業に戻る → 「vmのステートロード・セーブ機能、ターゲット衛星が近づくとその辺りをズームアップ ＆ スローモーションにしてより細かい作業を可能にする」 → などの人力二分探索を手厚くサポートする機能をクライアントに実装
そして 100x や 200x の自動解がものすごい勢いでチームメイトの手により手動チューニングされていく… → それはそうと 400x、スコアを稼ごうと思うとホーマン軌道を使っていちいち安定円軌道に乗るのを繰り返していると遅い → 結局、一個回収したら次をダイレクトに目指す最適なロケット噴射、を繰り返す解を探す方向でひたすら手作業 → やたー4004全部できたよー → サブミットしたらCRASHED!って言われる → この期に及んでまだ誤差か！ → 12個目を回収した後もローカルで走らせてみた → 月の重力でちょうどピッタリ進路が鉛直方向に向いてまっすぐ地球に突っ込んでる！すげえ → 最後にちょっとだけ加速して回避
基本的に、「一個取ったタイミングで即座に次に向けて噴射 / ただし次のデブリの予定軌道よりやや上まで行ける程度の強さで鉛直方向に加速 / あとは予定軌道到達時の地球との相対ラジアンで水平速度を二分探索 / あまりに早く着きすぎる場合は現在の高度で円軌道をキープできる速度に変えてしばらく待ってから↑をもう一度トライ」 なので、そのままアルゴリズムに落とせるなーとは思ったんですけど。 ただ、4004みたいに逆回りな時の相対速度10000m/sの衛星同士を 1s単位の離散化のなかで1000mの範囲に入れる、とかどういう扱いになるのかよくわからなかったのでやめたのでした。
あとはなんだろなー。VMのコード生成の最適化を色々考えてました。 結局、不要命令の除去と、CMPZのあとにすぐPHIが来るケースはstatusを経由せずに直接if文に落とすのだけ最後に使ってます。 データメモリを配列じゃなくて変数にしたりread onlyなものはstatic finalにしたり…は、 意外と全く高速化しなかった。ローカル変数にできれば違いそうだけどメンバ変数では大差ないのかな。 CMPZの前に来る引き算との融合は実装したけど誤差の問題が本当に大丈夫か自信がなかったのでナシ。
Solutions for the top ten teams will be validated, after the contest concludes, by generating a new collection of scenarios for each problem. The team's sub- mitted source code for the problem solutions will be be executed on these new scenarios to verify that solutions submitted are general solutions to the problem and that those solutions utilize only the sensor output exposed as described in the problem description.
とか書いてあることに今頃気づいた！これはダメだ！！仕様書はちゃんと読みましょう。
ICFP 2009 Programming Contest 出てました。チーム名 pepsiso です。@tsukuno と組んでます。 ペプシしそ がマイブームだったので彼が寝ている隙にチーム名がこうなりました。 言語は最初 D で書き始めてたんですが最終的に Java になりました。あと微妙に C++ 。 4時間前のフリーズされたスコアボードでは駆け込みでトップですけど、 どうなんだろう…そこから大して伸びてないので絶対抜かれまくってる気がする。
細かいことはそのうちまとめます。とりあえずおやすみなさいzzz。
Gray code#C に @pi8027 さんが挑んでいるのを見て面白そうだったので、 つられて参戦してました。
最初は wikipedia に書いてあった「数 n のグレイコードは n ^ n/2」 という式でやってました。109B まで進めたところで、 トップと10B差以上あるのにどうにも縮まなくなったのでアルゴリズムの差だろうと思って考え直し。 「数n-1のグレイコードと数nのグレイコードの違ってるビット ＝ nの二進表記で一番下位の1のビット」 を使うと、ずっと使いたいけど使えなかった printf("%o") が使えるようになると気づいてこっちになりました。
b,g,c; // b:二進数表記, g:グレイコード, c:変化するビットを入れる一時変数 (全部初期値0)
main(n) { // n:入力
for(gets(&n); b < 1<<n; c=-b&b)
printf("Gray code n=%1$d\n%0*o"+!!b++*17, n&=7, g^=c*c*c);
}
結局トップにはさらにここから9B差がついていて、かなわんなーという感じなのですが。 かなわんなー。
なんだか個人的に、for文の4カ所 for(A;B;C)D; がどれも空文にならず、コンマを使った複数にもならず、
きっちり一つずつ埋まるととても嬉しくなってしまいます。
Even 命令と Odd 命令の数が揃ってうまく埋まったときのような気分だと思う（適当な想像）。