STORES Product Blog

こだわりを持ったお商売を支える「STORES」のテクノロジー部門のメンバーによるブログです。

TRICK 2025 の mame のプログラムを語る

こんにちは、遠藤（@mametter）です。RubyKaigi 2025 では、変なコードで競い合う TRICK 2025 を開催しました。あらためまして、たくさんの投稿をいただき、本当にありがとうございました。

いまさらですが、自分が書いたプログラムについて語りたくなったので語ります。

Most Useful

github.com

概要

patch と diff をテーマとして、とにかくたくさんの要素を詰め込んだプログラムです。

  • patch コマンドとして動く
  • そのまま patch ファイルとしても解釈できる
  • 自分自身へのパッチを出力し、中心にある "p" のロゴを徐々に半回転して "d" にする
  • 最終的には diff コマンドとして動く
  • その間のパッチの連続を git log したら Quine になっている

Most Useful: 回るロゴ

挙動について詳しくは、TRICK 2025 Results の資料を見てください。

見てほしいところ：diff アルゴリズム

このプログラムは本質的には、Quine（自分自身を出力するプログラム）です。 ただ、自分自身をそのまま出力する代わりに、中心のロゴを少し回転した亜種を作ります。 また、回転後のバージョンをそのまま出力するのではなく、回転前と回転後の差分を diff にして出力します。

ということで、このプログラムのコアは diff の計算だと思ってます。 最終的に diff コマンドとして動くのはおまけで、途中のパッチ生成部分の diff コードを使いまわしただけになってます。

こういうアルゴリズムは、原理に沿ってナイーブに実装すれば、案外短く書けるものです。 正直あんまり覚えてないんですが、切り出してみたら次が diff コードのようでした。 O(NM) なので効率は度外視ですね。

S = <<END
aaa
bbb
ccc
END

T = <<END
aaa
BBB
BBB
ccc
END

o="--- file.old\n+++ file.new"

