TRICK2015 開催報告＆入賞作品紹介

初稿：2016-04-03

書いた人： 遠藤侑介 (@mametter)

はじめに

TRICK は、Ruby を使って「変」なプログラムを書き、その「変」度で競い合うプログラミングコンテストです。第 2 回となる TRICK 2015 は、RubyKaigi 2015 の場を借りて結果発表を行いました。この記事はその入賞作品について紹介していきます。

TRICK について

TRICK は Transcendental Ruby Imbroglio Contest for rubyKaigi の略で、日本語にすると「超絶技巧 Ruby 意味不明コンテスト」という意味です。

内容としては上述の通り、競い合って変なプログラムを書き、愛でようというイベントです。Ruby は「読みやすいプログラム」だけでなく、「読みにくいプログラム」を書く言語としても一流であることを実証したいと思ってます。IOCCC をご存知の方は、それの Ruby 版と考えて貰えば早いです。

開催の目的やルール、審査員などについては、公式サイトをご覧ください。基本的に第 1 回の TRICK 2013 から変わっていないので、過去の開催報告もあわせてご覧ください。

入賞作品一覧

今回の入賞は 12 作品です。総合点で上位だったトップ 5 作品に加え、審査員ごとに最高点を取った 7 作品を入賞としました。入賞作品は公式サイトで公開しています。

上位 5 位

  • 金賞: “Best piphilology” - kinaba
  • 銀賞: “Most unreadable ALU” - Keisuke Nakano
  • 銅賞: “Doubling amphisbaena award” - monae
  • 4位: “Least general solver” - Benoit Daloze (eregon)
  • 5位: “Most general solver”- Keisuke Nakano

審査員賞

  • leonid 賞: “Most inconsistent” - Koichi Sasada (ko1)
  • eto 賞: “Most illusionistic” - Don Yang
  • eban 賞: “Best document” - yoshi-taka
  • mame 賞: “Most timely” - Koichi Sasada (ko1)
  • matz 賞: “Matz Lisp award” - Kazuki Tsujimoto
  • shinh 賞: “Most fragile” - NAKAMURA Usaku
  • yhara 賞: “Most beautiful pattern” - Shinichiro Hamaji

各作品解説

以下、各作品をネタバレ気にせず紹介していきます。自分で読解を楽しみたい人はご注意ください。

金賞: “Best piphilology”

「円周率おぼえ歌」を Ruby で実現したものです。プログラムのトークンの長さを順番に見ていくと、

   big , temp = Array 100000000 ** 0x04e2
    3  1   4  1   5       9      2    6

ということで、円周率の桁数が出てきます。そして、実行すると円周率 10000 桁が出力されます。

解説

これはとても強烈なプログラムでした。グローバル変数の alias を使うことで、異なる桁数のトークンから同じ変数にアクセスしたり、前の乱数の種を返り値とする srand を記憶領域として使ったり、まさに TRICK でしか使えないような知識がいろいろ発見されました。

さすがにすべてのトークンを活用するのは難しいということで、桁合わせのために無意味なトークンが挿入されています。77 の本質的に必要なトークンに対し、165 のムダなトークンがあるとのことで、何倍に膨れ上がったかを計算すると、(165 + 77) / 77 ≒ 3.14 になるという。無意味さの中にも意味を入れるという、隙のないプログラムでした。

詳しくは、作者の kinaba さんが解説しているので、そちらもお読みください。

なお、誤解してはいけないのは、3文字＋スペース＋1文字＋スペース＋4文字＋… というだけのプログラムではないことです。1+1 とスペースを空けずに書いても、トークンとしては 1 文字が 3 つになります。

銀賞: “Most unreadable ALU”

コラッツ数列1の生成器です。これを、整数演算も分岐も使わずに実現しています。

解説

全体的に % だらけの意味不明なプログラムになっています。N の偶奇によって処理を切り替える仕組みを整数演算も分岐も使わずに実現するトリックだけ紹介します。

”, という 2 文字を N 回繰り返す、次のようなプログラム文字列を作って eval します。

[ ", ", ..., ", ]; even #"]; odd

