ICFPC 2014.

でした。 with @kinaba @fuqinho
完全に、年一の日記になっている。。。
まぁ、いつものごとく、自分やったことだけ。

初日

出張中のため早朝(っつーか夜明け前)開始。
すでに脳みそが死んでいる。

問題読む。ひたすら長い。
1.5h くらいは余裕でかかった。英語つらい。
まー、VM書く。振り返ると、いきなりAIから書き始めればよかったかなぁ。
VM最後まで bug ってたっぽい。細かいところの挙動が明らかにおかしい。

実装してると、明らかに spec に穴が。まぁ、例年通り。
適当に書ききって動かし始める。
Visualizer 御用達:http://en.wikipedia.org/wiki/ANSI_escape_code

並行して C++ で書いてもらってた AI を動かしてみると、それっぽい。
夕方(夜) kinaba さんが合流。
夕食食いながら、まぁ LISP ですかね、ということで、
VMLISP compiler、AI 考える、と task を割り振る。

深夜(lightning division終了前)、寝落ちしたと踏んで、AI を C++ -> GCC に hand compile/assemble。
ラベルの解決するくらいの asm は書いておくべきだった。(毎年恒例の反省)
DBUGはさめないのつらい。
結局、bug とれず。 lightning division は放棄。
就寝。

二日目

まぁ、LISP compiler できてたので、LISP で AI を書き直す。
以降、基本的に AI を C++ から LISP に書く下請けプログラマをひたすらやる。

さくっと LISP compiler 動いてすごいなぁ、さすが kinaba 先生。
ただ、括弧の数一個間違えると、一瞬でメモリを食い尽くして、virtual box を抹殺する凶器であった。
あと、変数 typo すると SEGV で死ぬので、compile 時には gdb が必須。

ゴーストさんは、お任せして、ひたすら lisp と格闘。
Mapをassoc list で実装してたけど、遅くて使い物にならない。

  • > AVLを実装。12年ぶりくらいである。一発で動く。多分ここで今回のコンテストの運をすべて使い果たした。

このころから PC が熱暴走して亡くなりまくる。
コンテスト中、別なものと闘うのも例年の恒例。。。

三日目

とりあえず、fuqinho さんが動かしてた AI を聞いて、LISP で再実装。
なんか、人手があれば C++ compiler 書けばよかったんだがなぁ、と思ったりした。
とにかく LISP つらい。

関数つくって、0 で上書きする、という謎のテクニックが作成され、ようやくグローバル変数が導入される。
あと、時刻の計算とか。
この辺から LISP compiler がいろいろ直って、普通にプログラム書けるようになる。
型チェック欲しい。

らむだまんさん食われまくるので、いろいろ細かい修正。
とりあえず、全力で逃げるのと、Power pill を追いかけにいく、フルーツ待機。
敵がよってくると、うっかりクリアしてしまうので、高得点がとれない。
配列に O(1) で触れないのが、大変ストレスフル。

あと、胃痛で死に始める。やはり出張中はだめだ。。。
巨大マップ用に枝狩りをあちこち入れる。

一応 LISP なんだけど、どう見ても手続き型にしか見えないソースを書きまくる。
関数の最後の行だけ閉じ括弧が多い謎コード。最大 18 個だった(数えた)。

胃痛がやばくて、ちょっと仮眠。仮眠すばらしい。あと、三共胃腸薬。

チーム名が決まらない。コードネームにつかったFOOを、何か意味あるものにしよう、という話に。
いくつかあげたけど、全却下された orz。
チーム名も決まって submit 。
のこり 5 分、なんか、たまに AI が死ぬケースが見つかる。
見つかるんだが、謎過ぎる。そのまま終了。

なんかできた AI

とりあえず、pill 幅優先探索。近くになかったら、適当にありそうなほうに向かう。
ゴーストよってきたら、逃げる。power pill あったらそっちに向かう。
フルーツは最優先。2個出てなかったら待つ。うっかりゴール避け。
power pillの隣でまつ。ゴーストがよってきたら食いに行く。
power pill chain つなげまくる AI とか書いてみたけど、いまいちだったので、没。

くらいかな。簡単なマップだとそこそこ動く。
けど、ゴースト次第で運ゲー
ところで、world-1って、spec 違反じゃないんかね。2x2あるし。。。

反省

腕力にたよるのは、いい加減やめてみるべき。
C++は人間がコンパイルするもんじゃないな。
LLVM BE とか覚えておけば来年は役に立つ気がする。
IFPとそろったので C をどこかから調達()できればよかったなぁ。

compiler とか asm とかがもりもり作られていくのを眺めていた。
let が導入されたときに、refactoring して書き直したんだけど、
compile 結果が同一であったので、compiler の気持ちはわかっていたらしい。

まとめ

結局、あんまりちゃんと動けてなかったなぁ、という感じ。
出張しんどい。

いつも思うんだけど、VM 書く系の部分は、なんか validator あるとうれしいよなぁ、と思う。
コレとおっておけばいいよ、的な。
どうせ、Judge も spec にミス埋め込むし。人間だもの(みつを)。

