Hatena::ブログ(Diary)

まめめも このページをアンテナに追加 RSSフィード

2009-09-16

[][][][][][][][][][][] quine リレー

Update (2013-07-15): I improved this program to 50-language version. 50 言語版にパワーアップさせました。


これはこのプログラム自身を出力する Unlambda プログラム、を出力する Whitespace プログラム、を出力する brainfuck プログラム、を出力する Java プログラム、を出力する C プログラム、を出力する Haskell プログラム、を出力する OCaml プログラム、を出力する Lua プログラム、を出力する Perl プログラム、を出力する Python プログラム、を出力する Ruby プログラム、です。

# ruby
l=92.chr;eval s="s=s.dump[r=1..-2].gsub(/("+l*4+"){4,}(?!\")/){|t|'\"+l*%d+\"'%(t
.size/2)};5.times{s=s.dump[r]};puts\"# python\\nprint(\\\"# perl\\\\nprint(\\\\\\
\"# lua"+l*4+"nprint("+l*7+"\"(* ocaml *)"+l*8+"nprint_endline"+l*15+"\"-- haskel
l"+l*16+"nimport Data.List;import Data.Bits;import Data.Char;main=putStrLn("+l*31
+"\"/* C */"+l*32+"n#include<stdio.h>"+l*32+"nint main(void){char*s[501]={"+l*31+
"\"++intercalate"+l*31+"\","+l*31+"\"(c(tail(init(show("+l*31+"\"/* Java */"+l*32
+"npublic class QuineRelay{public static void main(String[]a){String[]s={"+l*31+"
\"++intercalate"+l*31+"\","+l*31+"\"(c("+l*31+"\"brainfuck"+l*64+"n++++++++[>++++
<-]+++++++++>>++++++++++"+l*31+"\"++(concat(snd(mapAccumL h 2("+l*31+"\"110"+l*31
+"\"++g(length s)++"+l*31+"\"22111211100111112021111102011112120012"+l*31+"\"++co
ncatMap("+l*32+"c->let d=ord c in if d<11then"+l*31+"\"21002"+l*31+"\"else"+l*31+
"\"111"+l*31+"\"++g d++"+l*31+"\"22102"+l*31+"\")s++"+l*31+"\"2100211101012021122
2211211101000120211021120221102111000110120211202"+l*31+"\"))))))++"+l*31+"\","+l
*63+"\""+l*64+"n"+l*63+"\"};int i=0;for(;i<94;i++)System.out.print(s[i]);}}"+l*31
+"\")))))++"+l*31+"\",0};int i=0;for(;s[i];i++)printf("+l*63+"\"%s"+l*63+"\",s[i]
);puts("+l*63+"\""+l*63+"\");return 0;}"+l*31+"\");c s=map("+l*32+"s->"+l*31+"\""
+l*63+"\""+l*31+"\"++s++"+l*31+"\""+l*63+"\""+l*31+"\")(unfoldr t s);t[]=Nothing;
t s=Just(splitAt(if length s>w&&s!!w=='"+l*31+"\"'then 501else w)s);w=500;f 0=Not
hing;f x=Just((if x`mod`2>0then '0'else '1'),x`div`2);g x= reverse (unfoldr f x);
h p c=let d=ord c-48in(d,replicate(abs(p-d))(if d<p then '<'else '>')++"+l*31+"\"
."+l*31+"\");s="+l*31+"\"# ruby"+l*32+"n"+l*31+"\"++"+l*31+"\"l=92.chr;eval s=\"+
(z=l*31)+\"\\\"\"+s+z+\"\\\""+l*31+"\"++"+l*31+"\""+l*32+"n"+l*31+"\""+l*15+"\""+
l*7+"\")"+l*4+"n\\\\\\\")\\\")\"########### (c) Yusuke Endoh, 2009 ###########\n"

最初のコメント行以外の改行は読みやすさのために入れています。QuineRelay.rb などというファイルとして保存してください。以下のように実行します。

$ ruby QuineRelay.rb > QuineRelay.py
$ python QuineRelay.py > QuineRelay.pl
$ perl QuineRelay.pl > QuineRelay.lua
$ lua QuineRelay.lua > QuineRelay.ml
$ ocaml QuineRelay.ml > QuineRelay.hs
$ runghc QuineRelay.hs > QuineRelay.c
$ gcc -Wall -o QuineRelay QuineRelay.c && ./QuineRelay > QuineRelay.java
$ javac QuineRelay.java && java QuineRelay > QuineRelay.bf
$ beef QuineRelay.bf > QuineRelay.ws
$ wspace QuineRelay.ws > QuineRelay.unl
$ unlambda QuineRelay.unl > QuineRelay2.rb

最終的に得られる出力 QuineRelay2.rb は最初の Ruby プログラムと一致するはず。

$ diff QuineRelay.rb QuineRelay2.rb

念のため各処理系バージョンを書いておきます。すべて Debian/lennyaptインストールできるものです。

2007-06-10

[] SemiAutoMine: 半自動マインスイーパ

簡単なところを勝手に進めてくれてしまうマインスイーパです。若干考える余地が残っていますが、ほとんど運の勝負です。

http://dame.dyndns.org/misc/semiautomine/mine.jnlp

マインスイーパ 2000 プロジェクトという鬼のようなゲームをやりながら作りました。クリアしたよ!

マインスイーパは非常に機械的な作業の多いゲームで、誰しも一度は自動化を考えると思います (特にマインスイーパ 2000 をやると) 。しかし完全な自動回答は明らかに NP 完全の香りがするので*1、SemiAutoMine は以下の4点だけ自動で推論します。

  • 数字マスの周りにフラグマスと不確定マスが数字と同じ数しかない -> 周りの不確定マスに全部フラグを立てる
???     フフフ      ?:不確定マス
*5フ ==> *5フ      フ:フラグマス
**フ     **フ      *:数字マス
  • 数字マスの周りにフラグマスが数字と同じ数だけある -> 周りの不確定マスを全部開ける
???     開開開
*2フ ==> *5フ
**フ     **フ
  • 隣接する数字マスと数字マスから確実に機雷があるところ、ないところを判定する
????     開??フ
*12* ==> *12*
****     ****
  • 1 つ開けて隣接する数字マスと数字マスから確実に機雷があるところ、ないところを判定する
**???     **?開開
*1?1? ==> *1?1開
**???     **?開開

ただバグがあるので推論してくれないときもあります。原因は dirty flag の管理が適当なせいだとわかっているのですが面倒で直す気がしません。future work です。

少し一般化して、影響範囲が重なる任意の 2 つの数字マスについて推論するようにしたかったのですが、面倒で直す気がしません。future work です。

あと、下のような推論も面倒で実装する気がしません。future work です。

****     ****
*01?     *01?
*12? ==> *12?
*???     *??開

あ、SemiAutoMine はクリアしたことがないので、バグがあったらすみません (笑)


[] Java について思うこと

SemiAutoMine はアルゴリズムは大体決まっていたので 2 〜 3 時間くらいで動くものができると思ったのに、丸 1 日もかかってしまいました。Ruby ならきっと数時間でできます (実行速度が遅くて使い物にならないだろうけど) 。原因は明らかに Java にあると思う (Java Web Start を使いたかったので他に選択肢がなかった) のですが、ちょっとだけ詳しく考えてみました。

要するに Java への文句をたれます。Java マニアは目をつぶってください。


  • ドキュメントにサンプルコードがない ドキュメントはあればいいってもんじゃない、自然言語よりコードで語れ
  • ぐぐっても良いサンプルコードがなかなか見つからない コピペさせろ、メジャー言語のいいところは情報の多さじゃなかったっけ?
  • サンプルコードを見ていじるだけでは全然使いこなせない 特に Swing 周り、なんとなく真似しただけでは全然動かなくてストレスたまる、コンパイル時も実行時もエラーにならないのがさらにいらつかせる
  • ライブラリの作りや構成、メソッド名にセンスがない サンプルコードだけ見てもわからない主因?いいライブラリはドキュメントがなくてもサンプルコードがあれば使える
  • リテラルや無名関数がとても不十分なので何をするにも面倒くさい 内包表記や yield させろ
  • classpath や jar などツールの使い方で必ずはまる java.lang.NoClassDefFoundError は見飽きたんだよ
  • 何をするにもフレームワークばっかりで憂鬱
  • 末尾再帰最適化VM の仕様に入れてくれ (関係ない)
  • eclipse はなんかこう全体的に感じ悪い、キモい (FUD)

要約すると、Java は調べることが多すぎてコードを書くことに集中させてくれないので楽しくないです。これらの点、C# はかなりがんばってると思います *2Java を踏み台にしたおかげもあるのでしょうけどね。Sun はあせって Java を拡張してるみたいですけど、それは泥沼化なのでやっぱこの言語は一度廃棄すべき Javaアイデンティティーを失うことになるので難しいですよね。

*1:マインスイーパの解の存在判定は SAT に還元できるそうな。

*2Java の臭いがぷんぷんすることに加え、かつての VC++ の惨状を思い出してしまうので食わず嫌いしていたのですが、使ってみたらびっくりするほどいい感じです。きっと言語も開発環境もまじめにユーザテストしてるんだろうなぁ。

2007-05-31

boids

[][][] boids : 鳥の群れシミュレーション

boids の実装です。ぼーっと見たり、ドラッグで集めたり散らしたりして楽しんでください。

http://dame.dyndns.org/misc/boids/ (windows の IE と Firefox でしか動作確認していません)


boids (birdoids 、鳥もどき) とは 1986 年ごろ Craig Reynolds 氏が発表した鳥や魚の群れをシミュレーションする理論らしいです。参考サイト。要するに、

  • 仲間が近すぎる位置にいたら離れる
  • 周りの仲間と同じ方向を向いて飛ぶ
  • 周りの仲間の中心に近づく

という単純な 3 つのルールに従って鳥の群れをシミュレーションする感じ。


まあそんなことはどうでもよくて (?) 、これを作った真の目的は、swf と java applet の通信実験です。この boids は、表示は swf で、シミュレーションは java applet (下の方でちらちらしてるやつ) でやっています。この方法を使えば、swf よりはだいぶ速い java spplet で重い処理をこなし、すでにいろんなエフェクトが実装されている swf でインターフェイスを提供することができます *1 。最近の Flash 界隈は全然追っていないので、ひょっとしたらすでに知れ渡っている方法かもしれませんが、少なくともこれを実装した当時 (2005 年) はまだ誰もやってなかったと思います。


以下、通信方法のちょっとだけ具体的な説明。自分でもよく覚えてないので間違ってたらごめんなさい。ポイントは、javascript を介すことです。つまり、swf から javascript を叩き、javascript から applet を叩く感じ。

swf から javascript を叩くのは fscommand あたりでぐぐれば出てきます。javascript から swf を叩くのは、以下のようにすると swf 内の変数に代入ができるので、後は swf 側で変数の変化を観測すればいいです。

document.<swf を貼っている object 要素の id>.SetVariable('/:<ActionScript 内の変数名>', <文字列引数>);

javascript から java applet を叩くのは、以下で applet 内のメソッド呼び出しができます。メソッド呼び出しなので返値も取得できるはずです。

document.<class を貼っている applet 要素の id>.<public なメソッド名>(<引数>);

実際にはいろいろバッドノウハウがあった気がするのですが、よく覚えていません。詳しくはソースでも見てください。

*1:proce55ing だけでいいのかもしれませんが、私は使ったことないので知りません。