N が偶数の場合、例えば 4 のときは次のようになります。

[ ", ", ", ", ]; even #"]; odd

見ての通り、意味のない配列リテラルの直後にある even が実行されます。odd はコメントアウトされます。

N が奇数の場合、例えば 3 の場合は次のようになります。

[ ", ", ", ]; even #"]; odd

even やコメント記号が文字列リテラルに閉じ込められ、odd が地の文として現れてきます。以上。

このように整数演算や分岐を使っていないところもすごいんですが、それだけでなく、意味ありげに見える文字列に意味がなかったり、意味なさそうに見える文字列が重要な意味を持っていたり、これほど読みにくい 106 バイトはなかなかお目にかかれません。ぜひ解読に挑戦してください。これも作者の Keisuke Nakano さん自身が詳しく解説してくださっているので、そちらをお読みください。

銅賞: “Doubling amphisbaena award”

実行すると、自分自身を 2 倍に増殖させたプログラムを表示します。それを実行するとさらに 2 倍に、と、ドンドン大きくなっていきます。

解説

アンフィスバエナというのは、しっぽも頭になっている双頭の蛇のことですが、よくドラゴンのように書かれるようです。それにちなんで、プログラムの形状はドラゴン曲線（の亜種）になってます。

挙動自体はわりと普通と言えなくもないんですが、コードがかなり簡潔にまとまっていて、多くの審査員の心を打ってこの順位となりました。作者の monae さんが詳しく解説しているので、そちらをどうぞ。

4位: “Least general solver”

数独ソルバです。単に 1 つの解を見つけるのではなく、全部の解を列挙します。なお、数独の問題は、コード中に直接埋め込んであります。当然、盤面は固定ではなく、書き換え可です。

解説

1 行めのコードが難読化の肝です。

class String;def[]*a;$*<<a;b;end

String#[] を再定義し、引数の列を $* に追加しています。$* はコマンドライン引数の配列ですが、ゴルフ界隈では空として初期化済みの配列として使われます。b は String#b で、バイナリエンコーディングの文字列を返すメソッドですが、このプログラムでは事実上の self として使っています。エンコーディングなんかどうでもいい。

このような String#[] を定義すると何が嬉しいかというと、

   code="pri"[1, 2, 3]+"nt 1"

というコードを実行した時、変数 code には “print 1” というプログラム文字列が代入され、$* には 1, 2, 3 という数列が入ります。これによって、プログラム本体に割り込んでくる数独盤面のゴミ文字列を巧妙に回避しつつ、その盤面の情報も記憶することができています。

数独を解くプログラム本体は、Fiber を使って全探索をするコードが書かれています。たいへん教科書的なコードですが、Fiber での探索は慣れていないとなかなか解読が大変だと思います。でも勉強になるので、ぜひ解読してください。

ちなみに、5 位の SAT ソルバもこの数独ソルバもどちらも NP 完全問題の解を見つけるプログラムですが、SAT ソルバは色々な問題に応用できるのに対し、この数独ソルバは数独にしか使えません2。ということで、数独ソルバの方がより役に立たないわけですが、役に立たない方が上位に来たのは TRICK らしくていいなあと個人的に思っています。

5位: “Most general solver”

194 バイトの SAT ソルバです。以上。

解説

一定の形式をした論理式を真にするような変数割当を見つける問題を、充足可能性問題 (Satisfiability problem, SAT) といいます。

以下、Ruby の式を使って説明します。x && !y という式が与えられたとき、これを真にするには x = true; y = false としておけばいいです。x && !x は、x にどのような値を入れても真にすることはできません3。こういうふうに、式が与えられたとき、それを真にするように変数の値を決めていく問題が SAT です。4

そして SAT ソルバとは、SAT 問題を解いてくれるツールのことです。有名な SAT ソルバには MiniSAT や Sat4j などがあり、さらにこれらを改良したり組み込んだりした亜種がいろいろ存在します。SAT ソルバは、何か解きたい問題があるときに、その問題を SAT に変換し、SAT ソルバで解を見つけて、解を逆変換する、という風に使われます。興味のある人は調べてください。

