Shinichiro Hamaji <shinichiro.hamaji _at_ gmail.com>

Presentation on theme: "Shinichiro Hamaji <shinichiro.hamaji _at_ gmail.com>"— Presentation transcript:

1 Shinichiro Hamaji <shinichiro.hamaji _at_ gmail.com>
Code Golfについて Shinichiro Hamaji <shinichiro.hamaji _at_ gmail.com> 2007年8月9日 夏のプログラムシンポジウム

2 概要 Code Golfとは 歴史や派閥など 意義と面白さ アルゴリズム選択の重要性 なんでもアリの最小化 各言語のゴルフ

3 概要 Code Golfとは 歴史や派閥など 意義と面白さ アルゴリズム選択の重要性 なんでもアリの最小化 各言語のゴルフ

4 Code Golfとは ゴルフ: 少ないストローク数でホールインす ることを競う
ショートコーディングなどとも

5 具体例(仕様) 空行削除: 標準入力から受け取った文章から 改行だけの行を除去しろ。
標準入力: hoge fuga foo bar 標準出力: hoge fuga foo bar

6 具体例(投稿) コードを書いて Webフォームから投稿すると サーバが自動的に実行して動作確認して OKなら記録が残る
delete blank lines - result Success! test #1 success! size: 111 time: sec #include <stdio.h> int main() { char line[256]; while (gets(line)) { if (line[0]) puts(line); }

7 具体例(圧縮) 適当に縮めて37B 短さだけが正義 #includeしてない intの省略、mainの引数が一つだけ
int*をgetsに渡してputsに至っては引数省略 リトルエンディアンを仮定 @ (ASCIIで64)で始まる文字列が来ないと 仮定 main(i){for(;gets(&i);)i&63&&puts();}

8 具体例(制約条件) 基本的にはなんでもアリではあるものの 外部プロセス呼び出し禁止 main(){system("perl ...");}
モジュール禁止 ファイル入出力禁止 制限時間 バイナリ文字列の使用制限 eval Zlib.decode("*BINARY*") などの制限がつくことも

9 概要 Code Golfとは 歴史や派閥など 意義と面白さ アルゴリズム選択の重要性 なんでもアリの最小化 各言語のゴルフ

10 歴史 おそらくオリジナルはPerl Golf プログラムで変なことさせたらPerlは天下 一品
2001年にはNewsGroupでコンペティション が 520ページにも及ぶPerlgolf History Book もちろんそれ以前にもコードサイズを縮める 文化は多数存在していた 「ハッカーズ」によるとMITの学生はコー ドサイズを縮めることに魂を注ぎ込んでい た IOCCCにも短いコードは何度も登場

11 歴史2 Code Golf (2006/5~) http://codegolf.com/
Perl だけでなく、Ruby, Python, PHPも使用 可 運営者が出題して真剣に競う 休止気味？ Anarchy Golf (2007/01~) 約50言語をサポート ユーザーが出題して適当に競う

12 参加者 Code Golfサイトのtop10中6(7?)人が日本人 http://golf.shinh.org/
全部で: access/month トップ: access/month ~1000 unique users ちょっとしたブーム？

13 Short Coders C言語では北京大学がICPCなどの練習用とし て公開しているオンラインジャッジシステム を用いてゴルフをする文化がある 他のゴルフよりややアルゴリズム重視 Short Coding 職人達の技法

14 ゴルフで人気の言語

15 ゴルフに強い言語 数字は平均点、左にある言語ほど合計点が上

16 概要 Code Golfとは 歴史や派閥など 意義と面白さ アルゴリズム選択の重要性 なんでもアリの最小化 各言語のゴルフ

17 意義 昔はコードサイズ=実行速度だった 今でもハードウェア屋だと命令数は重要
とはいえ現在では基本的にゴルフによって作 られたコードは実用性は皆無 メンテ不能 最速・省メモリとも限らない というわけで基本的にはJust for Fun だと、私は考えています

