[Ruby] 初めての記号プログラミング

概要

Ruby はその言語の特性を利用することで，英数字を使用せずにプログラムを書ける．英数字を使用しないプログラムを書くことは，俗に記号プログラミングと呼ばれる．

この記事では，偉大な先駆者の記事をベースに，詳しい解説を加えつつ，競技プログラミングの簡単な問題に正解するプログラムを作成する段階まで追加で説明する．

前提

• Ruby で FizzBuzz を書ける
• Ruby で簡単な再帰処理をかける

注意事項

記号プログラミングは，暇を持て余したプログラマーが個人で楽しむための遊びである．保守性や可読性が著しく低いため，仕事では使用しないこと．

本編

先に方針について触れると，最終的には eval に任意の文字列を渡すことで任意のプログラムを実行させる．そのためには文字列を生成する必要があるが，英字は使用できないため数値を使用する．よって，まずは数値を錬成する．

0 と 1 の錬成

Ruby で記号のみから数値を錬成する最も簡単な方法の一つで，参考元でも紹介されている正規表現を応用した手法を示す．

# 1 を錬成
@_ = '_' =~ /$/
# 0 を錬成
__ = @_ - @_

@_ と __ は変数名である．Ruby では変数名に _ を使用できるほか，接頭辞にインスタンス変数を意味する @ やグローバル変数を意味する $ などを使用できる．ただし，この記事で紹介する使用方法は決して推奨されるものではないので注意されたい．

/$/ は文末にマッチし，=~ はマッチが成功するとマッチした位置のインデックスを返すため，長さ 1 の文字列に対してマッチさせると 1 が返る．よって @_ には 1 が代入される．また，__ に 1 - 1 を代入することで 0 が得られる．

任意の整数を取得

同様の方法で任意の数値を取得すると記述量が膨大になるので，記号で表現された符号なし 2 進数を整数に変換する処理を定義する．

まずは通常の (0 と 1 で構成された) 2 進数の文字列を 10 進数の数値に変換する処理を示す．

def f(s)
  if s[-1] != nil
  	return (s[-1] == "1" ? 1 : 0) + (f(s[0...-1]) * 2)
  else
  	return 0
  end
end

最下位桁の文字 (s[-1]) を 0/1 に変換したものと，それより上の桁を変換したものを 2 倍したものを足す，再帰的な処理として実装した．例えば，次のようにして呼び出せる．

f("10010") #=> 18

次に，記号のみで定義するために同じ処理をメソッドではなく Proc として定義する．

f = -> (s) {
  if s[-1] != nil
  	return (s[-1] == "1" ? 1 : 0) + (f(s[0...-1]) * 2)
  else
  	return 0
  end
}

例えば，次のようにして呼び出せる．

f["10010"] #=> 18

数値を 2 倍する処理は，左方向に 1 桁ビットシフトする処理に置換できるので，f(s[0...-1]) * 2 を f[s[0...-1]] << 1 とする．

後の記述量を減らすために，s[-1] == "1" ? 1 : 0 は正規表現を使用して " " + s[-1] =~ /1/ || 0 と書き換える．

また，if X then Y else Z は三項演算子を用いて X ? Y : Z に置換できるので，次のようになる．

f = -> s {
  s[-1] ? (" " + s[-1] =~ /1/ || 0) + (f[s[0...-1]] << 1) : 0
}

使用されている全ての英数字を記号に変換する．ここでは，. と | で構成された文字列を，. = 0，| = 1 として変換する．

# 1 を錬成
@_ = '_' =~ /$/
# 0 を錬成
__ = @_ - @_
# 任意の数値を取得
$_ = -> _ {
  _[-@_] ? (" " + _[-@_] =~ /\|/ || __) + ($_[_[__...-@_]] << @_) : __
}

例えば，次のようにして呼び出せる．

$_["|..|."] #=> 18

余分 (?) な空白と改行を取り除く．改行の代わりに ; を使用して，処理の境目を判別させることができる．

@_='_'=~/$/;__=@_-@_;$_=->_{_[-@_]?(" "+_[-@_]=~/\|/||__)+($_[_[__...-@_]]<<@_):__}

英数字の取得

Ruby では << を使用して文字列を破壊的に連結できるが，(噛み砕いて言うと) 引数が整数の場合には ASCII コードの値に応じた文字に変換して連結される (詳しくはリファレンスを参照)．

'' << 65 #=> "A"
'' << 67 << 65 << 84 #=> "CAT"

数値の代わりに先ほど定義した Proc $_ を使用することで，記号のみから任意の英数字 (および ASCII コードで定義されている記号) を取得できる．

'' << $_["|.....|"] #=> "A"
'' << $_["|....||"] << $_["|.....|"] << $_["|.|.|.."] #=> "CAT"

標準出力

Ruby では，$> を使用して文字列を標準出力できる

$> << "CAT" #=> nil

任意の処理

ここまでの記述で任意の文字や数値を出力することはできるが，それ以上の処理を人の手で記述するのは現実的ではないため，ここからはあまり綺麗ではないが eval を利用する．

しかし，今のままでは eval すらも記述できないため，追加で Proc を定義する．

# 定義する
g = -> (arg, proc) { proc['', arg] }
# 呼び出す
g["1 + 2", :eval.to_proc] #=> 3

Proc の引数にブロック引数 proc を渡すことで，Proc の中で proc を実行できる．ここでは，eval を Proc 化したものと，その引数として渡すための文字列 arg を g の引数に渡すことで，arg をプログラムとして実行する Proc g を定義した．

