Forums for Conway's Game of Life
https://conwaylife.com/forums/
Try gcc-g++, it's pretty much the standard C/C++ compiler.HelicopterCat3 wrote: ↑January 7th, 2021, 9:39 pmI'm sorry I have one last question. What do you recommend as a good c++ compiler? Or does WSL/Cygwin come with a c++ compiler built in?
Alright thanks! Once I get the c compiler and apgsearch itself, I should be able to contribute.bubblegum wrote: ↑January 7th, 2021, 9:46 pmTry gcc-g++, it's pretty much the standard C/C++ compiler.HelicopterCat3 wrote: ↑January 7th, 2021, 9:39 pmI'm sorry I have one last question. What do you recommend as a good c++ compiler? Or does WSL/Cygwin come with a c++ compiler built in?
Yes
How would you weed out non-interacting solutions?creeperman7002 wrote: ↑January 15th, 2021, 9:33 pmCan rlifesrc have a min-pop feature and an algorithm to weed out non-interacting solutions?
This is especially useful when enumerating patterns of a certain size.
Code: Select all
$ java -jar SeedsOfDestruction.v0-5.jar
Exception in thread "AWT-EventQueue-0" java.lang.ClassCastException: class [Ljava.lang.Object; cannot be cast to class [Ljava.lang.String; ([Ljava.lang.Object; and [Ljava.lang.String; are in module java.base of loader 'bootstrap')
at sphi.igblan.seedsOfDestruction.Nouns.<init>(Nouns.java:62)
at sphi.igblan.seedsOfDestruction.PuzzleTree.<init>(PuzzleTree.java:115)
at sphi.igblan.seedsOfDestruction.ui.Frame.<init>(Frame.java:38)
at sphi.igblan.seedsOfDestruction.ui.Frame$4.run(Frame.java:307)
at java.desktop/java.awt.event.InvocationEvent.dispatch(InvocationEvent.java:313)
at java.desktop/java.awt.EventQueue.dispatchEventImpl(EventQueue.java:770)
at java.desktop/java.awt.EventQueue$4.run(EventQueue.java:721)
at java.desktop/java.awt.EventQueue$4.run(EventQueue.java:715)
at java.base/java.security.AccessController.doPrivileged(Native Method)
at java.base/java.security.ProtectionDomain$JavaSecurityAccessImpl.doIntersectionPrivilege(ProtectionDomain.java:85)
at java.desktop/java.awt.EventQueue.dispatchEvent(EventQueue.java:740)
at java.desktop/java.awt.EventDispatchThread.pumpOneEventForFilters(EventDispatchThread.java:203)
at java.desktop/java.awt.EventDispatchThread.pumpEventsForFilter(EventDispatchThread.java:124)
at java.desktop/java.awt.EventDispatchThread.pumpEventsForHierarchy(EventDispatchThread.java:113)
at java.desktop/java.awt.EventDispatchThread.pumpEvents(EventDispatchThread.java:109)
at java.desktop/java.awt.EventDispatchThread.pumpEvents(EventDispatchThread.java:101)
at java.desktop/java.awt.EventDispatchThread.run(EventDispatchThread.java:90)Code: Select all
$ java --version
openjdk 11.0.10 2021-01-19
OpenJDK Runtime Environment (build 11.0.10+9-Ubuntu-0ubuntu1.18.04)
OpenJDK 64-Bit Server VM (build 11.0.10+9-Ubuntu-0ubuntu1.18.04, mixed mode, sharing)Repl.it, aha, that's another kettle of *WSSes entirely. Do you happen to have a repl where you're trying this, that you could make public and post a link to?
I don't think that's likely to work, because oscar.py/oscar.lua relies on the idea of keeping track of a list of just the lowest hash values in a range of tested generations. For a period-P pattern I don't see how you can be sure that you're going to find the matching hash value until you've tested P different generations -- no matter how cleverly you pick the ticks to check.Macbi wrote: ↑March 18th, 2021, 8:17 pmCould we speed up oscar.py by only looking at generations from a sparse ruler, and using hash life to jump between them?
Yes, that's exactly what lifelib does. The pdetect algorithm in lifelib accepts an upper limit N as a parameter, and it constructs a finite sparse ruler of size O(sqrt(N) log(N)).Macbi wrote: ↑March 18th, 2021, 8:17 pmCould we speed up oscar.py by only looking at generations from a sparse ruler, and using hash life to jump between them?
Indeed -- that's why lifelib can't use the Nivasch cycle detection algorithm; it instead stores the (hash --> generation) mapping in an associative array.dvgrn wrote: ↑March 18th, 2021, 8:46 pmI don't think that's likely to work, because oscar.py/oscar.lua relies on the idea of keeping track of a list of just the lowest hash values in a range of tested generations. For a period-P pattern I don't see how you can be sure that you're going to find the matching hash value until you've tested P different generations -- no matter how cleverly you pick the ticks to check.
In lifelib's periodicity detection code, the number of times that the step size is increased (specifically doubled) is only log_4(N), where N is the maximum period to consider.Then, also, changing the step in Golly is computationally expensive, so it seems like you'd actually be at a serious disadvantage over just keeping the step size at 1. Sometimes you'd definitely luck out and find the period faster with a sparse-ruler approach, but I would guess it would be slower more often than it was faster. (But quite possibly I'm just not understanding the suggestion.)
I've always thought that getting the space usage down to log(N) at the expense of doubling the running time was a false economy. On any modern computer one will run out of time to evolve generations long before one runs out of space to store hashes.dvgrn wrote: ↑March 18th, 2021, 8:46 pmI don't think that's likely to work, because oscar.py/oscar.lua relies on the idea of keeping track of a list of just the lowest hash values in a range of tested generations. For a period-P pattern I don't see how you can be sure that you're going to find the matching hash value until you've tested P different generations -- no matter how cleverly you pick the ticks to check.
It seems like lifelib is better than Golly in a lot of resepects. Would it be possible to take Golly's GUI and graft it onto a lifelib backend? What would be the main obstructions?
Gabriel Nivasch also describes a multi-stack generalisation on the same webpage, which allows you to increase the memory usage and decrease the running time:Macbi wrote: ↑March 20th, 2021, 3:39 amI've always thought that getting the space usage down to log(N) at the expense of doubling the running time was a false economy. On any modern computer one will run out of time to evolve generations long before one runs out of space to store hashes.dvgrn wrote: ↑March 18th, 2021, 8:46 pmI don't think that's likely to work, because oscar.py/oscar.lua relies on the idea of keeping track of a list of just the lowest hash values in a range of tested generations. For a period-P pattern I don't see how you can be sure that you're going to find the matching hash value until you've tested P different generations -- no matter how cleverly you pick the ticks to check.
The main disadvantages of lifelib are:It seems like lifelib is better than Golly in a lot of resepects. Would it be possible to take Golly's GUI and graft it onto a lifelib backend? What would be the main obstructions?
Code: Select all
# Golly Python script. Written by PM 2Ring, March 2009. Updated August 2009.
# Modified for Golly 2.0+ by Andrew Trevorrow.
''' Create a 'bitmap printer'.
Print a bitmap in LWSSs, using the current selection as the bitmap source.
'''
import golly
from glife import *
def get_bitmap():
''' Get current selection & turn it into a bitmap. '''
selrect = golly.getselrect()
if len(selrect) == 0: golly.exit("There is no selection, aborting.")
#Get bitmap size
w, h = selrect[2:]
#Adjust width, so it's in the form of 4m, m>1
w = (w + 3) // 4 * 4
w = max(8, w)
#Initialize empty bitmap
row = w * [0]
bm = [row[:] for i in xrange(h)]
#Populate bitmap with cell data
u, v = selrect[:2]
cells = golly.getcells(selrect)
cellsxy = [(cells[i] - u, cells[i+1] - v) for i in xrange(0, len(cells), 2)]
for x, y in cellsxy:
bm[y][x] = 1
return bm
def linemaker(loopm):
''' Create an empty LineMaker '''
LM = pattern('''
34b2o$34bo$25b2o5bobo$24b3o5b2o$12bo8bob2o$12bobo6bo2bo$2o11bobo5bob2o
$2o11bo2bo7b3o21b2o$13bobo9b2o21b2o$12bobo$12bo9bo$23b2o$22b2o6$47b3o$
24b2o20bo3bo$24b2o19bo5bo$46bo3bo$47b3o$47b3o5$49b3o$44bo3b2ob2o$42b2o
4b2ob2o$35b2o6b2o3b5o$35b2o10b2o3b2o7$45b2o5b2o$45bo6bo$46b3o4b3o$48bo
6bo!''')
LMTop = LM + pattern('2b2o$2bo$obo$2o!', 32, 7)
LMBase = pattern('''
11bo$10bo$10b3o12$23b2o$23bobo$10bobo13bo$9bo2bo2b2o6bo2bo12b2o$8b2o5b
obo8bo11b3o$2o4b2o3bo3bo3bo3bobo9bob2o15bo$2o6b2o5b3ob2o2b2o10bo2bo8b
3o4bobo$9bo2bo3b2o17bob2o16bobo$10bobo25b3o2b2o2bo7bo2bo3b2o$39b2o2bo
3bo7bobo4b2o$44bo2bo6bobo$26bo17b2o8bo$24bobo$25b2o2$36bo$36bobo$36b2o
7$33bo7bo$32b4o5bobo$27b2o2bo2b2o8b2o4b2o$27b2o2b2o11b2o4b2o$16b2o6b2o
10bo7b2o$16b2o5b3o10bo4bobo$24b2o10bo4bo$27b2o$27b2o!''', 14, 29)
LMBase += LM(55, 42, flip)
return LMTop(8 + loopm, -21 - loopm) + LMBase
def dmprinter(pdy, copies=1):
''' Generate & display a dot matrix printer for named bitmap pattern '''
#Horizontal pixel separation between LineMakers. minimum = 5
LMsx = 5
#Horizontal distance between bitmap pixels. Constant, due to LineMaker period
pdx = 15
#Distance between LineMakers
LMdx, LMdy = -LMsx * pdx, pdy
#Get bitmap pattern from current selection.
bm = get_bitmap()
#Make printer in a new layer
golly.duplicate()
golly.setoption("syncviews", False)
#Build new window title from old
title = golly.getname().split('.')[0]
title = '%s_Printer [%d] v0.10' % (title, pdy)
golly.new(title)
#Make sure we're using the standard Life generation rule
golly.setrule("B3/S23")
#Bitmap dimensions. Width MUST be of form 4m, for m >=1
bmheight = len(bm)
bmwidth = len(bm[0])
mid = (bmheight + 1) // 2
loopw = (bmwidth - 8) // 4
loopm = pdx * loopw
#Gliders, heading north-east
g0 = pattern('2bo$2o$b2o!')
g1 = pattern('obo$2o$bo!')
gliders = [g0, g1, g1(0, 2, rccw), g0(0, 2, rccw),
g0(2, 2, flip), g1(2, 2, flip), g1(2, 0, rcw), g0(2, 0, rcw)]
#Create full Glider loop.
gg = []
ox, oy = 35, 23
for j in xrange(loopw + 1):
dd = pdx * j
gg += [gliders[0](ox + dd, oy - dd), gliders[1](ox + 8 + dd, oy - 7 - dd)]
dd = loopm
gg += [gliders[2](45 + dd, 4 - dd), gliders[3](37 + dd, -3 - dd)]
ox, oy = 26 + loopm, -4 - loopm
for j in xrange(loopw + 1):
dd = pdx * j
gg += [gliders[4](ox - dd, oy + dd), gliders[5](ox - 8 - dd, oy + 7 + dd)]
dd = loopm
gg += [gliders[6](16, 15), gliders[7](24, 22)]
parity = 2*((loopw + 1)*(0, 0) + (1, 1))
def buildLM():
''' Build a complete LineMaker '''
#Populate glider loop. (jj, ii) are bitmap coords
gloop = pattern()
for j in xrange(bmwidth):
jj = (j - delta + bmwidth - 1) % bmwidth
#Is there a pixel at this location?
if bm[ii][jj] == parity[j]:
gloop += gg[j] #Add glider to the loop
#Only put LineMaker if glider loop isn't empty
if len(gloop) > 0:
(LMBlank + gloop).put(Lx, Ly, trans)
#Assemble blank LineMaker
LMBlank = linemaker(loopm)
#Do upper LineMakers
trans = identity
for i in xrange(mid):
ii = mid - (i + 1)
io = mid + (i + 1)
Lx, Ly = io * LMdx, ii * LMdy
delta = LMsx * io
buildLM()
#Do lower LineMakers
trans = flip_y
for i in xrange(mid, bmheight):
ii = i
io = i + 2
Lx, Ly = io * LMdx + pdx, ii * LMdy + 128
delta = LMsx * io - 1
buildLM()
#Eaters facing south-east & north-east
eaterSE = pattern('2o$bo$bobo$2b2o!')
eaterNE = eaterSE(0, 10, flip_y)
eY = 59
eaters = (eaterNE(0, eY), eaterSE(0, eY))
#Eater horizontal displacement. Must be odd
#bmwidth muliplier determines number of copies visible 'outside' printer.
eX = (bmheight + 1) * LMdx - (copies * bmwidth - 1) * pdx
eX = 1 + eX // 2 * 2 #Adjust parity
all = pattern()
for i in xrange(bmheight):
all += eaters[i % (1 + LMsx % 2)](eX, i * LMdy)
all.put()
#Centre view over bitmap output area
golly.setpos(str(-pdx * bmwidth // 2 + (bmheight - 1) * LMdx), str(Ly//2))
#golly.setmag(-2) #Aliasing effects happen at smaller scales than -2 :(
golly.fit()
def main():
#Vertical distance between pixels. Maybe get this from user. minimum = 16
pdy = 16
#Generate & display a dot matrix printer from current selection
dmprinter(pdy, copies=1)
golly.setcursor("Zoom In")
golly.setalgo("HashLife")
golly.setbase(2)
golly.setstep(6)
main()Code: Select all
# Golly Python script. Written by PM 2Ring, March 2009. Updated August 2009.
# Modified for Golly 2.0+ by Andrew Trevorrow. and for Python 3+ by Oscar Cunningham.
''' Create a 'bitmap printer'.
Print a bitmap in LWSSs, using the current selection as the bitmap source.
'''
import golly
from glife import *
def get_bitmap():
''' Get current selection & turn it into a bitmap. '''
selrect = golly.getselrect()
if len(selrect) == 0: golly.exit("There is no selection, aborting.")
#Get bitmap size
w, h = selrect[2:]
#Adjust width, so it's in the form of 4m, m>1
w = (w + 3) // 4 * 4
w = max(8, w)
#Initialize empty bitmap
row = w * [0]
bm = [row[:] for i in range(h)]
#Populate bitmap with cell data
u, v = selrect[:2]
cells = golly.getcells(selrect)
cellsxy = [(cells[i] - u, cells[i+1] - v) for i in range(0, len(cells), 2)]
for x, y in cellsxy:
bm[y][x] = 1
return bm
def linemaker(loopm):
''' Create an empty LineMaker '''
LM = pattern('''
34b2o$34bo$25b2o5bobo$24b3o5b2o$12bo8bob2o$12bobo6bo2bo$2o11bobo5bob2o
$2o11bo2bo7b3o21b2o$13bobo9b2o21b2o$12bobo$12bo9bo$23b2o$22b2o6$47b3o$
24b2o20bo3bo$24b2o19bo5bo$46bo3bo$47b3o$47b3o5$49b3o$44bo3b2ob2o$42b2o
4b2ob2o$35b2o6b2o3b5o$35b2o10b2o3b2o7$45b2o5b2o$45bo6bo$46b3o4b3o$48bo
6bo!''')
LMTop = LM + pattern('2b2o$2bo$obo$2o!', 32, 7)
LMBase = pattern('''
11bo$10bo$10b3o12$23b2o$23bobo$10bobo13bo$9bo2bo2b2o6bo2bo12b2o$8b2o5b
obo8bo11b3o$2o4b2o3bo3bo3bo3bobo9bob2o15bo$2o6b2o5b3ob2o2b2o10bo2bo8b
3o4bobo$9bo2bo3b2o17bob2o16bobo$10bobo25b3o2b2o2bo7bo2bo3b2o$39b2o2bo
3bo7bobo4b2o$44bo2bo6bobo$26bo17b2o8bo$24bobo$25b2o2$36bo$36bobo$36b2o
7$33bo7bo$32b4o5bobo$27b2o2bo2b2o8b2o4b2o$27b2o2b2o11b2o4b2o$16b2o6b2o
10bo7b2o$16b2o5b3o10bo4bobo$24b2o10bo4bo$27b2o$27b2o!''', 14, 29)
LMBase += LM(55, 42, flip)
return LMTop(8 + loopm, -21 - loopm) + LMBase
def dmprinter(pdy, copies=1):
''' Generate & display a dot matrix printer for named bitmap pattern '''
#Horizontal pixel separation between LineMakers. minimum = 5
LMsx = 5
#Horizontal distance between bitmap pixels. Constant, due to LineMaker period
pdx = 15
#Distance between LineMakers
LMdx, LMdy = -LMsx * pdx, pdy
#Get bitmap pattern from current selection.
bm = get_bitmap()
#Make printer in a new layer
golly.duplicate()
golly.setoption("syncviews", False)
#Build new window title from old
title = golly.getname().split('.')[0]
title = '%s_Printer [%d] v0.10' % (title, pdy)
golly.new(title)
#Make sure we're using the standard Life generation rule
golly.setrule("B3/S23")
#Bitmap dimensions. Width MUST be of form 4m, for m >=1
bmheight = len(bm)
bmwidth = len(bm[0])
mid = (bmheight + 1) // 2
loopw = (bmwidth - 8) // 4
loopm = pdx * loopw
#Gliders, heading north-east
g0 = pattern('2bo$2o$b2o!')
g1 = pattern('obo$2o$bo!')
gliders = [g0, g1, g1(0, 2, rccw), g0(0, 2, rccw),
g0(2, 2, flip), g1(2, 2, flip), g1(2, 0, rcw), g0(2, 0, rcw)]
#Create full Glider loop.
gg = []
ox, oy = 35, 23
for j in range(loopw + 1):
dd = pdx * j
gg += [gliders[0](ox + dd, oy - dd), gliders[1](ox + 8 + dd, oy - 7 - dd)]
dd = loopm
gg += [gliders[2](45 + dd, 4 - dd), gliders[3](37 + dd, -3 - dd)]
ox, oy = 26 + loopm, -4 - loopm
for j in range(loopw + 1):
dd = pdx * j
gg += [gliders[4](ox - dd, oy + dd), gliders[5](ox - 8 - dd, oy + 7 + dd)]
dd = loopm
gg += [gliders[6](16, 15), gliders[7](24, 22)]
parity = 2*((loopw + 1)*(0, 0) + (1, 1))
def buildLM():
''' Build a complete LineMaker '''
#Populate glider loop. (jj, ii) are bitmap coords
gloop = pattern()
for j in range(bmwidth):
jj = (j - delta + bmwidth - 1) % bmwidth
#Is there a pixel at this location?
if bm[ii][jj] == parity[j]:
gloop += gg[j] #Add glider to the loop
#Only put LineMaker if glider loop isn't empty
if len(gloop) > 0:
(LMBlank + gloop).put(Lx, Ly, trans)
#Assemble blank LineMaker
LMBlank = linemaker(loopm)
#Do upper LineMakers
trans = identity
for i in range(mid):
ii = mid - (i + 1)
io = mid + (i + 1)
Lx, Ly = io * LMdx, ii * LMdy
delta = LMsx * io
buildLM()
#Do lower LineMakers
trans = flip_y
for i in range(mid, bmheight):
ii = i
io = i + 2
Lx, Ly = io * LMdx + pdx, ii * LMdy + 128
delta = LMsx * io - 1
buildLM()
#Eaters facing south-east & north-east
eaterSE = pattern('2o$bo$bobo$2b2o!')
eaterNE = eaterSE(0, 10, flip_y)
eY = 59
eaters = (eaterNE(0, eY), eaterSE(0, eY))
#Eater horizontal displacement. Must be odd
#bmwidth muliplier determines number of copies visible 'outside' printer.
eX = (bmheight + 1) * LMdx - (copies * bmwidth - 1) * pdx
eX = 1 + eX // 2 * 2 #Adjust parity
all = pattern()
for i in range(bmheight):
all += eaters[i % (1 + LMsx % 2)](eX, i * LMdy)
all.put()
#Centre view over bitmap output area
golly.setpos(str(-pdx * bmwidth // 2 + (bmheight - 1) * LMdx), str(Ly//2))
#golly.setmag(-2) #Aliasing effects happen at smaller scales than -2 :(
golly.fit()
def main():
#Vertical distance between pixels. Maybe get this from user. minimum = 16
pdy = 16
#Generate & display a dot matrix printer from current selection
dmprinter(pdy, copies=1)
golly.setcursor("Zoom In")
golly.setalgo("HashLife")
golly.setbase(2)
golly.setstep(6)
main()
Code: Select all
Rule:B2/S
Width:13
Height:20
Period:6
dx:0
dy:6
Diagonal width:0
Transformation:flip|
Symmetry:C1
Max cell count:0
Search order:automatic
Choice of state for unknown cells:alive
Skip patterns with subperiod.Code: Select all
x = 13, y = 20, rule = B2/S
.............$
.............$
.............$
.............$
.............$
.oo.......oo.$
o..o.....o..o$
.............$
.............$
.oo.......oo.$
o...........o$
...o.....o...$
....o...o....$
..o.......o..$
........o....$
..........o..$
.....o.......$
.o...........$
.............$
.............!That's not a bug. It flips itself every 6 gens.yujh wrote: ↑March 25th, 2021, 7:14 amGitHub connection bad(probably banned in other places, as tested), so I’ll report a bug of rlifesrc here@alephalpha it makes this resultCode: Select all
Rule:B2/S Width:13 Height:20 Period:6 dx:0 dy:6 Diagonal width:0 Transformation:flip| Symmetry:C1 Max cell count:0 Search order:automatic Choice of state for unknown cells:alive Skip patterns with subperiod.Code: Select all
x = 13, y = 20, rule = B2/S .............$ .............$ .............$ .............$ .............$ .oo.......oo.$ o..o.....o..o$ .............$ .............$ .oo.......oo.$ o...........o$ ...o.....o...$ ....o...o....$ ..o.......o..$ ........o....$ ..........o..$ .....o.......$ .o...........$ .............$ .............!
Unfortunately, this "glitch" also affects gfind and JLS-I don't know of a single spaceship search program that this "glitch" doesn't affect.
So I wrote a issue for this: https://github.com/AlephAlpha/rlifesrc/issues/48yujh wrote: ↑March 25th, 2021, 7:14 amGitHub connection bad(probably banned in other places, as tested), so I’ll report a bug of rlifesrc here@alephalpha it makes this resultCode: Select all
Rule:B2/S Width:13 Height:20 Period:6 dx:0 dy:6 Diagonal width:0 Transformation:flip| Symmetry:C1 Max cell count:0 Search order:automatic Choice of state for unknown cells:alive Skip patterns with subperiod.Code: Select all
x = 13, y = 20, rule = B2/S .............$ .............$ .............$ .............$ .............$ .oo.......oo.$ o..o.....o..o$ .............$ .............$ .oo.......oo.$ o...........o$ ...o.....o...$ ....o...o....$ ..o.......o..$ ........o....$ ..........o..$ .....o.......$ .o...........$ .............$ .............!
I think it is fixed now. But I'm not sure if there are new bugs.yujh wrote: ↑March 25th, 2021, 7:14 amGitHub connection bad(probably banned in other places, as tested), so I’ll report a bug of rlifesrc here@alephalpha it makes this resultCode: Select all
Rule:B2/S Width:13 Height:20 Period:6 dx:0 dy:6 Diagonal width:0 Transformation:flip| Symmetry:C1 Max cell count:0 Search order:automatic Choice of state for unknown cells:alive Skip patterns with subperiod.Code: Select all
x = 13, y = 20, rule = B2/S .............$ .............$ .............$ .............$ .............$ .oo.......oo.$ o..o.....o..o$ .............$ .............$ .oo.......oo.$ o...........o$ ...o.....o...$ ....o...o....$ ..o.......o..$ ........o....$ ..........o..$ .....o.......$ .o...........$ .............$ .............!