Enumerating Still Lifes (in C)

For scripts to aid with computation or simulation in cellular automata.
User avatar
Nathaniel
Site Admin
Posts: 861
Joined: December 10th, 2008, 3:48 pm
Location: New Brunswick, Canada
Contact:

Enumerating Still Lifes (in C)

Post by Nathaniel » March 25th, 2009, 8:35 pm

The following code computes the number of still lifes with a given number of cells in a given Life-like cellular automaton. All the still lifes found will be outputted to a user-defined text file. This script was used to get the still life counts on the 2x2 and maze pages of LifeWiki.

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;
}
Attachments
EnumStillLifes v1.03.zip
Pre-compiled Windows executable version
(7.82 KiB) Downloaded 955 times

User avatar
Lewis
Posts: 337
Joined: March 17th, 2009, 5:26 pm
Location: UK
Contact:

Re: Enumerating Still Lifes (in C)

Post by Lewis » March 26th, 2009, 4:21 am

How do you run scripts like this as a program? I have no knowledge of programming so I don't know how to use the script.

User avatar
Nathaniel
Site Admin
Posts: 861
Joined: December 10th, 2008, 3:48 pm
Location: New Brunswick, Canada
Contact:

Re: Enumerating Still Lifes (in C)

Post by Nathaniel » March 26th, 2009, 7:30 am

Lewis wrote:How do you run scripts like this as a program? I have no knowledge of programming so I don't know how to use the script.
I've attached an executable version of the script to the original post now so that if you use Windows, you can just download and run that file. If you want to compile the script yourself or modify the script, then you'll have to download a C compiler and/or editor. I myself use CodeBlocks. Open the .c file in that program, then go to Build -> Build and Run.

Elithrion
Posts: 100
Joined: February 3rd, 2009, 4:02 pm
Contact:

Re: Enumerating Still Lifes (in C)

Post by Elithrion » March 26th, 2009, 12:58 pm

Nathaniel wrote:- The program seems to crash once it finds about 1,000 still lifes. I'm not sure why yet.
Could it be because you have

Code: Select all

unsigned char foundSL[1000][16][16]
I assume that's an array for keeping track of still lifes found (still only beginning to look through the code), and that it would overfill if you got >1000 still lifes. Or I could be jumping the gun with that guess *goes back to figuring out code*
Vi veri veniversum vivus vici.

User avatar
Nathaniel
Site Admin
Posts: 861
Joined: December 10th, 2008, 3:48 pm
Location: New Brunswick, Canada
Contact:

Re: Enumerating Still Lifes (in C)

Post by Nathaniel » March 26th, 2009, 2:10 pm

Elithrion wrote:
Nathaniel wrote:- The program seems to crash once it finds about 1,000 still lifes. I'm not sure why yet.
Could it be because you have

Code: Select all

unsigned char foundSL[1000][16][16]
I assume that's an array for keeping track of still lifes found (still only beginning to look through the code), and that it would overfill if you got >1000 still lifes. Or I could be jumping the gun with that guess *goes back to figuring out code*
Haha wow, I'm a bit slow it seems. Yeah, that'd be the cause. Dynamic arrays are slightly slower (and I'm lazy), so I hard-coded in the upper limit and forgot that I did that. Changing that from 1000 to something appropriately larger will fix the crashing.

Elithrion
Posts: 100
Joined: February 3rd, 2009, 4:02 pm
Contact:

Re: Enumerating Still Lifes (in C)

Post by Elithrion » March 26th, 2009, 7:27 pm

Okay, I think I understand about half the code now. The details of getNextStep and the entirety of the island stuff elude me. Didn't anyone ever tell you to make explanatory comments? :P

Speaking of islands, I played around and noticed that looking for 7-celled lifes in 23/3 with the code as-is took 304.467s. When I judiciously commented out all calls to the island thing, it went down to 69.287s. That's pretty horrible inefficiency, especially considering that there are no invalid islands in that configuration, and that it doesn't kill them all in others. Hence, a proposal (you know my unreasonable fondness for solving problems with tons of recursion, so brace yourself):
Kill the islands part, and replace it with a simple filter on the output. The filter would go through all the still lifes found and eliminate those that are entirely composed of still lifes in a list. The list would contain all the still lifes in the ruleset that have fewer cells (under every reflection/rotation). The whole process shouldn't be much worse than O(n^3) (maybe? total guess) and would eliminate all the pseudo-still-lifes completely (definitely!). I could write some pseudo-code if you want (or, god forbid, some actual code).

Also, would it be faster/possible to set the array dimensions after getting the user input? 'Cause they're usually way too big right now, although I suppose it shouldn't make too much difference.

More crazy plans to come as I think of them!
Vi veri veniversum vivus vici.

User avatar
Nathaniel
Site Admin
Posts: 861
Joined: December 10th, 2008, 3:48 pm
Location: New Brunswick, Canada
Contact:

Re: Enumerating Still Lifes (in C)

Post by Nathaniel » March 26th, 2009, 7:44 pm

Elithrion wrote:Okay, I think I understand about half the code now. The details of getNextStep and the entirety of the island stuff elude me. Didn't anyone ever tell you to make explanatory comments? :P
Yeah I didn't comment much mainly because 1) I never comment (I'm bad, I know), and 2) I figured I'd just explain the code in this thread. So to that end...

