トップ «前の日記(2007-02-09) 最新 次の日記(2007-02-14)» 編集

U-memo

2006|11|12|
2007|01|02|03|04|05|06|07|08|09|10|11|12|
2008|01|02|03|04|05|06|08|
2009|08|10|
2010|02|03|
2011|11|12|
2012|04|
2016|02|
All= / Today= / Yesterday=

2007-02-13 [長年日記]

_ [Golf][OCaml] あなごる

LCS

以下のようにまともに書いたらメモ化しても3つめで timeout を食らう。 toplevel環境は遅いじょー。 (メモ化しないと native でもダメダメですが)

open Hashtbl
let h,l,f=create 9,String.length,read_line
let b,a=f(),f()let n p q=if l p<l q then q else p
let m p q r=n p(n q r)let rec s x y=let k=y+x*256in
if mem h k then find h k else if x*y=0then""else(add
h k(m(s(x-1)y)(s x(y-1))((s(x-1)(y-1))^if
a.[x-1]=b.[y-1]then Char.escaped a.[x-1]else""));find
h k);;print_string(s(l a)(l b))

あと1バイトは縮まりますが(keyをtuppleにすればもう2バイトか?、 さらに大小比較はまだ圧縮の余地あり)、 これよりも決め打ちprintの方が短いってどーゆーことよ。

Fibonacci

ひどい。31bit int だと overflow するじゃないか(手元は 63bit int だから流して初めて気づいた)。 最後の二つは決め打ちprint。

(追記) Int32 で書き直したら短くなった

permutater

まともに組むより決め打ち print のほうが短い。

open Array
let r=read_line()let l=String.length r
let s k=print_char r.[k]let f k=k
let b,a=make l 1,init l f
let rec g p k=let q x=if b.(x)=1then g(p+1)x in
set a p k;if p=l-1then(iter s a;print_endline"")else(set b k 0;for
j=0to l-1do if b.(j)=1then g(p+1)j done;set b k 1);;for
i=0to l-1do g 0i done

bowling scorer もたぶん決め打ち print のほうが短いが 「ガチンコ」希望なので試していない。

_ [Golf] あなごる Square Root (続)

AWK すげー。OCaml の天下は終わったw

C は -lm 出来るようになったおかげもあるけど、 その前からなかなかの記録。 たぶん sqrt は inline-asm (かバイナリ埋め込み)だったんだろうけど。 手元のほとんど圧縮しないテストコードは以下でした。

#include<math.h>
#include<stdio.h>
#include<stdlib.h>
main(){char s[256];gets(s);
for(;!feof(stdin);gets(s))printf("%.9f\n",sqrt(atof(s)));}

Perl すげー。まだまだ知らない技が多いのぅ。

本日のツッコミ(全2件) [ツッコミを入れる]
_ shinh (2007-02-13 22:52)

permutaterですが、この問題で回答埋め込みの方が短いってことは無さそう…とRubyと同じアルゴリズムで組んでみたら211Bになりました。OCamlはズブの素人なので、本職の方がやったらもっと縮むかなと思います。

_ うかい (2007-02-14 12:54)

アルゴリズムを見直せということですね。考えてみます。