Coding Memorandum

プログラミングに関する備忘録

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

ICFPC 答え合わせ

早速,解法について書かれていたので参照させて頂きました。

ありゃ?ゲートの解析までは全く同じ考え方のようです。

ゲートはカルノー図で表される(ステートレス)であろうと想定し,入力と出力の組み合わせが分かっているので,カルノー図の全通りで探索すれば良いと「3^9=19683(片ピンのカルノー図パターン数)の二乗(L,Rピンの組み合わせ)×3(ループ接続したピンの初期値:0/1/2)」で探索をかけたのですが・・・解が見つかりませんでした。上の記事によればカルノー図でいけそうですね???

どうやらcircuit構文の解釈に間違いがあった・・・ようですが,まだよく分かっていません。なにせ,同じ入力シーケンスでありながら異なる出力値が出るという結果を得てしまっていましたので。もう少し,色々な方の記事をウォッチしてみます。

結局,ゲート解析の結論として「ゲートは何かレジスタを持ったステートマシンだ」という方向に走ってしまいました。これが敗因のようです。いま冷静に考えると,ここまで問題を難しくされることももないのかなぁとも思います。


7/7追記

どうやら,circuit構文の'X'の解釈を完全に間違えていたようです。
'X'表記のゲートは「a special "external" gate」だと誤解してました・・・。「'X'はspecial gateの接続点を示す」が正解だったようです。 この解釈でゲート解析を実行したら無事にカルノー図を得られました。

しかし・・・key circuitの例を見れば,自分の間違いに気づいてもよさそうですが。そのときは,'X'はNCを示すと思い込んでしまっていました。

このため,直列に接続したと思い込んでいた回路は実際にはフィードバックを含む回路となっていて,先の記述の通り「同じ入力シーケンスでありながら 異なる出力値が出る」という事態を起こしていました。

スポンサーサイト

ICFPC 2010

今年のICFPコンテストは,まったく良いところなく終わってしまいました・・・

言い訳じみれば,昼間は息子からの“かまって”攻撃(キーボードへのアタック)が頻繁に繰り返され,土曜と月曜は我が家の新築プロジェクトで急遽時間を取られてしまった等々・・・ICFPに割ける時間が少なかったかと。去年は完全にフリーな3日間を確保できましたが,そんなことは滅多にあることではなく。

まぁ実際のところは,時間があったとしても今年の問題は解けなかったようにも思います。初めのステップであるCircuitの構文を理解するのにはエラく時間がかかってしまいましたし(気付けば,どうということもないものでしたが),次のステップの鍵に至っては難しさに心が折れました・・・

なんとなく薄々と,たくさんのCircuitをWebサーバに投げてレスポンスを見るゲーなのかと思い始めるにつれ,簡易にHTTPを投げる環境がないことから,段々とモチベーションが下がっていったという感じでした。何かscript言語を一つはマスターしようとRubyの本を買ってはいたのですが,今のところ手付かずで・・・

なにか思いもよらない解法があるのか,他の人の解法を見るのが楽しみです。

しかし・・・ここのところプログラムコンテスト関係は絶不調です。Google Code JamはRound1でNG,TCOはSRM,Marathonともに初戦落ち・・・もう少しこっち方面に時間を取りたいところですが,しばらく難しそうです。

大ショック!!

ICFP Contestの参加者のブログを見て回っていて,次の記述に目が点となりました。
4002も2,3個拾えたので・・・

http://www.f13g.com/blog/2009-06-30/

400xは,全部回らなくても得点になったんですかぁ・・・と!
スコア説明のところを全く読み飛ばしていました。orz
今見たら,2/10^6秒後にスコアが入るよう書いとりますし。

400xは給油がネックなだけで,ある程度は回れていたのでとても無念です。
最初に一読したときに,Clear Skiesの得点説明はまだ不要と読み飛ばしたのが敗因でした。

    楕円方程式不要のシミュレーション方法を考え・・・
    給油不要で行くことを狙った省エネ航法を考え・・・

これらが報われるチャンスがあったのかと思うと残念でなりません。
「ルールはよく読むこと!」を肝に銘じたいと思います。