実行される proc は第一引数をレシーバーとするが，eval はレシーバーを指定せずに実行するため '' としている．

& と Symbol を連結すると暗黙的に同名の Proc に変換され，ブロックとして渡される．対応する引数をブロック引数にすることで，次のように書き換えられる．

# 定義する
g = -> (arg, &proc) { proc['', arg] }
# 呼び出す
g["1 + 2", &:eval] #=> 3

ただし，実行環境によっては '' に対して eval を呼び出そうとするとエラーが発生する．

Main.rb:1:in `block in <main>': private method `eval' called for "":String (NoMethodError)

従って，send を経由して呼び出すように書き換える．send の引数には Proc ではなく Symbol を渡す．

# 定義する
g = -> (arg, &proc) { proc["", :eval, arg] }
# 呼び出す
g["1 + 2", &:send] #=> 3

実行するたびに &:send を指定すると記述量が増えるので，Proc g を呼び出す g1 を定義する．

# eval を実行する
g = -> (arg, &proc) { proc["", :eval, arg] }
# eval を実行するための send を呼び出す
g1 = -> (arg) { g[arg, &:send] }
# 実行
g["1 + 2"] #=> 3

先述した記号を英数字に置換する Proc $_ を使用して Proc g と g1 を記号に書き換え，余分な空白を取り除く．

# eval を実行する
$___=->(_,&__){__["",:"#{''<<$_['||..|.|']<<$_['|||.||.']<<$_['||....|']<<$_['||.||..']}",_]}
# eval を実行するための send を呼び出す
$__=->(_){$___[_,&:"#{''<<$_['|||..||']<<$_['||..|.|']<<$_['||.|||.']<<$_['||..|..']}"]}
# 実行
$__["1 + 2"] #=> 3

標準入力

一行に 2 個の整数 a，b が並ぶ標準入力を受け取る，一般的な実装の一つを示す．

a, b = gets.split.map(&:to_i)

先ほど定義した $__ を使用して書き換える．

a, b = $__["gets.split.map(&:to_i)"]

英数字を記号に置換する．

_,__=$__[''<<$_['||..|||']<<$_['||..|.|']<<$_['|||.|..']<<$_['|||..||']<<$_['|.|||.']<<$_['|||..||']<<$_['|||....']<<$_['||.||..']<<$_['||.|..|']<<$_['|||.|..']<<$_['|.|||.']<<$_['||.||.|']<<$_['||....|']<<$_['|||....']<<$_['|.|...']<<$_['|..||.']<<$_['|||.|.']<<$_['|||.|..']<<$_['||.||||']<<$_['|.|||||']<<$_['||.|..|']<<$_['|.|..|']]

競技プログラミングの問題例

2 個の正整数 $A$，$B$ が以下の形式で与えられるとき，$A^B$ と $B^A$ のうち大きい値を出力せよ．

A B

この問題に正解するプログラムを記号のみで記述する例を示す．

# 1 を錬成
@_='_'=~/$/
# 0 を錬成
__=@_-@_
# 任意の数値を取得する Proc
$_=->_{_[-@_]?(" "+_[-@_]=~/\|/||__)+($_[_[__...-@_]]<<@_):__}
# eval を実行する Proc
$___=->(_,&__){__["",:"#{''<<$_['||..|.|']<<$_['|||.||.']<<$_['||....|']<<$_['||.||..']}",_]}
# eval を実行するための send を実行する Proc
$__=->(_){$___[_,&:"#{''<<$_['|||..||']<<$_['||..|.|']<<$_['||.|||.']<<$_['||..|..']}"]}
# a, b = gets.split.map(&:to_i)
_,__=$__[''<<$_['||..|||']<<$_['||..|.|']<<$_['|||.|..']<<$_['|||..||']<<$_['|.|||.']<<$_['|||..||']<<$_['|||....']<<$_['||.||..']<<$_['||.|..|']<<$_['|||.|..']<<$_['|.|||.']<<$_['||.||.|']<<$_['||....|']<<$_['|||....']<<$_['|.|...']<<$_['|..||.']<<$_['|||.|.']<<$_['|||.|..']<<$_['||.||||']<<$_['|.|||||']<<$_['||.|..|']<<$_['|.|..|']]
# x = a ** B
___=_**__
# y = b ** a
____=__**_
# print x < y ? y : x
$><<((___<____)?(____):___)

余分な空白と改行を取り除く．

@_='_'=~/$/;__=@_-@_;$_=->_{_[-@_]?(" "+_[-@_]=~/\|/||__)+($_[_[__...-@_]]<<@_):__};$___=->(_,&__){__["",:"#{''<<$_['||..|.|']<<$_['|||.||.']<<$_['||....|']<<$_['||.||..']}",_]};$__=->(_){$___[_,&:"#{''<<$_['|||..||']<<$_['||..|.|']<<$_['||.|||.']<<$_['||..|..']}"]};_,__=$__[''<<$_['||..|||']<<$_['||..|.|']<<$_['|||.|..']<<$_['|||..||']<<$_['|.|||.']<<$_['|||..||']<<$_['|||....']<<$_['||.||..']<<$_['||.|..|']<<$_['|||.|..']<<$_['|.|||.']<<$_['||.||.|']<<$_['||....|']<<$_['|||....']<<$_['|.|...']<<$_['|..||.']<<$_['|||.|.']<<$_['|||.|..']<<$_['||.||||']<<$_['|.|||||']<<$_['||.|..|']<<$_['|.|..|']];___=_**__;____=__**_;$><<((___<____)?(____):___)