confocaloid wrote: ↑June 29th, 2022, 5:46 am
Is there a tool that can be used to determine and display the minimum repeat time/best compression of a spaceship - something that outputs 14 for the glider and the LWSS, 16 for the MWSS and 196 for Sir Robin? E.g. neither LifeViewer nor Catagolue provide this information (although I understand this might be in general prohibitively costly to compute).
Another script I made years ago (June 26, 2020) and never bothered to publish until now:
Code: Select all
import golly as g
from glife import rect, pattern
from time import time
# --------------------------------------------------------------------
# initialize lists
hashlist = [] # for pattern hash values
genlist = [] # corresponding generation counts
poplist = [] # corresponding population counts
boxlist = [] # corresponding bounding boxes
# --------------------------------------------------------------------
pat = g.getcells(g.getrect())
p = 0
# --------------------------------------------------------------------
def oscillating():
# return True if the pattern is empty, stable or oscillating
# first get current pattern's bounding box
prect = g.getrect()
pbox = rect(prect)
if pbox.empty:
g.show("The pattern is empty.")
return True
# get current pattern and create hash of "normalized" version -- ie. shift
# its top left corner to 0,0 -- so we can detect spaceships and knightships
## currpatt = pattern( g.getcells(prect) )
## h = hash( tuple( currpatt(-pbox.left, -pbox.top) ) )
# use Golly's hash command (3 times faster than above code)
h = g.hash(prect)
# check if outer-totalistic rule has B0 but not S8
rule = g.getrule().split(":")[0]
hasB0notS8 = rule.startswith("B0") and (rule.find("/") > 1) and not rule.endswith("8")
# 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]
del poplist[pos : listlen]
del boxlist[pos : listlen]
break
else:
# h == 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 (int(g.getpop()) == poplist[pos]) and \
(pbox.wd == boxlist[pos].wd) and \
(pbox.ht == boxlist[pos].ht):
period = int(g.getgen()) - genlist[pos]
if hasB0notS8 and (period % 2 > 0) and (pbox == boxlist[pos]):
# ignore this hash value because B0-and-not-S8 rules are
# emulated by using different rules for odd and even gens,
# so it's possible to have identical patterns at gen G and
# gen G+p if p is odd
return False
if pbox == boxlist[pos]:
# pattern hasn't moved
if period == 1:
g.show("The pattern is stable.")
else:
g.show("Oscillator detected (period = " + str(period) + ")")
else:
global p
p = period
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
hashlist.insert(pos, h)
genlist.insert(pos, int(g.getgen()))
poplist.insert(pos, int(g.getpop()))
boxlist.insert(pos, pbox)
return False
# --------------------------------------------------------------------
def fit_if_not_visible():
# fit pattern in viewport if not empty and not completely visible
r = rect(g.getrect())
if (not r.empty) and (not r.visible()): g.fit()
# --------------------------------------------------------------------
def check_repeat_time(n):
g.show("Checking for repeat time " + str(n))
g.new("test")
g.putcells(pat)
g.run(n)
g.putcells(pat, 0, 0, 1, 0, 0, 1, "xor")
test_hash = g.hash(g.getrect())
g.run(p)
if len(g.getrect()) == 0: return False
current_hash = g.hash(g.getrect())
return current_hash == test_hash
g.show("Checking for oscillation... (hit escape to abort)")
oldsecs = time()
while not oscillating():
g.run(1)
newsecs = time()
if newsecs - oldsecs >= 1.0: # show pattern every second
oldsecs = newsecs
fit_if_not_visible()
g.update()
fit_if_not_visible()
i = 1
while not check_repeat_time(i):
i += 1
g.show(str(i))
I also made a "lazy" version that essentially does a binary search instead, although as a result it's not guaranteed to output the correct answer:
Code: Select all
import golly as g
from glife import rect, pattern
from time import time
# --------------------------------------------------------------------
# initialize lists
hashlist = [] # for pattern hash values
genlist = [] # corresponding generation counts
poplist = [] # corresponding population counts
boxlist = [] # corresponding bounding boxes
# --------------------------------------------------------------------
pat = g.getcells(g.getrect())
p = 0
# --------------------------------------------------------------------
def oscillating():
# return True if the pattern is empty, stable or oscillating
# first get current pattern's bounding box
prect = g.getrect()
pbox = rect(prect)
if pbox.empty:
g.show("The pattern is empty.")
return True
# get current pattern and create hash of "normalized" version -- ie. shift
# its top left corner to 0,0 -- so we can detect spaceships and knightships
## currpatt = pattern( g.getcells(prect) )
## h = hash( tuple( currpatt(-pbox.left, -pbox.top) ) )
# use Golly's hash command (3 times faster than above code)
h = g.hash(prect)
# check if outer-totalistic rule has B0 but not S8
rule = g.getrule().split(":")[0]
hasB0notS8 = rule.startswith("B0") and (rule.find("/") > 1) and not rule.endswith("8")
# 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]
del poplist[pos : listlen]
del boxlist[pos : listlen]
break
else:
# h == 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 (int(g.getpop()) == poplist[pos]) and \
(pbox.wd == boxlist[pos].wd) and \
(pbox.ht == boxlist[pos].ht):
period = int(g.getgen()) - genlist[pos]
if hasB0notS8 and (period % 2 > 0) and (pbox == boxlist[pos]):
# ignore this hash value because B0-and-not-S8 rules are
# emulated by using different rules for odd and even gens,
# so it's possible to have identical patterns at gen G and
# gen G+p if p is odd
return False
if pbox == boxlist[pos]:
# pattern hasn't moved
if period == 1:
g.show("The pattern is stable.")
else:
g.show("Oscillator detected (period = " + str(period) + ")")
else:
global p
p = period
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
hashlist.insert(pos, h)
genlist.insert(pos, int(g.getgen()))
poplist.insert(pos, int(g.getpop()))
boxlist.insert(pos, pbox)
return False
# --------------------------------------------------------------------
def fit_if_not_visible():
# fit pattern in viewport if not empty and not completely visible
r = rect(g.getrect())
if (not r.empty) and (not r.visible()): g.fit()
# --------------------------------------------------------------------
def check_repeat_time(n):
g.show("Checking for repeat time " + str(n))
g.new("test")
g.putcells(pat)
g.run(n)
g.putcells(pat, 0, 0, 1, 0, 0, 1, "xor")
test_hash = g.hash(g.getrect())
g.run(p)
if len(g.getrect()) == 0: return False
current_hash = g.hash(g.getrect())
return current_hash == test_hash
g.show("Checking for oscillation... (hit escape to abort)")
oldsecs = time()
while not oscillating():
g.run(1)
newsecs = time()
if newsecs - oldsecs >= 1.0: # show pattern every second
oldsecs = newsecs
fit_if_not_visible()
g.update()
fit_if_not_visible()
i = 1
while not check_repeat_time(i):
i *= 2
factor = i/4
i -= factor
while factor != 1:
factor /= 2
if check_repeat_time(int(i)):
i -= factor
else:
i += factor
g.show(str(i))
In fact, it appears to be buggy. Inputting Sir Robin correctly outputs 196 with the first script, but 195 with the second one, causing the two spaceships to collide.