getNextStep is the part that does the brute-forcing. Let's say you want to find all 4-cell still lifes. Then the program sets up a 4x4 bounding box (it's not completely trivial, though not hard, to prove that in any rule, a strict still life with k cells must be contained in a kxk bounding box, and this is the smallest bounding box that this result holds for).

getNextStep calls itself recursively until it has placed 4 cells (and it places 1 cell each time). If there are 4 cells on the board, it checks to see if they form a still life. If yes, increment the count and record it, if not, remove the last cell and place it at the next open location. Repeat this until the last cell is at the bottom-right corner of the bounding box. Once that happens, move cell 3 up one spot, and place cell 4 right next to it. Increment cell 4 until it reaches the end, and increment cell 3 when it's time to do so again. Repeat this until both cells 3 and 4 are at the bottom-right of the bounding box, and then increment cell 2. You see where I'm going with this.

Some of the weirder lines of code are things to speed up the process by reducing the number of situations that need to be checked. For example, rather than increasing cells all the way to the bottom-right of the bounding box, they only need to be incremented to 2 rows past the previous cell (otherwise any still lifes found would be pseudo-still lifes).

Similarly, the very first cell only needs to go through half of the first row, since any still lifes found after that would just be rotations/reflections of previously-found still lifes.

Any other speed-ups that anyone can think of for the recursion part are most welcome.
Elithrion wrote:Speaking of islands, I played around and noticed that looking for 7-celled lifes in 23/3 with the code as-is took 304.467s. When I judiciously commented out all calls to the island thing, it went down to 69.287s.
That's very weird, there's got to be a bug somewhere then, because the island-checking code only (should) get called if the pattern under consideration is a still life, and there's precious few 7-cell still lifes in 23/3. Combined with the fact that there are hundreds of island-based still lifes in maze (12345/3) and it runs at about the same speed for those, I think the island code must be getting called way more than it should, or some such thing.[/quote]

I'm done typing now. I'll give the rest of your post another hour to sink in and then reply to it :P

User avatar
Nathaniel
Site Admin
Posts: 861
Joined: December 10th, 2008, 3:48 pm
Location: New Brunswick, Canada
Contact:

Re: Enumerating Still Lifes (in C)

Post by Nathaniel » March 26th, 2009, 8:17 pm

Elithrion wrote:Speaking of islands, I played around and noticed that looking for 7-celled lifes in 23/3 with the code as-is took 304.467s.
Hrm, are you sure about this (ie. could you try it again)? I just tested this on my laptop, and without commenting out the islands stuff, it took 92 seconds, and that's while another instance of the program was running in the background calculating 9-cell still lifes in another rule (and my laptop is no supercomputer).

