apaap/4Gconstellation-gsets.py

## 4Gconstellation-gsets.py
#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
#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
#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()

## Shinjuku.LICENSE
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.
	#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.