ボレロ村上 - ENiyGmaA Code

中３女子です。

constexpr 逆FizzBuzz

中３女子です。


最近 Twitter で逆FizzBuzzが話題に上っていたので、constexpr で実装してみることにした。
なお、自分はこれまで逆FizzBuuz を実装したことはない。
どうやら様々なアプローチがあるらしいが、折角なので何も見ずに一から方法を検討することにする。

仕様・要件

逆FizzBuzz の内容は、概ね以下である。

  • Fizz, Buzz, FizzBuzz の文字列からなる配列を入力とする。
  • 上記を生成するような FizzBuzz問題に対する入力値の範囲のうち、最初かつ最短のものを求める。
  • 例：
input : Fizz FizzBuzz Fizz Buzz
answer: (12,20)


まずは仕様を決めてしまおう。
answer を求める関数 inv_fizzbuzz を以下のように定義することとした。

template<typename ForwardRange>
constexpr sprout::pair<int, int>
inv_fizzbuzz(ForwardRange const& rng);


要件は次の通りとする。

  • 返値は (始端,終端) のペア
    • ただし、空の範囲または不正な FizzBuzz列の場合は (0,0) を返す
  • 入力は ForwardRange
    • ただし要素の型は sprout::string と等値比較可能でなければならない

コード

解説は後に回すとして、先に解答を示す。

#include <sprout/array.hpp>
#include <sprout/string.hpp>
#include <sprout/utility.hpp>
#include <sprout/container.hpp>
#include <sprout/range.hpp>
#include <sprout/range/algorithm.hpp>
#include <sprout/range/adaptor.hpp>

static constexpr auto token_table = sprout::to_string_array<sprout::string<8> >(
    "Fizz", "Buzz", "Fizz", "Fizz", "Buzz", "Fizz", "FizzBuzz",
    "Fizz", "Buzz", "Fizz", "Fizz", "Buzz", "Fizz"
    );
static constexpr auto index_table = sprout::make_array<int>(
    3, 5, 6, 9, 10, 12, 15,
    18, 20, 21, 24, 25, 27
    );

template<typename ForwardRange, typename Difference>
constexpr sprout::pair<int, int>
inv_fizzbuzz_impl(ForwardRange const& rng, Difference found) {
    return found == sprout::size(token_table) ? sprout::pair<int, int>{0, 0}
        : sprout::pair<int, int>{
            index_table[found],
            sprout::size(rng) / 7 * 15 + index_table[found + sprout::size(rng) % 7 - 1]
            }
        ;
}
template<typename ForwardRange>
constexpr sprout::pair<int, int>
inv_fizzbuzz(ForwardRange const& rng) {
    return sprout::size(rng) <= 7
        || (sprout::size(sprout::range::find_end<sprout::range::return_found_end>(rng, rng | sprout::adaptors::taken(7))) == 7 + sprout::size(rng) % 7
            && sprout::range::equal(
                rng | sprout::adaptors::taken(sprout::size(rng) % 7),
                rng | sprout::adaptors::dropped(sprout::size(rng) - sprout::size(rng) % 7)
                )
            )
        ? inv_fizzbuzz_impl(
            rng,
            sprout::size(sprout::range::search<sprout::range::return_begin_found>(token_table, rng | sprout::adaptors::taken(7)))
            )
        : sprout::pair<int, int>{0, 0}
        ;
}

解説

まず、FizzBuzz列の性質を考える。

Fizz Buzz Fizz Fizz Buzz Fizz FizzBuzz
Fizz Buzz Fizz Fizz Buzz Fizz FizzBuzz
Fizz Buzz Fizz Fizz Buzz Fizz FizzBuzz
...

見てのとおり、FizzBuzz列は最小公倍数である 15 の範囲（要素数にして 7）で循環している。


このことから、任意の正しい FizzBuzz列の部分について、以下のことが言える。

  1. いかなるFizzBuzz列も、7 要素の循環である
  2. いかなるFizzBuzz列も、最初の 7 要素（Fizz Buzz Fizz Fizz Buzz Fizz FizzBuzz）のうちいずれかから開始する
テーブルを用意する

すなわち、入力から高々 7 要素を取り出して、最初の 7 要素のどこから開始するかを調べれば、始端を求めることができる。
最後の FizzBuzz が始端の場合は高々 13 要素までを調べる必要があるので、

table: Fizz Buzz Fizz Fizz Buzz Fizz FizzBuzz Fizz Buzz Fizz Fizz Buzz Fizz
input:                               FizzBuzz Fizz Buzz Fizz Fizz Buzz Fizz

最初から数えて 13 要素までのテーブルを用意すればよい。

static constexpr auto token_table = sprout::to_string_array<sprout::string<8> >(
    "Fizz", "Buzz", "Fizz", "Fizz", "Buzz", "Fizz", "FizzBuzz",
    "Fizz", "Buzz", "Fizz", "Fizz", "Buzz", "Fizz"
    );
static constexpr auto index_table = sprout::make_array<int>(
    3, 5, 6, 9, 10, 12, 15,
    18, 20, 21, 24, 25, 27
    );
高々 7 要素を検索

シーケンスからサブシーケンスを検索するには search アルゴリズムを使えばよい。
また、シーケンスから高々 n 要素を取り出すには taken アダプタを使う。

sprout::size(sprout::range::search<sprout::range::return_begin_found>(token_table, rng | sprout::adaptors::taken(7)))


