#icfpc2012  

Wrap-up of ICFP Programming Contest 2012.
http://icfpcontest2012.wordpress.com/

ちょうど日本の3連休にかけて行われていた、毎年、恒例の72時間耐久プログラミングコンテスト ICFPC 2012に、今年はじめてまともに参加しました。反省点だらけなので、まったくまとまっていないけど忘れないうちに箇条書きで。:)

Team: hayato
Team members: Hayato Ito


環境
- 問題を読み始める。どの言語を使用するかこの時点でまったく決めていなかったけど、なんとなく C++ かなーと思っていたけど、C++ とか使って Functional Programming の大会とかあんまり自分に対して教育的効果が少ないと思って、Scala にする。
- Scala 書くのは実は半年ぶりくらいで、この時点で、何かがもうすでにおかしい。たぶん、Google AI Challenge 以来。
- いきなり環境のセットアップから始める。Emacs とか今時ないわーと思い、Eclipse + scala-ide を使ってみようと思う。
  (注意: すでにコンテストは始まっています。)
- Eclipse を Emacs キーバインディングにするための設定を1時間くらいやりだす。
  (注意: もう一度いうとすでにコンテストは始まっています。)
- 結局、ぜーんぶ、捨てて、Emacs + ensime + sbt で書きだす。(・∀・) わーい。
- GDB に相当するものが、Scala にあるのかと思って探そうと思ったけど、「まーいいや、printf で」と思う。
- Scala 上で使える Profiler とか知らないけど、「まーいいや。必要になったら考えよう」と思う。

反省点) 環境は事前に整えておきましょう。


Simulator
- Simulator そのものはほぼ一瞬で書き終わる。Scala 楽だー。
- 盤面の状態は、Array[Array[Char]] で管理する。これはほぼJavaのネイティブの配列と同等。
- Simulator は早さが命。特に今回みたいに探索勝負みたいなお題だと、早いに越したことはない。でも定数倍の早さとか探索方法のちょっとした工夫で簡単に勝てるので、あんまりスピードは気にしないことにする。そもそも気にするなら、最初からC++使う。
- 単独のロボットの移動シーケンスは、Simulator で正確にシミュレートできているんだけど、後で述べるA* Search と組み合わせると、なぜか意図せず状態が壊れていて、キャッシュミスが起きているような気がする。
- なかなか原因を発見できす。.....デバッガー使いたいです。
- 「そもそも、Functional Programming Contest なんだから、Mutable なもの使うのやめようぜ。」と思いだす。
- Array[Array[Char]] ではなく、Seq[Seq[Char]] にする。この時点で、State は完全に Immutable になる。
- そして、map の更新は:
  def updated(map: Seq[Seq[Char]], x: Int, y: Int, c: Char): Seq[Seq[Char]] = map.updated(x, map(x).updated(y, c))
  というものになる、この時点で、「ないなー」と思いつつも、Immutable な世界を堪能しだす。
- Immutable にした瞬間、バグフリー(と思われる)になる。Immutable って素晴らしい。コンテスト参加者としてはどうなの?って気がするけど、気にしない気にしない。これはFPの大会と言い訳を始める。

反省点) もうなんか全体的にだめパターンな気がする。ちゃんと目標を事前にきちんと設定しましょう。まあでもこのあたりが一番楽しかった気がする。


AI
- 最初はラムダをほぼ Greedy にとる超シンプルなやつを書く。これは一瞬。
- いくつかのサンプルマップで遊びだす。人力でも解けないやつがあって、私が解けないのに私のAIがこれを解けるようになるのか、と今後の展開に期待する。
- Greedy じゃ絶対とけないMapがあるので、「とりあえず A* かなー」と思ってまじめに探索してみる。h(state) という評価関数を適当にでっちあげる。
- サンプルmapでいくつか試す。
- flood1 と trampoline1 が解けない。なんとなく悔しいので、これ以降は、flood1 と trampoline1 を特別なハックなしで、General な方法で解くことに全力を注ぐ。
 (注意: この時点で間違っています。特定のMapだけで評価するのはとっても危険なんです...。まあ本人が楽しんでいたので :)
- このあたりでだんだんいい加減になってきて、'return' とか恥ずかしげもなく使い出す。
  (注意: これはFPの大会です。)
- ようやく、flood1 が解けるようになる。(・∀・)
- そもそも、他のMapでぜんぜんAIを評価していないことにこのあたりで気づく。

反省点) 評価大事。ちゃんと全マップにたいしてAI走らせて数値化しましょう。ひとつのMapにこだわるとか愚の骨頂ですよ。まったくもー。


提出
- 提出用パッケージ作成のスクリプトを書きだす。
- どうせScalaだからどんな環境でも動くはず、指定環境でテストしないで、そのままだそうと思ったけど、さすがに踏みとどまる。
- Linuxの指定VMを動かすために、Mac に Virtual Box とかインストールしだす。
  (注意: 事前にやっておきましょう。)
- 「あれ、SIGINT、受け取れないんじゃない?」と気づく。scala コマンドは、Java を Exec しないで、普通に起動するので、Javaは別プロセスになる。へー。
- 「SIGINT受け取れないと、さすがにほぼ0点だなー。」と思い、Debian の scala コマンドを修正しだす。結局、myscala コマンドをつくって、ようやくSIGINT が直接受け取れるようになる。
- 提出は、Google Drive で 共有とかおしゃれだなーと妙なところで関心する。


...全体的にまったくTodoを消化しきれないまま、終わった感じでした。複数人チームだったら、もっと作業が分担できるのかも。でも一人でどれくらい戦い抜けるか試してみたかったんです。この反省をいかして、来年はもう少しがんばります。運営者さんありがとうございました。楽しかったです。

Code (の一部): https://gist.github.com/3123427
Shared publiclyView activity