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