1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
|
# Oscar is an OSCillation AnalyzeR for use with Golly.
# Author: Andrew Trevorrow (andrew@trevorrow.com), March 2006.
# Modified to handle B0-and-not-S8 rules, August 2009.
# This script uses Gabriel Nivasch's "keep minima" algorithm.
# For each generation, calculate a hash value for the pattern. Keep all of
# the record-breaking minimal hashes in a list, with the oldest first.
# For example, after 5 generations the saved hash values might be:
#
# 8 12 16 24 25,
#
# If the next hash goes down to 13 then the list can be shortened:
#
# 8 12 13.
#
# When the current hash matches one of the saved hashes, it is highly likely
# the pattern is oscillating. By keeping a corresponding list of generation
# counts we can calculate the period. We also keep lists of population
# counts and bounding boxes; they are used to reduce the chance of spurious
# oscillator detection due to hash collisions. The bounding box info also
# allows us to detect moving oscillators (spaceships/knightships).
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
# --------------------------------------------------------------------
def show_spaceship_speed(period, deltax, deltay):
# we found a moving oscillator
if period == 1:
g.show("Spaceship detected (speed = c)")
elif (deltax == deltay) or (deltax == 0) or (deltay == 0):
speed = ""
if (deltax == 0) or (deltay == 0):
# orthogonal spaceship
if (deltax > 1) or (deltay > 1):
speed += str(deltax + deltay)
else:
# diagonal spaceship (deltax == deltay)
if deltax > 1:
speed += str(deltax)
g.show("Spaceship detected (speed = " + speed + "c/" +str(period) + ")")
else:
# deltax != deltay and both > 0
speed = str(deltay) + "," + str(deltax)
g.show("Knightship detected (speed = " + speed + "c/" + str(period) + ")")
# --------------------------------------------------------------------
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 period == 1:
if pbox == boxlist[pos]:
g.show("The pattern is stable.")
else:
show_spaceship_speed(1, 0, 0)
elif pbox == boxlist[pos]:
g.show("Oscillator detected (period = " + str(period) + ")")
else:
deltax = abs(boxlist[pos].x - pbox.x)
deltay = abs(boxlist[pos].y - pbox.y)
show_spaceship_speed(period, deltax, deltay)
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()
# --------------------------------------------------------------------
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()
|