……という SAT ソルバと、（理論上は）同等の振る舞いをするプログラムを、たった 194 バイトで実現したというのがこの作品です。SAT 問題を正規表現マッチングの問題に変換し、正規表現エンジンにぶん投げるという仕組みになっています。（後方参照のある）正規表現マッチングは NP 完全問題なんですよね。詳しくは、作者の Keisuke Nakano さん自身が丁寧に解説してくださっているので、そちらをお読みください。なお、Keisuke Nakano (ksk) さんは著名な Ruby ゴルファーです。

後日談として、この SAT ソルバは果たして最小なのか？ということで、TRICK の審査員のひとりである浜地慎一郎 (shinh) さんが経営するゴルフ場で同様のプログラムを書くコンペが開かれたようです。チートっぽいのを除けば、shinh さん自身が書いた 188B が今のところ最短のよう？

yhara 賞： “Most beautiful pattern”

コードがバラバラ殺人事件です。もちろん、このままちゃんと動きます。実行すると、自分自身のソースコードを出力します。つまり Quine ですね。

解説

これの肝は「ほぼ 2 文字単位でバラバラにするという形状制約の下で、如何に eval を呼ぶか」というところになります。これは大変込み入っているので発表時には割愛したんですが、ここで要点だけ説明します。

Ruby には、eval という文字列を使わずに eval を呼び出すという、何とも意味不明なイディオムというのがあります。それがこれです。

->(&_){_["","ev"+"al","実行したいコード"]}[&:send]

これがどのように動くかは解説しません5が、なんとこれで

eval("実行したいコード")

と（ほぼ）同等の意味になっています。

これを使えば、ほとんどの部分は 2 文字単位でバラバラにできるのですが、:send のところだけはうまく切れません。ここで、Ruby 2.0 で導入された %I() というシンボルの配列のリテラルが活用できます。

