Lを探す日常

競プロ、ゴルフとか

Rubyの正規表現で加算を判定する

正規表現における「再帰」をご存知でしょうか。一部の正規(自称)表現では再帰的なパターンを定義できるような拡張がなされており、Rubyが使っているOnigmoの正規表現でも再帰の機能が利用できます。この機能は「田中哲スペシャル」と呼ばれて多くの人に愛されているはずなのですが、なぜか2進数の処理に関する記述がググっても見つからなかったので、ここで2進数(と10進数)の足し算について書きたいと思います。


環境: Ruby 2.4.2; (?~)は使ってないから2.3以下でもたぶん動く

changelog:

前提

正規表現or正規表現再帰をご存知ない方は、TSGの昨年の部報id:moratorium08さんの記事(p.5)や、今年の部報の私の記事(p.17)をご参照ください。
Perl正規表現をご存知なら、Perl\k{name}\g{name}Rubyでは\k<name>に、またPerl(?&name)(?P>name)\g<name>になっていると思ってください。

Perl正規表現はとても強力で任意のPerlコードを直接埋め込めるので、

m/^([01]++)\+([01]++)=0*(??{ sprintf "%b", oct("0b".$1) + oct("0b".$2) })$/

と書くことで"0+0=0""10+11=101"にマッチする2進数加算判定の正規表現を作ることができます。
一方Ruby正規表現はそこまで強力ではありません。しかし再帰を使えば、2進数の加算程度なら書くことができます。

本題

次の正規表現をご覧ください*1

ADD = / # A + B = C
  (?<B0> (?= (?<B0Rec> [01] \g<B0Rec> [01] | \+ .*? 0 ) \= )){0}
  (?<B1> (?= (?<B1Rec> [01] \g<B1Rec> [01] | \+ .*? 1 ) \= )){0}
  (?<C0> (?= (?<C0Rec> [01] \g<C0Rec> [01] | \+ .*? 0 ) $ )){0}
  (?<C1> (?= (?<C1Rec> [01] \g<C1Rec> [01] | \+ .*? 1 ) $ )){0}
  (?<Carry0> (?= (?: 1 \g<B0> | 0 \g<B1> )*+ (?: 0 \g<B0> | \+ ))){0}
  (?<Carry1> (?= (?: 1 \g<B0> | 0 \g<B1> )*+ 1 \g<B1> )){0}
  ^
  \g<Carry0>
  (?:
    0 \g<B0> \g<Carry0> \g<C0>
  | 0 \g<B0> \g<Carry1> \g<C1>
  | 0 \g<B1> \g<Carry0> \g<C1>
  | 0 \g<B1> \g<Carry1> \g<C0>
  | 1 \g<B0> \g<Carry0> \g<C1>
  | 1 \g<B0> \g<Carry1> \g<C0>
  | 1 \g<B1> \g<Carry0> \g<C0>
  | 1 \g<B1> \g<Carry1> \g<C1>
  )++
  \+ [01]++ \= [01]++ $ 
/x

これは、入力が"A+B=C"(A,B,Cは全て同じ桁数の2進数)という形式で与えられることを前提として*2、実際に A+B=C になっているときだけマッチする正規表現です。
最初に色々なパターンの定義が入っています。{0}をつけることによってこの時点ではマッチングは行われず、ただ単に後々参照するものを先にまとめて定義しただけになります(参考: プログラミング/ruby/正規表現 - 武内@筑波大)。

同じ位置の桁

(?<B0>),(?<B1>),(?<C0>),(?<C1>)はどれも、Aの i 桁目(以降 A_i )を読み終えたところからスタートしてB,Cの同じ桁、つまり B_iC_i を参照するテクニックを用いています。このテクは部報の「補数」の節にも書きましたがもう一度説明します。
(?<Rec> X \g<Rec> Y | ZZZ )という再帰的なパターンは、"XX…XXZZZYY…YY"という形式の文字列にマッチし、このときXとYの数は等しくなることがわかります。
具体的に(?<Bp>)( p=0,1 )を考えます。Xの直後に"+"が来ることから、Xは A_{i+1} から A_n (ただし n はAの長さ)の n-i 文字です。Yも等しく n-i 文字あり、また︎Yの直後に"="が来ることより、︎Yは B_{i+1} から B_n だとわかります。従ってZの右端は B_i になります。これが p に等しいときマッチします。

繰り上がり

1繰り上がって来る桁は、どこかに1+1という桁(起点)が存在して、その起点から左(上位)に0個以上の1+0(+繰り上がり1)を挟んだところにある桁です。
何の捻りもなく、A_i=1,B_i=0A_i=0,B_i=1 を0個以上読み、その先に起点 A_i=B_i=1 があるかどうかを(?<Bp>)も利用して判定しています。

足し算の判定

A_iB_i、繰り上がりの計3つのパラメータがそれぞれ0か1を取るときの C_i の値を判定すればいいので、2^3=8個のパターンを書いて完成です。

まとめ

この方法を用いると当然10進法の加算もできるのですが、10^2\cdot 2=200通りのパターンを書く部分が煩雑になるのでいい方法がないかなーと悩んでいます。
追記(11/25 0:00) 書きました: add10.rb - Gist
また、部報に書いた通り毎回繰り上がりを判定するのではなく下の位から順に繰り上がりを保持しながら判定していくというのもやってみたいです。良い方法があれば教えてください。
A,B,Cが同じ桁数じゃない場合の処理もすぐ書けそうなので書けたら追記します。
追記(12/10 11:00) 書きました: Rubyの正規表現で足し算 (2) 異なる桁数 - Lを探す日常

宣伝: 今回何度も登場(し|させ)た部報は2017年駒場祭号ですが、まさに現在(2017/11/24-11/26)東大駒場キャンパスにて駒場祭が開催中です! TSGも出展していますので是非ご来場ください*3

それでは、皆さんもよい正規表現ライフを過ごしてください。

*1:空白や#以降のコメントは無視される

*2:つまり形式が異なる場合の動作は未定義

*3:残念ながら私はCODE FESTIVALのためいません