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時 寝る。にはスコアボード1画面目まで上がれるといいなあ。
- 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
結果出てました。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手目までのデータベースになってます。勝手にデータベースが成長してくれるので楽でしたが、夜にマシンがうるさくて困りました。
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
ブロックスデュオ プログラム対戦
http://hp.vector.co.jp/authors/VA003988/gpcc/gpcc09.htm#g3
今年も開催されるそうなので興味のある方は参加すると良いです。私も何か考えないと…
そういえば前回の大会後の交流会で行われたという、対人間戦のレポートが面白かったです。
http://hp.vector.co.jp/authors/VA003988/gpcc/gpcc08.pdf
anarchy golf - numof 1 bits in 0 to 255
id:yshl さんにならって鑑賞会。関数型の esolang ばっかりです。
Lazy K
私
http://golf.shinh.org/reveal.rb?numof+1+bits+in+0+to+255/irori/1240716651&lazy
"8" から始めて、文字列を倍々にしつつ前半部分から1を引いていきます。
church数から1を引く関数がちょっとサイズ大きめ。
(lazy-def '(1- n) '(lambda (f z) (((n (lambda (g h) (h (g f)))) (lambda (x) z)) I))) (lazy-def '(dbl lst) '(((lambda (x) (x x)) (lambda (rec l) (if<= 256 (car l) lst (cons (1- (car l)) (rec rec (cdr l)))))) lst)) (lazy-def '(main input) '(8 dbl (cons 56 input))) (print-as-golf (laze 'main))
51b さん
http://golf.shinh.org/reveal.rb?numof+1+bits+in+0+to+255/51b/1240743932&lazy
http://d.hatena.ne.jp/yshl/20090429#1240985772
なるほどー。ビットを数える方法で私のより短くなるんだなあ。
Universal Lambda
私
http://golf.shinh.org/reveal.rb?numof+1+bits+in+0+to+255/irori/1240720054&lamb
処理系付属のアセンブラじゃなくて Lazy K のコンパイラを改造したものを使ってます。
アルゴリズムは Lazy K 版と同じ。
(lazy-def '(1- n) '(lambda (f z) (((n (lambda (g h) (h (g f)))) (lambda (x) z)) (lambda (x) x)))) (lazy-def '(dbl lst) '(((lambda (x) (x x)) (lambda (rec l) (l (lambda (hd tl _) (cons (1- hd) (rec rec tl))) lst))) lst)) (lazy-def '(main input) '(input (lambda (hd) (hd dbl)))) (print-as-binary (shrink (laze 'main))) (display "\x088")
hinoe さん
http://golf.shinh.org/reveal.rb?numof+1+bits+in+0+to+255/hinoe/1240735277&lamb
Universal Lambda の処理系についてきた逆アセンブラを使ってみると、
$lamd hinoe.lamb (\a.a (\b c.c (b (\d e f.d e (d (\g h.g (e g h)) f)) (\d e f.f d e)))) "\b0
(゜Д゜)ナニコレ
整理してみるとこんな感じのようでした。うーんかっこいい。
# input = cons 8 (cons 48 nil) succ n s z = s (n s z) main input = input (\n s. s (n (\f hd tl. f hd (f (succ hd) tl)) cons))
これを Lazy K 用に書き換えてみたら、私や 51b さんの半分以下の長さになってしまったのでした。
http://golf.shinh.org/reveal.rb?numof+1+bits+in+0+to+255/irori%28translation+of+hinoe%27s+Universal+Lambda%29/1241191578&lazy
Grass
私
http://golf.shinh.org/reveal.rb?numof+1+bits+in+0+to+255/irori/1240736568&grass
例によって必要な文字を作るのが一番大変です。
Glidで書いています。
let 2 f x = f (f x) let 4 = 2 2 let s4 = 4 Succ let s16 = 4 s4 let f2 x = Succ (s4 (s16 (x ((4 x) W)))) let c181 = f2 (2 s16) let c185 = s4 c181 (* '0' *) let append_rec rec xs ys f = (rec rec) (xs f) (ys f) let dbl fs = (append_rec append_rec) fs (fs Succ) let 3 f x = f (f (f x)) let 8dbl = 3 2 dbl let mapper_rec rec x f = (rec rec) (f x) let mapper = mapper_rec mapper_rec let seed = mapper c185 let flst = 8dbl seed let _ = flst Out
Unlambda
私
http://golf.shinh.org/reveal.rb?numof+1+bits+in+0+to+255/irori/1240725910&unl
秘密の俺コンパイラを使用。アルゴリズムは Grass と似ています。
ASCII コードの演算ができないのでコードの半分以上を数字のテーブルが占めているのが悲しい…
(lazy-def '(mapper x) '(lambda (f) (mapper (x f)))) (lazy-def '(append fs1 fs2) '(lambda (f) (append (fs1 f) (fs2 f)))) (lazy-def '(dbl fs) '(append fs (cdr fs)) (lazy-def 'digits '(cons* #\0 #\1 #\2 #\3 #\4 #\5 #\6 #\7 (lambda (f) #\8))) (lazy-def 'flst '(c8 dbl (mapper digits))) (lazy-def '(putc f) '(car f f)) (lazy-def 'main '(flst putc))
TCO09 Marathon Match Round 3
http://www.topcoder.com/longcontest/?module=ViewStandings&rd=13768
Top10通過のところ暫定35位。残念。
私の方針はこんな感じでした。特にかっこいいアイデアとかはなく。
- 一定時間ごとにいろんな方向に反射させてみて、結果がよいものを採用
- がんばってシミュレータを高速化
- パラメータ調整
Universal Lambda インタプリタを作ってみた
以前作った Lazy K インタプリタを改造して、Universal Lambda のインタプリタを作ってみました。
Universal Lambda のコードを一旦 SKI コンビネータ式に変換して、あとは Lazy K と同じように実行します。
公式のインタプリタ:
lamb sort+characters.lamb < input2 0.68s user 0.01s system 99% cpu 0.690 total
作ったやつ:
./clamb sort+characters.lamb < input2 0.24s user 0.00s system 99% cpu 0.249 total
まあまあ速いみたい。