Here is a really primitive target matcher that can be run after survive.
I guess the speed is tolerable if you turn off profiling.
I tried to optimize it a bit, but not much. A really strange thing is that using frozensets as target patterns are faster to iterate than using lists. Not sure why.
I really wonder how Guam's program searched for target patterns... (His main program seems to be something like Catforce, doesn't it?)
Code: Select all
# survive.py v0.95 by Dongook Lee
# Searches user-specified target patterns from ptbsearch dump files.
# The first layer should be empty.
import golly as g
import time
from collections import deque
from itertools import dropwhile
from datetime import datetime
def strftimedelta(td):
"""Just pretty format of the timedelta object"""
days = td.days
hours, less = divmod(td.seconds, 3600)
mins, secs = divmod(less, 60)
units = [(days, "d"), (hours, "h"), (mins, "m"), (secs, "s")]
# Discard larger units than necessary
words = ["{:02d}{}".format(t, u)
for t, u in dropwhile(lambda x: not x[0], units)]
if not words:
words = ["0s"]
return ''.join(words)
def symmetrize(onrle, offrle):
"""Return a list of the given target pattern of all symmetries.
Each output target pattern is a list of coordinates(2-tuples).
The target pattern input is given by its onfilter and offfilter as
an RLE string.
IMPORTANT NOTE!!!
The onrle and offrle should be on the same bounding box!!!
Like the following:
onrle offrle
..... *****
..*.. **.**
...*. ***.*
.***. *...*
..... *****
Also, the target would be pretty useless if a cell is both in onrle
and offrle...
"""
symmetries = [(1, 0, 0, 1), (-1, 0, 0, 1), (1, 0, 0, -1), (-1, 0, 0, -1),
(0, 1, 1, 0), (0, -1, 1, 0), (0, 1, -1, 0), (0, -1, -1, 0)]
oncells, offcells = g.parse(onrle), g.parse(offrle)
allcells = g.join(oncells, offcells)
uniqtargets = set()
for symm in symmetries:
shadow = g.transform(allcells, 0, 0, *symm)
offx, offy = min(shadow[::2]), min(shadow[1::2])
newon = g.transform(oncells, -offx, -offy, *symm)
newoff = g.transform(offcells, -offx, -offy, *symm)
# Just checking...
newall = g.join(newon, newoff)
assert min(newall[::2]) == min(newall[1::2]) == 0
ontarget = frozenset(zip(newon[::2], newon[1::2]))
offtarget = frozenset(zip(newoff[::2], newoff[1::2]))
uniqtargets.add((ontarget, offtarget))
assert not (ontarget & offtarget),\
"The ontarget and the offtarget overlap. You probably made a mistake."
return uniqtargets
def assertsymm(x, n):
assert len(x) == n, ''.join('On:{}\nOff:{}\n\n'.format(*a) for a in x)
# Just assertions
blocks = symmetrize('$b2o$b2o!', '4o$o2bo$o2bo$4o!')
hives = symmetrize('$2bo$bobo$bobo$2bo!', '5o$2ob2o$obobo$obobo$2ob2o$5o!')
# Gliders are used later, actually :)
gliders = (symmetrize('$2bo$3bo$b3o!', '5o$2ob2o$3obo$o3bo$5o!') |
symmetrize('$bo$2b2o$b2o!', '5o$ob3o$2o2bo$o2b2o$5o!'))
assertsymm(blocks, 1)
assertsymm(hives, 2)
assertsymm(gliders, 16)
# Common targets:
'''cf) All of them in one place:
x = 14, y = 34, rule = B3/S23
7b7o$2bo4b3ob3o$2ob2o2bo2bo2bo$bo2bo2b2ob2obo$2b2o3b3o2b2o$8b6o4$8b4o$
b2o5bo2b2o$bobo4bobob2o$bob2o3bobo2bo$2b2o4b2o2b2o$2bo5b2ob3o$9b4o3$8b
5o$bo6bob3o$bobo4bobobo$b3o4bo3bo$3bo4b3obo$8b5o4$8b5o$b2o5bo2b2o$bobo
4bobob2o$3bo4b3ob2o$bobo4bobob2o$b2o5bo2b2o$8b5o!
'''
rs = symmetrize('$3bo$b2ob2o$2bo2bo$3b2o!',
'7o$3ob3o$o2bo2bo$2ob2obo$3o2b2o$b6o!')
bs = symmetrize('$b2o$bobo$bob2o$2b2o$2bo!',
'4o$o2b2o$obob2o$obo2bo$2o2b2o$2ob3o$b4o!')
hs = symmetrize('$bo$bobo$b3o$3bo!',
'5o$ob3o$obobo$o3bo$3obo$5o!')
pis = symmetrize('$b2o$bobo$3bo$bobo$b2o!',
'5o$o2b2o$obob2o$3ob2o$obob2o$o2b2o$5o!')
# Personal additions:
cs = symmetrize('$b3o$bobo$bo2bo$3b2o!', '5o$o3bo$obob2o$ob2obo$3o2bo$2b4o!')
hfs = symmetrize(
'2$4b3o$3bo3bo$2bo5bo$3bo3bo$4b3o!',
'3b5o$2b7o$b3o3b3o$3ob3ob3o$2ob5ob2o$3ob3ob3o$b3o3b3o$2b7o$3b5o!')
def highlight(target, dx=0, dy=0):
"""For debugging.
Highlights a pattern as a collection of coordinates.
target: the catalyst target like the bs, hs, pis etc. above.
dx, dy: the translation to match the target in the whole pattern.
"""
mintx = min(tx for tx, ty in target)+dx
minty = min(ty for tx, ty in target)+dy
maxtx = max(tx for tx, ty in target)+dx
maxty = max(ty for tx, ty in target)+dy
g.select([mintx, minty, maxtx-mintx+1, maxty-minty+1])
""""""""""""""""""""""""""""SEARCH SETTINGS"""""""""""""""""""""""""""""
# The targets
# You can gather targets like this :)
targets = rs | bs | hs | pis | cs
# targets = hfs
# Filter settings
maxjunkpop = 20
# Gens to ignore targets from the beginning.
# e.g. If you're starting with a Herschel,
# you wouldn't want the H to be identified at gen 0, would you?
ignoregens = 20
# Number of gens for the catalysts to survive after target detection
survivegens = 30
# Stablization settings
recentgens = 10
"""""""""""""""""""""""""""""OTHER SETTINGS"""""""""""""""""""""""""""""
# Directories
ptbdir = '/home/scorbie/Apps/ptbsearch'
ptbdumppath = g.opendialog("Choose ptbsearch dump file", "*", ptbdir)
# Alignment of filtered patterns
space = 80
pats_in_row = 10
# Enable profiling?
# cProfile profiling
CPROFILE = False
# Line profiling: needs to have line_profiler installed.
# Can be installed with: sudo pip install line_profilter
LINEPROFILE = False
""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
def matchtarget(oncells):
"""Get the pattern as coordinates of ON cells and see if
any of the targets are in the pattern.
Return (glidercnt, matchpop) where
glidercnt is the number of gliders matched, and
matchpop is the population of the largest target matched.
"""
objects = gliders | targets
# Remove gliders and try to match patterns
glidercnt = 0
matchpops = [] # Pops of matched patterns
for ox, oy in oncells:
for t in objects:
# t[0] is a frozenset of target ON coordinates.
# Get an arbitrary target ON cell as pivot.
for px, py in t[0]:
break # Hacky...
for tx, ty in t[0]:
if (tx+ox-px, ty+oy-py) not in oncells:
break
else:
# All target ON cells in oncells!
for tx, ty in t[1]:
if (tx+ox-px, ty+oy-py) in oncells:
break
else:
# All target OFF cells not in oncells!
if t in targets:
matchpops.append(len(t[0]))
else: # glider
glidercnt += 1
# highlight(t[0], ox-px, oy-py); time.sleep(0.5)
return max(matchpops) if matchpops else 0, glidercnt
def groupblobs(cells):
"""Get the pattern as coordinates. Group cells into "blobs".
Two cells are in the same blob iff they have a common neighbor,
either dead or alive.
Return the list of blobs including dead cells. Each blob is a set.
"""
blobs = []
for x, y in cells:
newblob = {(nx, ny) for nx in (x-1, x, x+1)
for ny in (y-1, y, y+1)}
for blob in blobs[:]:
if blob & newblob:
blobs.remove(blob)
newblob |= blob
blobs.append(newblob)
return blobs
""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
def main():
g.setrule('B3/S23')
g.setalgo('QuickLife')
g.autoupdate(True)
# Position of the current filtered pattern:
patx, paty = 0, 0
cur_pat_col = 0
g.setlayer(0)
try:
g.addlayer()
g.setlayer(0)
with open(ptbdumppath) as ptbdumpfile:
npats = sum(1 for line in ptbdumpfile)
starttime = datetime.now()
with open(ptbdumppath) as ptbdumpfile:
for curr, line in enumerate(ptbdumpfile):
# Initialize
g.new('')
g.setmag(2)
currtime = datetime.now()
elapsed = currtime - starttime
remainingtime = elapsed / (curr+1) * (npats-curr-1)
g.show("Pat: {}/{}, Tot: {}, Est: {}".format(
curr+1, npats, strftimedelta(elapsed),
strftimedelta(remainingtime)))
pattern = line.split()[0]
rows = pattern.split('!')
# Rock cells: Catalyst cells that should never die.
rockcells = set()
catcells = set()
# Parse ptbdump; get the whole pattern and rock cells.
for y, row in enumerate(rows):
for x, char in enumerate(row):
g.setcell(x, y, 0 if char == '.' else 1)
if char == '*':
rockcells.add((x, y))
catcells.add((x, y))
if char == 'z':
catcells.add((x, y))
catpop = len(catcells)
initpat = g.getcells(g.getrect())
recentpops = deque([], recentgens)
envelope = set()
# Run the pattern and check for matches
while int(g.getgen()) < 500:
g.run(1)
curpop = int(g.getpop())
recentpops.append(curpop)
# Just let it run for "ignoregens"
if int(g.getgen()) < ignoregens:
continue
curpat = g.getcells(g.getrect())
oncells = {(x, y) for x, y in
zip(curpat[::2], curpat[1::2])}
envelope |= oncells
# Abort if any catalyst is damaged.
if not rockcells <= oncells:
break
oncells -= catcells
# Abort if the pattern "stabilized."
if (len(recentpops) == recentgens and
all(pop == recentpops[0] for pop in recentpops)):
break
# Check if the pattern contains the target
matchpop, glidercnt = matchtarget(oncells)
if not matchpop:
continue
# Check the junk population is small enough.
junkpop = curpop - catpop - 5 * glidercnt - matchpop
# g.show("cur:{} cat:{} gl:{} match:{} junk:{}".format(
# curpop, catpop, 5*glidercnt, matchpop, junkpop))
if junkpop > maxjunkpop:
continue
# Check if all catalysts reacted:
# 1. Group the catayst cells into catalysts.
catalysts = groupblobs(catcells)
# 2. Check if every blob reacted:
envelope -= catcells # Fallen into this!
hyperenvelope = {(nx, ny) for x, y in envelope
for nx in (x-1, x, x+1)
for ny in (y-1, y, y+1)}
# highlight(hyperenvelope)
# g.show("Envelope (+ 1 cell padding)")
# time.sleep(1)
# for cat in catalysts:
# highlight(cat)
# if not (hyperenvelope & cat):
# g.show("Catalyst does not meet Envelope!!!")
# time.sleep(1)
# else:
# g.show("Catalyst meets Envelope!")
# time.sleep(1)
# highlight(cat & hyperenvelope)
# g.show("Here's the overlapping region.")
# time.sleep(1)
if any(not(hyperenvelope&cat) for cat in catalysts):
continue
# Check if the catalyst survives long enough:
g.run(survivegens)
curpat = g.getcells(g.getrect())
oncells = {(x, y)
for x, y in zip(curpat[::2], curpat[1::2])}
if not rockcells <= oncells:
break
# Passed all filters!!!
# Save the pattern to the next layer.
g.setlayer(1)
g.putcells(initpat, patx, paty)
cur_pat_col += 1
if cur_pat_col < pats_in_row:
patx += space
else:
patx, paty, cur_pat_col = 0, paty+space, 0
g.setlayer(0)
break
except:
# g.dellayer()
if not ptbdumppath:
g.exit("No file specified; aborting.")
else:
raise
if CPROFILE:
import cProfile
import pstats
cProfile.runctx('main()', globals(), locals(), filename='profdump_survive')
with open('profile-survive.txt', 'w') as profileresults:
st = pstats.Stats('profdump_survive', stream=profileresults)
st.sort_stats('tottime')
st.print_stats()
elif LINEPROFILE:
from line_profiler import LineProfiler
profile = LineProfiler(main)
profile.runctx('main()', globals(), locals())
profile.dump_stats('profdump_survive')
with open('profile-survive.txt', 'w') as profileresults:
profile.print_stats(profileresults)
else:
main()
Save this as whatever.out and Select whatever.out inside survive.py. Make sure you tweak the hardcoded directories in the settings. (I grouped the settings and I'm sure they're not hard to find...)
gens to recover, so survive couldn't filter that from an identical reaction:
