Enumerating Still Lifes (in C)

[knightlife]

A while back I played around with coming up with a sort of grammar for P2 oscillators. Turns out it's a lot harder and complicated that I expected, as there are lots of different ways to put various parts together.

I will have to agree on that. I thought about actually showing "track" pieces that could be put together like a train set, but quickly saw that it would take quite a bit of work to show how to use them. Showing by example is fine (unless writing a program that needs the grammar to be defined).

Your collection is awesome.

Its true the 1-2-3-2-1 diamond was created by accident while I was connecting rotated patterns and I was thinking something is wrong, but it worked so I used it. This type of "happy accident" doesn't happen very often...

[hkoenig]

Turns out that that diamond rotor segment can be easily made into an oscillator. Here are the simplest versions, which are just the combination of smaller 12 and 14 bit oscillators.

Code: Select all

x=83, y=63
3o19b3o$4bo22b2o$b2o2b2o16b2obobo2$bo2bo19bobo$3bo23bo$3bo22b2o6$24b3o18b
2o$b3o41bobo$23bo2b2o$o2b2o18bo21bo2b2o$o22bobo2bo15bo$obo2bo21bo16b2obo2b
o$4bo21bo2bob2o16bo$3bo2bobo23bo15bo2bob2o$8bo18b2o2bo22bo$4b2o2bo40b2o2b
o$29bobo$5b3o22b2o19bobo$52b2o6$3o3b2o15b3o3b2o14b3o3b2o12b3o3b2o$7bo22bo21b
o19bo$bob2obo17bob2obo16bob2obo14bob2obo$o22bo21bo19bo$2o3b3o15b2o3b3o14b
2o3b3o3b2o7b2o3b3o3b2o$10b2o20bo24bo19bo$6b2obobo17b2o2b2o16bob2obo14bob2ob
o$50bo19bo$7bobo19bo2bo17b2o3b3o12b2o3b3o3b2o$10bo20bo50bo$9b2o20bo44bob2ob
o$75bo$75b2o3b3o3$24b3o$46b3o$3o20bo2b2o$4bo18bo7b3o11bo2b2o5bo$b2o2b2o16b
obo2bo6bo9bo9bo$27bo3bo3bo9bobo2bo3bo2bo$bo2bo21bo2bo3bobo13bo8b2o$3bo26b
o2bo14bo2bobobo$2bo2bobo17bobo3bo21bobobo$7bo17bobobo19b2o2bo$3b2o2bo17bo$50b
3o$4b3o47bo$51b2o2b2o2$51bo2bo$53bo$53bo!

Actually, these "happy accidents" seem to happen quite a bit. In this case, I'm surprised that the idea of overlapping the 3 bit line was never tried, as now it seems to be obvious, now. It also adds a new grammar element, as shown by the third and fourth lines above.

[knightlife]

hkoenig wrote:
Here are the simplest versions, which are just the combination of smaller 12 and 14 bit oscillators.

Pretty flexible grammar wouldn't you say? It seems P2 oscillators are almost as extensible as still life patterns. So enumerating P2 oscillators is almost as easy as still lifes? As you said before, still life is just a degenerate form of oscillator. P1 grammar may actually be less flexible than P2 grammar.

[Lewis]

P1 grammar may actually be less flexible than P2 grammar.

Would all periods of oscillator have a grammar like this?

[knightlife]

Would all periods of oscillator have a grammar like this?

I took a "random" P10 oscillator and extended it, a simple grammar:

Code: Select all

