条件6を満たすそれぞれの酵素に対して、DNAをカットする位置を求める。
パターンマッチは酵素ごとにDFAを作った。いくつかの酵素はワイルドカードが多くてDFAの状態数が膨大になるので、それらについてはナイーブな strstr的方法で。改善の余地はだいぶあるけど、どうせ前処理部全体で0.1秒以内で終わるのであまりここは凝らなかった。

また探索を高速化するために、いろいろ計算しておく。

カットの結果、条件2より多くのDNA片ができたら、その酵素は使えないので捨てる。
カットの結果、条件3より短いDNA片ができたら、その酵素は使えないので捨てる。
酵素のペア (A, B) のカットの和集合が条件2, 3を満たさない場合、Aを選んだらBは使えない（その逆も）。すべての酵素についてこの関係を記録しておく。

探索

酵素をカットの数が多い順に並べて、深さ優先で探索していく。マラソンでDFSで解けるってかなり珍しいんじゃないだろうか。

改良

TopCoderの実行サーバーで0.3秒を超えると点数が下がるので、時間がかかるテストケースを探しては遅くなる原因を探して枝刈りを追加、というくり返し。

枝刈りの例を挙げると、以下のような場合に探索を打ち切るようにした。

残りの酵素で条件8を満たせなくなった場合
条件4より長いDNA片をすべてカットすると条件2を満たさなくなる場合
残りの酵素で条件1と条件7を同時に満たせなくなった場合
残りの酵素で目いっぱいカットしても、条件1または条件4を満たせなくなった場合

最終的には、手元の環境で 200,000 ケース実行して解があるケースで 0.1 秒以上かかるものは無し、解なしのケースでは0.2秒台が1つだけになった。

結果

http://www.topcoder.com/longcontest/stats/?module=ViewOverview&rd=14525

1位! …だけど同点1位が16人というアレな結果に。
Forumを見ると100万件とかテストしてたりマッチングを超頑張ったりしてる人も居たけど、5000件程度の system test では差がつかなかったようだ。少々可哀想な気もする。

あと賞金貰うにはコードの解説を提出しないといけないらしい。めんどい…

2011-04-29

ブロックスデュオ

Blokus

今さらですが、ブロックスデュオ大会に参加したプログラムとブラウザ上で対戦できるものを作りました。

http://irorin.org/blokus.html

ブロックスデュオのルールはこちらで紹介されています。

操作方法

難易度と Violet(先手)・Orange(後手) を選んでゲームを開始します。
自分のピースをドラッグして盤面に置いていきます。
ピースはダブルクリックで左右反転、マウスホイールで回転します。Shift+クリックでも回転します。

(2011/07/09更新)
対戦結果をツイートできるようにしてみました。勝ったら自慢しましょう。

(2012/02/05更新)
ソースコードはこちらです。 https://github.com/irori/blokus

2010-06-21

ICFP Programming Contest 2010

http://icfpcontest.org/
今年も時系列でお送りします。問題については konnさんの翻訳など。

18日21時開始。
19日0時回路の構文がなんとなくわかった。ゲートの入出力表作成に入る。
19日2時入出力表できたー！と思って手元で17文字計算してみると結果が合わない。ショック。
19日4時手計算の間違いに気づく。どうして2cmしか離れてない場所に写す文字を間違えるのか…！ともかく一区切りついたので寝る。

19日8時起床。keyを出力する回路を考える。
19日12時むずいー。
19日18時わかんねー。
19日22時やめたくなってきた…。
20日2時ようやく使えそうな方法を思いついたので回路生成スクリプトを書く。
20日3時 keyが通った！達成感がハンパない。
20日4時 3進数コード解析のため、車のコードを集めたりしつつ寝る。

20日10時おはようございます。ずいぶん出遅れてしまったけれど頑張ります。
20日14時車のエンコーディングは分かった。次は燃料。
20日15時最初の燃料を提出。これでやっとスタートラインという感じ。
20日16時環境整備。車の取得と燃料の提出をするスクリプトを書く。
20日17時 80個ほど提出。そろそろまぜろよ(AA略)
20日22時単純なソルバを書いたり適当に手で解いて提出してみたり。
21日2時寝る。にはスコアボード１画面目まで上がれるといいなあ。

21日11時よくねた。寝てる間に増えた車の分を一気に提出。
21日15時賢いソルバを書こうとして失敗。
21日18時やっぱり最後は力技。車取得＆燃料提出スクリプトを回しつつ手動で問題を解いて提出していく。
21日20時 100個くらい解けたけど、今からじゃスコアにほとんど影響しないだろうなあ。
21日20時半サーバー頑張れ超頑張れ。
21日21時終了。

結果、1644種類の車を解いて696点でした。スコアボードで上から24番目だから29位でしょうか。回路の作り方が思いつかなくて土曜一日潰したのが痛すぎでした。
今回並列で出来る作業が多いのと提出の早さが重要ということで、複数人のチームに有利だった印象です。燃料産業は個人事業主には厳しいですね。

時間がなかったのと今回 100% Ruby だったので凝ったソルバは作れませんでした。代わりに irb 上からこんな風に提出できるようにして、人力で計算して提出していました。

irb(main):066:0> s.submit(59899, [[[2**17+1]], [[2]]])

係数の調整も手動です。 OpenOffice Calc に式を入力して調整したりしてました。

