Enumerating Three-Glider Collisions

For scripts to aid with computation or simulation in cellular automata.
User avatar
dvgrn
Moderator
Posts: 10610
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Enumerating Three-Glider Collisions

Post by dvgrn » April 23rd, 2017, 8:40 pm

EDIT: See this post by 2718281828 and these scripts by Goldtiger997, for a fairly complete enumeration of three-glider collisions (at least the useful ones). However, there are definitely some duplicates in this collection, so a rework in Shinjuku format would be a good idea at some point.

From the "Implications of a Three-Glider Switch Engine" thread:
dvgrn wrote:Someone should start a new thread for best-practices methods of filtering as-near-as-possible all distinct 3-glider collisions that produce small constellations. I used chris_c's suggestions from gencols: techniques -- thanks, chris_c!
AbhpzTa's discovery of a three-glider SE recipe is something of a wake-up call here. That recipe could have been found any time in the last forty years by enumerating all possible collisions of a glider with a 2-glider [traffic light|block|nothing] recipe.

Given that surprising fact, how likely is it that this new switch-engine recipe is the last unknown three-glider constructible object? How do we know there isn't a clean three-glider recipe for a snake out there somewhere, for example? Or pick your favorite object that we think needs more than three gliders to construct.

Switch engines were a weird case
New super-cheap still life recipes are not terribly likely, of course. The search space has been combed over fairly thoroughly by now, by several people... it's just that no one doing three-glider searches was specifically looking for switch engines, so presumably they got thrown out with all the other big messy explosions.

-- Well, simsim314 found a three-glider collision that produces a switch engine, a few years back, but that search wouldn't have found AbhpzTa's recipe either because clean switch engines self-destruct before too many cycles.

Constellations
There's also the problem of generating arbitrary small constellations as cheaply as possible, with fair confidence that the cheapest recipe has been found. An incredible number of two- and three-object constellations can be constructed with just three gliders, it's a huge search space. But so far, unless someone has a pre-built gencols collisions file that they haven't mentioned, pretty much every such problem has been solved by a separate search.

An Exact Count
The problem of enumerating all distinct three-glider collisions seems just about within reach these days. One thing we might be able to come up with is a precise total number of distinct output patterns excluding gliders, produced by configurations of three gliders in which all three participate in a collision.

If we don't exclude gliders the number of distinct outputs is unlimited, thanks to useless kickbacks on the 2-glider mess, TL+glider, and the three B-heptomino recipes. For example, the following infinite series will have distinct hashes (until the hash-generating algorithm fails and there's a collision, but that's a mighty long way out...!)

Code: Select all

x = 547, y = 120, rule = B3/S23
354bo$355b2o$177bo176b2o$178b2o$o176b2o$b2o$2o66$540bo2bo2bo36$129bo
176bo176bo$128bo176bo176bo$128b3o174b3o174b3o7$126bo176bo176bo$125b2o
175b2o175b2o$125bobo174bobo174bobo!
The hard part is that kickbacks do have to be allowed sometimes, when the kicked-back glider strikes an active or just-settled pattern. Once the kicked-back glider is striking the exact same settled pattern as another pattern's kicked-back glider, I think it shouldn't count as distinct. Seems like it will be pretty hard to get that count exactly right, but that's only a problem with five of the 71 collisions -- could leave those for last.

Thinking about moving the search tree up to four gliders, though, the problem is even worse. Kickback reactions that didn't count as distinct when the search stopped at three gliders, would suddenly count (by producing a different output pattern) when a fourth glider is added.

Collisions and Outputs
The full list of outputs, mostly copied from the 2-glider-collisions stamp collection, is

nothing, blinker, block, glider, boat, beehive, loaf, eater, pond, bi-block, loaf+blinker, loaf+blinker+tub+block (misc), half-blockade (misc), four skewed blocks (misc), traffic light, honeyfarm, B-heptomino, pi, lumps of muck, teardrop, interchange, traffic light+glider, octomino, 2-glider mess.

The great majority of the 71 collisions stabilize within a few dozen ticks. Only one of the "nothing" syntheses takes anywhere close to 100 ticks, for example. Even that is easily within reach of exhaustive enumeration of all possible third gliders.

Enumeration
I'd like to have an enumeration method with at least a little common sense built in -- something along the lines of gencols, tracking the 2-glider collision tick by tick and placing gliders in every possible position where they would interact with the collision for the first time at tick #T.

Really it might be simpler to use plain brute force -- place every glider in every orientation that could possibly touch the collision reaction. Run each one, and then throw away cases where the third glider is totally unaffected by the collision reaction (and vice versa).

Tangent on Heisenburps
If we're trying to get a count of all distinct 3-glider collisions, it's not sufficient to run the pattern and throw out cases where the added third glider is undamaged. There will be the occasional Heisenburp, like these four that showed up in 2003 from investigating just one orientation of B-heptomino:

Code: Select all

x = 306, y = 46, rule = B3/S23
102bobo$103b2o$103bo$201bobo$2bo199b2o$obo199bo$b2o16$303bo$301bobo$
302b2o19$3bo99bo99bo99bo$2b3o97b3o97b3o97b3o$b2o2bo95b2o2bo95b2o2bo95b
2o2bo!
-- It would slow things down quite a bit to have to track the third glider through every tick, to see if it ever has a temporary Heisenburp effect that isn't represented in a changed final pattern, I wonder if it would make sense to build a custom multistate Golly rule that changes a glider's color if it ever participates in a Heisenburp?

Handling Different Kinds of Nothing
Along the same lines as those no-effect Heisenburps, it will be good to have a count not just of all the distinct patterns that can result from three-glider collisions, but also all the collisions themselves, even though many of them produce the same final results. A next step might be to use the resulting collision list to try out every possible edgy 3G spark pattern against various still lifes, and see how many new converters turn up.

If we're really trying to get a count of all the distinct three-glider collision reactions, as opposed to distinct outputs, a subtler problem would be Heisenburps that have only a temporary effect -- changing the shape of a dying spark that does something new but then dies out anyway. Theoretically this could matter if we extended the search tree and hit the changed spark with a fourth glider... but in practice, nobody's going to be trying to count four-glider collisions any time soon. And relatively few useful constructions would come out of reactions like this, because there's an extra output glider that has to be disposed of.

Lists of Hashes
It seems like a good place to start would be to make an official list of the 71 2-glider collisions, each at the position where the gliders will interact for the first time on the next tick. Maybe order them by time to stability. For each collision except for the glider-producing ones, it's not too hard for a search program to find all distinct locations/orientations of a third glider that will interact in some way with that collision. If the search is done with a couple of different independent methods and the count agrees, that will be a good sign.

Each initial pattern of three gliders can be assigned an (extended) apgcode, and a hash can be recorded of the initial canonical orientation and also of its eventual stabilized output pattern, minus any gliders. At least one infinite-growth pattern will show up, so I guess that and any other unknown ones can best be handled as special cases.

To determine a final count of three-glider collisions we'll just have to compare the 71 lists of initial hashes and remove any duplicates. The only potential duplicates will be between cases where the third glider interacts immediately, at the same tick as the first two.

User avatar
Extrementhusiast
Posts: 1966
Joined: June 16th, 2009, 11:24 pm
Location: USA

Re: Enumerating Three-Glider Collisions

Post by Extrementhusiast » April 23rd, 2017, 11:02 pm

dvgrn wrote:Really it might be simpler to use plain brute force -- place every glider in every orientation that could possibly touch the collision reaction. Run each one, and then throw away cases where the third glider is totally unaffected by the collision reaction (and vice versa).
I've already been doing this for a few of them as part of my work on syntheses, as it's useful for slightly modifying edgy subpatterns that appear within two-glider collisions.
dvgrn wrote:-- It would slow things down quite a bit to have to track the third glider through every tick, to see if it ever has a temporary Heisenburp effect that isn't represented in a changed final pattern, I wonder if it would make sense to build a custom multistate Golly rule that changes a glider's color if it ever participates in a Heisenburp?
I've already done something similar: a rule that tracks if two differently-colored patterns interact:

Code: Select all

@RULE objtracklife2

@TABLE

n_states:5
neighborhood:Moore
symmetries:permute

# all states
var Aa={0,1,2,3,4}
var Ab={Aa}
var Ac={Aa}
var Ad={Aa}
var Ae={Aa}
var Af={Aa}
var Ag={Aa}
var Ah={Aa}

# live states
var La={1,2,3}
var Lb={La}
var Lc={La}
var Ld={La}
var Le={La}
var Lf={La}
var Lg={La}
var Lh={La}

# dead states
var Da={0,4}
var Db={Da}
var Dc={Da}
var Dd={Da}
var De={Da}
var Df={Da}
var Dg={Da}
var Dh={Da}


# off in both universes
# on in both universes (pre-interaction)
# on in only current universe (pre-interaction)
# on in both universes (post-interaction)
# on in only current universe (post-interaction)
# on in only alternate universe
# history in current universe; off in alternate universe
# history in current universe; on in alternate universe


0,Da,Db,Dc,Dd,De,La,La,La,La
Da,Db,Dc,Dd,De,Df,La,Lb,Lc,3

La,Da,Db,Dc,Dd,De,Df,La,La,La
La,Da,Db,Dc,Dd,De,La,La,La,La
La,Da,Db,Dc,Dd,De,Aa,Lb,Lc,3
3,Aa,Ab,Ac,Ad,Ae,Af,Ag,Ah,4
La,Aa,Ab,Ac,Ad,Ae,Af,Ag,Ah,0

0,Aa,Ab,Ac,Ad,1,1,1,2,4
0,Aa,Ab,Ac,Ad,1,2,2,2,4

@COLORS

1 255   0   0
2   0 255   0
3 255 255 255
4 102 102 102

@ICONS