x = 31, y = 69, rule = B3/S23
2$15bo$16b2o$14b2o$16bo2$11bo5bo$9bobo4bobob2o$10bobo2bo2bobo2bo$10bo
3bo$15b2o$20bobo2bo$15b2o2bobo4b2o$15bo4bo3b2o$19bo6bo3$9bo6bo$10b2o3b
o4bo$8b2o4bobo2b2o$10bo2bobo$19b2o$21bo3bo$12bo2bobo2bo2bobo$14b2obobo
4bobo$18bo5bo3$9bo5bo$7bobo4bobob2o$8bobo2bo2bobo2bo$8bo3bo$13b2o$18bo
bo2bo$13b2o2bobo4b2o$13bo4bo3b2o$17bo6bo2$17bo$7bo6bo$8b2o3bo4bo$6b2o
4bobo2b2o$8bo2bobo$17b2o$19bo3bo$10bo2bobo2bo2bobo$12b2obobo4bobo$16bo
5bo3$7bo5bo$5bobo4bobob2o$6bobo2bo2bobo2bo$6bo3bo$11b2o$16bobo2bo$11b
2o2bobo4b2o$11bo4bo3b2o$15bo6bo$12bo$17bo$15bobo$16bobo$16bo!

The link for the basic P10 oscillator is http://pentadecathlon.com/lifeNews/2009 ... ors_4.html
The stack of two has been extended to a stack of five (symmetry helps a lot).

By connecting using the surrounding P2 clock oscillators:

Code: Select all

x = 84, y = 148, rule = B3/S23
17$35bo$36b2o$34b2o$36bo2$31bo5bo$29bobo4bobob2o$30bobo2bo2bobo2bo$30b
o3bo$35b2o$40bobo2bo$35b2o2bobo4b2o$35bo4bo3b2o$39bo6bo3$29bo6bo$30b2o
3bo4bo$28b2o4bobo2b2o$30bo2bobo$39b2o$41bo3bo$32bo2bobo2bo2bobo$34b2ob
obo4bobo$38bo5bo3$29bo5bo$27bobo4bobob2o$28bobo2bo2bobo2bo$28bo3bo$33b
2o$38bobo2bo$33b2o2bobo4b2o$33bo4bo3b2o$37bo6bo3$27bo6bo$28b2o3bo4bo$
26b2o4bobo2b2o$28bo2bobo$37b2o$39bo3bo$30bo2bobo2bo2bobo$32b2obobo4bob
o$36bo5bo3$27bo5bo$25bobo4bobob2o$26bobo2bo2bobo2bo$26bo3bo$31b2o$36bo
bo2bo$31b2o2bobo4b2o$31bo4bo3b2o$35bo6bo$32bo$37bo5bo$35bobo4bobob2o$
36bobo2bo2bobo2bo$36bo3bo$41b2o$46bobo2bo$41b2o2bobo4b2o$41bo4bo3b2o$
45bo6bo3$35bo6bo$36b2o3bo4bo$34b2o4bobo2b2o$36bo2bobo$45b2o$47bo3bo$
38bo2bobo2bo2bobo$40b2obobo4bobo$44bo5bo3$35bo5bo$33bobo4bobob2o$34bob
o2bo2bobo2bo$34bo3bo$39b2o$44bobo2bo$39b2o2bobo4b2o$7bo31bo4bo3b2o$8b
2o33bo6bo$6b2o$8bo$33bo6bo$3bo5bo13bo10b2o3bo4bo$bobo4bob4o7bobo8b2o4b
obo2b2o$2bobo2bobob3o8bobo9bo2bobo$2bo3bobo13bo20b2o$7bo37bo3bo$7b2o3b
2o3bo6bo11bo2bobo2bo2bobo$7b2o2bobo4b2o3bobob2o9b2obobo4bobo$7b2o2b2o
3b2o4bobo2b2o13bo5bo$18bo2bobo$22bo40bo$13bo13b2o4bo5bo13bo10b2o$11bob
o8b2o2bobo2bobo4bobob2o7bobo8b2o$12bobo7b2o2b2o4bobo2bo2bobo2bo6bobo9b
o$12bo19bo3bo15bo$37b2o$27bo14bobo2bo6bo9b2o2b2o$28b2o7b2o2bobo4b2o3bo
bob2o4bobo2b2o$26b2o9bo4bo3b2o4bobo2b2o4b2o$28bo12bo6bo2bobo15bo$38bo
13bo15bobo2bo$43bo13b2o4b2o2bobo4b2o$41bobo8b2o2bobo4b2obobo3b2o$42bob
o7b2o2b2o9bo6bo$42bo$69bo$57bo9bobo$58b2o8bobo$56b2o10bo$58bo!