おまけ。時間ごとの提出数。
半分くらいは最後6時間で提出してるのでスコア的にはあまり効かなそうです。寝てる間スクリプトを回しておかなかったのが悔やまれます。
あとみんな終了間際に車追加しすぎです。

2009-11-01

ブロックスデュオ大会2009

Blokus

結果出てました。9勝1敗で優勝でした。

http://hp.vector.co.jp/authors/VA003988/gpcc/09g3b.htm

今年は東京農工大の会場に行ってきました。他の予定があったので途中で抜けてしまいましたが…。運営の皆さんお疲れ様でした＆ありがとうございました。

提出したプログラムはこちら。

hm5.zip (2013/09/04 UNLICENSE.txt を追加。ご自由にご利用ください)

昨年からの改良点は2つだけです。正直あんまり強くなってません。

盤面評価を約 15% 高速化
序盤の動きをあらかじめ計算して持っておくようにした

opening_book というファイルが序盤の着手データベースで、以下のようなテキストファイルになってます。

66t0
66t0 99t7 A7q1
66t0 99t7 A7q1 B7l4 7Al1
66t0 99t7 A7q1 58k2 BAk0
66t0 99t7 A7q1 58o6 BAk0
66t0 99t7 A7q1 68p2 BAo5

例えば一番下の行は、4手目まで 66t0→99t7→A7q1→68p2 という展開だったら BAo5 を置く、という感じです。

序盤データベースの作成方法はこの辺りを参考にしました。
http://www.cs.ualberta.ca/~mburo/ps/book.pdf
http://www.google.com/search?q=Generating+an+Opening+Book+for+Amazons

今回作った opening_book は各局面で深さ5の探索を行って次の手を決めています。PCを1ヶ月くらい回して生成したもので、最大6手目までのデータベースになってます。勝手にデータベースが成長してくれるので楽でしたが、夜にマシンがうるさくて困りました。

2009-06-30

ICFP Programming Contest 2009

http://icfpcontest.org/
年に一度のお祭りに参加してました。

27日1時 3時開始だがどうにも眠いので寝る。今にしてみればこれは正しい選択だった。
27日7時起きて問題文を読み始める。
27日10時 VMを実装してみたが動かない。あれー？と思ったら仕様の訂正が出ていた。遅くスタートすると他の人が先にバグに当たってくれるので精神衛生上良い。
27日12時なるほど Hohmann 軌道。
27日13時ビジュアライザをでっちあげる。VM とソルバは C で書いたので、ソルバから位置を出力してパイプでRubyのビジュアライザに流すようにした。
27日15時 100x が解けた。
27日18時なぜか submit すると CRASH になるなー、と思ったら config 番号を入れるのを忘れていた。
27日19時いまさら Point クラスを作る。
27日20時なんか噴射 1.1 倍とかにすると 100x の点数上がるなー。
27日21時 200x に取りかかる。多分タイミングを計って Hohmann 遷移すればいいんだよね。
27日23時計算合わない病に冒される。
28日1時わかんね (;_;) 寝る
28日8時今日も一日がんばりましょう。
28日10時分かった！符号間違ってんじゃん！
28日11時 2003 はターゲットのほうが低い位置にあるのか。さんざん悩んだから今度は間違えないぞ…あ、あれ？
28日16時 200x はこんなもんでいいや。300x はどうやるのかちょっと分からないなあ。
28日18時だらだらする。
28日21時 pepsiso にあやかろうと思ってペプシしそを買ってくる。これは…しそだ…！
28日23時ニコ動を見る。
29日2時寝て起きたらなんか思いつくかもしれんし寝るか…
29日10時寝過ぎた。
29日11時わかった。ターゲットの近地点で接近するように、近地点を含む軌道に遷移するタイミングを調整すればいい。
29日12時 3003 できた！
29日15時さて 400x ですが残り 12 時間でどこまでいけるやら。
29日19時ターゲットがほぼ円軌道な 4004 が一番簡単そう。自機と回転方向が逆だけどまあ接近してからの調整でなんとかなるだろう。
29日21時半 4004 でデブリ5個回収できた。この時点で21位。20位以内に入ったら記念撮影しようと思ってたのに！
29日22時半 4001 と 4003 でなんとかスコア獲得して20位。やったー
29日22:56 10位！自分をほめてあげたい！
29日23時スコアボードが凍結された。なんか7位になってるけど上位がちょうど submit ト中で一時的に点数下がってるっぽい。
29日23時あれ、10 位ってことは validation のことも考えないといけないのか。コードに直に回収する順番書いてあるんですけど！
30日0時頑張って general な解き方に直していく。こんなことしてる間に絶対順位下がってるよなあ。
30日1時ここに来てまさかの謎CRASH。
30日3時終了。回収する順番を探索するようにして裏で回しておいたら少しスコア上がった。

物理とか幾何とか苦手意識があるんですが、それでも3日間挫折せずに続けられたので難易度設定は絶妙だったと思います。
参加してた皆さんお疲れさまでした。

追記

ひっそりとソース追加。やる気ない感じなのがバレバレですな…
icfp09-irori.tar.gz

2009-06-14

ブロックスデュオプログラム対戦

Blokus

http://hp.vector.co.jp/authors/VA003988/gpcc/gpcc09.htm#g3
今年も開催されるそうなので興味のある方は参加すると良いです。私も何か考えないと…

そういえば前回の大会後の交流会で行われたという、対人間戦のレポートが面白かったです。
http://hp.vector.co.jp/authors/VA003988/gpcc/gpcc08.pdf