%I(  #{ ?s + ?e + ?n + ?d }  )[0]

これで :send が得られます。残念ながら %I( の 3 文字だけはこれ以上分割できませんが、それ以外は無事 2 文字単位バラバラが実現できました6。%I() は必要性がよくわからない機能ですが、このようなプログラムのために生まれたのだと納得できました。

shinh 賞: “Most fragile”

これも実行するとメッセージが出る系です。

$ ruby entry.rb
hello trick

さて、このメッセージはどのように隠されているでしょうか。

解説

各行の長さとしてメッセージが埋め込まれています。

例えば 1 行めの lines = Array.new は 18 文字です。18 に 62 を足すと 112 で、これは ‘p’ の ASCII コードです。2 行めは 23 文字で、62 を足すと ‘u’ の ASCII コードです。こんな風に各行を解釈していくと、

puts"hello trick"

という Ruby コードが出現します。これを eval するという仕組み。

各行の文字数を変えるだけで動かなくなるので、「少し変えて動作を見てみる」という解析方法が使えず、なかなか巧妙でした。自然なインデントに仕上げようとしている意図を感じつつ、一部不自然なところが残っているところ（謎のセミコロンだけの 1 行など）がかえって好評になったようです。

matz 賞: “Matz Lisp award”

大きな「λ」が目を引きますが、注目すべきは最後の 5 行です。どう見ても Ruby ではなく Scheme な階乗計算プログラムが書かれています。実はこの 5 行は、ちゃんと階乗計算をする Ruby プログラムです。どういうことでしょうか。

解説

Ruby としても Scheme としても実行できるプログラムです。いわゆる polyglot 。

前半の「λ」形をしたのコードブロックは、Ruby として解釈した時には Scheme インタプリタになっています。このインタプリタは、Scheme 風に書かれた最後の 5 行を実行します。

Scheme として解釈した時には、前半のラムダはコメントとしてすっかり無視され、最後の 5 行が Scheme プログラム本体として実行されます。つまり、Scheme 風に書かれたプログラムは本当に Scheme プログラムだったのでした。

このプログラムの審査についてはちょっと申し訳ないところがあります。インタプリタが作りこまれてるわりに、サンプルプログラムが階乗計算だけなのがつまらない、などと思っていたのですが、remarks にちゃんと metacircular evaluator の例が載ってました。他の審査員はどうか知りませんが、遠藤は完全にこれを見逃していました。すみません。このプログラムが Ruby インタプリタで評価できるのはなかなか圧巻ですね。

mame 賞: “Most timely”

実行すると、なんかメッセージが出てきます。

$ ruby entry.rb
"Nope. Already been there."

Back to the Future III のドクのセリフだそうです。

解説

このプログラムのどこにこのようなメッセージが隠されているでしょう。といってもクイズにならないくらい、見るからに怪しい時刻の列がありますね。デコード方法が少し凝っています。まずこの時刻の列をソートし、UNIX 時間の整数に変換し、0xff でビット積を取るとメッセージの ASCII 文字列が出てくるという趣向です。Ruby が 2038 年問題をすでに解決していることを華麗にデモしているとも言えます。

これの良さを文章で語るのは難しいのですが、プログラム中にメッセージを隠す系の投稿はかなりあった中で、シンプルかつお洒落に感じました。

eban 賞: “Best document”

Ruby プログラムとしても、markdown としても解釈できるテキストです。

Ruby プログラムとして実行しても何も起きません。驚くべきことに、エラーも出ないんです。プログラム全体にわたって、さまざまなテクニックを駆使して SyntaxError も NoMethodError も起きないよう、大変巧妙に書かれています。

解説

例えば 3 行目を見てみると、

What if $1 and under junk games take over the world.

は、$1 が正規表現の backref ですが、この時点で正規表現マッチングをしていないので nil と評価されます。すると nil and … という式になるので、後半部分は実行されません。さらにこの文全体は What if nil という文になるので、後置 if にとして解釈され、やはり What の部分が実行されません。

4 行目の最後は

TRICK!!!

となっていますが、このびっくりマークは 2 つ以上必要です。というのは、1 つめは TRICK! というメソッド名の一部として解釈され、2 つめ以降は式の否定演算子となるからです。これによって、2 行先の Demo まで無効化しています。

10 行目の

Criminal 1 :: There he is!

の :: もわからない人もいるかもしれません。これは定数参照の演算子で、Enumerator::Lazy などの :: と同じです。が、普通に実行すれば 1 はクラスでもモジュールでもないのでエラーになるのですが、これも巧妙に実行されないようになっています。（どこで無効化されているでしょうか？）

他にも Ruby の文法の闇に触れるヒントが多数仕込まれているので、ぜひ解読してみてください。

leonid 賞: “Most inconsistent”

Ruby としては見慣れない文字列が並んでいるプログラムです。実行すると、以下のようになります。

$ ruby entry.rb
"__\x10_________\xF0_____________"

26 文字なので、A から Z がだいたい _ になっているのですが、2 箇所ほど文字化けが起きています。どういう意味でしょうか？

解説

このプログラムを理解するには、Ruby の少しマイナーな言語機能を知っている必要があります。

?X が「文字リテラル」であることはご存知の人も多いでしょう。Ruby において文字は 1 文字の文字列なので、つまり “X” と同じ意味です。しかしこれにエスケープシーケンスが使えることは、あまり知られていないかも知れません。たとえば ?\n で “\n” と同じ意味になります。

それから、存在しないエスケープシーケンスを使ったときは、エスケープ記号が無視されるという挙動を知っておく必要があります。”\A” と書いても、そういうエスケープシーケンスはないので、”A” と書いたのと同じになります。7

例として、?\A-p を解釈してみます。?\A の部分は、”\A” と同じ意味なので、”A” という文字列になります。p はデバッグ出力に使う Kernel#p メソッドですが、無引数で呼び出すと nil を返します。よってこの式は、”A” - nil を計算することになります。String#- というメソッドはないですが、プログラムの末尾で Object#- を定義しています。このメソッドは単に self を返すので、この式は “A” を返すことになります。このように得られた文字列を A から Z まで結合し、最後に tr(“A-Z”, “_”) を実行するので、基本的にはアンダースコアばかりの文字列になります。

ここまでが前提知識。このプログラムの本題は、一部だけアンダースコアでなくなるのはなぜか？ということです。あっさり答えを言ってしまうと、”\C-p” と “\M-p” が仲間はずれです。これらは全体として、コントロール文字とメタ文字を表すエスケープシーケンスになります。

$ ruby -e 'p "\C-p"; p "\M-p"'
"\u0010"
"\xF0"

この機能は Emacs Lisp 由来という噂ですが、正直、現代でどの程度使われている機能なのかわかりません。そんな機能に脚光を浴びせてみるのも TRICK の一興です。

eto 賞: “Most illusionistic”

「シェルゲーム」のアニメーションを表示するプログラムです。シェルゲームとは、3 つのコップの中に 1 つだけボールを入れて、コップを何度も入れ替え、「さあボールはどこでしょう？」とする遊びです。

言葉の説明ではわからないかもしれませんが、実行してみればすぐ分かります。以下のように実行するといいですよ。

$ ruby entry.rb | tee result.rb
$ ruby result.rb

解説

技術的に特筆するところは、正直あまりありません。Ruby でアニメーション表示をするプログラムを普通に書いて、zlib 圧縮し、さらに BASE64 エンコードしてあるだけです。そのため、これを入選させるかどうかは審査員の間で少し意見が割れました。しかし、TRICK は必ずしも技術力を競うコンテストではないということで、アイデアを大きく評価して入選となりました。

ちなみに作者の Don Yang は IOCCC の常連入賞者で、その道では大変有名な akari.c や misaka.c の作者さんです。

景品

作品は以上です。景品は、

  • 受賞者全員: 「変態」の称号
  • 上位 5 作品: Ruby 公式リポジトリにサンプルコードとしてコミットされる (Ruby 2.3 としてリリース済み）

ということになりました。

全体評

前回以上におもしろい作品が一杯で、選定には審査員一同、苦労しました。前回と比べると、以下の点がよかったと思います。

  • 前回は審査員自らが投稿した作品ばかり入賞してしまったのですが、今回は 1 作品しか入賞しませんでした。投稿しなかったわけではないので、投稿作のレベルが上がってきたためと思います。
  • 前回は日本以外からの投稿がなかったのですが、今回は海外からの投稿もあってよかったです。
  • Rubykaigi での発表会場が巨大化しました。前回はサブセッションの位置づけで会場が立ち見であふれたためかと思います。ただ、正直興味のないだろう方まで見させられることになったのは良し悪しだったかもしれないですね。もっと少人数でカルト的に開催するのもありかもしれない。

なお、この文章は一審査員である筆者 (遠藤) の独断と偏見で書かれているので、他の審査員の記録にもリンクをはっときます。

まとめ

TRICK 2015 の作品紹介と審査員講評でした。応募いただいたみなさんと、最高の発表の場を提供してくださった RubyKaigi スタッフのみなさん、あと他の審査員のみなさんに感謝します。次回開催は未定ですが、もしあればまた会いましょう。

筆者について

遠藤侑介。CRuby コミッタ。超絶技巧プログラミング提唱者、IOCCC 2012,2013,2014,2015 入賞。Twitter: @mametter

  1. n が偶数だったら 2 で割り、基数だったら 3 をかけて 1 を足す操作を繰り返して得られる数列。 ↩

  2. もちろん理論上は NP 完全の問題は相互に還元可能なわけですが、わざわざ数独問題に還元させる人はいないと思いますので。 ↩

  3. もちろん、! を再定義するみたいなチートはなしで。 ↩

  4. ちなみに、式は「連言標準形」という形式に従う必要があります。 ↩

  5. 興味のある方は拙著「あなたの知らない超絶技巧プログラミングの世界」の 174 ページから 175 ページをお読みください :-) 読者プレゼントのページも参照のこと。 ↩

  6. 完全な 2 文字分割は今のところ未解決問題です。 ↩

  7. なお、将来的に \A というエスケープシーケンスが Ruby に導入された場合、このプログラムは予期せぬ挙動になる可能性があるので、普通のユーザは使うべきではありません。 ↩