FizzBuzz化ストリーム - yohhoyの日記（別館）

インターネット上で定期的に話題にのぼる「FizzBuzz問題」を、C++言語で変な風に解いてみたというお話。

今ではすっかり有名になったFizzBuzz問題ですが、元々はJeff Atwood氏による2007年の記事Why Can't Programmers.. Program?（青木靖氏による日本語訳）が初出のようです。ルールをおさらいしておくと、次の仕様を満たすプログラムを作れという問題ですね。

1から100までの数をプリントするプログラムを書け。ただし3の倍数のときは数の代わりに「Fizz」と、5の倍数のときは「Buzz」とプリントし、3と5両方の倍数の場合には「FizzBuzz」とプリントすること。

困ったときのおまじない

FizzBuzz問題はあまりにも有名なため、Web検索すればいくらでも実装コード例が見つかります。いまさら普通に解いてもしょうがない（？）ので、C++標準ライブラリI/Oストリームを利用して非侵襲的(nonintrusive)な解法をとりたいと思います。

つまり、オリジナルのこんなコードに対して：

#include <iostream>
const int N = 16;

// 1...Nまでの数字を出力
template <class OutputStream>
void countup(OutputStream& os)
{
  for (int i = 1; i <= N; ++i)
    os << i << os.widen(' ');
  os << std::endl;
}
 
int main()
{
  // countup()関数を呼ぶ
  countup(std::cout);
}
// 出力結果：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

標準出力ストリームstd::coutに小細工をすると…

int main()
{
  fizzbuzznizer fb(std::cout);  // おまじない

  // 先ほどと同じcountup()関数を呼ぶだけ
  countup(std::cout);
}
// 出力結果：
// 1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz 16

元の出力処理(countup関数)には一切手を加えずに（＝非侵襲的）、ちゃんとFizzBuzz問題が解けました。

ちなみにこの“おまじない”、出力処理側のコードには依存しないので：

fizzbuzznizer fb(std::cout);  // おまじない

// 出力が文字列でもOK
std::cout << "seq={1 2 3 4 5 6...}";
  // 出力結果：seq={1 2 Fizz 4 Buzz Fizz...}

// Boost.Formatとの組み合わせもOK
#include <boost/format.hpp>
std::cout << boost::format("%1% and %2%, %3%") % 1 % 42 % 105;
  // 出力結果：1 and Fizz, FizzBuzz

また出力ストリーム（std::ostream派生クラス）を対象として、こんなことも：

#include <sstream>
std::ostringstream oss;
fizzbuzznizer fb(oss);  // おまじないをossにふりかける

// ostringstreamでもいけるよ
oss << 6 << "/10";
assert(oss.str() == "Fizz/Buzz");

C++万歳！I/Oストリーム万歳！

タネ明かし

先ほど使った怪しい“おまじない”は、下記コードで実現されます。
実装の概略：

basic_fizzbuzznizer：対象出力ストリームオブジェクトのストリームバッファを、下記basic_fizzbuzz_streambufに差し替える。
basic_fizzbuzz_streambuf：対象ストリームオブジェクトから渡されてくる文字に対してFizzBuzz化を行い、結果を元ストリームバッファに転送する。
ジェネリックな記述によりwchar_t等にも（無駄に）対応。

basic_fizzbuzznizerクラステンプレート

同オブジェクトの変数スコープにあわせて、対象出力ストリームオブジェクト（std::coutなど）のストリームバッファを置換／復元するヘルパクラスです。

通常は「std::cout → {coutのストリームバッファ}」のようになっている関連付けを、コンストラクタにて「std::cout → basic_fizzbuzz_streambuf → {coutのストリームバッファ}」のように差し替え、またデストラクタでは関連付けを元に戻しています。

basic_fizzbuzz_streambufクラステンプレート

実際にFizzBuzz化処理を行う、std::basic_streambufから派生するストリームバッファクラスです。basic_fizzbuzz_streambufは一般的なストリームバッファと異なり、ストリームクラスから渡されてくる文字を変換（FizzBuzz化）するだけで、本当の“出力”処理は元のストリームバッファへ委譲します。

さて、FizzBuzz問題における倍数判定は「数値」に対して行う必要がありますが、残念ながらストリームバッファで受け取れるデータは「文字」シーケンスだけです。これは前段のストリームオブジェクトで整形(format)された結果であり、I/Oストリームライブラリ設計に起因しています。

ただ幸いなことに必要な倍数判定は3と5のため、次の代替判定アルゴリズムを利用できます。また、与えられた「文字」シーケンスに対して、“数字で構成される部分シーケンス”を「数値」として解釈することにします。

3の倍数＝各桁の数値の合計値が3の倍数
5の倍数＝最下位桁が0または5

以上をもとに、basic_fizzbuzz_streambuf各メンバ関数では次の処理を行います。

コンストラクタ: 元ストリームバッファを保持し(sb_)、自身の出力領域(put area)サイズを0に設定する(setp(0, 0))。これにより、1文字受け取るたびにoverflow()が呼び出されるようになる。
overflowオーバーライド: 出力領域があふれる＝ストリームバッファへ1文字入力された時に呼び出される。入力が“数字”であれば一時バッファ(tb_)で追加保持し、3の倍数判定準備(acc3_)と5の倍数判定(mul5_)を行う。数字以外の場合はそのまま元ストリームバッファへ転送する(sb_.sputc(c))。
syncオーバーライド: フラッシュ要求がなされた時に呼び出される。倍数判定結果に応じて出力文字列を決定し、putn()ヘルパ関数を経由して元ストリームバッファへ流し込む(sb_.sputc(...))。

fizzbuzznizer

仕上げに、C++標準ライブラリ風のchar／wchar_t用typedefを準備して完成です。

typedef basic_fizzbuzznizer<char> fizzbuzznizer;
typedef basic_fizzbuzznizer<wchar_t> wfizzbuzznizer;