// ////////////////////////////////////////////////////////
// # Title
// Robot Walks
//
// # URL
// https://projecteuler.net/problem=208
// http://euler.stephan-brumme.com/208/
//
// # Problem
// A robot moves in a series of one-fifth circular arcs (72°), with a free choice of a clockwise or an anticlockwise arc for each step, but no turning on the spot.
//
// One of 70932 possible closed paths of 25 arcs starting northward is
//
// ![path](p208_robotwalk.gif)
//
// Given that the robot starts facing North, how many journeys of 70 arcs in length can it take that return it, after the final arc, to its starting position?
// (Any arc may be traversed multiple times.)
//
// # Solved by
// Stephan Brumme
// November 2017
//
// # Algorithm
// I played around with a 3rd party graphics library and tried to brute force the solution for 25 arcs:
// - I set up rotation matrices
// - need to adjust the allowed error to fix floating-point issues
// - and had tons of other problems
// Nevertheless, my program found those 70932 paths.
//
// More interesting is that I analyzed all paths with 5,6,7,...,25 arcs (obviously you need at least 5 arcs; I didn't analyze longer paths):
// - there are only solutions for 5,10,15,20 and 25 arcs, that means the path length must be a multiple of 5
// - the number of arcs "leaning left" is always a multiple of 5
// - the number of arcs "leaning right" is always a multiple of 5
//
// Loosely speaking, each path consists only of full circles where the single parts are arbitrarily interleaved.
// For example: 25 arcs means I have 5 full circles, some clockwise and some anti-clockwise, and these parts of the circle are connected in a "random" way.
//
// The fascinating result of these observations: I don't need matrices at all - all I need is "counting" arcs !
// - the path always starts with arc 0
// - in each step I increment a counter in ''numVisited[currentArc]''
// - if the path turns left then I continue with the next arc (current arc plus 1 in modulo 5 ==> arc 1)
// - if the path turns right then I continue with the previous arc (current arc minus 1 in modulo 5 ==> arc -1 ==> arc 4)
//
// The same configurations of counters are repeatedly observed on different paths, so I can memoize them.
// The whole state consists of these five counters plus the current arc.
// I can merge these numbers into a single integer ''id'' and store it in a container ''cache''.
//
// Whenever I finish a path, all counters must have the same value.
// If the first four value are identical then the fifth must be, too.
// Instead of comparing the first four counters one-by-one I compare the first and second, the third and fourth and then the first and third.
// This way I save one comparison (it's somehow like binary search):
// "slow": ''numVisited[0] == numVisited[1] && numVisited[1] == numVisited[2] && numVisited[2] == numVisited[3] && numVisited[3] == numVisited[4]''
// "fast": ''numVisited[0] == numVisited[1] && numVisited[3] == numVisited[4] && numVisited[1] == numVisited[3]''
// ==> actually my code does the opposite thing because it want to detect those "failed" paths.
//
// # Note
// My initial version of the algorithm stored the memoized results in a hash-map.
// An ''std::vector'' is always faster at the cost of higher memory consumption, so I replaced it (see ''#define FAST'').
// I was surprised to see that the ''std::vector'' consumes actually 10% __less__ memory while being 6 times faster.
#include
#include
#include
unsigned char numVisited[5] = { 0,0,0,0,0 };
unsigned char maxPerArc = 0;
#define FAST
#ifdef FAST
const auto Unknown = 0xFFFFFFFFFFFFFFFFull;
std::vector cache;
#else
std::unordered_map cache;
#endif
// count number of valid arcs
unsigned long long search(unsigned char arcsLeft = 70, unsigned char currentArc = 0)
{
// all arcs were used
if (arcsLeft == 0)
{
// did not return to initial arc ?
if (currentArc != 0)
return 0;
// expect that all arcs were visited equally often
if (numVisited[0] != numVisited[1] ||
numVisited[2] != numVisited[3] ||
numVisited[0] != numVisited[2]) // no need to check visited[4]
return 0;
return 1;
}
// create a unique key
const auto IdFactor = maxPerArc + 1;
unsigned int id = currentArc;
id *= IdFactor;
id += numVisited[0];
id *= IdFactor;
id += numVisited[1];
id *= IdFactor;
id += numVisited[2];
id *= IdFactor;
id += numVisited[3];
id *= IdFactor;
id += numVisited[4];
// memoize
#ifdef FAST
if (cache.empty())
cache.resize(5 * IdFactor * IdFactor * IdFactor * IdFactor * IdFactor, Unknown);
if (cache[id] != Unknown)
return cache[id];
#else
auto lookup = cache.find(id);
if (lookup != cache.end())
return lookup->second;
#endif
unsigned long long result = 0;
// turn left if possible
auto turnLeft = (currentArc + 1) % 5;
if (numVisited[turnLeft] < maxPerArc)
{
numVisited[turnLeft]++;
result += search(arcsLeft - 1, turnLeft);
numVisited[turnLeft]--;
}
// turn right if possible
auto turnRight = (currentArc + 4) % 5; // -1 mod 5 => 5-1 mod 5
if (numVisited[turnRight] < maxPerArc)
{
numVisited[turnRight]++;
result += search(arcsLeft - 1, turnRight);
numVisited[turnRight]--;
}
// save result
cache[id] = result;
return result;
}
int main()
{
unsigned int numArcs = 70;
std::cin >> numArcs;
// let's go !
maxPerArc = numArcs / 5;
std::cout << search(numArcs) << std::endl;
return 0;
}