再帰を使った正規表現で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)//'

正規表現でFizzBuzz

FizzBuzzを正規表現で解きたくなったので解いた
知ってる人が多いと思いますが念のため問題の内容を説明しておくと、入力された整数が3の倍数のときはFizz、5の倍数のときはBuzz、15の倍数のときはFizzBuzz、その他のときは数値をそのまま出力します

• Fizz Buzz - Wikipedia

正規表現

というわけで書いた正規表現のコマンドを以下に書いておきます(seq 1 100は入力の整数列)
seq 1 100 | perl -pe 's/^(\d*[05])$/$1Buzz/;s/^((?:[0369]|[147](?:[0369]|[147][0369]*[258])*(?:[258]|[147][0369]*[147])|[258](?:[0369]|[258][0369]*[147])*(?:[147]|[258][0369]*[258]))+)(?=\D)/$1Fizz/;s/^\d+(?=B|F)//'

簡単に説明

5の倍数

^(\d*[05])$
末尾が0か5ならよいので判定は簡単です

3の倍数

(?:[0369]|[147](?:[0369]|[147][0369]*[258])*(?:[258]|[147][0369]*[147])|[258](?:[0369]|[258][0369]*[147])*(?:[147]|[258][0369]*[258]))+
以下の記事の正規表現を参考にしてほぼそのまま使わせていただきました
d.hatena.ne.jp

上の記事を読んだほうがわかりやすいと思いますが、雑に説明しておきます
ある数の各桁の和が3の倍数であれば、その数は3の倍数であることが知られています
それぞれの数字は3で割ったあまりが0になる数[0369]、1になる数[147]、2になる数[258]に分けることができます
3の倍数は、あまりが0の状態から変化して0の状態に戻るループとなる数字列の繰り返しとして考えることができます
以下の正規表現は。あまりが0から変化しない[0369]、あまりが1増えてから0に戻る[147](?:[0369]|[147][0369]*[258])*(?:[258]|[147][0369]*[147])、あまりが2増えてから0に戻る[258](?:[0369]|[258][0369]*[147])*(?:[147]|[258][0369]*[258])のそれぞれの繰り返しを表しています
わかりやすくするために改行を入れると、以下のそれぞれの3つの行の部位が上で説明した3つの遷移に対応しています

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

可視化したらこんな感じになりました

文字列の置換

というわけで3の倍数と5の倍数が求められるようになったので15の倍数も求めることができるようになっています
後は簡単にコマンドで置換している部分を説明しておきます

一つ目の置換までを適用すると、5の倍数の最後にBuzzが付けられます
s/^(\d*[05])$/$1Buzz/;

1
2
3
4
5Buzz
6
7
8
9
10Buzz
11
12
13
14
15Buzz
16
17
18
19
20Buzz

2つ目の正規表現では、3の倍数の後にFizzを付けます
s/^((?:[0369]|[147](?:[0369]|[147][0369]*[258])*(?:[258]|[147][0369]*[147])|[258](?:[0369]|[258][0369]*[147])*(?:[147]|[258][0369]*[258]))+)(?=\D)/$1Fizz/;

1
2
3Fizz
4
5Buzz
6Fizz
7
8
9Fizz
10Buzz
11
12Fizz
13
14
15FizzBuzz
16
17
18Fizz
19
20Buzz

最後にFizzやBuzzが付いている行の数字を消して終わりです
s/^\d+(?=B|F)//

1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
17
Fizz
19
Buzz

追記

以下の記事で少し正規表現を改良しました
sucrose.hatenablog.com
改良後の正規表現
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)//