Enumerating Still Lifes (in C)

For scripts to aid with computation or simulation in cellular automata.
hkoenig
Posts: 258
Joined: June 20th, 2009, 11:40 am

Re: Enumerating Still Lifes (in C)

Post by hkoenig » September 30th, 2017, 2:44 pm

Over the past few weeks I've been updating my Life object data files. Going through several years of posting here and updating the oscillator and spaceship discoveries. I've put together SOF files of Still Life objects up to 28 bits. Here's the resulting file size (including indexing metadata) in megabytes:

22 -- 32
23 -- 82
24 -- 210
25 -- 537
26 -- 1380
27 -- 3520
28 -- 8920

Total size for all SOF file, including oscillators and spaceships, is around 28Gig. That doesn't include the raw results for the pseudo-objects, which haven't been processed. And not sure if I can handle sorting the 25Gig of 29 bit files, which are still being generated.

As others have said, RLE format is not the right way to present object lists such as these. I've written display apps and command line tools that allow for the display, conversion, normalizing, sorting, and searching of all those files. Eventually, I'd like to set up a SQLite database which includes all the Glider constructions.

(The database has both SOF and a modified apgcode --there's the bit encoding to the right of the underscore, while putting size/period/speed info on the left. (e.g. LWSS = 9P4H2V0_6frc Pulsar = 48P3_co9nas0san9oczgoldlo0oldlogz1047210127401) )

The object directories, including the RLE files and the index thumbnails, shown on pentadecathlon.com are generated by the server from the SOF files. It's not that hard to do.

User avatar
Majestas32
Posts: 549
Joined: November 20th, 2017, 12:22 pm
Location: 'Merica

Re: Enumerating Still Lifes (in C)

Post by Majestas32 » June 27th, 2018, 1:16 am

Is there any hope of such a script supporting non totalistic rules?
Searching:
b2-a5k6n7cs12-i3ij4k5j8
b2-a3c7cs12-i

Currently looking for help searching these rules.

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 » April 5th, 2019, 12:50 pm

33-bit still life counts:

Strict: 14223867298
Pseudo: 15851861075

Pseudo still life results of interest include:
- Gabriel Nivasch's 34-bit Quad pseudo still life is minimal (i.e., there is no 33-bit pseudo still life that can be partitioned into 4 stable pieces, but not 2 or 3).
- There are exactly 11 33-bit pseudo still lifes that can be partitioned into 3 stable pieces, but not 2. They are displayed here:

Code: Select all

x = 80, y = 39, rule = B3/S23
57bo$4b2ob2o13bo33bobo16bo$4b2obobo11bobob2o11bobob2o12bo2bo9b2obobobo
$9bo9b3ob2obo9b3ob2obo8b2ob2o3bo9bob2o2bo$3bob2o2b2o7bo16bo16bo8bo7bo
6b2o$b3ob2o3bo8bob2ob2o10bob2ob2o10bob2o5bo6b2ob2o4bo$o8bo8b2ob2obo10b
2ob2obobo8b2ob2o2b3o8bob2o2b2o$2o6bo16bo16bo9bo6bo9bo6bo$2bob2obo9bob
2ob3o9bob2ob3o11b3obobo10b3obobo$2b2ob2o10b2obobo11b2obobo15bob2o13bob
2o7$5b2o16bo15b2o17bo16bo$2obo2bo10bob2obobo9bob2o2bo11b2obobobo9bob2o
bobo$bob2o2b2o8b2ob2o2bo9b2ob2o2b2o10bob2o2bo9b2ob2o2bo$o8bo14b2o17bo
8bo6b3o14b3o$2ob2o4bo7b2ob2o4bo7b2ob2o4bo8b2ob2o5bo6b2ob2o5bo$bob2o2b
2o9bob2o2b2o9bob2o2b2o10bob2o4bo8bob2o4bo$o6bo9bo6bo9bo6bo10bo7bo8bo7b
o$b3obobo10b3obobo10b3obobo11b3obobo10b3obobo$3bob2o13bob2o13bob2o14bo
b2o13bob2o6$41b2o$36b2obo2bo$36bob2obo$41b2o$36bob2o$34b3ob2ob2o$33bo
7bo$34b3ob2obo$36bobobo!
The results for each of the 100 subsets of the search space for 33 bits are attached to this post. The last remaining open question that I can think of is whether or not Nivasch's 34-bit quad pseudo still life is unique (or if there exist other such 34-bitters).
Attachments
33bit_counts.zip
(30.77 KiB) Downloaded 454 times

mniemiec
Posts: 1590
Joined: June 1st, 2013, 12:00 am

Re: Enumerating Still Lifes (in C)

Post by mniemiec » April 5th, 2019, 3:02 pm

Nathaniel wrote:33-bit still life counts: ... There are exactly 11 33-bit pseudo still lifes that can be partitioned into 3 stable pieces, but not 2. They are displayed here: ...
Excellent! I assume that the 32-bit three-partition pseudo-still-life is unique?

User avatar
dvgrn
Moderator
Posts: 10612
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Enumerating Still Lifes (in C)

Post by dvgrn » April 5th, 2019, 3:29 pm

mniemiec wrote:
Nathaniel wrote:33-bit still life counts: ... There are exactly 11 33-bit pseudo still lifes that can be partitioned into 3 stable pieces, but not 2. They are displayed here: ...
Excellent! I assume that the 32-bit three-partition pseudo-still-life is unique?
That result was reported with Nathaniel's 32-bit still life count a couple of years ago.

googoIpIex
Posts: 292
Joined: February 28th, 2019, 4:49 pm
Location: Sqrt(-1)

Re: Enumerating Still Lifes (in C)

Post by googoIpIex » April 5th, 2019, 4:02 pm

How long did the search take?
woomy on a vroomy

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 » April 5th, 2019, 5:23 pm

googoIpIex wrote:How long did the search take?
The 33-bit search took about 250 CPU days, which means we're looking at roughly 625 or so CPU days for a 34-bit search.

User avatar
testitemqlstudop
Posts: 1367
Joined: July 21st, 2016, 11:45 am
Location: in catagolue
Contact:

Re: Enumerating Still Lifes (in C)

Post by testitemqlstudop » August 4th, 2019, 9:33 pm

Is it possible to port this to nontotalistic rules?

User avatar
Freywa
Posts: 877
Joined: June 23rd, 2011, 3:20 am
Location: Singapore
Contact:

Re: Enumerating Still Lifes (in C)

Post by Freywa » October 6th, 2019, 10:52 am

I've made a Patreon post with an attachment listing out Niemiec's (corrected) original tabulation of all strict and pseudo still lifes to 24 bits, with apgcodes.

Of course, the attachment is too large to upload directly here, so it is there.
Princess of Science, Parcly Taxel

Code: Select all

x = 31, y = 5, rule = B2-a/S12
3bo23bo$2obo4bo13bo4bob2o$3bo4bo13bo4bo$2bo4bobo11bobo4bo$2bo25bo!

User avatar
testitemqlstudop
Posts: 1367
Joined: July 21st, 2016, 11:45 am
Location: in catagolue
Contact:

Re: Enumerating Still Lifes (in C)

Post by testitemqlstudop » October 6th, 2019, 7:50 pm

You do not need to be 18+ to view a list of apgcodes.

User avatar
Freywa
Posts: 877
Joined: June 23rd, 2011, 3:20 am
Location: Singapore
Contact:

Re: Enumerating Still Lifes (in C)

Post by Freywa » October 6th, 2019, 9:55 pm

testitemqlstudop wrote:
October 6th, 2019, 7:50 pm
You do not need to be 18+ to view a list of apgcodes.
I need a forum admin to upload the 43 MB zip file here. Anyway, the original location of said file was in my Google Drive here; I am merely looking for a place more permanent than Google Drive to store this.

There is also a cheekier point. A raw listing of such a large haul of data is bordering on the obscene.
Princess of Science, Parcly Taxel

Code: Select all

x = 31, y = 5, rule = B2-a/S12
3bo23bo$2obo4bo13bo4bob2o$3bo4bo13bo4bo$2bo4bobo11bobo4bo$2bo25bo!

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 » January 9th, 2020, 1:16 pm

34-bit still life counts:

Strict: 35422864104
Pseudo: 41058173683

Pseudo still life results of interest include:
- Gabriel Nivasch's 34-bit Quad pseudo still life is unique (i.e., there is no other 34-bit pseudo still life that can be partitioned into 4 stable pieces, but not 2 or 3).
- There are exactly 26 34-bit pseudo still lifes that can be partitioned into 3 stable pieces, but not 2 (Nivasch's quad pseudo still life is not included here, since it requires 4, not 3). They are displayed here:

Code: Select all

x = 102, y = 81, rule = B3/S23
61b2o$27bo15b2obo13bo2bo$8b2o13b2obobo13bob2obo11bo2b2o16bo$3b2obo2bo
12bob2o2bo12bo5bo10bo5b2o13bobob2o$3bob2obo12bo6b2o10bo6b2o8bo6bo12b3o
b2obo$8b2o10bo8bo9bo8bo7bo8bo10bo$o2bob2o12bo3b2ob3o9bo3b2ob3o7bo3b2ob
3o10bobob2ob2o$4ob2ob2o9b2o2b2obo11b2o2b2obo9b2o2b2obo13b2ob2obo$8bo
11bo18bo16bo26bo$2b2ob2obo11bobob2o13bobob2o11bobob2o13bob2ob3o$2b2obo
bo13b2ob2o14b2ob2o12b2ob2o13b2obobo6$80bo$43bo15b2ob2o15bobo$5bobob2o
12bobob2o13bobob2o10bob2obo15bo2bo$3b3ob2obo10b3ob2obo11b3ob2obo9bo6b
2o9b2ob2o3bo$2bo17bo18bo16bo8bo9bo8bo$bobob2ob2o11bob2ob2o12bob2ob2o8b
o3b2ob3o11bob2o5bo$2b2ob2obobo9b2ob2ob2o11b2ob2obobo7b2o2b2obo12b2ob2o
2b3o$9bo36bo9bo25bo$bob2ob3o10bob2ob4o10bob2ob3o10bobob2o13b4obobo$b2o
bobo12b2obobo2bo10b2obobo13b2obobo12bo2bob2o$61bo7$60b2ob2o$4b2obo14b
2obo16b2o16b2obobo13bobob2o$3bob2obo12bob2obo14bo2bo20bo11b3ob2obo$2bo
5bo11bo5bo12b3o2bo14bob2o2b2o9bo$bo6b2o9bo6b2o10bo6b2o10b3ob2o3bo10bob
2ob2o$b2o6bo9b2o6bo10b2o7bo8bo8bo10b2ob2obo$4b2obo14b2obo15b2obobo10bo
6bo18bo$b2ob2ob2o10b2ob2ob2o11b2ob2ob2o12bo5b2o10b2ob2ob2o$2bo5bo11bo
18bo19bo2b2o13bobo$2bob2obo12bob2ob2o12bob2ob2o14bo2bo12bo2bo$3bobob2o
12bob2obo13bob2obo15b2o14b2o8$80bo$4b2o16b2o18bo17b2o17bobo$3bo2bo14bo
2bo16bobo15bo2bo16bo2bo$2bobo2bo12bobo2bo13b3ob3o13bo2b3o12b3o3bo$bobo
4bo10bobo4bo11bo7bo10b2o6bo10bo7bo$bo7bo9bo7bo11bo5b2o10bo6b2o11bo5b2o
$2bo5b2o10bo5b2o12bob2o15bob2o15bob2o$3bob2o14bob2o14b2ob2ob2o11b2ob2o
b2o11b2ob2ob2o$2b2ob2ob2o10b2ob2ob2o11bo5bo12bo5bo12bo5bo$8bo11bo5bo
13bob2obo13bob2obo13bob2obo$2b2ob2obo12bob2obo12b2obobo13b2obobo13b2ob
obo$2bob2obo12b2obobo17bo18bo18bo6$43bo17bo18bo15b2o$42bobo15bobo16bob
o13bo2bo$5bo11b2obobo19bobo15bo2bo13b3ob3o11bo2b3o$b2obobo10bob2ob3o
13b2ob2ob2o12b3o3bo11bo7bo8b2o6bo$bob2ob3o16bo12bo18bo7bo11bo5b2o8bo6b
2o$9bo8b2ob2obobo12bob2ob2o12bo5b2o12bob2o13bob2o$2b2ob2obo10bob2ob2o
12b2ob2obo14bob2o14b2ob2ob2o9b2ob2ob2o$3bob2ob2o8bo26bo12b2ob2ob2o17b
2o15b2o$2bo15b2ob2ob2o12b2ob2ob2o18b2o11b2ob2o12b2ob2o$3b3ob2obo11bobo
14bobo16b2ob2o15bobo14bobo$5bobob2o11bobo14bobo17bobo16bobo14bobo$6bo
16bo16bo18bobo17bo16bo$60bo!
The results for each of the 100 subsets of the search space for 34 bits are attached to this post. This is the last still life bit count that I'll be doing, since all of the questions that I had about pseudo still lifes are now answered. Counting 35-bit still lifes with this script would take roughly 5 or 6 CPU years.
Attachments
34_bit_subsets.zip
(31.53 KiB) Downloaded 264 times

hkoenig
Posts: 258
Joined: June 20th, 2009, 11:40 am

Re: Enumerating Still Lifes (in C)

Post by hkoenig » January 9th, 2020, 8:15 pm

Thanks for reminding me that I'd forgotten to restart my searches when I got back from a trip last month. I prefer to only run them in the winter months when the processor heat contributes to the inside temperature instead of being something the air conditioning has to remove.

User avatar
77topaz
Posts: 1496
Joined: January 12th, 2018, 9:19 pm

Re: Enumerating Still Lifes (in C)

Post by 77topaz » January 10th, 2020, 5:20 pm

I've noticed some of these triple pseudo still lifes can even be decomposed into 1, 3 or 4 (but not 2) subpatterns:

Code: Select all

x = 63, y = 20, rule = B3/S23
5bo20bo27bo$4bobob2o15bobob2o22bobob2o$2b3ob2obo13b3ob2obo20b3ob2obo$b
o20bo27bo$obob2ob2o12bobo25bobo$b2ob2obo14b2o26b2o$8bo$ob2ob3o$2obobo$
26b2o26b2o$26b2o26b2o$61b2o$61bo$62bo$48bob2o7b3o$29b2o17b2obo7bo$29bo
$30bo$22bob2ob3o$22b2obobo!
Though I suppose that doesn't make them a special class as quad pseudo still life specifically needs only 1 or 4 as decompositions. It's still somewhat distinct, though, as some of the other triple pseudo still lifes can only be decomposed into 1 or 3 as they have no fourth subpattern.

User avatar
confocaloid
Posts: 2729
Joined: February 8th, 2022, 3:15 pm

Re: Enumerating Still Lifes (in C)

Post by confocaloid » February 19th, 2024, 5:23 pm

confocaloid wrote:
February 10th, 2024, 5:18 am
Maybe someone could double-check (verify) and extend the following table? [...] Assuming it is correct, it gives the number of still lives of any kind (strict, pseudo, quasi, constellations all included) with a specific bounding box, up to rotations and reflections. For example, according to the table, there are exactly 2048 distinct still lives with bounding box 7-by-6.
Crossposting an updated table:

Code: Select all

   |   2     3     4     5     6    7    8
---+--------------------------------------
 2 |   1     .     .     .     .    .    .
 3 |   0     3     .     .     .    .    .
 4 |   1     2     6     .     .    .    .
 5 |   1     2     7    15     .    .    .
 6 |   1     4    22    67   200    .    .
 7 |   3    18    93   405  2048 9244    .
 8 |   3    43   268  1106  8452    ?    ?
 9 |   5    81   702  3730 35800    ?    ?
10 |  10   150  1650 13126     ?    ?    ?
11 |  11   313  4358     ?     ?    ?    ?
12 |  21   722 12501     ?     ?    ?    ?
13 |  32  1624     ?     ?     ?    ?    ?
14 |  49  3457     ?     ?     ?    ?    ?
15 |  83  7259     ?     ?     ?    ?    ?
16 | 136 15494     ?     ?     ?    ?    ?
17 | 213     ?     ?     ?     ?    ?    ?
18 | 364     ?     ?     ?     ?    ?    ?
19 | 584     ?     ?     ?     ?    ?    ?
20 | 974     ?     ?     ?     ?    ?    ?
When a number is given in the table, a complete enumeration was done using LLS, with postprocessing using a lifelib script. For some larger bounding boxes, an incomplete enumeration (complete for specific populations) was done using LLS:
  • 10x10: 460 xs54, ???
  • 9x9: 10 xs43, 554 xs42, 2865 xs41, ???
  • 8x8: 1 xs36, 1 xs35, 8 xs34, 23 xs33, 182 xs32, 646 xs31, 2213 xs30, ???
The attached file lists apgcodes and bounding boxes in the following format:

Code: Select all

#C (8x6) xs25_3lkmhrz346226
#C (9x6) xs28_j9e0drzdd1dd
sl_apgcodes_by_bbox.txt
(3.36 MiB) Downloaded 13 times
127:1 B3/S234c User:Confocal/R (isotropic rules, incomplete)
Unlikely events happen.
My silence does not imply agreement, nor indifference. If I disagreed with something in the past, then please do not construe my silence as something that could change that.

Post Reply