Some notes about the script:
- It does a brute force search, and thus finds all strict still lifes
- The way in which it filters out pseudo still lifes is based on the definition that if it can be split up into two stable subpatterns, then it is pseudo. I realize that there are pseudos that it may miss (see this page for some discussion), but I can't see that being an issue for still lifes that can realistically be computed using this script.
- It filters out different reflections/rotations of the same still lifes.
- Realistically, it's fast enough to enumerate still lifes up to 9 or maybe 10 cells.
Note: If you use Windows, there is a compiled (ie. executable) version of this program attached at the bottom of this post.
EnumStillLifes.c
Code: Select all
/*
* EnumStillLifes.c
* v1.03
* Calculates the number of still lifes in a Life-like cellular automaton
* given a rulestring and a number of cells
* Does a brute-force search, so it is very slow for even moderately large n
*
* Created by Nathaniel Johnston (nathaniel@nathanieljohnston.com)
* Created: March 19, 2009
* Modified: March 28, 2009
*/
#include <math.h>
#include <stdio.h>
#include <string.h>
// If needed, change 10000 to a number larger than the number of still lifes that will be found
unsigned char foundSL[10000][16][16],islandCount=0,numIsl;
unsigned char group1[20][20],group2[20][20];
unsigned char birth23,n,u,uInc,curStep,islArr[16][20][20],been[20][20],tempB[20][20],tempC[20][20],xp[18],yp[18],minX,minY,maxX,maxY;
unsigned int i,j,survive=0,birth=0;
unsigned long int total=0;
char fName[50];
FILE *file;
int max(int mA, int mB)
{
if(mA >= mB) return mA;
return mB;
}
int min(int mA, int mB)
{
if(mA <= mB) return mA;
return mB;
}
unsigned char numNeighbours(unsigned char x, unsigned char y, unsigned char bArr[20][20]){
char nI,nJ;
unsigned char res=0;
for(nI=x-1;nI<=x+1;++nI){
for(nJ=y-1;nJ<=y+1;++nJ){
res+=bArr[nI][nJ];
}
}
return res;
}
void getMinMax()
{
unsigned char mI;
minX = u+2;
minY = u+2;
maxX = 2;
maxY = 2;
for (mI=1;mI<=n;mI++){
minY=min(yp[mI],minY);
minX=min(xp[mI],minX);
maxY=max(yp[mI],maxY);
maxX=max(xp[mI],maxX);
}
}
void printSL(unsigned char pArr[20][20])
{
unsigned char pI,pJ,pK;
printf("Still lifes found so far: %d\n",total+1);
file = fopen(fName,"a+");
for(pI=2;pI<=maxY+1;++pI){
for(pJ=2;pJ<=maxX;++pJ){
if(pArr[pJ][pI]==1){
fprintf(file,"*");
}else{
fprintf(file," ");
}
}
fprintf(file,"\n");
}
fprintf(file,"\n");
fclose(file);
}
unsigned char checkPreviousSL(unsigned char bArr[20][20])
{
unsigned char cI,cJ;
unsigned int cK;
unsigned char match;
for(cI=2;cI<=34;++cI){
for(cJ=2;cJ<=34;++cJ){
foundSL[total][cI-2][cJ-2] = bArr[cI][cJ];
}
}
for(cK=0;cK<total;++cK){
match=1;
for(cI=2;cI<=maxX;++cI){
for(cJ=2;cJ<=maxY;++cJ){
if(foundSL[cK][maxX-cI][maxY-cJ]!=bArr[cI][cJ]){
cJ=maxY;
cI=maxX;
match=0;
}
}
}
if(match==1){return 0;}
match=1;
for(cI=2;cI<=maxX;++cI){
for(cJ=2;cJ<=maxY;++cJ){
if(foundSL[cK][cI-2][maxY-cJ]!=bArr[cI][cJ]){
cJ=maxY;
cI=maxX;
match=0;
}
}
}
if(match==1){return 0;}
match=1;
for(cI=2;cI<=maxX;++cI){
for(cJ=2;cJ<=maxY;++cJ){
if(foundSL[cK][maxX-cI][cJ-2]!=bArr[cI][cJ]){
cJ=maxY;
cI=maxX;
match=0;
}
}
}
if(match==1){return 0;}
match=1;
for(cI=2;cI<=maxX;++cI){
for(cJ=2;cJ<=maxY;++cJ){
if(foundSL[cK][maxY-cJ][maxX-cI]!=bArr[cI][cJ]){
cJ=maxY;
cI=maxX;
match=0;
}
}
}
if(match==1){return 0;}
match=1;
for(cI=2;cI<=maxX;++cI){
for(cJ=2;cJ<=maxY;++cJ){
if(foundSL[cK][cJ-2][maxX-cI]!=bArr[cI][cJ]){
cJ=maxY;
cI=maxX;
match=0;
}
}
}
if(match==1){return 0;}
match=1;
for(cI=2;cI<=maxX;++cI){
for(cJ=2;cJ<=maxY;++cJ){
if(foundSL[cK][maxY-cJ][cI-2]!=bArr[cI][cJ]){
cJ=maxY;
cI=maxX;
match=0;
}
}
}
if(match==1){return 0;}
match=1;
for(cI=2;cI<=maxX;++cI){
for(cJ=2;cJ<=maxY;++cJ){
if(foundSL[cK][cJ-2][cI-2]!=bArr[cI][cJ]){
cJ=maxY;
cI=maxX;
match=0;
}
}
}
if(match==1){return 0;}
}
return 1;
}
unsigned char isStillLife(unsigned char beenArr[20][20], unsigned char forceY)
{
char sI,sJ,sRes;
getMinMax();
if(minY>forceY){
return 0;
}
for(sI=1;sI<=u+2;sI++){
for(sJ=1;sJ<=u+2;sJ++){
if(beenArr[sI][sJ]==1){
if((survive & (1 << (numNeighbours(sI,sJ,beenArr)-1))) == 0){
return 0;
}
}else if((birth & (1 << numNeighbours(sI,sJ,beenArr))) > 0){
return 0;
}
}
}
if(forceY==2){
sRes = checkPreviousSL(beenArr);
}else{
sRes = 1;
}
return sRes;
}
void fillOutIsland(unsigned char xC, unsigned char yC)
{
unsigned char fI, fJ;
for(fI=xC-1;fI<=xC+1;++fI){
for(fJ=yC-1;fJ<=yC+1;++fJ){
if((been[fI][fJ]==1)&(tempB[fI][fJ]==0)){
tempB[fI][fJ]=1;
tempC[fI][fJ]=1;
islArr[numIsl][fI][fJ]=1;
islandCount++;
fillOutIsland(fI,fJ);
}
}
}
}
void resetIslArr()
{
unsigned char iaI;
for(iaI=0;iaI<=15;++iaI){
for(i=0;i<=19;i++){
for(j=0;j<=19;j++){
islArr[iaI][i][j]=0;
}
}
}
}
void resetTempB()
{
for(i=0;i<=19;i++){
for(j=0;j<=19;j++){
tempB[i][j]=0;
}
}
}
void resetTempC()
{
for(i=0;i<=19;i++){
for(j=0;j<=19;j++){
tempC[i][j]=0;
}
}
}
void clearGroups()
{
for(i=0;i<=19;i++){
for(j=0;j<=19;j++){
group1[i][j]=0;
group2[i][j]=0;
}
}
}
unsigned char findIsland()
{
unsigned char iI,start;
for(iI=1;iI<=n;++iI){
if(tempC[xp[iI]][yp[iI]] == 0){
start=iI;
break;
}
}
resetTempB();
tempB[xp[start]][yp[start]]=1;
tempC[xp[start]][yp[start]]=1;
islArr[numIsl][xp[start]][yp[start]]=1;
islandCount++;
fillOutIsland(xp[start],yp[start]);
return (1-isStillLife(tempB,u+1));
}
unsigned char firstCellsCheck(unsigned char fPos){
return (birth & (1 << (been[2][fPos]+been[2][fPos-1]+been[2][fPos-2])));
}
unsigned char firstRowCheck(){
unsigned char fI;
unsigned long int tNum=0,rNum=0;
for(fI=0;fI<u;++fI){
rNum += ((long)been[2][fI+2] << ((u-1)-fI));
tNum += ((long)been[2][fI+2] << fI);
}
return (rNum >= tNum);
}
void combGroup(unsigned char groupArr[20][20], unsigned char islTArr[20][20]){
for(i=0;i<=19;i++){
for(j=0;j<=19;j++){
groupArr[i][j]=max(groupArr[i][j],islTArr[i][j]);;
}
}
}
unsigned char checkPseudo(){
unsigned int psI,psJ,psLim;
psLim = (1 << numIsl);
for(psI=psLim/2;psI<psLim-1;++psI){
clearGroups();
for(psJ=0;psJ<numIsl;++psJ){
if(psI & (1 << psJ)){
combGroup(group1,islArr[psJ]);
}else{
combGroup(group2,islArr[psJ]);
}
}
if(isStillLife(group1,u+1)&&isStillLife(group2,u+1)){return 0;}
}
return 1;
}
void getNextStep(char curM)
{
unsigned char m,cx,cy,isSL;
unsigned char lim = min(u*u - (u-curStep), curM + 2*(u+2));
if(curM==-1)lim=ceil(n/3.0001)-1;
m=curM+1;
if(!(birth23&&m<u&&firstCellsCheck(m))&&!(m==u&&(firstRowCheck()==0))){
curStep++;
while(m<=lim)
{
cx=floor(m/u)+2;
cy=(m%u)+2;
xp[curStep]=cx;
yp[curStep]=cy;
been[cx][cy]=1;
if(curStep==n){
islandCount=0;
isSL = isStillLife(been,2);
if(isSL==1){
numIsl=0;
isSL=0;
resetTempC();
resetIslArr();
while(islandCount<n){
isSL=max(findIsland(),isSL);
numIsl++;
}
if(numIsl==1){
isSL=1;
}else{
if(isSL==1){
isSL=checkPseudo();
}
}
}
if(isSL==1){
printSL(been);
}
total+=isSL;
}else{
getNextStep(m);
}
been[cx][cy]=0;
if(m==curM+u+2){m+=uInc;}
else{m++;}
}
curStep--;
}
}
void setVariables()
{
for(i=0;i<=19;i++){
for(j=0;j<=19;j++){
been[i][j]=0;
tempC[i][j]=0;
}
}
curStep=0;
total=0;
}
int main()
{
unsigned char foundSlash = 0;
char rs[19];
setVariables();
printf("This tool will calculate the number of still lifes in a Life-like cellular automaton.\nPlease enter the rulestring in S/B format (eg. 23/3 for Conway's Game of Life): ");
scanf("%s",&rs);
for(i=0;i<strlen(rs);i++){
if(foundSlash==0){
if(rs[i]=='/'){
foundSlash = 1;
}else{
survive += (1 << (rs[i]-16));
}
}else{
birth += (1 << (rs[i]-16));
}
}
if(birth & 1){
printf("There are no still lifes in any rule with \"0\" in the birth list.");
}else if(birth & 2){
printf("There are no still lifes in any rule with \"1\" in the birth list.");
}else if(!(survive & 1)&&!(survive & 2)&&!(survive & 4)&&!(survive & 8)&&!(survive & 16)){
printf("There are no still lifes in this rule because all cells with 4 or fewer neighbours die.");
}else{
birth23=((birth & 4)||(birth & 8));
printf("Enter the number of cells (1 <= n <= 16): ");
scanf("%d",&n);
u = n;
if(!(survive & 2)){ // if "1" is not in the survival list
u = min(max(n - 2, min(n, 4)), u);
}
uInc = max(u-4,1);
printf("Please enter an output file name (eg. \"output.txt\"): ");
scanf("%s",&fName);
getNextStep(-1);
file = fopen(fName,"a+");
fprintf(file,"Number of %d-cell still lifes in \"%s\": %d\n",n,rs,total);
fclose(file);
printf("Total number of %d-cell still lifes in \"%s\": %d",n,rs,total);
}
return 0;
}