ちなみに、Sprout の Rangeアルゴリズムのうち検索用アルゴリズムは、明示的テンプレート引数で返値をカスタマイズすることができる。

  • sprout::range::return_found - 発見位置のイテレータを返す（デフォルト）
  • sprout::range::return_found_end - [発見位置,end) の範囲を返す
  • sprout::range::return_begin_found - [begin,発見位置) の範囲を返す

例えば返値を [発見位置,end) とすれば、「発見したかどうか」を返値が空かどうかで判定できるし、
[begin,発見位置) とすれば、「発見位置のインデックス」を返値のサイズから求めることができる。


よって、始端はここから直接算出できる。

index_table[found]

終端の方は、循環数に 15 を掛けて、剰余部分を足してやればよい。

sprout::size(rng) / 7 * 15 + index_table[found + sprout::size(rng) % 7 - 1]


もし入力がテーブルと一致しなかった場合は、不正な FizzBuzz列ということなので (0,0) を返す。

found == sprout::size(token_table) ? sprout::pair<int, int>{0, 0}
不正な循環のチェック

入力が不正な FizzBuzz列でないかどうかのチェックは、もう一つ付け加える必要がある。
つまり、入力が正しく循環しているかチェックしなければならない。


入力が 7 要素以下である場合は当然正しい。

sprout::size(rng) <= 7


7 要素より大きい場合、まず find_end アルゴリズムの返値が、ちょうど剰余を除いた最後の 7 要素の位置かどうかで判定する。

sprout::size(sprout::range::find_end<sprout::range::return_found_end>(rng, rng | sprout::adaptors::taken(7))) == 7 + sprout::size(rng) % 7

つまり、以下のようになればよい。

input: Fizz Buzz Fizz Fizz Buzz Fizz FizzBuzz Fizz Buzz Fizz Fizz Buzz Fizz FizzBuzz Fizz Buzz
taken:                                       [Fizz Buzz Fizz Fizz Buzz Fizz FizzBuzz]
                                              ^

また、剰余の部分が一致するかどうかを判定する。

sprout::range::equal(
    rng | sprout::adaptors::taken(sprout::size(rng) % 7),
    rng | sprout::adaptors::dropped(sprout::size(rng) - sprout::size(rng) % 7)
    )

input  : Fizz Buzz Fizz Fizz Buzz Fizz FizzBuzz Fizz Buzz Fizz Fizz Buzz Fizz FizzBuzz Fizz Buzz
dropped:                                                                              [Fizz Buzz]

これらが真でなかった場合、正しく循環していないということなので (0,0) を返す。

テスト

さて、正しく実装できているかテストしてみる。

#include <iostream>

template<typename ForwardRange, typename Pair>
void print(ForwardRange const& input, Pair const& answer) {
    std::cout << "input : ";
    for (auto const& e : input) {
        std::cout << e << ' ';
    }
    std::cout << std::endl;
    std::cout << "answer: (" << answer.first << ',' << answer.second << ')' << std::endl;
}

int main() {
    {
        constexpr auto input = sprout::to_string_array<sprout::string<8> >(
            "Fizz", "FizzBuzz", "Fizz", "Buzz"
            );
        constexpr auto answer = inv_fizzbuzz(input);

        static_assert(answer.first == 12 && answer.second == 20, "answer is (12,20)");
        print(input, answer);
    }
    {
        constexpr auto input = sprout::to_string_array<sprout::string<8> >(
            "FizzBuzz", "Fizz", "Buzz", "Fizz", "Fizz", "Buzz", "Fizz",
            "FizzBuzz", "Fizz", "Buzz", "Fizz", "Fizz", "Buzz", "Fizz",
            "FizzBuzz", "Fizz", "Buzz"
            );
        constexpr auto answer = inv_fizzbuzz(input);

        static_assert(answer.first == 15 && answer.second == 50, "answer is (15,50)");
        print(input, answer);
    }
    {
        constexpr auto input = sprout::to_string_array<sprout::string<8> >(
            "Fizz", "FizzBuzz", "Buzz"
            );
        constexpr auto answer = inv_fizzbuzz(input);

        static_assert(answer.first == 0 && answer.second == 0, "answer is (0,0)");
        print(input, answer);
    }
}

出力：

input : Fizz FizzBuzz Fizz Buzz
answer: (12,20)
input : FizzBuzz Fizz Buzz Fizz Fizz Buzz Fizz FizzBuzz Fizz Buzz Fizz Fizz Buzz Fizz FizzBuzz Fizz Buzz
answer: (15,50)
input : Fizz FizzBuzz Buzz
answer: (0,0)

どうやら正しく動作しているようだ。
constexpr であるので、当然 answer はコンパイル時に計算されている。

感想

Sprout の既存のアルゴリズムをそのまま活用できたので、実装にさほど困難はなかった。
テーブルを使った実装は個人的にあまり好みでないが、シンプルさでいえばこれがベターだと思う。


おそらく他の言語であれば、まったく別のアプローチの実装にもなりうるのだろう。
言語やパラダイムやプログラマ個人の考え方など、各々の特徴が出るという意味で逆FizzBuzz は良い問題ではないかと思う。


どうせなので、今回のコードを Sprout の example にも追加しておいた。
https://github.com/bolero-MURAKAMI/Sprout/blob/master/example/inv_fizzbuzz/main.cpp