式のつぶし方

主にやってたのこれなのですが、結構いろいろあって、コンパイラ屋さん大変だなぁ、と思ったりしてました（小並感）。
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

■

二年ぶりのICFP

ICFPC2012に参加。去年は出題者のお手伝いだったので二年ぶり。
@xhl_kogitsune, @chunjp, @nya3jp と4人チーム。

-1ヶ月くらい

どうせならあんまり普段一緒にいない人と、と思い nya さんと chun 宅@関西へ突撃を計画

-3日目くらい

結局チーム決まらないままずるずると。nya さんから xhl さんと一緒にやるけど、と誘われ渡りに船とばかりに乗る。チーム名決まらない。

0日目くらい

VM ware セットアップ
チームメモに

TODO(phoenixstarhiro): 7/13 21:00 から全力で書いてくれる予定

と書かれる

1日目

会社を20時くらいに出れば余裕、と思っていたら、すっかり夕食のことを失念。予定を繰り上げ夕食を食べ帰宅。(休み明けちゃんと仕事します・・・)
チーム名に"Tapl of Night Sky"を提案するも、誰も元ねたがわからない。

  • コンテスト開始

とりあえず問題読む。仕様あとから追加されるよ、ってのにうーんと思いながら、理解に努める。
どうせVisualizer必要だろ、と思ってさっくり実装。開始2時間後ぐらいにようやく動く。
xhlさんによってロボットとラムダが狐と油揚げに置換される。
Chun氏が achievement unlocked を手動管理。
とりあえずみんな手で解き始める。
開始3時間後くらいに nya さんが python Simulator 作成。 -> Visualizer お払い箱
Score 計算くらい足しておく。

  • 0:38
＿人人 人人＿ 
 ＞ 突然の死 ＜ 
 ￣Y^Y^Y^Y￣

by chun.

翌日の集合時間を決めて早めに就寝。

2日目

寝てる間に仕様変更。
まず寝坊。そして、Debian update かけたら終わらない -> 遅刻。結局毎日遅刻（酷
妻が旅行へ

  • 集合

nya さん超重要な用により一時離脱。
Simulator書き始める in C++。コードが汚い。
xhlさんが酷いマップを作り始める。人でも解くの大変・・・。
nya さん復帰。
探索用にジャーナルベースの UNDO 実装。
コードが汚い。
nyaさんによってpython simulator が c++ 版に移植される。

  • 夕方

Jenkins さん起動。そのご背景画像がダメな感じになる。
xhlさんのAIが動き始める。
チーム名決定。
lightning division 終了
京鼎樓。小籠包、ウマー。
xhl solverバグが取れる。
nya さんによって、status 画面がいい感じにセットアップされる。

  • 仕様変更(22時間ぶり2回目)

3日目

  • 寝坊

さらに寝てる間に仕様変更。ヒゲー。
Chun 氏による GA solver が初 submit。
加えて Simulator 方針転換により全書き換え決行。(24時間ぶり2回目)

  • 夕方から夜

ようやくトランポリンサポート & ひげサポート、とおもったらラムダ岩登場。(4回目)
Solverが八神一家になる。
https://twitter.com/icfpcontest2012/status/224432221405192192
ご飯食べて解散。
ラムダ岩サポート。

4日目

  • 寝坊

nya さんの手によって、AIの自動実行とかが実装される。
ひたすらSimulator書きまくってるのもあれなんで、AIを書いてみる。
バカモンテカルロ探索。不思議とちょこちょこ解ける、が死ぬほど重い。
AIの名前を決めるのに、nyaさんがすごい長さ候補をチャットに貼る、しかも手書き。
細かいチューニングと、bug fix を続ける。ぽこぽこ点数が上がりはじめる。
あと、予選ラウンドでSampleと同じマップくらいjudgeは食わせてくるだろう、と予測し手でといたのを即返すAI(?)を作成。無駄に強い。

  • 夕方

