コンパイル時 逆fizzbuzz [C++]
巷で噂の逆fizzbuzz問題です。
http://d.hatena.ne.jp/matarillo/20120515/p1
コンパイル時に解けるようにテンプレート引数として<fizz,buzz,fizz,fizz...>といった物を与えるとfizzbuzzにおいてそれを生成する最小の数列を要素として持つsprout::array型のオブジェクトを得るメタ関数を作ってみました。
テンプレート引数として扱えるようにfizz,buzz,fizzbuzzにはそれぞれ整数値の0,1,2を割り当てて処理しています。
ありえないパターンbuzz,buzz...などは全要素を0としたsprout::arrayを返します。
static_assertで軽く動作チェックをしてみただけなので、もしかするとバグがあるかもしれませんので参考程度に…。
constexpr内でも副作用は使っていないので、C++11(C++14である必要はない)で動作します。
#include <type_traits> #include <boost/mpl/vector_c.hpp> #include <boost/mpl/at.hpp> #include <sprout/array.hpp> #include <sprout/index_tuple.hpp> namespace mpl = boost::mpl; namespace ifzbz { static constexpr auto fizz = 0; static constexpr auto buzz = 1; static constexpr auto fizzbuzz = 2; using base = mpl::vector_c<std::size_t, fizz, buzz, fizz, fizz, buzz, fizz, fizzbuzz>; template<std::size_t first, std::size_t last, std::size_t step = 0, bool finish = step >= last, std::size_t... args> struct circulate { using type = mpl::vector_c<std::size_t, args...>; }; template<std::size_t first, std::size_t last, std::size_t step, std::size_t... args> struct circulate<first, last, step, false, args...> : circulate<first, last, step + 1, first + step >= last, args..., mpl::at_c<base, (first + step) % 7>::type::value> {}; template<sprout::index_t... indexes> constexpr sprout::array<std::size_t, sizeof...(indexes)> make_result(sprout::index_tuple<indexes...>) { return sprout::array<std::size_t, sizeof...(indexes)>{{static_cast<std::size_t>(indexes)...}}; } constexpr std::size_t calc_sum(const std::size_t& n, const std::size_t& size, const std::size_t& step = 0, const std::size_t& result = 0) { return step >= size ? result : (n + step) % 7 == 0 ? calc_sum(n, size, step + 1, result + 2) : (n + step) % 7 == 1 ? calc_sum(n, size, step + 1, result + 1) : (n + step) % 7 == 2 ? calc_sum(n, size, step + 1, result + 3) : (n + step) % 7 == 3 ? calc_sum(n, size, step + 1, result + 1) : (n + step) % 7 == 4 ? calc_sum(n, size, step + 1, result + 2) : (n + step) % 7 == 5 ? calc_sum(n, size, step + 1, result + 3) : calc_sum(n, size, step + 1, result + 3) ; } template<std::size_t... args> struct inverse_fizzbuzz { static constexpr auto value = sprout::array<std::size_t, sizeof...(args)>{{}}; }; template<> struct inverse_fizzbuzz<fizz> { static constexpr auto value = sprout::array<std::size_t, 1>{{3}}; }; template<std::size_t... args> struct inverse_fizzbuzz<fizz, fizz, args...> { static constexpr auto value = std::is_same< typename circulate<2, sizeof...(args) + 2 + 1>::type, mpl::vector_c<std::size_t, fizz, fizz, args...> >::value ? make_result(typename sprout::index_range<6, calc_sum(6, sizeof...(args)) + 9 + 1>::type()) : decltype(make_result(typename sprout::index_range<6, calc_sum(6, sizeof...(args)) + 9 + 1>::type())){{}} ; }; template<> struct inverse_fizzbuzz<fizz, buzz> { static constexpr auto value = sprout::array<std::size_t, 2>{{3, 5}}; }; template<> struct inverse_fizzbuzz<fizz, buzz, fizz> { static constexpr auto value = sprout::array<std::size_t, 3>{{3, 5, 6}}; }; template<std::size_t... args> struct inverse_fizzbuzz<fizz, buzz, fizz, fizz, args...> { static constexpr auto value = std::is_same< typename circulate<0, sizeof...(args) + 0 + 3>::type, mpl::vector_c<std::size_t, fizz, buzz, fizz, fizz, args...> >::value ? make_result(typename sprout::index_range<3, calc_sum(3, sizeof...(args)) + 9 + 1>::type()) : decltype(make_result(typename sprout::index_range<3, calc_sum(3, sizeof...(args)) + 9 + 1>::type())){{}} ; }; template<std::size_t... args> struct inverse_fizzbuzz<fizz, buzz, fizz, fizzbuzz, args...> { static constexpr auto value = std::is_same< typename circulate<3, sizeof...(args) + 3 + 3>::type, mpl::vector_c<std::size_t, fizz, buzz, fizz, fizzbuzz, args...> >::value ? make_result(typename sprout::index_range<9, calc_sum(6, sizeof...(args)) + 15 + 1>::type()) : decltype(make_result(typename sprout::index_range<9, calc_sum(6, sizeof...(args)) + 15 + 1>::type())){{}} ; }; template<std::size_t... args> struct inverse_fizzbuzz<fizz, fizzbuzz, args...> { static constexpr auto value = std::is_same< typename circulate<5, sizeof...(args) + 5 + 1>::type, mpl::vector_c<std::size_t, fizz, fizzbuzz, args...> >::value ? make_result(typename sprout::index_range<12, calc_sum(6, sizeof...(args)) + 15 + 1>::type()) : decltype(make_result(typename sprout::index_range<12, calc_sum(6, sizeof...(args)) + 15 + 1>::type())){{}} ; }; template<> struct inverse_fizzbuzz<buzz> { static constexpr auto value = sprout::array<std::size_t, 1>{{5}}; }; template<> struct inverse_fizzbuzz<buzz, fizz> { static constexpr auto value = sprout::array<std::size_t, 2>{{5, 6}}; }; template<std::size_t... args> struct inverse_fizzbuzz<buzz, fizz, fizz, args...> { static constexpr auto value = std::is_same< typename circulate<1, sizeof...(args) + 1 + 2>::type, mpl::vector_c<std::size_t, buzz, fizz, fizz, args...> >::value ? make_result(typename sprout::index_range<5, calc_sum(3, sizeof...(args)) + 9 + 1>::type()) : decltype(make_result(typename sprout::index_range<5, calc_sum(3, sizeof...(args)) + 9 + 1>::type())){{}} ; }; template<std::size_t... args> struct inverse_fizzbuzz<buzz, fizz, fizzbuzz, args...> { static constexpr auto value = std::is_same< typename circulate<4, sizeof...(args) + 4 + 2>::type, mpl::vector_c<std::size_t, buzz, fizz, fizzbuzz, args...> >::value ? make_result(typename sprout::index_range<10, calc_sum(6, sizeof...(args)) + 15 + 1>::type()) : decltype(make_result(typename sprout::index_range<10, calc_sum(6, sizeof...(args)) + 15 + 1>::type())){{}} ; }; template<std::size_t... args> struct inverse_fizzbuzz<fizzbuzz, args...> { static constexpr auto value = std::is_same< typename circulate<6, sizeof...(args) + 6 + 0>::type, mpl::vector_c<std::size_t, fizzbuzz, args...> >::value ? make_result(typename sprout::index_range<15, calc_sum(6, sizeof...(args)) + 15 + 1>::type()) : decltype(make_result(typename sprout::index_range<15, calc_sum(6, sizeof...(args)) + 15 + 1>::type())){{}} ; }; } int main() { using namespace ifzbz; static_assert(inverse_fizzbuzz<buzz,fizz,fizz>::value == sprout::array<std::size_t, 5>{{5,6,7,8,9}}, ""); static_assert(inverse_fizzbuzz<fizz,buzz,fizz,fizz,buzz,fizz,fizzbuzz,fizz,buzz>::value == sprout::array<std::size_t, 18>{{3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}}, ""); static_assert(inverse_fizzbuzz<buzz,buzz>::value == sprout::array<std::size_t, 2>{{0,0}}, ""); // impossible case }
TMPは処理途中の状態を確認する事が難しいので、デバッグには若干苦労しましたが、なんとかなりました。
逆fizzbuzz自体を解いた事が無かったゆえ方針があまり賢いとは言えなさそうです。
改良の余地はいくらでもあると思います。
それにしてもboost.mplとsproutは素晴らしいライブラリですね。
追記
rangeだけで良いようなのでrangeをsprout::pairとして返すようにしてみました。
若干コード減りますね。
#include <type_traits> #include <boost/mpl/vector_c.hpp> #include <boost/mpl/at.hpp> #include <sprout/utility/pair.hpp> namespace mpl = boost::mpl; namespace ifzbz { static constexpr auto fizz = 0; static constexpr auto buzz = 1; static constexpr auto fizzbuzz = 2; using base = mpl::vector_c<std::size_t, fizz, buzz, fizz, fizz, buzz, fizz, fizzbuzz>; template<std::size_t first, std::size_t last, std::size_t step = 0, bool finish = step >= last, std::size_t... args> struct circulate { using type = mpl::vector_c<std::size_t, args...>; }; template<std::size_t first, std::size_t last, std::size_t step, std::size_t... args> struct circulate<first, last, step, false, args...> : circulate<first, last, step + 1, first + step >= last, args..., mpl::at_c<base, (first + step) % 7>::type::value> {}; constexpr std::size_t calc_sum(const std::size_t& n, const std::size_t& size, const std::size_t& step = 0, const std::size_t& result = 0) { return step >= size ? result : (n + step) % 7 == 0 ? calc_sum(n, size, step + 1, result + 2) : (n + step) % 7 == 1 ? calc_sum(n, size, step + 1, result + 1) : (n + step) % 7 == 2 ? calc_sum(n, size, step + 1, result + 3) : (n + step) % 7 == 3 ? calc_sum(n, size, step + 1, result + 1) : (n + step) % 7 == 4 ? calc_sum(n, size, step + 1, result + 2) : (n + step) % 7 == 5 ? calc_sum(n, size, step + 1, result + 3) : calc_sum(n, size, step + 1, result + 3) ; } template<std::size_t... args> struct inverse_fizzbuzz { static constexpr auto value = sprout::pair<std::size_t, std::size_t>(0, 0); }; template<> struct inverse_fizzbuzz<fizz> { static constexpr auto value = sprout::pair<std::size_t, std::size_t>(3, 3); }; template<std::size_t... args> struct inverse_fizzbuzz<fizz, fizz, args...> { static constexpr auto value = std::is_same< typename circulate<2, sizeof...(args) + 2 + 1>::type, mpl::vector_c<std::size_t, fizz, fizz, args...> >::value ? sprout::pair<std::size_t, std::size_t>(6, calc_sum(6, sizeof...(args)) + 9) : sprout::pair<std::size_t, std::size_t>(0, 0) ; }; template<> struct inverse_fizzbuzz<fizz, buzz> { static constexpr auto value = sprout::pair<std::size_t, std::size_t>(3, 5); }; template<> struct inverse_fizzbuzz<fizz, buzz, fizz> { static constexpr auto value = sprout::pair<std::size_t, std::size_t>(3, 6); }; template<std::size_t... args> struct inverse_fizzbuzz<fizz, buzz, fizz, fizz, args...> { static constexpr auto value = std::is_same< typename circulate<0, sizeof...(args) + 0 + 3>::type, mpl::vector_c<std::size_t, fizz, buzz, fizz, fizz, args...> >::value ? sprout::pair<std::size_t, std::size_t>(3, calc_sum(3, sizeof...(args)) + 9) : sprout::pair<std::size_t, std::size_t>(0, 0) ; }; template<std::size_t... args> struct inverse_fizzbuzz<fizz, buzz, fizz, fizzbuzz, args...> { static constexpr auto value = std::is_same< typename circulate<3, sizeof...(args) + 3 + 3>::type, mpl::vector_c<std::size_t, fizz, buzz, fizz, fizzbuzz, args...> >::value ? sprout::pair<std::size_t, std::size_t>(6, calc_sum(6, sizeof...(args)) + 15) : sprout::pair<std::size_t, std::size_t>(0, 0) ; }; template<std::size_t... args> struct inverse_fizzbuzz<fizz, fizzbuzz, args...> { static constexpr auto value = std::is_same< typename circulate<5, sizeof...(args) + 5 + 1>::type, mpl::vector_c<std::size_t, fizz, fizzbuzz, args...> >::value ? sprout::pair<std::size_t, std::size_t>(12, calc_sum(6, sizeof...(args)) + 15) : sprout::pair<std::size_t, std::size_t>(0, 0) ; }; template<> struct inverse_fizzbuzz<buzz> { static constexpr auto value = sprout::pair<std::size_t, std::size_t>(5, 5); }; template<> struct inverse_fizzbuzz<buzz, fizz> { static constexpr auto value = sprout::pair<std::size_t, std::size_t>(5, 6); }; template<std::size_t... args> struct inverse_fizzbuzz<buzz, fizz, fizz, args...> { static constexpr auto value = std::is_same< typename circulate<1, sizeof...(args) + 1 + 2>::type, mpl::vector_c<std::size_t, buzz, fizz, fizz, args...> >::value ? sprout::pair<std::size_t, std::size_t>(5, calc_sum(3, sizeof...(args)) + 9) : sprout::pair<std::size_t, std::size_t>(0, 0) ; }; template<std::size_t... args> struct inverse_fizzbuzz<buzz, fizz, fizzbuzz, args...> { static constexpr auto value = std::is_same< typename circulate<4, sizeof...(args) + 4 + 2>::type, mpl::vector_c<std::size_t, buzz, fizz, fizzbuzz, args...> >::value ? sprout::pair<std::size_t, std::size_t>(10, calc_sum(6, sizeof...(args)) + 15) : sprout::pair<std::size_t, std::size_t>(0, 0) ; }; template<std::size_t... args> struct inverse_fizzbuzz<fizzbuzz, args...> { static constexpr auto value = std::is_same< typename circulate<6, sizeof...(args) + 6 + 0>::type, mpl::vector_c<std::size_t, fizzbuzz, args...> >::value ? sprout::pair<std::size_t, std::size_t>(15, calc_sum(6, sizeof...(args)) + 15) : sprout::pair<std::size_t, std::size_t>(0, 0) ; }; } int main() { using namespace ifzbz; static_assert(inverse_fizzbuzz<buzz,fizz,fizz>::value == sprout::pair<std::size_t, std::size_t>(5, 9), ""); static_assert(inverse_fizzbuzz<fizz,buzz,fizz,fizz,buzz,fizz,fizzbuzz,fizz,buzz>::value == sprout::pair<std::size_t, std::size_t>(3, 20), ""); static_assert(inverse_fizzbuzz<buzz,buzz>::value == sprout::pair<std::size_t, std::size_t>(0, 0), ""); // impossible case static_assert(inverse_fizzbuzz<buzz,fizzbuzz>::value == sprout::pair<std::size_t, std::size_t>(0, 0), ""); // impossible case static_assert(inverse_fizzbuzz<buzz,fizz,fizz,buzz,buzz>::value == sprout::pair<std::size_t, std::size_t>(0, 0), ""); // impossible case }