ICFPプログラミングコンテストが始まっています。
今年は、宇宙船を操縦して4つのミッションをクリアする課題です。去年は惑星探査車の操縦でした。
去年は環境(live CD)が配布されて、その環境で動かしていました。今年は仮想マシン上で動かすので、仮想マシンの作成から始めないといけません。
仮想マシンを作るところから始めるのは2006年, 2007年もそうでした。2007年のように仮想マシンを作ること自体が難しくて入り口にすらたどり着けないということはなく、今年の仮想マシンはかなりシンプルです。
仮想マシンのレジスタはPCと比較結果を入れるstatusの2つだけです。アキュムレータもないので、演算結果は全てメモリに格納します。また、PCを操作する命令もないので、ストレートに実行されるだけになります。0番地から開始して最終番地まで実行して、おしまいです。ハーバードアーキテクチャなので、プログラムとデータは別の空間です(さらにはI/O空間も別です)。つまり自己書き換えコードも存在しません。メモリ空間は14ビットなので16kバイトです。
宇宙船の操作は、以下を繰り返します。
(1) プログラムとメモリの初期値を読み込む
(2) 入力ポートにデータを設定する
(3) 仮想マシンを動かす
(4) 出力を読み取る
(5) (2)に戻る
仮想マシンの仕様やミッションについては開催ホームページからpdfをダウンロードできます。宇宙船(仮想マシン上のプログラム自体)は、メールアドレスを登録するとTeam Pageからダウンロードできるようになります。今、見てみたら仕様書がV1.6になっています。
参加者のすることは、宇宙船を制御するプログラムを書くことです。うまく制御すると点数が高く(低く?)なるようで、点数を競います。
主催者に提出するのは、制御プログラムそのものではなく、どのタイミングでどんな入力を与えたかを示すバイナリファイルです。これなら、どんな言語を使っても平気です。去年の実行ファイルの提出よりはスマートです。なんか2007年と2008年のいいところを合わせた感じになっています。宇宙船の仕様というか動作を知るために仮想マシン上のコードを読まないといけないのも2007年と似ています。
というわけで、概要はなんとなく分かったので、仮想マシンのコードでも書いてみようと思います。逆アセンブラも必要そうです。
6/29 追記 結局、コンパイラを書いちゃいました。って、肝心の問題の方はほとんどやっていません。物理というか数学というか、むずかしいです。最初っから、式で考えるのは諦めて、数字を変えながら、グルグル回すプログラムを作ってたりします。課題1の4つのコースはなんとかできました。そもそもブレーキを踏むと、なんで楕円な軌道になるのかさっぱりです。
上で宇宙船と言っているのは、全て衛星(satellite)の間違いです。英語もさっぱりだあ。
一応、全員のランキングが見えるんですが、下の方に載ってます。同じ数字がいっぱい並んでいるのは、たぶん式で解いた人達なんでしょう。これから課題2を考えてみようと思います。課題1は軌道に乗せればおしまいだったけど、課題2は別な衛星の1k以内に近づかないといけません。さてさて、どうすればいいのやら。今日というか、明日の夜中の3時までになんとかなるんでしょうか。
6/30 追記
今日の夜中の3時に無事終了したみたいです。結局、寝ちゃって課題2はしませんでした。今公開されているランキングは終了4時間前のものみたいです。その段階では249位でした。最終結果はICFPという国際会議で発表されます。
今更ながら、wikiのHohmann transfer orbitの記事を見ました。計算式が載っていて、試しに代入してみるとぴったりではありませんが、それっぽい数値が出てきます。うーん、計算式なしでやってたなんて、かなりの時間の無駄でした。出てくるのは最初の加速と2番目の加速と、あとは2番目に加速するまでの時間の3つです。この3つを力任せで探索してました。そのせいか計算式で計算するより、少しだけ点数がよくなっています。これは当たり判定が1kmあるので、当たり判定のあるあたりだけコースに入っていて、その先は知らないみたいなコース選びだったということだと思います。
物理関連だということで、おもいっきりやる気をなくしてましたが、wikiをちゃんと読めば普通に計算できたんですね。しくしく。
上でコンパイラと書きましたが、正確にはCへのトランスレータです。代入文くらいしかないので、ひたすら対応するCのコードに変換しているだけです。
課題2は既に別の軌道にいる人工衛星とランデブーする問題です。同じ軌道に入るのは課題1と同じです。回転速度は半径だけの関数なので、もう一つの人工衛星も同じ速度で回っています。なので、軌道に入っただけだと、速度が同じ同士でいつまでたっても追いつくことはありません。ちゃんとは解いていませんが、最初に時間あわせのための待ちを設けて、必要なだけ待ってから軌道移動すればぴったりの座標にいけるはずだと思います。課題3は相手が円でなく楕円の軌道になっています。これも時間合わせと、さらには2番目の加速で同じ楕円軌道になるようにしてやらないといけないはずです。たぶん楕円の一番底でランデブーします。課題2と違うのは、ランデブーするタイミングも合わせてやらないといけないことだと思います。ってか、そこまで分かっていて、なぜ手が動かないのか不思議です。課題4は問題すら見てません。
課題1の軌道変更の様子です。
グラフはエクセルで書きました。プログラムはx, y座標をprintfするので、ファイルにリダイレクトして、エクセルシートにコピペしています。xとyの間をTABにすると直接別の列になってくれるので、即時にグラフも更新されます。って、原始的ですね。
主催者から、各データがダウンロードできるようになっていますが、パスが間違っていて、ダウンロードできません。URLからbinaries/を削ってやるとダウンロードできるようになります。
とりあえず色々と楽しませていただきました。主催者のみなさまありがとうございます。参加者の皆様ごくろうさまでした。
今年は、宇宙船を操縦して4つのミッションをクリアする課題です。去年は惑星探査車の操縦でした。
去年は環境(live CD)が配布されて、その環境で動かしていました。今年は仮想マシン上で動かすので、仮想マシンの作成から始めないといけません。
仮想マシンを作るところから始めるのは2006年, 2007年もそうでした。2007年のように仮想マシンを作ること自体が難しくて入り口にすらたどり着けないということはなく、今年の仮想マシンはかなりシンプルです。
仮想マシンのレジスタはPCと比較結果を入れるstatusの2つだけです。アキュムレータもないので、演算結果は全てメモリに格納します。また、PCを操作する命令もないので、ストレートに実行されるだけになります。0番地から開始して最終番地まで実行して、おしまいです。ハーバードアーキテクチャなので、プログラムとデータは別の空間です(さらにはI/O空間も別です)。つまり自己書き換えコードも存在しません。メモリ空間は14ビットなので16kバイトです。
宇宙船の操作は、以下を繰り返します。
(1) プログラムとメモリの初期値を読み込む
(2) 入力ポートにデータを設定する
(3) 仮想マシンを動かす
(4) 出力を読み取る
(5) (2)に戻る
仮想マシンの仕様やミッションについては開催ホームページからpdfをダウンロードできます。宇宙船(仮想マシン上のプログラム自体)は、メールアドレスを登録するとTeam Pageからダウンロードできるようになります。今、見てみたら仕様書がV1.6になっています。
参加者のすることは、宇宙船を制御するプログラムを書くことです。うまく制御すると点数が高く(低く?)なるようで、点数を競います。
主催者に提出するのは、制御プログラムそのものではなく、どのタイミングでどんな入力を与えたかを示すバイナリファイルです。これなら、どんな言語を使っても平気です。去年の実行ファイルの提出よりはスマートです。なんか2007年と2008年のいいところを合わせた感じになっています。宇宙船の仕様というか動作を知るために仮想マシン上のコードを読まないといけないのも2007年と似ています。
というわけで、概要はなんとなく分かったので、仮想マシンのコードでも書いてみようと思います。逆アセンブラも必要そうです。
6/29 追記 結局、コンパイラを書いちゃいました。って、肝心の問題の方はほとんどやっていません。物理というか数学というか、むずかしいです。最初っから、式で考えるのは諦めて、数字を変えながら、グルグル回すプログラムを作ってたりします。課題1の4つのコースはなんとかできました。そもそもブレーキを踏むと、なんで楕円な軌道になるのかさっぱりです。
上で宇宙船と言っているのは、全て衛星(satellite)の間違いです。英語もさっぱりだあ。
一応、全員のランキングが見えるんですが、下の方に載ってます。同じ数字がいっぱい並んでいるのは、たぶん式で解いた人達なんでしょう。これから課題2を考えてみようと思います。課題1は軌道に乗せればおしまいだったけど、課題2は別な衛星の1k以内に近づかないといけません。さてさて、どうすればいいのやら。今日というか、明日の夜中の3時までになんとかなるんでしょうか。
6/30 追記
今日の夜中の3時に無事終了したみたいです。結局、寝ちゃって課題2はしませんでした。今公開されているランキングは終了4時間前のものみたいです。その段階では249位でした。最終結果はICFPという国際会議で発表されます。
今更ながら、wikiのHohmann transfer orbitの記事を見ました。計算式が載っていて、試しに代入してみるとぴったりではありませんが、それっぽい数値が出てきます。うーん、計算式なしでやってたなんて、かなりの時間の無駄でした。出てくるのは最初の加速と2番目の加速と、あとは2番目に加速するまでの時間の3つです。この3つを力任せで探索してました。そのせいか計算式で計算するより、少しだけ点数がよくなっています。これは当たり判定が1kmあるので、当たり判定のあるあたりだけコースに入っていて、その先は知らないみたいなコース選びだったということだと思います。
物理関連だということで、おもいっきりやる気をなくしてましたが、wikiをちゃんと読めば普通に計算できたんですね。しくしく。
上でコンパイラと書きましたが、正確にはCへのトランスレータです。代入文くらいしかないので、ひたすら対応するCのコードに変換しているだけです。
課題2は既に別の軌道にいる人工衛星とランデブーする問題です。同じ軌道に入るのは課題1と同じです。回転速度は半径だけの関数なので、もう一つの人工衛星も同じ速度で回っています。なので、軌道に入っただけだと、速度が同じ同士でいつまでたっても追いつくことはありません。ちゃんとは解いていませんが、最初に時間あわせのための待ちを設けて、必要なだけ待ってから軌道移動すればぴったりの座標にいけるはずだと思います。課題3は相手が円でなく楕円の軌道になっています。これも時間合わせと、さらには2番目の加速で同じ楕円軌道になるようにしてやらないといけないはずです。たぶん楕円の一番底でランデブーします。課題2と違うのは、ランデブーするタイミングも合わせてやらないといけないことだと思います。ってか、そこまで分かっていて、なぜ手が動かないのか不思議です。課題4は問題すら見てません。
課題1の軌道変更の様子です。
グラフはエクセルで書きました。プログラムはx, y座標をprintfするので、ファイルにリダイレクトして、エクセルシートにコピペしています。xとyの間をTABにすると直接別の列になってくれるので、即時にグラフも更新されます。って、原始的ですね。
主催者から、各データがダウンロードできるようになっていますが、パスが間違っていて、ダウンロードできません。URLからbinaries/を削ってやるとダウンロードできるようになります。
とりあえず色々と楽しませていただきました。主催者のみなさまありがとうございます。参加者の皆様ごくろうさまでした。