今年は、心躍る感が若干弱かったなぁ。
AI の年はだいたいそうなんだけども・・・。

さて、寝よう。

雑感

今年のは結構いい感じのサイズだなぁ、と。「もう1日欲しい」というところで終わるあたりが、ちょうどいい。
主催のみなさまありがとうございました(と日本語で書いてもダメか・・・)
こういうの書いてるとやっぱり pattern match が欲しくなりますね。というか、matcher 書くべきだったかなぁ・・・。
くわえて、あちこち相互再帰してるので、変な無限ループに入るケースがなくなるように気をつけるのは、
だいぶ面倒だなぁ、と思ったり。
今回はC++だったんですが、メモリ管理やっぱりちょっと気を使いますね。まぁでもGCよりはマシかな。
チーム funny quotes はきっとメンバーの誰かがなんとかしてくれるハズ。
チームでわいわいやるの楽しいですね、やっぱり。ありがとうございました。
来年も出たいなぁー。

式のつぶし方

主にやってたのこれなのですが、結構いろいろあって、コンパイラ屋さん大変だなぁ、と思ったりしてました(小並感)。
4種類ほど紹介します。

自明な bit 演算

(and 0 A) -> 0, (and 0xFFFFFFFFFFFFFFFF A) -> A, (and A A) -> A, (xor A A) -> 0, (and (not A) A) -> 0, (or (not A) A) -> 0xFFFFFFFFFFFFFFFF,
(not (not A)) -> A, (not (or (not A) B) -> (or A B), (xor (not A) (not B)) -> (xor A B) etc. etc...

0/非0 の判定

定数は畳み込むので

(if0 0 A B) -> A

は即判断化ですが、逆はそうでもない。ので、(if0 C A B) に関して、基本Cの全bitを追いかけて、ひとつでも確実に1になるbitがあるなら B 。わからないときはあきらめてそのまま。

(if0 x A B)

Aが選択されるのは x = 0 の場合のみ。なので、(if0 x A[x/0], B)。さらに A[x/0] == B[x/0] なら B。

不必要な bit 演算の削除

(shr1 (xor 1 (or 1 x)))

みたいな式は、最後の shr1 が末尾の bit 操作をおとしてしまうので、xor も or も実は不必要。

やったこととか

初日

9:00, @nya3jp さん宅に @kinaba さんと集合。いきなり遅刻 orz。電車の中で問題読む。
とりあえず何にせよ式の構造とかは必要になるだろうと踏んで、コード書き始め。
今回ミスると以降問題が解けなくなるので、書いたコードの検証とそもそも問題の理解のため、
@kinaba さんと自分と同じコードを二つ作る。@nya3jp さんは、サーバと喋る部分作成。
今回はパフォーマンス重要だよ、という主催のアナウンスにしたがって C++ を選択。
昼食をとりつつとりあえず、構文木全列挙コード/Eval/テスト用parserを書く。
@kinaba さんよりだいぶ遅れて完成。 diff とって大丈夫そうだったので submit。
16:00 ころ初得点。0 点脱却!

(and 0 x) -> 0, (and (not 0) x) -> x

みたいな無駄が大量にあるので、つぶすコードを書き始める。
夕方 @kinaba さんが離脱。
夕食後 @dmikurube さんが合流。
深夜、第一バージョン完成。 -> 帰宅。
lightning は捨てることに。

二日目

起きてちょっと作業。妻と子どもが、妻の同僚の家に泊まりに行くのを見送る。
SAO 13巻購入。
12:00 集合。ちょこちょこ submit はじめる。
昼食。
とりあえず、今の方針ですすめる。@dmikurube さん作 Unittest を全面的に信頼して、
ひたすら最適化コードを足す。
とはいえ、半分終了くらいで、いい加減このまま 30 は解けないと判断して方針転換を図る。
なんとなく思いついた値 base 方針に。
夜中に @dmikurube さんコード書き上げてる。みんなはやい・・・。

三日目

ちょっと寝坊。というか腹痛・・・。
12:00集合、が遅刻(二回目
bonus が @kinaba さん作 leafa によって撃破される。圧倒的撃破率。
ちょっと思いついた最適化ルールを入れる。
終了後 @dmikurube さんの値 base 方針に合流。
夕食。
fold/tfoldがないやつに特攻。だいぶ解けたりする。
終電にて @dmikurube さん翌日のため離脱。
夜中2時すぎ頃 fold に着手。@nyaさんが恐るべきスピードで solver を daemon 化する。@kinaba さんと分担して fold solver 作成。
4時ころ完成。ぶん回し始める。
6時ころ、全生成した小さめの tfold 全部試すコードを挿入。ラストスパート。
8:30ころ、bonus2以外全部まわし終わる。bonus2 に特攻。


というところで時間切れ。

毎年ICFPCの日記しかかいていない気がするが気にしないことにする、、、というわけで参加記。
今年は @nya3jp, @kinaba, @dmikurube な皆様と4人チーム。

問題のまとめは、kinabaさんやまめさんの解説が詳しいです。というか kinaba さんの記事まとまりすぎてて書くことない。。。
ソースコードhttps://github.com/NekoSamaDuce/icfpc2013