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