Lを探す日常

競プロ、ゴルフとか

Rubyの正規表現で足し算 (2) 異なる桁数

この記事はTSG Advent Calendar 2017の10日目です。昨日の記事は id:gasin さんの[null]でした。TSGでは(特に1年生の)新入部員を募集しています。

さて、TSGの先輩方と雑談しているときに出てきた「正規表現で2進数を扱ったりして遊ぶ」という話題を発展させて、正規表現で足し算の式が正しいか判定することについて考えます。
先日の記事「Rubyの正規表現で加算を判定する (1)」では次のようなRuby正規表現を書きました:

ADD2 =~ "1+0=1"
ADD2 =~ "011+001=100"
ADD2 !~ "1+1=0"

ADD10 =~ "1+1=2"
ADD10 =~ "486+001=487"
ADD10 !~ "123+456=789"

二進、十進それぞれ2番目の例において、数の先頭に余分な0が付いています。これは前回紹介した正規表現に「A,B,Cは全て同じ桁数」という制約があったためです。
今回の目標は、この不自然な制約を、「数の先頭に余分な0が付いていない*1」という(自然な)制約に変えて*2自然な形式の足し算を判定する正規表現を作ることです。

※完成したものはGistにあります


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

ふりかえり

前回の記事では次のようなことを言いました。

  • 正規表現再帰を用いることで、(各iについて)A[i]を読み終えた位置から、先読みでちょうどB[i]C[i]を参照する正規表現が書ける。
  • これを用いて、繰り上がりを判定する正規表現をゴリゴリ書く。
  • これらを組み合わせることで足し算の判定ができる。

これを踏まえて、次のようなコードを紹介しました*3*4

