Page 1 of 1
In Search of Maximum Density Still Lifes
Posted: July 1st, 2022, 2:13 pm
by Book
Please refer to the wiki Density article
https://conwaylife.com/wiki/Density.
While the nxn SL max density problem was mathematically solved and solutions published a decade ago, many pattern files for the solutions had not been captured in an accessible place. We now have memorialized these RLEs in the wiki article. Some were already there. Some were reconstructed from images. Most were the result of converting a cache of binary text patterns to plaintext to rles. We now have rles for n=2 to 200 and some over 200 (see article table and external link),
with the exception of 12x12, 13x13, 16x16, 17x17 and 18x18. Anyone who can produce an rle for any of these 5 will earn huge kudos.
Re: In Search of Maximum Density Still Lifes
Posted: July 1st, 2022, 3:01 pm
by yujh
Here is one example for 12x12
Code: Select all
x = 0, y = 0, rule = B3/S23
14b$b2ob2ob2o2b2ob$2bob2obobo2bob$bo5bobobo2b$b4ob2obob2ob$4bobo2bobo2b$b2obobob2obo2b$b2obobo2bob2ob$4bob3o5b$b4o4b4ob$bo3b3obo2bob$2bobo2bobobo2b$b2ob2o2b2ob2ob$14b$!
I'm curioused what script people used to find the 20*20 and above patterns.
13x13
Code: Select all
x = 0, y = 0, rule = B3/S23
15b$b2ob2obob2ob2ob$b2obob3obob2ob$4bo5bo4b$b3ob5ob3ob$bo2bo5bo2bob$2bobo2b2obobo2b$b2obobobobob2ob$2bobobobobobo2b$bo2bobobobo2bob$b4obobob4ob$7bo7b$b5obob2ob2ob$bo2bob2ob2ob2ob$15b$!
Re: In Search of Maximum Density Still Lifes
Posted: July 1st, 2022, 3:09 pm
by Jormungant
well well, someone posted faster :/
in any case, here is a symmetric 12x12:
Code: Select all
x = 12, y = 12, rule = LifeHistory
2A.A.2A.2A.A$A.3A.A.A.2A$6.A.A$.6A.A.2A$A6.2A.2A$6A$6.6A$2A.2A6.A$2A.
A.6A$3.A.A$2A.A.A.3A.A$A.2A.2A.A.2A!
Re: In Search of Maximum Density Still Lifes
Posted: July 1st, 2022, 4:10 pm
by LucasBrown
The maximum population of an n × n still life is tabulated in the OEIS at
https://oeis.org/A055397. That listing disagrees with table 7 of
https://people.eng.unimelb.edu.au/pstuc ... l-life.pdf at n = 24 and n = 26. Could someone who is more familiar with this topic look into that?
Re: In Search of Maximum Density Still Lifes
Posted: July 1st, 2022, 4:29 pm
by Book
yujh wrote: July 1st, 2022, 3:01 pm
Here is one example for 12x12
Code: Select all
x = 0, y = 0, rule = B3/S23
14b$b2ob2ob2o2b2ob$2bob2obobo2bob$bo5bobobo2b$b4ob2obob2ob$4bobo2bobo2b$b2obobob2obo2b$b2obobo2bob2ob$4bob3o5b$b4o4b4ob$bo3b3obo2bob$2bobo2bobobo2b$b2ob2o2b2ob2ob$14b$!
I'm curioused what script people used to find the 20*20 and above patterns.
13x13
Code: Select all
x = 0, y = 0, rule = B3/S23
15b$b2ob2obob2ob2ob$b2obob3obob2ob$4bo5bo4b$b3ob5ob3ob$bo2bo5bo2bob$2bobo2b2obobo2b$b2obobobobob2ob$2bobobobobobo2b$bo2bobobobo2bob$b4obobob4ob$7bo7b$b5obob2ob2ob$bo2bob2ob2ob2ob$15b$!
20 and above were found in a binary text zip file in an obscure corner of a university server. The references (1 and 2 in wiki article) show how they were found for all periods. Not by what we'd call a script.
Re: In Search of Maximum Density Still Lifes
Posted: July 1st, 2022, 4:34 pm
by Book
That was fast work for n=12 and 13. Thanks.
Yearning for n=16, 17, 18...
Re: In Search of Maximum Density Still Lifes
Posted: July 1st, 2022, 6:04 pm
by Anivec
It would be cool if we had a script for this.
Re: In Search of Maximum Density Still Lifes
Posted: July 1st, 2022, 6:43 pm
by Book
I believe the errors are in the paper. 24 should be 301; 26 should be 352. I have the patterns they generated for those 2 periods in binary text format that I used to make the RLEs in the PatMan collection and they are as stated here.
Re: In Search of Maximum Density Still Lifes
Posted: July 2nd, 2022, 5:00 am
by Macbi
LLS has the option to search for still lifes with population constraints within a given box. Unfortunately the step of enforcing the population constraint is very slow (due to my amaturish implementation). But I should be able to churn out the 16, 17 and 18 cases over the next couple of days, if no one else gets there first.
Re: In Search of Maximum Density Still Lifes
Posted: July 2nd, 2022, 2:45 pm
by yujh
16x16
Code: Select all
x = 0, y = 0, rule = B3/S23
18b$b2ob2ob2obob2ob2ob$b2ob2obob3obob2ob$7bo5bo4b$b4obob6ob2ob$bo2bobobo6b2ob$2bobobobob4o4b$b2obobobobo3b3ob$bo2bobobo2b3o2bob$2bobobob3o2bobo2b$b2obobo4bobob2ob$2bobob6obobo2b$bo2bo8bo2bob$b3ob8ob3ob$4bo8bo4b$b2obob2ob3obob2ob$b2ob2ob2obob2ob2ob$18b$!
Re: In Search of Maximum Density Still Lifes
Posted: July 4th, 2022, 4:07 pm
by Book
yujh wrote: July 2nd, 2022, 2:45 pm
16x16
2 to go! 17 and 18. Then we'll have all n=2...200.
Re: In Search of Maximum Density Still Lifes
Posted: July 4th, 2022, 7:24 pm
by xpsd
Another 16x16 and a 18x18 close relative :
Code: Select all
x = 58, y = 27, rule = LifeHistory
3D.D.D5.D.D25.D.D.3D5.D.D$2.D.D.D.D.D.D.D25.D.D3.D.D.D.D.D$3D.3D2.D2.
3D25.3D.3D2.D2.3D$2.D3.D.D.D3.D27.D.D3.D.D3.D$3D3.D7.D27.D.3D7.D5$2A.
2A.A2.E.2E.2E24.2A.2A.A.2E.A.2A.2A$2A.A.3A3E.E.2E24.2A.A.2A.2E.2A.A.
2A$3.A8.E30.A10.A$3A.4A4E.3E24.3A.4A2E4A.3A$A2.A8.E2.E24.A2.A10.A2.A$
.A.A.3A3E.E.E26.A.A.3A2E3A.A.A$2A.A.A4.E.E.2E24.2A.A.A6.A.A.2A$.A.A.A
.AE.E.E.E28.A.A.A2EA.A.A$.A.A.A.2A.A.A.A25.2E.E.E.E2.E.E.E.2E$2A.A.A
4.A.A.2A24.2E.E.E.E2.E.E.E.2E$.A.A.6A.A.A28.A.A.A2EA.A.A$A2.A8.A2.A
24.2A.A.A6.A.A.2A$3A.8A.3A25.A.A.3A2E3A.A.A$3.A8.A27.A2.A10.A2.A$2A.A
.6A.A.2A24.3A.4A2E4A.3A$2A.2A.A2.A.2A.2A27.A10.A$40.2A.A.2A.2E.2A.A.
2A$40.2A.2A.A.2E.A.2A.2A!
Re: In Search of Maximum Density Still Lifes
Posted: July 4th, 2022, 7:46 pm
by Book
xpsd wrote: July 4th, 2022, 7:24 pm
Another 16x16 and a 18x18 close relative :
That's a nice sym 16x16, I've added it. To be clear, the 18x18 "close relative" is not a max density.
Re: In Search of Maximum Density Still Lifes
Posted: July 6th, 2022, 2:00 pm
by yujh
17x17
Code: Select all
x = 0, y = 0, rule = B3/S23
19b$bob2ob2obob2ob2obob$b2obobob3obobob2ob$4bobo5bobo4b$b2obob7obob2ob$b2obo9bob2ob$4b11o4b$b3o11b3ob$bo2b11o2bob$3bo11bo3b$bob13obob$b2o13b2ob$4b11o4b$b2obo9bob2ob$b2obob7obob2ob$4bobo5bobo4b$b2obobob3obobob2ob$bob2ob2obob2ob2obob$19b$!
Re: In Search of Maximum Density Still Lifes
Posted: July 6th, 2022, 4:28 pm
by Book
Nice sym 17x17! Here it is, tidied up:
Code: Select all
x = 17, y = 17, rule = B3/S23
ob2ob2obob2ob2obo$2obobob3obobob2o$3bobo5bobo$2obob7obob2o$2obo9bob2o$
3b11o$3o11b3o$o2b11o2bo$2bo11bo$ob13obo$2o13b2o$3b11o$2obo9bob2o$2obob
7obob2o$3bobo5bobo$2obobob3obobob2o$ob2ob2obob2ob2obo!
Just need 18x18 now to complete n=2...200.
Re: In Search of Maximum Density Still Lifes
Posted: July 7th, 2022, 5:26 pm
by Book
Macbi wrote: July 2nd, 2022, 5:00 am
LLS has the option to search for still lifes with population constraints within a given box. Unfortunately the step of enforcing the population constraint is very slow (due to my amaturish implementation). But I should be able to churn out the 16, 17 and 18 cases over the next couple of days, if no one else gets there first.
Just need 18x18 now.
Why brute force won't work: there are about 9x10^95 possibilities.
Re: In Search of Maximum Density Still Lifes
Posted: July 8th, 2022, 9:35 am
by yujh
18x18
Code: Select all
x = 18, y = 18, rule = B3/S23
ob2ob2ob2obob2ob2o$2obobob2ob3obob2o$3bobo8bo$2obob9ob3o$2obo4bo5bo2bo
$3b4o3b3obobo$3o3b4o2bobob2o$o2b2o4bobo2bobo$bobob4o2b4o2bo$2obobo2bob
o4b3o$bobobo2bob5o$o2bob2obo6b3o$4obo2b7o2bo$5bobo6bobo$6ob6obob2o$o5b
o5bobo$bob2obob3obobob2o$2ob2ob2obob2ob2obo!
Re: In Search of Maximum Density Still Lifes
Posted: July 8th, 2022, 12:41 pm
by Book
Bravo! We now have at least one example for all n from 2 to 200.
Mission accomplished.