// A101856 - Number of non-intersecting polygons that it is possible for an accelerating ant
// to produce with n steps (rotations & reflections not included). On step 1 the ant moves
// forward 1 unit, then turns left or right and proceeds 2 units, then turns left or right 
// until at the end of its n-th step it arrives back at its starting place.
// C++ program by Bert Dobbelaere

#include <iostream>
#include <cstring>

#define MAXN 70
//#define VERBOSE

// Array indices must be positive in C/C++ language. Applying an offset.
#define ARRMAX (MAXN*MAXN)
#define OFFSET (ARRMAX/2)

// Keeps record of the traversed vertices:
int traceX[MAXN+1];
int traceY[MAXN+1];

// The "canvas" is a boolean grid used to draw to polygon upon. Purpose is not graphical
// output production, but to serve as a simple intersection detector. In this special case 
// that combines pure vertical and horizontal segments on integer coordinates with short edge
// lengths, grid based marking of visited coordinates is faster (and simpler) than a generic
// line intersection check algorithm.
bool canvas[ARRMAX][ARRMAX];

// At any depth in the recursive algorithm, these boolean arrays are used to check whether the
// current position can possibly lead us to the destination using only the remaining section 
// lengths and by considering their direction restrictions (disregarding possible collisions)
bool checkX[MAXN+1][ARRMAX];
bool checkY[MAXN+1][ARRMAX];

int N; // sequence index
int minlen; // smallest segment length added by recursive algorithm

// "count" counts the solutions. Should have >32 bit.
#if __cplusplus < 201103L
unsigned long long count;
#else
#include <cstdint>
uint64_t count;
#endif

enum Direction{
	UP=0, DOWN=1, LEFT=2, RIGHT=3
};

// Checks whether a line can be drawn on the canvas without intersection, and draws it only if
// conflict free. Returns "true" on success.
bool markPath(int x0, int y0, Direction d, int l)
{
	const int deltax[4]={0,0,-1,1};
	const int deltay[4]={1,-1,0,0};
	int x=x0;
	int y=y0;
	for(int k=0;k<l;k++)
	{
		x+=deltax[d]; y+=deltay[d];
		if(canvas[OFFSET+x][OFFSET+y])
			return false;
	}
	x=x0;
	y=y0;
	for(int k=0;k<l;k++)
	{
		x+=deltax[d]; y+=deltay[d];
		canvas[OFFSET+x][OFFSET+y] = true;
	}
	return true;
}

// Erase a line from the canvas
void clearPath(int x0, int y0, Direction d, int l)
{
	const int deltax[4]={0,0,-1,1};
	const int deltay[4]={1,-1,0,0};
	int x=x0;
	int y=y0;
	for(int k=0;k<l;k++)
	{
		x+=deltax[d]; y+=deltay[d];
		canvas[OFFSET+x][OFFSET+y] = false;
	}
}

// Show the solutions (if VERBOSE defined)
void printTrace()
{
	std::cout << "[";
	for(int k=0;k<=N;k++)
	{
		std::cout << "(" << traceX[k] << "," << traceY[k] << ")";
		if(k<N)
			std::cout << ", ";
	}
	std::cout << "]" << std::endl;
}