ADD2 = /
  (?<B0> (?= (?<a> \d \g<a> \d | \+ \d*? 0 ) \= )){0}
  (?<B1> (?= (?<b> \d \g<b> \d | \+ \d*? 1 ) \= )){0}
  (?<C0> (?= (?<c> \d \g<c> \d | \+ \d++ \= \d*? 0 ) $ )){0}
  (?<C1> (?= (?<d> \d \g<d> \d | \+ \d++ \= \d*? 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の桁数(それぞれX,Y,Zとする)の大小で場合分けし、個別に考えます。

(0) A = 0B = 0のとき

こうなるのはA + 0 = A及び0 + B = Bのみです。

(I) Y <= X = Z のとき

例: 100+1=101
この場合、基本的にチェックする内容は(前回の記事の)同桁数の場合と同じです。ただし、BY桁目以上は「0」と見なすようにします。そうすることで、A[i]+B[i]=C[i]の形式を崩さずに判定できます。

(II) Y <= X < Zのとき

例: 1+1=101100+111=10111
この条件を満たすのは、Z = X + 1で、Cの最高位の1がA + Bの繰り上がりの1となっているときです。
同桁数の場合は「必ず0」としていた最高位の繰り上がりの判定を、場合によって\g<Carry0>\g<Carry1>で使い分ける必要があります。

(III,IV) X < Y <= Zのとき

例: 1+101=110101+1010=1111101+1110=10011
まず、(I)と同様に「Bの最高位より上に0が続いていると見なす」パターンが必要です。
Bの上位Y - X桁(Dとする)」と「Cの上位Z - X桁(E)」に注目します。対応するAの桁が「0」と見なせることより、E - Dは0または(繰り上がりの)1です。

(III) E - D = 0のとき

X桁目の繰り上がりは0です。
X < Yのチェックの際に、Dをキャプチャします。これをX < Zのチェックの際にそのまま用います。

(IV) E - D = 1のとき

X桁目の繰り上がりは1です。
この場合インクリメント判定(TSG部報 p.18)を利用できます。ただし、インクリメント判定のうち「左辺や右辺の終端」で判定していたところを、「BCの終端」ではなく「DEの終端」にする必要があります。そのために、「B,Cの下位X桁(それぞれF,Gとする)」をキャプチャして、「Dの終端からはFと『=』が続く」、「Eの終端からはGが続いて文字列終端に達する」という風に判定します。

実装

Y <= X, Z = X, Z = X+1, Z = Y, Z = Y+1を判定する正規表現*5:

/
  (?<YleX>  (?= (?<e> \d \g<e> \d | \d*+ \+ ) \=     )){0}
  (?<ZeqX>  (?= (?<f> \d \g<f> \d | \+ \d++ \=   ) $ )){0}
  (?<ZeqSX> (?= (?<g> \d \g<g> \d | \+ \d++ \= 1 ) $ )){0}
  (?<ZeqY>  (?= (?<h> \d \g<h> \d |         \=   ) $ )){0}
  (?<ZeqSY> (?= (?<i> \d \g<i> \d |         \= 1 ) $ )){0}
/x

※ただしグループ名の中の"S"は"Succ"、つまり+ 1を表す。

(I)等で言及した「Bの最高位より上に0が続いていると見なす」書き方:

old: / (?<B0> (?= (?<a> \d \g<a> \d | \+ \d*? 0           ) \= )){0} /x
new: / (?<B0> (?= (?<a> \d \g<a> \d | \+ \d*? 0 | \d*+ \+ ) \= )){0} /x

(III)、(IV)で用いる、D,E,F,Gをキャプチャする正規表現:

/
  (?<GetD> (?= (?<j> \d \g<j> \d | \+         (?<D> \d+ ) (?= (?<F> \d*+))) \= )){0}
  (?<GetE> (?= (?<k> \d \g<k> \d | \+ \d++ \= (?<E> \d+ ) (?= (?<G> \d*+))) $ )){0}
/x

(III)のE = D正規表現:

/ (?<EeqD> \g<GetD> (?= (?<l> \d \g<l> \d | \+ \d++ \= \k<D> ) $ )){0} /x

(IV)のE = D + 1正規表現:

/
  (?<EeqSD> \g<GetD> \g<GetE>
    (?= (?<m> \d \g<m> \d | \+ (?= # increment
        \g<ZeqSY>
        (?<n> 1 \g<n> 0 | \k<F> \= 1 ) \k<G> $
      | \g<ZeqY>
        (?<DECommon> (?: (?<DI> \d) (?=
          (?<o> \d \g<o> \d | \k<F> \= \d*? \k<DI> ) \k<G> $
        ))*+)
        0 (?<p> 1 \g<p> 0 | \k<F> \= \k<DECommon> 1 ) \k<G> $
    ) \d*? ) \= )
  ){0}
/x

最上位の繰り上げ判定も含めた、(I)〜(IV)の場合分け:

/
  (?: \g<YleX> \g<ZeqX> \g<Carry0> # I
    | \g<YleX> \g<ZeqSX> \g<Carry1> # II
    | \g<EeqD> \g<Carry0> # III
    | \g<EeqSD> \g<Carry1> # IV
  )
/x

まとめ

これらを全て結合させると、このようになります。
長い正規表現となってしまいましたが、任意の桁数に対応する、自然な足し算を判定する正規表現が書けました!!

正規表現を書いていて、「Bの桁が足りないときは簡単なのに対して、どうしてAの桁が足りないときはここまで煩雑になってしまうんだ……」と思いました。Ruby正規表現後読みが任意の長さに対応していれば簡単なのですが……
ともかく、これで無事完成です。今後の展望orやりたいこととしては、

  • Aの桁が足りないときも簡単に書けるような方法を探す
  • 計算量を解析したり(少なくとも \mathcal{O}(Z^4) はあるっぽい)、より効率の良い正規表現を探す
  • かけ算!! やりたい

といった感じです。出来るのでしょうか?

アドベントカレンダーを埋めるのは大変ですね。ということで明日は[未定]さんの[null]でお送りします!

*1:非零の数は「1」から始まる

*2:逆に01+01=10のような文字列は受け付けない

*3:ほんのちょっとだけ変更しています。

*4:グループ名のうち、小文字の"a"から"d"は再帰のためのマーカーであり、意味はありません。

*5:以降も同様に、小文字一文字のグループ名は再帰のマーカーであり特に意味はない。

広告を非表示にする