18 何がおもしろいのか？ 一般化はできないのですが、個人的には パズルゲームとして
コードを眺めつつチマチマ削るのは数独な どのパズルに通じるものがあるかも 元々ヘンなコードが好き Quine, Polyglot, esoteric languages プログラム言語の可能性 1000ケタの円周率をbzip2で圧縮して524B Rubyだと54B

19 副産物としての意義 プログラマのための頭の体操 新しい言語を学ぶ時にとりあえずゴルフの問 題を解いてみるという学習法
ゴルフのためにRubyを覚えたゴルファー 、優秀な成績を残すがclassの書き方すら知 らない事件 短いイディオムや言語機能は身につく ひとつやり方を覚えると使い続けてしまう 現象 勝ちたければ新しい表現を模索する必要が ある 実は短いコードはたいてい速い 最初は時間制限にひっかかったけど縮めて いたら通ったり

20 概要 Code Golfとは 歴史や派閥など 意義と面白さ アルゴリズム選択の重要性 なんでもアリの最小化 各言語のゴルフ

21 基本はアルゴリズム 意外にも、最も差がつく部分 例えば自分が100Bで解いた問題を他の人 が70Bで解いてたら間違いなくアルゴリズ ムが違う
とにかく色んな方法で問題をとらえてみる 多くの場合、速いアルゴリズムは短い 特に長い/難しい問題では

22 空行削除問題アゲイン 22B 21B 空行削除をCの感覚でRubyで解いてみると while l=gets puts l if l=~/./
end 22B 適当に縮める print if/./ while gets #!ruby -p sub /^ /,'' #!ruby -p next if/^ / #!ruby -n print if/./ 21B

23 発想の転換 18B! 14B! 「一行ずつ読んで空行じゃなきゃ表示する」 →「全部読んで空行だけの行を捨てる」
良いアルゴリズム>細かい小細工 puts $<.map-["\n"] 18B! 暗号化ゴルフイディオム適用 $><<[*$<]-[$/] 14B!

24 中置記法→後置記法問題 普通に考えると再帰下降のパーサとか書く Shunting yard algorithm とかいうのがあるら しい
標準入力: a+b+c*d a*b*(c+d)+e 標準出力: ab+cd*+ ab*cd+*e+ 普通に考えると再帰下降のパーサとか書く Shunting yard algorithm とかいうのがあるら しい 間違いなく暗号(104B) #!ruby -p $\="( " z=/([^(]*)/ gsub(/\W/){|c|$\["+-"[c]?z:"("[c]?//:c>")"?/([*\/]*)/:/#{c="";z}\(/]=c;$1}

25 処理系におまかせ 61B! Rubyはもともと中置記法→eval a,b,c,dは未定義な変数→method_missing
逆にpが定義済みなので邪魔→undef 短くなったのに暗号度大幅にダウン undef:p def method_missing s,* $><<s end loop{eval(gets)<<$/} 61B!

26 概要 Code Golfとは 歴史や派閥など 意義と面白さ アルゴリズム選択の重要性 なんでもアリの最小化 各言語のゴルフ

27 暗号記述言語Perl Hello, world!
by ppencode ( e/demo.html) ') length q caller exec and print chr ord uc q chr lc and print chr ord q ref or and print chr ord q else and print chr ord q else and print chr ord q xor x and print chr oct oct ord uc qw q bind q and print chr ord q q q and print chr ord q qw q and print chr ord q xor x and print chr ord q qr eq and print chr ord q else and print chr ord qw q die q and print chr hex length q q bless localtime ref q

28 暗号記述言語Perl rev(1) 明らかに括弧の対応がおかしい 標準入力: hoge fuga foo bar baz 標準出力: baz
#!perl -p $\=$_.$\}{