// Recursive routine performing the walk
// By proceeding from longest to shortest section, we attempt to reduce the workload at
// the deepest recursion levels.
void solve(int l)
{
	// See if we still have a chance of reaching the destination. If not, waste no time.
	if(!checkX[l][traceX[l]+OFFSET])
		return;
	if(!checkY[l][traceY[l]+OFFSET])
		return;
		
	if(l<minlen)
	{
		count++; // We have reached our destination point with no sections left. Count the solution.
#ifdef VERBOSE		
		printTrace();
#endif
		return;
	}
	if(l&1) // X direction for odd length
	{
		traceX[l-1]=traceX[l]-l;
		traceY[l-1]=traceY[l];
		if(markPath(traceX[l], traceY[l], LEFT, l))
		{
			solve(l-1);
			clearPath(traceX[l], traceY[l], LEFT, l);
		}
		traceX[l-1]=traceX[l]+l;
		if(markPath(traceX[l], traceY[l], RIGHT, l))
		{
			solve(l-1);
			clearPath(traceX[l], traceY[l], RIGHT, l);
		}
	}
	else // Y direction for even length
	{
		traceY[l-1]=traceY[l]-l;
		traceX[l-1]=traceX[l];
		if(markPath(traceX[l], traceY[l], DOWN, l))
		{
			solve(l-1);
			clearPath(traceX[l], traceY[l], DOWN, l);
		}
		traceY[l-1]=traceY[l]+l;
		if(markPath(traceX[l], traceY[l], UP, l))
		{
			solve(l-1);
			clearPath(traceX[l], traceY[l], UP, l);
		}
	}
}

// Initialize the coordinate filters
void initCheckArrays()
{
	memset(checkX,false,sizeof(checkX));
	memset(checkY,false,sizeof(checkY));
	// After traversing the last section, the only valid location is the destination itself.
	if(minlen==1)
	{   // For even N, destination is the origin
		checkX[minlen-1][0+OFFSET]=true;
		checkY[minlen-1][0+OFFSET]=true;
	}
	else
	{   // For odd N, destination is start of fixed length 1 section at coordinates (-1,0)
		checkX[minlen-1][(-1)+OFFSET]=true;
		checkY[minlen-1][0+OFFSET]=true;
	}
	for(int l=minlen;l<=MAXN;l++)
	{
		if(l&1)
		{
			memcpy(checkY[l],checkY[l-1],sizeof(checkY[l])); // Horizontal motion preserves Y
			for(int k=0;k<ARRMAX;k++)
			{   // X is valid before the move if any option leads to a valid X after the move.
				checkX[l][k] = ((k>=l) && checkX[l-1][k-l]) || ((k<(ARRMAX-l)) && checkX[l-1][k+l]);
			}
		}
		else
		{
			memcpy(checkX[l],checkX[l-1],sizeof(checkX[l])); // Vertical motion preserves X
			for(int k=0;k<ARRMAX;k++)
			{   // Y is valid before the move if any option leads to a valid Y after the move.
				checkY[l][k] = ((k>=l) && checkY[l-1][k-l]) || ((k<(ARRMAX-l)) && checkY[l-1][k+l]);
			}
		}
	}
}

int main()
{
	for(N=4;N<=MAXN;N++)
	{
		count=0;
		memset(canvas,0,sizeof(canvas));
		minlen = (N&1) ? 2 : 1;
		initCheckArrays();
		// Start with the fixed sections: 2 first directions are fixed, so rotations and mirror images are avoided.
		if(N&1)
		{
			// For odd N, we start with the shortest segment (1) extended by the longest (N).
			// We expect to end with a vertical segment of length 2.
			traceX[0]=0;traceY[0]=0;
			traceX[N]=0;traceY[N]=0;	
			traceX[1]=-1;traceY[1]=0;
			traceX[N-1]=N;traceY[N-1]=0; 
			markPath(-1,0,RIGHT,N+1);
			traceX[N-2]=N;traceY[N-2]=N-1;
			markPath(N,0, UP, N-1);
		}
		else
		{
			// For even N, just start with length N and end with a horizontal segment of length 1.
			traceX[0]=0;traceY[0]=0;
			traceX[N]=0;traceY[N]=0;	
			traceX[N-1]=0;traceY[N-1]=N;
			markPath(0,0,UP,N);
			traceX[N-2]=N-1;traceY[N-2]=N;
			markPath(0,N,RIGHT,N-1);
		}
		// Apply recursive routine from length N-2 downwards.
		solve(N-2);
		std::cout << "A101856(" << N << ") = " << count << std::endl;
	}
}