Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
193 lines (125 sloc) 6.1 KB

What is a glider synthesis?

A number of gliders hitting a constellation of still-lifes or oscillators that produces another constellation of still-lifes or oscillators.

How do we encode a glider synthesis?

By a single line string consisting of 8 fields separated by 7 semi-colons, like so:

input_apgcode;output_apgcode;phase;ne_data;se_data;sw_data;nw_data;transform

What are these fields?

input_apgcode is a string representing the input constellation.

output_apgcode is a string representing the output constellation.

phase is a non-negative integer.

ne_data is a comma separated list of integers giving the positions of all north-east traveling gliders.

se_data, sw_data and nw_data are similarly defined.

transform is a comma separated list of 6 integers.

What are apgcodes?

See http://conwaylife.com/wiki/Apgcode

How exactly is the glider data defined?

All of the xx_data fields are comma separated lists containing an even number (possibly zero) of integers.

Each pair of integers represents a single glider.

The integer pair 0, 0 represents the canonical glider for each direction.

The canonical glider for the north-west direction is 3o$o$bo!. Cell (0,0) is on and all live cells have non-negative x and y coordinates.

The canonical gliders for the other directions are generated by the reflections x -> -x and y -> -y.

The integer pair x, t represents the canonical glider shifted horizontally by x cells and advanced in time by t generations. If t is negative then this is taken to mean that the canonical glider should be rewound by -t generations.

How are the input and output apgcodes related to all this?

The answer to this question will reveal the intention of the fields phase and transform.

To get the full input pattern, draw the input_apgcode at the origin of the universe and draw all of the gliders defined by the four xx_data fields.

Call the input pattern X.

The output pattern is just the output_apgcode drawn at the origin of the universe. Call the output pattern Y.

Remember that phase is a non-negative integer and transform is a comma-separated list of six integers.

If transform is given by a, b, c, d, e, f then it represents the transformation T:(x,y) -> (a + c * x + d * y, b + e * x + f * y).

Define Y to be T(Y) advanced by phase generations.

It is expected that for all sufficiently large values of t that X advanced by t generations is precisely the same pattern as Y' advanced by t generations.

When is a glider synthesis considered canonical?

Well, ... when it is output of the cananicaliser script.

But if you want more details.....

The input and output apgcodes should be canonical apgcodes.

phase must be strictly less than the period of the output apgcode.

The pairs in each xx_data list should be sorted in ascending lexicographic order.

If the input apgcode is non-zero then draw the input pattern at the origin. Run the pattern through a full cycle and note the LifeHistory envelope. A cell is forbidden if its x-value (or its y-value) is within distance 2 of an x-value (or a y-value) of the cells in the LifeHistory envelope.

In the case of a non-zero input apgcode, a glider synthesis is at canonical time if:

  • none of the gliders contain a forbidden cell now
  • none of the gliders contain a forbidden cell if we rewind by an arbitrary amount
  • by the next time the input pattern is in canonical phase at least one glider has encountered a forbidden cell

If the input apgcode is 0 then we define the canonical time using the separation between gliders travelling in different directions.

If a north traveling glider and a south traveling glider have 6 on-cells in a single horizontal line then define that they have time difference 0.

Time differences for gliders in other phases and locations can be calculated relative to this.

Time differences between east and west traveling gliders can be computed by rotating by 90 degrees and using the north-south definition.

If the input apgcode is 0 then a glider synthesis is at canonical time if:

  • all north traveling gliders are at least 12 ticks away from all south traveling gliders.
  • all east traveling gliders are at least 12 ticks away from all west traveling gliders.
  • there is a pair of north-south gliders or a pair of east-west gliders that are 12 or 13 ticks away from each other.

If the input apgcode is 0 and the glider synthesis is canonical in time then to be considered canonical the glider synthesis must consist of only cells with positive x and y coordinate and there must be at least one cell with x-coordinate zero and at least one cell with y-coordinate zero.

If the input constellation has N symmertries then there can be up to N glider syntheses that are the same up to translation, reflection or rotation and satisfy all the conditions given so far. We define an ordering on the tuples (ne_data, se_data,sw_data, nw_data) to define which glider synthesis is canonical.

We order glider data for a single direction by ranking:

  • smaller glider salvos before larger glider salvos
  • glider salvos of equal length by lexicographic order.

We order tuples of glider data by the lexicographic order implied by this ordering.

Now the canonical generation and canonical transformation for the input have been defined.

There can still be more than one valid output transformation. To be canonical the output transform must have its last four integers appear as early as possible in this list:

[(1, 0, 0, 1), (-1, 0, 0, 1), (1, 0, 0, -1), (-1, 0, 0, -1),
 (0, 1, 1, 0), (0, -1, 1, 0), (0, 1, -1, 0), (0, -1, -1, 0)]

Examples

Canonical two-glider boat synthesis:

0;xs5_253;0;;0,7;;2,-20;6,2,-1,0,0,1

RLE:

x = 10, y = 8, rule = B3/S23
o$b2o$2o3$7b3o$7bo$8bo!

Canonical pond -> tub reaction:

xs8_6996;xs4_252;0;;;;-7,-50;-6,2,1,0,0,1

RLE:

x = 9, y = 15, rule = B3/S23
b2o$o2bo$o2bo$b2o9$6b2o$6bobo$6bo!
You can’t perform that action at this time.