29 暗号記述言語Perl 実は-pオプションは前後にプログラムコード を追加しているだけというすごい実装 while (<>) {
$\=$_.$\ } { print; #!perl -p $\=$_.$\}{

30 マインスイーパ まわりにある爆弾の数を数える
Perl Golf history book p ip.org/perlgolf_history_ pdf 標準入力: ....***. ...**.*. ..**.... ...***** ...*.*.* ...*.*** 標準出力: 0013***2 013**5*2 01**6543 014***** 003*7*8* 002*4***

31 Insane Perl Golfers 36B (ただしPerl Golfでは#!perlはカウントしな い) 正規表現1個で終了
しかもほぼ同一の解に4人が到達 #!perl -p0 s!\.!map/"/g,$`.666e6x3&$^.$_!eg

32 正規表現の構文でループ shebangは入力を全て$_に入れるという意味
#!perl -p0 s!\.!map/"/g,$`.666e6x3&$^.$_!eg shebangは入力を全て$_に入れるという意味 $_=" \n \n....***.\n …"; s!\.!!eg は、全ての.を、右辺を実行した結果 に置き換える、という意味 s///egはループの代用としてよく使われる

33 悪魔の数字 $`はマッチした部分の左側文字列 666e6=666000000
#!perl -p0 s!\.!map/"/g,$`.666e6x3&$^.$_!eg ここがマッチ したとする $`はマッチした部分の左側文字列 666e6= 666e6x3= まさにマジックナンバー ....***. ...**.*. ..**.... ...***** ...*.*.* ...*.***

34 悪魔の数字 $`はマッチした部分の左側文字列 666e6=666000000
#!perl -p0 s!\.!map/"/g,$`.666e6x3&$^.$_!eg $`はマッチした部分の左側文字列 666e6= 666e6x3= つまり右図のような文字列…？ ....***. ...**.*. ..**.666 00000

35 謎の特殊変数 $^は"STDOUT_TOP"という文字列 10Byte(8+1+1)の文字列なら なんでも良かった
#!perl -p0 s!\.!map/"/g,$`.666e6x3&$^.$_!eg 一行と一列 だけずれた $^は"STDOUT_TOP"という文字列 10Byte(8+1+1)の文字列なら なんでも良かった $_は最初に全部読み込んだ STDOUT_T P ....*** ...**.* ..**... ...**** ...*.*. ...*.**

36 文字列& & = 全ての文字に対して論理和 #!perl -p0 s!\.!map/"/g,$`.666e6x3&$^.$_!eg
....***. ...**.*. ..**.666 00000 STDOUT_T P ....*** ...**.* ..**... ...**** ...*.*. ...*.** ???????? ? ...***. ..***** .***"&" &&& """ & =

37 mapで数を数える言語 後は"の数を数えるだけ
#!perl -p0 s!\.!map/"/g,$`.666e6x3&$^.$_!eg 後は"の数を数えるだけ 神秘的な理由により、Perlでは関数型言語で おなじみのmap関数を使って文字列中に出現 した部分文字列の数を数えることができる

38 C 機械語をはじめとして、低レベル技術と仲良 しであることが必要 スタックやらポインタやら ビット演算 ~演算子
x*(x+1) vs. x*-~x -10 vs. ~9 for(;~scanf("%d");)

39 qsort void qsort(void *base, size_t nmemb, size_t size,
int (*cmp) (const void *, const void *));

40 qsort (正しい実装) intをソートしたい 完全に問題の無い実装 ゴルフとしては0点
int cmp(void *a0, void *b0) { int *a=a0, *b=b0; return *a<*b?-1:*a>*b; } int main() { // ... qsort(ary, size, 4, &cmp);

41 qsort (入力依存) intをソートしたい 型宣言を消して引き算でかえり値を計算 オーバーフローの危険 ゴルフとしては50点
c(int*a,int*b) { return*a-*b; }

42 qsort (引数減らし) intをソートしたい メモリ空間の知識がないと理解できない C言語の知識がないと理解できない
c(int*a) { return*a-**(&a+1); } c(int*a) { return*a-*1[&a]; }

43 qsort (return消し) intをソートしたい アセンブリの知識がないと理解できない 代入しとけばEAXに残ったままの場合があ る
c(int*a) { a=*a-*1[&a]; }

44 qsort (x86) intをソートしたい Cは匿名関数をサポートした言語 これで短くなるのはCISCの神秘 11Byteで9命令
pop, pop, pop, push, push, push, mov, sub, ret 処理系依存でさらに短くなったりも qsort(ary, size, 4, "YXZQQQ\x8b\0+\x02\xc3");

45 まとめ Code Golf について概要および実際のコード を紹介しました 言語自身や処理系の癖などについて、広い知 識が必要なパズル
たぶん時間がないと思って割愛しましたが、 OCaml, Haskell, LISP, PHP, PostScript, sed, Bash, Brainf*ck, Befungeでのゴルフや、サー バの構成について補足としてつけました

46 概要 Code Golfとは 歴史や派閥など 意義と面白さ アルゴリズム選択の重要性 なんでもアリの最小化 各言語のゴルフ

47 OCaml 関数名が長い(print_string) 型システムをいかに騙すか Trueより1>0 切り札Obj.magic
if c then print_stirng"hoge"よりc&()=print_string"hoge" 切り札Obj.magic 自然対数の底の小数点以下を100ケタ表示 せよ Obj.magic Array.iter print_int"\173\137g \023\245\214d \151L\230\\147\255\031\016K=y\\\238\233p\000o\153\138D Y\158\212J\023\221$K\237\224\224F\221'H\021e!\000"

48 Haskell 割と強い Cより強くてスクリプト言語に負けるくら い 気の効いた標準関数群
interact :: (String -> String) -> IO() 細かいシンタクスシュガー $で括弧を除去 main再帰 main=...>>main

49 CLISP / Scheme あまり強くない？ マクロがあるとは言うけれど そもそもマクロが生きるほど長い問題は少 なめ
可読性無視のゴルフでは、LISPのマクロが 使える局面では、スクリプト言語のevalも 使える

50 PHP Hello, world!最強言語 基本的には長い標準関数名が不利でスクリプ ト言語としてはイマイチ ereg_replace

51 PostScript 割と強い その上バイナリ表現ができる

52 sed 実は四則演算やソートくらいはできる 単純な問題で無類の強さ 空行除去5B
ただし、難しい問題はそもそも制限時間内に 解けないことが多い /^$/d

53 Bash FizzBuzz最強 1から100まで数え上げていって、3の倍数 ならFizzを、5の倍数ならBuzzを、15の倍 数ならFizzBuzzを出力し、それらでなけれ ばその数値を出力する。 seq 100|sed 5~5s/.*/Buzz/\;3~3s/[^B]*/Fizz/

54 Brainf*ck ただ解くだけでも大変 データの用意のしかたが重要 16を用意したいのなら… メモリ領域を喰いつぶしていく
0クリアしたい場合、[-]とかするより>で 新しいメモリアドレスに 空行除去 ++++[->++++<] ,+[-[-<+<+>>] < [<.>>>>] <<[>.>>] >>,+]

55 Befunge 2D言語ゴルフ 演算能力は結構ある calを253Bで 非常に独特のパズルに なるべく左寄せ 行数は少なく
v 0&#&%&%&&%&%& >25*"aS rF hT eW uT oM uS">:#,_&v v+g0p00:&--+/4:/**455:/***2558::< >\:::554**%!\4%+\8552***%*!\v v:%7-p12+g12*!-2g00:*!`2g00$< >v >1-" ",,, v>:#^_ >1+:: 9`!#v_ #vv# " "\_v 52*,$0\:v>" ",>.\1+:7%^> |--7g1g00<: < #v_>~:52*-:#v_$\ 0< ^,

56 x86 ELFヘッダとプログラムヘッダと機械語をが んばって重ねる
CISCマジック 1Bでも強力な子たち: push, pop, inc, dec, ... decでZFが立つとか for (int i = 0; i < 10; i++) { ... } for (int i = 10; --i; ) { ... } 未だに残る8bitレジスタ群 2Bで計算実行

57 サーバ構成 Celeron 1.7GHz, 384MB, Ubuntu linux 負荷記録: 20000access/6hours
Webサーバ(lighttpd & mod_fastcgi) 実行以外の全てを担当 実行サーバ(Xen) 基本的にノーガード fork連打やファイル書き込みで破壊可能 ネットワークはホストとしかつながってい ない 人様には迷惑をかけない exec(2)対策にstrace(1)を利用