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
まあまあ速いみたい。
Marathon Match 46 KnightsMoveCipher
http://www.topcoder.com/longcontest/?module=ViewStandings&rd=13679
久しぶりに参加。Coding phase が終わったところで暫定3位で、とりあえず賞金はもらえそう。
図のように正方形の盤面に文字が並べられていて、盤上をチェスのナイトの駒のように移動しながら文字を読んでいく。出てくる文章を答えてね!という問題。例えばこの図だと赤いところから順に IN.THIS.SHORT.NOTE... という具合。
ナイトのように、といっても移動する距離は4マス以上の場合もあって(例えば図の I→N)、各ステップで何マス離れた場所に動くかの情報は与えられている。スタート地点は与えられない。
平文は約8万通りの文章からランダムに選ばれる。この文章は配布されてるけど、ソースコードのサイズが 500KB に制限されてるので全部は埋め込めない。ただし getWords() という関数が用意されていて、上記の文章全体で出てくる単語と出現回数のリストが実行時に得られる。
以下自分の戦略。
まず getWords() で得られる単語表を 512 個のグループに分ける。このとき、グループ内の単語の出現頻度の合計が平均的になるようにする。頻度の高い "THE" や "OF" は単独でひとつのグループになるし、1回しか出現しない単語は 7000 語くらいのグループになる。
で、各グループのペア(512×512通り)について、グループ内の単語が平文中の連続した2単語として現れる確率を求めて、コードに埋め込んでおく。このテーブルが 512×512×1byte で 256KB。圧縮すればもっとグループの数を増やせるけど、増やしてもあまりスコアに影響なかったので無圧縮で。
実行時はこの表を使って順位をつけて、単語単位で順位優先探索。この方針で暫定スコア 42/100点くらい。
あとは枝刈りのために、3語・4語・5語まで探索したところで使った単語からハッシュ値を計算し、平文から生成したハッシュ値と符合するかチェックするようにした。これで暫定スコア 49/100 点くらい。平文のハッシュ値を格納するテーブルが約64KB×3個で、ソースコード全体のサイズは 460KB ほど。
Forum を見るといろんなアプローチがあったみたいで、なかなか面白い問題だったと思う。あと上位2人が際限なくスコアを伸ばしていくのが凄かった。
ブロックスデュオ
今年も参加してました。結果は13勝1敗で優勝。
http://hp.vector.co.jp/authors/VA003988/gpcc/08g2b.htm
提出したプログラムはこちら。
思考ルーチンは 去年 とほぼ同じもので、前向き枝刈りに Multi-ProbCut (リンク先pdf注意) を使うようにしたのが主な変更点です。
ブロックスデュオと ProbCut は相性がいいようで、去年のより一手くらい深く読めるようになって、去年のプログラムと戦わせた勝率も7割くらいでした。
でも相変わらず作者自身は全然強くなってないという…
Google Code Jam 2008 APAC Local Onsite
36名通過のところ暫定41位。意外と健闘してた。
A-small
今回の鬼門。直しても直しても通らない!
1時間くらい粘ったけど埒があかないので後回し。
D-small
さすがに0点ではかっこ悪いので解けそうな問題を探してみる。
問題 D は small だけなら力押しで楽勝。10行くらいコード書いて通した。
B-small
面倒臭そうに見えたけど、やってみるとそうでもなかった。
全探索でOK。
B-large
多分フルパワーか何もしないかでいいんじゃないかな…と思って B-small のテストケースで試してみたら同じ結果になった。ので、確信は持てなかったけどその方針で解いて submit しておいた。
結局通ったみたいでラッキー
A-small 再び
バグ見つけた!と思ったら残り10秒。お疲れ様でした。
自分のコードを USB メモリにコピーしておくの忘れたので、直したら通ってたかどうかは不明。