第23回オフラインリアルタイムどう書く を C++のテンプレート で解く

久々にC++テンプレートプログラミングに挑戦してみました。

お題はこちらです。

C++で別解

まず鍋谷さんの解答を参考にC++でもう一度書いたもの。

#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>

int get_length(const std::string& values, int pos, int lengths[])
{
    if(std::isdigit(values[pos]) && (lengths[pos] == 0))
    {
        int l[] =
        {
            (values[pos] < values[pos - 6]) ? get_length(values, pos - 6, lengths) : 0,
            (values[pos] < values[pos + 6]) ? get_length(values, pos + 6, lengths) : 0,
            (values[pos] < values[pos - 1]) ? get_length(values, pos - 1, lengths) : 0,
            (values[pos] < values[pos + 1]) ? get_length(values, pos + 1, lengths) : 0
        };

        lengths[pos] = *std::max_element(std::begin(l), std::end(l)) + 1;
    }

    return lengths[pos];
}

std::string solve(const std::string& input)
{
    std::string source = std::string(6, '/') + input + std::string(6, '/');

    int lengths[36] = {};
    for(int pos = 0; pos < 36; ++pos)
    {
        get_length(source, pos, lengths);
    }

    std::ostringstream oss;
    oss << *std::max_element(std::begin(lengths), std::end(lengths));

    return oss.str();
}

void test(const std::string& input, const std::string& expected)
{
    std::string actual = solve(input);
    if(expected == actual)
    {
        std::cout << "." << std::flush;
    }
    else
    {
        std::cout << "\ninput: " << input << ", expected: " << expected << ", acutal: " << actual << std::endl;
    }
}

int main(int argc, char* argv[])
{
    /*0*/ test( "01224/82925/69076/32298/21065", "6" );
    /*1*/ test( "03478/12569/03478/12569/03478", "10" );
    /*2*/ test( "09900/28127/87036/76545/87650", "10" );
    /*3*/ test( "77777/77777/77777/77777/77777", "1" );
    /* ... */
    /*50*/ test( "02489/77571/84873/03879/84460", "7" );

    std::cout << std::endl;

    return 0;
}

C++のテンプレートで書く

これをふまえて。
C++のテンプレートで書き直してみます。
実行環境はC++コンパイラです。「コンパイルが通る」がすなわち「テストにパスした」ことになります。
久々のテンプレートプログラミングとはいえ、脇が甘い感じ。

template<bool F, typename T, typename U> struct If;
template<typename T, typename U> struct If<true,  T, U> { static const int value = T::value; };
template<typename T, typename U> struct If<false, T, U> { static const int value = U::value; };

template<typename T, typename U>
struct Max
{
    static const int value = If<(T::value > U::value), T, U>::value;
};

struct Zero { static const int value = 0; };

template<int N>
struct Table
{
    constexpr static char chr(int n);
};

template<int N, int POS, char C>
struct Length
{
    static const int value = Max<
        Max<
            If<
                Table<N>::chr(POS) < Table<N>::chr(POS - 6),
                Length<N, POS - 6, Table<N>::chr(POS - 6)>,
                Zero
            >,
            If<
                Table<N>::chr(POS) < Table<N>::chr(POS + 6),
                Length<N, POS + 6, Table<N>::chr(POS + 6)>,
                Zero
            >
        >,
        Max<
            If<
                Table<N>::chr(POS) < Table<N>::chr(POS - 1),
                Length<N, POS - 1, Table<N>::chr(POS - 1)>,
                Zero
            >,
            If<
                Table<N>::chr(POS) < Table<N>::chr(POS + 1),
                Length<N, POS + 1, Table<N>::chr(POS + 1)>,
                Zero
            >
        >
    >::value + 1;
};

template<int N, int POS>
struct Length<N, POS, '/'>
{
    static const int value = 0;
};

template<int N, int POS = 35>
struct Solve
{
    static const int value = Max<
        Length<N, POS, Table<N>::chr(POS)>,
        Solve<N, POS - 1>
    >::value;
};

template<int N>
struct Solve<N, -1>
{
    static const int value = 0;
};

template<int M, int N> struct Assert;
template<int N> struct Assert<N, N> {};

#define TEST(N, S, E) \
template<> constexpr char Table<N>::chr(int n) { return ("//////" S "//////")[n]; } \
Assert<E, Solve<N>::value> assert##N

TEST(  0, "01224/82925/69076/32298/21065",  6 );
TEST(  1, "03478/12569/03478/12569/03478", 10 );
TEST(  2, "09900/28127/87036/76545/87650", 10 );
/* ... */
TEST( 50, "02489/77571/84873/03879/84460",  7 );