Dynamic programming in templates

There is such a wonderful weekend website, like codeeval.com . On which there is a good collection of small algorithmic tasks and a convenient checking system that allows you to spend an interesting evening for bored programmers. As a rule, the file with test data is used as input data. However, I came across one problem in which test data is known in advance. Download a program that will simply display the correct answer is not sports, but to calculate it at the compilation stage - the most it.

What came out of this can be seen inside.

The task itself is not complicated and is very easy to solve recursively. For example, using the following function:

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); } 

And actually getting the result:

 int result = GetRouteCount(1, 0, 1) << 1; 

Now let's try to rotate the same calculations in the templates. As parameters of the template, we need to transfer the "map" of displacements and the coordinates of the current point. Since instead of if specialization will be used, to check for a visit to the point, you need to create a separate template that will have specialization for such a case. If you try to add another parameter to the main template, then unsolvable situations will arise at the compilation stage. The check for a visit will look like this:
')

 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 }; }; 

Now we will create a main template that will have specializations on coordinates that go beyond the grid and checks that the destination has been reached:

 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 }; }; 

So, the result is almost as succinct as in the calculation variant in runtime:

 int result = MapRoute<0, 0, 0>::value; 

You can view the entire code and the result of its execution by following the link .