Posted at

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

More than 5 years have passed since last update.

久々に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 );