FizzBuzz問題

本記事では、プログラミングにおけるアルゴリズムの定番問題である「FizzBuzz問題」について解説します。

1. FizzBuzz問題の定義

まずFizzBuzz問題が何かを定義しておきます。 FizzBuzz問題のルールはいたって単純で、1から任意の整数 $N$ までの数値を順に出力する時、以下の規則に従って数値を文字列に変換します。

FizzBuzz問題のルール

1. 3の倍数である場合は、数値の代わりに “Fizz” と出力する。
2. 5の倍数である場合は、数値の代わりに “Buzz” と出力する。
3. 3の倍数かつ5の倍数（すなわち15の倍数）である場合は、数値の代わりに “FizzBuzz” と出力する。
4. 上記のいずれの条件も満たさない場合は、数値をそのまま出力する。

1から15までを出力する場合、特に最後の15番目で両方の条件が重なり、"FizzBuzz" という出力が現れることになります。

2. 条件分岐内での優先順位

それでは実際に解いてみましょう。

ルール通りに if 文を上から順番に書いていけば、簡単に実装できそうじゃないですか？

実は、条件を並べる順番を誤ると、意図しない挙動になってしまいます。

例えば、Pythonで以下のような順序で条件分岐を組んだとします。

for i in range(1, 16):
    if i % 3 == 0:
        print("Fizz")
    elif i % 5 == 0:
        print("Buzz")
    elif i % 15 == 0:
        print("FizzBuzz")
    else:
        print(i)

一見するとルールをすべて網羅しているように見えますが、このプログラムを実行して 15 に到達したとき、期待される “FizzBuzz” ではなく “Fizz” が出力されてしまいます。

15は3の倍数でもあるから、最初の if の条件に引っかかって、下の elif まで辿り着かないですね。

集合の包含関係において、より限定的な条件を先に判定しなければ、広い条件に吸収されてしまいます。

数学的に考えると、3の倍数の集合を $A$、5の倍数の集合を $B$ としたとき、15の倍数は共通部分 $A \cap B$ です。 Pythonの if-elif-else 構文は「真になったブロックを実行した時点でそれ以降の判定をスキップする」という性質を持つため、最も狭い範囲である $A \cap B$ の判定を最優先に行う必要があります。

3. 正しい実装例

それでは正しい実装例をいくつか紹介します。前半2つは標準的でぜひ押さえておきたい考え方です。後半2つも、少しトリッキーですが勉強になる考え方です。

(実装例1)：15の倍数の判定を最優先する

最も直感的かつ標準的なやりかたとして、共通部分である15の倍数の判定を先頭に配置する構成です。

for i in range(1, 16):
    if i % 15 == 0:
        print("FizzBuzz")
    elif i % 3 == 0:
        print("Fizz")
    elif i % 5 == 0:
        print("Buzz")
    else:
        print(i)

(実装例2)：文字列の結合を利用する

もう一つのやりかたは、条件を独立させて文字列の結合を利用する方法です。この方法であれば、15の倍数という条件をわざわざ書く必要がなくなります。

for i in range(1, 16):
    output = ""

    if i % 3 == 0:
        output += "Fizz"
    if i % 5 == 0:
        output += "Buzz"

    print(output or i)

これなら、15のときに “Fizz” と “Buzz” が順番に足されて自動的に “FizzBuzz” になります。最後の print(output or i) はどういう意味ですか？

Pythonでは、空文字列 "" は False とみなされます。そのため、どの倍数でもなく output が空のときは、or 演算子によって右側の数値 i が採用されて出力される仕組みです。これによってルールに引っかからない数値をそのまま返しています。

なるほど。実装例２のほうが少しスマートなやり方に感じられますね。

(実装例3)：条件文なしの解法

さらにコードをスマートに、かつ極限まで短くする方法として、Pythonの文字列スライスの仕様を逆手に取った、条件分岐を一切使わない記述方法があります。

for i in range(1, 16):
    print("Fizz"[i % 3 * 4 :] + "Buzz"[i % 5 * 4 :] or i)

短いですね…これで本当に FizzBuzz が動くんですか？

これは、Pythonのスライスの仕組みを利用したコードです。

ポイントは “Fizz”[i % 3 * 4 :]の部分です。Pythonでは、スライスの開始インデックスが文字列の長さを超えていると、エラーにならずに空文字列 "" を返す仕様（スライスハック）があります。

• i が3の倍数のとき： i % 3 は 0 になるため “Fizz”[0:]となり、“Fizz” がそのまま残ります。
• i が3の倍数でないとき： i % 3 は 1 か 2 になります。それを4倍すると 4 か 8 です。 “Fizz”は4文字しか存在しないため、4文字目以降をスライスしようとすると空文字列 "" になります。

これを “Buzz”でも同時に行い、最後に or i でルールに引っかからない数字に対応しています。

(実装例4)：リストの周期性を利用した割り算の演算を使わない解法

3の倍数と5の倍数は、15番周期で同じパターンを繰り返すという最小公倍数の周期性を利用すれば、ループの中で毎回 i % 3 などの割り算をする必要がなくなります。

pattern = [
    "", "", "Fizz", "", "Buzz",
    "Fizz", "", "", "Fizz", "Buzz",
    "", "Fizz", "", "", "FizzBuzz"
]

for i in range(1, 16):
    print(pattern[(i - 1) % 15] or i)

なるほど、あらかじめ15番目までの答えの型を作っておいて、周期性にそろえて返すということですね。

その通りです。これはルックアップテーブル（照合表）と呼ばれる手法で、実行時の計算コストを下げる方法の1つです。

ループが回るたびに (i - 1) % 15 を計算することで、配列のインデックスが 0, 1, 2 ... 14, 0, 1 ... と綺麗にループします。該当する要素が空文字列 "" であれば、やはり or i の評価によってその数値がそのまま出力されます。

まとめ

FizzBuzz問題は単純な問題ですが、多角的な視点からこの問題を解いていくことで、様々な力を身に着けられる良問といえるでしょう。