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