A 5-glider run of this code, looking for splitters and *WSS instead of simple turners, takes a few days on my system. Looks like I'll have a complete report by tomorrow -- and I'm not seeing any trouble with memory usage at all, this time around. I'm over halfway through the search, and have found over twenty different splitters so far, not counting mirror-image duplicates.
The more the better, of course. What I'd really like would be several edge-shooting splitters that can be chained easily to produce arbitrary slow salvos. Need different ones for different combinations of slow-salvo glider output color and parity. It's more the "continuation glider", the one that goes on to trigger the next splitter, that needs to appear at the edge of the reaction.
Not sure whether to attempt 6G with this script; it might be worth setting it up to write intermediate results to a file, so a search can be picked up where it left off. I haven't looked for other possible optimizations yet.
Here's the version of the script that I'm currently running to find splitters and *WSSes. The test to find these things is probably a lot slower than the one-time-turner-finding code that it replaces, but it seems to work okay.
Code: Select all
import golly as g
from hashlib import sha256
from itertools import chain
from time import sleep
#arbitrary numbers
MAX_GENERATIONS = 256
MAX_POPULATION = 40
MAX_GLIDERS = 5
#NE glider
GLIDER = g.parse('3o$2bo$bo!')
#put any ad-hoc patterns that you want to bombard with slow gliders here.
TARGET_PATTERNS = []#('known_splitter', 'bo$obo$b2o$5bo$4bobo$5bobo$6b2o!')]
#put simple targets here, along with rotational symmetry
SIMPLE_TARGETS = [
('block', '2o$2o!', 4),
# ('blinker', '3o$!', 4),
# ('tub', 'bo$obo$bo!', 4),
# ('boat', 'b2o$obo$bo!', 1),
# ('hive', 'b2o$o2bo$b2o!', 2),
# ('ship', 'b2o$obo$2o!', 2),
# ('loaf', 'b2o$o2bo$bobo$2bo!', 1),
# ('lboat', '2b2o$bobo$obo$bo!', 1),
# ('pond', 'b2o$o2bo$o2bo$b2o!', 4),
# ('tlight', '4bo$4bo$4bo2$3o3b3o2$4bo$4bo$4bo!', 4),
# ('hfarm', '6bo$5bobo$5bobo$6bo2$b2o7b2o$o2bo5bo2bo$b2o7b2o2$6bo$5bobo$5bobo$6bo!', 4),
]
def get_pattern_variants(cells, symmetry):
variants = []
for t in range(0, 4, symmetry):
variants.append(cells)
cells = g.transform(cells, 0, 0, 0, -1, 1, 0)
return variants
TARGETS = []
for name, pattern in TARGET_PATTERNS:
cells = g.parse(pattern)
p = len(cells) / 2
TARGETS.append((name, cells, p))
for name, pattern, sym in SIMPLE_TARGETS:
cells = g.parse(pattern)
variants = get_pattern_variants(cells, sym)
for i, v in enumerate(variants):
p = len(v) / 2
TARGETS.append((name+str(i), v, p))
def patterns_identical(cells1, cells2):
if len(cells1) != len(cells2):
return False
if sum(cells1) != sum(cells2):
return False
return sorted(zip(cells1[::2], cells1[1::2])) == sorted(zip(cells2[::2], cells2[1::2]))
def get_pattern_period(cells):
temp_cells = cells
for p in range(0, 2):
temp_cells = g.evolve(temp_cells, 1)
if patterns_identical(cells, temp_cells):
return p+1
return None
def get_shooting_range(cells):
min_d1 = max_d1 = cells[0] + cells[1]
min_d2 = cells[0] - cells[1]
for i in range(2, len(cells), 2):
min_d1 = min(min_d1, cells[i] + cells[i+1])
max_d1 = max(max_d1, cells[i] + cells[i+1])
min_d2 = min(min_d2, cells[i] - cells[i+1])
min_lane = min_d1 - 6
max_lane = max_d1 + 3
shift = 6 - min_d2 // 2
return min_lane, max_lane, shift
def get_pattern_to_try(cells, lane, parity, offset=50):
glider = g.transform(GLIDER, lane - lane // 2 - offset, lane // 2 + offset)
if parity % 2:
glider = g.evolve(glider, 1)
return list(chain(cells, glider))
offset = 0
def display_solution(start, lanes, debug, last_cells):
global offset
cells = [c for n, c, _ in TARGETS if n == start][0]
i = 100
for lane in lanes:
lane_num, parity = lane
cells = get_pattern_to_try(cells, lane_num, parity, i)
i += 100
g.putcells(cells, 0, offset)
for i, p in enumerate(debug):
g.putcells(p, 100 + 100 * i, offset)
g.putcells(last_cells, 100 + 100 * len(debug), offset)
g.fit()
g.update()
g.show(' '.join(chain([str(start), str(len(lanes))], [str(lane) for lane in lanes])))
offset += 400
randoms = []
for i in range(4096):
randoms.append(int(sha256(str(i)).hexdigest()[:16], 16))
def to_hashable(cells):
if not cells:
return 0
minx = min(cells[::2])
miny = min(cells[1::2])
hash = 0
for i in range(0, len(cells), 2):
hash ^= randoms[64 * ((cells[i] - minx) & 63) + ((cells[i+1] - miny) & 63)]
return hash
def deltas(cells):
return len(cells), sum(cells[::2]), sum(cells[1::2])
def intersect(cells1, cells2):
# find out if pattern is made up of only moving objects --
# presumably *WSS or gliders, since otherwise we'd have to use T=+65 or so,
# just for example, to catch any stray loafers that might appear.
# No doubt there's something a lot more efficient, but this might be fast enough.
coords1=[[cells1[i],cells1[i+1]] for i in range(0,len(cells1),2)]
coords2=[[cells2[i],cells2[i+1]] for i in range(0,len(cells2),2)]
for item in coords1:
if item in coords2:
# g.note(str([item,coords2]))
return 1 # return as soon as we see any overlap
return 0
def bombard_final(start, lanes, cells, period, debug, flipx, flipy):
cells = g.transform(cells, 0, 0, flipx, 0, 0, flipy)
min_lane, max_lane, shift = get_shooting_range(cells)
for lane_num in range(min_lane, max_lane + 1):
for parity in range(period):
sleep(.01)
lane = (lane_num, parity)
start_cells = get_pattern_to_try(cells, lane[0], lane[1], shift)
new_cells = g.evolve(start_cells, MAX_GENERATIONS)
# Is pattern two or more gliders, or a *WSS?
if len(new_cells) in [20,30,40,18,22,24,26,30,36]:
new_cells_later = g.evolve(new_cells, 28)
if len(new_cells)!=len(new_cells_later):
continue
if intersect(new_cells, new_cells_later)==0:
#Success??
#flip back for display purposes
start_cells = g.transform(start_cells, 0, 0, flipx, 0, 0, flipy)
new_cells = g.transform(new_cells, 0, 0, flipx, 0, 0, flipy)
#add
debug.append(start_cells)
# lanes.append(lane)
#display
display_solution(start, lanes, debug, new_cells)
#remove
# lanes.pop()
debug.pop()
g.new('')
new_queue = []
for name, cells, _ in TARGETS:
period = get_pattern_period(cells)
new_queue.append( (name, [], cells, period, []) )
seen = set()
for n in range(MAX_GLIDERS):
queue = new_queue
new_queue = []
count = 0
for start, lanes, last, period, debug in queue:
sleep(.01)
count += 1
min_lane, max_lane, shift = get_shooting_range(last)
for lane_num in range(min_lane, max_lane + 1):
g.show(str((n+1,count,len(queue),lane_num)))
for parity in range(period):
lane = (lane_num, parity)
start_cells = get_pattern_to_try(last, lane[0], lane[1], shift)
new_cells = g.evolve(start_cells, MAX_GENERATIONS)
if not new_cells or len(new_cells) > 2 * MAX_POPULATION:
continue
new_period = get_pattern_period(new_cells)
if new_period is None:
continue
new_hashable = to_hashable(new_cells)
if new_hashable in seen:
continue
seen.add(new_hashable)
if new_period > 1:
seen.add(to_hashable(g.evolve(new_cells, 1)))
new_lanes = lanes + [lane]
new_debug = debug + [start_cells]
bombard_final(start, new_lanes, new_cells, new_period, new_debug, 1, 1)
bombard_final(start, new_lanes, new_cells, new_period, new_debug, 1, -1)
bombard_final(start, new_lanes, new_cells, new_period, new_debug, -1, -1)
if n + 1 < MAX_GLIDERS:
new_queue.append( (start, new_lanes, new_cells, new_period, new_debug) )
Here's an entertaining splitter that can be triggered from two different directions, due to symmetry:
Here's the more-than-complete 5G splitters list (mirror-image duplicates not removed):