# 動的計画法で最長共通部分列問題を解き、エディットグラフを作る
a=[i=0]*v=(s=[s]+S.lines).size;
c=b=s.map{c=_1&&[c,?-+_1,i+=1]||0};
T.lines{|t|
  s.map{|s|
    a<<((s)?[x=a[-1],y=a[-v]].max+((f=s==t)?1:0):0);
    c,d=(f)?[v+1," "+t]:s&&(x>y)?[1,?-+s]:[v,?++t];
    b<<[b[-c],d,i+=1]
  }
};
c=b[-1].flatten;
b=c[(1..)%2];
# エディットグラフから diff を生成する
(b.map{_1[0]}*"").scan(/\s{,3}([-+]\s{,6})*[-+]\s{,3}/){
  n=c[2*i=$`.size];
  o=o,
    "@@ -%s,%s +%s,%s @@"%[n%v+1-1/v,(m=c[2.*i+j=$&.size]-n)%v,T>""?n/v+1:0,m/v],
    b[i,j]
}

puts o
#=>
# --- file.old
# +++ file.new
# @@ -1,3 +1,4 @@
#  aaa
# -bbb
# +BBB
# +BBB
#  ccc

裏話など

ときどき「どうやってそういう Quine を思いつくのか」と聞かれますが、日頃から目に入ったものについて、「これと Quine を組み合わせたらおもしろくないか？」と考えてます。

ある時 diff コマンドが意識に止まりました。diff はおもしろいコマンドなので、それをうまく Quine に絡めればとてもおもしろくなることは明らかでした。

なかなかうまい絡め方を思いつかなくて 5 年ほど死蔵していたのですが、「diff といえば git」「git log --oneline | ruby が動けばすごくない？」と思いついたので、あとは実装するだけでした。

ただ、実際にやってみたら git log --oneline | ruby は予想以上に難しくありませんでした。 各業の先頭に置かれるコミットハッシュを gsub で除去して実行するだけ。 一番最初の行に置かれるコミットハッシュだけはそれで回避できないのですが、最初の一文字が a ～ f のアルファベットであれば、ただの識別子として扱われるので、文法エラーにはなりません。 BEGIN { } という最高の言語機能を使うことで、そこの実行を回避するだけで済みます。

それで不安になって要素をてんこ盛りにしたのですが、これは逆効果だったかなあ。 もっとすっきりまとめつつ、もっと本質的に困難な課題設定ができていれば金賞いけてた気がする。 思い入れの強かったネタほど綺麗にまとめにくいかもですね。

Best Bonus

github.com

概要

irb の syntax highlight で絵を書こう！という、一発ネタなプログラムです。

  • bbb を入力したら 111 を出力する（irb で 111 は数字のリテラルとして青く表示される）
  • rrr を入力したら ";" を出力する（irb で ";" は文字列リテラルとして赤く表示される）
  • などなど

Best Bonus: irb で神奈川沖浪裏を描いた様子

詳しくは資料を参照ください。

見てほしいところ：意外と丁寧なコード生成

発表ではまったく説明できなかったんですが、実はこのコード生成はそこまで自明ではないです。

rrrrrbbbbb を入力したとき、安易に ";;;"11111 を出力してしまうと、";;;"という文字列リテラルの直後に11111という数値リテラルが続いているため、Ruby コードとしてはパースエラーになってしまいます。 これでは irb で期待通りに色付けされません。

パースエラーのせいで青くならない

そこでこのプログラムでは、必要に応じて色指定を無視してセミコロンを挟む配慮をしてます。bbbbbrrrrr に対しては ";;";11111 を出力するようになってます。

セミコロンを挟むと意図通りに色付けされる

特にこだわったのが c（水色）の指定です。 c は nil true false の 3 つをセミコロンで区切りながらうまいこと埋めるのですが、

  • 長さが 1 や 2 の場合は埋められないのでセミコロンにする
  • なるべく左右の両端が水色になるようにしたい
  • セミコロンの連続は避けたい
  • 機械的に false を選んで単調にしたくない

などなど、試行錯誤を繰り返して謎のアルゴリズムをあみだしました。

nil/self/false をいい感じに詰めていく様子

裏話など

syntax highlight で絵を書くという発想は、IOCCC 2012 の "Most useful obfuscation" から得ています。パクリですね。向こうは「syntax highlighter のプログラムで、自分自身を syntax highlight すると絵が浮かび上がる」というもので、ネタの完成度が高い。

こちらは irb がすでに実装している syntax highlighter を使うので、小ネタとして小さくまとめるつもりでした。やってみたら上記のように、コード生成にこだわりが必要でおもしろかったです。

仕上がり自体は気に入っているのですが、「syntax highlighter の悪用」というネタかぶりがあったのは残念。あきらかに tompng さんの "Most Arithmetic" のほうがクオリティが高いので、文句のつけようがないですね。

Most Uncovered

github.com

概要

バーコード生成をするプログラム。ただし出力は、コードカバレッジとして行います。

Most Uncovered: バーコード画像を生成した様子
詳しくは資料を。

見てほしいところ：バーコード生成とコードカバレッジの相性

このコードの肝は、次のガジェットです。

v=
[->{p}][cond] # ※
v&.()

cond が 0 なら※の行がカバー（実行）される、1 ならカバーされません。 これによってコードカバレッジを制御しています。 ただ、このガジェットだと、v= の行や v&.() の行は常に実行されてしまいます。 どうしたかというと、バーコードの仕様を exploit して問題を回避しました。

よく見る 13 桁のバーコードは EAN-13 と呼ばれるものですが、これは実はすごく簡単な仕様です。

英語版 Wikipedia の記事が詳しいですが、ざっと説明すると、次のような感じです。

  • 2～7 番目までの 6 桁を左半分、8～13 番目までの 6 桁を右半分で表現する（最初の数字だけは特別扱い）
  • 各数字には、L 、G 、R という 3 つの符号（7 ビット）が決まっている
  • 左半分は、最初の数字に応じて L の符号または G の符号を並べる
  • 右半分の 6 桁は、対応する R の符号を並べるだけ

コードで見たほうがわかりやすいかもしれません。

S = %w(LLLLLL LLGLGG LLGGLG LLGGGL LGLLGG LGGLLG LGGGLL LGLGLG LGLGGL LGGLGL)
L = %w(0001101 0011001 0010011 0111101 0100011 0110001 0101111 0111011 0110111 0001011)
G = %w(0100111 0110011 0011011 0100001 0011101 0111001 0000101 0010001 0001001 0010111)
R = %w(1110010 1100110 1101100 1000010 1011100 1001110 1010000 1000100 1001000 1110100)

# エンコードしたい13桁の数字
v = "9780201710892"

# 最初の数字だけ特別扱いをする
s = S[v[0].to_i]

# 左半分の出力
o = "0" * 11 + "101"
6.times do |i|
  n = v[i+1].to_i
  o += s[i] == ?L ? L[n] : G[n]
end

# 中間セパレータ
o += "01010"

# 右半分の出力
6.times do |i|
  o += R[v[i+7].to_i]
end
o += "101" + "0" * 7

puts o
#=> 00000000000101011101100010010100111001001101001110011001010101000100110011011100101001000111010011011001010000000

ここで興味深いのが、L または G の符号は常に右端が 1 であり、また、R の符号は常に左端が 1 なことです。

これが、コードカバレッジでエンコードするのに大変都合がいいんです。 私が使ったカバレッジ制御のガジェットでは、どうしても常に実行されてしまう行（v= など）が存在します。 その「常に実行されてしまう行」を、バーコード仕様上の「常に1になるビット（＝必ず実行される行）」に割り当てることで、バーコードのデータ部分に影響を与えることなく、カバレッジのON/OFFを制御できました。

裏話など

きっかけは、同僚の @riseshia さんが「コードカバレッジを悪用して TRICK ネタを作りたい」と言っていたことでした。

行カバレッジは一次元なので、一次元で表現できる、ハッカー心をくすぐるもの。と言えば、セルオートマトンとバーコードが思いつきました。

結局 @riseshia さんは別のネタを考えることにしたそうなので、埋もれさせるには惜しいネタと思い、ネタを引き継いで完成させました。

やってみたら、サイズ制限内で実装するのが意外と大変でした。仕上がりには結構満足してます。ただ、コードカバレッジの挙動が変わって動かなくなる日が来そうなエントリではあります。

おまけ：HELLO!

TRICK とはどういうコンテストか、を一目でわかってもらえるよう、HELLO! というプログラムを書きました。

$s=   %w(   p=25;;$-w   ?44         1.t         imes{|x|$   ><<
"\s   $s=   %w(         #$s         )*'         ';e   val   #{p
&&"   ?$+   "}$         s;"         [(v         ="u   Eqm   bHj
UDQ=nHjUD   QmbHJu]wE   UrD         kjj         hUU   Emj   fhU
UEm   jjh   JR]         C"[         x/1         8+(   p||   0)]
.or   d[x   /3%         6])         *$.         +=v   ]+?
\n[   0,x   %63/62]}:   puts("Hel   lo!")#YE;   )*'';eval   $s;

これは、実行すると "Hello!" と出力します。

$ ruby hello.rb
Hello!

警告を有効にする -w オプション付きで実行すると、WORLD に変形します。

$ ruby -w hello.rb
$s=   %w(   p=2      5;;      $-w?44      1.t         imes{|
x|$   ><<   "\s   $s=   %w(   #$s   )*'   ';e         val   #{p
&&"   ?$+   "}$   s;"   [(v   ="u   Eqm   bHj         UDQ   =nH
jUD   Qmb   HJu   ]wE   UrD   kjjhUU      Emj         fhU   UEm
jjh   JR]   C"[   x/1   8+(   p||   0)]   .or         d[x   /3%
6])   *$.   +=v   ]+?   \n[   0,x   %63   /62         ]}:   put
   s("   Hel         lo!      ")#   YE;   )*'';eval   ?$+$s;

この WORLD を実行すると "Hello!" を出力するのですが

$ ruby -w hello.rb | ruby
Hello!

-w オプション付きで実行すると、最初の HELLO! というプログラムに戻ります。

$ ruby -w hello.rb | ruby -w
$s=   %w(   p=25;;$-w   ?44         1.t         imes{|x|$   ><<
"\s   $s=   %w(         #$s         )*'         ';e   val   #{p
&&"   ?$+   "}$         s;"         [(v         ="u   Eqm   bHj
UDQ=nHjUD   QmbHJu]wE   UrD         kjj         hUU   Emj   fhU
UEm   jjh   JR]         C"[         x/1         8+(   p||   0)]
.or   d[x   /3%         6])         *$.         +=v   ]+?
\n[   0,x   %63/62]}:   puts("Hel   lo!")#YE;   )*'';eval   $s;

これは、-wオプションの有無で組み込み変数$-wの値（true / false）が変わることを利用して、処理を分岐させています。

小ネタでした。

まとめ

TRICK 2025 に入賞した自分の 3 つのプログラム＋αについて語りました。長文にお付き合いいただき、ありがとうございました。

今回紹介したコードは、実用性だけを考えれば無意味なものばかりです。 しかし、普段使っているツールや言語の仕様の境界を探り、その隙間でいかに面白い「表現」ができるかを探求するプロセスは、私にとって非常に価値のある遊びです。

5年間アイデアを温め続けたdiffのネタのように、すぐには形にならないこともありますが、そうした遊びの中から、時として普段の仕事にも活かせるような深い理解や発見が生まれることもあります。

皆さんもぜひ、自分だけの「変なプログラム」を育ててみてはいかがでしょうか。 そしてまたいつか TRICK を開催すると思うので、そのときは是非投稿をお願いします！