再帰を使った正規表現で3の倍数を表す (正規表現で FizzBuzz の続き)

PerlやPHPなどの標準の正規表現ライブラリはパターンの再帰をサポートしています(どこまでを正規表現というかはともかくとして)

以下の記事のFizzBuzzを解く話で使った3の倍数を表す正規表現が再帰を使えばスッキリ書けそうだったので試してみました

正規表現でFizzBuzz - 唯物是真 @Scaled_Wurm

上の記事では3の倍数を以下のような正規表現で判定しました

(?:[0369]|[147](?:[0369]|[147][0369]*[258])*(?:[258]|[147][0369]*[147])|[258](?:[0369]|[258][0369]*[147])*(?:[147]|[258][0369]*[258]))+

この正規表現では、3で割ったあまりが0から0に遷移するパターン、0から1に遷移した後なんやかんや遷移してから0に戻るパターン、0から2に遷移した後なんやかんや遷移してから0に戻るパターンのいずれかの繰り返しとして3の倍数を表しています

しかしこの正規表現は一目では少しわかりづらい気がします

そこでパターンの再帰を使うことでより簡潔なパターンを考えます

3の倍数になるような遷移のパターンのうち、途中に冗長なループを含まないパターンとして以下のものが考えられます

• [0369]、3で割ったあまりの遷移が0→0
• [147][147][147]、3で割ったあまりの遷移が0→1→2→0
• [147][258]、3で割ったあまりの遷移が0→1→0
• [258][258][258]、3で割ったあまりの遷移が0→2→1→0
• [258][147]、3で割ったあまりの遷移が0→2→0

3の倍数に3の倍数である部分文字列を付け足したりしても3の倍数であることは変わらないので、これらの前後や途中に3の倍数が含まれる場合の繰り返しを考えれば3の倍数を表せられそうです
再帰を使えば以下のように簡単にかけます
(?1)は一つ目のカッコへの再帰、つまり3の倍数を表しています
([0369]|[147](?1)*[147](?1)*[147]|[147](?1)*[258]|[258](?1)*[147]|[258](?1)*[258](?1)*[258])+

わかりやすくするために改行と空白を入れるとこんな感じです

(
  [0369]
  |[147](?1)*[147](?1)*[147]
  |[147](?1)*[258]
  |[258](?1)*[147]
  |[258](?1)*[258](?1)*[258]
)+

可視化すると結構シンプルな感じになっています

まとめられる部分をまとめて整理すると
([0369]|[147](?1)*(?:[258]|[147](?1)*[147])|[258](?1)*(?:[147]|[258](?1)*[258]))+

というわけでこの正規表現を使って3の倍数だけを列挙できます

seq 1 100000 | perl -ne'print if /^(?>([0369]|[147](?1)*(?:[258]|[147](?1)*[147])|[258](?1)*(?:[147]|[258](?1)*[258])))+$/'

マッチしない場合にバックトラックの数が多くて非常に遅くなるので、上に書いたコマンドでは(?>)を使ってバックトラックしないようにしています

試しにseqコマンドの出力とdiffを取っても差分はないので問題なさそうです
diff <(seq 3 3 100000) <(seq 1 100000 | perl -ne'print if /^(([0369]|[147](?1)*(?:[258]|[147](?1)*[147])|[258](?1)*(?:[147]|[258](?1)*[258])))+$/')

というわけで再帰を使うことで前回使った正規表現よりも短くわかりやすいものにすることができました

この正規表現を使うとFizzBuzzを以前よりも短く書けます
seq 1 100 | perl -pe 's/^(\d*[05])$/$1Buzz/;s/^(?>([0369]|[147](?1)*(?:[258]|[147](?1)*[147])|[258](?1)*(?:[147]|[258](?1)*[258])))+(?=\D)/$1Fizz/;s/^\d+(?=B|F)//'

追記

わかりやすさなどは少し損なわれるような気がしますが、他の箇所も再帰を使うと更に短くなりそうな気がしてきました

3の倍数を表す正規表現は以下のような形になります

(?>([0369]|([147](?1)*)(?:([258](?1)*)|(?2){2})|(?3)(?:(?2)|(?3){2})))+

FizzBuzzは以下のような形
seq 1 10000 | perl -pe 's/^(\d*[05])$/$1Buzz/;s/^(?>([0369]|([147](?1)*)(?:([258](?1)*)|(?2){2})|(?3)(?:(?2)|(?3){2})))+(?=\D)/$1Fizz/;s/^\d+(?=B|F)//'