1-- Oscar is an OSCillation AnalyzeR for use with Golly.
2-- Author: Andrew Trevorrow (andrew@trevorrow.com), Mar 2016.
3--
4-- This script uses Gabriel Nivasch's "keep minima" algorithm.
5-- For each generation, calculate a hash value for the pattern.  Keep all of
6-- the record-breaking minimal hashes in a list, with the oldest first.
7-- For example, after 5 generations the saved hash values might be:
8--
9--   8 12 16 24 25,
10--
11-- If the next hash goes down to 13 then the list can be shortened:
12--
13--   8 12 13.
14--
15-- If the current hash matches one of the saved hashes, it is highly likely
16-- the pattern is oscillating.  By keeping a corresponding list of generation
17-- counts we can calculate the period.  We also keep lists of population
18-- counts and bounding boxes to reduce the chance of spurious oscillator
19-- detection due to hash collisions.  The bounding box info also allows us
20-- to detect moving oscillators (spaceships/knightships).
21
22local g = golly()
23
24-- initialize lists
25local hashlist = {}     -- for pattern hash values
26local genlist = {}      -- corresponding generation counts
27local poplist = {}      -- corresponding population counts
28local boxlist = {}      -- corresponding bounding boxes
29
30-- check if outer-totalistic rule has B0 but not S8
31local r = g.getrule()
32r = string.match(r, "^(.+):") or r
33local hasB0notS8 = r:find("B0") == 1 and r:find("/") > 1 and r:sub(-1,-1) ~= "8"
34
35--------------------------------------------------------------------------------
36
37local function show_spaceship_speed(period, deltax, deltay)
38    -- we found a moving oscillator
39    if deltax == deltay or deltax == 0 or deltay == 0 then
40        local speed = ""
41        if deltax == 0 or deltay == 0 then
42            -- orthogonal spaceship
43            if deltax > 1 or deltay > 1 then
44                speed = speed..(deltax + deltay)
45            end
46        else
47            -- diagonal spaceship (deltax == deltay)
48            if deltax > 1 then
49                speed = speed..deltax
50            end
51        end
52        if period == 1 then
53            g.show("Spaceship detected (speed = "..speed.."c)")
54        else
55            g.show("Spaceship detected (speed = "..speed.."c/"..period..")")
56        end
57    else
58        -- deltax != deltay and both > 0
59        local speed = deltay..","..deltax
60        if period == 1 then
61            g.show("Knightship detected (speed = "..speed.."c)")
62        else
63            g.show("Knightship detected (speed = "..speed.."c/"..period..")")
64        end
65    end
66end
67
68--------------------------------------------------------------------------------
69
70local function oscillating()
71    -- return true if the pattern is empty, stable or oscillating
72
73    -- first get current pattern's bounding box
74    local pbox = g.getrect()
75    if #pbox == 0 then
76        g.show("The pattern is empty.")
77        return true
78    end
79
80    local h = g.hash(pbox)
81
82    -- determine where to insert h into hashlist
83    local pos = 1
84    local listlen = #hashlist
85    while pos <= listlen do
86        if h > hashlist[pos] then
87            pos = pos + 1
88        elseif h < hashlist[pos] then
89            -- shorten lists and append info below
90            for i = 1, listlen - pos + 1 do
91                table.remove(hashlist)
92                table.remove(genlist)
93                table.remove(poplist)
94                table.remove(boxlist)
95            end
96            break
97        else
98            -- h == hashlist[pos] so pattern is probably oscillating, but just in
99            -- case this is a hash collision we also compare pop count and box size
100            local rect = boxlist[pos]
101            if tonumber(g.getpop()) == poplist[pos] and pbox[3] == rect[3] and pbox[4] == rect[4] then
102                local period = tonumber(g.getgen()) - genlist[pos]
103
104                if hasB0notS8 and (period % 2) > 0 and
105                   pbox[1] == rect[1] and pbox[2] == rect[2] and
106                   pbox[3] == rect[3] and pbox[4] == rect[4] then
107                    -- ignore this hash value because B0-and-not-S8 rules are
108                    -- emulated by using different rules for odd and even gens,
109                    -- so it's possible to have identical patterns at gen G and
110                    -- gen G+p if p is odd
111                    return false
112                end
113
114                if pbox[1] == rect[1] and pbox[2] == rect[2] and
115                   pbox[3] == rect[3] and pbox[4] == rect[4] then
116                    -- pattern hasn't moved
117                    if period == 1 then
118                        g.show("The pattern is stable.")
119                    else
120                        g.show("Oscillator detected (period = "..period..")")
121                    end
122                else
123                    local deltax = math.abs(rect[1] - pbox[1])
124                    local deltay = math.abs(rect[2] - pbox[2])
125                    show_spaceship_speed(period, deltax, deltay)
126                end
127                return true
128            else
129                -- look at next matching hash value or insert if no more
130                pos = pos + 1
131            end
132        end
133    end
134
135    -- store hash/gen/pop/box info at same position in various lists
136    table.insert(hashlist, pos, h)
137    table.insert(genlist, pos, tonumber(g.getgen()))
138    table.insert(poplist, pos, tonumber(g.getpop()))
139    table.insert(boxlist, pos, pbox)
140
141    return false
142end
143
144--------------------------------------------------------------------------------
145
146local function fit_if_not_visible()
147    -- fit pattern in viewport if not empty and not completely visible
148    local r = g.getrect()
149    if #r > 0 and not g.visrect(r) then g.fit() end
150end
151
152--------------------------------------------------------------------------------
153
154g.show("Checking for oscillation... (hit escape to abort)")
155
156local oldsecs = os.clock()
157while not oscillating() do
158    g.run(1)
159    local newsecs = os.clock()
160    if newsecs - oldsecs >= 1.0 then   -- show pattern every second
161        oldsecs = newsecs
162        fit_if_not_visible()
163        g.update()
164    end
165end
166fit_if_not_visible()
167