The Idea is something like Randomagar + ptbsearch; Generate a finite random soup, perturb it with some catalysts, and see if it stabilizes with the help of the catalyst. Even the eater is pretty rare in random ash, so its search space is not yet explored by Randomagar.
I couldn't had the time to make it into a C program, so I just sketched it into a python script. Here it is:
Code: Select all
import golly as g
import random
import time
# Thanks to Huy Nguyen's site for the timer code:
# http://www.huyng.com/posts/python-performance-analysis/
class Timer(object):
def __init__(self, verbose=False):
self.verbose = verbose
def __enter__(self):
self.start = time.time()
return self
def __exit__(self, *args):
self.end = time.time()
self.secs = self.end - self.start
self.msecs = self.secs * 1000 # millisecs
if self.verbose:
print 'elapsed time: {:.f} ms'.format(self.msecs)
class Catalyst(object):
def __init__(self, patrle, period, width, height, recoverrle=None):
if recoverrle == None:
recoverrle = patrle
patcelllist = g.parse(patrle)
recovercelllist = g.parse(recoverrle)
self.patcells = zip(patcelllist[::2], patcelllist[1::2])
self.period = period
self.width = width
self.height = height
self.recovercells = zip(recovercelllist[::2], recovercelllist[1::2])
# List of catalysts
eater = Catalyst('2o$o$b3o$3bo!', 1, 4, 4, 'bo$o$b3o$3bo!')
# List of symmetries
C1 = lambda (x, y): [(x, y)]
C21 = lambda (x, y): [(x, y), (-x, -y)]
C22 = lambda (x, y): [(x, y), (-x, -y-1)]
C24 = lambda (x, y): [(x, y), (-x-1, -y-1)]
C41 = lambda (x, y): [(x, y), (-y, x), (-x, -y), (y, -x)]
C44 = lambda (x, y): [(x, y), (-y-1, x), (-x-1, -y-1), (y, -x-1)]
D21 = lambda (x, y): [(x, y), (x, -y)]
D22 = lambda (x, y): [(x, y), (x, -y-1)]
D2X = lambda (x, y): [(x, y), (y, x)]
D41 = lambda (x, y): [(x, y), (x, -y), (-x, y), (-x, -y)]
D42 = lambda (x, y): [(x, y), (x, -y-1), (-x, y), (-x, -y-1)]
D44 = lambda (x, y): [(x, y), (x, -y-1), (-x-1, y), (-x-1, -y-1)]
D4X1 = lambda (x, y): [(x, y), (y, x), (-x, -y), (-y, -x)]
D4X4 = lambda (x, y): [(x, y), (y, x), (-x-1, -y-1), (-y-1, -x-1)]
D81 = lambda (x, y): [(x, y), (x, -y), (-x, y), (-x, -y), (y, x), (y, -x), (-y, x), (-y, -x)]
D84 = lambda (x, y): [(x, y), (x, -y-1), (-x-1, y), (-x-1, -y-1), (y, x), (y, -x-1), (-y-1, x), (-y-1, -x-1)]
class CatSoup(object):
symmetrydict = {'C1':C1, 'C21':C21, 'C22':C22, 'C24':C24, 'C41':C41, 'C44':C44,\
'D21':D21, 'D22':D22, 'D2X':D2X, 'D41':D41, 'D42':D42, 'D44':D44,\
'D4X1':D4X1, 'D4X4':D4X4, 'D81':D81, 'D84':D84}
def __init__(self, width, height, symstring, catalyst, spacing):
self.halfwidth = width/2
self.halfheight = height/2
self.widthparity = width%2
self.heightparity = height%2
self.symmetry = self.symmetrydict[symstring]
self.canonicalcells = self.getcanonicalcells(width, height)
self.catalyst = catalyst
self.catokaycells = self.getcatokaycells(width, height, spacing, catalyst)
def getcanonicalcells(self, width, height):
hrange = xrange((-height+1)/2, (height+1)/2)
wrange = xrange((-width+1)/2, (width+1)/2)
cells = [(w, h) for w in wrange for h in hrange]
canonical = []
dependent = []
for cell in cells:
if cell not in dependent:
canonical.append(cell)
dependent += self.symmetry(cell)
return canonical
def getcatokaycells(self, soupwidth, soupheight, spacing, catalyst):
hrange = xrange((-soupheight-catalyst.height+1)/2-spacing, (soupheight+1)/2+spacing)
wrange = xrange((-soupwidth-catalyst.width+1)/2-spacing, (soupwidth+1)/2+spacing)
souphrange = xrange((-soupheight-catalyst.height+1)/2-2, (soupheight+1)/2+2)
soupwrange = xrange((-soupwidth-catalyst.width+1)/2-2, (soupwidth+1)/2+2)
cells = [(w, h) for w in wrange for h in hrange if w not in soupwrange or h not in souphrange]
okaydict = {}
g.addlayer()
g.setrule('Life')
for px, py in cells:
if g.getrect() != []:
g.select(g.getrect())
g.clear(0)
for cx, cy in catalyst.patcells:
for x, y in self.symmetry((cx+px, cy+py)):
g.setcell(x, y, 1)
catfield = g.getcells(g.getrect())
g.run(catalyst.period)
if g.getcells(g.getrect()) == catfield:
okaydict[(px, py)] = catfield
g.dellayer()
return okaydict
def randfill(self):
# Generate random soup
n = len(self.canonicalcells)
canonicalbits = random.getrandbits(n)
oncells = []
oncelllist = []
for i in xrange(n):
if canonicalbits & (1<<i):
oncells += self.symmetry(self.canonicalcells[i])
for oncell in oncells:
oncelllist.append(oncell[0])
oncelllist.append(oncell[1])
catcell = random.choice(self.catokaycells.keys())
oncelllist += self.catokaycells[catcell]
return catcell, oncelllist
def symtest():
g.new('Symmetry Test')
g.setrule('Life')
g.setalgo('QuickLife')
symmetries = [['C1'], ['C21', 'C22', 'C24'], ['C41', 'C44'], ['D21', 'D22', 'D2X'],\
['D41', 'D42', 'D44', 'D4X1', 'D4X4'],['D81', 'D84']]
for i in range(len(symmetries)):
for j in range(len(symmetries[i])):
samplesoup = CatSoup(16, 16, symmetries[i][j], eater, 10)
catcell, celllist = samplesoup.randfill()
g.putcells(celllist, 100*j, 100*i)
g.fit()
# Code from oscar.py
class Oscar(object):
def __init__(self):
# initialize lists
self.hashlist = [] # for pattern hash values
self.genlist = [] # corresponding generation counts
self.poplist = [] # corresponding population counts
self.period = None
def reset(self):
# initialize lists
self.hashlist = [] # for pattern hash values
self.genlist = [] # corresponding generation counts
self.poplist = [] # corresponding population counts
self.period = None
def oscillating(self, prect):
# Test if pattern (without sparks) is empty:
cells = g.getcells(prect)
curpop = len(cells) # Current population * 2
for i in cells[::3]:
if i==1 or i==2:
break
else:
return True
curgen = int(g.getgen())
# Get current pattrn and create hash
h = g.hash(prect)
# determine where to insert h into self.hashlist
pos = 0
listlen = len(self.hashlist)
while pos < listlen:
if h > self.hashlist[pos]:
pos += 1
elif h < self.hashlist[pos]:
# shorten lists and append info below
del self.hashlist[pos : listlen]
del self.genlist[pos : listlen]
del self.poplist[pos : listlen]
break
else:
# h == self.hashlist[pos] so pattern is probably oscillating, but just in
# case this is a hash collision we also compare pop count and box size
if (curpop == self.poplist[pos]):
self.period = (curgen - self.genlist[pos])
return True
else:
# look at next matching hash value or insert if no more
pos += 1
# store hash/gen/pop/box info at same position in various lists
self.hashlist.insert(pos, h)
self.genlist.insert(pos, curgen)
self.poplist.insert(pos, curpop)
return False
def main():
g.setrule('Life')
g.setalgo('QuickLife')
soup = CatSoup(10, 10, 'C22', eater, 10)
oscar = Oscar()
soupcount = 0
display = 100
totaltime = inittime = souptime = gentime = 0
# Run soup
starttime = time.time()
while True:
with Timer() as inittimer:
g.new('Randcat')
g.setstep(3)
with Timer() as souptimer:
catpos, celllist = soup.randfill()
cx, cy = catpos
g.putcells(celllist)
souprect = g.getrect()
with Timer() as gentimer:
g.step()
soupcount += 1
# Check if eater is not destroyed:
for rx, ry in soup.catalyst.recovercells:
if g.getcell(cx+rx, cy+ry) == 0:
break
else:
oscar.reset()
while not oscar.oscillating(souprect):
g.run(1)
if oscar.period > 3:
g.reset()
g.setstep(0)
g.show("Oscillator detected (period = " + str(oscar.period) + ")")
break
inittime += inittimer.msecs
souptime += souptimer.msecs
gentime += gentimer.msecs
if soupcount % display == 0:
endtime = time.time()
totaltime = endtime-starttime
g.show('{0:.2f} soups/second; Init time: {1:.2f}ms, Soup time: {2:.2f}ms, Gen time: {3:.2f}ms'.format(soupcount/totaltime, inittime/display, souptime/display, gentime/display))
inittime = souptime = gentime = 0
g.fit()
g.update()
#symtest()
main()