Есть такой чудный сайт выходного дня, как codeeval.com. На котором неплохая коллекция небольших алгоритмических задачек и удобная система проверки, позволяющая занимательно провести вечер скучающим программистам. Как правило в качестве входных данных используется файл с тестовыми данными. Однако мне попалась одна задача, в которой тестовые данные известны заранее. Загружать программу, которая будет просто выводить правильный ответ не спортивно, а вот вычислять его на этапе компиляции — самое то.
Что из этого получилось можно посмотреть внутри.
Задача сама по себе не сложная и рекурсивно решается очень просто. Например с помощью вот такой вот функции:
int GetRouteCount(int map, int x, int y) {
if ((x == -1) || (y == -1) || (x == 4) || (y == 4)) return 0;
if ((x == 3) && ( y == 3)) return 1;
if ( ( map & (1 << ( ( x << 2) +y) )) != 0 ) return 0;
map |= (1 << ( (x << 2) +y));
return GetRouteCount(map, x-1, y) +
GetRouteCount(map, x+1, y) +
GetRouteCount(map, x, y-1) +
GetRouteCount(map, x, y+1);
}
И собственно получение результата:
int result = GetRouteCount(1, 0, 1) << 1;
Теперь попробуем провернуть эти же вычисления в шаблонах. Как параметры шаблона нам надо передавать «карту» перемещений и координаты текущей точки. Так как вместо if будет использоваться специализация, то для проверки на посещение точки надо создать отдельный шаблон, у которого будет специализация на такой случай. Если попытаться добавить еще один параметр в основной шаблон, то возникнут неразрешимые ситуации на этапе компиляции. Выглядеть проверка на посещение будет вот так:
template< template<int, int, int> class _MR, int map, int x, int y, bool visited>
struct GetCount {
enum Result
{
value = _MR<(map | (1 << ( ( x << 2) +y ))), (x-1), y>::value +
_MR<(map | (1 << ( ( x << 2) +y ))), (x+1), y>::value +
_MR<(map | (1 << ( ( x << 2) +y ))), x, (y-1)>::value +
_MR<(map | (1 << ( ( x << 2) +y ))), x, (y+1)>::value
};
};
template< template<int, int, int> class _MR, int map, int x, int y>
struct GetCount<_MR, map, x, y, true> {
enum Result { value = 0 };
};
Теперь создадим основной шаблон, который будет иметь специализации по координатам, которые выходят за пределы сетки и проверяет, что достигнута точка назначения:
template <int map, int x, int y>
struct MapRoute {
enum Result { value = GetCount<MapRoute, map, x, y, ( (map & ( 1 << ( (x << 2) +y))) != 0 )>::value };
};
template<int map, int y>
struct MapRoute<map, -1, y> {
enum Result { value = 0 };
};
template<int map, int y>
struct MapRoute<map, 4, y> {
enum Result { value = 0 };
};
template<int map, int x>
struct MapRoute<map, x, -1> {
enum Result { value = 0 };
};
template<int map, int x>
struct MapRoute<map, x, 4> {
enum Result { value = 0 };
};
template<int map>
struct MapRoute<map, 3, 3> {
enum Result { value = 1 };
};
Вот и готово, получение результата выглядит почти так же лаконично, как и в варианте вычисления в рантайме:
int result = MapRoute<0, 0, 0>::value;
Посмотреть весь код и результат его выполнения можно пройдя по ссылке.
Автор: Ation
