プログラミング言語APLで謹賀新年Golf

2012年の元旦ということで、プログラミング言語APLで謹賀新年Golfをやってみました。
APL2012golf-73byte
APLとはA Programming Languageの略で、1957年のFORTRAN登場以降にケネス・アイバーソン博士によって発明された数式処理のための記法をIBMが対話型のプログラミング言語として修正し実装したものです。当時は⍳{iota}や⍴{rho}など特殊な記号を入力するためのAPLキーボードがあったそうです。
APL-keyboard
今ではAPLフォントの記号はすべてUnicodeの中で定義されています。
先月開催したサイボウズ・ラボユース冬の合宿では、林拓人さんが筑波大学の図書館から借りてきたAPLの教科書があったので少し斜め読みしてみました。それで、APLの記号の使い方が大体わかったので、今回の謹賀新年Golfをしてみることにしました。
まずは91文字のAPLプログラム。
11×((3⊖5 o↑1⌽(1 o⍴⍳o)∊3 o)+1⊖5 o↑1⌽(2 o⍴⍳o)∊3 7 o)+1-((5 o⍴0,⍳27)∊o(o+10))∨(5 o⍴⍳o)∊2×⍳o←13

11 11 11 0 11 11 11 0 11 0 11 11 11
0  0 11 0 11  0 11 0 11 0  0  0 11
11 11 11 0 11  0 11 0 11 0 11 11 11
11  0  0 0 11  0 11 0 11 0 11  0  0
11 11 11 0 11 11 11 0 11 0 11 11 11

こんな感じで上のAPLの1行プログラムを実行すると、5×13のマトリクスで表現された 2 0 1 2 という 0 1 の数列が出力されます。バイナリアンになった気持ちで、0は空白、11はドットで塗り潰す、という心の眼で実行結果を見てください。今年の西暦2012に見えますよね?

■■■□■■■□■□■■■
□□■□■□■□■□□□■
■■■□■□■□■□■■■
■□□□■□■□■□■□□
■■■□■■■□■□■■■

もうちょっと数列の作り方を工夫すればコードが短くなるかな、と思ってGolfしたのがこちら。67文字。
11×1+(8⌽1⊖5 o↑2 1⍴1)-(⍵+3⌽⍵←4⊖5 o↑3 3⍴7⌽5<⍳9)+5 o⍴¯2⌽(o⍴⍳o←13)∊2×⍳4

11 11 11 0 11 11 11 0 11 0 11 11 11
0  0 11 0 11  0 11 0 11 0  0  0 11
11 11 11 0 11  0 11 0 11 0 11 11 11
11  0  0 0 11  0 11 0 11 0 11  0  0
11 11 11 0 11 11 11 0 11 0 11 11 11

24文字も短くなっています!
非常に簡潔なコードですね。
APLの処理系はたくさんあるのですが、openAPLという処理系がオープンソースで公開されていて、Ubuntuでも何とか動かすことができました。
openAPL
しかし、X11のAPLフォントとキーバインドの設定がよくわからなかったので、結局はWindowsで動作するAPL処理系の一つNARS2000でプログラムを作成しました。林さんも合宿中はこの処理系を使ってAPLプログラミングを楽しんでいました。
■APLによるFizzBuzzとLifeGame (林拓人さん作)
APLによるFizzBuzzとLifeGame (林拓人さん作)
林さんは合宿中、自分でFizzBuzzやライフゲームのコードをフルスクラッチから書き起こしていて、かっこよかったです。
林拓人さんによるAPLプログラミング紹介
というわけで、今年の元旦は未来のプログラミング言語として評価の高いAPLの書き初めでした。
Javaアプレットとして動作するAPLetteという冗談のような名前のプログラムもあるそうです。ただ、こちらはAPLフォントによる直接入力ができないので、ASCIIテキストの記法で入力してあげる必要があります。
プログラミング言語Jの記法に馴染めなかったという人も、APLの記号ならわかりやすく理解できるかもしれません。温故知新のAPL。ぜひ、みなさんも楽しいAPLライフをお過ごしください。

カテゴリー: Golf

core dumpするコードの短さを競う「Core Golf」

まめめもさんの core golf のエントリー(6/27)より

さて、core dump するコードの短さで競う core golf はゲームとして成立するでしょうか。明らかに環境や処理系に依存するのでルールの決め方が難しいです。とりあえずうちでは core dump した C のコード (15B) 。もっと短くなる?

