Rubyの正規表現で足し算 (2) 異なる桁数
この記事はTSG Advent Calendar 2017の10日目です。昨日の記事は id:gasin さんの SECCONにゆるふわ参加してみた話 - gasin’s blog でした。TSGでは(特に1年生の)新入部員を募集しています。
gasin.hatenadiary.jp
さて、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以下でもたぶん動く。
更新履歴:
- 2018/12/06 アドベントカレンダーの記事へのリンクを追加
ふりかえり
前回の記事では次のようなことを言いました。
- 正規表現の再帰を用いることで、(各
iについて)A[i]を読み終えた位置から、先読みでちょうどB[i]やC[i]を参照する正規表現が書ける。 - これを用いて、繰り上がりを判定する正規表現をゴリゴリ書く。
- これらを組み合わせることで足し算の判定ができる。
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 = 0やB = 0のとき
こうなるのはA + 0 = A及び0 + B = Bのみです。
(I) Y <= X = Z のとき
例: 100+1=101
この場合、基本的にチェックする内容は(前回の記事の)同桁数の場合と同じです。ただし、BのY桁目以上は「0」と見なすようにします。そうすることで、A[i]+B[i]=C[i]の形式を崩さずに判定できます。
(II) Y <= X < Zのとき
例: 1+1=10、1100+111=10111。
この条件を満たすのは、Z = X + 1で、Cの最高位の1がA + Bの繰り上がりの1となっているときです。
同桁数の場合は「必ず0」としていた最高位の繰り上がりの判定を、場合によって\g<Carry0>と\g<Carry1>で使い分ける必要があります。
(III,IV) X < Y <= Zのとき
例: 1+101=110、101+1010=1111、101+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)を利用できます。ただし、インクリメント判定のうち「左辺や右辺の終端」で判定していたところを、「BやCの終端」ではなく「DやEの終端」にする必要があります。そのために、「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の桁が足りないときも簡単に書けるような方法を探す
- 計算量を解析したり(少なくとも
はあるっぽい)、より効率の良い正規表現を探す
- かけ算!! やりたい
といった感じです。出来るのでしょうか?
アドベントカレンダーを埋めるのは大変ですね。ということで明日はhakatashiさんの SECCON 2017 Quals Writeup - z80, SHA-1 is dead, Qubic Rube - 博多電光 でお送りします！
hakatashi.hatenadiary.com
