正規表現を使って FizzBuzz

この記事は、FizzBuzz の書き方がわからない初心者の方のための解説記事……ではなく、正規表現に苦しむ駆け出しプログラマーを応援する記事……でもなく、くだらなくて面白い FizzBuzz の書き方を追求する記事です。

---

FizzBuzz の条件分岐には普通、剰余を用いますが、それを完全に正規表現で置き換えたバージョンを作るのが、この記事の目的です。

まず、正規表現で 3 の倍数・5 の倍数を表す方法を考えます。(以下、数値は全て十進法とします。)

5 の倍数

これは簡単ですね。一の位が 0 か 5 なら 5 の倍数です。

\d*[05]

3 の倍数

こちらは一筋縄ではいきそうにありません。

取っ掛かりとして、3 の倍数を次のように分割してみましょう。

• 上の位から順に区切っていく
• 各部分ができる限り小さな 3 の倍数になるようにする

(例)

123456           → 12 3 45 6
11202201         → 11202 201
3275910026414877 → 3 27 591 0 0 264 14877

こうしてできる各部分全てにマッチする正規表現を A とすると、3 の倍数全体を表す正規表現は A+ と書けます。

補足

3 の倍数は全て、上の方法で 1 つ以上の 3 の倍数に分割することができます。 3 の倍数から 3 の倍数を引いた結果は必ず 3 の倍数になるので、3 で割り切れなくなることはありません。

123456 = 12 * 10000 + 3 * 1000 + 45 * 10 + 6

逆に、3 の倍数を並べると 3 の倍数ができるのも明らかです。

---

早速 A に取り掛かりたいところですが、もう少し簡略化します。

3 の倍数の判定にあたって重要なのは 3 で割った余りなので、数字 [0-9] は [0369]/[147]/[258] に分けることができます。これを 0/1/2 で (代表して) 表すことにします。

状態遷移図

さて、ここからが本題です。正規表現 A を求めるにあたって、次のような状態遷移図を使います。

丸数字は状態を表していて、矢印は入力に対してどの状態に遷移するかを示します。入力は、上の桁の数字から順に読まれるものとします。

記号	状態
⓪	初期状態 (まだ文字を読んでいない)
①	3 で割って 1 余る
②	3 で割って 2 余る
③	受容状態 (3 の倍数にマッチした)

上の図では、状態①と②を相互に行き来できるので、このままの形で正規表現に変換することはできません。そこで、状態③の直前にどの状態にあるのかで場合分けします。

⓪→③

⓪から③への遷移は、書き換える必要はありません。

①→③

①から③への遷移は、途中で②を経由する場合があります。これを②を使わない形に変換します。順を追って見ていきましょう。

図	説明
	①に初めて到達するまでの経路は、 ⓪→① ⓪→②→②→…→②→①
	入力をまとめて、⓪から直接遷移するように書き換える
	①から出て①に戻る経路は、 ①→① ①→②→①→…→②→①
	②を通らないように書き換える

②→③

②から③への遷移も、同様に変換します。

図	説明
	②に初めて到達するまでの経路は、 ⓪→② ⓪→①→①→…→①→②
	入力をまとめて、⓪から直接遷移するように書き換える
	②から出て②に戻る経路は、 ②→② ②→①→②→…→①→②
	①を通らないように書き換える

正規表現

上の変換の結果、状態遷移図は以下のようになります。

単純な分岐と繰り返しだけになったので、正規表現で表すことができます。

0|(1|20*2)(0|10*2)*2|(2|10*1)(0|20*1)*1

これの数字 0/1/2 を [0369]/[147]/[258] でそれぞれ置き換えたものが、正規表現 A です。

結果として、3 の倍数全体にマッチする正規表現は次のようになります¹。

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

……長いですね。3 の倍数を検索しなければならないけど正規表現しか使えないような特殊な状況に陥った際に、是非ご利用ください。

FizzBuzz

道具は全て出揃いました。コードを書き始めましょう。以下のような形になるのが理想です。

for (let i = 1; i <= 100; ++i) {
   console.log(i.toString().replace(/* ... */))
}

15 の倍数は、3 の倍数と後読みを使えば良さそうです。また、キャプチャを利用することで、どのパターンにマッチしたかを知ることができます。

一度の replace で済ますには、正規表現に一工夫が必要です。

^
(?:
   # 3 の倍数を判定
   (?:[0369]|(?:[147]|[258][0369]*[258])(?:[0369]|[147][0369]*[258])*[258]|(?:[258]|[147][0369]*[147])(?:[0369]|[258][0369]*[147])*[147])+
|
   # 5 の倍数を判定
   \d*[05]
   # (3 の倍数でない) かつ (5 の倍数) のとき、空文字列をキャプチャ (f)
   ()
)
(?:
   # 5 の倍数のとき、何もしない
   (?<=[05])
|
   # (3 の倍数) かつ (5 の倍数でない) とき、空文字列をキャプチャ (b)
   ()
)
$

これによって、全てのパターンを判別できます。

	置換の有無	f	b
(3 の倍数) かつ (5 の倍数)	○	undefined	undefined
(3 の倍数) かつ (5 の倍数でない)	○	undefined	""
(3 の倍数でない) かつ (5 の倍数)	○	""	undefined
(3 の倍数でない) かつ (5 の倍数でない)	×	―	―

あとは undefined を Fizz/Buzz に置き換えれば OK です²。

// f と b の少なくとも一方は undefined なので、空文字列にはならない
(f ?? "Fizz") + (b ?? "Buzz")

完成したコードはこちらになります。

for (let i = 1; i <= 100; ++i) {
   console.log(
      i.toString().replace(
         /^(?:(?:[0369]|(?:[147]|[258][0369]*[258])(?:[0369]|[147][0369]*[258])*[258]|(?:[258]|[147][0369]*[147])(?:[0369]|[258][0369]*[147])*[147])+|\d*[05]())(?:(?<=[05])|())$/,
         (_, f, b) => (f ?? "Fizz") + (b ?? "Buzz")
      )
   )
}

---

いかがでしたか。FizzBuzz も正規表現も、奥が深いですね。

ところで、Number.prototype.toString は、引数で基数を指定できるのですが、なぜ私はそれを使わなかったのでしょうか³……

1. 導出の方法によっては、他の正規表現が得られます。 ↩

2. String.prototype.replace の 2 番目の引数には関数を使うことができます。色々カスタマイズできるので便利です。 ↩

3. 正規表現を使う場合、絶対に 15 進数の方が楽だと思います。 ↩