micro performance tuining. ちょっとしたキャッシュを導入。
GA solver が吐いたコードが長すぎる問題。xhlさんが、一瞬で短くする -> いろんな問題が解けるように。
bug fix 祭り
そして提出へ

  • 提出後

京鼎樓。小籠包、ウマー。
評価用に時間を短くするためつけていたリミッタ解除してテスト。
なんか、解けてる問題が増えるw

で

はなから無理ゲー感漂う中、最後はそこそこな点数はでてたので、
1,2回戦くらいは突破したい、今日この頃。


チームの方針は、AIを5本立てで、よさそうなやつに時間を多めに割り振って一番いいやつを採用。
基本、探索か、GAか、その辺で、特有の知識はあまりない感じ。
仕様変更がくるたび、中のデータ構造があちこち移動したのは、ちょっといまいちだった気がする。
あと、bugと戦いまくってた。
GAの中身とかあんまりわかってない。2年前とあんまり変わってないなぁ。
また、来年も参加しよう。

学んだこと

  • git の使い方(初級編その２)
  • Jenkinsは自宅に導入してもいいかもしれない
  • AI難しい
  • 仕様変更乱発する際に、ジャーナルベースの undo はちょっときつい。でも performance はちょっとよかったっぽい。
  • この面子だったら Persistent なデータじゃなくて Copy on write なデータ構造のほうがコピー回数はたぶん大分減ったはず && たぶん全員余裕で扱えるはず。ただ、 bug との戦い考えるとやらなくてもよかったのかもしれない。
  • 関数型言語とはなんだったのか。
  • tab と space をまぜるとプログラマは死ぬ
  • http://google-styleguide.googlecode.com/svn/trunk/google-c-style.el
  • 自分の思考回路をプログラムに素直に落とせるようになれると、もう一段階段を上れそう。

うおー、久々

なんと、やく半年振りの更新。
ICFPCっぽいことを書こうと思って、でもあんまり練れてないので、
またちょっとしてから出そう（と思っているうちにブームを逃しそうだ。


大学時代の同期他の人と飲んできた。
みんな相変わらずだったけど、ちょっと話題が変わっててなんか年齢を感じたりした。

続きを読む

ぼくのかんがえたさいきょうのぱたーんまっち。

c++

以前twitterで、@kinaba先生にあおられたのを思い出したので、冬休みのリハビリがてら作ってみました。c++0x 版パターンマッチ。できたのを見ると厨二病全開です、はい。

以下みたいなのができます。とりあえず書き方。

#define match PHOENIX_MATCH
#define with PHOENIX_WITH

match (expr) {
  with (ptn1) {
    ...
  }
  with (ptn2) {
    ...
  }
  ...
}

switch-case のまねです。はい。ptn1 -> ptn2 -> ... の順で評価してマッチしたら中を実行後 match から出る。


ptnの中身は以下の4種類

  • 式との比較
#define match PHOENIX_MATCH
#define with PHOENIX_WITH

match (expr) {
  with (value) {
    // expr == value のときだけ実行
  }
}
  • 変数のbind
#define match PHOENIX_MATCH
#define with PHOENIX_WITH
#define ref PHOENIX_REF

match (expr) {
  with (ref(var)) {
     // 変数 var は expr への束縛
  }
}
  • 何でもマッチ
#define match PHOENIX_MATCH
#define with PHOENIX_WITH

match (expr) {
  with (_) {
    // 任意の expr とマッチ
  }
}
  • struct/classとマッチ
#define match PHOENIX_MATCH
#define with PHOENIX_WITH
#define ptn PHOENIX_PTN
#define ref PHOENIX_REF

struct A {
  int x, y;
};
DECLARE_PHOENIX_PATTERN(A, (x, y));

...
match (expr) {  // expr は A型
  with (ptn(A, (10, 20))) {
    // expr.x == 10 && expr.y == 20 でここにマッチ
  }
  with (ptn(A, (ref(x), _))) {
    // この中で x は expr.x, expr.y はなんでもマッチ
  }
}
続きを読む