雑記

2015-09-28(Mon) isucon5

に出てみました。

結果は惨敗。というか、最後まで終わらなかった。

(´・ω・`)。

チームは @nya3jp さんと @thimura さんとの3人でした。

以下反省文。

続きを読む

2014-09-23(Tue)

CSAW CTF 2014

年一の日記が、年二に!

誘われて CTF に出てみました。詳細:

http://d.hatena.ne.jp/shinichiro_h/20140922

で、大体かいてあるので、まぁ、自分が見たとこだけ備忘録的に。

続きを読む

2014-07-28(Mon)

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終了前)、寝落ちしたと踏んで、AIC++ -> GCC に hand compile/assemble。

ラベルの解決するくらいの asm は書いておくべきだった。(毎年恒例の反省)

DBUGはさめないのつらい。

結局、bug とれず。 lightning division は放棄

就寝。

二日目

まぁ、LISP compiler できてたので、LISPAI を書き直す。

以降、基本的に AIC++ から 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 の年はだいたいそうなんだけども・・・。

さて、寝よう。

2013-08-12(Mon)

毎年ICFPCの日記しかかいていない気がするが気にしないことにする、、、というわけで参加記。

今年は @nya3jp, @kinaba, @dmikurube な皆様と4人チーム。

問題のまとめは、kinabaさんやまめさんの解説が詳しいです。というか kinaba さんの記事まとまりすぎてて書くことない。。。

ソースコードhttps://github.com/NekoSamaDuce/icfpc2013

やったこととか

初日

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 に特攻


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

式のつぶし方

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

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 も実は不必要。

雑感

今年のは結構いい感じのサイズだなぁ、と。「もう1日欲しい」というところで終わるあたりが、ちょうどいい。

主催のみなさまありがとうございました(と日本語で書いてもダメか・・・)

こういうの書いてるとやっぱり pattern match が欲しくなりますね。というか、matcher 書くべきだったかなぁ・・・。

くわえて、あちこち相互再帰してるので、変な無限ループに入るケースがなくなるように気をつけるのは、

だいぶ面倒だなぁ、と思ったり。

今回はC++だったんですが、メモリ管理やっぱりちょっと気を使いますね。まぁでもGCよりはマシかな。

チーム funny quotes はきっとメンバーの誰かがなんとかしてくれるハズ。

チームでわいわいやるの楽しいですね、やっぱり。ありがとうございました。

来年も出たいなぁー。

2012-07-17(Tue)

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