Now this P10 oscillator has its own 2D grammar. But P2 grammar connects different kinds of oscillators in a smooth "seamless" fashion.

[dvgrn]

But P2 grammar connects different kinds of oscillators in a smooth "seamless" fashion.

Nicolay Beluchenko wrote his "Oscichem" (oscillator chemistry) series of articles five years or so ago, proposing an interesting pile of new terminology based on analogies to chemical bonds and the like.

Based on the above link, parts 2 and 3 can be found with varying amounts of difficulty. It seems I never got a final draft of article #3 from Nicolay, so it's still in text-only format -- and the Javascript isn't working properly (or perhaps is nonexistent) for the majority of article #2... Heigh-ho, more work to do. Life is a toil, as the old song says. I'll post a full set of links when I get this straightened out.

[knightlife]

dvgrn wrote:
an interesting pile of new terminology based on analogies to chemical bonds

This definitely crosses over into the wick and agar areas of interest. Attempts to classify quickly become unbounded in several ways.

I am not complaining. More toil, but it is fun toil. Maybe there is a unified super-grammar theory for all possible oscillators.

Edit:
Challenge: connect P1, P2, P3, P5, P7, P11 ... oscillators non-trivially (oscillators that have a period that is a prime number).
Can such an oscillator continue to be made larger by continuing the prime number sequence?
Prove it possible or not possible even through some prime period oscillators have not been discovered yet.
Never mind.
Connecting all by embedding "rotors" in a giant still life should be possible. Is that trivial?
Could a Herschel conduit be embedded too? Would it still be a single oscillator if there were many of these embedded conduits?
Never mind.
But it would be fun to build a Herschel conduit inside a giant (polyplet) still life.

[dvgrn]

Nicolay Beluchenko wrote his "Oscichem" (oscillator chemistry) series of articles five years or so ago, proposing an interesting pile of new terminology based on analogies to chemical bonds and the like... I'll post a full set of links when I get this straightened out.

Just for the record, here are the links:

#1: Barber-Chemistry
#2: Chemistry of Period-2 Oscillators
#3: Oscichemistry (definitions and summary)

Oscichem #3 might still change a bit, since there have been some new discoveries since it was written, and the provisional updates I put in haven't gone through a final review yet.

[Tropylium]

Bumping with a possibly naïve question: wouldn't a surefire way to weed out translations (vs. fussing with floor/ceiling functions) be to progress one bounding box at a time, and require the still life to actually touch all the edges? With S0 or S1, there might be no more than 2 cells on the edges, and the preblock in something like B4/S2 is another exception with 3 edge cells, but in all other cases you'd need to have 4 cells on the edges of the bounding box. That only leaves rotations/reflections, which should be largely handleable by checking what goes on in row 1 and column 1.

BTW Nathaniel, I saw a note on the wiki from a few years ago that you were enumerating still lifes for B3/S012345678. Any results yet?

—As for the p2 grammar derail, one connection I have not seen around is integration of the clock and related oscs into the ring-of-fire series:

Code: Select all

x = 36, y = 46, rule = B3/S23
5bo$3b2o$5b2o$4bo3$5bo$3b2o$5b2o$2b3o$5b3o$3b2o20bo$5b2o19b2o$4bo19b2o
$26b3o$23b3o$5bo20b4o$3b2o17b4o$5b2o19b5o$2b3o16b5o$5b3o18b6o$b4o15b4o
2bo$5b4o14bo5b4o$2b3o14b4o6bo$5b3o22b4o$3b2o13b3o$5b2o14bo10b3o$4bo12b
4o10bo$31b5o$16b3o10b2o$5bo13bo8bobo2b2o$3b2o10b5o8bobobo$5b2o13b2o3b
2obobo2bo$2b3o11b2o2bobobobobo2bo$5b3o10bobobobobo2bo$b3o13bo2bobobo2b
o$4b5o10bo2bo2bo$4o17bobo$4b6o$b3o$5b4o$2b3o$5b3o$3b2o$5b2o$4bo!

