17
\$\begingroup\$

Conways' Game of Life is a well known cellular automaton "played" on an infinite grid, filled with cells that are either alive or dead. Once given an initial state, the board evolves according to rules indefinitely. Those rules are:

  • Any live cell with 2 or 3 living neighbours (the 8 cells immediately around it) lives to the next state
  • Any dead cell with exactly 3 living neighbours becomes a living cell
  • Any other cell becomes a dead cell

Consider the following initial state:

enter image description here

That is, PPCG made up of living cells. Each letter is in a \$4×6\$ bounding box, with a single empty column of cells between boxes, for a total bounding box of \$19×6\$

After 217 generations, it reaches the following states:

enter image description here

From this point onwards, it is a "fixed state". All structures on the board are either still lifes or oscillators, so no meaningful change will occur.

Your task is to improve this.

enter image description here

You may place up to 50 live cells in the \$5\times10\$ highlighted area, such that, when run, it takes more than 217 generations to reach a "fixed state". The answer with the highest number of generations wins, with ties being broken by the fewest number of placed living cells.

For the purposes of this challenge, a "fixed state" means that all structures on the board are either still lifes or oscillators. If any spaceships or patterns of infinite growth are generated, the board will never reach a "fixed state" and such cases are invalid submissions.

For example, this initial configuration takes 294 generations to reach a fixed state (this), so is a valid submission with a score of 294:

enter image description here

Preloaded testable version, with the \$5\times10\$ box fully filled in.

\$\endgroup\$
8
  • 1
    \$\begingroup\$ It's not difficult to beat the 294 example, but brownie points for beating my best shot of 797 iterations! \$\endgroup\$ Commented Mar 25, 2021 at 15:52
  • 1
    \$\begingroup\$ Next challenge: add outside cells to turn PPCG into CGCC with minimal number of iterations :-P \$\endgroup\$
    – Luis Mendo
    Commented Mar 25, 2021 at 16:33
  • 4
    \$\begingroup\$ @LuisMendo Obviously the title would be "Graduate PPCG in Game of Life" :P \$\endgroup\$ Commented Mar 25, 2021 at 16:35
  • \$\begingroup\$ Are there techniques here other than brute force? \$\endgroup\$
    – Jonah
    Commented Mar 25, 2021 at 17:13
  • 2
    \$\begingroup\$ @Jonah I believe so. The original idea on Puzzling.SE was solved without using brute force, so I suspect that, due to the smaller area, proper analysis is likely to lead to a better solution faster \$\endgroup\$ Commented Mar 25, 2021 at 17:15

5 Answers 5

14
\$\begingroup\$

2986 2320 1228 generations

I wrote a rudimentary Python script for Golly to generate random 5x10 patterns until it encountered one whose population was fixed, and whose bounding box was not too large (as would be expected of soups containing spaceships, as spaceships expand the bounding box as they travel). Here was what it came up with after about 50,000 patterns investigated, and I suspect this is not maximal. If anyone wants to continue this search by using my script, it's located below the pattern.

enter image description here

RLE of solution:

# 2986 generations
x = 19, y = 20, rule = B3/S23
3o2b3o3b3o2b3o$o2bobo2bobo4bo$o2bobo2bobo4bo$3o2b3o2bo4bob2o$o4bo4bo4b
o2bo$o4bo5b3o2b2o5$7bobobo$7b2ob2o$8bo2bo$11bo$10b2o$7bo2bo2$8b4o$7bo$
7bo3bo!

Python script, to be run in Golly from File > Run Script (not golfed). You will need to paste/draw in the PPCG pattern and select the 5x10 rectangle first.

import golly as g
from glife import rect, pattern

g.setrule("B3/S23") #set the rule to Conway's Life
soupcount = 0 #create a counter for # of soups processed

while True:
    pop = 0
    g.randfill(50) #randomly fill the 5x10 selection
    g.run(2400) #run the pattern for 2400 generations
    if g.getrect()[2] * g.getrect()[3] < 40000: #after 2400 generations, if the bounding box is small
        pop = g.getpop() #check to make sure the population is not the same (pattern is not static)
        g.run(120)
        if g.getpop() != pop:
            g.run(9880) #after 9880 more generations, if the bounding box is still small
            if g.getrect()[2] * g.getrect()[3] < 40000: #check to make sure the population is the same (pattern is static)
                pop = g.getpop()
                g.run(120)
                if g.getpop() == pop:
                    g.reset() #if so, break the loop and return the pattern
                    break
    g.reset() #repeat the loop and generate a new pattern if the pattern does not satisfy the conditions
    soupcount += 1
    g.show(str(soupcount)) #continually show the # of soups processed to make sure the program isn't dead

