I updated the script to allow for a defined number of NE and SE gliders. Also I added some more starting configurations. Good news is that the loaf + block can be made in two NE gliders like so:
but I don't know how to make that starting configuration so I can't tell how expensive it will be.
but unfortunately I think it needs 10 rephasers before the first NE glider (EDIT: but 0 rephasings for the second NE glider so still possibly competitive).
Here is this script (I have set MAX_GLIDERS_NE = 2 and MAX_GLIDERS_SE = 1 so this is not expensive to run):
Code: Select all
import golly as g
from hashlib import sha256
from itertools import chain
#arbitrary numbers
MAX_GENERATIONS = 160
MAX_POPULATION = 30
MAX_HEIGHT = 24
MAX_GLIDERS_NE = 2
MAX_GLIDERS_SE = 1
GLIDER_NE = g.parse('3o$2bo$bo!')
GLIDER_SE = g.parse('bo$2bo$3o!')
#put any ad-hoc patterns that you want to bombard with slow gliders here.
TARGET_PATTERNS = [
'b2o$b2o!',
'b2o$o2bo$b2o$5b2o$5b2o2$13b2o$13b2o!',
'2bo$bobo4b2o$bobo4b2o$2bo!',
'2b2o$bo2bo$bobo$2bo!',
'2b3o7$3o3$7b2o$7b2o!',
'2bo$bobo$bo2bo$2b2o2$10b2o$5b2o3b2o$bo3b2o$obo$obo$bo10bo$11bobo$11b2o!',
'10bo$9bobo$9bo2bo$10b2o$bo$bo$bo13b2o$15b2o4$17bo$16bobo$16b2o!',
'8bo$7bobo$7bo2bo$8b2o2$16b2o$b2o13b2o$b2o3$18bo$17bobo$17b2o!',
'2b2o$2b2o6$2b2o$bo2bo$bobo$2bo3$3o!',
'2b2o$2b2o6$bo4b2o$obo3b2o$b2o!',
'11b2o$11b2o$b2o$o2bo$o2bo$b2o21bo$24bo$24bo3$6b2o$6b2o!',
'11bo$11bo$b2o8bo$o2bo$b2o$5b2o19b2o$5b2o19b2o5$15b2o$15b2o!',
'2b2o$bo2bo$2b2o4$35b2o$35b2o6$24b3o2$18bo$17bobo$18b2o!',
'2o$obo$bo6$8b2o$8b2o!',
'b2o$o2bo$bobo$2bo10$13b2o$13b2o!',
'o$o$o7$15b2o$15b2o!',
'b2o$b2o4$9b3o8$13b2o$13b2o!',
'b2o$obo$2o$9b3o4$8b2o$8b2o4$12b2o$12b2o!',
'6b3o8$7b2o$7b2o3$3b2o$2bo2bo$3b2o2$o$o$o!'
]
TARGET_PATTERNS = [('blob%d' % i, patt) for i, patt in enumerate(TARGET_PATTERNS)]
wanted = ["2b2o3b2o$bobo2bo2bo$bo5b2o$2o!",
"2b2o$2b2o3$bo$obo$o2bo$b2o!"]
wanted_color = ["2b3o2$o5bo$o5bo$o5bo2$2b3o8$2b3o!",
"$3b3o13$2b3o2$o5bo$o5bo$o5bo2$2b3o!"]
wanted = [g.parse(x) for x in wanted]
wanted_color = [g.parse(x) for x in wanted_color]
# test if sub_cells appears in cells_set (optionally with same color)
def find_wanted(cells_set, sub_cells, color=False):
x0, y0 = sub_cells[0], sub_cells[1]
for x, y in cells_set:
dx, dy = x - x0, y - y0
if color and ((dx ^ dy) & 1):
continue
if all((sub_cells[j] + dx, sub_cells[j+1] + dy) in cells_set for j in range(0, len(sub_cells), 2)):
return True
return False
TARGETS = []
for name, pattern in TARGET_PATTERNS:
cells = g.parse(pattern)
p = len(cells) / 2
TARGETS.append((name, cells, 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 is_p2(cells):
return patterns_identical(cells, g.evolve(cells, 2))
def get_shooting_range(cells):
min_d1 = max_d1 = cells[0] + cells[1]
min_d2 = max_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])
max_d2 = max(max_d2, cells[i] - cells[i+1])
min_lane_ne = min_d1 - 6
max_lane_ne = max_d1 + 3
shift_ne = 3 - min_d2 // 2
min_lane_se = min_d2 - 4
max_lane_se = max_d2 + 5
shift_se = 4 - min_d1 // 2
shift_se += (shift_se - shift_ne) % 2
return min_lane_ne, max_lane_ne, shift_ne, min_lane_se, max_lane_se, shift_se
def get_pattern_to_try(cells, lane, offset=50):
y = lane // 2 + offset
return cells + g.transform(GLIDER_NE, lane - y, y)
def add_glider_se(cells, lane, offset=50):
y = lane // 2 + offset
return cells + g.transform(GLIDER_SE, lane - y, -y)
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:
try:
lane_ne, lane_se, delay = lane
if lane_ne is not None:
cells = get_pattern_to_try(cells, lane_ne, i)
cells = add_glider_se(cells, lane_se, i + delay)
except:
cells = get_pattern_to_try(cells, lane, 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.select(g.getrect())
g.copy()
g.select([])
g.update()
offset += 800
g.update()
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] & 63) + (cells[i+1] & 63)]
return hash
def try_it(start_cells, lanes, debug):
global seen
new_cells = g.evolve(start_cells, MAX_GENERATIONS)
if not new_cells or len(new_cells) > 2 * MAX_POPULATION:
return None
if max(new_cells[1::2]) - min(new_cells[1::2]) >= MAX_HEIGHT:
return None
if not is_p2(new_cells):
return None
new_hashable = to_hashable(new_cells)
if new_hashable in seen:
return None
seen.add(new_hashable)
cells_set = set(zip(new_cells[::2], new_cells[1::2]))
if any(find_wanted(cells_set, w, False) for w in wanted):
display_solution(start, lanes, debug, new_cells)
if any(find_wanted(cells_set, w, True) for w in wanted_color):
display_solution(start, lanes, debug, new_cells)
return new_cells
g.new('')
for i, (_,p) in enumerate(TARGET_PATTERNS):
g.putcells(g.parse(p), 100*i, -800)
new_queue = []
for name, cells, _ in TARGETS:
new_queue.append( (name, [], cells, [], MAX_GLIDERS_NE, MAX_GLIDERS_SE) )
seen = set()
loop = 0
while new_queue:
queue = new_queue
new_queue = []
loop += 1
count = 0
for start, lanes, last, debug, num_ne, num_se in queue:
g.show(str((loop,count,len(queue))))
count += 1
tup = get_shooting_range(last)
min_lane_ne, max_lane_ne, shift_ne = tup[:3]
min_lane_se, max_lane_se, shift_se = tup[-3:]
if num_se > 0:
se_end = min(min_lane_se + 27, max_lane_se)
for lane_se in range(se_end-27, se_end+1):
if lane_se % 2:
continue
start_cells = add_glider_se(last, lane_se, shift_se)
new_lanes = lanes + [(None, lane_se, 0)]
new_debug = debug + [start_cells]
new_cells = try_it(start_cells, new_lanes, new_debug)
if new_cells is not None and (num_se > 1 or num_ne > 0):
new_queue.append( (start, new_lanes, new_cells, new_debug, num_ne, num_se-1) )
if num_ne == 0:
continue
ne_end = min(min_lane_ne + 25, max_lane_ne)
for lane in range(ne_end-25, ne_end+1):
# monochromatic
if lane % 2:
continue
start_cells = get_pattern_to_try(last, lane, shift_ne)
new_lanes = lanes + [lane]
new_debug = debug + [start_cells]
new_cells = try_it(start_cells, new_lanes, new_debug)
if new_cells is not None and (num_ne > 1 or num_se > 0):
new_queue.append( (start, new_lanes, new_cells, new_debug, num_ne-1, num_se) )
if num_se > 0:
se_end = min(min_lane_se + 27, max_lane_se)
for lane_se in range(se_end-27, se_end+1):
if lane_se % 2:
continue
for delay in range(-6, 7, 2):
start_cells = get_pattern_to_try(last, lane, shift_ne + max(delay, 0))
start_cells = add_glider_se(start_cells, lane_se, shift_se - min(delay, 0))
new_lanes = lanes + [(lane, lane_se, shift_se - shift_ne - delay)]
new_debug = debug + [start_cells]
new_cells = try_it(start_cells, new_lanes, new_debug)
if new_cells is not None and (num_se > 1 or num_ne > 1):
new_queue.append( (start, new_lanes, new_cells, new_debug, num_ne-1, num_se-1) )