Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Generate 4G collisions which result in constellations of stationary objects (p1, p2, p3, or p6)
#4Gconstellation-gsets.py
"""Generate a batch of 4 glider collisions and report those which result
in stable constellations. Converts collisions to Shinjuku's gliderset format
and outputs comp lines. This version generates a subset of 4G collisions for
use with synthesise-constelation.py v2.0
Usage:
$ python 4Gconstellation-gsets.py > <compfile>.sjk
Based on popseq.c by Chris Cain
Includes a (slightly modified) version of shinjuku/glidersets.py and the
encode_comp function from shinjuku/transcode.py
See Shinjuku.LICENSE for details.
"""
# For Python3 print function
from __future__ import print_function
import lifelib
import itertools
import os
import sys
# PY2 = sys.version_info[0] == 2
# Lifelib lifetree for B3/S23
lt = lifelib.load_rules("b3s23").lifetree()
count = 0 # Total number of collisions tested
results = set() # Set of glider collisions producing stionary constellations
def main():
tmax = 40
x1 = range(5)
t1 = range(tmax-5)
x2 = range(5)
t2 = range(4)
x3 = range(5)
t3 = range(tmax)
# 1-sided collisions
print("\nGenerating 1-sided collisions.", file=sys.stderr)
for ii in itertools.product(x1,t1):
pat = glider_comp0(ii)
if not check_collision(pat, 2):
continue
for jj in itertools.product(x2,t2,x3,t3):
pat = glider_comp0(ii + jj)
if not check_collision(pat, 4):
continue
test_collision(pat)
# print("\nFound %d out of %d collisions resulting in stable constellations." % (len(results), count), file=sys.stderr)
# 3 direction collisions
print("\nGenerating 3-dir collisions, batch 1.", file=sys.stderr)
for ii in itertools.product(x1,t1):
pat = glider_comp1(ii)
if not check_collision(pat, 2):
continue
for jj in itertools.product(x2,t2,x3,t3):
pat = glider_comp1(ii + jj)
if not check_collision(pat, 4):
continue
test_collision(pat)
print("\nGenerating 3-dir collisions, batch 2.", file=sys.stderr)
t2 = range(tmax)
t3 = range(4)
for ii in itertools.product(x1,t1):
pat = glider_comp2(ii)
if not check_collision(pat, 2):
continue
for jj in itertools.product(x2,t2,x3,t3):
pat = glider_comp2(ii + jj)
if not check_collision(pat, 4):
continue
test_collision(pat)
print("\nFound %d out of %d collisions resulting in stable constellations." % (len(results), count), file=sys.stderr)
# Gliders travelling in four directions: SE, SW, NW and NE
gliders = [lt.pattern(x) for x in ["bo$2bo$3o", "o$obo$2o", "3o$o$bo", "b2o$obo$2bo"]]
# Helper functions to enumerate a small subset of 4 glider collisions
def glider_comp0(ii):
# One sided collisions like original popseq
x1, t1 = ii[:2]
pat = gliders[0] + gliders[0](-12+x1,-12-x1)[t1]
if len(ii) == 6:
_, _, y2, t2, y3, t3 = ii
pat += gliders[1](6,2-y2)[t2] + gliders[1](15,-8-y3)[t3]
return pat
def glider_comp1(ii):
# gliders[1] close to point of collision
# t2 < 4
x1, t1 = ii[:2]
pat = gliders[0] + gliders[0](-12+x1,-12-x1)[t1]
if len(ii) == 6:
_, _, y2, t2, y3, t3 = ii
pat += gliders[1](6,2-y2)[t2] + gliders[2](15,15-y3)[t3]
return pat
def glider_comp2(ii):
# gliders[2] close to point of collision
# t3 < 4
x1, t1 = ii[:2]
pat = gliders[0] + gliders[0](-12+x1,-12-x1)[t1]
if len(ii) == 6:
_, _, y2, t2, y3, t3 = ii
pat += gliders[1](15,-8-y2)[t2] + gliders[2](6,5-y3)[t3]
return pat
def check_collision(pat0, ng):
# Naive check for valid glider collision by testing population for 4 gen
pop = ng * 5
if not (pop == pat0.population):
return False
isValid = True
pat = pat0[0]
for ii in range(4):
pat = pat[1]
if not (pop == pat.population):
isValid = False
return isValid
# Test a glider collision and if it results in a stationary constellation then
# output the apgcode of the resulting constellation and the rle of the collision
def test_collision(gliderPat):
global count, results
count += 1
if count % 1000 == 0:
print(".", file=sys.stderr, end='')
sys.stderr.flush()
# Evolve glider collision for 200 gen and test if result is stationary (p6)
pat = gliderPat[200]
# Ignore if empty
if pat.empty():
return False
pop = pat.population
pat6 = pat[6]
# Test if result is a constellation
if not (pat6.population == pop and pat6 == pat):
return False
# Ignore if constellation producable with 2G
apgcode = pat.apgcode
if apgcode in twoGconsts:
return False
# Found an interesting collision
gliderComp = encode_coll(gliderPat, pat.apgcode)
if gliderComp in results:
print('# ', end='')
else:
results.add(gliderComp)
print(gliderComp)
sys.stdout.flush()
return True
# Gliders in all orientations and all phases. Groups of four are SE, SW, NW and NE respectively
# and phase advances within each group.
gset_gliders = [lt.pattern(x) for x in ["bo$2bo$3o", "obo$b2o$bo", "2bo$obo$b2o", "o$b2o$2o",
"o$obo$2o", "2bo$2o$b2o", "bo$o$3o", "obo$2o$bo",
"3o$o$bo", "bo$2o$obo", "2o$obo$o", "b2o$2o$2bo",
"b2o$obo$2bo", "2o$b2o$o", "3o$2bo$bo", "bo$b2o$obo"]]
oriens = ("identity", "rot90", "rot180", "rot270", "flip_y", "swap_xy_flip", "flip_x", "swap_xy")
# Constellations requiring only two gliders
twoGconsts = ['xp2_7', 'xp2_7zw6952', 'xp2_ggg07y270gggzy0ey2e', 'xp2_s01110szw222',
'xp2_xccy3252zgw8kicz3', 'xp2_y8s0111z6996yggg33zyk11z0cczypez066zykggzciicyg11oozy870ggg',
'xp2_yj2552z696ycezy0888y41110s0111zw70ggg07yh696zzybg8gzyb121', 'xs12_2552zy2696',
'xs16_0ggydgj3zop1yd11', 'xs16_ooy033zy1ooy033', 'xs24_y1696z2552wgw2552zy1343', 'xs4_33',
'xs5_253', 'xs6_696', 'xs7_178c', 'xs7_2596', 'xs8_6996', 'xs8_33w66', 'xs8_rr']
# Glider set class from Shinjuku (by Jeremy Tan)
class gset:
def __init__(self, ll):
"""Create a new glider set by setting this instance's list to ll,
which should have exactly four Patterns."""
self.l = ll
@staticmethod
def extract(comp):
"""Factory method that extracts the gliders from the Pattern comp.
The gliders should be well-spaced for the matching to work."""
res = []
for block in zip(*[iter(gset_gliders)] * 4):
z = [comp.match(g, halo="3o$3o$3o").convolve(g) for g in block]
res.append(z[0] + z[1] + z[2] + z[3])
return gset(res)
@property
def s(self):
"""Return the combination of all Patterns in this glider set."""
return self.l[0] + self.l[1] + self.l[2] + self.l[3]
def __getitem__(self, n):
"""Applies [n] to the individual salvos of this glider set. Since each Pattern
is itself periodic, lifelib can rewind them on its own."""
return gset([part[n] for part in self.l])
def __call__(self, *args):
"""Applies (*args) to this glider set. Care must be taken to permute salvos in case of a rotation."""
temp = self.l
if len(args) & 1: # rotation
o = args[0]
r0, r1, r2, r3 = [part(o) for part in temp]
if o == "identity": temp = [r0, r1, r2, r3]
elif o == "rot90": temp = [r1, r2, r3, r0]
elif o == "rot180": temp = [r2, r3, r0, r1]
elif o == "rot270": temp = [r3, r0, r1, r2]
elif o == "flip_y": temp = [r3, r2, r1, r0]
elif o == "swap_xy_flip": temp = [r2, r1, r0, r3]
elif o == "flip_x": temp = [r1, r0, r3, r2]
elif o == "swap_xy": temp = [r0, r3, r2, r1]
if len(args) >= 2: # translation
temp = [part(args[-2], args[-1]) for part in temp]
return gset(temp)
def ngliders(self):
"""Return the number of gliders in each unidirectional salvo."""
return [salvo.population // 5 for salvo in self.l]
def __len__(self):
"""Return the number of gliders in this glider set as a whole."""
return sum(self.ngliders())
def centre(self):
"""Returns this glider set centred on its overall bounding box, following lifelib's definition."""
bb = self.s.getrect()
return self(-(bb[0] + bb[2] // 2), -(bb[1] + bb[3] // 2))
def canonical_time_finite(self):
"""Given that this glider set has finite lifetime, advance it to canonical time
and return that alongside the number of generations advanced."""
glider_set = gset(self.l)
for i in itertools.count(1): # Advance individual gliders by i generations
advanced = glider_set[1]
if advanced.s == glider_set.s[1]: glider_set = advanced
else: return (glider_set, i - 1)
def pairs(self):
"""Returns a representation of this set's gliders as a length-4 list of lists,
where the entries in each sub-list are pairs (time, lane number) corresponding
to the gliders in the sub-list's corresponding Pattern."""
res = []
for salvo in [self.l[0], self.l[1]("rot90"), self.l[2]("rot180"), self.l[3]("rot270")]:
codes = [] # this direction's gliders
for phase in range(4):
for (x, y) in salvo.match(gset_gliders[phase]).coords():
time = 1 - 4 * (x + 1) - (phase + 1) % 4
lane = x - y + (0 < phase < 3)
codes.append((time, lane))
codes.sort()
res.append(codes)
return res
def __str__(self):
"""Returns a string representation of this glider set based on pairs()."""
return "/".join(" ".join(str(n) for n in itertools.chain.from_iterable(direc)) for direc in self.pairs())
def canonical_form(self):
"""Given that this glider set is at canonical time, returns the canonical form
(orientation and origin included). Not intended for unidirectional sets."""
return max([self(o).centre() for o in oriens], key=lambda x: x.pairs())
def encode_coll(coll, out_apgcode):
"""Extracts the glider set of the collision and determines the canonical
form at canonical time. Assumes collision is made of gliders only.
Returns a Shinjuku component as a string."""
glider_set = gset.extract(coll)
constell = coll - glider_set.s
if constell.nonempty(): assert("Glider collision not completely separated.")
ctime, t = glider_set.canonical_time_finite()
cform = ctime.canonical_form()
if out_apgcode == "xs0_0": out_apgcode = ""
return ">{}>{}".format(cform, out_apgcode)
main()
#4Gconstellation.py
# Generate a batch of 4 glider collisions and report those which result in
# stable constellations
# Based on popseq.c by Chris Cain
# For Python3 print function
from __future__ import print_function
import lifelib
import itertools
import os
import sys
# PY2 = sys.version_info[0] == 2
# Lifelib lifetree for B3/S23
lt = lifelib.load_rules("b3s23").lifetree()
# Process pid
# pid = os.getpid()
# fstdout = '/proc/%d/fd/1' % pid
# Gliders travelling in four directions: SE, SW, NW and NE
gliders = [lt.pattern(x) for x in ["bo$2bo$3o", "o$obo$2o", "3o$o$bo", "b2o$obo$2bo"]]
# Helper functions to enumerate a small subset of 4 glider collisions
def glider_comp0(ii):
# One sided collisions like original popseq
x1, t1 = ii[:2]
pat = gliders[0] + gliders[0](-12+x1,-12-x1)[t1]
if len(ii) == 6:
x1, t1, y2, t2, y3, t3 = ii
pat += gliders[1](6,2-y2)[t2] + gliders[1](15,-8-y3)[t3]
return pat
def glider_comp1(ii):
# gliders[1] close to point of collision
# t2 < 4
x1, t1 = ii[:2]
pat = gliders[0] + gliders[0](-12+x1,-12-x1)[t1]
if len(ii) == 6:
x1, t1, y2, t2, y3, t3 = ii
pat += gliders[1](6,2-y2)[t2] + gliders[2](15,15-y3)[t3]
return pat
def glider_comp2(ii):
# gliders[2] close to point of collision
# t3 < 4
x1, t1 = ii[:2]
pat = gliders[0] + gliders[0](-12+x1,-12-x1)[t1]
if len(ii) == 6:
x1, t1, y2, t2, y3, t3 = ii
pat += gliders[1](15,-8-y2)[t2] + gliders[2](6,5-y3)[t3]
return pat
def check_collision(pat, ng):
# Naive check for valid glider collision by testing population for 4 gen
pop = ng * 5
if not (pop == pat.population):
return False
isValid = True
pat0 = pat[0]
for _ in range(4):
pat0 = pat0[1]
if not (pop == pat0.population):
isValid = False
return isValid
count = 0
results = 0
# Test a glider collision and if it results in a stationary constellation then
# output the apgcode of the resulting constellation and the rle of the collision
def test_collision(gliderPat):
global count, results
count += 1
if results % 10000 == 0:
print(".", file=sys.stderr, end='')
sys.stderr.flush()
# Evolve glider collision for 200 gen and test if result is stationary (p6)
pat = gliderPat[200]
pop = pat.population
pat6 = pat[6]
# Test if result is a constellation
if not (pat6.population == pop and pat6 == pat):
return False
# Ignore if pop < 7 (easy 4G exists)
if pop < 7:
return False
# Ignore if pop < 9 and no tub in constellation (easy 4G exists)
try:
if pat.period == 1:
parts = map(lambda p: p.apgcode, pat.components())
if pop < 9 and not 'xs4_252' in parts:
return False
except KeyError:
# Constellation contains an object with separated parts, e.g carrier
pass
# Found an interesting collision
results += 1
print(pat.apgcode)
print(gliderPat.rle_string(), end='')
sys.stdout.flush()
return True
tmax = 40
x1 = range(5)
t1 = range(tmax-5)
x2 = range(5)
t2 = range(4)
x3 = range(5)
t3 = range(tmax)
# 1-sided collisions
print("Generating 1-sided collisions.", file=sys.stderr)
for ii in itertools.product(x1,t1):
pat = glider_comp0(ii)
if not check_collision(pat, 2):
continue
for jj in itertools.product(x2,t2,x3,t3):
pat = glider_comp0(ii + jj)
if not check_collision(pat, 4):
continue
test_collision(pat)
# print("Found %d out of %d collisions resulting in stable constellations." % (results, count), file=sys.stderr)
# 3 direction collisions
print("Generating 3-dir collisions, batch 1.", file=sys.stderr)
for ii in itertools.product(x1,t1):
pat = glider_comp1(ii)
if not check_collision(pat, 2):
continue
for jj in itertools.product(x2,t2,x3,t3):
pat = glider_comp1(ii + jj)
if not check_collision(pat, 4):
continue
test_collision(pat)
print("Generating 3-dir collisions, batch 2.", file=sys.stderr)
tmax = 40
t2 = range(tmax)
t3 = range(4)
for ii in itertools.product(x1,t1):
pat = glider_comp2(ii)
if not check_collision(pat, 2):
continue
for jj in itertools.product(x2,t2,x3,t3):
pat = glider_comp2(ii + jj)
if not check_collision(pat, 4):
continue
test_collision(pat)
print("Found %d out of %d collisions resulting in stable constellations." % (results, count), file=sys.stderr)
#convert3Gcolls.py
"""Survey glider collisions resulting in stationary constellations.
Convert collisions to Shinjuku's gliderset format and output comp lines
This version converts the existing 3G collision dataset to comp format
Use with synthesise-constelation.py v2.0
Usage:
$ python convert3Gcols.py > <compfile>.sjk
- Requires cols.txt file from original synthesise-constellation script
to be in the same directory.
Includes a (slightly modified) version of shinjuku/glidersets.py and the
encode_comp function from shinjuku/transcode.py
See Shinjuku.LICENSE for details.
"""
# For Python3 print function
from __future__ import print_function
import lifelib
import itertools
import os
import sys
# PY2 = sys.version_info[0] == 2
# Lifelib lifetree for B3/S23
lt = lifelib.load_rules("b3s23").lifetree()
count = 0 # Total number of collisions tested
results = set() # Set of glider collisions producing stionary constellations
def main():
"""Import existing 3G collisions"""
print("\nConvert existing 3G collisions.", file=sys.stderr)
with open("cols.txt","r") as F:
cols = (F.read()[2:-2]).split("], [")
for i in range(0,len(cols)):
cols[i] = cols[i].split(", ")
for rlepat in itertools.chain.from_iterable(cols):
print(rlepat)
pat = lt.pattern(rlepat)
test_collision(pat)
print("\nFound %d out of %d collisions resulting in stable constellations." % (len(results), count), file=sys.stderr)
def test_collision(gliderPat):
"""Test a glider collision and if it results in a stationary
constellation then output the apgcode of the resulting constellation
and the rle of the collision
"""
global count, results
count += 1
if count % 1000 == 0:
print(".", file=sys.stderr, end='')
sys.stderr.flush()
# Evolve glider collision for 200 gen and test if result is stationary (p6)
pat = gliderPat[1000]
# Ignore if empty
if pat.empty():
return False
pop = pat.population
pat6 = pat[6]
# Test if result is a constellation
if not (pat6.population == pop and pat6 == pat):
return False
# Found an interesting collision
gliderComp = encode_coll(gliderPat, pat.apgcode)
if not gliderComp:
return False
if gliderComp in results:
print('# ', end='')
else:
results.add(gliderComp)
print(gliderComp)
sys.stdout.flush()
return True
# Gliders in all orientations and all phases. Groups of four are SE, SW, NW and NE respectively
# and phase advances within each group.
gset_gliders = [lt.pattern(x) for x in ["bo$2bo$3o", "obo$b2o$bo", "2bo$obo$b2o", "o$b2o$2o",
"o$obo$2o", "2bo$2o$b2o", "bo$o$3o", "obo$2o$bo",
"3o$o$bo", "bo$2o$obo", "2o$obo$o", "b2o$2o$2bo",
"b2o$obo$2bo", "2o$b2o$o", "3o$2bo$bo", "bo$b2o$obo"]]
oriens = ("identity", "rot90", "rot180", "rot270", "flip_y", "swap_xy_flip", "flip_x", "swap_xy")
# Constellations requiring only two gliders
twoGconsts = ['xp2_7', 'xp2_7zw6952', 'xp2_ggg07y270gggzy0ey2e', 'xp2_s01110szw222',
'xp2_xccy3252zgw8kicz3', 'xp2_y8s0111z6996yggg33zyk11z0cczypez066zykggzciicyg11oozy870ggg',
'xp2_yj2552z696ycezy0888y41110s0111zw70ggg07yh696zzybg8gzyb121', 'xs12_2552zy2696',
'xs16_0ggydgj3zop1yd11', 'xs16_ooy033zy1ooy033', 'xs24_y1696z2552wgw2552zy1343', 'xs4_33',
'xs5_253', 'xs6_696', 'xs7_178c', 'xs7_2596', 'xs8_6996', 'xs8_33w66', 'xs8_rr']
# Glider set class from Shinjuku (by Jeremy Tan)
class gset:
def __init__(self, ll):
"""Create a new glider set by setting this instance's list to ll,
which should have exactly four Patterns."""
self.l = ll
@staticmethod
def extract(comp):
"""Factory method that extracts the gliders from the Pattern comp.
The gliders should be well-spaced for the matching to work."""
res = []
for block in zip(*[iter(gset_gliders)] * 4):
z = [comp.match(g, halo="3o$3o$3o").convolve(g) for g in block]
res.append(z[0] + z[1] + z[2] + z[3])
return gset(res)
@property
def s(self):
"""Return the combination of all Patterns in this glider set."""
return self.l[0] + self.l[1] + self.l[2] + self.l[3]
def __getitem__(self, n):
"""Applies [n] to the individual salvos of this glider set. Since each Pattern
is itself periodic, lifelib can rewind them on its own."""
return gset([part[n] for part in self.l])
def __call__(self, *args):
"""Applies (*args) to this glider set. Care must be taken to permute salvos in case of a rotation."""
temp = self.l
if len(args) & 1: # rotation
o = args[0]
r0, r1, r2, r3 = [part(o) for part in temp]
if o == "identity": temp = [r0, r1, r2, r3]
elif o == "rot90": temp = [r1, r2, r3, r0]
elif o == "rot180": temp = [r2, r3, r0, r1]
elif o == "rot270": temp = [r3, r0, r1, r2]
elif o == "flip_y": temp = [r3, r2, r1, r0]
elif o == "swap_xy_flip": temp = [r2, r1, r0, r3]
elif o == "flip_x": temp = [r1, r0, r3, r2]
elif o == "swap_xy": temp = [r0, r3, r2, r1]
if len(args) >= 2: # translation
temp = [part(args[-2], args[-1]) for part in temp]
return gset(temp)
def ngliders(self):
"""Return the number of gliders in each unidirectional salvo."""
return [salvo.population // 5 for salvo in self.l]
def __len__(self):
"""Return the number of gliders in this glider set as a whole."""
return sum(self.ngliders())
def centre(self):
"""Returns this glider set centred on its overall bounding box, following lifelib's definition."""
bb = self.s.getrect()
return self(-(bb[0] + bb[2] // 2), -(bb[1] + bb[3] // 2))
def canonical_time_finite(self):
"""Given that this glider set has finite lifetime, advance it to canonical time
and return that alongside the number of generations advanced."""
glider_set = gset(self.l)
for i in itertools.count(1): # Advance individual gliders by i generations
advanced = glider_set[1]
if advanced.s == glider_set.s[1]: glider_set = advanced
else: return (glider_set, i - 1)
def pairs(self):
"""Returns a representation of this set's gliders as a length-4 list of lists,
where the entries in each sub-list are pairs (time, lane number) corresponding
to the gliders in the sub-list's corresponding Pattern."""
res = []
for salvo in [self.l[0], self.l[1]("rot90"), self.l[2]("rot180"), self.l[3]("rot270")]:
codes = [] # this direction's gliders
for phase in range(4):
for (x, y) in salvo.match(gset_gliders[phase]).coords():
time = 1 - 4 * (x + 1) - (phase + 1) % 4
lane = x - y + (0 < phase < 3)
codes.append((time, lane))
codes.sort()
res.append(codes)
return res
def __str__(self):
"""Returns a string representation of this glider set based on pairs()."""
return "/".join(" ".join(str(n) for n in itertools.chain.from_iterable(direc)) for direc in self.pairs())
def canonical_form(self):
"""Given that this glider set is at canonical time, returns the canonical form
(orientation and origin included). Not intended for unidirectional sets."""
return max([self(o).centre() for o in oriens], key=lambda x: x.pairs())
def encode_coll(coll, out_apgcode):
"""Extracts the glider set of the collision and determines the canonical
form at canonical time. Assumes collision is made of gliders only.
Returns a Shinjuku component as a string."""
glider_set = gset.extract(coll)
constell = coll - glider_set.s
if constell.nonempty():
print(coll.rle_string(), file=sys.stderr)
return ''
# assert("Glider collision not completely separated.")
ctime, t = glider_set.canonical_time_finite()
cform = ctime.canonical_form()
if out_apgcode == "xs0_0": out_apgcode = ""
return ">{}>{}".format(cform, out_apgcode)
main()
MIT License
© 2019 Parcly Taxel / Freywa / Jeremy Tan
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.