RLEs of old solutions:

#C 2320 generations
x = 19, y = 20, rule = B3/S23
3o2b3o3b3o2b3o$o2bobo2bobo4bo$o2bobo2bobo4bo$3o2b3o2bo4bob2o$o4bo4bo4b
o2bo$o4bo5b3o2b2o5$7bo3bo$7b3o$10bo2$7bo$7bo2bo$7bo$7b2o$7bo3bo$7b2o2b
o!
#C 1228 generations, found manually with Ctrl+5
#C to continually generate random 5x10 patterns
x = 19, y = 17, rule = B3/S23
3o2b3o3b3o2b3o$o2bobo2bobo4bo$o2bobo2bobo4bo$3o2b3o2bo4bob2o$o4bo4bo4b
o2bo$o4bo5b3o2b2o5$7b5o$7bobobo$7b2obo$8bob2o$8b4o$8bo2bo$7bobo!
\$\endgroup\$
4
  • \$\begingroup\$ @OriginalOriginalOriginalVI I'm not sure what you mean, could you explain? \$\endgroup\$
    – Cloudy7
    Commented Mar 26, 2021 at 0:08
  • \$\begingroup\$ @OriginalOriginalOriginalVI The last score is 2986. The higher, the better. \$\endgroup\$
    – Arnauld
    Commented Mar 26, 2021 at 0:22
  • \$\begingroup\$ @Arnauld Oh, I see, I didn't bother looking at the first one :) \$\endgroup\$
    – user
    Commented Mar 26, 2021 at 0:24
  • \$\begingroup\$ I just noticed that I typed from glife import rect, pattern and then completely failed to use it any way. In my defense, it was my first time writing a Golly script, so I was copying the imports from another program. Oops! \$\endgroup\$
    – Cloudy7
    Commented Mar 26, 2021 at 5:06
8
\$\begingroup\$

887 generations

Solution

Explanation

…There is no explanation. I just brute-forced it manually and somehow beat ChartZ Belatedly by 90 generations.

\$\endgroup\$
5
\$\begingroup\$

 884  900 generations

Just some random handcrafted pattern.

pattern

\$\endgroup\$
1
  • 3
    \$\begingroup\$ Beat you by 5 seconds and 3 iterations... :) \$\endgroup\$
    – Makonede
    Commented Mar 25, 2021 at 18:37
4
\$\begingroup\$

3020 3179 Generations


# #  
### #
 # # 
   ##
##   
    #
     
    #
 # ##
##   

Found by random search

\$\endgroup\$
6
  • \$\begingroup\$ Yup, I also got 3020 on this one! (my own best so far is 851) \$\endgroup\$
    – Kjetil S
    Commented Mar 26, 2021 at 23:49
  • \$\begingroup\$ I regret to inform you that there are thirty blinkers in the ash of that soup. Nice work in beating me, though! \$\endgroup\$
    – Cloudy7
    Commented Mar 26, 2021 at 23:56
  • \$\begingroup\$ @Cloudy7 – Oscillators are okay says the challenge. I'm guessing those the same as blinkers (typically a bar of 3 vertical or 3 horizontal). Inits that leads to gliders/spaceships that continue forever are invalid, but this submission didn't have any of those. \$\endgroup\$
    – Kjetil S
    Commented Mar 27, 2021 at 0:07
  • \$\begingroup\$ @KjetilS. They claimed that the final pattern "reaches a still life with no oscillators". \$\endgroup\$
    – Cloudy7
    Commented Mar 27, 2021 at 0:13
  • 1
    \$\begingroup\$ @Cloudy7 – Oh, I see now. Yes, that wasn't so, but we seem to agree that the submission is okay. \$\endgroup\$
    – Kjetil S
    Commented Mar 27, 2021 at 0:14
3
\$\begingroup\$

3365 generations

_#_#_
##__#
_##__
_____
#####
_##__
#____
#_#_#
##___
_#_#_

This 5x10 start can be expressed as 379744881760010 in decimal, 159603ec8570a in hex or 01010 11001 01100 00000 11111 01100 10000 10101 11000 01010 in 50-bit binary. Crossing my fingers that nobody starts a new alt-coin based on rewarding many generations in Conway's Game of Life...LifeCoins.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.