トップ 最新 追記

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-07 [長年日記]

_ [Golf][OCaml] Anarchy Golf

世界の一流プロに紛れた素人感バリバリですが、m.ukai で参加してます。 Perl では勝てそうにないので、参加数の少ない OCaml で ;-)

stderr に何を吐いても問題ないので、stdin を読みすぎて例外 End_of_file で終わってよい。

echo

exec ごめんなさい。使わなければ 44byte。

e

Nums 使うと 148B (+ #load ディレクティブもいるのでもっと長くなる) なのでどうにも戦いにならない。

delete blank lines

最初は while ループでその時点のトップ記録にあと 1byte がなじょだったが、やりかた変えたら抜けた。

tennis

まだ短くなる気はする。

99 shinichiroes of hamaji

Printf.printf だけで長いよもう。三項演算子も if then else になるから長いよもう。

even lines

delete blank lines と同じような戦略。

これは Perl でもやってみたが 19B。1バイトいったい何が削れるんだ?


2007-02-08 [長年日記]

_ [Golf] even lines

Perl の 15B わかった。気づけば単純ですね。


2007-02-09 [長年日記]

_ [Golf] あなごる Square root

問題を追加させてもらったのです。

Perl,Ruby の類は相変わらず簡単でしょうが、-lm のない C の類はいきなりきつい。(テストデータの確認は OCaml と C でやったんだが)

# OCaml は他の問題で #load"str.cma" してるんだからあいこ :-)

befunge とかは入力パターンから決め打ちで出すんだろうか。

それにしても Perl, Ruby が苦手なのってなんだろうなぁ。

(追記) Perl は難しい。負数の sqrt が落ちるのと、-0 と 16進数がダメ。 16進数の小数表記がガンになりそうだ。

ふふ。


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 [permutaterですが、この問題で回答埋め込みの方が短いってことは無さそう…とRubyと同じアルゴリズムで組んで..]

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


2007-02-14 [長年日記]

_ [Golf][OCaml] あなごる (URL変更)

順列のアルゴリズムなー、と、無い頭を使って考えていたら、 フィボナッチでぬかれてしまったので、現実逃避の逃避(*1) で追い抜き返す。ワンライナーになったような。

(*1) あなごる自体が現実逃避の一環であるため

競争相手がいてくれるとやる気が出るというものです。

# 現実逃避から戻れないとも言う

なお、e のまじめ版はこんな感じ。(141Bになった)

open Num let u=Int 1 let rec e p i k=if p>99then u-/u else
k+/(e(p+1)(i+/u)(k//i));;print_string(String.sub(approx_num_exp
101(e 1u u))3 101)

(追記) 実際には #load"nums.cma" がいるな

_ [Golf][OCaml] あなごる フィボナッチ

64B っていったいなんだー!?

# 記号がやけに多いのと空白がほとんど無いのと...なんだろう。 短くマジックナンバーを生成できるネタがある?


2007-02-15 [長年日記]

_ [Golf][OCaml] あなごる

何か突然 OCaml で盛り上がりだしたような。

いちおう斜壊社会人の身としては、フルに時間を使えないというのはあるけど、ゴルフ本職の人らも含めてみんなに付いていけるのだろうかという感じ。

触発されていくつかは記録を更新したけど、ダメだなー。でも面白いぞー。

みなさんに習っていくつかのノウハウを出しておこう。

OCaml のパーサの癖を読む

最初の時期の smiley triangle (82B)から。

let b=ref"\n:-)";;print_string":\n:-";for i=0to 31do print_string!b;b:=!b^"))"done
  • 「文字 記号」もしくは「記号 文字」と来る場合はスペースは省略できる
  • 「数字 文字」と来る場合もスペースは省略できる。逆は一つのトークンになるのでダメ。
  • 「演算記号 演算記号」は詰められない。ひとつの別の演算子と思われてしまう。特に参照を条件節で使うときにはまる。!a>!b は >! が一つの演算と思われてしまうわけだ。

どっちが得か

マッチ構文が出てくるなら後者。

f x=match x with hoge->fuga|...
f=function hoge->fuga|...

副作用と括弧

条件の中などに出力があるときはどこかに詰め込めるかを考える

... then(print_string"hoge";f(n+1))else....
... then f(print_string"hoge";n+1)else....

ネタばれがあるような例はもう少し様子を見よう。

ライブラリロード

幸いなことにゴルフ場は toplevel 環境で実行されるので ライブラリの読み込みが必要な場合でも実行できる。 extLib があるかどうかは知らないけれど。

初期の bowling scorer の例:

#load"str.cma"open Printf let rec s f t r=match f with
h::i::j::k->let p=t+h+i+if h+i>9then j else 0in
printf"%d "p;s(if h=10then i::j::k else
j::k)p(r+1)|h::i::j->if r<10then
printf"%d"(t+h+i);;s(List.map
int_of_string(Str.split(Str.regexp" ")(read_line())))0 0

ただし当然 #load ディレクティブがいるし、そもそも Num と Str 以外は用が無い気はするけれど。

ゴルフサーバの癖

出力は、いちばん最後の改行、空白についてはあってもなくても通るので、最後のつじつま合わせは不要。だから上の bowling の例は後ろの printf も "%d " にして問題ない。 また、前にも書いたとおり stderr に何を出してもいいのでファイルの読み込みの例外の後始末は不要。

複数行出力

print_int の出番が無いような感じ。 改行のためだけに print_endline"" とか print_newline() とするのはあまりにも無駄過ぎるので、

Printf.printf"%d\n"i

になってしまう。改行コードは jijixi さんの技 (というか他の言語のゴルフでは有名な話か?)により

Printf.printf"%d
"i

とできる。

複数の束縛

関数では無いものの束縛は tupple を使いまくれる。

let p,q=ref 0,ref 0
let a,b,c,d=read_line(),[|"Ace";"2";"3";"4";"5";"6";"7";"8";"9";"10";"Jack"|],[|"Queen"|],[|"King"|]

ネタばれか?

割り切れるかどうかの判定のためだけに mod なんて演算は長いんですよ。

if i mod j=0then ...
if i/j*j=i then ...

割り切れなきゃ切り捨てられるんで掛けても元に戻らない。 これでも長いけどどうにかならんかねぇ。

本日のツッコミ(全3件) [ツッコミを入れる]

_ shinh [おお、 mod の代替は気付いてませんでした。まだ他の部分でも縮むかなーと思うので口惜しいので他で探します。]

_ ukai [あらら、本当にネタばれになってしまったとは申し訳ないです。]

_ うかい [確かに縮みました。これのネタばれは当分やめておきます。]


2007-02-16 [長年日記]

_ [Golf][OCaml] あなごるネタばれあまりしない編 (Delete blank lines)

Rank	User	Size	Statistics
1	m.ukai	55	0B / 32B / 19B
2	shinh	56	0B / 32B / 20B
3	soutaro	59	0B / ?B / ?B
4	hrkw	65	?B / ?B / ?B
5	jijixi	65	0B / ?B / ?B

65B というのはたぶんこれ。最初に書いたのとほぼ同等。

while 1=1do let a=read_line()in if a<>""then print_endline a done

ここから if-then をなくせば 59B になるはず(だがこの59Bはそうなっているかどうかは不明)。

55B は while 構文を使っていません。

_ [Golf][OCaml] あなごるネタばれしまくり編 (Fibonacci)

Rank	User	Size	Statistics
1	ksk	58	0B / 34B / 17B
2	m.ukai	65	0B / 37B / 19B

Int32 より float を使ったほうが短かったが、とにかく素朴な再帰手段+αで現在の状況。if - then も除いた状態なのでここから 7byte 縮む気はしない。

この前に持っていた直接算出するやつは縮むのかもしれないが、どうやって?

for i=1to 46do Printf.printf"%.0f\n"(1.61803398875**float i/.sqrt 5.)done

さっぱりわからんなー。

(追記)ksk さんはまじめに計算している ことから考え、終了条件をひねって 62B。あと4Bに使えるネタはなんだろう?

_ [Golf][OCaml] あなごるネタばれしない編その2 (Delete Last-line)

delete blank line で shinhさんと 1B の差はたぶんあれだろう、なのになぜ delete last line は同じスコアなんだろう、と考えたら一気に 6B 縮んだ。

_ [Golf][OCaml] あなごるネタばれしまくり編その2 (invert case)

Rank	User	Size	Statistics
1	ksk	63	0B / 50B / 10B
2	shinh	74	0B / 53B / 17B
3	m.ukai	79	0B / 60B / 15B

全然太刀打ちできる気配が無いのは普通に書きすぎているからか。

while 1=1do print_char(char_of_int(32 lxor(int_of_char(input_char stdin))))done

そもそも非対称なことに read_char が無い時点で困ってしまうわけだが、 String.iter しても Char.lowercase / uppercase は長いしなぁ。

_ [Golf][OCaml] あなごる今日のノウハウ

昨日は演算記号の続きはスペースが無いとダメだと書いたけれど、

a:=!b

これはスペースが不要(a := !b ね)。演算記号でないならいいという感じだが、パーサの癖は謎だらけ。

本日のツッコミ(全2件) [ツッコミを入れる]

_ ksk [こんにちは. 参考までに書いておきますと,私のinvert caseのコードも,一応それの延長線上にあります.]

_ ukai [こんにちは。 これの延長で縮めるって、禁断のあれかなぁ?]


2007-02-17 [長年日記]

_ [Golf][OCaml] あなごる delete-line

55B が一気に 19B にー!!って、19B は exec なひとですよね。Bash が6文字だから。

echo 以外は exec なことはしない(というか中盤以降は exec 禁止がほとんどのはずだけど)ようにしてる。 echo はなんというかほかの言語でも exec 祭になってた感があったようにみえたからやってしまったので今は反省して...いない(ぇ

せめて名前変えて突っ込めばよかったなー。echo だって 44B よりは縮むし。

来週考えよう(不良社員

本日のツッコミ(全2件) [ツッコミを入れる]

_ ksk [すみません.jijixiさんの21B(当時)を見て便乗してしまいました. exec不使用版もニックネームを変えてエン..]

_ ukai [いえいえもともとわたしがえちょで使ってしまったのが諸悪の根源なんで。 露骨に数字が違うから悩む必要はなかったけど、..]


2007-02-19 [長年日記]

_ [OCaml] OCaml本

住井先生の情報 によると日本語な OCaml のテキストが出るらしい。

しかし、買うかどうかは微妙だなー。 出たらとりあえず立ち読みだな。

_ [Golf][OCaml] あなごる問題が増えたなー

週末は風邪で倒れてたりしたわけだがー。

exit status

exec するのが前提な問題だけど、あえて exec なしでもやってみた。

Show the way

入力決め打ち(embed、でいいんですよね>誰?)のほうがはるかに短い。

組み方によって最初の数字のあり無しの優位性がどちらにも転ぶ。

  • 数字があると終了条件を作りやすいかもしれない
  • 数字が無ければそれだけのために read_int() しなくてむのに...

決め打ちするならあった方が断然楽 :-)

transpose lines

入れ替え後の改行のためだけに print_endline"" してるのは長いんだけど、String.iter (長さ) '\n' するのはもっと長いだけに。

実は print_char するよりも文字列を構成してから print_endline のほうが短い、なんてこともなさそうだしなー。

rotate lines

jijixi さんとおそらく完全に同一内容だろう。 ksk さんは内容が違うんだろうけど、はて。(その違いがトップ取れない奴に効いているんだろうなぁ)

_ [Golf][OCaml] あなごる既存の問題編

Dancing Kids

前からある問題だけど週末で祭になったのか? とりあえず適当に入れていただけだったので更新してみたが トップは遠い。

invert case

マニュアル良く嫁!という感じ(exit を exec なしでやるときに気づいた) で縮まったがあとの 1B は謎過ぎる。たぶん jijixi さんと同じ状態。

Bowling scorer

一人旅は続く。まだ縮んだけどもうネタは無いかなー。

sort characters

shinhさんに追い付いた、が中身は全然違うみたいだなー。

_ [Golf][OCaml] あなごる今日の技?

まだ禁断?の魔法は使ってないですー。

ループに使える構文

当たり前の話だけれども、

for i=0to n do ... done
for i=n downto 0do ... done
while 1=1do ... done
let rec f x=...;f(x+1);;f 0

それぞれに得意不得意があるので使い分ける。 まれにイテレータ (*.iter) を使うこともある。


2007-02-20 [長年日記]

_ [Golf][OCaml] あなごる e Num版

kskさんが Num 版でエントリ されてたので 1B 抜くまでがんばった。

_ [Golf][OCaml] あなごるねたばらし

shinh さんのところ(2007-02-20)で幾つか情報が出たのでー。

ただし permutater は見ない。がんばるもん。

blank.ml

予想通りの 1B 差。そこから 1B 縮むんです。誰かが到達した時点でネタばらししましょう。

even.ml

全く同じ。

csort.ml

同じ 92B なのにずいぶんと違うこと。

open List let rec l x=try l(input_char stdin::x)with _->iter print_char(sort compare x);;l[]

トップはどうなってるのかさっぱり分かりません。

prime.ml

アルゴリズムが違いますねー。 shinh さんは素数をリストに蓄え込んでますが、私は純粋な試し割りです (自分自身未満の全てを扱う)。 119B だったころの記録をさらしておきます。

let rec f r j i=r>0&j<2&(Printf.printf"%d
"i;f(r-1)i(i+1))||j>1&i/j*j=i&f r i(i+1)||i/j*j<i&f r(j-1)i;;f(read_int())1 2

あらあら、shinh さんのからいじると 113B になってしまいますよ、奥様。

# 以前さらした mod の書き換え以外にも縮むネタがあります。これはまだネタばれしません。ヒント:入力が 1 のときに期待の動作にならなくなります。

inv.ml

昨日書いた 通りマニュアルを良く読むと、 っていうか input_char で止まらずにもう少し読むと、 魔法を使う必要が無いことに気づく罠。

while 1=1do print_char(Char.chr(input_byte stdin lxor 32))done

本日のツッコミ(全2件) [ツッコミを入れる]

_ うんの [w3m では、はじめっからネタばれしちゃいますね。 RSS はどうなっているのかなと思って見ましたが、thunde..]

_ うかい [それがプラグインの仕様なのですー。 Javascript 非対応 -> ソース直読みしかない CSS 非対応 ->..]


2007-02-21 [長年日記]

_ [Golf][OCaml] あなごる prime numbers

shinh さんのが 113B になるって書いたけど自分のはもっと縮むじゃねーか。

scheme を抜けたっ!

本日のツッコミ(全1件) [ツッコミを入れる]

_ ksk [おー,ずいぶん短くなりましたねぇ. こちらも引き続き頑張ってみます.]


2007-02-22 [長年日記]

_ [Golf][OCaml] あなごる delete blank lines

kskさんに追い付かれたので予告通りネタばらし。

let rec f s=s<>""&()=print_endline s;f(read_line());;f""
  • 使用後
let rec f s=s>""&()=print_endline s;f(read_line());;f""

つまり、"" 以外の文字列は "" よりも大きいから <> ではなく > で十分なのです。

本日のツッコミ(全1件) [ツッコミを入れる]

_ ksk [私も全く同じ方法です.これは他にも役立ちそうなノウハウですね.]


2007-02-23 [長年日記]

_ [Golf][OCaml] あなごる Hamming numbers

なぜそれで動くのかはさっぱり理解していませんが、魔法を使ったら縮みました。

Obj.magic true => 1
Obj.magic false => 0

ってことかな。

_ [Golf][OCaml] あなごる fibonacci

ひねる必要の無い終了条件があったじゃないか!

ようやくkskさんに追い付いた。

本日のツッコミ(全2件) [ツッコミを入れる]

_ ksk [すみません.トラックバックを送ったら化けてしまったみたいです.]

_ うかい [たぶん化けた原因はこっち側の環境のせいですね...ご迷惑お掛けします]


2007-02-26 [長年日記]

_ [Golf][OCaml] 演算子法(ネタばれ)

いやーこれはすごい技だ。suiginto さんすごい。 prime numbers はとうとう二桁台に突入してしまいましたよ。

# ハミング数は追い付いたけれど中身が全然違いそうですね。

この技、 応用できるケースは少ないですが、単にスペース分が減るだけじゃない事も出来たりします。

let f a b=hoge;;f p q;f r s
let(@)a b=hoge;;p@q;r@s
let(@)a b=hoge;r;;p@q@s

演算子関数に値をうまく返してやると、 最後のように演算の連続にすることで短くなるようなケースがあるよ (例では同じ長さだが)。

_ [Golf][OCaml] あなごる ちょーネタばれ

最後の?隠しネタをネタばらし。

今までずいぶんと使ったけれど、最新の記録ではあまり使わなくなった、 というのもあって。

ヒントは書いたことがあるけれど。

固定回数のループを再帰で書く場合、

let rec f i=i>0&f(...;i-1);;f(read_int())

などと、ループの非終了条件になる i>0 を書くと思うが、 「ゴルフ場は標準エラー出力に何を出してもいい」のだから、

let rec f i=f(...;i-i/i);;f(read_int())

と書ける。Division by Zero 例外で再帰を抜けるわけだ。 もっとも簡単なのは上の通り、定数の 1 を i/i で置き換える。

prime numbers はこれを使っても使わなくても 97B になってしまったのだが、それまではこれを利用していた。

類似のネタとして、配列や文字列の Out of bounds も使える。