Blogの生存報告がてら。
ちょっと旬の過ぎた話題ですが、逆FizzBuzz問題をC++で、自分なりにがんばってオブジェクト指向っぽく解いてみます。
逆FizzBuzz問題
FizzBuzzゲームは英語圏での定番飲み会用ゲームで、日本で言うナベアツゲームみたいなものです。
ルールは各人が1から順に数を言っていき、3の倍数のときには数字の代わりにFizz、5の倍数のときにはBuzz、3かつ5の倍数のときにはFizzBuzzを言うというものです。
具体的にはこうなります: 1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, …
プログラミング界隈では初歩的なコーディング問題として、相手が本当にプログラミングができるのかどうかを知る問題として使われるそうです。(現場で本当に使われているのかは知りません。)
さて、逆FizzBuzz問題というのは、これに関連した問題の逆問題として定義されます。
まず、1からでなく適当な数字から始め、さらに数字を言わないFizzBuzz問題を考えます。
例えば25から始めるとすると、25はBuzz、26は飛ばす、27はFizz、28は飛ばす、29は飛ばす、30はFizzBuzz、… となり、この結果はBuzz, Fizz, FizzBuzz, … となります。
これの逆問題を考えます。つまり、FizzやBuzzやFizzBuzzの羅列でできた文字列が与えられたとき、結果がそれに一致するような数列を求めたい、それを逆FizzBuzz問題と定義します。
それだけだと答えが複数あるので、今回はその中で最小の数列の最も小さい数から始まるものを答えとしましょう。
具体的な問題例とその答えは以下のようになります。
- “Fizz”なら3
- “Fizz, Buzz”なら9,10 (3,4,5より短い)
- “FizzBuzz”なら15
- “FizzBuzz, Fizz”なら15, 16, 17, 18
より詳しくは元ネタを和訳されている以下のリンクを参照してください:
逆FizzBuzz問題 (Inverse FizzBuzz) – 猫とC#について書くmatarilloの雑記
オブジェクト指向で逆FizzBuzz問題
ここからプログラミングの話題。
先に挙げたリンク先(とさらにその先の英語原文)では、オブジェクト指向プログラミングがプログラマーに滅びをもたらす思想であると認定され、代わりに関数型プログラミングが広く認められた近未来で逆FizzBuzz問題を解くお話になっています。
まあ、オブジェクト指向が悪であるかどうかは議論を避けるとして、ここでは2016年になってもやっぱりオブジェクト指向は世の中を支配していた、そしてその世界で逆FizzBuzz問題もオブジェクト指向のノリで解く必要に迫られたらどうなるのかをやってみた、という内容になります。(そもそも私は関数型プログラミングをきちんと勉強していない人なので、善悪の議論ができません。)
言語は例によってC++11です。だいたい次のように決めておきます。
- 出力は逆FizzBuzz問題の解の数列の範囲。例:”Fizz Buzz” → “[3,5]”
- 入力が空文字のときは[0,0]を返す。
- 解がないときは適当に文句を返す。
先にソースコードを書いてしまいましょう。
#include <iostream>
#include <vector>
#include <sstream>
#include <algorithm>
const int fbNum = 7;
const int fbCycle = 15;
class fbTest{
static const std::vector<std::string> fbString;
static const std::vector<int> fbInt;
int start, current;
bool alive;
public:
constexpr fbTest(int _start):start(_start), current(_start-1), alive(true){}
bool isAlive() const{ return alive; }
int startInt() const{ return current<start ? 0 : fbInt[start]; }
int endInt() const{ return current<start ? 0 : fbCycle*(current/fbNum)+fbInt[current%fbNum]; }
void next(const std::string& nextfb){
current++;
if(fbString[current%fbNum]!=nextfb) alive = false;
}
};
decltype(fbTest::fbString) fbTest::fbString = {"Fizz","Buzz","Fizz","Fizz","Buzz","Fizz","FizzBuzz"};
decltype(fbTest::fbInt) fbTest::fbInt = {3,5,6,9,10,12,15};
int main(int argc, char** argv){
std::stringstream ss(argv[1]);
std::string elem;
std::vector<fbTest> fbTestArr = {0,1,2,3,4,5,6,7};
while(ss >> elem) for(auto& it : fbTestArr) it.next(elem);
std::stable_sort(fbTestArr.begin(), fbTestArr.end(), [](const fbTest& lv, const fbTest& rv){return (lv.endInt()-lv.startInt())<(rv.endInt()-rv.startInt());});
const auto it_suit = std::find_if(fbTestArr.begin(), fbTestArr.end(), [](const fbTest& fbt){return fbt.isAlive();});
if(it_suit == fbTestArr.end()) std::cout << "No Solution..." << std::endl;
else std::cout << "[" << it_suit->startInt() << "," << it_suit->endInt() << "]" << std::endl;
return 0;
}
説明
FizzBuzz問題は3と5の公倍数の15ごとに繰り返すので、数字を抜いたFizzBuzz問題は7つ置きに同じ言葉を繰り返すことがわかります。
そうなると出発点のバリエーションはせいぜい7種類しかないわけです。そのため、7種類の出発点について与えられた文字列が最後まで問題ないかどうかを調べればよいことになります。
ここでは指定した出発点から文字列(FizzとかBuzzとか)を次々に与えて、その出発点で題意を満たすか逐一確認していくクラスを用意しました。このクラスを全ての出発点(7種類)だけ生成して、全てに文字列を順次与えていき最後まで生き残ったものを解としています。
どうせ7つで1周するので、検査の際に長大な文字列は用意せず7種類の文字列をぐるぐる巡回するようにしてあります。長大なFizzBuzz文を生成して比較、としないのは言語というより性格の問題でしょうか?
このクラスは内部状態を持ち、副作用のあるメンバ関数まで持ちます。これらを見ただけで吐き気を催すような方々がいましたら悪いことをしたと思います。
実行例
いろいろ試してみました。検索して見つかる様々な方の先行例には入力に上限を設けているものも見られましたが、上記のものは余程のことがなければ大丈夫のはずです。
$./test "" [0,0] $./test "Fizz Buzz" [9,10] $./test "Fizz Buzz Fizz Fizz" [3,9] $./test "FizzBuzz Fizz Buzz Fizz" [15,21] $./test "FizzBuzz Fizz Buzz Fizz Buzz" No Solution... $./test "FizzBuzz Fizz Buzz Fizz Fizz Buzz Fizz FizzBuzz Fizz Buzz Fizz Fizz Buzz Fizz" [15,42] $./test "FizzBuzz Fizz Buzz Fizz Fizz Buzz Fizz ...(長いので省略)... Fizz Buzz Fizz Fizz Buzz Fizz" [15,6492]
元気に動いています。
参考
constexpr 逆FizzBuzz – ボレロ村上 – ENiyGmaA Code
「コンパイル時に」逆FizzBuzz問題を解いてしまったものです。文字列とセットでコンパイラに渡すとコンパイル後(実行前)にはもう結果が求まっています。すごい。
頭の体操みたいな問題ですが、順(?)FizzBuzz問題と違って、言語や思想など人によってアプローチの仕方が変わる問題だと思います。
ところで、FizzBuzz問題の”Fizz”と”Buzz”ってどういうニュアンスなんでしょう。日本語で言うと…「しゅー」「わー」みたいなものでしょうか? 「1、2、しゅー、4、わー、しゅー、7、…」
んー、気の抜けたゲームになりそう。