Rubyの全バージョンで動くQuine
このプログラムは、Ruby 0.49（1994年リリース）からRuby 3.2.1（今月リリース）まで、現在確認されているすべてのCRubyで動作するQuineです。
eval($s=("t='eval($s=('+d=34.chr;s=3
2.chr+$s*i=8;v=$VERSION||eval('begin;v=V
ERSION;rescue;v||RUBY_VERSION;end');f=('?'*8
+'A|'+'?'*20+'G?c'+'?'*15+'A@CXx@~@_`OpGxCxp@~pO
xS|O~G?c?q?xC`AP|q?x_|C_xC_xO@H@cG?G?qA|_|_`GCpOxC|H
NFccqq@`_|OF@`?q?x_@x_x_`GB`O``O~G?C@qCxCxP@D@|G~C?pO|C?
pO|C?AP|A~HNN`ccxC|Q@L@B"+"GpGpc@p?x_`GB`???_@FO|OB@
xC|P`@?c?q?HPx@~@_`G@`????@L^`?q?x?xq@|_|O~GC`
xA~@_@GBD').unpack('c*');w=4+v.length*u=
15;r=10.chr;j=0;while-24+w*u>i=1+i
;x=i%w;x>0||t=t+d+'+'+r+d;k=
i/w%12>2&&x%u>3&&x%u+i
/w*11-34+('-._'.
index(c=v[
x/u,1]
)||c.hex +3)*99|
|0; k=f [k/6 ][k%
6]; t=t +s[
k*j =k+ j,1
]end;pr int (t+
d+' ).s pli
t.j oin [0,
609 ])# Y.E. '+r)
").split .join)#
プログラミング言語Ruby 30周年記念イベントでLT発表したものです。コードはGitHubに置きました。
動作方法
全バージョンで実行するには、rubylang/all-rubyというdocker imageを使ってください。
$ wget https://raw.githubusercontent.com/mame/all-ruby-quine/main/all-ruby-quine.rb $ docker run --rm -ti -v `pwd`:/src rubylang/all-ruby
./bin/ruby-0.49 /src/all-ruby-quine.rb とすると、ruby 0.49で実行できます。
# ./bin/ruby-0.49 /src/all-ruby-quine.rb
eval($s=("t='eval($s=('+d=34.chr;s=32.chr+$s*i=8;v=$VERSION||eval"+
"('begin;v=VERSION;rescue;v||RUBY_VERSION;end');f=('?'*8+'A|'+'?'"+
"*20+'G?c'+'?'*15+'A@CXx@~@_`OpGxCxp@~pOxS|O~G?c?q?xC`AP|q?x_|C_x"+
"C_xO@H @cG?G?qA|_|_`GCpOxC|HNFcc qq@`_|O F@`?q"+
"?x_@ x_x _`GB`O``O~G?C@qCxCxP@D @|G~C? pO| C?pO"+
"|C?A P|A~H NN`ccxC|Q@L@BGpGpc@p? x _`GB`? ??_@F O|OB"+
"@xC| P`@?c ?q?HPx@~@_`G@`????@L ^` ?q?x?x q@|_ |O~G"+
"C`xA ~@_@G BD').unpack('c*');w =4+ v.lengt h*u="+
"15;r =10.c hr;j=0;while-24+w*u >i= 1+i;x=i%w;x>0| |t=t"+
"+d+' +'+r+ d;k=i/w%12>2&&x%u>3 &&x%u+i/w*11 -34+"+
"('-. _'. index(c= v[x/u,1])||c.h ex+3)* 99|| 0;k="+
"f[k/6] [k%6];t=t+ s[k*j=k+j,1]en d;print (t+d+"+
"').split.join[0,609])#Y.E.'+r)t='eval($s=('+d=34.chr;s=32.chr+$s"+
"*i=8;v=$VERSION||eval('begin;v=VERSION;rescue;v||RUBY_VERSION;en"+
"d');f=('?'*8+'A|'+'?'*20+'G?c'+'?'*15+'A").split.join[0,609])#Y.E.
同様に、./bin/ruby-3.2.1 /src/all-ruby-quine.rb とすればruby 3.2.1で実行できます。
# ./bin/ruby-3.2.1 /src/all-ruby-quine.rb
eval($s=("t='eval($s=('+d=34.chr;s=32.chr+$s*i=8;v=$VERSION||eval('begin;v=VERSI"+
"ON;rescue;v||RUBY_VERSION;end');f=('?'*8+'A|'+'?'*20+'G?c'+'?'*15+'A@CXx@~@_`Op"+
"GxCxp@~pOxS|O~G?c?q?xC`AP|q?x_|C_xC_xO@H@cG?G?qA|_|_`GCpOxC|HNFccqq@`_|OF@`?q?x"+
"_@x_x _`GB`O``O~G?C@qCxCxP@D @|G~C?pO|C?pO|C?AP|A~HN N`ccxC|Q"+
"@L@B GpGp c@p?x_`GB`???_@FO|OB @xC|P `@?c?q?HPx@~@_`G@`??? ?@L^`?q?"+
"x?xq@|_|O~GC `xA~@_@GBD').unpack('c*');w =4+v.length*u=15;r=1 0 .chr;j=0"+
";while-24+w *u>i=1+i;x=i%w;x>0||t=t+d+'+ '+r+d;k=i/w%12>2&&x%u>3 &&x%u+i/"+
"w*11-3 4+('-._'.index(c=v[x/u,1])| |c.hex+3)*99||0;k=f[k/6] [k%6];t="+
"t+s[k*j=k+j ,1]end;print(t+d+').spli t.join[0,609])#Y.E.'+r)t=' eval($s="+
"('+d=34.chr; s=32.chr+$s*i=8;v=$VE RSION||eval('begin;v=VERSION ;rescue;"+
"v||R UBY_ VERSION;e nd');f=( '?'*8+'A|'+'?'* 20+'G?c'+'?' *15+'A@C"+
"Xx@~@ _`OpGxCxp@ ~pOxS|O~ G?c?q?xC `AP|q?x_| C_xC_"+
"xO@H@cG?G?qA|_|_`GCpOxC|HNFccqq@`_|OF@`?q?x_@x_x_`GB`O``O~G?C@qCxCxP@D@|G~C?pO|"+
"C?pO|C?AP|A~HNN`ccxC|Q@L@BGpGpc@p?x_`GB`???_@FO|OB@xC|P`@?c?q?HPx@~@_`G@`????@L"+
"^`?q?x?xq@|_|O~GC`xA~@_@GBD').unpack('c*');w=4+v.length").split.join[0,609])#Y.E.
./bin/ruby-3.2.0 /src/all-ruby-quine.rb | ./bin/ruby-0.49 で、ruby 3.2.0の出力をruby 0.49で動かせます。逆も可。
全バージョンで動かしたかったら ./all-ruby all-ruby-quine.rb としてください。
Rubyの全バージョンで動くプログラムの作り方
たぶん誰の役にも立ちませんが、このQuineを書くのに得られた知見をまとめておきます。
ブロックは使用不可
ruby 0.49のブロックは、do ary.each using x ... end という記法だったようです。現代で見る ary.each {|x| ... } や ary.each do |x| ... end のようなブロックはありません。旧式の文法は現代のRubyではsyntax errorになるので、全バージョンで動かすにはブロックは使えません。while文などでがんばりましょう。
x += 1は使用不可
ruby 0.49には x += 1 や x ||= 1 のような構文がありません。x = x + 1 などと書き下します。
三項演算子は使用不可
ruby 0.49には cond ? a : b がまだありません。if文はありますが、ちょっと長いので cond && a || b などとするとおしゃれで しょう。
大きい文字列リテラルは使用不可
ruby 0.49で大きめ（700バイトくらい）の文字列リテラルを作るとSEGVするようでした。文字列の連結を使って回避します。ちなみに文字列の連結で動くということは、全バージョンでGCがそこそこ安定して動いているってことなので、結構すごいことです。
%-記法のリテラルや式展開は使用不可
この手のQuineで非常に便利な %(...) という文字列リテラルは、ruby 0.49では未実装です。String#splitやArray#joinがあるので、コードのアスキーアート化は eval(s="...メインのコード...".split.join) とすれば可能です。
あと、"#{expr}"もないので注意。がんばって文字列連結しましょう。
evalの中でメソッド定義は使用不可
ruby 1.3.1-990324 では eval("def foo; end") などとすると nested method definition という例外になります。おそらくバグなんですが、いずれにせよ全バージョンで動かすためには使えません。
evalの中でコメントは使用不可
ruby 1.1d0 で eval("1#") などとするとSEGVします。間違いなくバグですが、コメントを使うのは避けましょう。
evalでローカル変数を参照するのは不可
再現条件がやや微妙なのですが、ruby 0.51など初期バージョンでは次のコードでSEGVします。
s = "hello"; eval("print(t = s)")
evalで外のローカル変数を読み出すところにバグがあるようでした。グローバル変数を使うと安定して動きました。
$s = "hello"; eval("print(t = $s)")
str[idx]に注意
Ruby 1.8まで、str[idx]はidx番目のバイトを整数で返していましたが、1.9からは1文字の文字列に変わっています。なのでstr[idx] は使わないのが無難です。どうしても使いたかったら、たとえば次のように書けば良いでしょう。
ch="ABC"[1]; "@"[0] == 64 && ch=[ch].pack("C*")
これで全バージョンで ch == "B" になります。ポイントは、"@"[0] が整数かどうかを見て分岐するところです（?@ == 64 でもよい）。型がなくてよかったですね。
利用可能な組み込みメソッドに注意
当然ですが、昔のRubyは今ほど組み込みメソッドが充実していないので、何が利用可能かを慎重に試す必要があります。とはいえ、ruby 0.49の時点で意外と多いです。現代の組み込みメソッドの半分以上はすでにあるんじゃないかな。
どんなメソッドがあるかは、ruby 0.49に同梱されているspecというファイルが便利です。かつて「Rubyにはドキュメントがない」と言われていたのはなんだったのか。
Rubyのバージョン番号を出力するプログラム
all-ruby-quineの肝はインタプリタのバージョン番号を取得するところなのですが、これが結構 hacky でした。その部分だけ取り出した次のコードが、各Rubyバージョンでどのように解釈されるか説明しておきます。
print($VERSION||eval('begin;v=VERSION;rescue;v||RUBY_VERSION;end'))
このコードが各バージョンでどのように解釈されるかを説明しておきます。
0.49 .. 0.65
これらのバージョンでは $VERSION が定義されています。よって、$VERSION || ... の後半は評価されず、そのまま $VERSION が返ります。後半でeval を使っているのは、これらのバージョンでは begin; ...; end の構文がまだ存在せず、そのまま書いたら syntax error になるからです。
0.69 .. 0.76
ここが一番おもしろいです。これらのバージョンでは $VERSION が定義されておらず、定数のVERSIONが定義されています。後述する1.9.0からはRUBY_VERSIONにリネームされるのですが、RUBY_VERSIONを参照すると例外になってしまうので、少し工夫が必要です。次のようにしました。
begin v = VERSION rescue v || RUBY_VERSION end
rescue のインデントがおかしいのは意図的です。というのも、これらのバージョンでは例外捕捉キーワードは resque であり、rescue はただのメソッド呼び出しと解釈されます。「なら undefined method エラーになるのでは？」と思うかもしれませんが、幸いなことにこれらのバージョンでは「未定義メソッド呼び出しは黙って nil を返す」というパワーのある仕様です。よって、変数 v に VERSION の中身が代入されたあと、v || RUBY_VERSION の後半は評価がショートカットされるので、無事 VERSION が返されます。
0.95 .. 1.8.7-p374
これらのバージョンでは VERSION が定義されています。0.95で resque が rescue に変わったので、素直に v = VERSION だけ評価されて値を返します。
1.9.0 ..
VERSION 定数が削除されたので、v = VERSION は NameError を投げます。しかし rescue によって補足されるので、RUBY_VERSION が評価されて値を返します。
感想
なにより驚いたのは、ruby 0.49の時点でかなりRubyになっていることです。現代のRubyの機能の半分以上はすでにありそう。
そして、そこからほとんど変わってないのもすごい。このQuine程度に非自明なプログラムが書けるくらいに、本質的な非互換がない。やりはじめたときは、ここまでできるとは思ってませんでした。
「Rubyは未完成だったので開発協力者がたくさん現れて、それがOSSとしての成功につながった」のようにmatzが語っているのはわりと有名ですが、そうはいっても「最初の時点でかなり完成していること、そしてそこからブレないこと」も成功するOSSの秘訣なのではないかという気がします。
それから、初期も含めて各リリースの品質が非常に高い。バグ回避のテクニックをたくさん書いたので言ってることと違うと思うかもしれませんが、言語処理系って多くの人が実戦で使ってはじめてまともになるものなんですよね。信じられない人はquine-relayを作ってみるといいです。世のマイナー言語処理系たちがいかにふつうのコードでもすぐSEGVするとか、致命的に機能が足りないとか、そもそも起動もしないとかがわかります。それを考えると、ユーザがほとんどいなかった初期でもRubyの各リリースの品質がここまで高いのは驚異的です。
ということで、matzはすごい！ということを体感できる遊びでした。だれかPythonとか他の言語でもやるといいと思います。
蛇足
ruby 0.49以前のコードが発掘されませんように。
Go言語の不満
ちょっとバイナリ配布したいツール↓があったので、Go言語と戯れました。
ほぼはじめてGoを使ったので、にわかほど語りたがる法則に従って、Go言語の感想を書きます。
新しい言語にふれたときは、できることには気づきにくく、できないことに気づきやすいので、不満が多めです。主な比較対象はRuby、C言語、JS/TS、Rustあたりです。
よかったところ
- ひとことで言えば「便利になったC言語」という感じでした。結構低レベルなAPIも揃っていてよかった（デーモン化が素直にできなかったこと以外）。
- Rustと比べたらストレスフリーです。思った通りに書くだけでとりあえず動いてくれる。すばらしい。
- 見た目はあきらかに長くてダサいですが、こだわりを捨てて割り切って書けると言えなくもない。
- 配布しやすいシングルバイナリが作れるのはやはりよい。今回Goを選んだ理由がこれ。
細かいカプセル化がむずかしい
カプセル化の単位がパッケージしかないのがとにかくつらいです。ローカル変数以外の変数や構造体のフィールドが、パッケージ内のどこからも参照できてしまう。
今回はじめて自覚したのですが、ぼくは数十行単位の細かい抽象化を積み上げてプログラムを書くようです。たとえばRubyだと、インスタンス変数は基本的にclass～endの中でしかアクセスできません。これにより、単一ファイル内でも細かくカプセル化ができます。
同じことをGoでやるには、パッケージ（つまりディレクトリ）を分けないといけないので、数十行のファイルが一つだけあるディレクトリを大量に作るハメになりそうです。そんなの明らかにやりたくないし、Go的に推奨されてもなさそうです。
別案として、すべてのstructをinterfaceにキャストして扱う手も教わりましたが、それは明らかに面倒くさすぎる（わがまま）。
慣れの問題もあると思いますが、同一パッケージ内でもファイル単位などで手軽にカプセル化したい。この点はextern宣言やヘッダファイルを#includeするC言語のほうがマシとすら思った。
goroutineむずかしい
むずかしくないですか？ wsl2-ssh-agentでは、複数のsshクライアントからのリクエストを受けて、それらをシーケンシャルに処理するサーバを書く必要があったのですが、設計に数時間以上かかりました。
とりあえず動かすだけなら10分くらいでできたんですが、雑に立ち上げたgoroutineをすべてきちんと終了させるのがめちゃくちゃしんどい。雑にチャンネルをクローズすると、それに書き込むgoroutineがpanicする可能性が（稀なレースコンディションとして）見つかったりするので、終了させるべき順序がめちゃくちゃ繊細です。今もバグが取り切れた自信はないです。
Goではcontextが便利という噂を聞いてましたが、IO待ちがcontextを受け取ってくれないので、肝心なところで使えない印象でした。
この問題は他言語なら楽というわけでもないですが、今回の問題に限って言えば、シングルスレッドでselect(2)みたいなAPIのほうが楽そうだったなあと思いました。Goを捨ててC言語で書き直すか迷ったくらい。「goroutineをすべてきちんと終了させる」なんて考えないほうがいいんですかね。
その他雑な感想
- そうは言ってもやっぱ記述が冗長すぎる。
if err != nil {}つらい。サンプルコードの読解すらつらい。 - めっちゃ書かされるわりには型が弱いので、なんとなく割に合ってない気分。nil unsafeとかは別にいいんだけど、組み込みでoptional intくらい欲しい。
- めっちゃ書かされるわりにはエラーの扱いが微妙？ エラーのとき、どこで何が起きたか把握するのに手間がかかると思うことが多かった。スタックトレースで見たい。
- テストむずかしい。
os.Exit(0)を呼ぶ関数はほぼテスト不能とか *1 。動的言語のテスタビリティの高さをあらためて感じた。
*1:os.Exit を変数経由で呼ぶようにしておいてテスト時に差し替えるみたいなテクニックもあるようですが、コードにとって完全に無意味な複雑性をテストのためだけに入れるのはちょっとなー。
6x6リバーシの神
絶対に勝てない6x6リバーシを作りました。あなたは黒番、AIが白番です。
絶対に勝てない6x6リバーシを作りました！ ぜひ挑戦してみてくださいhttps://t.co/Ul5n3q9jMp
— Yusuke Endoh (@mametter) December 30, 2021
これは何？
6x6の盤面のリバーシは後手必勝 *1 であることが知られています。 このAIは白番（後手）で完璧にプレイします。つまり黒番のあなたは絶対に勝てません。無力感を楽しんでください。
技術的な話
このAIはWebAssemblyになっているので、全部あなたのブラウザの上で動いてます。真のサーバーレスです。
AIのソースコードはRustで書きました。わりと堅実なゲーム木探索になってます。UIは普通にTypeScriptとthree.jsで実装しました。
作った順に説明します。
盤面の表現
なにはともあれ、盤面を表すデータ構造を作りました（src/bitboard.rs）。
ファイル名の通り、ビットボードです。
Rustのu64（64ビット整数）を2つ使って1つの盤面を表現します（1つが黒石の位置、もう1つが白石の位置）。
着手可能数のカウントなどすべて、ビット演算を駆使してやります。 石をひっくり返す処理は探索性能に直結するのでがんばってます。 36マスすべてに特化したコードをマクロで生成してます（src/bitboard/flip.rs）。 ただし、最終的にWASMにするので、アセンブリを書くようなことはしてません。
ちなみにビットボードを選んだ理由は、そうしないとRustの所有権や借用がすごく面倒くさそうだったからです。
ビットボードならu64が2つだけなので、雑にCopyトレイトを実装しても大丈夫。
終盤のアルゴリズム
最初に書いた探索アルゴリズムは、単純なネガマックス法です。 これはゲーム終盤（空きマスが11個以下）の探索に使っています。
終盤の探索は、凝ったアルゴリズムより、定数オーダの最適化がよく効くところです。 たとえば、空きマスを探すために全マスをチェックすると遅いです（終盤の場合、多くのマスはすでに石があるので無駄）。 そこで、終盤の探索に入る前にすべての空きマスの位置を列挙して連結リストでつなぎ、再帰のたびにこのリストをなめるようにしています。
残念ながら、Rustはリスト構造の扱いが極めて不得意な言語です *2 。
Rustでリストを作るには（型チェックを通すために）リファレンスカウントのセルを使うのが定番のようですが、今回はパフォーマンスが重要なのでunsafeを使いました。
こういうときはunsafeで良いという知見をもらっていたので。
Programming Rust 以下の記述が良かった。「コンテナはunsafe無しに効率的には書けないのでunsafeで良い」 まめさんの以下の記述への回答になっている。 https://t.co/r5iunzkpWH pic.twitter.com/e2bk3R5IFE
— Yu SUGAWARA (@gusmachine) May 10, 2017
中盤のアルゴリズム
次に、単純なネガマックス法で深く読むことはできないので、空きマスが12個以上あるときのためのもう少し賢いアルゴリズムを実装しました。 置換表付きMTD(f)＋評価関数によるムーブオーダリングという、とても昔ながらの方法です（src/search/midgame.rs）。
評価関数は、手動で作った特徴量（いわゆるedge2xのパターンと、着手可能数）を入力とし、勝ちそうか負けそうかを予測します。 これの学習のために、中盤の盤面を数十万ほどランダム生成し、それぞれに対して終盤探索のアルゴリズムを使って実際の勝敗を判定しました。 そして実際の勝敗を教師データとして焼きなまし法と最急降下法を適当に使って重みを決めました（src/learn.rs）。 学習した重みは浮動小数点数が3000個ちょっとなので、Rustの配列としてコードに直接埋め込んであります（data/weight.rs）。
あと、ビットボードのedge2xパターンから高速に係数を算出するために、完全ハッシュを用意しました。
補足 このヒューリスティックな評価関数はあくまでムーブオーダリング（良さそうな手から先に調べることで枝刈りを増やすテクニック）のために使っているだけです。メインの探索では、空きマスが11個のところまで読んだら終盤探索アルゴリズム自体を評価関数として使います。なので、全体としては近似解法ではなく完全探索になります。
序盤のアルゴリズム
6x6のリバーシは1993年に後手必勝であることが示されたそうです。 当時のワークステーションで数週間くらいかけて探索したらしいですが、そんな計算も現代では一瞬……かと思ったのですが、ここまでで作ったアルゴリズムで初期盤面からの探索をすると、1分強かかりました。ディープラーニングで評価関数作ってムーブオーダリングするともっと速くなるのかなあ？
これでリアルタイムに探索するのは厳しいので、序盤の16手をあらかじめ計算してしまうことにしました。 黒が任意の手を選ぶのに対し、白の手は1つだけ覚えればいいので、深さ8のツリーを作ります。 白は最善手（最も大きい石差で勝つ手）のうち、黒の着手可能数が小さくなる枝を選ぶようにすることで、なるべく覚える数を減らしました。 結果的に、およそ10万盤面程度を覚えることになりました。
ツリー部分は簡潔データ構造を使ったLOUDSという表現でエンコードし、およそ700キロバイトとなっています *3 。
そんなに大きくないので、include_bytes!マクロでバイナリデータを直接実行ファイルに埋め込みました。
これでAIは完成です。
ブラウザで動かす
ここまでは、Linuxでのネイティブ実行ファイルとして作ってました。 今回は探索をブラウザで動かす目標だったので、wasm-bindgenでブラウザ向けのAPIを用意し（src/api.rs）、wasm-packでWebAssembly（以下wasm）にしました。 emscriptenに比べるとびっくりするほど簡単にwasmができたのでびっくりしました。
ただ、動かして見るとpanicで落ちました。
「やっぱりwasm生成は完成度そんなに高くないのかなー」などと他人のせいにしつつ、何が起きているか調べてみると、usizeでオーバーフローが発生してました。
試してたネイティブビルドは64ビットなのでオーバーフローしないのですが、wasmは32ビットなのでオーバーフローが起きる。
要するに完全に自分のせいでした。完成度高いなあ。
直したら無事にwasmがWeb workerから動きました。 なお、panicは調べ始めてから数十分で直せたのに対し、wasm+Web workerのwebpackの設定に数時間ほど消費しました。webpack許せない。
UI部分
ここまでRustで開発してきたので、UIもyewで！ などと考えなくもなかったのですが、この時点でRustへのヘイトが溜まりすぎていたのでTypeScriptで書きました。 いやー、ちょっとmapしたいだけなのにiterだのcollectだの書かないといけないとか、雑なコード書くとunwrapだらけになるし……。
閑話休題。
かっこいいUIを作りたくなったので、three.jsを使うことにしました。 最初はReactで実装しようとしましたが、three.jsが状態のかたまりで相性最悪だった *4 ので、素で書きました。
雑感
完全解析されているゲームは、どうやっても勝てないところを実際に体験したいですよね。 6x6リバーシのパーフェクトプレイの棋譜は発見者のJoel Feinsteinが書いたニュースレターを始めいろいろなところで見かけますが、インタラクティブにできるものは見つからなかったので作りました。
あと、wasmで遊んでみたかったのも動機です。 6x6リバーシは全盤面をデータベースにするのは明らかに無理なので、ブラウザで現実的に動かせる速度とバイナリサイズを実現するにはwasmがよいかなと。 はやくWebアプリのフロントエンドが全部wasmで動く世界になるといいなあ。
まとめ
6x6のリバーシはやっぱり勝てませんでした。
アニメ「Sonny Boy」の『難解』プログラムの解説
『Sonny Boy』というアニメが放送されています。学校が異次元に漂流してしまい、超能力に目覚めた生徒たちがサバイバルしながら、さまざまな奇妙な現象の裏にあるルールを解き明かし、元の世界に変える方法を探す、というストーリーです。ルールが分かったあとで何度も見直したくなります。
さて今回、『Sonny Boy』に、プログラムを寄稿しました。プログラムでおもしろいCGを作ったとかではなく、プログラムの実行の様子そのものが『Sonny Boy』の5話の中で放送されました。
こういうプログラムです。
このプログラムがどういうものだったかを解説します。
どんなプログラム？
実行すると、「難解」という文字がほどけてなくなるアニメーションをします。
起動したらまず、プログラム自身が画面に表示されます。 しばらくしたら「難解」が左から右へほどけていきます。 その後上からヒモが降ってきて、"Solved" という単語になったあと、再度ほどけて終了。 実行時間5秒程度のちょっとしたデモアプリです。
手元で試してみたい人は、Rubyをインストールした上で、nankai.rbを保存しruby nankai.rbと起動します。
端末のサイズを 180 x 40 以上に広げて実行してください。
なお、プログラムはGitHubに置いてあります。
制作の背景
拙作のASCII Fluid（下記動画）が、Sonny Boyの監督の夏目真悟さんの目に止まったのがきっかけです。
「解ける（ほどける、とける）」というテーマで、数秒程度の難解なプログラムを自由に作ってほしい、と声をかけていただいたので、そのまま『難解』をほどくプログラムにしました。 作中に出てくる、『解く』という能力を示すデモになってます。 アニメで使ってもらうということで、わりと動きにこだわって作ってみたつもりです。
ちょっとだけ技術解説
アニメーションはハードコードしているのではなく、実際に「難解」の文字を分解することで表現しています。 「難解」を17領域くらいに分割し、それぞれの中でスパニングツリーを構成します。 その端っこを引っ張るような感じでアニメーションします。なので正確には一本のヒモではなく、何本かのヒモが絡まったような形になってます。
プログラム自身を表示するのは単にソースコードをファイル読み込みするのではなく、クワインという方法で実現しています。 端末でのアニメーションはエスケープシーケンスを使ってやってます。 エスケープシーケンスは無害化して出力されているので、エスケープシーケンスを含むコードを含めて再実行できるようになっています。
$ ruby nankai.rb > nankai.output $ ruby nankai.output
Rubyというプログラミング言語はとても実用的な言語ですが、こんな変わった使い方もできて、とても良い言語です。もしこういうプログラムに興味があったら、こんな感じのプログラムばっかり集めた本を書いているのでぜひ見てみてください（宣伝）。
まとめ
ということで、「難解」という文字が自発的に解けていくというプログラムでした。アニメ見てた方に「おっ」と思っていただけていたら嬉しいです。見てなかった方は、いろいろ配信があるので、5話だけと言わず、ぜひ1話から追っかけてください。
...
以下は、読まなくていいです。
おまけ
ここからはギークなプログラマ向けの、ちょっとしたおまけです。
このプログラムは「ほどいても」動作するようになってます。 どういうことかというと、左半分の「難」だけを切り出しても実行できるプログラムになっています。
q=%q!s =q[/#{ N=?\n}( #{Z=?\~
s}*)/, 1];E=3 3.chr; $><<t=~
(N*12+s+"q=%q#{E+q+E};eval# {Z*8}n= '#{n}'~
"+N*13+?#).gsub(/^.*/){(Z*( 35-s.si ze)+$&)
|c|d=d *90+(c -2)%91};d};b=116;c=0;i=D
`?oT`r #?jn%: _(7AF5]7lZ}|N,),slN15Ap8<
]];g=[];F=->x,m{g<<[t[x ],b>0?[0]*c+[x]*b+m:[0]*(c
map{|i|i+=x;s<=i&&i<s+n -170&&(i-s )%W<n%W
<<x;v <1&&v=D ["axC4?ap'5.bbU lui?h|b
".split(??)[(x%W+x/W)%8]];(d+=1;v/=2)while+v%2>0;z=
x+=d%8>3?z:-z;v/=2)whil e-x%W>1&&0<x&&x<8208;F[y,
8-'#'L> *B(B[(*-$XG|"E"H=$H:)$'$
,n=a;v=B.pop-34;v%3<2?( z=n%W; S[s+y=(
;y)]):(b+=200/r+=2;M[D[ "=,)_q >Z"]>>r
170]*19;b=0;T=(c+(0..8) .map{Z*51+(0..67).map{i/
%w{puts (["Usage:",:ruby,$0,100]
/q/)?$q[/^#{z}+/]+z+z+"R=ev al#{z*18}$q=#{z*35}%q{#$
1]:[]};n+z+?=+z+(m>1?f[2]:[ m])*(z +?x+z))
,n=0,m;6.ti mes{|i |c+=10;
[i]*684];b=52;t= T;M[6,(x-i%2)%W+4788]};s=
{|i|o=[Z* 170]*48*N; g.map{|c,m|x=m[i]||0;x>0&
ub(N,"\e[E ");slee p(0.01)};puts(s)#Unravel#
"q!;p 0/ 0.0;#";
これ実行すると、"NaN"が出力されます。ナンだけに。
$ ruby nan.rb NaN
もちろん、右半分の「解」も実行可能です。
p="><"
puts""+ p||$><<"____\n\s/\s/\n";(
"\u89D2";;x=(%~ );%#?_Y}_U1jojD(i0(DVA1aq
.ljust(170)};D=-> e{d=0;e. bytes{
["cGIY& ?dUptZ yGj5?= 1+wD5G
XzIUF<+ <L-MlD )"+t[2 513,21
-m.size)+m.reverse];t[x]= Z;[1,-1 ,-W,W].
&&t[i]>Z&&F[i,[i]+m]}};M=- >d,x{y=x; m=[];v=0;(m
*?_jJc? _v_&z 'NcJ{(Hn{?_O6m ?}3k7>?Q,
-(d%4) %172+ 1;~+%~ ##Y. #E2021
m]};W=171;B=%{36<-~;%w~ ;puts :Moo;'
OAs"3$*2$-2"*5s}.bytes; r=8;S= ->*a{s
v%3*17 0+1)* w=v/3, n-(S[s,v%3<1?n+w-z:w*W+z]
&6,s+B .pop- 34+v/3 *W])};S[2082,m=8378];c=[Z*
=2;i%2>0?%q@_R=eval$q=%q{z=?\ s;eval
*z)if[]==$*.map{|n|puts (n. match(
q}":(m=n.to_i;f=->x{m>1 ?m%x<1?(m/=x;[x]+f[x]):f[x+
)}}*"" }@[b+= 1]:Z}*""+Z*51}+c)*N;c=340;s
t=T+"" ;b=0;M [2,x=D["^lv(2A"[i]]+3302+26
"\e[F"* 47;504 .times
&o[x]=c };$><< s+o.gs
#!;eval n='eval q. gsub((
/[\s ]|~.*$/) ,"")#'
実行すると"><"が出力されます。ギリシャ文字のカイのイメージ。
$ ruby kai.rb ><
プログラムを横に分解してそれぞれ違う動きをさせるのはわりと難解だと思うので、腕に覚えのあるプログラマは解読してみてください。
ヒント：Rubyの「%記法」をうまく使って実現してます。 最初の2行と終わりの2行あたりに注目すると良いです。
おまけのおまけ
これで終わり？ まだ分解できますよね。そう、「角」と「刀」と「牛」。
p="><"
puts""+
"\u89D2";;x=(%~
.ljust(170)};D=->
["cGIY& ?dUptZ
XzIUF<+ <L-MlD
-m.size)+m.reverse];t[x]=
&&t[i]>Z&&F[i,[i]+m]}};M=-
*?_jJc? _v_&z 'NcJ{(
-(d%4) %172+ 1;~+%~
m]};W=171;B=%{36<-~;%w~
OAs"3$*2$-2"*5s}.bytes;
v%3*17 0+1)* w=v/3,
&6,s+B .pop- 34+v/3
=2;i%2>0?%q@_R=eval$q=%
*z)if[]==$*.map{|n|puts
q}":(m=n.to_i;f=->x{m>1
)}}*"" }@[b+=
t=T+"" ;b=0;M
"\e[F"* 47;504
&o[x]=c };$><<
#!;eval n='eval q.
/[\s ]|~.*$/)
「角」を実行すると角が出ます。
$ ruby tsuno.rb 角
次は「刀」。
p||$><<"____\n\s/\s/\n";(
);%#?_Y}_U1jojD(i0(DVA1aq
e{d=0;e. bytes{
yGj5?= 1+wD5G
)"+t[2 513,21
Z;[1,-1 ,-W,W].
>d,x{y=x; m=[];v=0;(m
Hn{?_O6m ?}3k7>?Q,
##Y.
「刀」を実行すると「刀」のアスキーアートっぽいものが出ます。
$ ruby katana.rb ____ / /
最後は「牛」。
#E2021
;puts :Moo;'
r=8;S= ->*a{s
n-(S[s,v%3<1?n+w-z:w*W+z]
*W])};S[2082,m=8378];c=[Z*
q{z=?\ s;eval
(n. match(
?m%x<1?(m/=x;[x]+f[x]):f[x+
1]:Z}*""+Z*51}+c)*N;c=340;s
[2,x=D["^lv(2A"[i]]+3302+26
.times
s+o.gs
gsub((
,"")#'
「牛」を実行すると鳴きます。
$ ruby ushi.rb Moo
それぞれのプログラムは単純なので、Rubyがわかれば普通に読めると思います。 実行に関係ない文字列がいかにSyntax Errorにならないようにするかがポイントです。
しかし、「解」や「難解」に合体させても動くようにするのは、かなり苦労しました。 その甲斐あって、なかなか香ばしいコードに仕上がったと思うので、ぜひ解読して欲しいです。
ヒント：pや~.*$/が分解次第で構文の解釈が変わります。ダブルミーニングなコード。
さらなるおまけ
最後に一瞬表示される "Solved" も実行可能になってます。
R=eval $q= %q{
z=?\s;eval %w{ put
s([" Usa ge: ",:
ruby ,$0 ,10
0]*z)if []==$*. map {|n |pu ts(n.ma tch(/q/)
?$q[ /^# {z} +/] +z+ z+" R=e val #{z *18
}$q =#{z *35} %q{# $q} ":( m=n .to_i;f=->x {m>1 ?m%
x<1?(m/=x; [x] +f[ x]) :f[ x+1 ]:[ ]}; n+z
+?=+z+ (m>1?f[ 2]: [m])* (z+?x+z) ))}}*""}
実行すると使い方が表示されます。
$ ruby solved.rb Usage: ruby solved.rb 100
この通りに実行してみます。
$ ruby solved.rb 100 100 = 2 x 2 x 5 x 5
100が素因数「分解」されました。コマンドライン引数の数字を次々に素因数分解していくプログラムになってます。
$ ruby solved.rb 1 2 3 4 5 6 7 8 9 10 1 = 1 2 = 2 3 = 3 4 = 2 x 2 5 = 5 6 = 2 x 3 7 = 7 8 = 2 x 2 x 2 9 = 3 x 3 10 = 2 x 5
最後のおまけ
もはや全然関係ないおまけですが、solved.rb は引数に "quine" を渡すと、自分自身を表示します。ここにもクワイン。
$ ruby solved.rb quine
R=eval $q= %q{
eval(%w{z= ?\s ;pu
ts([ "Us age :",
:rub y,$ 0,6
]*z)if[ ]==$*.m ap{ |n| put s(n.mat ch(/q/)?
$q[/ ^#{ z}+ /]+ z+z +"R =ev al# {z* 18}
$q= #{z* 35}% q{#$ q}" :(m =n. to_i;f=->x{ m>1? m%x
<1?(m/=x;[ x]+ f[x ]): f[x +1] :[] };n +z+
?=+z+( m>1?f[2 ]:[ m])*( z+?x+z)) )}}*"")}
ささやかなこだわりですが、左側に空白をいれたら出力も同じようにずれるようになってます。 アニメ中のように、画面真ん中あたりに表示されたのをコピペしてもちゃんとクワインになります。
$ cat solved2.rb
R=eval $q= %q{
eval(%w{z= ?\s ;pu
ts([ "Us age :",
:rub y,$ 0,6
]*z)if[ ]==$*.m ap{ |n| put s(n.mat ch(/q/)?
$q[/ ^#{ z}+ /]+ z+z +"R =ev al# {z* 18}
$q= #{z* 35}% q{#$ q}" :(m =n. to_i;f=->x{ m>1? m%x
<1?(m/=x;[ x]+ f[x ]): f[x +1] :[] };n +z+
?=+z+( m>1?f[2 ]:[ m])*( z+?x+z)) )}}*"")}
$ ruby solved2.rb quine
R=eval $q= %q{
eval(%w{z= ?\s ;pu
ts([ "Us age :",
:rub y,$ 0,6
]*z)if[ ]==$*.m ap{ |n| put s(n.mat ch(/q/)?
$q[/ ^#{ z}+ /]+ z+z +"R =ev al# {z* 18}
$q= #{z* 35}% q{#$ q}" :(m =n. to_i;f=->x{ m>1? m%x
<1?(m/=x;[ x]+ f[x ]): f[x +1] :[] };n +z+
?=+z+( m>1?f[2 ]:[ m])*( z+?x+z)) )}}*"")}
IOCCC日本語ネタバレ解説 中間報告
変態C言語プログラムコンテストであるIOCCCの全作品を日本語でネタバレ解説するサイトを書いてます。
年初にIOCCC 1984の解説から書き始めて、先程IOCCC 2000の解説を公開したところです。
数えてみると、ここまで165作品を解説したようです。どれも面白いものばかりですが、その中でも特におすすめの作品を個人的な好みでピックアップ紹介してみました。
Brian Westleyの作品
初期のIOCCCを支えたwestleyの作品群。多彩で超絶技巧で、とにかくすごいです。絶対に見てほしい！ので、まずは彼の作品だけまとめます。 ネタバレ解説を書き始めたのは、すごさのわりにあまり注目されていない彼の作品を紹介したかったのが動機のひとつです。
- IOCCC 1987 Best Layout 線対称なプログラム。実行すると回文が出る。
- IOCCC 1988 Best Layout 円の形のプログラムで、円周率を計算する。ちゃんと円の形に意味があるのがよい。
- IOCCC 1989 Most algorithms in one program ROT13しても文字列反転しても動くプログラム。コード形状のトリックが芸術の域。
- IOCCC 1990 Best Layout 演劇の英語脚本っぽいプログラム。これでちゃんと意味のある動きをするのだから衝撃的。
- IOCCC 1991 Grand Prize ○✕ゲームを組み込んだQuine。
- IOCCC 1992 Best Small Program 小さな円（地球）の形のプログラムで、世界地図が出る。指定した緯度経度にマークを置ける機能付き。
- IOCCC 1994 Worst Abuse of the C Preprocessor Cプリプロセッサでアドベンチャーゲームを実装。
- IOCCC 1996 Best One Liner たった92文字のコードで、様々な時計を表示するワンライナー。
気楽に楽しめる作品
個人的な好みでwestleyだけ贔屓しましたが、他にも面白いのがたくさんあります。 まずは、コードの形や実行結果がひと目で面白く、気楽に楽しめるものをピックアップ。
- IOCCC 1989 Best layout π、と見せかけてe
- IOCCC 1991 Best Output ターミナルで3D迷路。
- IOCCC 1994 Best Utility ターミナルでグラフ。
- IOCCC 1994 Most Well Rounded Obfuscation psで時計。
- IOCCC 1995 Best Layout 加算器の形をした加算器。
- IOCCC 1998 Best Object Orientation ターミナルで3Dオブジェクトのビューア。
- IOCCC 1998 Best of Show 飛行機の形をしたフライトシミュレータ。
- IOCCC 2000 Best Layout 「あく」「そく」「ざん」
- IOCCC 2000 Best Small Program 現在の月齢をわかりやすく表示する。
地味だけどよく見るとすごい作品
ちょっととっつきにくいけれど、個人的にかなり好きなもの。
- IOCCC 1988 Most useful Obfuscated C program わかりにくいC言語の型宣言を、英語で解説してくれる。
- IOCCC 1989 Best self-modifying program 自分自身を書き換えながら階乗を計算する。
- IOCCC 1990 Best of Show 微分方程式のソルバで、ソートで、フィボナッチ。
- IOCCC 1993 Best Abuse of the C Preprocessor ライフゲームのためのC言語埋め込みDSL。
- IOCCC 1994 Best Layout 入力を転置行列のように転置するプログラムで、自分自身も転置可能。
- IOCCC 1996 Best Obfuscated Character Set Utility 点字の形をした点字変換プログラム。
- IOCCC 1996 Best of Show セルフホスト可能なC言語サブセットコンパイラ。
縛りプレイな作品
C言語の機能を制約して書かれたプログラム。無意味な超絶技巧にIOCCCらしさを感じられます。
- IOCCC 1988 Best abuse of C constructs ほぼwhileとdecrementだけのプログラム。
- IOCCC 1998 Best Flow Control 条件分岐を使わずに条件分岐をするプログラム。
また、C言語ではなくCプリプロセッサで計算をするプログラムも結構あります。
ルールの悪用系の作品
「C言語プログラムとは何なのか」を考えさせられる哲学的な作品群。実にIOCCCならではです。
- IOCCC 1984 The Grand Prize
short main[]={...}; - IOCCC 1987 Best Abuse of the Rules
P; - IOCCC 1988 Best abuse of the rules
#include "/dev/tty" - IOCCC 1989 Strangest abuse of the rules
char*_="Hello, world.\n"; - IOCCC 1990 Strangest Abuse of the Rules
c - IOCCC 1993 Most Versatile Source
char*_=__FILE__; - IOCCC 1994 Worst Abuse of the Rules 世界最小Quine。
まとめ
20世紀のIOCCCから個人的なおすすめ作品ピックアップでした。 紹介しなかったやつもだいたい面白いので、ぜひ暇な土日などにでも眺めてみてほしいです。
20世紀のIOCCCは、古いC言語なので、動作確認やパッチ作成がやたら大変でした。 来週からは21世紀のIOCCCのネタバレを書いていきます。 動作確認は楽になりそうですが、そのかわり作品の数や難解さが増えるので、やっぱり大変そう。
WSL2 + subsystemctlの設定メモ
WSL2 + subsystemctlの設定メモ
WSL2のおかげでLinuxからWindowsに移住できました。WSL2はデフォルトでsystemdが動いていないので、genieを使うのが定番ですが、自分はsubsystemctlを使っています。subsystemctlの設定方法はあまり見かけないので、メモを残しておきます。
インストール
コンパイルからインストールまでのコマンドを一気に書きます。
sudo apt-get install cargo systemd-container binfmt-support git clone https://github.com/sorah/subsystemctl.git cd subsystemctl cargo build --release sudo install -m6755 -oroot -groot ./target/release/subsystemctl /usr/local/bin/subsystemctl sudo systemctl disable systemd-resolved sudo systemctl disable systemd-networkd
Windows Terminalの設定と起動
Windows Terminalの設定で、起動時に"subsystemctl shell --start --quiet"を呼ぶように設定しておきます。
{
"guid": "{XXXXXXXX-XXXX-XXXX-XXXX-XXXXXXXXXXXX}",
"hidden": false,
"name": "Ubuntu",
"source": "Windows.Terminal.Wsl",
"commandline": "wsl -d Ubuntu subsystemctl shell --start --quiet",
...
},
起動時に次のように表示されたら成功。このメッセージはWSL2の初回起動時だけに表示されますが、気になるなら"RUST_LOG=error subsystemctl shell --start --quiet"とすれば消えます。
[2020-09-26T07:05:16Z INFO subsystemctl] Starting systemd mame@hostname:~$
subsystemctlのための.bashrcの設定
.bashrcに次の一文を足しておきます。
stty -echoprt
これをしないと、バックスペースを押したときに表示が妙なことになることがあります。subsystemctlというより、machinectl shellを通すとechoprtが有効になるようなのですが、systemd側の設定でこれを止める方法を知ってる人がいたら教えてほしいです。
それから、WSL2はデフォルトでWindowsのPATH設定をすべて引き継いでくれますが、subsystemctlを通すとそれが消えます。個人的にはデフォルトの状態はパスが多すぎて補完がよくわからなくなったので、必要なものだけパスを通すことにしました。特に使うものはaliasにしています。
alias explorer="/mnt/c/Windows/SysWOW64/explorer.exe" alias chrome="/mnt/c/Program\ Files\ \(x86\)/Google/Chrome/Application/chrome.exe" alias code="/mnt/c/Users/ユーザ名/AppData/Local/Programs/Microsoft\ VS\ Code/bin/code" alias mery="/mnt/c/Users/ユーザ名/AppData/Roaming/Mery/Mery.exe"
あとsubsystemctlにすると、起動時のディレクトリが"/mnt/c/Users/ユーザ名"ではなく"/home/ユーザ名"になります。これも自分は満足していますが、不満なら適宜変えるとよいと思います。
subsystemctlに関係ないですがついでに。WSL2で大きいファイルや大量のファイルにアクセスしていると、たまにPCが激重になります。ホストのメモリ枯渇が原因（この記事が詳しい）で、topでbuff/cacheが巨大化していたらそれです。次のコマンドで軽くなるので、これもaliasを設定してます。
alias wsl2_drop_caches='sudo sh -c "sync && echo 3 > /proc/sys/vm/drop_caches"'
追記：WSLgのための設定
/tmp/.X11-unix/X0のunix socketで通信するようなので、systemdがtmpfilesを消してしまわないようにする。
sudo systemctl mask systemd-tmpfiles-setup-dev sudo systemctl mask systemd-tmpfiles-setup sudo systemctl mask systemd-tmpfiles-clean
.bashrcでDISPLAY環境変数を定義しておく。
export DISPLAY=:0
これでxclockなど立ち上がる、はず。
IOCCC ネタバレ解説はじめました & IOCCC 2020 に入賞したよ
IOCCC の全作品のネタバレ解説を目指すサイトを作りました。
いまのところ、最初の 4 年分まで書いてます（IOCCC 1984 ～ IOCCC 1987）。週ペースで書き足していくつもりなのでご笑覧ください。
IOCCC は、「現存する世界最古のプログラミングコンテスト」と言われることもあります。つまり、現在も開催されているということです。今年の正月に、昨年の IOCCC 2020 の入賞作品が公開されました。自分のプログラムが 3 つ入賞したので、デモ動画と簡単な紹介を書いておきます。
endoh1 - Most explosive
端末でのマインスイーパーですが、推論でわかるようなところは大体勝手に進めてくれます。 そういうダルくてミスしやすい作業はコンピュータにやらせて、マインスイーパーの本質（勘で適当に開くところ）に集中できます。
このプログラムは IOCCC 2019 用に作っていたのですが、時差で締め切りを勘違いして投稿しそこねたやつなので、1 年寝かしてました。そのわりにはひねりがあまりないですが、それでも今回の中では一番よい出来かなと思っています。 アニメキャラ形状のプログラムで有名な omoikane さんがマップを作ってくれたのがとても嬉しかったです。IOCCC を知ったきっかけが omoikane さんの作品なので感慨深い。
ちなみにこれは 2007 年頃に Java Web Start で作ってたネタの焼き直しです。
endoh2 - Best perspective
スター・ウォーズのオープニング風にメッセージを流す ROT13 デコーダ。
フォントはベジエ曲線で表現したものをコード内に埋め込んでいます。monumental quine で作った経験を生かして一晩くらいで作りました。
スター・ウォーズのスクロールはずっとやりたいと思っていたネタでしたが、いまいち面白くする工夫を思いつかず、ずっと放置していました。結局 ROT13 を混ぜる程度になったけれど、気に入り度は普通。
endoh3 -- Most head-turning
散髪屋にある時計のように左右反転している時計を埋め込んだ Quine 。
本当に単純なプログラムなので、これが採択されたのはちょっと意外でした。まあ、「今年の Quine」みたいな扱いでしょうか。もっと頑張りたかったので、やや不満な出来。
審査員から「Unicode の文字を使ったもっと鏡文字っぽいバージョンが欲しい」と言われたので、prog.alt.c も作りました。動画のいちばん最後にデモしてるとおり、I ᨅ ℇ ᔨ ਟ ∂ ⎲ 8 ♇ OI II ᨅI を使ってます。これを作らせたくて採択されたのかも。
他の入賞作品
こちらからどうぞ。
そのうち日本語での解説も書くのでお楽しみに。