core dumpの定義はいろいろあると思いますが、とりあえず手元の環境 CentOS Linux x64_64 で segmentation fault が起きるコードで。

(1) C言語で core dump

早速、core dumpした5byteのCのコード。
(via. λx.x K S K @ はてな – core golf

main;
実行結果
$ echo -n "main;" > a.c && cc a.c && ./a.out 
a.c:1: 警告: データ定義が型や記憶クラスを持っていません
a.c:1:6: 警告: no newline at end of file
zsh: segmentation fault  ./a.out

コンパイラの警告は出るけどちゃんと実行バイナリができて、それを実行するとsegmentation faultしてくれます。

(2) Perlでcore dump

正規表現でsegmentation faultを起こすのが簡単かな、と思ってトライ。Perlで22byte。
(via. [perl #33945] Segmentation fault with deep recursion in regex engine

$x=qr/(??{$x})/;""=~$x
実行結果
$ perl -e'$x=qr/(??{$x})/;""=~$x' 
zsh: segmentation fault  perl -e'$x=qr/(??{$x})/;""=~$x'

barewordを使ってもよければもう1byte節約することができますが、とりあえずここまで。

(3) Rubyでcore dump

ruby-devのMLには、最新のrubyをcore dumpさせるコードがたくさん投稿されているようです。以下、手元の環境で再現した5byteのコードです。
(via. [ruby-dev:31085] 0..:" dumps core

0..:"
実行結果
$ ruby -e '0..:"'
-e:1: unterminated string meets end of file
-e:1: empty symbol literal
-e:1: [BUG] Segmentation fault
ruby 1.8.5 (2006-08-25) [x86_64-linux]

アボートしました

最強言語 Ruby ?

あと、Ruby 1.8系では正常に(?)core dumpできませんが、Ruby 1.9 では 4byte で core dump 可能なコードもいくつか報告されているみたいでした。
もしかしたら最新のリリースビルドでは再現できないかもしれません。

$ ruby -e '$&;[]'
$ ruby -e '$`;0'
$ ruby -e '$1;0'
$ ruby -e '{*0}'

ということで、現在 Ruby 1.9 が 4 byte で Core Golf 最強になっていますが、3 byte 以下で core dumpできる処理系をご存知の方がいらっしゃいましたら教えてください。

SWF Binary Golf on FlashLite

先週の土曜日の勉強会で発表した資料を公開します。

FizzBuzz SWF Binary Golf on FlashLite 1.1

FizzBuzz SWF Binary Golf on FlashLite 1.1
http://namazu.org/~takesako/swf/FizzBuzz-SWF-Golf.ppt

申し訳ないことにActionScriptの話は一つもでてきません。
SWFファイルの構造解析とASバイトコードの話です。
そんなシチュエーションがあるかどうかわかりませんが、
SWFファイルのバイナリを直接いじりたいときに役に立つのではないかと。

勉強会ではどの発表も面白かったのですが、個人的にはBeInteractive!のyossyさんとASバイトコードの話ができて嬉しかったです。

[お約束] SWF で FizzBuzz ってみた

とりあえず

(1) 正解のFizzBuzz文字列をそのまま出力した場合 -> 478 byte (FlashLite1.1)
http://namazu.org/~takesako/swf/fizz478.txt

(2) FizzBuzzを計算しながら出力した場合 -> 251 byte (FlashLite1.1)
http://namazu.org/~takesako/swf/fizz251.txt

(3) FizzBuzzを計算しながら出力した場合 -> 159 byte (FlashLite2.0)
http://namazu.org/~takesako/swf/fizz159.txt

ここまで圧縮できました。

ASバイトコード最適化

ASバイトコードの最適化の過程はこんな感じで

http://namazu.org/~takesako/swf/

--- fizz287.flm	
+++ fizz161.flm
@@ -1,71 +1,48 @@
-movie 'fizz287.swf' // flash 4, total frames: 1, frame rate: 12 fps, 104x104 px
+movie 'fizz161.swf' compressed // flash 6, total frames: 1, frame rate: 12 fps, 104x104 px

   frame 0
-    push 'i', '0'
-    setVariable
    label1:
-    push 'i', 'i'
+    push '100', 'i', 'i', 'i'
     getVariable
     increment
     setVariable
-    push '100', 'i'
     getVariable
     oldLessThan
-    not
-    not
     branchIfTrue label6
-    push 'x', 'x', 'x'
-    getVariable
-    push 'i'
+    push 'x', 'x'
     getVariable
     push 'i'
     getVariable
     push '15'
-    divide
-    int
-    push '15'
-    multiply
-    subtract
+    modulo
     branchIfTrue label2
     push 'FizzBuzz'
     branch label5
    label2:
     push 'i'
     getVariable
-    push 'i'
-    getVariable
     push '5'
-    divide
-    int
-    push '5'
-    multiply
-    subtract
+    modulo
     branchIfTrue label3
     push 'Buzz'
     branch label5
    label3:
     push 'i'
     getVariable
-    push 'i'
-    getVariable
     push '3'
-    divide
-    int
-    push '3'
-    multiply
-    subtract
+    modulo
     branchIfTrue label4
     push 'Fizz'
     branch label5
    label4:
     push 'i'
     getVariable
    label5:
     concat
     push ' '
     concat
     setVariable
     branch label1
    label6:
   end // of frame 0
end

yossyさんから教えてもらったFlasmのコードでASバイトコードを読みやすい形に変換しています。

最後のFizzBuzz159byteへの圧縮は、ちょっとトリッキーなことをしています。

僕はActionScriptの経験は素人以下ですが、SWFバイナリの話ならできますので、
またどこかでAS関係のイベントがあれば声を掛けてくださると嬉しいです。(><)

この度は貴重な勉強会に参加できてよかったです。ありがとうございました。

連載企画 FizzBuzz ではじめる Code Golf (x86 32bit) 入門

Code Golf とは? Matzにっき(2006-10-05) より

ゴルフとは如何に少ないストロークでホールインするかを競う競技である。
コードゴルフとは、如何に少ないキーストローク(バイト数)で、プログラムを実装できるかを競う競技である。

先日FizzBuzz.com (MS-DOS 16bit版) を作ってみたら、32bit版のプログラムにも挑戦したくなりましたので、x86 32bitで命令長を減らすテクニックについて紹介したいと思います。

※まずはコード長の比較のみで実行クロック数は競わないことにします。

■ x86 32bit コード最適化

【問題】EBXレジスタに1を、EAXレジスタに4を代入したい

できるだけ短いバイト数でコードを実現するためには、いろいろなx86命令をフル活用することを考えます。

自分の思いついた解答をNASMの記法で書いてみます。

続きを読む

FizzBuzz x86 for バイナリアン

昨日の続き。今日は息抜きに FizzBuzz.com (MS-DOS 16bit版) を作ってみました。

0000000 b4 02 bb 31 30 30 ed e8 2c 00 e8 29 00 e8 39 00 
0000020 e8 23 00 e8 3e 00 e8 30 00 e8 1a 00 e8 17 00 e8
0000040 27 00 e8 2f 00 e8 0e 00 e8 1e 00 e8 08 00 e8 05
0000060 00 e8 13 00 eb d1 80 ff 30 74 04 88 fa cd 21 88
0000100 da cd 21 e8 28 00 c3 fe c5 b2 46 cd 21 b2 69 cd
0000120 21 e9 08 00 b2 42 cd 21 b2 75 cd 21 b2 7a cd 21
0000140 cd 21 84 ed 75 04 e8 05 00 c3 30 ed eb e6 b2 0d
0000160 cd 21 b2 0a cd 21 fe c3 80 fb 3a 75 09 b3 30 fe
0000200 c7 80 ff 3a 74 01 c3 b8 00 4c cd 21
0000214

これで140byte

続きを読む

FizzBuzz – Golf Challenge

FizzBuzzプログラムを書くのが流行っているみたいなので私も参加してみることに。

Perl部門

1. 目指せ最短 (perl -eも含めて56byte)

perl -e’die+map{(Fizz)[$_%3].(Buzz)[$_%5]||$_,$/}1..1e2′

※ perl -lオプションを使わずに最短を目指す。標準エラー出力がNGの場合はprintを使って57byteに

perl -e’print+(Fizz)[$_%3].(Buzz)[$_%5]||$_,$/for 1..1e2′

anarchy golf – FizzBuzz で換算すると48byteでPerl最短 (perl -eを含めない)

print+(Fizz)[$_%3].(Buzz)[$_%5]||$_,$/for 1..1e2

これだと perl FizzBuzz.pl と実行できて Code Golf に参加できます。

お約束の展開

2. ppencodeバージョンで

perl -e "print q q print q and print chr oct oct ord uc q map m and print chr oct oct oct ord uc q else and print chr ord uc qw q for q and print chr ord q tie gt and print chr length q x rename sethostent srand pack pipe setpwent syscall else eq split sleep endservent qw require symlink ne keys ord require x and print chr length q q splice srand getservbyname setnetent ne reset endprotoent foreach scalar rewinddir cos setnetent not else getprotobyname q and print chr oct oct oct ord uc q rmdir and print chr oct hex ord uc q dump and and print chr oct oct oct ord uc qw q binmode q and print chr oct hex ord uc q my m and print chr oct oct oct ord uc q oct no and print chr oct oct ord uc q rmdir and print chr oct hex ord uc qw q wait q and print chr oct oct ord uc qw q fcntl q and print chr oct hex ord q q eq and print chr ord uc qw q bind q and print chr ord q dump and and print chr length q q splice srand getservbyname setnetent ne reset endprotoent foreach scalar rewinddir cos setnetent not else getprotobyname q and print chr length q q splice srand getservbyname setnetent ne reset endprotoent foreach scalar rewinddir cos setnetent not else getprotobyname q and print chr oct oct oct ord uc q rmdir and print chr oct hex ord uc q dump and and print chr oct oct oct ord uc qw q bless q and print chr oct hex ord uc q my m and print chr oct oct oct ord uc q lc eval and print chr oct ord uc q each ne and print chr oct hex ord uc qw q wait q and print chr oct oct hex ord qw q die q and print chr oct oct hex ord qw q die q and print chr oct oct oct ord uc qw q binmode q and print chr oct hex ord uc q my m and print chr oct oct ord uc qw q bind q and print chr oct oct oct ord uc qw q binmode q and print chr oct oct ord uc qw q gt q and print chr ord qw q for q and print chr ord q xor x and print chr ord q or no and print chr ord q q q and print chr oct oct oct ord q eq ne and print chr oct oct ord uc qw q fcntl q and print chr oct oct ord uc qw q for q and print chr oct oct oct ord q eq le and print chr ord q ne sin and print chr hex ord q m alarm" | perl

※ perlの予約語だけでプログラミングした場合

他の Perl Monger の解答

3. 404 Blog Not Found:ブクマゴルフってどうよ? (66byte)

perl -le ‘print $_%15?$_%5?$_%3?$_:Fizz:Buzz:FizzBuzz for(1..100)’

※オーソドックスな実装

4. ひおにっき(2007-05-09) [Program] FizzBuzz (56byte)

perl -le’print+(Fizz)[$_%3].(Buzz)[$_%5]||$_ for 1..100′

※インスパイヤの元ネタ。おそらくこれが最短でスマートな実装かも。hioさんの実装よりも短くしようと頑張ったけど、結局抜けませんでした。

5. Golf Challenge: FizzBuzz (この中から面白い実装をピックアップ)

perl -le ‘print+($_,Fizz,Buzz,FizzBuzz)[3&19142723>>2*$_%30]for 1..100′

※ あとでググって見つけたページ。自分の解答もかぶっててちょっと悔しかったです。(><)

6. YappoLogs: FizzBuzzのPerlさいたんきろくたっせい(34ばいと) (Yappoさんのwarn実装)

perl -le’warn((Fizz)[$_%3].(Buzz)[$_%5]||$_)for 1..100′

※ FizzBuzz at -e line 1. みたいな表示になるけど、hioさんの実装より1byte短くなる

7. Acme::FizzBuzz を使えば、これ最強

SET PERL5OPT=-MAcme::FizzBuzz                 # MS-DOSの場合
setenv PERL5OPT="-MAcme::FizzBuzz"            # tcsh系の場合
PERL5OPT="-MAcme::FizzBuzz"; export PERL5OPT  # bash系の場合

※ 環境変数PERL5OPTを使う方法はmiyagawaさんに教えてもらいました。

perl -e1

やっぱりPerl最強です。Ruby や Python でもこの最短記録を抜けるのかな?

anarchy golf – FizzBuzz #Language Ranking ではPerlを抜いてBashが1位で43byte、すげー。どんなコードなんだろうか。興味津々です。