Code: Select all
import lifelib
from functools import reduce
sess = lifelib.load_rules('b3s23')
lt = sess.lifetree(n_layers=1)
raw_splitters = ['9bo$8bobo$8bo2bo$9b2o3$2o$obo$bo3$6b3o$6bo$7bo!',
'7b2o$6bo2bo$7b2o3$2bo$bobo$o2bo$b2o4$9b3o$9bo$10bo!',
'3bo$2bobo$2b2o3$2o$obo$bobo$2bo2$9b3o$9bo$10bo!',
'2bo$2b3o$5bo$4b2o5$b2o$o2bo$o2bo$b2o3$11b3o$11bo$12bo!',
'2o$obo$bo2$9b2o$8bo2bo$8bobo$9bo7$11b3o$11bo$12bo!',
'5b2o$5bobo$6bobo$7bo3$2o$obo$bo6$3b3o$3bo$4bo!',
'2bo6bo$bobo4bobo$obo5bobo$2o7bo6$9b3o$9bo$10bo!',
'2b2o$2bobo$3bobo$4bo3$b2o$o2bo$b2o$7b3o$7bo$8bo!',
'2b2o$bobo$obo$bo3$7b2o$6bobo$7bo5$9b3o$9bo$10bo!',
'8b2o$b2o4bo2bo$o2bo3bobo$o2bo4bo$b2o3$11b3o$11bo$12bo!',
'8b2o$7bo2bo$7bo2bo$8b2o$bo$obo$obo$bo2$7b3o$7bo$8bo!']
raw_180 = ['10b2o$10bobo$11bobo$12b2o5$3o$2bo$bo!',
'5b2o$5bobo$6bobo$7bo8$3o$2bo$bo!',
'11bo$10bobo$11bobo$12b2o4$3o$2bo$bo!',
'6b2o$6bobo$7bobo$8b2o8$3o$2bo$bo!']
raw_90 = ['53bo$52bobo$53b2o52$3o$2bo$bo!',
'47b2o$48bo$48bobo$49b2o52$b2o$obo$2bo!',
'52b2o$51bobo$50bobo$51bo53$2o$b2o$o!',
'52b2o$52b2o3$57b2o$57b2o49$2o$b2o$o!',
'53bo$52bobo$53bobo$54b2o$59b2o$58bo2bo$58bo2bo$59b2o54$b2o$obo$2bo!',
'39bo$38bobo$39b2o$43b2o$42bobo$42b2o46$3o$2bo$bo!',
'46bo$44bobo$45bobo$45bo3$48b2o$48b2o49$3o$2bo$bo!',
'26bo$25bobo$26b2o4$33b2o$32bobo$31bobo$32bo5$28b2o$27bo2bo$28bo2bo$29b2o9$bo$b2o$obo!',
'22bo$20bobo$21bobo$21bo4$28bo$28b3o$31bo$30b2o$20bo$19bobo11b2o$18bobo12b2o$18b2o2$28b2o$16b2o10bobo$16bobo10bo$17bobo$18bo23$2o$b2o$o!']
def centre_by(x, y):
bbox = y.bounding_box
return x(-(bbox[0] + (bbox[2] // 2)), -(bbox[1] + (bbox[3] // 2)))
def normalise_inserter(p):
p = lt.pattern(p)
g = (p - p[8])
p = (p - g) + g(-128, 128)
p = centre_by(p, p[1024])(256, 256)
return p
inserters = [normalise_inserter(p) for p in raw_90]
def try_build_salvo(s, ins):
gc = lt.pattern('bo$2bo$3o!').centre()
v = s.components()
v.sort(key=(lambda x : x.bounding_box[0] - x.bounding_box[1]))
for g in v:
for i in range(4):
h = g[-i]
if h.centre() == gc:
dx, dy = h.bounding_box[:2]
dx += 1
dy += 1
assert(gc(dx, dy)[i] == g)
ii = ins(dx, dy)[i]
if (s - g + ii)[1024] == s[1024]:
return (s - g, ii)
break
else:
raise RuntimeError('Unexpected object in salvo')
def build_salvo_1G(s, direction='left'):
orients = ['identity', 'transpose'][::{'left': 1, 'right': -1}[direction]]
for (i, ins) in enumerate(inserters):
for o in orients:
res = try_build_salvo(s(o), ins)
if res:
return tuple([r(o) for r in res]) + (i, o)
raise RuntimeError('Failed to construct glider')
def analyse_turner(x):
tg = x - x[8]
sl = x & x[8]
assert(tg.population == 5)
og = lt.pattern('2o$obo$o!')('flip_x')
for t in range(4):
m = tg.match(og[t])
if m.nonempty():
x, y = m.bounding_box[:2]
return [x + y, t - 4*y, sl]
def build_salvo(s, direction='left'):
comps = []
dirs = []
while s.nonempty():
s, c, i, o = build_salvo_1G(s, direction)
direction = {'identity': 'right', 'transpose': 'left'}[o]
comps.append(c)
dirs.append(o)
fds = [(sum((r - r[8]).bounding_box) + 48 * i) >> 1 for (i, r) in enumerate(comps)]
m = max(fds)
fds = [m - f for f in fds]
comps = [(((r & r[8]) + (r - r[8])[-4*f])(d)(f, f), d) for (f, r, d) in zip(fds, comps, dirs)]
comps = [[d] + analyse_turner(c) for (c, d) in comps]
return comps
def make_adj_splitter(a, b):
a = lt.pattern(a)
b = lt.pattern(b)
a160 = a[160]
c = lt.pattern('', 'b3s23')
gnw = lt.pattern('3o$o$bo!', 'b3s23')
for _ in range(4):
c += a160.match(b - b[8]).convolve(b & b[8])
b = b[1]
while True:
gg = (a + c(-5, 5))[256] ^ (a + c)[256]
if (gg.population != 10):
break
if (gg[4] != gg(-1, 1)):
break
c = c(-1, 1)
a = a + c(8, -8)
a = gnw.replace(a.match(gnw).convolve(gnw), a)
return a
def analyse_splitter(x):
g = x - x[8]
assert(g.bounding_box == [0, 0, 3, 3])
assert(g.population == 5)
res = []
for s in [-1, 1]:
for t in range(256, 260):
a = x[t].match(g)
if (a.nonempty()):
a = a.bounding_box[:2] + [t]
a[2] += 4 * a[1]
a[0] += s * a[1]
res.append(a[::2])
break
g = g('flip_x')
solid = x & x[8]
res += [solid[:,:8], solid[:,8:]]
print([(p if isinstance(p, list) else p.apgcode) for p in res])
return res
def make_best_splitters():
v = [make_adj_splitter(a, b) for a in raw_splitters for b in raw_180]
v.sort(key=(lambda x : x.population))
d = {}
g = lt.pattern('bo$o$3o!', 'b3s23')
for w in v[::-1]:
w256 = w[256]
for i in range(4):
m = w256.match(g[i])
if m.nonempty():
k = i + ((m.bounding_box[0] & 1) << 2) + ((sum(m.bounding_box) & 1) << 3)
d[k] = w
d = [analyse_splitter(d[k]('transpose')) for k in range(16)]
return d
adj_splitters = make_best_splitters()
# print(reduce((lambda x, y : x + y), [l(i*100, 0) for (i, l) in enumerate(adj_splitters)]).rle_string())
def split_synth(x):
g = lt.pattern("bo$2bo$3o", "b3s23")
gsets = []
for i in range(4):
gsets.append(lt.pattern('', 'b3s23'))
for j in range(4):
gsets[-1] += x.match(g, halo="3o$3o$3o").convolve(g)
g = g[1]
g = g('rot90')
y = x - (gsets[0] + gsets[1] + gsets[2] + gsets[3])
return y, gsets
def load_seed():
runtime = 4096
seed = '''x = 389, y = 389, rule = B3/S23
185bo$184bobo$185bo3$179bo$179b3o$182bo$181b2o91$278b2o$278b2o3$278b2o
$278b2o3$108b2o$108b2o167b2ob2o$99b2o2b2o172b2ob2o$99b2o2b2o3b2o$108b
2o65$202bo$201bobo$201b2o$382b2o$382bo$380bobo$380b2o2$195b2o190bo$
194bo2bo188bobo$195b2o190bo5$185bo31b2o72bo$184bobo30b2o70bo3bo$184bob
o37b2o3b2o57bo$185bo17bo20b2o2bo2bo56bo4bo$202bobo24b2o57b5o$202bobo$
194b2o7bo$194b2o21b2o$217b2o3$bo190b2o$obo188bo2bo$bo190b2o2$7b2o$6bob
o$6bo$5b2o68$279b2o$279b2o3b2o2b2o$107b2ob2o172b2o2b2o$107b2ob2o167b2o
$279b2o3$109b2o$109b2o3$109b2o$109b2o91$206b2o$206bo$207b3o$209bo3$
203bo$202bobo$203bo!'''
seed = lt.pattern(seed).centre()
mwss = (seed - seed[32])
seed -= mwss
seed += mwss(1024, 0)
# check D8_1 symmetry of glider outputs:
gliders = seed[runtime]
assert(gliders('rot90') == gliders)
assert(gliders('flip_x') == gliders)
bbox = gliders.match(lt.pattern('2o$obo$o!')).bounding_box
dx = bbox[0] - bbox[1]
dt = runtime + 4 * bbox[1]
return seed, dx, dt
class Octopus(object):
def __init__(self):
self.seed, dx, dt = load_seed()
self.arms = [[dx, dt] for _ in range(8)]
self.starts = ['left', 'left', 'left', 'left']
print(self.arms)
def add_stage(self, salvos):
reverse_transforms = ['identity', 'rot270', 'rot180', 'rot90']
forward_transforms = ['identity', 'rot90', 'rot180', 'rot270']
rotated_salvos = [s(t) for (s, t) in zip(salvos, reverse_transforms)]
rotated_seeds = []
for (i, s) in enumerate(rotated_salvos):
seedpart = []
if s.nonempty():
comps = build_salvo(s, self.starts[i])
for (tfm, ol, ot, sl) in comps:
aidx = 2*i+len(tfm)-8
il, it = self.arms[aidx]
for (j, aspl) in enumerate(adj_splitters):
disp, delay = aspl[1]
if (((disp + il - ol) & 1) == 0) and (((delay + it + ot) & 7) == 0):
self.arms[aidx][0] += aspl[0][0]
self.arms[aidx][1] += aspl[0][1]
x = (il + ol - disp) >> 1
y = x - il
z = (-ot - it - delay) >> 3
seedpart.append([z, x, y, j, sl, tfm])
break
self.starts[i] = {'transpose': 'left', 'identity': 'right'}[tfm]
minz = min([a[0] for a in seedpart])
for a in seedpart:
for jdx in range(3):
a[jdx] -= minz
a[4] = a[4](-minz, -minz)
seedpart = [[tfm, sl + adj_splitters[j][2](x, y), adj_splitters[j][3](x - z, y + z)] for z, x, y, j, sl, tfm in seedpart]
rotated_seeds.append(seedpart)
flat_seeds = []
for s in rotated_seeds:
subseed = lt.pattern('')
for tfm, sl1, sl2 in s:
subseed += (sl1 + sl2)(tfm)
flat_seeds.append(subseed)
lb = 0
ub = 65536
halo = lt.pattern('4bo$2b5o$b7o$b7o$9o$b7o$b7o$2b5o$4bo!').centre()
forbidden = self.seed.convolve(halo)
def try_dist(d):
s = self.seed
for fs, tfm in zip(flat_seeds, forward_transforms):
fs = fs(-d, -d)(tfm)
if (fs & forbidden):
return None
s = s + fs
t = 65536 + 8 * d
st = s[t]
og = lt.pattern('2o$obo$o!')
for (i, (x, dt)) in enumerate(self.arms):
g = og[t - dt](x, 0)
g = g(['identity', 'transpose'][i & 1])
g = g(forward_transforms[i >> 1])
if ((st & g) != g):
return None
st -= g
return s, st
s, desired = try_dist(ub)
while (ub - lb > 1):
mb = (ub + lb) >> 1
x = try_dist(mb)
if (x is not None) and (x[1] == desired):
s = x[0]
ub = mb
else:
lb = mb
print(ub)
for seedpart in rotated_seeds:
for s in seedpart:
for i in [1, 2]:
s[i] = s[i](-ub, -ub)
self.binary_search(rotated_seeds)
def binary_search(self, rotated_seeds, strategy='binary'):
halo = lt.pattern('4bo$2b5o$b7o$b7o$9o$b7o$b7o$2b5o$4bo!').centre()
forbidden = self.seed.convolve(halo)
forward_transforms = ['identity', 'rot90', 'rot180', 'rot270']
collapsed = lt.pattern('')
for (tfm, seedpart) in zip(forward_transforms, rotated_seeds):
for s in seedpart:
collapsed += (s[1] + s[2])(s[0])(tfm)
res = (self.seed + collapsed)[65536]
for (tfm, seedpart) in zip(forward_transforms, rotated_seeds):
for s in seedpart:
lb = sum(s[1].bounding_box[:2]) >> 1
ub = 0
while (ub - lb > 1):
if (strategy == 'linear') and (ub - lb > 8):
mb = ub - 8
elif (strategy == 'raenil') and (ub - lb > 8):
mb = lb + 8
else:
mb = (ub + lb) >> 1
newp = (s[1] + s[2](mb, -mb))(s[0])(-mb,-mb)(tfm)
if (newp & forbidden).nonempty():
lb = mb
continue
cprime = collapsed - (s[1] + s[2](ub, -ub))(s[0])(-ub,-ub)(tfm)
cprime = cprime + newp
if (self.seed + cprime)[65536] == res:
ub = mb
collapsed = cprime
else:
lb = mb
print(ub)
comp = (s[1] + s[2](ub, -ub))(s[0])(-ub,-ub)(tfm)
self.seed += comp
forbidden += comp.convolve(halo)
def finalise(self):
rotated_seeds = []
for j in range(4):
rotated_seeds.append([])
for (k, tfm) in enumerate(['identity', 'transpose']):
rotated_seeds[-1].append([tfm,
lt.pattern('oo$oo!')(-8000 + self.arms[2*j+k][0], -8000),
lt.pattern()])
self.binary_search(rotated_seeds, 'linear')
def load_stages(filename='gnf.rle'):
gnf = lt.load(filename)
bbox = gnf.bounding_box
gnf = centre_by(gnf, gnf[bbox[0] + bbox[2] - 128:,:])
stages = []
while gnf.nonempty():
x = gnf[-80:, :]
if x.empty():
raise ValueError('Malformed GNF')
# print(x.bounding_box)
stages.append(x)
gnf = (gnf - x)(160, 0)
print('%d stages collected.' % len(stages))
stages = [split_synth(x) + (x[4096],) for x in stages[::-1]]
for i in range(len(stages)):
des = (stages[i-1][2] if (i > 0) else lt.pattern())
if (stages[i][0] != des):
print(stages[i][0].rle_string())
print(des.rle_string())
assert(False)
gcount = sum([y.population for x in stages for y in x[1]]) // 5
print('%d gliders involved.' % gcount)
return stages
def to_cts(stages):
orig = lt.pattern()
for _, g, t in stages:
lb = 0
ub = 65536
while (ub - lb >= 4):
mb = (ub + lb) >> 1
g4 = g[0][-mb] + g[1][-mb] + g[2][-mb] + g[3][-mb]
if (orig + g4)[mb + 4096] == t:
ub = mb
else:
lb = mb
print(ub)
g4 = g[0][-ub] + g[1][-ub] + g[2][-ub] + g[3][-ub]
orig = orig + g4
return orig
def main():
octo = Octopus()
stages = load_stages()
# print(to_cts(stages).rle_string())
for (i, s) in enumerate(stages):
octo.add_stage(s[1])
print('Finalising...')
octo.finalise()
print(octo.seed.rle_string())
if __name__ == '__main__':
main()