One possible cause of the discrepancy is that the time that it gives you is the time since you opened the program, not the time that it spent calculating (ie. it's a timestamp produced by DOS, not by my script). Thus, if you open the program and leave it at the prompts for a while, that time gets added to the total time.

Elithrion
Posts: 100
Joined: February 3rd, 2009, 4:02 pm
Contact:

Re: Enumerating Still Lifes (in C)

Post by Elithrion » March 26th, 2009, 8:39 pm

Oh, possible. I presumably overlooked that fact. Redoing the experiment with a minimum of time spent typing stuff in got me 59.825s on unmodified, 58.691s modified.

So, I suppose at least it's working properly. Still, it doesn't look remotely efficient (and there's only 4 still lifes in this case anyway) and I'll maybe get some numbers that properly show that! Perhaps! Also, was getting like 650 or something still lifes for 8 cells 2x2 correct? If so, you are truly a hero for sorting through them.

[edit:] also, I'm doing it wrong. Hold on, I'll get back to you with real results some time. Meanwhile, my proposal still works fine.

[and another edit:] okay, fine, I stand defeated. Running 7-cell maze is actually more efficient with the islands bit included, presumably because without it the rotation/reflection check chugs. That said, in my defence, it's still not very good at killing off pseudo still lifes, and the rotation/reflection check could also perhaps be exported to post-processing or simplified (I honestly don't like it much as-is, but haven't figured out a good plan of attack yet).
Last edited by Elithrion on March 26th, 2009, 8:55 pm, edited 1 time in total.
Vi veri veniversum vivus vici.

User avatar
Nathaniel
Site Admin
Posts: 861
Joined: December 10th, 2008, 3:48 pm
Location: New Brunswick, Canada
Contact:

Re: Enumerating Still Lifes (in C)

Post by Nathaniel » March 26th, 2009, 8:52 pm

Elithrion wrote:Also, was getting like 650 or something still lifes for 8 cells 2x2 correct? If so, you are truly a hero for sorting through them.
Yeah, fortunately it doesn't take too long when the vast majority of them consist of a 2-cell still life a good distance away from something else. They tend to come in clumps as well, so you get streams that look like:

Code: Select all

.OO
O  O
O O
.O.....OO


.OO
O  O
O O
.O.....O
........O


.OO
O  O
O O
.O.....O
.......O

Elithrion
Posts: 100
Joined: February 3rd, 2009, 4:02 pm
Contact:

Re: Enumerating Still Lifes (in C)

Post by Elithrion » March 26th, 2009, 9:36 pm

Edit: Sorry, this post was made by Nathaniel. I accidentally edited rather than quoted.
Elithrion wrote:Hmm... I would have said that something can be done about the translation component since a pattern's cells all move one to the right at some predictable interval, but the cells "only need to be incremented to 2 rows past the previous cell" speed-up makes it much harder to predict.
Are you talking about noting duplicates like the following?

Code: Select all

......
.OO...
O  O..
O O...
.O....


...OO.
..O  O
..O O.
...O..
......
If so, then the vast majority of them are captured automatically by making sure that the first cell is placed somewhere in the first half of the first row (which is one of the speed-ups I mentioned). A still life can at most be located in floor(n/2) different translated locations then in the current program, so trying to speed that part of the program up shouldn't be a big concern.

In fact, given that the VAST majority of patterns found are not still lifes, altering the code that weeds out pseudo/already found still lifes will make just a drop in the bucket speed up, I think (though it would be nice to have it weed out all pseudo still lifes). I think what we need to focus on is finding ways to speed up (1) checking whether or not the given pattern is a still life, and (2) checking all relevant patterns (ie. are there other search speed ups that we can make that speed up the recursion? Other large sets of patterns that will *never* be still lifes, or at least won't ever be still lifes given a certain easy-to-check condition on the rulestring?)
Vi veri veniversum vivus vici.

Elithrion
Posts: 100
Joined: February 3rd, 2009, 4:02 pm
Contact:

Re: Enumerating Still Lifes (in C)

Post by Elithrion » March 26th, 2009, 10:54 pm

Psst... the edit button is not the quote button, Mr. Admin :P

That said, while the vast majority of them are eliminated, yes, the check for them is still performed every time, right (at least for ones that aren't ruled out by other matches)? That still drags on the program a bit, I expect (a full comparison against every previously found still life and all). Incidentally, there should be a way to actually see what takes how long, with debugging and whatnot. But also, I've noticed that still life finds get rarer as the program runs longer. This is probably mostly because the pattern becomes more sparse, but I'll check semi-properly by trying a version completely without checks (for matches/islands) in a little bit, I think.

But I did come up with a pair speed-ups so minor I'm not even sure they're worth doing:
  • cells below ceiling(n/2) in number should never be in the second half of the first row (as the result would necessarily be a reflection of something across the vertical)
  • the first cell should never be the leftmost cell if there are any cells outside the first row (as the result would be a translation [if it's the single leftmost] and/or rotation [if it's tied for leftmost])
More rules of similar inconsequence to come, no doubt!
Vi veri veniversum vivus vici.

Elithrion
Posts: 100
Joined: February 3rd, 2009, 4:02 pm
Contact:

Re: Enumerating Still Lifes (in C)

Post by Elithrion » March 26th, 2009, 11:41 pm

Okay, you're absolutely right - removing the checks (and even the file writing) made no noticeable positive difference. Some results over multiple trials:

12345/3, 7 cells
no checks: 77.030s, 75.454, 76.746
yes checks: 72.302s, 75.798, 72.273
no checks or writing: 72.915s, 72.780

23/3, 6 cells
no checks: 4.348s, 4.222, 3.740, 3.887
yes checks: 4.085s, 3.798, 3.740, 3.629
Vi veri veniversum vivus vici.

User avatar
Nathaniel
Site Admin
Posts: 861
Joined: December 10th, 2008, 3:48 pm
Location: New Brunswick, Canada
Contact:

Re: Enumerating Still Lifes (in C)

Post by Nathaniel » March 27th, 2009, 12:03 am

Elithrion wrote:cells below ceiling(n/2) in number should never be in the second half of the first row (as the result would necessarily be a reflection of something across the vertical)
Hrm... I don't think I'm understanding this one... what about the rule 12/4, and consider the following pattern:

Code: Select all

.OO.
O..O
....
....
That's a still life, and the 2nd cell is in the right half of the first row. The only form of it that doesn't have one of its early cells near the top right is a 90-degree rotation clockwise, so I don't think that's what you were referring to... am I misunderstanding what you said?

User avatar
Nathaniel
Site Admin
Posts: 861
Joined: December 10th, 2008, 3:48 pm
Location: New Brunswick, Canada
Contact:

Re: Enumerating Still Lifes (in C)

Post by Nathaniel » March 27th, 2009, 12:05 am

Elithrion wrote:Okay, you're absolutely right - removing the checks (and even the file writing) made no noticeable positive difference.
Good to know, that narrows down what parts of the code we need to worry about ;)

Elithrion
Posts: 100
Joined: February 3rd, 2009, 4:02 pm
Contact:

Re: Enumerating Still Lifes (in C)

Post by Elithrion » March 27th, 2009, 12:49 am

Nathaniel wrote:
Elithrion wrote:cells below ceiling(n/2) in number should never be in the second half of the first row (as the result would necessarily be a reflection of something across the vertical)
Hrm... I don't think I'm understanding this one... what about the rule 12/4, and consider the following pattern:

Code: Select all

.OO.
O..O
....
....
That's a still life, and the 2nd cell is in the right half of the first row. The only form of it that doesn't have one of its early cells near the top right is a 90-degree rotation clockwise, so I don't think that's what you were referring to... am I misunderstanding what you said?
Hmm... no, I guess I messed up. There's definitely something there, though - maybe "floor(n/2) + 1 (counting from the end of the row)" instead of "second half"? *goes off to actually experiment* No, okay, that's not better. New, sensible version:
There should never be more cells in the second half of the first row than in the first half (same number is okay). Hmm... but more than that, starting from the middle of the first row (ignoring the centre cell if the width is odd), and taking first the two centremost cells, then the four centremost, etc, each time there should not be more living cells on the right than the left. i.e. (first rows only shown)

Code: Select all

...OOO... <-- okay
...O..O. <-- also okay
.O..O... <-- not okay (first pair fails)
O...OOO... <-- not okay (second pair fails) 
Incidentally, this encompasses the "first cell stays on the left" rule, but is admittedly quite complicated.
Vi veri veniversum vivus vici.

User avatar
Nathaniel
Site Admin
Posts: 861
Joined: December 10th, 2008, 3:48 pm
Location: New Brunswick, Canada
Contact:

Re: Enumerating Still Lifes (in C)

Post by Nathaniel » March 27th, 2009, 6:53 am

Ah I get what you're saying. How about this version of it, which I believe is more general:

Convert the first row to a binary string and also a reversed copy of that binary string. For example,

Code: Select all

..**.*.
0011010
0101100
If the reversed binary string represents a larger number than the non-reversed binary string, abort, because it's just going to be a reflection.

I implemented this and it seems to be working, though the time savings unfortunately seem to be almost non-existent. I suppose because so many of the cells already have to be placed before this catches any degenerate cases.

Edit: I think one speed-up that might be fruitful is nailing down exactly how far we really need to let the first cell go. Certainly if we let it run over the first half of the row (ie. ceil(n/2) locations), then that is sufficient? But is it necessary? I think that we can likely lower this to something like ceil(n/3), but I can't think of why/how exactly.

Edit again: Also, we can almost certainly reduce the bounding box size that is checked in certain broad classes of rules. The only n-cell still life that actually uses the whole n-by-n bounding box in any rule is the diagonal line, and many rules (certainly the more interesting ones) won't come close to being the large. For Conway's Life, for example, the snake, long snake, long long snake, and so on, seems to be the still life with the largest bounding box... but is that provably/generalizable? I feel like if 1 is not in the survival list of the rule, in particular, then the bounding box should be smaller.

Final edit: Well, if 1 is not in the survival list, then the bounding box will always be at most (n-2)-by-(n-2) (right? assuming n >= 6 anyways), so that's one reduction that is nice for a fairly large class of rules (and this is the smallest we can make the bounding box with only the consideration of 1 not being in the survival list, since the rule 02345678/ obviously has still lifes with this size of bounding box). Any other reductions that can be made for large groups of rules?

Elithrion
Posts: 100
Joined: February 3rd, 2009, 4:02 pm
Contact:

Re: Enumerating Still Lifes (in C)

Post by Elithrion » March 27th, 2009, 11:06 am

Nathaniel wrote:Ah I get what you're saying. How about this version of it, which I believe is more general: ...
Well, that's actually equally general, isn't it? Way less confusing to check, though.
Nathaniel wrote:Edit: I think one speed-up that might be fruitful is nailing down exactly how far we really need to let the first cell go. Certainly if we let it run over the first half of the row (ie. ceil(n/2) locations), then that is sufficient? But is it necessary? I think that we can likely lower this to something like ceil(n/3), but I can't think of why/how exactly.
Well, there are always cases like

Code: Select all

..OO..
.O....
O.....
.O....
..O...
......
right? Hmm... to be fair, you can do this:

Code: Select all

O.....
O...O.
.O.O..
..O...
......
......
to that one, and while designing it, I couldn't figure out a way to make that impossible, but a proof of why that should always hold is only slowly beginning to coalesce in my mind. I'll get back to you when it's done.
Nathaniel wrote:Edit again: Also, we can almost certainly reduce the bounding box size that is checked in certain broad classes of rules. The only n-cell still life that actually uses the whole n-by-n bounding box in any rule is the diagonal line, and many rules (certainly the more interesting ones) won't come close to being the large. For Conway's Life, for example, the snake, long snake, long long snake, and so on, seems to be the still life with the largest bounding box... but is that provably/generalizable? I feel like if 1 is not in the survival list of the rule, in particular, then the bounding box should be smaller.

Final edit: Well, if 1 is not in the survival list, then the bounding box will always be at most (n-2)-by-(n-2) (right? assuming n >= 6 anyways), so that's one reduction that is nice for a fairly large class of rules (and this is the smallest we can make the bounding box with only the consideration of 1 not being in the survival list, since the rule 02345678/ obviously has still lifes with this size of bounding box). Any other reductions that can be made for large groups of rules?
Well, I'm not sure what sort of density 0 makes possible, but I don't think it's a significant contribution... point being that the next victim to attack is probably the 2. Without it, you can't have a line, so the most space consuming thing is... I don't know, actually. However! What we should do is just run your program for 013456789/-, 5 cells, say, then 13456789/-, etc, for all likely cases and just check what's the smallest. With most S numbers still included, small numbers of cells shouldn't be a problem and should extrapolate upwards easily. Or that's the plan, at least. I'll go maybe do that now.
Vi veri veniversum vivus vici.

User avatar
Nathaniel
Site Admin
Posts: 861
Joined: December 10th, 2008, 3:48 pm
Location: New Brunswick, Canada
Contact:

Re: Enumerating Still Lifes (in C)

Post by Nathaniel » March 27th, 2009, 11:44 am

Elithrion wrote:Well, that's actually equally general, isn't it? Way less confusing to check, though.
Might be the same, yeah. As long as that's what you were getting at anyways, it's implemented now.
Elithrion wrote:Well, there are always cases like

Code: Select all

..OO..
.O....
O.....
.O....
..O...
......
right? Hmm... to be fair, you can do this:

Code: Select all

O.....
O...O.
.O.O..
..O...
......
......
to that one, and while designing it, I couldn't figure out a way to make that impossible, but a proof of why that should always hold is only slowly beginning to coalesce in my mind. I'll get back to you when it's done.
Yeah, the only way to have a still life that *needs* the first cell in the n/2 position in the first row, it would also have to be present at the n/2 position (ie. the midpoint) down each side of the bounding box as well (and nowhere else along the edge of the bounding box, but that seems less relevant). It seems to me then that there would have to be way too many other cells present in order for this still life to not be pseudo (at least 2n cells, I believe?).

However, pinning down what the last possible position of the first cell actually *is* seems much less easy to visualize.
Nathaniel wrote:Well, I'm not sure what sort of density 0 makes possible, but I don't think it's a significant contribution... point being that the next victim to attack is probably the 2. Without it, you can't have a line, so the most space consuming thing is... I don't know, actually. However! What we should do is just run your program for 013456789/-, 5 cells, say, then 13456789/-, etc, for all likely cases and just check what's the smallest. With most S numbers still included, small numbers of cells shouldn't be a problem and should extrapolate upwards easily. Or that's the plan, at least. I'll go maybe do that now.
That seems like a good approach. I've added some quick checks to see if 0 or 1 is in the birth list, in which case the program just spits out "0 still lifes", and similarly if none of 0,1,2,3, or 4 are in the survival list. O(1) efficiency in those cases! ;)

Edit: Also, I implemented the (n-2)-by-(n-2) bounding box thing for rules that don't have 1 in the survival list, and the speed-up is quite nice. 7 cells compute about as fast as 6 cells used to compute, 8 cells compute about as fast as 7 cells used to compute, etc. I'll re-upload the script after we figure out another speed-up or two.

Elithrion
Posts: 100
Joined: February 3rd, 2009, 4:02 pm
Contact:

Re: Enumerating Still Lifes (in C)

Post by Elithrion » March 27th, 2009, 12:05 pm

Okay, without the two, the best design seems to be (effectively for 13456789/, since without B, 0 is useless):

Code: Select all

** 
** 
  *
   

* *
 * 
* *
   

 * 
***
 * 
any of those for 5 (so, (n-2)x(n-2))

Code: Select all

*   
.*  
.** 
..* 
...*
for 6 (so that's (n-1)x(n-1)) and

Code: Select all

*    
.*   
.**  
..** 
....*
for 7 (so, (n-2)x(n-2))... at least assuming islands don't add anything meaningful (probably a safe assumption, but maybe not). This is more complicated than I thought. I'll think about it, since further brute force would not be practical, and I'm not convinced this extends to larger things.
Vi veri veniversum vivus vici.

User avatar
Nathaniel
Site Admin
Posts: 861
Joined: December 10th, 2008, 3:48 pm
Location: New Brunswick, Canada
Contact:

Re: Enumerating Still Lifes (in C)

Post by Nathaniel » March 27th, 2009, 12:22 pm

Ah that's some good work actually, it looks like the best that can be done for rules without 2 on the survival list is make up "diagonal" patterns consisting of some combination of the following two patterns, placed repeatedly so that their corners touch:

Code: Select all

*.
**
.*


*..
**.
.**
These can be stabilized on the ends by placing one diagonally-touching cell at either end (which is easily seen as the optimal way to cap the ends). Thus, the a 15-cell still life would look like:

Code: Select all

*
.*
.**
..*
...*
...**
....**
......*
......**
.......*
........*
This gives us an 11-by-11 bounding box, and it would be easy to get formulas for what the bounding boxes are of arbitrary sizes then. We just need to show that these are the biggest possible, which I'm willing to bet they are. I'm beginning to think that islands won't ever play a role in this problem, regardless of ruleset. I'll see if I can pin that down or not though.

Elithrion
Posts: 100
Joined: February 3rd, 2009, 4:02 pm
Contact:

Re: Enumerating Still Lifes (in C)

Post by Elithrion » March 27th, 2009, 2:10 pm

I agree about islands, purely because I tried to imagine some uses for 0 survival and they were all unhelpful.

And that picture looks good. I guess the way to look at it is that the best solution is a diagonal line, but (ignoring the two cells on the ends) it needs at least one additional cell for every three cells to not develop two neighbours. So, bx=by, and: cells(bx) >= bx + (ceil((bx - 2)/3)). I leave the solving for bx to the reader (i.e. I'm lazy and it's not that interesting).

Okay, with regards to first cell location. We can consider it to be the lowest x or y coordinate of any cell on the convex hull of the still life relative to the cell that would give it the highest coordinate. Err... less, confusingly,

Code: Select all

["real" px(c1)] = min(max(px(c1)-px(c2),px(c1)-px(c3),...), max(py(c1)-py(c2),...), max( px(c2)-px(c3),...), ...) 
Well, maybe less confusingly. Anyway, for the resulting px(c1) to be a, we'd need each cell on the hull to be at least a away from the extremes (in x and in y). Less solid conjecture-land time: if we don't have islands, and we use all cells to build connections, this will result in us needing to build three sides, so as to get the four extremes as far apart as possible. To get them all to be a apart, we'll need 3(a-1) cells to link them, and 3 cells to be the extremes. Thus we need 3a cells total to get the real position of the first cell in the row to be a. Thus, if this makes sense and holds up, your guess seems correct, except maybe floor(n/3) instead of ceil - not entirely sure.
Also, if that didn't make sense, let me know and I'll draw a picture.

Now I'll go look at what happens if neither 1 nor 2 gets survival, I think. Should be much more compact.
Vi veri veniversum vivus vici.

FractalFusion
Posts: 52
Joined: March 27th, 2009, 2:07 pm

Re: Enumerating Still Lifes (in C)

Post by FractalFusion » March 27th, 2009, 2:22 pm

Nathaniel wrote:The program seems to crash once it finds about 1,000 still lifes. I'm not sure why yet.
The foundSL array only has array size 1000. You would need to make it larger, or change to a larger array before it overflows.

Edit: I can't read. Elithrion already answered this above.
Last edited by FractalFusion on March 28th, 2009, 1:51 am, edited 2 times in total.

Elithrion
Posts: 100
Joined: February 3rd, 2009, 4:02 pm
Contact:

Re: Enumerating Still Lifes (in C)

Post by Elithrion » March 27th, 2009, 7:17 pm

Okay, for 3456789/-

Code: Select all

4 cells (2x2)

OO
OO

Code: Select all

5 cells (3x3)

.O.
OOO
.O.

Code: Select all

6 cells (3x3)

OO.
OOO
.O.

Code: Select all

7 cells (3x3)

OO.
OOO
.OO

Code: Select all

8 cells (4x4)

.O..
OOO.
.OOO
..O.

or

OO..
OO..
..OO
..OO
so, it looks like tiling blocks and blocks-with-pips-on-their sides from this point onward will be the way to go, giving a sequence (starting with two cells) of: 0,2,2,3,3,3,4,4,5,5,6,6,7,7,8,... I would guess.

Also, enough of that, I think. So far we've narrowed the bounding box a bit, and have absorbed nearly all gains from eliminating duplicates produced via translation and reflection across the vertical. It seems like schemes to deal with reflection across the horizontal and with rotation would offer the greatest remaining gain.
Vi veri veniversum vivus vici.

User avatar
Nathaniel
Site Admin
Posts: 861
Joined: December 10th, 2008, 3:48 pm
Location: New Brunswick, Canada
Contact:

Re: Enumerating Still Lifes (in C)

Post by Nathaniel » March 28th, 2009, 1:53 pm

Alright, I've updated the original post to include v1.01 of this script. The changes since the last version include:

- Takes into account the (n-2)x(n-2) bounding box observation for rules without "1" in their survival string
- Writes the output file in bits and pieces now, so that you may view the still lifes that it has found so far while it is still calculating
- The first cell no longer goes across the first half of the first row, but only goes across the first ceil((n+1)/4) cells in the first row. This bound definitely can't be lowered, and I'm quite sure that you don't miss any still lifes this way (though if someone is uncomfortable with this, I'm always up for a discussion).
- A few other speed-ups that mostly don't make much difference in practice. They include: if "2" or "3" is in the birth list of the rulestring, then stop right away if you have something like "OOO" (for 3) or "O.O" or "OO" (for 2) in the first row, since a birth would then happen above the pattern. Also, the change about checking for reflections after building the first row of the pattern (mentioned earlier in the thread when talking with Elithrion).
- The 1000 still life limit has been raised to 10000. Dynamic multi-dimensional arrays are a pain in C.

Post Reply