kt3k 日記

スポンサーサイト

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

ICFP contest 2010 参加

ICFP contest 2010 (6/18 - 6/21) に参加しました。

6/18日午後9時スタート
以下経過時間ごとの記録。

00時間 スタートと同時に問題を読み始める。一部、twitter などで問題見れない発言があったけど、自分は普通に見れた。
05時間 gate の文法がやっと分かり、ちゃんと繋がったゲートを作れるようになる。
30時間 ゲートが2入力2出力の関数じゃないかという気がしてくる。
31時間 「ハイスコアが高すぎてやる気がしない」と発言する。
33時間 最初のモデルでの gate の評価が間違っている事が分かる。
39時間 backward wire の意味を変えてもう一度 gate を評価してみると、入力から出力が正しく導き出せる事に気づく。(gate の意味が分かった!
42時間 一人でやる事に限界を感じたので、hirose 君をチームに誘う。(チームのマージは ok 情報より)
45時間 gate のパーサー&シミュレータを作って、出題の入力&ゲートを計算して、key prefix を知る。
48時間 6 gate で key prefix できるよ情報を信じて、6 gate を brute force するコードを書いてみる。python で書いてるのと、アルゴリズムが多分バカなせいで、大会時間内に終わりそうな brute force にならない。悔しいので、Amazon で普段使わない良いインスタンス起動させて、そちらで計算させてみると、3倍ぐらいスピードが違って、Amazon sugeeee と思うが、プログラムがダメなので、結局計算できず、余計悔しい思いをする。
51時間 hirose 君が定数を出す gate を発明。
55時間 hirose 君が任意の3進列を出力する gate を返してくれる関数を書いてくれた。
57時間 一問目が解けた。
64時間 hirose 君から、111110 ていう fuel で、いくつか解ける車があるよと教わる。
66時間 コマンドラインからサーバーに投稿できるツールなどを作る。
67時間 完全に自動投稿するツール作成。111110 fuel を投稿してるだけで、どんどん点が入る。
71時間 2 tank で dimension mismatch しない fuel を発見。自動投稿にかける。
72時間 終了 109位

gate 解読までが難しすぎで、そこまででかなり疲れて
しまいました。(そこまでが分からないと、
ポイントが全く入らないので、精神的にも疲れる。)
(でも、そこまでを瞬殺している人もいて驚きました。)
毎年の事ながら、問題の本質的なアルゴリズム的部分には
ほとんど触れられずに終わってしまいました。

最後の方で、自動投稿しながら点がぽんぽん入っていった時とか、
サーバーの仕様がちまちま変わっていく様子とかは
ライブ感があって、コンテストの内容はともかくとして、
祭りっぽくて楽しめました。

スポンサーサイト

iPhone アプリ作成

会社で、主に加藤さんと協力して、The Best Sellers という iPhone アプリ
をリリースしました。amazon の新着書籍ランキングを表示するだけと
いうアプリで、存在意義自体クエッションマークなアプリだと思いつつ
作っていたけど、いくつか好意的なレビューも貰えてほっとしました。

http://d.hatena.ne.jp/comboo/20091115
http://osuban.jp/?p=3671#more-3671

技術的には、下からせり出してくるピッカー(ドラム状選択肢)の中身を
入れ替える瞬間とか前後で、アプリが落ちまくるところをデバッグするのが
大変だった。

thebestsellers

→iTunes
→AppAdvise

ICFP Contest 2009 (3)

ICFP Contest 2009 3日目

問題2 は、与えられた2つの周回軌道に乗っている衛星のうち、片方を
動かしてランデブーさせなさいという問題。
(ランデブーの条件は1km圏内に900秒(以上)とどまる事)
問題1 と同様に、燃料制限があるので、あまり無茶な動かし方をすると燃料切れ
でクラッシュしてしまう。

自分が思いついた解答は、問題1のホーマントランスファを利用して、
相手の軌道に対してホーマントランスファしたときに、相手の軌道内で、
さらに同じ位置にぴったり合うようなタイミング(これは計算できる)まで、
待ってからホーマントランスファするというもの。

これを実装したら、2001, 2003, 2004 の3問が解けて、100位ぐらいになった。
(2002 は目標の衛星が遠過ぎたため、精度的にギリギリ解けなかった。)

その後、2002 を解くために相手とかなり近い位置に居るとき用の軌道補正プログラム
を書いて、2002 を安定して解けるようになった。

2002 を調べてる最中で、どうも、点数が自分で計算したものと
サーバーの出力が違うことに気づいて、vm の演算の丸め誤差で
なにか狂ってると考えて、その辺のコードをかなり長時間眺めた。

最終的に、トレースのタイミングが一秒ずれていた(一秒未来の噴射のデータを送っていた)
ことに気づいて、これで、10点アップ。(このデバッグをしたときが大会中一番嬉しかった。)
これが最後の更新になって、そのまま終了。暫定143位。

pepsiso

ICFP Contest 2009 (2)

ICFP Contest 2日目

VM の動作が安定してきた。
2007 年のようなはまり要素が無かったので、割と素直に出来たと思った。

.osf ファイルヘッダーの、0xCAFEBABE をリトルエンディアンにしていないことに気づけなくて、
そのまま大会終了するところだった。Ymgve さんという人の spoiler を見て、
やっと間違いに気づいた。

python で書いた VM が遅かったので、psyco を初めて使った。
簡単に導入できて、使い方も簡単で、効果もハッキリ見えてすごいと思った。

問題 1 はある円軌道上に居る衛星を、指定された高さの軌道に移動させなさいという問題。
問題の題名が ホーマントランスファーで、その名のとおり、hohmann transfer という衛星の
移動のさせ方を使うと解けるようになっていた。
wikipedia の、hohmann transfer の式をそのまま実装して、4シナリオ(初期配置)すべて
解けた。まったく同じ点数の人が、20人ぐらい居たので、たぶん同じことをやったんだろうと思った。
でも、点数を眺めていると、どうも、 hohmann transfer は使ってないという人も結構
いるっぽい感じだった。

icfp20090628

(問題 2 を計算している様子)

ICFP Contest 2009 (1)

毎年恒例の ICFP Contest に参加。
今年は、衛星のシミュレーションで、
衛星の推力をコントロールする事で、
指定された軌道に乗ったり、別な
衛星に近づいたりせよ、という問題。
シミュレーションをするための実行環境が
独自定義のバイナリフォーマットで与えられていて、
それを解釈、実行することも、参加者の課題。

icfp20090627

(シミュレーションの実行マシンを解釈してる様子)

プロジェクトオイラー、久々に

euler_portrait

久々に Project Euler を2問ぐらい解いた。
ランキングが復活したり、スタティスティックスが復活したり、
サービスが向上(回復?)していた。
フォーラムを見ていたら、最近 anarchy golf - python でよく見かける hallvabo さんが
Norway norway_flag の人らしいということが分かった。

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