/*
 * numLakes.c
 * v1.00
 * Calculates the number of lakes in Conway's Game of Life on a given
 * number of cells.
 *
 * Created by Nathaniel Johnston (nathaniel@nathanieljohnston.com)
 * February 4, 2009
 *
 * http://www.nathanieljohnston.com/?title=counting_lakes
 * http://www.conwaylife.com/wiki/index.php?title=Lake
 */

#include <stdio.h>

unsigned char j,n,curStep,nextStep,curX[65],curY[65],been[65][65];
unsigned int i,numLakes,tempLakes;
unsigned long long int k,path[66000];
char forceS[61],forceE[61];

unsigned long long int cycleBinDigs(unsigned long long int inpDigs, unsigned char numDigs)
{
    unsigned long long int tCurDigs;
    tCurDigs = inpDigs + ((inpDigs % 2) << numDigs);
    return (tCurDigs >> 1);
}

unsigned char getDir(unsigned char y1, unsigned char y2, unsigned char x1, unsigned char x2)
{
    char dSide = x2 - x1, dUp = y2 - y1;
    return abs(dUp + 2*dSide - 1);
}

unsigned long long int revBits(unsigned long long int v, unsigned char len)
{
    unsigned long long int r = v;
    unsigned char s = sizeof(v) * 8 - 1;
    unsigned char t = s;
    for (v >>= 1; v; v >>= 1){
        r <<= 1;
        r |= v & 1;
        s--;
    }
    r <<= s;
    return r>>(t-len+1);
}

unsigned long long int getCurPath()
{
    unsigned long long int tPath=0;
    unsigned char curDir,lDir=getDir(curY[4*n-1],curY[0],curX[4*n-1],curX[0]);
    for(i=1;i<=(4*n);i++){
        tPath<<=1;
        curDir = getDir(curY[i-1],curY[i],curX[i-1],curX[i]);
        if(((curDir+1)%4)==lDir){
            tPath+=1;
        }
        lDir=curDir;
    }
    return tPath;
}

unsigned long long int checkNewPath()
{
    unsigned long long int curPath = getCurPath();
    for(i=1;i<=numLakes;i++){
        for(j=0;j<=(4*n)-1;j++){
            if((path[i-1]==curPath)||((path[i-1]+curPath+1)==(((long long)1)<<(4*n)))||((path[i-1]==revBits(curPath,4*n)))||((path[i-1]+revBits(curPath,4*n)+1==(((long long)1)<<(4*n))))){
                curPath=0;
                break;
            }
            curPath=cycleBinDigs(curPath,4*n);
        }
        if(curPath==0){break;}
    }
    return curPath;
}

void getNextStep()
{
    unsigned long long int tempPath;
    char m;

    for(m=forceS[curStep];m<=forceE[curStep];m+=2)
    {
        if(curStep%2==0){ // MOVE UP OR DOWN
            curX[nextStep]=curX[curStep];
            curY[nextStep]=curY[curStep]+m;
        }else{ // MOVE LEFT OR RIGHT
            curX[nextStep]=curX[curStep]+m;
            curY[nextStep]=curY[curStep];
        }

        if(((been[curY[nextStep]][curX[nextStep]]==0)&&(abs(curX[curStep]-curX[0])<=(4*n-curStep+1)/2)&&(abs(curY[curStep]-curY[0])<=(4*n-curStep+1)/2))^(curStep==(4*n)-1)){
            k++;
            if((k%1000==0)&&(tempLakes!=numLakes)){
                printf("Lakes found: %d\n",numLakes);
                tempLakes = numLakes;
            }
            if(curStep==((4*n)-1)){
                if((curY[0]==curY[4*n])&&(curX[0]==curX[4*n])){
                    tempPath = checkNewPath();
                    if(tempPath>0){
                        path[numLakes]=tempPath;
                        numLakes++;
                    }
                }
            }else{
                been[curY[nextStep]][curX[nextStep]]=1;
                curStep=nextStep;
                nextStep++;
                getNextStep();
            }
        }
    }
    been[curY[curStep]][curX[curStep]]=0;
    curStep--;
    nextStep--;
}

void setVariables()
{
    for(i=0;i<=64;i++){
        for(j=0;j<=64;j++){
            been[i][j]=0;
        }
    }
    for(i=0;i<=60;i++){
        forceS[i]=-1;
        forceE[i]=1;
    }

    nextStep=1;
    curStep=0;
    numLakes=0;
    curY[0]=32;
    curX[0]=32;
    forceS[0]=1;
    forceE[0]=1;
    forceS[1]=1;
    forceE[1]=1;
    forceS[2]=1;
    forceE[2]=1;
    forceS[3]=-1;
    forceE[3]=-1;
    forceS[4]=1;
    forceE[4]=1;
    been[curY[0]][curX[0]]=1;
    k=0;
}

int main()
{
    setVariables();

    printf("This tool will calculate the number of lakes in the Game of Life with 8n cells.\nPlease enter n (1 <= n <= 15): ");
    scanf("%d",&n);

    if(n==1){
        numLakes=1;
    }else{
        getNextStep();
    }
    printf("Total number of lakes with %d cells: %d",8*n,numLakes);
    getchar();
    return 0;
}