# Problems Solved が 12 で止まっている人の中には,私と同じ境遇の人がいるはず・・・

ICFP Contest 2009 メモ

何をするか

今回の問題は衛星の軌道制御でした。得点を得るためには次のことしていきます。

  1. VMの実装 :VM仕様に合わせ作る
  2. VMプログラムのダウンロード:これが衛星のシミュレータになっている
  3. 衛星制御の実装:指定された課題に応えるように衛星を動かすプログラムを作成。
                VMのI/Oポートに数値を書けば衛星の速度・軌道を変えられる。
  4. 衛星制御のトレース情報を作成:タイミング(時刻)とI/Oポートへの出力値をファイル化する
  5. トレースファイルをUp:得点をGet!

問題は全部で4タイプあり,それぞれVMのプログラムが提供されています。
以下,それぞれの問題に対しての取り組みを書いていきます。

Hohmann

■ 円軌道にある衛星を別の円軌道へ移動させます。

衛星の軌道変更は,“Hohmann遷移”が使えるとヒントが出されています。これに従って制御するだけでOKです。数学の問題でした。

問題1003だったか1004だったかは,遷移する軌道が遠く誤差で近づけなかったため,一旦近くの軌道に遷移して,もう一度ターゲットの軌道へ遷移する2段階遷移としました。

Meet and Greet

■ 円軌道にある自衛星と別の円軌道で回っている衛星とをランデブーさせる。
    1km以内に900秒間いればOK

 まずは,お互いの衛星が円軌道であるので,簡単な計算で2つの衛星の位置を割り出せると考えました。一つ前の問題の流れを汲んで,数学的に解こうとチャレンジしました。

しかしながら,実際に試すと誤差が大きくて1km以内に収束できません。ここで,しばらく足止めをくってしまいます。直径が大きい値のため三角関数の誤差が影響か?など迷走していました。モチベーションも下がってしまって,早期リタイアを考えてしまうほどでした。

だいぶ経って,これはシミュレーションの問題だと気付きました。衛星は秒速数km/sで動いていて,かつVMは1秒単位の粒度のシミュレータなので,数学的な計算で上手くいくわけがないと悟りました。

VMに状態のsave(),restore()を追加して,値を変えながらトライすることで解を見つけることができました。解の探索は焼きなまし的に探索点を段々狭めるように組みました。 

Eccentric Meet and Greet

 ■ Meet and Greetの条件で,軌道が楕円になる。

Hohmann遷移は地球をはさんで自衛星の反対側に到着するという点に着目しました。
自衛星と地球を結ぶ直線とターゲット衛星軌道の楕円の交点がランデブーポイントになります。最初に一巡観測して,楕円の方程式を求めました。

第1段階のシミュレーションでは,Hohmann遷移の発射位置を決めます。
第2段階のシミュレーションでは,速度を決定します。
最後にランデブーポイント到着後に微調整を行って,OKとなります。

楕円軌道からのHohmann遷移は,現在の速度ベクトルに対して,地球と自衛星の直角方向(接線方向)の速度となるようΔvを与えてあげました。到着後は,ターゲット衛星の速度ベクトルと同じになるよう噴かしてあげます。

Operation Clear Skies

■ 11個の衛星とランデブー(一瞬会えばよい)する。
    燃料を補給するrefuel stationと新たな重力源“月”が加わります。

月に近い衛星は,もはや楕円軌道ではなく,前述の方式が封じられました。他のものも軌道周期が長く,一巡観測することが困難でした。
また,refuel stationは自衛星と反対向きに周回しているので,近づくことがシビアになります。

色々な方法にトライしたのですが,どれもNGで,残念ながら力尽きました。

ICFP Contest 2009 終わりました

ICFP Programing Contest 2009 が終わりました。
今回はじめて参加しましたが,3日間疲れながらも楽しめました。来年も,(なかなか難しいですが)時間を割けれたら参加したいと思います。
今回の結果は,いま一つの3問目までで最後の Clear Skies は Give up でした。

 こまかな話はまた後で書いてみたいと思います。参加されたみなさまお疲れ様でした。

次のページ

FC2Ad

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。