[Nathaniel]

BTW Nathaniel, I saw a note on the wiki from a few years ago that you were enumerating still lifes for B3/S012345678. Any results yet?

Very strange -- I have no idea what happened mid-computation back then that caused me not to keep/upload/finish computing the results. It's running again and I should have the still life counts up to 9 cells by tomorrow morning. I'll try to do the 10 cell count sometime soon, but my computer currently has other things it needs to be doing.

Edit: Well, it's three days later, and the computation is still running. It seems I quite wildly underestimated how long the 9 cell count would take. It's at 1329 9-cell still lifes so far.

[Nathaniel]

Well, the computation randomly died (most likely a memory issue) after computing for several days. The still life counts for 1 - 8 cells are: 1, 2, 1, 6, 8, 23, 65, 337. The number of 9-cell still lifes is greater than 1300, but that's all I know. The still lifes themselves are attached.

[Apple Bottom]

Just to breathe some life into this thread again... are there any other tools for enumerating (or at the very least counting) still lifes? Nathaniel's code is very useful, but not particularly fast; when I just tested it, enumerating all the 10-bit still lifes in Conway's Game of Life took 5704.26 seconds, and the time required grows exponentially as the desired population goes up. (I'd estimate that 11-bitters would take around 3 days, and the 12-bitters around 5 months.)

Mark Niemiec has computed the number of still lifes up to 24 bits. Any word on how this was achieved -- software used, hardware used, time required? Having more information on this would allow others to verify his numbers, and if the software was available it could perhaps be employed to carry out similar calculations for other cellular automata.

That's the reason I'm asking, BTW -- although Catagolue can provide some good estimates for well-searched rules, it would still be nice to properly compute the numbers.

[BlinkerSpawn]

The description in Niemiec's page contains a good description of his process but doesn't contain the specifics you're looking for or any actual downloadable code.

[Apple Bottom]

The description in Niemiec's page contains a good description of his process but doesn't contain the specifics you're looking for or any actual downloadable code.

A good start, however. Thanks for the link!

[simeks]

Just to breathe some life into this thread again... are there any other tools for enumerating (or at the very least counting) still lifes?

I decided to make an attempt with this, and I've been able to write a program that counts still lifes in B3/S23 pretty efficiently.
So far I have confirmed the numbers reported by Mark Niemiec for bit counts from 4 to 23.
However for 24 bits my program finds 6 more scrict still lifes and 1 more pseudo still life than previously reported. My numbers are 4051732 and 3069135 respectively.
There is no database of 24 bit still lifes from Mark Niemiec's search, or anyone who has access to the code used for it? It would be interesting to find out if the extra still lifes I've found have any special propertly...

Since my program reports more results than previously thought, it would be easy to confirm that this is correct if someone would be willing to write an independent script that takes a database from my program and verifies that all generated results are indeed valid 24 bit still lifes and that they are all different.
Would anyone be interested in doing this?

I'm currently running the search for 25 bit still lifes, I will report the result soon.
EDIT: The result I get is 9971377 strict still lifes and 7906676 pseudo still lifes.

I will do a bit more work on my program, but then I will I post it here.

[Apple Bottom]

Since my program reports more results than previously thought, it would be easy to confirm that this is correct if someone would be willing to write an independent script that takes a database from my program and verifies that all generated results are indeed valid 24 bit still lifes and that they are all different.
Would anyone be interested in doing this?

This sounds easy enough, so sure. Let me know where I can grab the database and I'll take a stab.

I'm currently running the search for 25 bit still lifes, I will report the result soon.
I will do a bit more work on my program, but then I will I post it here.

Excellent, looking forward to both your program and your further results! How fast is the program, BTW? And does it work (or can it be adapted to work) for other rules as well?

Once we've got some new/corrected results, someone should also edit A019473 on the OEIS, BTW.

[simeks]

This sounds easy enough, so sure. Let me know where I can grab the database and I'll take a stab.

Great! I will have to re-run the search to actually generate the database and not just the count, give me a few hours...

The database will be two textfiles of this format:

Code: Select all

3.2A$3.A$2A.A$2A.2A!
3.2A$2.A.A$.A.A$A.A$2A!
4.2A$.2A2.A$A2.2A$2A!
4.2A$4.A$.2A.A$A2.A$2A!
4.A$3.A.A$4.A$.3A$A$2A!
A.2A.2A$2A.2A.A!
5.2A$A.2A2.A$2A.2A!
4.A$3.A.A$A.A2.A$2A3.2A!
5.2A$6.A$5.A$4.A$3.A$A.A$2A!
6.2A$5.A.A$4.A$3.A$A.A$2A!
5.2A$2.2A2.A$A2.2A$2A!
4.2A$5.A$2A2.A$A2.A$.2A!
5.2A$2A2.A.A$A2.A$.2A!
4.2A$3.A.A$2A2.A$A.2A!
4.2A$3.A.A$3.A$2A.A$A.A!
5.A$2A2.A.A$A.A2.A$3.2A!
5.A$3.3A$2.A$3.A$3A$A!
2.2A$.A2.A$.A.A$2A.2A!
4.2A$2A3.A$.A2.A$.A.A$2.A!
4.A$3.A.A$3.2A$.2A$A.A$.A!
2.A$.A.A$A.A.A$.A2.A$2.2A!
4.A$3.A.A$2.A.A$.A.A$A.A$.A!
5.A$3.3A$2.A$.A.A$A.A$.A!
4.2A$.A2.A$A.A.A$.A.A$2.A!
4.2A$4.A$.2A.A$A2.A$.2A!

Code: Select all

4.2A$2A.A.A$2A.2A!
4.2A$5.A$2A.A$2A.2A!
5.2A$2A.A2.A$2A.2A!
4.A$2A.A.A$2A.A.A$4.A!
A.2A.2A$2A.A.2A!
5.A$.2A.A.A$A.A.2A$.A!
.A3.A$A.A.A.A$.2A.2A!

I'm sure you're aware of this, but the important part of the verification will be to check that the islands of the results are properly connected through at least one off-cell with more than 3 on-cell neighbours.

How fast is the program, BTW? And does it work (or can it be adapted to work) for other rules as well?

The running time for 24 bits is about 4 hours, but I can see a simple way to improve speed by a factor of 2 or 3. The asymptotic speed is around O(2.6^n), the same as reported by Mark Niemiec.
I'm sure the program can be adapted for other rules, but there are some assumptions about the properties of B3/S23 that will need some consideration.

EDIT: By the way, the program does not need to store generated still lifes in memory, so patience is the only limit to the bit count we can reach.

[Apple Bottom]

The database will be two textfiles of this format:

Right -- one (pseudo) still life per line, then, in a format I'm sure I've seen before and that's easy enough to understand anyway. Got it.

I'm sure you're aware of this, but the important part of the verification will be to check that the islands of the results are properly connected through at least one off-cell with more than 3 on-cell neighbours.

Oh, don't count on me being aware of much of anything. My knowledge of cellular automata is -- uneven. Thanks for the tip, though!

The running time for 24 bits is about 4 hours, but I can see a simple way to improve speed by a factor of 2 or 3. The asymptotic speed is around O(2.6^n), the same as reported by Mark Niemiec.
I'm sure the program can be adapted for other rules, but there are some assumptions about the properties of B3/S23 that will need some consideration.

That's not bad at all - it puts counts up to 28 bits within easy reach.

EDIT: actually, thinking about some more now I'm probably not qualified to write a verification tool; I just remembered and looked up the quad pseudo still life, and I'm not at all sure how you'd detect such patterns as pseudo-objects, short of trying to separate their constituent islands in every possible combination and checking if the results are stable. (After all, while the still lifes making up this particular object only consist of one island each, that needn't be true in the general case.) This would not only take time (naively, O(2^n) for a still life with n islands; granted n would be guaranteed to be quite small for the small objects we're talking about), it might also well exceed my limited programming skills.

So I apologize for having volunteered too eagerly, biting off more than I realized, only to find I couldn't chew it. Someone else will have to do this, someone who actually knows what they're doing.

[simeks]

EDIT: actually, thinking about some more now I'm probably not qualified to write a verification tool; I just remembered and looked up the quad pseudo still life, and I'm not at all sure how you'd detect such patterns as pseudo-objects, short of trying to separate their constituent islands in every possible combination and checking if the results are stable. (After all, while the still lifes making up this particular object only consist of one island each, that needn't be true in the general case.) This would not only take time (naively, O(2^n) for a still life with n islands; granted n would be guaranteed to be quite small for the small objects we're talking about), it might also well exceed my limited programming skills.

This is pretty much how my program does this part, but I don't think it will be necessary to do this for the verification - it would be enough to verify that the union of the strict and pseudo still lifes are all valid 24-bit still lifes without duplicates, and not worry about if they are correctly categorized as strict or pseudo still lifes. If that checks out we will at least know that a few still lifes were missing in Mark Niemiec's result.

[Apple Bottom]

it would be enough to verify that the union of the strict and pseudo still lifes are all valid 24-bit still lifes without duplicates, and not worry about if they are correctly categorized as strict or pseudo still lifes. If that checks out we will at least know that a few still lifes were missing in Mark Niemiec's result.

Hmm. So for that, wouldn't it be enough to convert them all to apgcode format and verify there's no duplicate entries on the list?

[chris_c]

it would be enough to verify that the union of the strict and pseudo still lifes are all valid 24-bit still lifes without duplicates, and not worry about if they are correctly categorized as strict or pseudo still lifes. If that checks out we will at least know that a few still lifes were missing in Mark Niemiec's result.

Hmm. So for that, wouldn't it be enough to convert them all to apgcode format and verify there's no duplicate entries on the list?

If you converted them all to apgcode format, verified that everything was of the form xs24_??? and checked that there are no duplicates then that would tell us that all of simeks' patterns are distinct P1 patterns having 24 bits. That would be a good start but it wouldn't tell us if every pattern was either a strict or pseudo still life. To prove that you could run each pattern through a census using apgsearch 1.0 or you could try the following code which is largely taken from a script I posted recently here. Note that this is slow python code that was hacked together at speed... even if it is correct it may not be fast enough for the job....

Code: Select all

import golly as g

FILENAME = "simeks_big_list_of_rle.txt"

deltas = [(1,0), (1,1), (0,1), (-1,1), (-1,0), (-1,-1), (0,-1), (1,-1)]

def cnt(x, y, cells):
    return sum((x+dx, y+dy) in cells for dx, dy in deltas)

# Define a cell as "interesting" if it is on or if it has at least 3
# live neighbors. This function returns True if the set of interesting
# cells is connected. So bi-blocks are semi-strict but tubs with
# offset (4,0) and blocks with offset (3,3) are not.
def is_semi_strict(cells):
   
    if not cells:
        return True

    for P in cells:
        break

    new_spread = set([P])
    spread = set([P])

    old_size = 0
    new_size = 1

    while new_size > old_size:

        next_spread = set()
        for x, y in new_spread:
            for dx, dy in deltas:
                if (x+dx, y+dy) in cells:
                    next_spread.add((x+dx,y+dy))
                else:
                    if cnt(x+dx, y+dy, cells) >= 3:
                        for ddx, ddy in deltas:
                            if (x+dx+ddx, y+dy+ddy) in cells:
                                next_spread.add((x+dx+ddx,y+dy+ddy))

        new_spread = next_spread
        spread.update(new_spread)

        old_size = new_size
        new_size = len(spread)

    return len(cells) == len(spread)

count = 0
with open(FILENAME) as f:
    for s in f:
        if count & 1023 == 0:
            g.show(str(count))
        cell_list = g.parse(s)
        cell_set = set(zip(cell_list[::3], cell_list[1::3]))
        if not is_semi_strict(cell_set):
            g.putcells(cell_list)
            g.exit(s + "is not strict or pseudo!")
        count += 1

g.exit("Success " + str(count))

[simeks]

If you converted them all to apgcode format, verified that everything was of the form xs24_??? and checked that there are no duplicates then that would tell us that all of simeks' patterns are distinct P1 patterns having 24 bits. That would be a good start but it wouldn't tell us if every pattern was either a strict or pseudo still life. To prove that you could run each pattern through a census using apgsearch 1.0 or you could try the following code which is largely taken from a script I posted recently ...

Thanks!
(I've posted the database for 24 bit still lifes here)
EDIT: This database was a bit too big for GitHub, so I've removed it. Use the program posted here to generate it locally instead an about an hour!

[Scorbie]

Not sure if this is enough, but is_semi_strict made 2.5x faster; not sure if the code has no bugs, though.
(Note: I changed deltas.)

EDIT: I think it has some errors... Sorry
EDIT2: Fixed, but not tested. Does anyone have any test cases?

Code: Select all

import golly as g
from collections import Counter

FILENAME = "test.txt"
deltas = [(1,0), (1,1), (0,1), (-1,1), (0, 0), (-1,0), (-1,-1), (0,-1), (1,-1)]

# Define a cell as "interesting" if it is on or if it has at least 3
# live neighbors. This function returns True if the set of interesting
# cells is connected. So bi-blocks are semi-strict but tubs with
# offset (4,0) and blocks with offset (3,3) are not.
def is_semi_strict(cells):

    neighbors = {(x, y): {(x+dx, y+dy) for dx, dy in deltas} for x, y in cells}
    neighbor_counts = Counter()
    for c in cells:
        neighbor_counts.update(neighbors[c])
    interesting_cells = cells.union(c for c in neighbor_counts
                                    if neighbor_counts[c]>3)
    # see if all "blobs" are interconnected:
    blobs = []
    for x, y in interesting_cells:
        newblob = (neighbors.get((x, y), {(x+dx, y+dy) for dx, dy in deltas})
                   & interesting_cells)
        for blob in blobs[:]:
            if blob & newblob:
                blobs.remove(blob)
                newblob |= blob
        blobs.append(newblob)
    return len(blobs) == 1

count = 0
with open(FILENAME) as f:
    for s in f:
        if count & 1023 == 0:
            g.show(str(count))
        cell_list = g.parse(s)
        cell_set = set(zip(cell_list[::3], cell_list[1::3]))
        if not is_semi_strict(cell_set):
            g.putcells(cell_list)
            g.exit(s + "is not strict or pseudo!")
            g.show("{} is not strict or pseudo!".format(s))
        count += 1
g.exit("Success " + str(count))

I got the "blob" algorithm from a good solution by someone called Sim0000 from checkio, but unfortunately the site requires one to solve the problem and wait for 24h to view others' solutions, so I couldn't properly cite the source.

EDIT: Wow, all checks of 24bits < 1m is amazing! The script above should take about an hour.

[chris_c]

Thanks!
I've posted the database for 24 bit still lifes here

My python script was too slow so I wrote something in C instead:

Code: Select all

#include "stdio.h"

void add(int x, int y, int z, int *a, int *b) {

    int w = y ^ z;
    *a = x ^ w;
    *b = (x & w) | (y & z);

}

//add to x any cells having 4 or more neighbors
void fill4(unsigned x[]) {

    unsigned i, a, b, c, d, row0[32], row1[32];

    for (i = 0; i < 32; i++)
        add(x[i], x[i] << 1, x[i] >> 1, &row0[i], &row1[i]);

    for (i = 0; i < 32; i++) {

        int row0m1 = i > 0 ? row0[i-1] : 0;
        int row0p1 = i < 31 ? row0[i+1] : 0;
        add(row0[i], row0m1, row0p1, &a, &b);

        int row1m1 = i > 0 ? row1[i-1] : 0;
        int row1p1 = i < 31 ? row1[i+1] : 0;
        add(row1[i], row1m1, row1p1, &c, &d);
        
        x[i] |= d | (b & c); //it turns out that a is unused
    }
}

int is_connected(unsigned x[]) {

    unsigned i, update, y[32], z[32];

    for (i = 0; i < 32; i++)
        y[i] = 0;

    for (i = 0; i < 32; i++)
        if (x[i]) {
            y[i] = x[i] & -x[i];
            break;
        }

    // now y is a 0 or 1 bit subset of x

    do {

        // spread each bit of y to the surrounding 8 bits and store in z

        for (i = 0; i < 32; i++)
            z[i] = y[i] | (y[i] << 1) | (y[i] >> 1);
        
        for (i = 0; i < 31; i++)
            z[i] |= z[i+1];
        
        for (i = 1; i < 32; i++)
            z[i] |= z[i-1];

        // trim back down to x
        for (i = 0; i < 32; i++)
            z[i] &= x[i];

        // check if z is bigger than y and update y
        update = 0;

        for (i = 0; i < 32; i++) {
            update |= z[i] & ~y[i];
            y[i] = z[i];
        }

    } while(update);

    // check if x is a subset of y

    for (i = 0; i < 32; i++)
        if (x[i] & ~y[i])
            return 0;

    return 1;
}

int main() {

    char c, *p, s[128];
    unsigned i, x[32], b, d;
    while(gets(s)) {
        for (i = 0; i < 32; i++)
            x[i] = 0;

        i = d = 0;
        b = 1;
        p = s;

        while((c = *p++)) {
            if ('0' <= c && c <= '9')
                d = 10 * d + (int) (c - '0');
            else {
                if (d == 0) d = 1;
                while (d > 0) {
                    if (c == 'A') {
                        x[i] |= b;
                        b <<= 1;
                    } else if (c == '.') {
                        b <<= 1;
                    } else if (c == '$') {
                        i++;
                        b = 1;
                    }
                    d--;
                }
            }
        }

        fill4(x);

        if(!is_connected(x))
            printf("Fail %s\n", s);
    }

    return 0;
}

It is meant to check that the pattern on each line is connected via on cells and off cells with at least 4 neighbours. I can run "./still_test < 24s.txt" and "./still_test < 24p.txt" without seeing the string "Fail" in less than 1 minute.

[Apple Bottom]

It is meant to check that the pattern on each line is connected via on cells and off cells with at least 4 neighbours. I can run "./still_test < 24s.txt" and "./still_test < 24p.txt" without seeing the string "Fail" in less than 1 minute.

Excellent! BTW, is Mark Niemiec reading this thread? It'd be very interesting to see which six objects appear on Simeks's list but not in his database.

Second question: Simeks, does your program's design allow for dividing up the task of enumerating still lives of a given population? With running time growing exponentially, this would be useful if we wanted to enumerate, say, all the 30-bitters (which otherwise would take an estimated two months, roughly).

Finally: what's the best place to store the resulting databases? (I assume we do want to store them somewhere, for later verification and also to avoid requiring interested users to recompute them.) The full list of 30-bitters would take an estimated 130-150 GiB; xz (-9v) achieves a compression ratio of about 0.07 on the 24-bitters, but that would still leave us with ~10 GiB. archive.org, perhaps?