circles
One then just needs to check for cells of at least state 3, which is easily done with another rule: every generation, reduce all non-empty cellstates by one (a bit like //256 in reverse).

(However, I'm planning on making objtracklife3, featuring a three-layered simulation of A, B, and A+B, as soon as I can figure out the details within the damn transitions!)
I Like My Heisenburps! (and others)

User avatar
Scorbie
Posts: 1692
Joined: December 7th, 2013, 1:05 am

Re: Enumerating Three-Glider Collisions

Post by Scorbie » April 23rd, 2017, 11:49 pm

Extrementhusiast wrote:
dvgrn wrote:-- It would slow things down quite a bit to have to track the third glider through every tick, to see if it ever has a temporary Heisenburp effect that isn't represented in a changed final pattern, I wonder if it would make sense to build a custom multistate Golly rule that changes a glider's color if it ever participates in a Heisenburp?
I've already done something similar: a rule that tracks if two different patterns interact...
Why not just run the pattern until stabilization (or the until the generation of stabilization of the two-glider collision) And see if the end product is merely the sum of the two patterns, the two-glider collision stabilization and the third glider?

User avatar
dvgrn
Moderator
Posts: 10610
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Enumerating Three-Glider Collisions

Post by dvgrn » April 24th, 2017, 8:15 am

Scorbie wrote:Why not just run the pattern until stabilization (or the until the generation of stabilization of the two-glider collision) And see if the end product is merely the sum of the two patterns, the two-glider collision stabilization and the third glider?
The possibility of zero-effect Heisenburps makes that not quite good enough. We could end up with a passing glider encouraging a huge and useful spark, for example. The spark might very well die out in the end, producing an identical output as if no Heisenburp had happened.

It looks like a regular no-interaction, and is in danger of getting discarded if we only use the run-to-stabilization test. But that case needs to be counted as a real three-glider collision, and it's not just a technicality -- the spark might turn out to be uniquely useful in some synthesis or other, for all we know.

In practice that's not going to happen much, since Heisenburps by definition always have an extra output glider that will probably need to be disposed of, so there's a built-in inefficiency. Really the main reason for noticing these is that if you don't, the statistics on the total number of 3-glider collisions will be wrong (horrors!)

User avatar
Scorbie
Posts: 1692
Joined: December 7th, 2013, 1:05 am

Re: Enumerating Three-Glider Collisions

Post by Scorbie » April 24th, 2017, 12:44 pm

dvgrn wrote:It looks like a regular no-interaction, and is in danger of getting discarded if we only use the run-to-stabilization test. But that case needs to be counted as a real three-glider collision, and it's not just a technicality -- the spark might turn out to be uniquely useful in some synthesis or other, for all we know.

In practice that's not going to happen much, since Heisenburps by definition always have an extra output glider that will probably need to be disposed of, so there's a built-in inefficiency. Really the main reason for noticing these is that if you don't, the statistics on the total number of 3-glider collisions will be wrong (horrors!)
Ah, I see, thanks :) Having a similar idea for ptbsearch, I decided (in my vaporware blueprint) to discard those cases...

User avatar
dvgrn
Moderator
Posts: 10610
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Enumerating Three-Glider Collisions

Post by dvgrn » April 24th, 2017, 1:58 pm

dvgrn wrote:It seems like a good place to start would be to make an official list of the 71 2-glider collisions, each at the position where the gliders will interact for the first time on the next tick.
On second thought, it seems like a better idea to start N ticks back from the first interaction. When we drop in glider #3, we have to have some way to verify that the new glider would not have interacted with either of the existing gliders before they collide with each other.

(If this happens, we'll get unnecessary duplication -- the collision usually becomes a different collision entirely, of a type that will be enumerated elsewhere.)

The only duplication that needs to be checked for will be in the fairly limited number of cases where the three gliders all start interacting on the same tick. If any two gliders A and B start interacting first, then that collision is the primary collision, and the 3-glider recipe can be enumerated unambiguously as "glider collision #{0..70} plus {NE|SE|SW|NW} glider on lane L, delay of T ticks".

It seems like an interesting subproblem to generate all of these simultaneous-collision cases, and remove the duplicates -- probably using a dictionary of apgcodes, to automatically choose a canonical orientation.

Once the duplicates are removed, a delayed glider can be added in every possible way to each of the 71 collisions. That will be 71 separate searches, with no possibility of duplication with any other search. Or am I missing something important here?

... It should be fairly easy to produce four graphs for each of the 71 collisions, showing the possible {NE|SE|SW|NW} lanes in one dimension, and the allowable values of T (delay times) on each lane that produce actual collisions -- instead of trivial flyby behavior, or duplication due to collision with an already-settled part of the pattern. Maybe separate colors for small constellations and for the occasional Heisenburp reactions.

User avatar
_zM
Posts: 186
Joined: June 26th, 2016, 3:07 pm

Re: Enumerating Three-Glider Collisions

Post by _zM » April 25th, 2017, 2:27 pm

dvgrn wrote: Tangent on Heisenburps
If we're trying to get a count of all distinct 3-glider collisions, it's not sufficient to run the pattern and throw out cases where the added third glider is undamaged. There will be the occasional Heisenburp, like these four that showed up in 2003 from investigating just one orientation of B-heptomino:

Code: Select all

x = 306, y = 46, rule = B3/S23
102bobo$103b2o$103bo$201bobo$2bo199b2o$obo199bo$b2o16$303bo$301bobo$
302b2o19$3bo99bo99bo99bo$2b3o97b3o97b3o97b3o$b2o2bo95b2o2bo95b2o2bo95b
2o2bo!
-- It would slow things down quite a bit to have to track the third glider through every tick, to see if it ever has a temporary Heisenburp effect that isn't represented in a changed final pattern, I wonder if it would make sense to build a custom multistate Golly rule that changes a glider's color if it ever participates in a Heisenburp?
So I tried making that rule you mentioned, and it kind of works:

Code: Select all

@RULE heisenbork

@TABLE
n_states:3
neighborhood:Moore
symmetries:rotate4reflect

var a = {0,1,2}
var b = a
var c = a
var d = a
var e = a
var f = a
var g = a
var h = a
var i = a

var j = {1,2}
var k = j
var l = j
var m = j

0,1,1,1,0,0,0,0,0,1 #B3a
0,0,1,1,1,0,0,0,0,1 #B3i
0,1,1,0,1,0,0,0,0,1 #B3n
0,1,0,1,1,0,0,0,0,1 #B3j

1,1,1,0,0,0,0,0,0,1 #S2a
1,1,0,1,0,0,0,0,0,1 #S2e
1,1,0,1,1,0,0,0,0,1 #S3j
1,1,1,0,1,0,0,0,0,1 #S3n
1,1,1,0,0,1,0,0,0,1 #S3r

j,k,l,0,0,0,0,0,0,2 #S2a
j,k,0,l,0,0,0,0,0,2 #S2e
j,k,0,0,l,0,0,0,0,2 #S2k
j,k,0,0,0,l,0,0,0,2 #S2i
j,0,k,0,0,0,l,0,0,2 #S2n
j,0,k,0,l,0,0,0,0,2 #S2c

a,j,0,k,l,0,0,0,0,2 #3j
a,j,k,0,l,0,0,0,0,2 #3n
a,j,k,0,0,l,0,0,0,2 #3r
a,0,j,0,k,0,l,0,0,2 #3c
a,j,0,k,0,l,0,0,0,2 #3e
a,j,0,k,0,0,l,0,0,2 #3k
a,j,k,l,0,0,0,0,0,2 #3a
a,0,j,k,l,0,0,0,0,2 #3i
a,0,j,k,0,0,l,0,0,2 #3q
a,j,0,0,k,0,l,0,0,2 #3y

a,b,c,d,e,f,g,h,i,0
Of the four heisenburps shown above, this rule detects two (by turning the glider from state 1 to state 2). I don't know if this is any useful, but...
moment

User avatar
Rhombic
Posts: 1072
Joined: June 1st, 2013, 5:41 pm

Re: Enumerating Three-Glider Collisions

Post by Rhombic » April 26th, 2017, 9:26 am

_zM wrote:
dvgrn wrote: Tangent on Heisenburps
If we're trying to get a count of all distinct 3-glider collisions, it's not sufficient to run the pattern and throw out cases where the added third glider is undamaged. There will be the occasional Heisenburp, like these four that showed up in 2003 from investigating just one orientation of B-heptomino:

Code: Select all

x = 306, y = 46, rule = B3/S23
102bobo$103b2o$103bo$201bobo$2bo199b2o$obo199bo$b2o16$303bo$301bobo$
302b2o19$3bo99bo99bo99bo$2b3o97b3o97b3o97b3o$b2o2bo95b2o2bo95b2o2bo95b
2o2bo!
-- It would slow things down quite a bit to have to track the third glider through every tick, to see if it ever has a temporary Heisenburp effect that isn't represented in a changed final pattern, I wonder if it would make sense to build a custom multistate Golly rule that changes a glider's color if it ever participates in a Heisenburp?
So I tried making that rule you mentioned, and it kind of works:

Code: Select all

@RULE heisenbork

@TABLE
n_states:3
neighborhood:Moore
symmetries:rotate4reflect

var a = {0,1,2}
var b = a
var c = a
var d = a
var e = a
var f = a
var g = a
var h = a
var i = a

var j = {1,2}
var k = j
var l = j
var m = j

0,1,1,1,0,0,0,0,0,1 #B3a
0,0,1,1,1,0,0,0,0,1 #B3i
0,1,1,0,1,0,0,0,0,1 #B3n
0,1,0,1,1,0,0,0,0,1 #B3j

1,1,1,0,0,0,0,0,0,1 #S2a
1,1,0,1,0,0,0,0,0,1 #S2e
1,1,0,1,1,0,0,0,0,1 #S3j
1,1,1,0,1,0,0,0,0,1 #S3n
1,1,1,0,0,1,0,0,0,1 #S3r

j,k,l,0,0,0,0,0,0,2 #S2a
j,k,0,l,0,0,0,0,0,2 #S2e
j,k,0,0,l,0,0,0,0,2 #S2k
j,k,0,0,0,l,0,0,0,2 #S2i
j,0,k,0,0,0,l,0,0,2 #S2n
j,0,k,0,l,0,0,0,0,2 #S2c

a,j,0,k,l,0,0,0,0,2 #3j
a,j,k,0,l,0,0,0,0,2 #3n
a,j,k,0,0,l,0,0,0,2 #3r
a,0,j,0,k,0,l,0,0,2 #3c
a,j,0,k,0,l,0,0,0,2 #3e
a,j,0,k,0,0,l,0,0,2 #3k
a,j,k,l,0,0,0,0,0,2 #3a
a,0,j,k,l,0,0,0,0,2 #3i
a,0,j,k,0,0,l,0,0,2 #3q
a,j,0,0,k,0,l,0,0,2 #3y

a,b,c,d,e,f,g,h,i,0
Of the four heisenburps shown above, this rule detects two (by turning the glider from state 1 to state 2). I don't know if this is any useful, but...
It should make detection of Heisenburps trivial with a very simple script. The question is whether the Heisenburps themselves are useful and the answer should be "generally yes, especially for stable ash (i.e. stable glider detectors)". However, there's that - most Heisenburps will involve a Heisenburp chaotic explosion from a constellation or, in fact, mainly Heisenburps with non-stable patterns. The latter would need specific design to be incorporated into any kind of circuitry and, on top of that, synchronising a glider - if it is, say, p120 Herschel interactions, the gliders can only transmit information at a maximum of 120 ticks per bit. How useful is this? Just now, not that useful. But Boole never imagined his concepts ending up being so amazingly important either.

The main problem is, with the current state-of-art circuitry, at most there will be four or five Heisenburps that are actually worth discovering (without having to design massive circuits to use them in a totally different way). Even then, these will most certainly be edge-shooters and still, it is highly unlikely for there to be a useful Heisenburp associated.

But the script is trivial nonetheless (check that pattern evolution is different from the same without the glider, then check glider has changed colour to avoid trivial solutions and check that it is in the same position as an unhindered evolution).
SoL : FreeElectronics : DeadlyEnemies : 6a-ite : Rule X3VI
what is “sesame oil”?

User avatar
dvgrn
Moderator
Posts: 10610
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Enumerating Three-Glider Collisions

Post by dvgrn » May 27th, 2017, 3:31 pm

Extrementhusiast wrote:I've already done something similar: a rule that tracks if two differently-colored patterns interact:

Code: Select all

@RULE objtracklife2...
That seems to work fine for any possible Heisenburp -- at least, it passes the test for all four samples that I posted:

Code: Select all

x = 307, y = 166, rule = objtracklife2
102.B.B$103.2B$103.B$201.B.B$2.B199.2B$B.B199.B$.2B16$303.B$301.B.B$
302.2B19$3.A99.A99.A99.A$2.3A97.3A97.3A97.3A$.2A2.A95.2A2.A95.2A2.A
95.2A2.A75$103.A.A$104.2A$104.A$202.A.A$3.A199.2A$.A.A199.A$2.2A16$
304.A$302.A.A$303.2A19$4.B99.B99.B99.B$3.3B97.3B97.3B97.3B$2.2B2.B95.
2B2.B95.2B2.B95.2B2.B!
Extrementhusiast wrote:One then just needs to check for cells of at least state 3, which is easily done with another rule: every generation, reduce all non-empty cellstates by one (a bit like //256 in reverse).
Here's the cleanup rule boiled down to about as simple as I can make it. If the universe isn't empty after the combined state-1 and state-2 pattern runs for LONG_ENOUGH in objtrack2, and then one tick in objtrackcleanup, then the two subpatterns interacted:

Code: Select all

@RULE objtrackcleanup

@TABLE
n_states:5
neighborhood:oneDimensional
symmetries:none

var a = {0,1,2,3,4}
var b = a
var c = {3,4}
var d = {1,2}
c,a,b,3
d,a,b,0
Extrementhusiast wrote:(However, I'm planning on making objtracklife3, featuring a three-layered simulation of A, B, and A+B, as soon as I can figure out the details within the damn transitions!)
Wasn't that already done a few years ago? ... ah, I guess that was just two superimposed layers, not three. For three layers I'd probably have to give up and write a script to generate the rule -- sorting out all the transitions by hand would be too much of a pain.

User avatar
Extrementhusiast
Posts: 1966
Joined: June 16th, 2009, 11:24 pm
Location: USA

Re: Enumerating Three-Glider Collisions

Post by Extrementhusiast » May 29th, 2017, 6:37 pm

dvgrn wrote:
Extrementhusiast wrote:(However, I'm planning on making objtracklife3, featuring a three-layered simulation of A, B, and A+B, as soon as I can figure out the details within the damn transitions!)
Wasn't that already done a few years ago? ... ah, I guess that was just two superimposed layers, not three. For three layers I'd probably have to give up and write a script to generate the rule -- sorting out all the transitions by hand would be too much of a pain.
I did so without using such a script (although using other software, in this case Mathematica, to generate what combinations made what):

Code: Select all

@RULE deeperlife

@TABLE

n_states:8
neighborhood:Moore
symmetries:permute

# all states
var a={0,1,2,3,4,5,6,7}
var b={a}
var c={a}
var d={a}
var e={a}
var f={a}
var g={a}
var h={a}
var i={a}

# states with red
var Ra={4,5,6,7}
var Rb={Ra}
var Rc={Ra}
var Rd={Ra}
var Re={Ra}
var Rf={Ra}
var Rg={Ra}
var Rh={Ra}
var Ri={Ra}

# states without red
var ra={0,1,2,3}
var rb={ra}
var rc={ra}
var rd={ra}
var re={ra}
var rf={ra}
var rg={ra}
var rh={ra}
var ri={ra}

# states with green
var Ga={2,3,6,7}
var Gb={Ga}
var Gc={Ga}
var Gd={Ga}
var Ge={Ga}
var Gf={Ga}
var Gg={Ga}
var Gh={Ga}
var Gi={Ga}

# states without green
var ga={0,1,4,5}
var gb={ga}
var gc={ga}
var gd={ga}
var ge={ga}
var gf={ga}
var gg={ga}
var gh={ga}
var gi={ga}

# states with blue
var Ba={1,3,5,7}
var Bb={Ba}
var Bc={Ba}
var Bd={Ba}
var Be={Ba}
var Bf={Ba}
var Bg={Ba}
var Bh={Ba}
var Bi={Ba}

# states without blue
var ba={0,2,4,6}
var bb={ba}
var bc={ba}
var bd={ba}
var be={ba}
var bf={ba}
var bg={ba}
var bh={ba}
var bi={ba}

# states with red and with green
var RGa={6,7}
var RGb={RGa}
var RGc={RGa}
var RGd={RGa}
var RGe={RGa}
var RGf={RGa}
var RGg={RGa}
var RGh={RGa}
var RGi={RGa}

# states with red and without green
var Rga={4,5}
var Rgb={Rga}
var Rgc={Rga}
var Rgd={Rga}
var Rge={Rga}
var Rgf={Rga}
var Rgg={Rga}
var Rgh={Rga}
var Rgi={Rga}

# states without red and with green
var rGa={2,3}
var rGb={rGa}
var rGc={rGa}
var rGd={rGa}
var rGe={rGa}
var rGf={rGa}
var rGg={rGa}
var rGh={rGa}
var rGi={rGa}

# states without red and without green
var rga={0,1}
var rgb={rga}
var rgc={rga}
var rgd={rga}
var rge={rga}
var rgf={rga}
var rgg={rga}
var rgh={rga}
var rgi={rga}

# states with red and with blue
var RBa={5,7}
var RBb={RBa}
var RBc={RBa}
var RBd={RBa}
var RBe={RBa}
var RBf={RBa}
var RBg={RBa}
var RBh={RBa}
var RBi={RBa}

# states with red and without blue
var Rba={4,6}
var Rbb={Rba}
var Rbc={Rba}
var Rbd={Rba}
var Rbe={Rba}
var Rbf={Rba}
var Rbg={Rba}
var Rbh={Rba}
var Rbi={Rba}

# states without red and with blue
var rBa={1,3}
var rBb={rBa}
var rBc={rBa}
var rBd={rBa}
var rBe={rBa}
var rBf={rBa}
var rBg={rBa}
var rBh={rBa}
var rBi={rBa}

# states without red and without blue
var rba={0,2}
var rbb={rba}
var rbc={rba}
var rbd={rba}
var rbe={rba}
var rbf={rba}
var rbg={rba}
var rbh={rba}
var rbi={rba}

# states with green and with blue
var GBa={3,7}
var GBb={GBa}
var GBc={GBa}
var GBd={GBa}
var GBe={GBa}
var GBf={GBa}
var GBg={GBa}
var GBh={GBa}
var GBi={GBa}

# states with green and without blue
var Gba={2,6}
var Gbb={Gba}
var Gbc={Gba}
var Gbd={Gba}
var Gbe={Gba}
var Gbf={Gba}
var Gbg={Gba}
var Gbh={Gba}
var Gbi={Gba}

# states without green and with blue
var gBa={1,5}
var gBb={gBa}
var gBc={gBa}
var gBd={gBa}
var gBe={gBa}
var gBf={gBa}
var gBg={gBa}
var gBh={gBa}
var gBi={gBa}

# states without green and without blue
var gba={0,4}
var gbb={gba}
var gbc={gba}
var gbd={gba}
var gbe={gba}
var gbf={gba}
var gbg={gba}
var gbh={gba}
var gbi={gba}

# B[RGB]
a,0,0,0,0,0,7,7,7,7
a,0,0,0,0,1,6,7,7,7
a,0,0,0,0,2,5,7,7,7
a,0,0,0,0,3,4,7,7,7
a,0,0,0,0,3,5,6,7,7
a,0,0,0,1,1,6,6,7,7
a,0,0,0,1,2,4,7,7,7
a,0,0,0,1,2,5,6,7,7
a,0,0,0,1,3,4,6,7,7
a,0,0,0,1,3,5,6,6,7
a,0,0,0,2,2,5,5,7,7
a,0,0,0,2,3,4,5,7,7
a,0,0,0,2,3,5,5,6,7
a,0,0,0,3,3,4,4,7,7
a,0,0,0,3,3,4,5,6,7
a,0,0,1,1,1,6,6,6,7
a,0,0,1,1,2,4,6,7,7
a,0,0,1,1,2,5,6,6,7
a,0,0,1,1,3,4,6,6,7
a,0,0,1,2,2,4,5,7,7
a,0,0,1,2,2,5,5,6,7
a,0,0,1,2,3,4,4,7,7
a,0,0,1,2,3,4,5,6,7
a,0,0,1,3,3,4,4,6,7
a,0,0,2,2,2,5,5,5,7
a,0,0,2,2,3,4,5,5,7
a,0,0,2,3,3,4,4,5,7
a,0,0,3,3,3,4,4,4,7
a,0,1,1,1,2,4,6,6,7
a,0,1,1,2,2,4,4,7,7
a,0,1,1,2,2,4,5,6,7
a,0,1,1,2,3,4,4,6,7
a,0,1,2,2,2,4,5,5,7
a,0,1,2,2,3,4,4,5,7
a,0,1,2,3,3,4,4,4,7
a,1,1,1,2,2,4,4,6,7
a,1,1,2,2,2,4,4,5,7
a,1,1,2,2,3,4,4,4,7

# B[RG], S[B]
Ba,0,0,0,0,0,6,7,7,7
Ba,0,0,0,0,1,6,6,7,7
Ba,0,0,0,0,2,4,7,7,7
Ba,0,0,0,0,2,5,6,7,7
Ba,0,0,0,0,3,4,6,7,7
Ba,0,0,0,0,3,5,6,6,7
Ba,0,0,0,1,1,6,6,6,7
Ba,0,0,0,1,2,4,6,7,7
Ba,0,0,0,1,2,5,6,6,7
Ba,0,0,0,1,3,4,6,6,7
Ba,0,0,0,2,2,4,5,7,7
Ba,0,0,0,2,2,5,5,6,7
Ba,0,0,0,2,3,4,4,7,7
Ba,0,0,0,2,3,4,5,6,7
Ba,0,0,0,3,3,4,4,6,7
Ba,0,0,1,1,2,4,6,6,7
Ba,0,0,1,2,2,4,4,7,7
Ba,0,0,1,2,2,4,5,6,7
Ba,0,0,1,2,3,4,4,6,7
Ba,0,0,2,2,2,4,5,5,7
Ba,0,0,2,2,3,4,4,5,7
Ba,0,0,2,3,3,4,4,4,7
Ba,0,1,1,2,2,4,4,6,7
Ba,0,1,2,2,2,4,4,5,7
Ba,0,1,2,2,3,4,4,4,7
Ba,1,1,2,2,2,4,4,4,7

# B[RB], S[G]
Ga,0,0,0,0,0,5,7,7,7
Ga,0,0,0,0,1,4,7,7,7
Ga,0,0,0,0,1,5,6,7,7
Ga,0,0,0,0,2,5,5,7,7
Ga,0,0,0,0,3,4,5,7,7
Ga,0,0,0,0,3,5,5,6,7
Ga,0,0,0,1,1,4,6,7,7
Ga,0,0,0,1,1,5,6,6,7
Ga,0,0,0,1,2,4,5,7,7
Ga,0,0,0,1,2,5,5,6,7
Ga,0,0,0,1,3,4,4,7,7
Ga,0,0,0,1,3,4,5,6,7
Ga,0,0,0,2,2,5,5,5,7
Ga,0,0,0,2,3,4,5,5,7
Ga,0,0,0,3,3,4,4,5,7
Ga,0,0,1,1,1,4,6,6,7
Ga,0,0,1,1,2,4,4,7,7
Ga,0,0,1,1,2,4,5,6,7
Ga,0,0,1,1,3,4,4,6,7
Ga,0,0,1,2,2,4,5,5,7
Ga,0,0,1,2,3,4,4,5,7
Ga,0,0,1,3,3,4,4,4,7
Ga,0,1,1,1,2,4,4,6,7
Ga,0,1,1,2,2,4,4,5,7
Ga,0,1,1,2,3,4,4,4,7
Ga,1,1,1,2,2,4,4,4,7

# B[GB], S[R]
Ra,0,0,0,0,0,3,7,7,7
Ra,0,0,0,0,1,2,7,7,7
Ra,0,0,0,0,1,3,6,7,7
Ra,0,0,0,0,2,3,5,7,7
Ra,0,0,0,0,3,3,4,7,7
Ra,0,0,0,0,3,3,5,6,7
Ra,0,0,0,1,1,2,6,7,7
Ra,0,0,0,1,1,3,6,6,7
Ra,0,0,0,1,2,2,5,7,7
Ra,0,0,0,1,2,3,4,7,7
Ra,0,0,0,1,2,3,5,6,7
Ra,0,0,0,1,3,3,4,6,7
Ra,0,0,0,2,2,3,5,5,7
Ra,0,0,0,2,3,3,4,5,7
Ra,0,0,0,3,3,3,4,4,7
Ra,0,0,1,1,1,2,6,6,7
Ra,0,0,1,1,2,2,4,7,7
Ra,0,0,1,1,2,2,5,6,7
Ra,0,0,1,1,2,3,4,6,7
Ra,0,0,1,2,2,2,5,5,7
Ra,0,0,1,2,2,3,4,5,7
Ra,0,0,1,2,3,3,4,4,7
Ra,0,1,1,1,2,2,4,6,7
Ra,0,1,1,2,2,2,4,5,7
Ra,0,1,1,2,2,3,4,4,7
Ra,1,1,1,2,2,2,4,4,7

# B[R], S[GB]
GBa,0,0,0,0,0,4,7,7,7
GBa,0,0,0,0,0,5,6,7,7
GBa,0,0,0,0,1,4,6,7,7
GBa,0,0,0,0,1,5,6,6,7
GBa,0,0,0,0,2,4,5,7,7
GBa,0,0,0,0,2,5,5,6,7
GBa,0,0,0,0,3,4,4,7,7
GBa,0,0,0,0,3,4,5,6,7
GBa,0,0,0,1,1,4,6,6,7
GBa,0,0,0,1,2,4,4,7,7
GBa,0,0,0,1,2,4,5,6,7
GBa,0,0,0,1,3,4,4,6,7
GBa,0,0,0,2,2,4,5,5,7
GBa,0,0,0,2,3,4,4,5,7
GBa,0,0,0,3,3,4,4,4,7
GBa,0,0,1,1,2,4,4,6,7
GBa,0,0,1,2,2,4,4,5,7
GBa,0,0,1,2,3,4,4,4,7
GBa,0,1,1,2,2,4,4,4,7

# B[G], S[RB]
RBa,0,0,0,0,0,2,7,7,7
RBa,0,0,0,0,0,3,6,7,7
RBa,0,0,0,0,1,2,6,7,7
RBa,0,0,0,0,1,3,6,6,7
RBa,0,0,0,0,2,2,5,7,7
RBa,0,0,0,0,2,3,4,7,7
RBa,0,0,0,0,2,3,5,6,7
RBa,0,0,0,0,3,3,4,6,7
RBa,0,0,0,1,1,2,6,6,7
RBa,0,0,0,1,2,2,4,7,7
RBa,0,0,0,1,2,2,5,6,7
RBa,0,0,0,1,2,3,4,6,7
RBa,0,0,0,2,2,2,5,5,7
RBa,0,0,0,2,2,3,4,5,7
RBa,0,0,0,2,3,3,4,4,7
RBa,0,0,1,1,2,2,4,6,7
RBa,0,0,1,2,2,2,4,5,7
RBa,0,0,1,2,2,3,4,4,7
RBa,0,1,1,2,2,2,4,4,7

# B[B], S[RG]
RGa,0,0,0,0,0,1,7,7,7
RGa,0,0,0,0,0,3,5,7,7
RGa,0,0,0,0,1,1,6,7,7
RGa,0,0,0,0,1,2,5,7,7
RGa,0,0,0,0,1,3,4,7,7
RGa,0,0,0,0,1,3,5,6,7
RGa,0,0,0,0,2,3,5,5,7
RGa,0,0,0,0,3,3,4,5,7
RGa,0,0,0,1,1,1,6,6,7
RGa,0,0,0,1,1,2,4,7,7
RGa,0,0,0,1,1,2,5,6,7
RGa,0,0,0,1,1,3,4,6,7
RGa,0,0,0,1,2,2,5,5,7
RGa,0,0,0,1,2,3,4,5,7
RGa,0,0,0,1,3,3,4,4,7
RGa,0,0,1,1,1,2,4,6,7
RGa,0,0,1,1,2,2,4,5,7
RGa,0,0,1,1,2,3,4,4,7
RGa,0,1,1,1,2,2,4,4,7

# S[RGB]
7,0,0,0,0,0,0,7,7,7
7,0,0,0,0,0,1,6,7,7
7,0,0,0,0,0,2,5,7,7
7,0,0,0,0,0,3,4,7,7
7,0,0,0,0,0,3,5,6,7
7,0,0,0,0,1,1,6,6,7
7,0,0,0,0,1,2,4,7,7
7,0,0,0,0,1,2,5,6,7
7,0,0,0,0,1,3,4,6,7
7,0,0,0,0,2,2,5,5,7
7,0,0,0,0,2,3,4,5,7
7,0,0,0,0,3,3,4,4,7
7,0,0,0,1,1,2,4,6,7
7,0,0,0,1,2,2,4,5,7
7,0,0,0,1,2,3,4,4,7
7,0,0,1,1,2,2,4,4,7

# B[RG], D/A[B]
rga,rgb,rgc,rgd,rge,rgf,RGg,RGh,RGi,6
rga,rgb,rgc,rgd,rge,rGf,Rgg,RGh,RGi,6
rga,rgb,rgc,rgd,rGe,rGf,Rgg,Rgh,RGi,6
rga,rgb,rgc,rGd,rGe,rGf,Rgg,Rgh,Rgi,6

# B[R], S[G], D/A[B]
rGa,rgb,rgc,rgd,rge,rgf,RGg,RGh,RGi,6
rGa,rgb,rgc,rgd,rge,rf,Rgg,RGh,RGi,6
rGa,rgb,rgc,rgd,re,rGf,Rgg,Rgh,RGi,6
rGa,rgb,rgc,rd,rGe,rGf,Rgg,Rgh,Rgi,6

# B[G], S[R], D/A[B]
Rga,rgb,rgc,rgd,rge,rgf,RGg,RGh,RGi,6
Rga,rgb,rgc,rgd,rge,rGf,gg,RGh,RGi,6
Rga,rgb,rgc,rgd,rGe,rGf,gg,Rgh,RGi,6
Rga,rgb,rgc,rGd,rGe,rGf,gg,Rgh,Rgi,6

# S[RG], D/A[B]
RGa,rgb,rgc,rgd,rge,rgf,RGg,RGh,RGi,6
RGa,rgb,rgc,rgd,rge,gf,rg,RGh,RGi,6
RGa,rgb,rgc,rgd,ge,rf,rGg,Rgh,RGi,6
RGa,rgb,rgc,gd,re,rGf,rGg,Rgh,Rgi,6

# B[RB], D/A[G]
rba,rbb,rbc,rbd,rbe,rbf,RBg,RBh,RBi,5
rba,rbb,rbc,rbd,rbe,rBf,Rbg,RBh,RBi,5
rba,rbb,rbc,rbd,rBe,rBf,Rbg,Rbh,RBi,5
rba,rbb,rbc,rBd,rBe,rBf,Rbg,Rbh,Rbi,5

# B[R], S[B], D/A[G]
rBa,rbb,rbc,rbd,rbe,rbf,RBg,RBh,RBi,5
rBa,rbb,rbc,rbd,rbe,rf,Rbg,RBh,RBi,5
rBa,rbb,rbc,rbd,re,rBf,Rbg,Rbh,RBi,5
rBa,rbb,rbc,rd,rBe,rBf,Rbg,Rbh,Rbi,5

# B[B], S[R], D/A[G]
Rba,rbb,rbc,rbd,rbe,rbf,RBg,RBh,RBi,5
Rba,rbb,rbc,rbd,rbe,rBf,bg,RBh,RBi,5
Rba,rbb,rbc,rbd,rBe,rBf,bg,Rbh,RBi,5
Rba,rbb,rbc,rBd,rBe,rBf,bg,Rbh,Rbi,5

# S[RB], D/A[G]
RBa,rbb,rbc,rbd,rbe,rbf,RBg,RBh,RBi,5
RBa,rbb,rbc,rbd,rbe,bf,rg,RBh,RBi,5
RBa,rbb,rbc,rbd,be,rf,rBg,Rbh,RBi,5
RBa,rbb,rbc,bd,re,rBf,rBg,Rbh,Rbi,5

# B[GB], D/A[R]
gba,gbb,gbc,gbd,gbe,gbf,GBg,GBh,GBi,3
gba,gbb,gbc,gbd,gbe,gBf,Gbg,GBh,GBi,3
gba,gbb,gbc,gbd,gBe,gBf,Gbg,Gbh,GBi,3
gba,gbb,gbc,gBd,gBe,gBf,Gbg,Gbh,Gbi,3

# B[G], S[B], D/A[R]
gBa,gbb,gbc,gbd,gbe,gbf,GBg,GBh,GBi,3
gBa,gbb,gbc,gbd,gbe,gf,Gbg,GBh,GBi,3
gBa,gbb,gbc,gbd,ge,gBf,Gbg,Gbh,GBi,3
gBa,gbb,gbc,gd,gBe,gBf,Gbg,Gbh,Gbi,3

# B[B], S[G], D/A[R]
Gba,gbb,gbc,gbd,gbe,gbf,GBg,GBh,GBi,3
Gba,gbb,gbc,gbd,gbe,gBf,bg,GBh,GBi,3
Gba,gbb,gbc,gbd,gBe,gBf,bg,Gbh,GBi,3
Gba,gbb,gbc,gBd,gBe,gBf,bg,Gbh,Gbi,3

# S[GB], D/A[R]
GBa,gbb,gbc,gbd,gbe,gbf,GBg,GBh,GBi,3
GBa,gbb,gbc,gbd,gbe,bf,gg,GBh,GBi,3
GBa,gbb,gbc,gbd,be,gf,gBg,Gbh,GBi,3
GBa,gbb,gbc,bd,ge,gBf,gBg,Gbh,Gbi,3

# B[R], D/A[GB]
ra,rb,rc,rd,re,rf,Rg,Rh,Ri,4

# S[R], D/A[GB]
Ra,rb,rc,rd,re,rf,g,Rh,Ri,4

# B[G], D/A[RB]
ga,gb,gc,gd,ge,gf,Gg,Gh,Gi,2

# S[G], D/A[RB]
Ga,gb,gc,gd,ge,gf,g,Gh,Gi,2

# B[B], D/A[RG]
ba,bb,bc,bd,be,bf,Bg,Bh,Bi,1

# S[B], D/A[RG]
Ba,bb,bc,bd,be,bf,g,Bh,Bi,1

# D/A[RGB]
a,b,c,d,e,f,g,h,i,0

@COLORS

0   0   0   0
1   0   0 255
2   0 255   0
3   0 255 255
4 255   0   0
5 255   0 255
6 255 255   0
7 255 255 255

@ICONS

circles
At this point, it's just figuring out the conditions under which markings are placed and whatnot.

----------

In other news, I seem to have figured out the simultaneous cases:
3gcolls-simultaneous-2state.rle
PRELIMINARY
(69.35 KiB) Downloaded 699 times
However, since I did this relatively by hand (i.e. no scripts whatsoever, only rule and paste manipulation), somebody should check this result. Here are the steps that I took:
  1. List all 71 two-glider collisions (preferably by location, NOT by result), timed a moderate number of generations (I used 24) before canonical form. (Careful! Sudden-contact collisions such as the TL+glider actually interact one generation before they "should"!)
  2. Duplicate all entries within the list, so that every collision is listed twice. For each identical pair of collisions, designate one glider in one copy and the other glider in the other copy as the key glider; I used a separate cellstate to denote this.
  3. For each collision, rotate/reflect it so that the "key" glider is traveling SE, and is in one of the two phases listed below:

    Code: Select all

    ...........
    .A.A.....B.
    ..AA...B.B.
    ..A.....BB.
    ...........
  4. Split the list into two sub-lists; one sub-list should contain all of the collisions with key gliders in Phase A, and all of the collisions with key gliders in phase B belong to the other sub-list. (If you haven't already, now would be a good time to check for duplicates, which will all be symmetrical.) (I ended up with sub-lists of length 53 and 73.)
  5. Now for the fun part: for each sub-list, take every possible pair of entries, combining them so that their key gliders are superimposed; the resultant lists of pairs can be combined into a single list. (I ended up making the non-key cellstates different within each pair.)
  6. Remove any collisions with illegal pairs of non-key gliders (a.k.a. pairs of gliders traveling in the same direction that don't stay separate).
  7. Remove any collisions in which the key gliders interact too early.
  8. At this point (at which I had a total of 1602 entries), every collision is a proper member of this set, but there are still some duplicates hiding within. Take all of the entries for which every pair of gliders interacts at the same time; set aside the rest for now.
  9. Of this subset of collisions, keep only the entries without a NW-bound glider. (Yes, it really is that simple to remove the duplicates!)
  10. Recombine this now-smaller subset with the entries set aside to obtain the final list.
An alternative option to part of the first few steps is to use what I like to call "gridding", i.e. making a Moiré pattern from two grids with slightly different offsets in space and/or time:

Code: Select all

x = 1025, y = 364, rule = B3/S23
obo47bobo47bobo47bobo47bobo47bobo47bobo47bobo47bobo47bobo47bobo47bobo
47bobo47bobo47bobo47bobo47bobo47bobo47bobo47bobo47bobo$b2o48b2o48b2o
48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o
48b2o48b2o48b2o48b2o$bo49bo49bo49bo49bo49bo49bo49bo49bo49bo49bo49bo49b
o49bo49bo49bo49bo49bo49bo49bo49bo8$3o48b3o48b3o48b3o48b3o48b3o48b3o48b
3o48b3o48b3o48b3o48b3o48b3o48b3o48b3o48b3o48b3o48b3o48b3o48b3o48b3o$o
50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo
50bo50bo50bo$bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50b
o50bo50bo50bo50bo50bo50bo38$obo47bobo47bobo47bobo47bobo47bobo47bobo47b
obo47bobo47bobo47bobo47bobo47bobo47bobo47bobo47bobo47bobo47bobo47bobo
47bobo47bobo$b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b
2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o$bo49bo49bo49bo49bo49bo
49bo49bo49bo49bo49bo49bo49bo49bo49bo49bo49bo49bo49bo49bo49bo8$b2o49b2o
49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o
49b2o49b2o49b2o49b2o49b2o$2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o
49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o$2bo50bo
50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo
50bo50bo38$obo47bobo47bobo47bobo47bobo47bobo47bobo47bobo47bobo47bobo
47bobo47bobo47bobo47bobo47bobo47bobo47bobo47bobo47bobo47bobo47bobo$b2o
48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o
48b2o48b2o48b2o48b2o48b2o48b2o$bo49bo49bo49bo49bo49bo49bo49bo49bo49bo
49bo49bo49bo49bo49bo49bo49bo49bo49bo49bo49bo8$b2o49b2o49b2o49b2o49b2o
49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o
49b2o49b2o$bobo48bobo48bobo48bobo48bobo48bobo48bobo48bobo48bobo48bobo
48bobo48bobo48bobo48bobo48bobo48bobo48bobo48bobo48bobo48bobo48bobo$bo
50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo
50bo50bo50bo38$obo47bobo47bobo47bobo47bobo47bobo47bobo47bobo47bobo47bo
bo47bobo47bobo47bobo47bobo47bobo47bobo47bobo47bobo47bobo47bobo47bobo$b
2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b
2o48b2o48b2o48b2o48b2o48b2o48b2o$bo49bo49bo49bo49bo49bo49bo49bo49bo49b
o49bo49bo49bo49bo49bo49bo49bo49bo49bo49bo49bo8$2bo50bo50bo50bo50bo50bo
50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo$b2o49b2o
49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o
49b2o49b2o49b2o49b2o49b2o$bobo48bobo48bobo48bobo48bobo48bobo48bobo48bo
bo48bobo48bobo48bobo48bobo48bobo48bobo48bobo48bobo48bobo48bobo48bobo
48bobo48bobo38$obo47bobo47bobo47bobo47bobo47bobo47bobo47bobo47bobo47bo
bo47bobo47bobo47bobo47bobo47bobo47bobo47bobo47bobo47bobo47bobo47bobo$b
2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b
2o48b2o48b2o48b2o48b2o48b2o48b2o$bo49bo49bo49bo49bo49bo49bo49bo49bo49b
o49bo49bo49bo49bo49bo49bo49bo49bo49bo49bo49bo9$b3o48b3o48b3o48b3o48b3o
48b3o48b3o48b3o48b3o48b3o48b3o48b3o48b3o48b3o48b3o48b3o48b3o48b3o48b3o
48b3o48b3o$bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo
50bo50bo50bo50bo50bo50bo$2bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo
50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo37$obo47bobo47bobo47bobo47bobo
47bobo47bobo47bobo47bobo47bobo47bobo47bobo47bobo47bobo47bobo47bobo47bo
bo47bobo47bobo47bobo47bobo$b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o
48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o$bo49bo49b
o49bo49bo49bo49bo49bo49bo49bo49bo49bo49bo49bo49bo49bo49bo49bo49bo49bo
49bo9$2b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o
49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o$b2o49b2o49b2o49b2o49b2o49b2o
49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o
49b2o$3bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo
50bo50bo50bo50bo50bo37$obo47bobo47bobo47bobo47bobo47bobo47bobo47bobo
47bobo47bobo47bobo47bobo47bobo47bobo47bobo47bobo47bobo47bobo47bobo47bo
bo47bobo$b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b
2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o$bo49bo49bo49bo49bo49bo49bo
49bo49bo49bo49bo49bo49bo49bo49bo49bo49bo49bo49bo49bo49bo9$2b2o49b2o49b
2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b
2o49b2o49b2o49b2o49b2o$2bobo48bobo48bobo48bobo48bobo48bobo48bobo48bobo
48bobo48bobo48bobo48bobo48bobo48bobo48bobo48bobo48bobo48bobo48bobo48bo
bo48bobo$2bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo
50bo50bo50bo50bo50bo50bo37$obo47bobo47bobo47bobo47bobo47bobo47bobo47bo
bo47bobo47bobo47bobo47bobo47bobo47bobo47bobo47bobo47bobo47bobo47bobo
47bobo47bobo$b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b
2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o48b2o$bo49bo49bo49bo49bo49bo
49bo49bo49bo49bo49bo49bo49bo49bo49bo49bo49bo49bo49bo49bo49bo9$3bo50bo
50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo50bo
50bo50bo$2b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o
49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o49b2o$2bobo48bobo48bobo48bobo
48bobo48bobo48bobo48bobo48bobo48bobo48bobo48bobo48bobo48bobo48bobo48bo
bo48bobo48bobo48bobo48bobo48bobo!
This method, which I ended up using, might be easier, as the duplications have already been taken care of, even avoiding copying the symmetric cases! (The key glider is always in the same place for this method.) However, timing adjustments still need to occur, and don't forget to sort out the cases where the gliders miss!

(If needed, I can explain any of the steps and/or why they work in more detail.)
I Like My Heisenburps! (and others)

User avatar
dvgrn
Moderator
Posts: 10610
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Enumerating Three-Glider Collisions

Post by dvgrn » May 29th, 2017, 8:53 pm

Extrementhusiast wrote:I did so without using such a script (although using other software, in this case Mathematica, to generate what combinations made what)...
At this point, it's just figuring out the conditions under which markings are placed and whatnot.
That seems simple enough. The primary Life universes are red (binary 100), green (010) and blue (001), right? (Hmm, if you switched green and blue, then those colors would be correct in LifeHistory... but sadly I didn't add a state 7, so there are some combinations that there's no room for.)

XOR works!
Anyway, then I think we can just XOR-paste in Golly to encode simultaneous red = A+B. green = A, and blue = B universes -- or to remove a red, blue, or green universe from a combined pattern. Here's a test:

Code: Select all

x = 96, y = 11, rule = deeperlife
14.B39.D39.F$.A10.2B27.D10.2D27.E10.2F$2.A10.2B27.D10.2D27.E10.2F$3A
37.3D37.3E4$13.3B37.3D37.3F$.2A10.B27.2D10.D27.2E10.F$2.2A10.B27.2D
10.D27.2E10.F$.A39.D39.E!
XOR-pasting the first group of gliders onto the second, or the second onto the first, produces the third group, the purple and yellow gliders at the right. Pasting one of the first two groups onto the third group produces the remaining group. And when you run the purple and yellow group, the blue and green universes die out as they should, and all that's left is the correct red A+B combination. Looks good!

But XOR doesn't replace objtracklife2 --
I still like the objtracklife2 rule better for checking interactions. It will notice a change due to a Heisenburp reaction even if the resulting Heisenspark dies out with no permanent consequences. I kind of expect to run into a few such cases among the three-glider collisions, and it would be good to track them.

(If anyone is ever crazy enough to try to enumerate a subset of the 4G collisions somehow starting with the 3G ones, there might just possibly be some interesting recipes that would otherwise be missed, maybe with the Heisenburp glider being kicked back to hit the dying Heisenspark. But see below.)
Extrementhusiast wrote:In other news, I seem to have figured out the simultaneous cases ...
(If needed, I can explain any of the steps and/or why they work in more detail.)
It seems clear enough on first inspection. I certainly don't see any holes in your method immediately, though I'll try to think about it some more. Looks like your magic number for simultaneous collisions is 23190/15 = 1546.

Same number from a different search (I hope)
I'm planning to take a somewhat different approach, based on what will have to be done anyway to enumerate all the distinct 3G cases where two of the gliders collide first:
  • Start with each of the 71 two-glider collisions, rewound by let's say 24 ticks. Call the start time T=-24.
  • Find the reaction envelope of the 2G collision.
  • Enumerate all lanes, with gliders coming from all four possible directions, where some part of the lane touches some part of the reaction envelope.
  • Test all gliders on each lane that could possibly interact with the two-glider reaction.
    • Start with a glider just beyond the reaction envelope on that lane, that are traveling away from the reaction.
    • Try every glider spacetime location backwards from there until the gliders start hitting a completely stabilized pattern.
    • Keep all 3G combinations that interact in any way.
    • (Use objtracklife2 to make sure that the apparent noninteractions aren't really Heisenburps.)
  • Of these sets of three interacting gliders, throw out those that start interacting before T=0. These will be enumerated elsewhere.
  • Then sort out those that start interacting at T=0. If all goes well, there should be a total of 1546 of them.
  • The rest are all distinct 3-glider collisions. Like the simultaneous 3Gs, many of them will produce output identical to other collisions, but they should all still be counted as distinct cases.
Argh, kickbacks...
I'm not looking forward to troubleshooting the cases where there's an output glider that can be kicked back into a still-active reaction... but it seems clear that once the reaction settles, there's only one more set of four kickbacks that should be considered distinct from the more-delayed kickbacks. A higher delay doesn't do anything from a 3G point of view -- the "same glider" ends up hitting the "same junk" in the exact same way, after everything gets a little older.

From the point of view of 4G collisions, that's actually not good enough. A fourth glider could hit a piece of junk, or the last dying spark from let's say the 2-glider-mess reaction, and prolong it for long enough that a very long-delayed kickback glider might do something unique.

Unfortunately almost none of these "4-glider mess" reactions are going to be very interesting, except maybe a few that produce a really rare still life. There will be a large number of 4-glider-mess collisions, a truly horribly large number, so that will certainly happen occasionally...!

Conclusion
The moral of this story is: don't anyone ever try to enumerate all 4G collisions. If anything, maybe try to work on subsets like 4G simultaneous collisions, or 4G collisions based on each 3G collision that doesn't produce a switch engine or an output glider or *WSS.

I'm looking forward to having a nice complete list of all the small constellations that can be constructed with three gliders, though...!

User avatar
2718281828
Posts: 738
Joined: August 8th, 2017, 5:38 pm

Re: Enumerating Three-Glider Collisions

Post by 2718281828 » October 19th, 2017, 2:06 pm

After my post of a few 3glider collisions (3GCs) I am writing my thoughts to the enumeration of all 3 glider collisions.
And of course one of the main challenges is the definition of a 3 glider collision. It is a not just a pattern containing three gliders...

To start simple, 3GC must have arbitrary many preprocessors containing 3 gliders.
This removes pattern as the upper one in:

Code: Select all

x = 10, y = 32, rule = B3/S23
8bo$9bo$7b3o4$4bo2b3o$2bobo4bo$3b2o3bo11$6bo$7bo$5b3o4$2bo$obo$b2o2$5b
3o$7bo$6bo!
The same problem occurs for 2 gliders:

Code: Select all

x = 7, y = 4, rule = B3/S23
2bo$obo2bo$b2o2b2o$4bobo!
which is not of the 71 2-glider collisions.

So in general we need the condition:
[1] reaction must have arbitrary many preprocessors containing 3 gliders.

Now to the question what is a collision? (For me) it is clear that all three gliders must be involved in a reaction.
Thus, the Heisenburb as mentioned counts as a collision

Code: Select all

x = 98, y = 36, rule = B3/S23
5$63bo25bo$61bobo23bobo$62b2o24b2o19$14bo48bo$13b3o46b3o$12b2o2bo44b2o
2bo!
Similarly, it might be that a two glider reaction creates something such that the third glider continues its flight but creates an additional 'spark'.
The only theoretical possibility I know are two diagonal cells at a back of a glider that could add a new spark (see

Code: Select all

x = 24, y = 7, rule = B3/S23
$2bo$bo10bo$11bo$4bobo6bobo5bobo$5b2o7b2o6b2o$5bo8bo7bo!
at generation 1). If a 2-glider reaction could create this kind of 'spark', then this would be a new 3GC even though one glider would continue its flight all the way. But it generates a new cell, which makes the reaction distinct from the 2-glider reaction with a third glider passing without influencing the 2-glider reaction. However, my feeling is that this is not possible for a 3 glider collision, but I did not check this so far.
To formalise this to some extent, we need the 'not decomposable condition':
[2] a 3 glider collision must be distinct of all 2-glider collision + third glider (A+B,C), and distinct from 3 just passing gliders (A,B,C).

This will be a key for the enumeration. Before going in this direction another problem:
I also like the general approach (that is proposed here) of taking the 71 different 2-glider collusion as a basis and add a third glider, the (A+B, C) approach.

However, I am not 100% sure if this covers all possible reactions. We could theoretically have a constellation of 3 gliders that react together (A,B,C), but each pair of two gliders (out of the three) do not react, e.g.

Code: Select all

x = 48, y = 7, rule = B3/S23
b2o18b2o19b2o$2o18b2o19b2o$2bo19bo20bo$4bobo26bobo9bobo$2bo2b2o15bo8bo
2b2o10b2o$2o3bo14b2o7b2o3bo11bo$b2o18b2o7b2o!
I think such pattern is not possible under [1] because we have only two different directions where the gliders can come from, but it must be proven.
If I assume that we all 3GCs results from a 2-glider collision + third glider (A+B,C) we can start counting them.

My actual procedure is not done, actually scripts are still running (and might have to be rerun...) - a lot of postprocessing (concerning symmetries, and things we have to discuss concerning the definition) must be done as well.

I am taking always one of the 2 glider collisions as starting point,

Code: Select all

x = 7007, y = 12, rule = B3/S23
404bobo6599bo$404b2o6598b2o$405bo6599b2o$bo99bo99bo99bo99bo99bo99bo99b
o98bo100bo99bo99bo99bo98bo99bo99bo100bo99bo99bo99bo99bo99bo99bo99bo98b
o100bo99bo99bo99bo99bo99bo99bo99bo99bo99bo99bo99bo99bo99bo99bo98bo100b
o99bo99bo99bo99bo98bo99bo100bo98bo100bo99bo99bo99bo99bo99bo99bo99bo99b
o99bo99bo98bo100bo99bo99bo98bo100bo99bo99bo99bo99bo$2bo99bo99bo99bo99b
o99bo99bo99bo98b2o99bo99bo99bo99bo98b2o98b2o98b2o99bo99bo99bo99bo99bo
99bo99bo99bo98b2o99bo99bo99bo99bo99bo99bo99bo99bo99bo99bo99bo99bo99bo
99bo99bo98b2o99bo99bo99bo99bo99bo98b2o98b2o99bo98b2o99bo99bo99bo99bo
99bo99bo99bo99bo99bo99bo99bo98b2o99bo99bo99bo98b2o99bo99bo99bo99bo99bo
$3o97b3o97b3o97b3o97b3o97b3o2bo94b3o97b3o97b2o98b3o97b3o97b3o97b3o97b
2o98b2o98b2o98b3o97b3o97b3o97b3o97b3o97b3o97b3o97b3o97b2o98b3o97b3o97b
3o97b3o97b3o97b3o97b3o97b3o97b3o97b3o97b3o97b3o97b3o97b3o97b3o97b2o98b
3o97b3o97b3o97b3o97b3o97b2o3bo94b2o98b3o97b2o98b3o97b3o97b3o97b3o97b3o
97b3o97b3o97b3o97b3o97b3o97b3o97b2o98b3o97b3o97b3o97b2o98b3o97b3o97b3o
97b3o97b3o$505bobo997b2o2298bo200bo598b2o98bo1799bo$505b2o297bo499b2o
99b2o97b2o799bo99bo99b2o1298b2o197b2o598bobo98b2o197bobo397b3o698bo99b
o398b2o$199bo98bo298b2o100b2o103b2o95b2o97b2o98b3o99b3o98b2o99b2o100bo
494b3o95b3o102bo99b2o98b2o98b2o94bo102b2o97b2o97b2o100b2o98b3o94b2o97b
2o102b3o92b2o103bobo94b2o102bobo95b2o101b2o96b2o93b2o101bo98bo303bobo
95b3o99b2o92b3o100b2o100b2o101bo95bo97b2o100b2o100b2o97bo97b2o100b2o
98b2o98bo98b2o96b3o101bobo94b3o97bo100bo96b2o$b3o98b3o94b2o97b2o298b2o
100b2o101bobo96b2o97b2o97bo101bo102bo100bo195b3o96b3o96b3o96b3o99bo97b
o103b2o99bobo97bobo99bo92b2o101b2o98bobo95bobo99bobo98bo95b2o97b2o105b
o91bobo103b2o95bobo198b2o200bobo93b2o99b2o98b2o98b3o301bo100bo92bo101b
2o102b2o99bo96b2o95bobo99bobo99b2o97b2o97bobo100b2o98b2o97b2o98b2o97bo
200bo97b2o98b2o96bobo$3bo100bo93bobo96bobo297bo101bo201bo98bo100bo101b
o398bo98bo98bo98bo102bo97bo102bobo393bobo102bo97bo99bo101bo99bo96bo98b
o103bo94bo104bo95bo202bo199bo94bo101bobo96bobo100bo300bo195bo102bo100b
o197bobo97bo101bo101bo96bobo96bo300bobo97bo98bo200bo97bobo98bobo95bo$
2bo100bo1499bo98bo98bo98bo2600bo!
in such a state before they get connected in the sense that the Moore neighbourhoods of the two gliders overlap. Additionally I save the stabilisation time (ST), e.g. starting in the position showed below (how ST is defined exactly is explained later), for the 2GCs that result in nothing this is simply the life span.

For adding the third glider I am using a fix point which should be close to the 2G reaction centre (in my implementation this is the upper left point of glider A which is at coordinate (0,0)). Then I setting a radius R which defines the distance to the fix point in either x or y direction, this radius will be increased.
Somehow, illustrated as in

Code: Select all

x = 57, y = 25, rule = B3/S23
39bo6bo$39bo6bo$27bo3bo7bo6bo$27bo3bo4b14o$16bobo6b9o5bo6bo$15b5o7bo3b
o7bo6bo$16bobo8bo3bo7bo6bo$15b5o7bo3bo7bo6bo$16bobo6b9o5bo6bo$27bo3bo
7bo6bo$27bo3bo4b14o$39bo6bo$39bo6bo$39bo6bo5$5o12bo10b4o9b4o$o3bo12bo
13bo12bo$o3bo2b3o7bo13bo12bo$4o13bo12bo11b3o7bobobo$obo4b3o7bo11bo14bo
$o2bo13bo10bo15bo$o3bo12bo10b4o9b4o!
this forms something like balls or 4walls dependend on the radius. At each of these points a place a glider (out of the 16 possible constellation only those ones which travel in the direction of the reaction center).
Then I check [1] (replacing them 40 generations back in the past and see if the pattern matches the 'proposed' one 40 generations later) to have a valid pattern. Then I run the 3G pattern for ST generations and store the hashes - AND - the hashes of the pattern where the third glider is removed. If both hash-sequences are the same, then the gilder simply passed the reaction otherwise it influenced the reaction. Note that Heisenburbs are detected by this. If the hash sequence is different then I save the original 3G pattern. Of course this might introduce many pattern multiple times (as they occur for multiple 2G collisions) and we have to delete many of them afterwards, also some because of symmetry. The relevant radius R can be easily computed using the life time of the 2G constellation.
However, the 5 reaction, the 2-glider-mess, B and the TL+glider, which releases at least one gliders make life even more complicated. Here the ST must be increased further to make sure that a released glider hits a third glider so that the 2-glider pattern is influenced (also kick-backs is possible). However, this is possible if ST is large enough [and upper bounds can be computed], everything can be covered.

If we have all possible reaction there is the question what do we count as a new 3GC? And even without kickbacks this question is not trivial.
To illustrate the problem consider:

Code: Select all

x = 324, y = 69, rule = B3/S23
18bo26bo27bo$18bobo22b2o27bo26bobo28bo26bo27bo$18b2o24b2o26b3o24b2o29b
obo22b2o27bo26bobo26bo26bo27bo$100bo29b2o24b2o26b3o24b2o27bobo22b2o27b
o26bobo$212bo27b2o24b2o26b3o24b2o$322bo5$bo25bo28bo26bo30bo25bo28bo26b
o28bo25bo28bo26bo$2bo25bo28bo26bo30bo25bo28bo26bo28bo25bo28bo26bo$3o
23b3o26b3o24b3o28b3o23b3o26b3o24b3o26b3o23b3o26b3o24b3o3$3b2o24b2o27b
2o25b2o29b2o24b2o27b2o25b2o27b2o24b2o27b2o25b2o$2bobo23bobo26bobo24bob
o28bobo23bobo26bobo24bobo26bobo23bobo26bobo24bobo$4bo25bo28bo26bo30bo
25bo28bo26bo28bo25bo28bo26bo5$145bo55b2o27b2o24b2o27b2o25b2o$145bo27b
3o25b2o27b2o24b2o27b2o25b2o$145bo23$14bo24bo$12b2o24bo28bobo24bo31bo
24bo$13b2o23b3o26b2o25bobo27b2o24bo28bobo24bo29bo24bo$68bo25b2o29b2o
23b3o26b2o25bobo25b2o24bo28bobo$180bo25b2o27b2o23b3o26b2o$290bo$7bo25b
o28bo26bo30bo25bo28bo26bo28bo25bo28bo$8bo25bo28bo26bo30bo25bo28bo26bo
28bo25bo28bo$6b3o23b3o26b3o24b3o28b3o23b3o26b3o24b3o26b3o23b3o26b3o3$
7b2o24b2o27b2o25b2o29b2o24b2o27b2o25b2o27b2o24b2o27b2o$6bobo23bobo26bo
bo24bobo28bobo23bobo26bobo24bobo26bobo23bobo26bobo$8bo25bo28bo26bo30bo
25bo28bo26bo28bo25bo28bo7$202b2o27b2o24b2o27b2o$202b2o27b2o24b2o27b2o!
There I listed a couple of different 3G pattern, some of them have a blinker or a block under them.
However, the question is: How many different 3GCs do we have here?
My suggestion is 11 (those with a blinker and a block below). However, those with a blinker are only representatives, the other ones without a blinker or block below could serve as well. Those ones with a block below are for me different reactions, even though the first blinker and first block reaction result in the almost the same, but generation 28 resp. 26 look different. To summarise the patterns with a block count under my point of view as a 'standard' new reaction, and these ones with a blinker as '3rd glider hits stable pattern' reaction. If this is anwered we can deal with the problem of pattern that release gliders.

Here we have the problem that the glider can hit another glider arbitraryly late. So there are theoretically infinitely many reactions and even ashes possible. Therefore we can not list all of them. But if we consider e.g.

Code: Select all

x = 129, y = 35, rule = B3/S23
17bo45bo30bo31bo$18bo45bo30bo31bo$16b3o43b3o28b3o29b3o3$17b3o43b3o28b
3o29b3o$19bo45bo30bo31bo$18bo45bo30bo31bo19$bo$b2o$obo44bo$47b2o$46bob
o29bo$78b2o$77bobo30bo$110b2o$109bobo!
Then we see that the first 3G pattern is clearly an new collision, and the other ones are somehow similar and we can take a representative for describing this pattern class. For me the most plausible choice is for the 2nd 3G pattern shown above. Then we have reactions {A&B + C+(0,2a)} for all integers a>=0 (A&B is the 2 glider constellation which leads here to TL+glider, C the third glider). We have 5 of these constellations releasing 1 (TL+G), 2,2,2 (B), 4(2Gmess) gliders. So there should be in total at most Zx(1+2+2+2+4)=Zx11 of these infinite sets where Z enumerates the potential 2G collisions. Z should be at least 71, but it is larger due to symmetries, as e.g.

Code: Select all

x = 68, y = 34, rule = B3/S23
65bobo$65b2o$66bo$17bo29bo$18bo29bo$16b3o27b3o3$17b3o27b3o$19bo29bo$
18bo29bo21$bo$b2o$obo!
are different, but the latter 2G collisions is counted only once in the 71.
This does not hold only for gliders from different directs, but also for 'front' collisions.
So

Code: Select all

x = 61, y = 33, rule = B3/S23
bo41bo$2bo41bo$3o39b3o3$b3o39b3o$3bo41bo$2bo41bo19$58b3o$58bo$59bo2$
14b3o$14bo$15bo!
show two different infinite representations (even though the glider come from the same side in the same way [considering the 71 basic 2G colls.]). So an open question is what is Z? I guess 71x2, but this is just a guess.

What is my actual status? I just have a lot 3G constellations that react, I have to remove many of them because of symmetry or identical with other pattern and then have to apply a definition of 3GC to consider the resulting subset of collisions. I guess that there are many of them likely something between 100.000 and 1.000.000.
To get an impression all reactions resulting from the longest lasting 2G collision that results in nothing, I receive 13575 collisions, and as the reaction is not symmetric they should be all distinct. Unfortunately it is too large to upload all, but I uploaded the 352 resulting from the first 2G reaction.

So that's from my side for the moment.
Attachments
2glidercollision100.zip
(95.99 KiB) Downloaded 622 times

User avatar
dvgrn
Moderator
Posts: 10610
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Enumerating Three-Glider Collisions

Post by dvgrn » October 19th, 2017, 7:55 pm

Great summary -- thank you very much!
2718281828 wrote:I also like the general approach (that is proposed here) of taking the 71 different 2-glider collusion as a basis and add a third glider, the (A+B, C) approach.

However, I am not 100% sure if this covers all possible reactions. We could theoretically have a constellation of 3 gliders that react together (A,B,C), but each pair of two gliders (out of the three) do not react, e.g.

Code: Select all

x = 48, y = 7, rule = B3/S23
b2o18b2o19b2o$2o18b2o19b2o$2bo19bo20bo$4bobo26bobo9bobo$2bo2b2o15bo8bo
2b2o10b2o$2o3bo14b2o7b2o3bo11bo$b2o18b2o7b2o!
I think such pattern is not possible under [1] because we have only two different directions where the gliders can come from, but it must be proven.
Good point. I think this possibility can be disposed of fairly easily, though.

At least, a script could be written to exhaustively enumerate all (8*7*6) * (5 cells per glider) = 1680 ways that ON cells from three different gliders could possibly collaborate to produce a new ON cell. In each case, have the script move the gliders backwards by 10 cells (or whatever) and show that the candidate arrangement does not reappear after 40 ticks. That will mean that none of these arrangements pass criterion [1].

Even if we try to imagine a way for three gliders to interact, such that they jointly cause an overpopulation but separately fail to cause a birth, I think all of those possible cases are within easy reach of an exhaustive enumeration. A brute-force search should be able to provide the required proof with no possible worries about missed cases.

The search space is relatively small. It can't include any collisions where two of the gliders interact even a single tick before the third one, because no subset of two gliders is allowed to interact. So the script could just check all positions and orientations of three gliders where the centers are separated from each other by less than 5 cells. (If one glider is 5 cells away from both of the others, it can't interact on the next tick.)

That ends up being only something like

2 phases for the first glider
* 77 center locations for the second glider
* 4 phases for the second glider
* 4 orientations for the second glider
* average 200? (it varies) center locations for the third glider
* 4 phases for the third glider
* 4 orientations for the third glider

That looks like less than ten million possibilities, anyway, and many of them can be dismissed immediately because gliders' ON cells overlap. Should be an easy proof by exhaustive enumeration.
2718281828 wrote:What is my actual status? I just have a lot 3G constellations that react, I have to remove many of them because of symmetry or identical with other pattern and then have to apply a definition of 3GC to consider the resulting subset of collisions. I guess that there are many of them likely something between 100.000 and 1.000.000.
I was going to say that I thought the 2-glider mess by itself seems likely to produce over 100,000 distinct 3G collisions, but now I'm not so sure.

The four output gliders from the 2-glider mess do add a lot of weird cases, well outside of the normal active area:

Code: Select all

x = 114, y = 154, rule = LifeHistory
112.C$111.C$111.3C7$109.C$108.2C$108.C.C140$3A$2.A$.A!
On the other hand, I think the following two collisions should count as the same 3G reaction -- and this kind of thing is going to happen a lot:

Code: Select all

x = 208, y = 117, rule = LifeHistory
4.C117.C$3.C117.C$3.3C115.3C7$.C117.C$2C116.2C$C.C115.C.C102$206.A$
87.3A115.2A$87.A117.A.A$88.A!
The main pattern is still highly active at the time of collision, but the difference in the third glider's timing doesn't change anything interesting at all. After the third glider arrives, the reaction envelope of the glider+block collision and the remaining active pattern don't even overlap. The total effect is identical, cell for cell, with just a tiny timing difference.

Not sure there's an easy algorithm to combine those two cases, while still keeping other cases separate when they should be separate. -- Or do people think that the above should count as two separate 3Gs? They're certainly different in potentially important ways, if we're planning to add a fourth glider (!).

A really difficult case might be where a cell somewhere stays dead by overpopulation thanks to a spark thrown off by a deletion reaction like this one... where otherwise that same cell would still have stayed dead, but by underpopulation. Is that the same 3G collision, or two different collisions?
2718281828 wrote:To get an impression all reactions resulting from the longest lasting 2G collision that results in nothing, I receive 13575 collisions, and as the reaction is not symmetric they should be all distinct. Unfortunately it is too large to upload all, but I uploaded the 352 resulting from the first 2G reaction.
Maybe it's worth coming up with a more compact way of representing these collisions -- choice of 2G reaction plus a direction, lane and timing, possibly? A script could be written to produce the pattern from the description in a standard way.

The RLE patterns in the archive look like this at the moment --

Code: Select all

#CXRLE Pos=0,-2 Gen=284
x = 7, y = 11, rule = B3/S23
4bo$4bobo$bo2b2o$2bo$3o4$b3o$3bo$2bo!
-- so at least it wouldn't hurt anything to remove the first two lines, and maybe list 3G collisions in a text file with one chunk of RLE per line.

User avatar
2718281828
Posts: 738
Joined: August 8th, 2017, 5:38 pm

Re: Enumerating Three-Glider Collisions

Post by 2718281828 » October 21st, 2017, 2:54 am

I am still looking for a good way to classify and tabulating the collisions.
Especially the mentioned problem with the infinite sets, e.g.

Code: Select all

x = 129, y = 35, rule = B3/S23
17bo45bo30bo31bo$18bo45bo30bo31bo$16b3o43b3o28b3o29b3o3$17b3o43b3o28b
3o29b3o$19bo45bo30bo31bo$18bo45bo30bo31bo19$bo$b2o$obo44bo$47b2o$46bob
o29bo$78b2o$77bobo30bo$110b2o$109bobo!
make me struggle a bit.

However, I decided to start simple. So I am using the ash excluding escaping spaceships (e.g. after 20k generation everything has 'stabilized' except the infinite growth pattern(s?) ) as a classifier. Subclassifier is the population of the ash. And then we have the standard ashes, and these 'infinite sets' mentioned above. For the latter I am still looking for a solution to store them, likely something as ("ashpattern1! & ashpattern2!+(2a,0)" where a>=0 - the gliders then as something like "gliderA+B! & gliderC!+(2a,0)")
However, to present first results, I am showing only a list of hashes of the ashes that results from 2glider collisions excluding TL+G, the 3 B's and the 2 glider mess AND have a finite bounding box - esp. only these ashes where no spaceship escapes. The list is not cleaned for symmetries and rotations, so pattern might occur just mirrored/rotated. For the empty set I took representative pattern 'o!' and its hash.

I would need more upload-space to show e.g. the pattern of the ashes and a representative glider constellation that produces the ashes.
Attachments
bounded_ash_without_TLG_3B_2Gmess_hash_part2.csv.zip
(225.76 KiB) Downloaded 619 times
bounded_ash_without_TLG_3B_2Gmess_hash_part1.csv.zip
(230.07 KiB) Downloaded 612 times

User avatar
dvgrn
Moderator
Posts: 10610
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Enumerating Three-Glider Collisions

Post by dvgrn » January 26th, 2018, 1:38 am

In October, 2718281828 wrote:I would need more upload-space to show e.g. the pattern of the ashes and a representative glider constellation that produces the ashes.
After a little offline correspondence, 2718281828 just sent me a 130-megabyte ZIP file containing 464,746 RLE files divided between 71 folders.

Windows at least isn't too happy with this storage method -- it decompresses to only 44.8MB of actual files, but the size on disk is 1.77GB (!).

I took the liberty of converting all the data to a single text file containing the filenames and headerless RLE for each 3-glider collision. This compresses a lot better, down to less than 2.5MB:
3gdata.zip
almost half a million distinct 3-glider collisions enumerated by 2718281828 (probably not quite an exhaustive list)
(2.46 MiB) Downloaded 713 times
We could fit the key list of glider collisions in a much smaller space, e.g., using the glider recipe format from chris_c's still-life builder script.

The next step might be to sort this list in order of ash size, and maybe collect all the reasonable-size small constellations, so that some kind of lookup script could give instant answers about the existence or non-existence of a three-glider recipe for a given constellation, without having to re-run a half million collisions every time a new question is asked.

chris_c
Posts: 966
Joined: June 28th, 2014, 7:15 am

Re: Enumerating Three-Glider Collisions

Post by chris_c » January 26th, 2018, 8:14 am

dvgrn wrote: We could fit the key list of glider collisions in a much smaller space, e.g., using the glider recipe format from chris_c's still-life builder script.

The next step might be to sort this list in order of ash size, and maybe collect all the reasonable-size small constellations, so that some kind of lookup script could give instant answers about the existence or non-existence of a three-glider recipe for a given constellation, without having to re-run a half million collisions every time a new question is asked.
Dusting down my scripts for glider synthesis and applying them to this collection of patterns sounds like a nice well-defined task. I'll make this a goal in the near term and report back if I actually get this done.

hkoenig
Posts: 258
Joined: June 20th, 2009, 11:40 am

Re: Enumerating Three-Glider Collisions

Post by hkoenig » January 27th, 2018, 1:56 am

What's the meaning of the header on each line?
Windows at least isn't too happy with this storage method -- it decompresses to only 44.8MB of actual files, but the size on disk is 1.77GB (!).
You probably have a huge block size on that disk. Even though a file is only a few bytes long, the space allocated is probably something like 64k or more. Remember-- an OS filesystem usually doesn't make for an efficient database.

User avatar
dvgrn
Moderator
Posts: 10610
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Enumerating Three-Glider Collisions

Post by dvgrn » January 27th, 2018, 4:10 am

hkoenig wrote:You probably have a huge block size on that disk. Even though a file is only a few bytes long, the space allocated is probably something like 64k or more. Remember-- an OS filesystem usually doesn't make for an efficient database.
Yeah, that's why I wrote the converter to get the data out of that format as quickly as possible. I was impressed that a ZIP of the resulting text file could squeeze the size down to just a couple and a half megabytes, though -- isn't that only about five bytes per line? Seems like pretty darn good compression.

User avatar
2718281828
Posts: 738
Joined: August 8th, 2017, 5:38 pm

Re: Enumerating Three-Glider Collisions

Post by 2718281828 » January 27th, 2018, 10:46 am

Thanks dvgrn for data handling. On my (linux) system everything takes 239.4 MB uncompressed, not great but okay.
dvgrn wrote:
hkoenig wrote: Seems like pretty darn good compression.
It is not too surprising for me, even though you also saved my 'internal' strings (like 3g_0_1_0_5_5) which decode the position of the 3 gliders. 2 gliders are almost all the time at same position (just 71 options...), for the third glider we only require the information of the position (x and y and rotation) - so 5 byte seems to be reasonable.

Many 3 glider pattern are kind of redundant for practice purpose, as e.g. they are e.g. 3 2-glider options which evolve into a pi, so many reactions in the files are basically the same, for the pi case even 6 times (3 (2-glider options) x 2 because of symmetry).

Of course I ran all the pattern and looked at the ashes, the bounded ashes (excluding gliders) and the full ones. I did not find something really surprising so far. So no new (pseudo) still life, or (pseudo)-oscillator. Okay, I found some 3 glider synthesis for some methuselah (Acorn, Mango-glider collusion, ...) but they are not really of relevance. Also there is only one infinite growth pattern (the known one) and one synthesis for the switch engine. Also no 3 glider synthesis which gives 3 (or more) gliders. But there are a few ones which give e.g. 3 gliders and a block/blinker/hive.

I think the 3 glider collisions are most suitable for small constellations, and the synthesis of small methuselahs/induction coils and sparks. For some synthesis of still lifes/oscillator and spaceships I found small reductions like for the 7G Coe ship, 5G MWSS on MWSS or 13G copperhead I used my 3 glider collision collection.

When turning to 4 glider collisions, it might be first a good idea to create all collisions with a new glider and all bounded ashes. Maybe in future we can even enumerate all 4 glider collisions, but there are many. Still, all symmetric ones, are doable (maybe that's already done?). However, we first have to really define a 3-glider collision, because it is still an open point to deal in a good way with kick-backs and 'infinite collision classes'. I will comment on this in future.


When thinking about 3 and 4 glider collision I got a nice puzzle kind question: :?:

Given an integer N. Are 4 gliders sufficient to create a pattern with constant population N? (so stabilisation at population size N after a finite number generation)

I think yes, but I am not sure. However, I am sure that 5 gliders is sufficient, and 3 gliders does obviously not work.

chris_c
Posts: 966
Joined: June 28th, 2014, 7:15 am

Re: Enumerating Three-Glider Collisions

Post by chris_c » January 27th, 2018, 12:28 pm

2718281828 wrote: When thinking about 3 and 4 glider collision I got a nice puzzle kind question: :?:

Given an integer N. Are 4 gliders sufficient to create a pattern with constant population N? (so stabilisation at population size N after a finite number generation)

I think yes, but I am not sure. However, I am sure that 5 gliders is sufficient, and 3 gliders does obviously not work.
My guess is also yes. My reasoning is from taking the 3-glider infinite growth and firing a 4th glider at the head of the glider producing switch engine. Glider producing switch engines grow by 59 cells every 384 generations so if one of these 4G collisions ends up with population N then (hopefully) by moving the 4th glider back by 128 steps you will end up with a collision giving population N+59.

I wrote a crude script that:

1. Evolves the 3G infinite growth through 20000 generations
2. Adds in a 4th glider in a range of locations. (I tried to make sure to avoid the NW travelling glider that is not part of the GPSE but I might have made a mistake)
3. Does a crude search for the final population and inserts it modulo 59 into the set of already seen values.

The number of seen values reaches 59 a long time before the end of the loop so I am pretty confident that all values of N are achievable beyond a certain limit. To find what the limit is and to also account for all populations below the limit would be extra work of course.

Code: Select all

import golly as g

g.new('')

gl = g.parse('bo$2bo$3o!')

x0, y0 = -1600, -1535

g.putcells(g.parse('97bo$95b2o$96b2o69$4bo$3bo$3b3o$bo$2o$obo!'))
g.run(20000)
g.setpos(str(x0), str(y0))
g.setmag(2)
g.update()
g.setgen('0')

mod59pops = set()
tries = 0
for phase in range(4):
    gl = g.evolve(gl, 1)
    for x in range(128):
        for y in range(30):

            g.reset()

            g.run(1)
            g.putcells(gl, x0 - x, y0 - x - y)

            g.show(str((tries, len(mod59pops))))
            g.update()

            g.run(200)

            tries += 1
            n = 0
            constpops = 0
            lastpop = int(g.getpop())

            while n < 1000:
                g.run(1)
                n += 1
                if int(g.getpop()) == lastpop:
                    constpops += 1
                    if constpops >= 50:
                        mod59pops.add(lastpop % 59)
                        break
                else:
                    constpops = 0
                    lastpop = int(g.getpop())
Hmm... I just realised that checking for 50 generations of constant population may not be long enough to account for stray gliders that get fired back towards the ash near the origin.... oh well....

User avatar
dvgrn
Moderator
Posts: 10610
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Enumerating Three-Glider Collisions

Post by dvgrn » March 5th, 2018, 6:18 pm

chris_c wrote:Dusting down my scripts for glider synthesis and applying them to this collection of patterns sounds like a nice well-defined task.
Any luck getting the dust off those synthesis scripts? The format you used seems nice and compact, and maybe it could be extended by adding optional labels that can be safely ignored --

nesalvo= sesalvo= swsalvo= nwsalvo= lane= delay= transform=

It would be nice to have some Python and/or Lua code that knows how to find the zero lane, or zero timing for a given lane, in each direction. I can dig the details out of display_synth.js, but so far I've been avoiding it on the grounds that I'll get something wrong the first umpteen times I try a translation, and that will cause me Terrible Mental Anguish.
2718281828 wrote:When thinking about 3 and 4 glider collision I got a nice puzzle kind question: :?:

Given an integer N. Are 4 gliders sufficient to create a pattern with constant population N? (so stabilisation at population size N after a finite number generation)...
No, four gliders aren't enough -- but only because the rules seem to let me choose N=1 or N=2.
chris_c wrote:Glider producing switch engines grow by 59 cells every 384 generations so if one of these 4G collisions ends up with population N then (hopefully) by moving the 4th glider back by 128 steps you will end up with a collision giving population N+59.
...
Hmm... I just realised that checking for 50 generations of constant population may not be long enough to account for stray gliders that get fired back towards the ash near the origin.... oh well....
I tried out the script, and that uncertainty is easy enough to fix -- just do one extra VeryLongTime run at the end and make sure the population is still the same afterwards.

I added a secondary test that checks that the next nine (-128N,-128N) adjustments of each pattern do in fact produce a population that's 59N more than the original pattern's population. If that test fails, the collision in question doesn't get added to the toolkit.

The three-glider infinite-growth pattern starts getting repetitive around T=2500 or thereabouts, so I dialed back the collision to right about then, to get a lower minimum "safe" population above which any population can be trivially produced by a script.

The minimum script-compatible population is currently 822. It could probably be reduced to somewhere in the 700s with a more exhaustive search, and maybe into the 600s but clearly not the 500s -- the random ash before the switch engine appears is around 650 cells.

Here's the script. It will build a 4-glider recipe for any population that it knows a workable infinite family for:

Code: Select all

import golly as g

d = {0: ([-175, -140, -177, -139, -175, -139, -176, -138, -175, -138], 708),
     1: ([-179, -146, -181, -145, -179, -145, -180, -144, -179, -144], 709),
     2: ([-141, -113, -140, -112, -142, -111, -141, -111, -140, -111], 710),
     3: ([-172, -136, -174, -135, -172, -135, -173, -134, -172, -134], 711),
     4: ([-149, -114, -148, -113, -150, -112, -149, -112, -148, -112], 653),
     5: ([-179, -141, -181, -140, -179, -140, -180, -139, -179, -139], 713),
     6: ([-195, -165, -194, -164, -196, -163, -195, -163, -194, -163], 714),
     7: ([-162, -129, -161, -128, -163, -127, -162, -127, -161, -127], 656),
     8: ([-169, -142, -171, -141, -169, -141, -170, -140, -169, -140], 775),
     9: ([-147, -112, -146, -111, -148, -110, -147, -110, -146, -110], 658),
    10: ([-162, -126, -164, -125, -162, -125, -163, -124, -162, -124], 659),
    11: ([-135, -100, -134,  -99, -136,  -98, -135,  -98, -134,  -98], 778),
    12: ([-188, -149, -187, -148, -189, -147, -188, -147, -187, -147], 720),
    13: ([-167, -128, -169, -127, -167, -127, -168, -126, -167, -126], 662),
    14: ([-157, -124, -156, -123, -158, -122, -157, -122, -156, -122], 663),
    15: ([-161, -126, -160, -125, -162, -124, -161, -124, -160, -124], 664),
    16: ([-164, -133, -163, -132, -165, -131, -164, -131, -163, -131], 665),
    17: ([-174, -139, -173, -138, -175, -137, -174, -137, -173, -137], 725),
    18: ([-161, -125, -160, -124, -162, -123, -161, -123, -160, -123], 667),
    19: ([-164, -127, -163, -126, -165, -125, -164, -125, -163, -125], 668),
    20: ([-164, -126, -166, -125, -164, -125, -165, -124, -164, -124], 669),
    21: ([-155, -121, -154, -120, -156, -119, -155, -119, -154, -119], 670),
    22: ([-192, -159, -191, -158, -193, -157, -192, -157, -191, -157], 789),
    23: ([-162, -124, -164, -123, -162, -123, -163, -122, -162, -122], 672),
    24: ([-146, -111, -145, -110, -147, -109, -146, -109, -145, -109], 673),
    25: ([-164, -131, -163, -130, -165, -129, -164, -129, -163, -129], 674),
    26: ([-196, -159, -195, -158, -197, -157, -196, -157, -195, -157], 675),
    27: ([-191, -156, -190, -155, -192, -154, -191, -154, -190, -154], 676),
    28: ([-189, -150, -188, -149, -190, -148, -189, -148, -188, -148], 677),
    29: ([-197, -159, -196, -158, -198, -157, -197, -157, -196, -157], 678),
    30: ([-147, -111, -146, -110, -148, -109, -147, -109, -146, -109], 679),
    31: ([-197, -163, -196, -162, -198, -161, -197, -161, -196, -161], 680),
    32: ([-169, -133, -171, -132, -169, -132, -170, -131, -169, -131], 681),
    33: ([-197, -161, -196, -160, -198, -159, -197, -159, -196, -159], 682),
    34: ([-163, -128, -165, -127, -163, -127, -164, -126, -163, -126], 683),
    35: ([-172, -134, -174, -133, -172, -133, -173, -132, -172, -132], 684),
    36: ([-195, -158, -194, -157, -196, -156, -195, -156, -194, -156], 685),
    37: ([-165, -127, -167, -126, -165, -126, -166, -125, -165, -125], 686),
    38: ([-195, -166, -194, -165, -196, -164, -195, -164, -194, -164], 687),
    39: ([-194, -159, -193, -158, -195, -157, -194, -157, -193, -157], 688),
    40: ([-169, -130, -171, -129, -169, -129, -170, -128, -169, -128], 689),
    41: ([-190, -152, -189, -151, -191, -150, -190, -150, -189, -150], 690),
    42: ([-165, -124, -163, -124, -164, -123, -163, -123, -164, -122], 691),
    43: ([-167, -132, -169, -131, -167, -131, -168, -130, -167, -130], 692),
    44: ([-171, -131, -170, -130, -169, -130, -171, -129, -170, -129], 693),
    45: ([-146, -110, -145, -109, -147, -108, -146, -108, -145, -108], 694),
    46: ([-178, -144, -180, -143, -178, -143, -179, -142, -178, -142], 695),
    47: ([-176, -137, -178, -136, -176, -136, -177, -135, -176, -135], 696),
    48: ([-197, -162, -196, -161, -198, -160, -197, -160, -196, -160], 697),
    49: ([-165, -133, -164, -132, -166, -131, -165, -131, -164, -131], 698),
    50: ([-194, -158, -193, -157, -192, -157, -194, -156, -193, -156], 699),
    51: ([-157, -122, -156, -121, -158, -120, -157, -120, -156, -120], 641),
    52: ([-136, -103, -135, -102, -137, -101, -136, -101, -135, -101], 642),
    53: ([-164, -127, -166, -126, -164, -126, -165, -125, -164, -125], 702),
    54: ([-176, -140, -175, -139, -177, -138, -176, -138, -175, -138], 703),
    55: ([-134, -104, -133, -103, -135, -102, -134, -102, -133, -102], 822),
    56: ([-130,  -93, -129,  -92, -131,  -91, -130,  -91, -129,  -91], 646),
    57: ([-139, -106, -138, -105, -140, -104, -139, -104, -138, -104], 706),
    58: ([-197, -167, -196, -166, -198, -165, -197, -165, -196, -165], 707)}

# safelim = 822
initialrun = 2400
poptarget = g.getstring("Enter a population:","99999")
ipoptarget = int(poptarget)
# if ipoptarget<safelim: g.note("Not all populations under " + str(safelim) + " are supported.")

modval = ipoptarget % 59
g.addlayer()
g.putcells(g.parse('97bo$95b2o$96b2o69$4bo$3bo$3b3o$bo$2o$obo!'))
glider, basepop = d[modval]
diff = ipoptarget - basepop
offset = diff/59
if offset<0:
    g.note("Population " + poptarget + " is not in a known series.")
    g.exit()
g.putcells(g.transform(glider, -128*offset-initialrun/4, -128*offset-initialrun/4))
g.setstep(10)
So now we just need a list of 2-, 3-, or 4-glider collisions that produce all the populations in the range from 3 to 822. A good fraction of the ones above 650 are implied by the script above.

Here's my adjusted version of chris_c's original search script. If anyone wants to run it all night, change the X and Y ranges to cover the search space better and set it going. It takes somewhat under an hour with the current settings. When it's done, it will copy to the clipboard a dictionary containing the lowest population found for each of the 59 classes. This can be pasted straight into the other script above.

Code: Select all

import golly as g

g.new('')

initialrun = 2400
gl = g.parse('bo$2bo$3o!')

x0, y0 = -1600, -1535

x0, y0 = -160, -120 # for initialrun ~2400
x0, y0 = -128, -90 # for initialrun ~2400

g.putcells(g.parse('97bo$95b2o$96b2o69$4bo$3bo$3b3o$bo$2o$obo!'))
g.run(initialrun)
g.setpos(str(x0), str(y0))
g.setmag(2)
g.update()
g.setgen('0')
basepat = g.getcells(g.getrect())

mod59pops = set()
mod59pats = dict()
tries = 0
nummatches = 0
for phase in range(4):
    gl = g.evolve(gl, 1)
    for x in range(40):
        g.show (str(["Tries:",tries, "Matches:", nummatches, "Phase:", phase, "X: ",x]))
        g.update()
        for y in range(40):

            g.new("Test")
            g.putcells(basepat)
            glider = g.transform(gl, x0 - x, y0 - x - y)
            g.putcells(glider)

            g.run(20000)
            
            tries += 1
            n = 0
            constpops = 0
            lastpop = int(g.getpop())

            while n < 1000:
                g.run(1)
                n += 1
                newpop = int(g.getpop())
                if newpop == lastpop:
                    constpops += 1
                    if constpops >= 50:
                        g.run(100000)
                        if int(g.getpop()) == lastpop:
                            mpop = lastpop % 59
                            if mpop not in mod59pats or mod59pats[mpop][1]>mpop:
                                # do the test to make sure the series actually works
                                passes=1
                                for i in range(10):
                                    g.new("SecondaryTest")
                                    g.putcells(basepat)
                                    g.putcells(g.transform(glider,-128*i,-128*i))
                                    g.run(100000)
                                    newpop=int(g.getpop())
                                    if newpop!=lastpop+59*i:
                                        passes=0
                                        break
                                if passes==1:
                                    mod59pops.add(mpop)
                                    mod59pats[mpop] = (glider,lastpop)
                        break
                else:
                    constpops = 0
                    lastpop = newpop
        nummatches=len(mod59pats)
# better to let this run to completion, to find the solutions with lowest population
#        if nummatches == 59:
#            g.setclipstr(str(mod59pats))
#            g.exit()
g.setclipstr(str(mod59pats))

chris_c
Posts: 966
Joined: June 28th, 2014, 7:15 am

Re: Enumerating Three-Glider Collisions

Post by chris_c » March 6th, 2018, 10:04 am

dvgrn wrote:
chris_c wrote:Dusting down my scripts for glider synthesis and applying them to this collection of patterns sounds like a nice well-defined task.
Any luck getting the dust off those synthesis scripts? The format you used seems nice and compact, and maybe it could be extended by adding optional labels that can be safely ignored --

nesalvo= sesalvo= swsalvo= nwsalvo= lane= delay= transform=

It would be nice to have some Python and/or Lua code that knows how to find the zero lane, or zero timing for a given lane, in each direction. I can dig the details out of display_synth.js, but so far I've been avoiding it on the grounds that I'll get something wrong the first umpteen times I try a translation, and that will cause me Terrible Mental Anguish.
Sorry, I haven't looked at it. A few months ago I made a Very Silly backup blunder that meant I lost quite a bit of the code to do with this stuff. I still have the code that takes a bunch of RLE, splits each RLE into a bunch of syntheses and spits out the canonical synthesis string for each. Also there is still the display_synth.py script that can read the strings and piece them together to make a full synthesis.

Unfortunately I lost the code that takes a universe of synthstrings and outputs only the minimal set of strings needed to make a list of target objects in the most efficient way possible. This is not a great loss since it is a relatively easy implementation of Dijkstra's algorithm. It would have needed a rewrite anyway because the list of target objects was hard-coded as the list of 16-bit still lifes that I gave here. Instead I think the target objects should be any object that is not a constellation but I do not have (and never had) code that does this detection.

More annoying is that I lost my collection of converters. Most of these would have been "well-known" but quite a few were custom made improvements to existing converters that allowed completion of the 16-in-16 project. These now only exist if they happen to be mentioned somewhere in min_paths.txt.

The format for the synthesis strings is terse but the code to display them should not be complicated. Here is an absolutely minimal python script that can display a synthesis given a synthstring. It is just a stripped down version of display_synth.py but all of the extra stuff to make sure that the output and all intermediate steps are in the same orientation as the user requested has been removed. This means that the "output_code", "phase" and "transform" sections of the synthstrings are not looked at.

Code: Select all

import golly as g

GLIDERS = [(g.parse("3o$2bo$bo!", -2, 0), 1, -1),   #NE
           (g.parse("bo$2bo$3o!", -2, -2), 1, 1),   #SE
           (g.parse("bo$o$3o!", 0, -2), -1, 1),     #SW
           (g.parse("3o$o$bo!", 0, 0), -1, -1)]     #NW

def get_gliders(glider_lists, t):

    ret = []

    for (glider, vx, vy), glider_list in zip(GLIDERS, glider_lists):
        
        for lane, timing in glider_list:

            phase = (t + timing) % 4
            d = (t + timing) // 4

            ret += g.transform(g.evolve(glider, phase), lane + d * vx, d * vy)

    return ret

def simple_display_edge(edge):

    input_code, output_code, phase, glider_lists, transform = edge

    input_cells = decodeCanon(input_code) + get_gliders(glider_lists, 0)

    g.putcells(input_cells, 0, 0)    

def edge_from_string(s):

    t = s.split(";")

    glider_lists = []
    for gliders_string in t[3:7]:
        glider_list = []
        if gliders_string:
            gs = gliders_string.split(",")
            for i in range(0, len(gs), 2):
                glider_list.append((int(gs[i]), int(gs[i+1])))
        glider_lists.append(glider_list)

    transform = tuple(map(int, t[7].split(",")))

    return (t[0], t[1], int(t[2]), glider_lists, transform)    

chars = "0123456789abcdefghijklmnopqrstuvwxyz"

# Based on code by Arie Paap Sept. 2014
def decodeCanon(canonPatt):

    if not canonPatt or canonPatt[0] != 'x' or '_' not in canonPatt:
        return []
    
    blank = False
    x = y = 0
    clist = []
    
    for c in canonPatt[canonPatt.find("_")+1:]:
   
        if blank:
            x += chars.index(c)
            blank = False
        else:
            if (c == 'y'):
                x += 4
                blank = True
            elif (c == 'x'):
                x += 3
            elif (c == 'w'):
                x += 2
            elif (c == 'z'):
                x = 0
                y += 5
            else:
                v = chars.index(c)
                for i in range(5):
                    if v & (1 << i):
                        clist += [x, y+i]
                x += 1

    return clist

s = g.getstring("Enter string:", "xs10_0cp3z32;xs12_3pczw1246;0;;9,-46;7,-40;;0,6,1,0,0,-1")

g.setrule("Life")

simple_display_edge(edge_from_string(s))
EDIT: It looks like a simple explanation of the lane/timing is that a glider with (lane,timing)=(0,0) has 3 ON-cells in a single horizontal line and the cell (0,0) will be on in this generation and the next three and all lane numbers increase by 1 when shifting east.

EDIT2: Fixed typo simply->simple in the code sample.
Last edited by chris_c on March 6th, 2018, 1:57 pm, edited 1 time in total.

hkoenig
Posts: 258
Joined: June 20th, 2009, 11:40 am

Re: Enumerating Three-Glider Collisions

Post by hkoenig » March 6th, 2018, 1:12 pm

It looks like a simple explanation of the lane/timing is that a glider with (lane,timing)=(0,0) has 3 ON-cells in a single horizontal line and the cell (0,0) will be on in this generation and the next three and all lane numbers increase by 1 when shifting east.
A couple or three examples would also help in the validating of converters in other languages-- the string and its corresponding RLE. (Unit tests are your friends...)

Did I get even close to getting these (encoded by hand) right?

nw (0,0) ne(-2,-1)

Code: Select all

x=7, y=3, h=-4, v=0
2o2b3o$b2obo$o4bo!
nw(4,0) ne(2,-1)

Code: Select all

x=7, y=3
2o2b3o$b2obo$o4bo!
sw(3,6) sw(11,33) ne(6,-16)
0;xp15_4r4z4r4;0;6,-16;;3,6,11,33;;

Code: Select all

x=7, y=10
2bo$2bobo$2b2o2$3o$2bo$bo$4bobo$4b2o$5bo!

In the code you posted, you have the line in "edge_from_string":

for gliders_string in t[3:7]:

I'm not familiar with Python, but shouldn't that be [3:6]? Because later [7] is used for the transform.

User avatar
dvgrn
Moderator
Posts: 10610
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Enumerating Three-Glider Collisions

Post by dvgrn » March 6th, 2018, 1:23 pm

hkoenig wrote:In the code you posted, you have the line in "edge_from_string":

for gliders_string in t[3:7]:

I'm not familiar with Python, but shouldn't that be [3:6]? Because later [7] is used for the transform.
Nah, that's standard Python. [3:7] is a four-item slice of the list, including the item with index 3, but not including the item with index 7.
>>> word = 'Python'
>>> word[0:2] # characters from position 0 (included) to 2 (excluded)
'Py'
>>> word[2:5] # characters from position 2 (included) to 5 (excluded)
'tho'

Note how the start is always included, and the end always excluded. This makes sure that s[:i] + s[i:] is always equal to s:

>>> word[:2] + word[2:]
'Python'
>>> word[:4] + word[4:]
'Python'
Also this way the length of the slice is the difference between the start and end values. You can think of the indices as pointing to the gaps between items, rather than the items themselves -- numbered starting at zero for the gap before the first item... anyway, Python is very consistent about it, so once you've been brainwashed enough it makes perfect sense.

chris_c
Posts: 966
Joined: June 28th, 2014, 7:15 am

Re: Enumerating Three-Glider Collisions

Post by chris_c » March 6th, 2018, 2:45 pm

hkoenig wrote:
It looks like a simple explanation of the lane/timing is that a glider with (lane,timing)=(0,0) has 3 ON-cells in a single horizontal line and the cell (0,0) will be on in this generation and the next three and all lane numbers increase by 1 when shifting east.
A couple or three examples would also help in the validating of converters in other languages-- the string and its corresponding RLE. (Unit tests are your friends...)

Did I get even close to getting these (encoded by hand) right?

nw (0,0) ne(-2,-1)

Code: Select all

x=7, y=3, h=-4, v=0
2o2b3o$b2obo$o4bo!
nw(4,0) ne(2,-1)

Code: Select all

x=7, y=3
2o2b3o$b2obo$o4bo!
sw(3,6) sw(11,33) ne(6,-16)
0;xp15_4r4z4r4;0;6,-16;;3,6,11,33;;

Code: Select all

x=7, y=10
2bo$2bobo$2b2o2$3o$2bo$bo$4bobo$4b2o$5bo!
The first two look correct. I guess the last one should be sw(12,33). These are synthstrings that produce your RLE above:

Code: Select all

0;0;0;-2,-1;;;0,0;0,0,1,0,0,1
0;0;0;2,-1;;;4,0;0,0,1,0,0,1
0;xp15_4r4z4r4;0;6,-16;;3,6,12,33;;0,0,1,0,0,1
I added "0,0,1,0,0,1" as the transform on every line because that is the identity transform in Golly. a,b,c,d,e,f is the transformation that sends (x,y) -> (a + c*x + d*y, b + e*x + f*y).
In the code you posted, you have the line in "edge_from_string":

for gliders_string in t[3:7]:

I'm not familiar with Python, but shouldn't that be [3:6]? Because later [7] is used for the transform.
dvgrn's explanation is correct here (thanks!).

Now let me explain what the transform and phase sections of the string are supposed to do. It is intended that the following two procedures should result in identical patterns when run to infinity.

A) Draw the constellation defined by the first apgcode. Draw in the gliders (according to the method specified in the code ;)).

B) Draw the constellation defined by the second apgcode. Evolve by phase generations. Apply golly.transform(transform) to the pattern.

Code to implement procedures A and B and display the results 100 cells apart is here:

Code: Select all

def simple_display_edge2(edge):

    input_code, output_code, phase, glider_lists, transform = edge

    input_cells = decodeCanon(input_code) + get_gliders(glider_lists, 0)
    output_cells = g.evolve(decodeCanon(output_code), phase)

    g.putcells(input_cells, 100, 0)
    g.putcells(output_cells, *transform)
The synthstring "xs7_178c;xp2_70ggzw12hu0ok8;1;7,-95;-13,-12,-5,-44;;-8,-93;-6,10,1,0,0,-1" should be a decent test case for this behaviour.

EDIT: Description of procedures A and B and the simple_display_edge2 code was wrong originally.

Post Reply