I actually did this with v0.3 a while ago, since that version was made before Catagolue. Download the ordinary zip file from
Code: Select all
# Optimised soup searcher, v0.3 (beta release).
#
# -- Processes roughly 100 soups per (second . core . GHz).
#
# -- Can perfectly identify oscillators with period < 1000, well-separated
# spaceships of low period, and certain infinite-growth patterns (such
# guns and puffers, including both naturally-occurring types of switch
# engine).
#
# -- Separates most pseudo-objects into their constituent parts, including
# all pseudo-still-lifes of 18 or fewer live cells (which is the maximum
# theoretically possible, given there is a 19-cell pseudo-still-life
# with two distinct decompositions).
#
# -- Correctly separates non-interacting standard spaceships, irrespective
# of their proximity. In particular, a LWSS-on-LWSS is registered as two
# LWSSes, whereas an LWSS-on-HWSS is registered as a single spaceship
# (since they interact by suppressing sparks).
#
# -- At least 99.9999999% reliable at identifying objects.
#
# -- Scores soups based on the total excitement of the ash objects.
#
# By Adam P. Goucher, with contributions by Andrew Trevorrow,
# Tom Rokicki, Nathaniel Johnston and Dave Greene.
import golly as g
from glife import rect, pattern
import time
import math
import operator
import hashlib
import datetime
import os
# Takes approximately 350 microseconds to construct a 16-by-16 soup based
# on a SHA-256 cryptographic hash in the obvious way.
def hashsoup(instring):
thesoup = g.parse(g.getclipstr())
g.putcells(thesoup, -8, -8)
# Obtains a canonical representation of any oscillator/spaceship that (in
# some phase) fits within a 40-by-40 bounding box. This representation is
# alphanumeric and lowercase, and so much more compact than RLE. Compare:
#
# Common name: pentadecathlon
# Canonical representation: 4r4z4r4
# Equivalent RLE: 2bo4bo$2ob4ob2o$2bo4bo!
#
# It is a generalisation of a notation created by Allan Weschler in 1992.
def canonise(duration):
representation = "#"
# We need to compare each phase to find the one with the smallest
# description:
for t in xrange(duration):
rect = g.getrect()
if (len(rect) == 0):
return "0"
if ((rect[2] <= 40) & (rect[3] <= 40)):
# Fits within a 40-by-40 bounding box, so eligible to be canonised.
# Choose the orientation which results in the smallest description:
representation = compare_representations(representation, canonise_orientation(rect[2], rect[3], rect[0], rect[1], 1, 0, 0, 1))
representation = compare_representations(representation, canonise_orientation(rect[2], rect[3], rect[0]+rect[2]-1, rect[1], -1, 0, 0, 1))
representation = compare_representations(representation, canonise_orientation(rect[2], rect[3], rect[0], rect[1]+rect[3]-1, 1, 0, 0, -1))
representation = compare_representations(representation, canonise_orientation(rect[2], rect[3], rect[0]+rect[2]-1, rect[1]+rect[3]-1, -1, 0, 0, -1))
representation = compare_representations(representation, canonise_orientation(rect[3], rect[2], rect[0], rect[1], 0, 1, 1, 0))
representation = compare_representations(representation, canonise_orientation(rect[3], rect[2], rect[0]+rect[2]-1, rect[1], 0, -1, 1, 0))
representation = compare_representations(representation, canonise_orientation(rect[3], rect[2], rect[0], rect[1]+rect[3]-1, 0, 1, -1, 0))
representation = compare_representations(representation, canonise_orientation(rect[3], rect[2], rect[0]+rect[2]-1, rect[1]+rect[3]-1, 0, -1, -1, 0))
g.run(1)
return representation
# A subroutine used by canonise:
def canonise_orientation(length, breadth, ox, oy, a, b, c, d):
representation = ""
chars = "0123456789abcdefghijklmnopqrstuvwxyz"
for v in xrange(int((breadth-1)/5)+1):
zeroes = 0
if (v != 0):
representation += "z"
for u in xrange(length):
baudot = 0
for w in xrange(5):
x = ox + a*u + b*(5*v + w)
y = oy + c*u + d*(5*v + w)
baudot = (baudot >> 1) + 16*g.getcell(x, y)
if (baudot == 0):
zeroes += 1
else:
if (zeroes > 0):
if (zeroes == 1):
representation += "0"
elif (zeroes == 2):
representation += "w"
elif (zeroes == 3):
representation += "x"
else:
representation += "y"
representation += chars[zeroes - 4]
zeroes = 0
representation += chars[baudot]
return representation
# Compares strings first by length, then by lexicographical ordering.
# A hash character is worse than anything else.
def compare_representations(a, b):
if (a == "#"):
return b
elif (b == "#"):
return a
elif (len(a) < len(b)):
return a
elif (len(b) < len(a)):
return b
elif (a < b):
return a
else:
return b
# This explodes pseudo-still-lifes and pseudo-oscillators into their
# constituent parts.
#
# -- Requires the period (if oscillatory) and graph-theoretic diameter
# to not exceed 4096.
# -- Never mistakenly separates a true object.
# -- Correctly separates most pseudo-still-lifes, including the famous:
# http://www.conwaylife.com/wiki/Quad_pseudo_still_life
# -- Works perfectly for all still-lifes of up to 17 bits.
# -- Doesn't separate 'locks', of which the smallest example has 18
# bits and is unique:
#
# ** **
# ** **
#
# * *** *
# ** * **
#
# To use this function (standalone), merely copy it into a script of
# the following form:
#
# import golly as g
#
# def pseudo_bangbang():
#
# [...]
#
# pseudo_bangbang()
#
# and execute it in Golly with a B3/S23 universe containing any still-
# lifes or oscillators you want to separate. Pure objects correspond to
# connected components in the final state of the universe.
#
# This has dependencies on the rules ContagiousLife, PercolateInfection
# and EradicateInfection.
#
# Not to be confused with the Unix shell instruction for repeating the
# previous instruction as a superuser (sudo !!), or indeed with any
# parodies of this song: https://www.youtube.com/watch?v=YswhUHH6Ufc
#
# Adam P. Goucher, 2014-08-25
def pseudo_bangbang():
g.setrule("ContagiousLife")
g.setbase(2)
g.setstep(12)
g.step()
celllist = g.getcells(g.getrect())
for i in xrange(0, len(celllist)-1, 3):
# Only infect cells that haven't yet been infected:
if (g.getcell(celllist[i], celllist[i+1]) <= 2):
# Seed an initial 'infected' (red) cell:
g.setcell(celllist[i], celllist[i+1], g.getcell(celllist[i], celllist[i+1]) + 2)
prevpop = 0
currpop = int(g.getpop())
# Continue infecting until the entire component has been engulfed:
while (prevpop != currpop):
# Percolate the infection to every cell in the island:
g.setrule("PercolateInfection")
g.setbase(2)
g.setstep(12)
g.step()
# Transmit the infection across any bridges.
g.setrule("ContagiousLife")
g.setbase(2)
g.setstep(12)
g.step()
prevpop = currpop
currpop = int(g.getpop())
g.fit()
g.update()
# Red becomes green:
g.setrule("EradicateInfection")
g.step()
# Counts the number of live cells of each degree:
def degreecount():
celllist = g.getcells(g.getrect())
counts = [0,0,0,0,0,0,0,0,0]
for i in xrange(0, len(celllist), 2):
x = celllist[i]
y = celllist[i+1]
degree = -1
for ux in xrange(x - 1, x + 2):
for uy in xrange(y - 1, y + 2):
degree += g.getcell(ux, uy)
counts[degree] += 1
return counts
# Counts the number of live cells of each degree in generations 1 and 2:
def degreecount2():
g.run(1)
a = degreecount()
g.run(1)
b = degreecount()
return (a + b)
# If the universe consists only of disjoint *WSSes, this will return
# a triple (l, w, h) giving the quantities of each *WSS. Otherwise,
# this function will return (-1, -1, -1).
#
# This should only be used to separate period-4 moving objects which
# may contain multiple *WSSes.
def countxwsses():
degcount = degreecount2()
if (degreecount2() != degcount):
# Degree counts are not period-2:
return (-1, -1, -1)
# Degree counts of each standard spaceship:
hwssa = [1,4,6,2,0,0,0,0,0,0,0,0,4,4,6,1,2,1]
mwssa = [2,2,5,2,0,0,0,0,0,0,0,0,4,4,4,1,2,0]
lwssa = [1,2,4,2,0,0,0,0,0,0,0,0,4,4,2,2,0,0]
hwssb = [0,0,0,4,4,6,1,2,1,1,4,6,2,0,0,0,0,0]
mwssb = [0,0,0,4,4,4,1,2,0,2,2,5,2,0,0,0,0,0]
lwssb = [0,0,0,4,4,2,2,0,0,1,2,4,2,0,0,0,0,0]
# Calculate the number of standard spaceships in each phase:
hacount = degcount[17]
macount = degcount[16]/2 - hacount
lacount = (degcount[15] - hacount - macount)/2
hbcount = degcount[8]
mbcount = degcount[7]/2 - hbcount
lbcount = (degcount[6] - hbcount - mbcount)/2
# Determine the expected degcount given the calculated quantities:
pcounts = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
pcounts = map(lambda x, y: x + y, pcounts, map(lambda x: hacount*x, hwssa))
pcounts = map(lambda x, y: x + y, pcounts, map(lambda x: macount*x, mwssa))
pcounts = map(lambda x, y: x + y, pcounts, map(lambda x: lacount*x, lwssa))
pcounts = map(lambda x, y: x + y, pcounts, map(lambda x: hbcount*x, hwssb))
pcounts = map(lambda x, y: x + y, pcounts, map(lambda x: mbcount*x, mwssb))
pcounts = map(lambda x, y: x + y, pcounts, map(lambda x: lbcount*x, lwssb))
# Compare the observed and expected degcounts (to eliminate nonstandard spaceships):
if (pcounts != degcount):
# Expected and observed values do not match:
return (-1, -1, -1)
# Return the combined numbers of *WSSes:
return(lacount + lbcount, macount + mbcount, hacount + hbcount)
class Soup:
# A dict to store memoized decompositions of possibly-pseudo-objects
# into constituent parts. This is initialised with the unique minimal
# pseudo-still-life (two blocks on lock) that cannot be automatically
# separated by the routine pseudo_bangbang(). Any larger objects are
# ambiguous, such as this one:
#
# *
# * * **
# ** **
#
# * *** *
# ** * **
#
# Is it a (block on (lock on boat)) or ((block on lock) on boat)?
# Ahh, the joys of non-associativity.
#
# See http://paradise.caltech.edu/~cook/Workshop/CAs/2DOutTot/Life/StillLife/StillLifeTheory.html
decompositions = {"xs18_3pq3qp3": ["xs14_3123qp3", "xs4_33"]}
# A dict of objects in the form {"identifier": ("common name", points)}
#
# As a rough heuristic, an object is worth 15 + log2(n) points if it
# is n times rarer than the pentadecathlon.
commonnames = {"xp3_co9nas0san9oczgoldlo0oldlogz1047210127401": ("pulsar", 9),
"xp15_4r4z4r4": ("pentadecathlon", 15),
"xp2_31ago": ("bipole", 17),
"xp2_0g0k053z32": ("quadpole", 17),
"xp2_g8gid1e8z1226": ("great on-off", 18),
"xp2_rhewehr": ("spark coil", 18),
"xp8_gk2gb3z11": ("figure-8", 19),
"xp4_37bkic": ("mold", 20),
"xp2_31a08zy0123cko": ("quadpole on ship", 20),
"xp2_g0k053z11": ("tripole", 20),
"xp4_ssj3744zw3": ("mazing", 22),
"xp8_g3jgz1ut": ("blocker", 23),
"xp3_695qc8zx33": ("jam", 23),
"xp30_w33z8kqrqk8zzzw33": ("cis-queen-bee-shuttle", 23),
"xp30_w33z8kqrqk8zzzx33": ("trans-queen-bee-shuttle", 23),
"xp4_8eh5e0e5he8z178a707a871": ("cloverleaf", 24),
"xp5_idiidiz01w1": ("octagon II", 25),
"xp6_ccb7w66z066": ("unix", 25),
"xp14_j9d0d9j": ("tumbler", 26),
"xp3_025qzrq221": ("trans-tub-eater", 27),
"xp3_4hh186z07": ("caterer", 28),
"xp3_025qz32qq1": ("cis-tub-eater", 29),
"xp8_wgovnz234z33": ("Tim Coe's p8", 30),
"xp5_3pmwmp3zx11": ("fumarole", 32),
"xq288_gg8ugicy333oooz1o0h8y9355y133zw1yboozwo772zw1": ("block-laying switch engine", 14),
"xq384_037boz0gg1ya33zg978y988y3ooz0120d52y6gsxgzyf4c4qf6xgy0ggzy233y4eaj44swewg0h0vooog9ezye111y51zyu8kc": ("glider-producing switch engine", 16),
"xq4_6frc": ("lightweight spaceship", 8),
"xq4_27dee6": ("middleweight spaceship", 10),
"xq4_27deee6": ("heavyweight spaceship", 12),
"xq4_153": ("glider", 0),
"xp2_7": ("blinker", 0),
"xs4_33": ("block", 0),
"xs4_252": ("tub", 0),
"xs5_253": ("boat", 0),
"xs6_bd": ("snake", 0),
"xs6_356": ("ship", 0),
"xs6_696": ("beehive", 0),
"xs6_25a4": ("barge", 0),
"xs6_39c": ("carrier", 0),
"xp2_7e": ("toad", 0),
"xp2_2a54": ("clock", 0),
"xp2_318c": ("beacon", 0),
"xs7_3lo": ("long snake", 0),
"xs7_25ac": ("long boat", 0),
"xs7_178c": ("eater", 0),
"xs7_2596": ("loaf", 0),
"xs8_178k8": ("twit", 0),
"xs8_32qk": ("hook with tail", 0),
"xs8_69ic": ("mango", 0),
"xs8_6996": ("pond", 0),
"xs8_25ak8": ("long barge", 0),
"xs8_3pm": ("shillelagh", 0),
"xs8_312ko": ("canoe", 0),
"xs8_31248c": ("very long snake", 0),
"xs8_35ac": ("long ship", 0),
"xs12_g8o653z11": ("ship-tie", 0),
"xs14_g88m952z121": ("half-bakery", 0),
"xs14_69bqic": ("paperclip", 0),
"xs9_31ego": ("integral sign", 0),
"xs10_g8o652z01": ("boat-tie", 0),
"xs14_g88b96z123": ("big ess", 0),
"xs16_g88m996z1221": ("bipond", 0),
"xs12_raar": ("table on table", 0),
"xs9_4aar": ("hat", 0),
"xs10_35ako": ("very long ship", 0),
"xs9_178ko": ("trans-boat-with-tail", 0),
"xs15_354cgc453": ("moose antlers", 0),
"xs14_6970796": ("cis-mirrored r-bee", 0),
"xs10_32qr": ("block on table", 0),
"xs16_j1u0696z11": ("beehive on dock", 0),
"xs14_j1u066z11": ("block on dock", 0),
"xs11_g8o652z11": ("boat-tie-ship", 0),
"xs9_25ako": ("very long boat", 0),
"xs16_69egmiczx1": ("scorpion", 0),
"xs18_rhe0ehr": ("dead spark coil", 0),
"xs17_2ege1ege2": ("twinhat", 0),
"xs10_178kk8": ("beehive with tail", 0),
"xs10_69ar": ("loop", 0),
"xs14_69bo8a6": ("fourteener", 0),
"xs14_39e0e93": ("bookends", 0),
"xs9_178kc": ("cis-boat-with-tail", 0)}
# A tally of objects that have occurred during this run of apgsearch:
objectcounts = {}
# Any soups with positive scores, and the number of points.
soupscores = {}
# Temporary list of unidentified objects:
unids = []
# Things like glider guns and large oscillators belong here:
superunids = []
gridsize = 0
resets = 0
# For profiling purposes:
qlifetime = 0.0
ruletime = 0.0
gridtime = 0.0
# Increment object count by given value:
def incobject(self, obj, incval):
if (incval > 0):
if obj in self.objectcounts:
self.objectcounts[obj] = self.objectcounts[obj] + incval
else:
self.objectcounts[obj] = incval
# Increment soup score by given value:
def awardpoints(self, soupid, incval):
if (incval > 0):
if soupid in self.soupscores:
self.soupscores[soupid] = self.soupscores[soupid] + incval
else:
self.soupscores[soupid] = incval
# Increment soup score by appropriate value:
def awardpoints2(self, soupid, obj):
if obj in self.commonnames:
self.awardpoints(soupid, self.commonnames[obj][1])
elif (obj[0] == 'x'):
prefix = obj.split('_')[0]
prenum = int(prefix[2:])
if (obj[1] == 's'):
self.awardpoints(soupid, 10) # rare still-lifes are limited to 10 points
elif (obj[1] == 'p'):
if (prenum == 2):
self.awardpoints(soupid, 20) # p2 oscillators are limited to 20 points
elif ((prenum == 3) | (prenum == 4)):
self.awardpoints(soupid, 30) # p3 and p4 oscillators are limited to 30 points
else:
self.awardpoints(soupid, 40)
else:
self.awardpoints(soupid, 50)
else:
self.awardpoints(soupid, 50)
# Assuming the pattern has stabilised, perform a census:
def census(self, stepsize):
g.setrule("CoalesceObjects")
g.setbase(2)
g.setstep(stepsize)
g.step()
g.setrule("IdentifyGliders")
g.setbase(2)
g.setstep(2)
g.step()
g.setrule("ClassifyObjects")
g.setbase(2)
g.setstep(max(8, stepsize))
g.step()
# Only do this if we have an infinite-growth pattern:
if (stepsize > 8):
g.setrule("HandlePlumes")
g.setbase(2)
g.setstep(1)
g.step()
g.setrule("ClassifyObjects")
g.setstep(stepsize)
g.step()
# Remove any gliders:
g.setrule("ExpungeGliders")
g.run(1)
pop5 = int(g.getpop())
g.run(1)
pop6 = int(g.getpop())
self.incobject("xq4_153", (pop5 - pop6)/5)
# Remove any blocks, blinkers and beehives:
g.setrule("ExpungeObjects")
g.run(1)
pop1 = int(g.getpop())
g.run(1)
pop2 = int(g.getpop())
g.run(1)
pop3 = int(g.getpop())
g.run(1)
pop4 = int(g.getpop())
# Blocks, blinkers and beehives removed by ExpungeObjects:
self.incobject("xs4_33", (pop1-pop2)/4)
self.incobject("xp2_7", (pop2-pop3)/5)
self.incobject("xs6_696", (pop3-pop4)/8)
# Removes an object incident with (ix, iy) and returns the cell list:
def grabobj(self, ix, iy):
allcells = [ix, iy, g.getcell(ix, iy)]
g.setcell(ix, iy, 0)
livecells = []
deadcells = []
marker = 0
ll = 3
while (marker < ll):
x = allcells[marker]
y = allcells[marker+1]
z = allcells[marker+2]
marker += 3
if ((z % 2) == 1):
livecells.append(x)
livecells.append(y)
else:
deadcells.append(x)
deadcells.append(y)
for nx in xrange(x - 1, x + 2):
for ny in xrange(y - 1, y + 2):
nz = g.getcell(nx, ny)
if (nz > 0):
allcells.append(nx)
allcells.append(ny)
allcells.append(nz)
g.setcell(nx, ny, 0)
ll += 3
return livecells
# Command to Grab, Remove and IDentify an OBJect:
def gridobj(self, ix, iy):
allcells = [ix, iy, g.getcell(ix, iy)]
g.setcell(ix, iy, 0)
livecells = []
deadcells = []
# This tacitly assumes the object is smaller than 1000-by-1000.
# But this is okay, since it is only used by the routing logic.
dleft = ix + 1000
dright = ix - 1000
dtop = iy + 1000
dbottom = iy - 1000
lleft = ix + 1000
lright = ix - 1000
ltop = iy + 1000
lbottom = iy - 1000
lpop = 0
dpop = 0
marker = 0
ll = 3
while (marker < ll):
x = allcells[marker]
y = allcells[marker+1]
z = allcells[marker+2]
marker += 3
if ((z % 2) == 1):
livecells.append(x)
livecells.append(y)
lleft = min(lleft, x)
lright = max(lright, x)
ltop = min(ltop, y)
lbottom = max(lbottom, y)
lpop += 1
else:
deadcells.append(x)
deadcells.append(y)
dleft = min(dleft, x)
dright = max(dright, x)
dtop = min(dtop, y)
dbottom = max(dbottom, y)
dpop += 1
for nx in xrange(x - 1, x + 2):
for ny in xrange(y - 1, y + 2):
nz = g.getcell(nx, ny)
if (nz > 0):
allcells.append(nx)
allcells.append(ny)
allcells.append(nz)
g.setcell(nx, ny, 0)
ll += 3
lwidth = max(0, 1 + lright - lleft)
lheight = max(0, 1 + lbottom - ltop)
dwidth = max(0, 1 + dright - dleft)
dheight = max(0, 1 + dbottom - dtop)
llength = max(lwidth, lheight)
lbreadth = min(lwidth, lheight)
dlength = max(dwidth, dheight)
dbreadth = min(dwidth, dheight)
self.gridsize = max(self.gridsize, llength)
# **** Routing logic ****
#
# This checks against definitions of known small common objects
# in B3/S23, so that they don't have to be 'manually' canonised.
objid = "unidentified"
if (lpop < 3):
objid = "nothing"
elif (lpop == 3):
objid = "xp2_7" #blinker
elif (lpop == 4):
if (dpop == 0):
objid = "xs4_33" #block
else:
objid = "xs4_252" #tub
elif (lpop == 5):
if (dpop == 1):
objid = "xs5_253" #boat
else:
objid = "xq4_153" #glider
elif (lpop == 6):
if (dpop == 1):
objid = "xs6_356" #ship
else:
if (lbreadth == 2):
if (dpop == 2):
objid = "xs6_bd" #snake
else:
objid = "xp2_7e" #toad in resting phase
elif (lbreadth == 4):
if (dpop == 2):
objid = "xs6_25a4" #barge
elif (dpop == 6):
objid = "xp2_2a54" #clock
else:
objid = "xp2_7e" #toad in panting phase
for i in xrange(0, 12, 2):
if (livecells[i] == lleft):
if (livecells[i + 1] == ltop | livecells[i + 1] == lbottom):
objid = "xp2_318c" #beacon
else:
objid = "xs6_696" #beehive
for i in xrange(0, 12, 2):
if (livecells[i] == lleft):
if (livecells[i + 1] == ltop | livecells[i + 1] == lbottom):
objid = "xs6_39c" #aircraft carrier
elif (lpop == 7):
if (dpop == 2):
if (dlength == 3):
objid = "xs7_3lo" #long snake
else:
objid = "xs7_25ac" #long boat
else:
if (dlength == 3):
objid = "xs7_178c" #eater (fishhook)
else:
objid = "xs7_2596" #loaf
elif (lpop == 8):
if (dpop == 4):
if (dlength == 4):
if (lbreadth == 5):
objid = "xs8_178k8" #tub with tail
else:
objid = "xs8_32qk" #hook with tail
elif (dlength == 3):
objid = "xs8_69ic" #mango
else:
objid = "xs8_6996" #pond
elif (dpop == 3):
if (lbreadth == 5):
objid = "xs8_25ak8" #long barge
else:
objid = "xs8_3pm" #shillelagh
else:
if (lbreadth == 2):
objid = "xs8_rr" #block on block
elif (lbreadth == 5):
objid = "xs8_312ko" #canoe
elif (lbreadth == 4):
if (llength == 6):
objid = "xs8_31248c" #very long snake
else:
diagcount = 0
for i in xrange(0, 12, 2):
if ((livecells[i] - lleft) == (livecells[i + 1] - ltop)):
diagcount += 1
if (diagcount == 2):
objid = "xs8_35ac" #long ship
else:
objid = "xp2_318c" #beacon
elif (lpop == 12):
# Ship-ties are just about common enough to warrant being handled in the routing logic:
if ((lwidth == 6) & (lheight == 6)):
bitstring = 0
for i in xrange(0, 24, 2):
bitstring += (1 << ((livecells[i] - lleft) + 6*(livecells[i + 1] - ltop)))
if ((bitstring == 52217012547) | (bitstring == 3306785328)):
objid = "xs12_g8o653z11"
elif (lpop == 14):
# As is the miraculous half-bakery:
if ((lwidth == 7) & (lheight == 7)):
bitstring = 0
for i in xrange(0, 28, 2):
bitstring += (1 << ((livecells[i] - lleft) + 7*(livecells[i + 1] - ltop)))
if ((bitstring == 213590917399170) | (bitstring == 8970354435120) |
(bitstring == 26700311308320) | (bitstring == 143505703994502)):
objid = "xs14_g88m952z121"
# **** End of routing logic ****
if (objid == "xs8_rr"):
# A biblock should be registered as two blocks:
self.incobject("xs4_33", 2)
elif (objid == "unidentified"):
# This has passed through the routing logic without being identified,
# so save it in a temporary list for later identification:
self.unids.append(livecells)
self.unids.append(lleft)
self.unids.append(ltop)
elif (objid != "nothing"):
# The object is non-empty, so add it to the census:
self.incobject(objid, 1)
# Tests for population periodicity:
def naivestab(self, period, security, length):
depth = 0
prevpop = 0
for i in xrange(length):
g.run(period)
currpop = int(g.getpop())
if (currpop == prevpop):
depth += 1
else:
depth = 0
prevpop = currpop
if (depth == security):
# Population is periodic.
return True
return False
# This should catch most short-lived soups with few gliders produced:
def naivestab2(self, period, length):
for i in xrange(length):
r = g.getrect()
if (len(r) == 0):
return True
pop0 = int(g.getpop())
g.run(period)
hash1 = g.hash(r)
pop1 = int(g.getpop())
g.run(period)
hash2 = g.hash(r)
pop2 = int(g.getpop())
if ((hash1 == hash2) & (pop0 == pop1) & (pop1 == pop2)):
if (g.getrect() == r):
return True
g.run((2*int(max(r[2], r[3])/period)+1)*period)
hash3 = g.hash(r)
pop3 = int(g.getpop())
if ((hash2 == hash3) & (pop2 == pop3)):
return True
return False
# Runs a pattern until stabilisation with a 99.99996% success rate.
# False positives are handled by a later error-correction stage.
def stabilise3(self):
# Phase I of stabilisation detection, designed to weed out patterns
# that stabilise into a cluster of low-period oscillators within
# about 6000 generations.
if (self.naivestab2(12, 10)):
return 4;
if (self.naivestab(12, 30, 200)):
return 4;
if (self.naivestab(30, 30, 200)):
return 5;
# Phase II of stabilisation detection, which is much more rigorous
# and based on oscar.py.
# Should be sufficient:
prect = [-2000, -2000, 4000, 4000]
# initialize lists
hashlist = [] # for pattern hash values
genlist = [] # corresponding generation counts
for j in xrange(4000):
g.run(30)
h = g.hash(prect)
# determine where to insert h into hashlist
pos = 0
listlen = len(hashlist)
while pos < listlen:
if h > hashlist[pos]:
pos += 1
elif h < hashlist[pos]:
# shorten lists and append info below
del hashlist[pos : listlen]
del genlist[pos : listlen]
break
else:
period = (int(g.getgen()) - genlist[pos])
prevpop = g.getpop()
for i in xrange(20):
g.run(period)
currpop = g.getpop()
if (currpop != prevpop):
period = max(period, 4000)
break
prevpop = currpop
return max(1 + int(math.log(period, 2)),3)
hashlist.insert(pos, h)
genlist.insert(pos, int(g.getgen()))
g.setalgo("HashLife")
g.setbase(2)
g.setstep(16)
g.step()
stepsize = 12
g.setalgo("QuickLife")
return 12
# Differs from oscar.py in that it detects absolute cycles, not eventual cycles.
def bijoscar(self, maxsteps):
initpop = int(g.getpop())
initrect = g.getrect()
if (len(initrect) == 0):
return 0
inithash = g.hash(initrect)
for i in xrange(maxsteps):
g.run(1)
if (int(g.getpop()) == initpop):
prect = g.getrect()
phash = g.hash(prect)
if (phash == inithash):
period = i + 1
if (prect == initrect):
return period
else:
return -period
return -1
# For a non-moving unidentified object, we check the dictionary of
# memoized decompositions of possibly-pseudo-objects. If the object is
# not already in the dictionary, it will be memoized.
#
# Low-period spaceships are also separated by this routine, although
# this is less important now that there is a more bespoke prodecure
# to handle disjoint unions of standard spaceships.
#
# @param moving a bool which specifies whether the object is moving
def enter_unid(self, unidname, soupid, moving):
if not(unidname in self.decompositions):
# Separate into pure components:
if (moving):
g.setrule("CoalesceObjects")
g.setbase(2)
g.setstep(3)
g.step()
else:
pseudo_bangbang()
listoflists = [] # which incidentally don't contain themselves.
# Someone who plays the celllo:
celllist = g.join(g.getcells(g.getrect()), [0])
for i in xrange(0, len(celllist)-1, 3):
if (g.getcell(celllist[i], celllist[i+1]) != 0):
livecells = self.grabobj(celllist[i], celllist[i+1])
if (len(livecells) > 0):
listoflists.append(livecells)
listofobjs = []
for livecells in listoflists:
g.new("Subcomponent")
g.setalgo("QuickLife")
g.setrule("B3/S23")
g.putcells(livecells)
period = self.bijoscar(1000)
canonised = canonise(abs(period))
if (period < 0):
listofobjs.append("xq"+str(0-period)+"_"+canonised)
elif (period == 1):
listofobjs.append("xs"+str(len(livecells)/2)+"_"+canonised)
else:
listofobjs.append("xp"+str(period)+"_"+canonised)
self.decompositions[unidname] = listofobjs
# Actually add to the census:
for comp in self.decompositions[unidname]:
self.incobject(comp, 1)
self.awardpoints2(soupid, comp)
# This function has lots of arguments (hence the name):
#
# @param gsize the square-root of the number of soups per page
# @param gspacing the minimum distance between centres of soups
# @param ashes a list of cell lists
# @param stepsize binary logarithm of amount of time to coalesce objects
# @param intergen binary logarithm of amount of time to run HashLife
# @param pos the index of the first soup on the page
def teenager(self, gsize, gspacing, ashes, stepsize, intergen, pos):
# For error-correction:
if (intergen > 0):
g.setalgo("HashLife")
g.setrule("B3/S23")
# If this gets incremented, we panic and perform error-correction:
pathological = 0
# Draw the soups:
for i in xrange(gsize * gsize):
x = int(i % gsize)
y = int(i / gsize)
g.putcells(ashes[3*i], gspacing * x, gspacing * y)
# Because why not?
g.fit()
g.update()
# For error-correction:
if (intergen > 0):
g.setbase(2)
g.setstep(intergen)
g.step()
# Apply rules to coalesce objects and expunge annoyances such as
# blocks, blinkers, beehives and gliders:
start_time = time.clock()
self.census(stepsize)
end_time = time.clock()
self.ruletime += (end_time - start_time)
# Now begin identifying objects:
start_time = time.clock()
celllist = g.join(g.getcells(g.getrect()), [0])
if (len(celllist) > 2):
for i in xrange(0, len(celllist)-1, 3):
if (g.getcell(celllist[i], celllist[i+1]) != 0):
self.gridobj(celllist[i], celllist[i+1])
# If we have leftover unidentified objects, attempt to canonise them:
while (len(self.unids) > 0):
ux = int(0.5 + float(self.unids[-2])/float(gspacing))
uy = int(0.5 + float(self.unids[-1])/float(gspacing))
soupid = ux + (uy * gsize) + pos
unidname = self.process_unid()
if (unidname == "PATHOLOGICAL"):
pathological += 1
if (unidname != "nothing"):
if ((unidname[0] == 'U') & (unidname[1] == 'S') & (unidname[2] == 'S')):
# Union of standard spaceships:
countlist = unidname.split('_')
self.incobject("xq4_6frc", int(countlist[1]))
for i in xrange(int(countlist[1])):
self.awardpoints2(soupid, "xq4_6frc")
self.incobject("xq4_27dee6", int(countlist[2]))
for i in xrange(int(countlist[2])):
self.awardpoints2(soupid, "xq4_27dee6")
self.incobject("xq4_27deee6", int(countlist[3]))
for i in xrange(int(countlist[3])):
self.awardpoints2(soupid, "xq4_27deee6")
elif ((unidname[0] == 'x') & ((unidname[1] == 's') | (unidname[1] == 'p'))):
self.enter_unid(unidname, soupid, False)
else:
if ((unidname[0] == 'x') & (unidname[1] == 'q') & (unidname[3] == '_')):
# Separates low-period (<= 9) non-standard spaceships in medium proximity:
self.enter_unid(unidname, soupid, True)
else:
self.incobject(unidname, 1)
self.awardpoints2(soupid, unidname)
end_time = time.clock()
self.gridtime += (end_time - start_time)
return pathological
# This basically orchestrates everything:
def stabilise_soups_parallel(self, root, pos, gsize):
ashes = []
stepsize = 3
g.new("Random soups")
g.setalgo("QuickLife")
g.setrule("B3/S23")
gspacing = 0
# Generate and run the soups until stabilisation:
for i in xrange(gsize * gsize):
# Generate the soup from the SHA-256 of the concatenation of the
# seed with the index:
hashsoup(root + str(pos + i))
# Run the soup until stabilisation:
start_time = time.clock()
stepsize = max(stepsize, self.stabilise3())
end_time = time.clock()
self.qlifetime += (end_time - start_time)
# Ironically, the spelling of this variable is incurrrect:
currrect = g.getrect()
ashes.append(g.getcells(currrect))
if (len(currrect) == 4):
ashes.append(currrect[0])
ashes.append(currrect[1])
# Choose the grid spacing based on the size of the ash:
gspacing = max(gspacing, 2*currrect[2])
gspacing = max(gspacing, 2*currrect[3])
g.select(currrect)
g.clear(0)
else:
ashes.append(0)
ashes.append(0)
g.select([])
# Account for any extra enlargement caused by running CoalesceObjects:
gspacing += 2 ** (stepsize + 1) + 1000
# Remember the dictionary, just in case we have a pathological object:
prevdict = self.objectcounts.copy()
prevscores = self.soupscores.copy()
prevunids = self.superunids[:]
if (self.teenager(gsize, gspacing, ashes, stepsize, 0, pos) > 0):
# Arrrggghhhh, there's a pathological object!
# Usually this means that naive stabilisation detection returned a false positive.
self.resets += 1
# Reset the object counts:
self.objectcounts = prevdict
self.soupscores = prevscores
self.superunids = prevunids
# 2^18 generations should suffice. This takes about 30 seconds in
# HashLife, but error-correction only occurs very infrequently, so
# this has a negligible impact on mean performance:
gspacing += 2 ** 19
stepsize = max(stepsize, 12)
# Clear the universe:
g.new("Error-correcting phase")
self.teenager(gsize, gspacing, ashes, stepsize, 18, pos)
# Erase any ashes. Not least because England usually loses...
ashes = []
# Pop the last unidentified object from the stack, and attempt to
# ascertain its period and classify it.
def process_unid(self):
g.new("Unidentified object")
g.setalgo("QuickLife")
g.setrule("B3/S23")
y = self.unids.pop()
x = self.unids.pop()
livecells = self.unids.pop()
g.putcells(livecells, -x, -y, 1, 0, 0, 1, "or")
period = self.bijoscar(1000)
if (period == -1):
# Infinite growth pattern, probably. The only infinite-growth
# patterns that have been known to occur naturally in the history
# of GoL are the block-laying and glider-producing switch-engines,
# so we include code for identifying probable switch-engines.
prevpop = g.getpop()
for i in xrange(20):
g.run(1152)
currpop = g.getpop()
diff = int(currpop) - int(prevpop)
if ((diff != 128) & (diff != 177)):
# not a switch engine
break
prevpop = currpop
if (i == 19):
if (diff == 128):
# block-laying switch engine
return "xq288_gg8ugicy333oooz1o0h8y9355y133zw1yboozwo772zw1"
else:
# glider-producing switch engine
return "xq384_037boz0gg1ya33zg978y988y3ooz0120d52y6gsxgzyf4c4qf6xgy0ggzy233y4eaj44swewg0h0vooog9ezye111y51zyu8kc"
# Okay, so it's not a switch-engine. It may be an unstabilised
# ember that slipped through the net, but this will be handled
# by error-correction (unless it persists another 2^18 gens,
# which is so unbelievably improbable that you are more likely
# to be picked up by a passing ship in the vacuum of space).
self.superunids.append(livecells)
self.superunids.append(x)
self.superunids.append(y)
return "PATHOLOGICAL"
elif (period == 0):
return "nothing"
else:
if (period == -4):
triple = countxwsses()
if (triple != (-1, -1, -1)):
# Union of Standard Spaceships:
return ("USS_" + str(triple[0]) + "_" + str(triple[1]) + "_" + str(triple[2]))
canonised = canonise(abs(period))
if (canonised == "#"):
# Okay, we know that it's an oscillator or spaceship with
# a non-astronomical period. But it's too large to canonise
# in any of its phases (i.e. transcends a 40-by-40 box).
self.superunids.append(livecells)
self.superunids.append(x)
self.superunids.append(y)
return "OVERSIZED"
else:
# Prepend a prefix according to whether it is a still-life,
# oscillator or moving object:
if (period == 1):
return ("xs"+str(len(livecells)/2)+"_"+canonised)
elif (period > 0):
return ("xp"+str(period)+"_"+canonised)
else:
return ("xq"+str(0-period)+"_"+canonised)
# This doesn't really do much, since unids should be empty and
# actual pathological/oversized objects will rarely arise naturally.
def display_unids(self):
self.unids.extend(self.superunids)
g.new("Unidentified objects")
g.setalgo("QuickLife")
g.setrule("B3/S23")
rowlength = 1 + int(math.sqrt(len(self.unids)/3))
for i in xrange(len(self.unids)/3):
xpos = i % rowlength
ypos = int(i / rowlength)
g.putcells(self.unids[3*i], xpos * (self.gridsize + 8) - self.unids[3*i + 1], ypos * (self.gridsize + 8) - self.unids[3*i + 2], 1, 0, 0, 1, "or")
g.fit()
g.update()
# Saves a machine-readable textual file containing the census:
def save_progress(self, numsoups, root):
g.show("Saving progress...")
# Count the total number of objects:
totobjs = 0
censustable = "@CENSUS TABLE\n"
tlist = sorted(self.objectcounts.iteritems(), key=operator.itemgetter(1), reverse=True)
for objname, count in tlist:
totobjs += count
censustable += objname + " " + str(count) + "\n"
g.show("Writing header information...")
# The MD5 hash of the root string:
md5root = hashlib.md5(root).hexdigest()
# Header information:
results = "@MD5 "+md5root+"\n"
results += "@ROOT "+root+"\n"
results += "@NUM_SOUPS "+str(numsoups)+"\n"
results += "@NUM_OBJECTS "+str(totobjs)+"\n"
results += "\n"
# Census table:
results += censustable
g.show("Compactifying score table...")
results += "\n"
# Number of soups to record:
highscores = 1
results += "@TOP "+str(highscores)+"\n"
ilist = sorted(self.soupscores.iteritems(), key=operator.itemgetter(1), reverse=True)
# Empty the high score table:
self.soupscores = {}
for soupnum, score in ilist[:highscores]:
self.soupscores[soupnum] = score
results += str(soupnum) + " " + str(score) + "\n"
g.show("Writing progress file...")
dirname = g.getdir("data")
separator = dirname[-1]
progresspath = dirname + "apgsearch" + separator + "progress" + separator
if not os.path.exists(progresspath):
os.makedirs(progresspath)
filename = progresspath + "search_" + md5root + ".txt"
try:
f = open(filename, 'w')
f.write(results)
f.close()
except:
g.warn("Unable to create progress file:\n" + filename)
# Display results in Help window:
def display_census(self, numsoups, root):
results = "<html>\n<title>Census results</title>\n<body bgcolor=\"#FFFFCE\">\n"
results += "<p>Census results after processing " + str(numsoups) + " soups (with "+str(self.resets)+" resets):\n"
tlist = sorted(self.objectcounts.iteritems(), key=operator.itemgetter(1), reverse=True)
results += "<p><center>\n"
results += "<table cellspacing=1 border=2 cols=2>\n"
results += "<tr><td> Object </td><td align=center> Common name </td><td align=right> Count </td></tr>\n"
for objname, count in tlist:
if (objname[0] == 'x'):
if (objname[1] == 'p'):
results += "<tr bgcolor=\"#CECECF\">"
elif (objname[1] == 'q'):
results += "<tr bgcolor=\"#CEFFCE\">"
else:
results += "<tr>"
else:
results += "<tr bgcolor=\"#FFCECE\">"
results += "<td>"
results += " "
results += objname
results += " "
# As a compromise, we only show ASCII art for oscillators and
# spaceships, not still-lifes. This economises on vertical space
# and helps to make more interesting objects more prominent.
if ((objname[0] == 'x') & (objname[1] != 's')):
# This enables one to click on the ASCII art to open the pattern in Golly:
results += "<pre><a href=\"lexpatt:\">\n"
# http://ferkeltongs.livejournal.com/15837.html
compact = objname.split('_')[1] + "z"
i = 0
strip = []
while (i < len(compact)):
c = ord2(compact[i])
if (c >= 0):
if (c < 32):
# Conventional character:
strip.append(c)
else:
if (c == 35):
# End of line:
if (len(strip) == 0):
strip.append(0)
for j in xrange(5):
for d in strip:
if ((d & (1 << j)) > 0):
results += "o"
else:
results += "."
results += "\n"
strip = []
else:
# Multispace character:
strip.append(0)
strip.append(0)
if (c >= 33):
strip.append(0)
if (c == 34):
strip.append(0)
i += 1
d = ord2(compact[i])
for j in xrange(d):
strip.append(0)
i += 1
# End of pattern representation:
results += "</a></pre>\n"
results += "</td><td align=center> "
if (objname in self.commonnames):
results += self.commonnames[objname][0]
results += " </td><td align=right> " + str(count) + " "
results += "</td></tr>\n"
results += "</table>\n</center>\n"
ilist = sorted(self.soupscores.iteritems(), key=operator.itemgetter(1), reverse=True)
results += "<p><center>\n"
results += "<table cellspacing=1 border=2 cols=2>\n"
results += "<tr><td> Soup number </td><td align=right> Score </td></tr>\n"
for soupnum, score in ilist[:50]:
results += "<tr><td> "
results += root + str(soupnum)
results += "<pre><a href=\"lexpatt:\">\n"
hashdigest = hashlib.sha256(root + str(soupnum)).digest()
for j in xrange(32):
t = ord(hashdigest[j])
for k in xrange(8):
if (t & (1 << (7 - k))):
results += "o"
else:
results += "."
if ((j % 2) == 1):
results += "\n"
results += "</a></pre>\n"
results += " </td><td align=right> " + str(score) + " </td></tr>\n"
results += "</table>\n</center>\n"
results += "</body>\n</html>\n"
dirname = g.getdir("data")
separator = dirname[-1]
apgpath = dirname + "apgsearch" + separator
if not os.path.exists(apgpath):
os.makedirs(apgpath)
htmlname = apgpath + "latest_census.html"
try:
f = open(htmlname, 'w')
f.write(results)
f.close()
g.open(htmlname)
except:
g.warn("Unable to create html file:\n" + htmlname)
# Converts a base-36 case-insensitive alphanumeric character into a
# numerical value.
def ord2(char):
x = ord(char)
if ((x >= 48) & (x < 58)):
return x - 48
if ((x >= 65) & (x < 91)):
return x - 55
if ((x >= 97) & (x < 123)):
return x - 87
return -1
# Obtain the parameters to conduct the search:
number = 1
rootstring = datetime.datetime.now().isoformat()+"_"
# initpos = int(g.getstring("Initial position: ", "0"))
initpos = 0
start_time = time.clock()
soup = Soup()
scount = 0
# We have 100 soups per page, instead of one. This parallel approach
# was suggested by Tomas Rokicki, and results in approximately a
# fourfold increase in soup-searching speed!
sqrtspp = 1
spp = sqrtspp ** 2
# Do stuff repeatedly:
for i in xrange(int((number-1)/spp)+1):
soup.stabilise_soups_parallel(rootstring, scount + initpos, sqrtspp)
scount = spp*(i+1)
g.show(str(scount) + " soups processed ("+str(int(scount/(time.clock() - start_time)))+" per second) : (type 's' to see latest census or 'q' to quit).")
# Automatically save progress every 250000 soups:
if ((scount % 250000) == 0):
soup.save_progress(scount, rootstring)
event = g.getevent()
if event.startswith("key"):
evt, ch, mods = event.split()
if ch == "s":
soup.save_progress(scount, rootstring)
soup.display_census(scount, rootstring)
elif ch == "q":
break
end_time = time.clock()
# Give the number of soups processed together with the amount of time
# elapsed (and indications as to which parts of the script are taking
# the longest).
g.show(str(scount) + " soups processed in " + str(end_time - start_time) +
"(" + str(soup.qlifetime) + ", " + str(soup.ruletime) + ", " + str(soup.gridtime) + ") secs.")
soup.save_progress(scount, rootstring)
soup.display_unids()
soup.display_census(scount, rootstring)
You'll also need to add this script to remove headers from RLEs, since the Golly functions only accept "raw" RLEs:
Once you've done that, copy the pattern you want to census, run the header-removing script, then run the modified apgsearch, and it should pop out the results from that pattern.
