Динамическое программирование в шаблонах

Есть такой чудный сайт выходного дня, как codeeval.com ^[1]. На котором неплохая коллекция небольших алгоритмических задачек и удобная система проверки, позволяющая занимательно провести вечер скучающим программистам. Как правило в качестве входных данных используется файл с тестовыми данными. Однако мне попалась одна задача ^[2], в которой тестовые данные известны заранее. Загружать программу, которая будет просто выводить правильный ответ не спортивно, а вот вычислять его на этапе компиляции — самое то.

Что из этого получилось можно посмотреть внутри.

Задача сама по себе не сложная и рекурсивно решается очень просто. Например с помощью вот такой вот функции:

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;

Посмотреть весь код и результат его выполнения можно пройдя по ссылке ^[3].

Автор: Ation

Источник ^[4]