ConwayLife.com - A community for Conway's Game of Life and related cellular automata
Home  •  LifeWiki  •  Forums  •  Download Golly

Slow Salvo Gliders

For discussion of specific patterns or specific families of patterns, both newly-discovered and well-known.

Slow Salvo Gliders

Postby The Turtle » May 9th, 2015, 12:30 pm

I've been trying to find a slow salvo that when it hits a block, it produces a glider, then restores the block in the original location. Here are some examples.
x = 1315, y = 198, rule = B3/S23
1175b2o$695b2o477b2o$b2o158b2o158b2o208b2o158b2ob2o145b2o178b2o148b2o
3bo$b2o158b2o158b2o208b2o158b2o3bo144b2o178b2o148b2o2$bo159bo159bo209b
o309bo179bo$2o158b2o158b2o208b2o308b2o178b2o$obo157bobo157bobo207bobo
307bobo177bobo160b2o$1182b2o$709bo474bo$546b2o160b2o$545b2o161bobo325b
2o$547bo487b2o$712bo324bo$711b2o327b2o$13b2o696bobo325b2o$12b2o1027bo$
14bo316bo519bo$330b2o518b2o343bo$169b2o159bobo517bobo341b2o$168b2o561b
o462bobo$21b2o147bo554b3o2b2o$20b2o151b2o550bo4bobo$22bo149b2o552bo$
174bo$337bo519bo$336b2o518b2o$336bobo517bobo184b2o$1042b2o$192bo851bo$
191b2o$34b2o155bobo$34bobo682b2o$34bo683b2o326b2o$199b2o365b3o151bo
324b2o$199bobo364bo480bo4b3o$180b2o17bo367bo160b3o321bo157bo$180bobo
545bo324bo155b2o$180bo169b2o377bo140b2o337bobo$46bo3b2o297b2o518b2o$
45b2o3bobo298bo519bo$45bobo2bo129b2o$179b2o$181bo$44b2o532b3o635bo$44b
obo531bo636b2o$44bo534bo635bobo$367b3o517b3o$367bo519bo186bo$368bo519b
o184b2o$1073bobo3$580b3o$580bo$581bo$1065bo$1064b2o163b2o$1064bobo161b
2o$1230bo7$45b3o544b3o481b3o167b3o$45bo546bo483bo169bo$46bo546bo483bo
169bo$208b2o$207b2o$209bo$1084b3o$749b2o333bo$748b2o335bo$598b3o149bo$
598bo503bo$599bo501b2o$83b3o1015bobo$83bo517bo$84bo515b2o503b2o$217b3o
158b3o219bobo501b2o$217bo160bo727bo$218bo160bo380b3o141b3o$760bo143bo$
761bo143bo$82b2o1010bo$81b2o153b2o855b2o$83bo152bobo680b2o172bobo$236b
o531b3o148bobo$86bo133b2o546bo150bo$85b2o133bobo390bo155bo$85bobo132bo
391b2o$239b2o371bobo$226b2o11bobo$225b2o12bo$227bo559b3o128bo$787bo
129b2o348b3o$244bo543bo128bobo347bo$243b2o366b2o655bo$243bobo365bobo$
611bo2$615b2o158bo$615bobo156b2o$415b3o197bo158bobo$415bo$416bo4$925b
2o$924b2o11b2o$627b2o297bo9b2o$626b2o310bo$628bo301bo$929b2o$788b2o
139bobo343b3o$787b2o486bo$635b2o152bo486bo$634b2o303bo$636bo301b2o$
788b3o147bobo$788bo$789bo$941b2o$940b2o$942bo2$1291bo$1290b2o$646b2o
642bobo$645b2o$647bo5$1305b3o$1305bo$1306bo4$1298b2o$984bo312b2o$448bo
534b2o314bo$447b2o534bobo318bo$447bobo853b2o$1303bobo2$1312b2o$670b2o
640bobo$669b2o641bo$671bo7$455b2o$454b2o11b2o$456bo9b2o$468bo$460bo$
459b2o$459bobo3$469bo$468b2o$468bobo3$471b2o$470b2o$472bo15$726b2o$
725b2o$727bo3bo$514bo215b2o$513b2o215bobo$513bobo!

The least number of gliders I have so far is 11. This probably can be improved.
Also, I need optimal solutions for gliders of each color.
Can you help me?
Only two things are constant: change and the speed of light.
User avatar
The Turtle
 
Posts: 102
Joined: May 6th, 2015, 8:14 pm
Location: Chicago, Illinois

Re: Slow Salvo Gliders

Postby dvgrn » May 9th, 2015, 2:21 pm

The Turtle wrote:I've been trying to find a slow salvo that when it hits a block, it produces a glider, then restores the block in the original location. Here are some examples... The least number of gliders I have so far is 11. This probably can be improved.

Six gliders is enough for one of the two output colors:

x = 57, y = 55, rule = LifeHistory
2E2.3A$2E2.A$5.A6$19.3A$19.A$20.A12$24.3A$24.A$25.A8$37.2A$36.2A$38.A
8$43.3A$43.A$44.A8$54.3A$54.A$55.A!

The Turtle wrote:Also, I need optimal solutions for gliders of each color.

I adapted the above from the ninth recipe in the following list, which is extracted from a much larger list of block-to-two-block recipes, which in turn is a subset of almost a quarter million block-to-constellation slow-salvo recipes. (Those 236,000 recipes were generated by truncating a table of block-move recipes, so unfortunately even that isn't quite an exhaustive list of 8-glider slow-salvo recipes -- but it's good enough for most purposes.)

b0  ,0  m-14,2  :E9 E23 E7 E-41 E-11 E-27
b0  ,0  m-10,-5 :E9 E15 O-3 O19 E3 O7
b0  ,0  m-4 ,4  :E9 E15 E-1 O-11 O7 O-5
b0  ,0  m-4 ,15 :E-9 E-7 O-31 O-7 O1 E5
b0  ,0  m-3 ,5  :E9 E3 E-1 E9 O-7 O13
b0  ,0  m-2 ,2  :E9 E15 E15 O17 O25 E41
b0  ,0  m-2 ,2  :E9 E15 E15 O17 O37 E15
b0  ,0  m-2 ,10 :E-9 E11 E-3 O-3 E-21 E-5
b0  ,0  m0  ,11 :E9 E9 O-15 O9 E3 E5
b0  ,0  m7  ,18 :E-9 E-7 E-21 O-7 O1 E5

b0  ,0  m1  ,24 :E-9 E-7 O-39 O-37 O-7 O1 E5
b0  ,0  m2  ,17 :E-9 E-15 O-31 O-39 E-41 E-27 O-3
b0  ,0  m4  ,27 :E-9 E-7 O-11 O5 O-11 O9 O-51
b0  ,0  m5  ,26 :E-9 E-7 O-11 O5 O-11 O9 O-37
b0  ,0  m17 ,28 :E-9 E-17 O11 O-3 O5 O5 O27 O-29

To build one of these recipes, run build-EO-lane-slow-salvo.py. They use Paul Chapman's quarter-diagonal lane measurements, so you can get the mirror-image recipe by negating all the lane numbers -- but there are no even lane numbers (or at least gliders can't run on them... something like a 295P5H1V1 could run on even lanes but not odd ones.)

There are six-glider recipes for a "spare block" of either color, so at worst we could do block-to-2-block (6 gliders) plus spare-block-to-glider (4 gliders). But probably a careful inspection of the above recipes will turn up something a few gliders cheaper than that.

Also, I seem to recall chris_c ran some searches along these lines, several months back. I don't remember if this particular question was answered then -- but it should be easy to adapt that script to do an exhaustive search for a slow invariant turner recipe for both glider colors.

EDIT: Does the invariant target object have to be a block, or could it be some other stable object -- a beehive or a honeyfarm, let's say? Probably the total cost will come out about the same, but there might be a lucky cheaper recipe out there for one target or another.
User avatar
dvgrn
Moderator
 
Posts: 5820
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Slow Salvo Gliders

Postby The Turtle » May 9th, 2015, 2:45 pm

How about P1 slow salvos?
I don't know how to run Python or Perl scripts, so I can't run your scripts in Golly. (I hope I will know how to before next year)
Only two things are constant: change and the speed of light.
User avatar
The Turtle
 
Posts: 102
Joined: May 6th, 2015, 8:14 pm
Location: Chicago, Illinois

Re: Slow Salvo Gliders

Postby dvgrn » May 9th, 2015, 3:31 pm

The Turtle wrote:How about P1 slow salvos?
I don't know how to run Python or Perl scripts, so I can't run your scripts in Golly. (I hope I will know how to before next year)

Hmm, P1 slow salvos are going to be a bit more expensive. The most recent investigation was several years ago, resulting in Paul Chapman's P1 slow-salvo block-move table. Unfortunately it looks like the old Glue output code just shows the shortest recipe for each (X, Y) move, and (0,0) has a zero-glider recipe -- no way to know what else it found.

There's an invariant block recipe with eight gliders (I looked up "-2,-1" in Paul's table) but I'm not sure if two more gliders can be added to get a clean glider output, to beat your current 11-glider recipe. Half of the gliders are just cleanup gliders, so the odds aren't too bad:

x = 47, y = 43, rule = B3/S23
2o$2o3b3o$5bo$6bo4$20b3o$20bo$21bo4$21b3o$21bo$22bo2$36b3o$36bo$37bo$
40b3o$40bo$41bo8$34b3o$34bo$35bo5$34b3o$34bo$35bo$44b3o$44bo$45bo!

So this would need a different adaptation of chris_c's search code, and it would probably find solutions in the 8-10 glider range. Because the search tree has a much lower branching factor at P1, this will still be within pretty easy reach of an exhaustive search.

For most people -- well, people with administrative access to their computer, at least -- installing Python is somewhat less than five minutes of work. You just have to know whether you've downloaded a 32-bit or 64-bit version of Golly, and install a matching 32-bit or 64-bit version of Python.

If you're lucky, the Python scripts that come with Golly will Just Work after that. If not, you could copy and post here whatever error messages you see...!
User avatar
dvgrn
Moderator
 
Posts: 5820
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Slow Salvo Gliders

Postby The Turtle » May 9th, 2015, 3:36 pm

dvgrn wrote:You just have to know whether you've downloaded a 32-bit or 64-bit version of Golly, and install a matching 32-bit or 64-bit version of Python.

How can I tell what version of Golly I have?
Only two things are constant: change and the speed of light.
User avatar
The Turtle
 
Posts: 102
Joined: May 6th, 2015, 8:14 pm
Location: Chicago, Illinois

Re: Slow Salvo Gliders

Postby dvgrn » May 9th, 2015, 4:47 pm

The Turtle wrote:How can I tell what version of Golly I have?

Well, if you just downloaded the version pointed to by golly.sourceforge.net or the Sourceforge project page, you would have gotten the 32-bit version by default -- a download file name like "golly-2.6-win.zip". If your installer or ZIP file is called something like "golly-2.7b2-win64.zip" (or an equivalent name if you're using an operating system other than Windows) then you have the 64-bit version.

The actual version number will be under Help > About Golly, of course, but that unfortunately doesn't give you that key information about 32 bits versus 64 bits.

EDIT: And maybe I should say: you don't really need the builder Python script to translate those recipes, of course -- it's just easier that way.

An "E9" or "E-9" is the first glider hitting the block and turning it into a honeyfarm. If the next number is 2 away from the last one -- E11 following E9, let's say -- then move the next glider over one more lane away from the block's original zero lane. "E" versus "O" defines whether the glider should be in an even or odd phase... so since you're interested in P1 slow salvos, maybe you're not interested in all these recipes with O's in them anyway.
User avatar
dvgrn
Moderator
 
Posts: 5820
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Slow Salvo Gliders

Postby The Turtle » May 10th, 2015, 5:16 pm

Should I run the Python scripts in Python or in Golly?
Also, do I need a specific version number of Python?
(I still don't have Python)

EDIT:
I have Golly 2.6.
Only two things are constant: change and the speed of light.
User avatar
The Turtle
 
Posts: 102
Joined: May 6th, 2015, 8:14 pm
Location: Chicago, Illinois

Re: Slow Salvo Gliders

Postby dvgrn » May 10th, 2015, 5:35 pm

The Turtle wrote:Should I run the Python scripts in Python or in Golly?

Most Python scripts quoted or described on the forums, including the ones mentioned above, are meant to be run from inside Golly -- File > Run Script.

The Turtle wrote:Also, do I need a specific version number of Python?
(I still don't have Python)

That's a really good question, and I should have thought to answer it before now. On the Python.org downloads page, you'll see a button labeled "Download Python 2.7.9". Clicking on that will take you straight to the correct installer file for 32-bit Python 2.7.9, which matches the 32-bit Windows version of Golly that SourceForge recommends by default.

So if all you know is that you're using Golly on Windows, that's the button to choose. Definitely don't try Python 3.x -- that's a major new version of Python, and Golly hasn't taken the big step to be compatible with it yet...!

If you have some other platform and/or version of Golly, such as the 64-bit version, then you'll want to download the matching version of Python 2.7.9 from the Python 2.7.9 download page.
User avatar
dvgrn
Moderator
 
Posts: 5820
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Slow Salvo Gliders

Postby The Turtle » May 10th, 2015, 5:59 pm

I installed Python today. Everything is working fine. (so far)
How do I install Perl?
Only two things are constant: change and the speed of light.
User avatar
The Turtle
 
Posts: 102
Joined: May 6th, 2015, 8:14 pm
Location: Chicago, Illinois

Re: Slow Salvo Gliders

Postby dvgrn » May 10th, 2015, 6:25 pm

The Turtle wrote:I installed Python today. Everything is working fine. (so far)
How do I install Perl?

For Golly purposes, you don't need to worry about Perl. Pretty much all of the available Perl scripts have Python equivalents -- and the reverse is not true. It turned out that Perl never got to be particularly popular as a scripting language for Golly.

If you do want to try Perl out, you can use this link to download an ActivePerl installer.

I actually don't know whether the very latest Perl (5.20 or 5.18) plays nicely with the current version of Golly, though. It might be safer to get hold of a 5.12 or 5.14 Perl installer, but it looks as if those are only available for download as part of the Business Edition or Enterprise Edition.

Has anyone successfully done a 5.18+ Perl installation lately? Are there any avoidable stumbling blocks along the way?
User avatar
dvgrn
Moderator
 
Posts: 5820
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Slow Salvo Gliders

Postby The Turtle » May 10th, 2015, 6:31 pm

I have two questions:
1. What does the Glue program do?
2. Where can I download the Glue program?
Only two things are constant: change and the speed of light.
User avatar
The Turtle
 
Posts: 102
Joined: May 6th, 2015, 8:14 pm
Location: Chicago, Illinois

Re: Slow Salvo Gliders

Postby dvgrn » May 10th, 2015, 7:00 pm

The Turtle wrote:I have two questions:
1. What does the Glue program do?
2. Where can I download the Glue program?

Glue, versions 1 and 2, were both fairly highly optimized slow-salvo search programs written by Paul Chapman several years ago. They produced a lot of the slow-salvo search results linked to earlier in this thread.

Unfortunately, Glue was written in an archaic version of Smalltalk, and never got past the alpha stage, so it doesn't run easily on any version of Windows beyond Windows 98, I think. That makes it not very useful to do new searches.

A recent equivalent is chris_c's Python search script, which can be found here. It won't need too many changes to allow it to find invariant slow-salvo glider outputs, though if you're just starting out with Python you may find it a bit tricky to figure out where to begin.

I can probably find a little time to make the necessary script changes next weekend, if no one else gets around to it first.
User avatar
dvgrn
Moderator
 
Posts: 5820
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Slow Salvo Gliders

Postby The Turtle » May 11th, 2015, 8:45 pm

In my original question, it was about P1 slow salvos hitting blocks.
How about P1 slow salvos hitting beehives (and the like)?
Only two things are constant: change and the speed of light.
User avatar
The Turtle
 
Posts: 102
Joined: May 6th, 2015, 8:14 pm
Location: Chicago, Illinois

Re: Slow Salvo Gliders

Postby simsim314 » May 12th, 2015, 3:27 am

The Turtle wrote:How about P1 slow salvos hitting beehives (and the like)?


From my experience with slow salvo, hitting "only" beehives will be worse than block for simple reason - beehives are more rare than blocks, so you will simply get less recipes per same depth.

Saying that we could have several "bases", and this would obviously be better than just having only block as a base. Having N bases will require NxN recipes per depth, which is kinda complicating things, but should work.
User avatar
simsim314
 
Posts: 1702
Joined: February 10th, 2014, 1:27 pm

Re: Slow Salvo Gliders

Postby dvgrn » May 12th, 2015, 6:09 am

simsim314 wrote:
The Turtle wrote:How about P1 slow salvos hitting beehives (and the like)?

From my experience with slow salvo, hitting "only" beehives will be worse than block for simple reason - beehives are more rare than blocks, so you will simply get less recipes per same depth.

A honeyfarm target might be the only exception to the rule that everything is rarer than a block. Any set of recipes with an invariant block can be converted to an equivalent set with an invariant honeyfarm -- usually by simply moving the first glider in each recipe to the end. But there are quite a few ways of producing a honeyfarm that don't go through a block stage, so there might possibly be some small efficiency gains there.

simsim314 wrote:Saying that we could have several "bases", and this would obviously be better than just having only block as a base. Having N bases will require NxN recipes per depth, which is kinda complicating things, but should work.

It depends on what these P1 slow invariant elbows are being used for, doesn't it? Multiple bases probably won't give much advantage if output gliders always have to be on exactly the same lanes, one lane of each color.

@Turtle: So where are these reflected gliders going to end up, exactly? And where are the P1 input gliders coming from, and why can't they be P2?

So far, universal constructor designs have generally included recipes that move the target block forward and backward, as the simplest way to get 90-degree glider outputs on different lanes. The recent exception to this is simsim314's "armless" universal constructors, which are still somewhat in the experimental stage but have been used, for example, in chris_c's rather awe-inspiring HBK gun.
User avatar
dvgrn
Moderator
 
Posts: 5820
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Slow Salvo Gliders

Postby The Turtle » May 12th, 2015, 4:49 pm

More questions...
What are the smallest slow salvo gliders, including P2?
How about LWSS's, MWSS's, and HWSS's?
Only two things are constant: change and the speed of light.
User avatar
The Turtle
 
Posts: 102
Joined: May 6th, 2015, 8:14 pm
Location: Chicago, Illinois

Re: Slow Salvo Gliders

Postby The Turtle » May 12th, 2015, 4:57 pm

dvgrn wrote:So where are these reflected gliders going to end up, exactly?

I wanted to make something where a salvo hits a block, it produces another salvo, which in turn hits another block, and etc.
dvgrn wrote:And where are the P1 input gliders coming from, and why can't they be P2?

It makes things easier. I could do it with P2, if I wanted to.
AND... more questions.
Glue's slow salvo table produces only P1 results. How about P2 results? Did anyone put together a list?
Only two things are constant: change and the speed of light.
User avatar
The Turtle
 
Posts: 102
Joined: May 6th, 2015, 8:14 pm
Location: Chicago, Illinois

Re: Slow Salvo Gliders

Postby simsim314 » May 12th, 2015, 5:03 pm

dvgrn wrote: Any set of recipes with an invariant block can be converted to an equivalent set with an invariant honeyfarm -- usually by simply moving the first glider in each recipe to the end.


It's not exactly correct. Many recipes start from moving block by (2,1). Of course you could add this movement to the end of the previous recipe as well, but this could make the recipes a bit longer than recipes with only block. And because we're limited by memory in the depth that we can search for recipes, so always starting with HF will cause us actually lose some of the recipes, that we wouldn't lose if we would start from block. This is obviously "sad truth" caused by limited resources, if we could have recipes of any length there would be no difference between HF and block (obviously).

As for the second comment: I really don't see why is it important for what purpose we use block as base? As using more bases will simply include all options with block, and many other options as well. Even if you don't need all other options, you can't get worse than recipes with block alone - you can get only better or equal. The only disadvantage is that you need more memory, and more "look ahead" functionality, because it's possible to see three steps ahead and get something very efficient, but then get stuck with "bad base" for the next SL. Anyway mathematically speaking, having more bases is obviously can't be worse than block alone, because more bases include all the options of block alone as well.
User avatar
simsim314
 
Posts: 1702
Joined: February 10th, 2014, 1:27 pm

Re: Slow Salvo Gliders

Postby dvgrn » May 12th, 2015, 5:24 pm

The Turtle wrote:
dvgrn wrote:So where are these reflected gliders going to end up, exactly?

I wanted to make something where a salvo hits a block, it produces another salvo, which in turn hits another block, and etc.

Have a look at this posting, then. There's a perfect challenge pattern in there for you (!).

I think that in that case, you're going to want an adjustable elbow, not an invariant turner reaction. That is, the block-or-whatever shouldn't necessarily have to stay in exactly the same spot, as you originally described it -- because you'll want to fire 90-degree gliders on various different lanes, not the same lane every time.

It makes more sense now that you wanted output gliders of two different colors.

To run a series of slow, slow^2, slow^3... slow^N elbows, you'd have to be able to compile a slow recipe so that it works around a slow^2 corner, then compile that recipe into a new recipe that fires the slow^2 recipe around the slow^3 corner, and so on. It will be quite impressive to see how many gliders would be needed to fire even just a single glider from the fourth slow elbow.

dvgrn wrote:Glue's slow salvo table produces only P1 results. How about P2 results? Did anyone put together a list?

The post that follows the above link has an enormous collection of P2 block-move recipes attached to it. Combine either P2 or P1 block-moves with the 5-glider slow glider-turning recipe from the previous post (which is actually P1) and you should have a toolkit that can build anything you want around any number of corners.
User avatar
dvgrn
Moderator
 
Posts: 5820
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Slow Salvo Gliders

Postby The Turtle » May 12th, 2015, 7:32 pm

dvgrn wrote:Combine either P2 or P1 block-moves with the 5-glider slow glider-turning recipe from the previous post (which is actually P1) and you should have a toolkit that can build anything you want around any number of corners.

If I combine Glue's block-move table with the 5-glider slow salvos, it still has 12 gliders.
x = 58, y = 68, rule = B3/S23
4b2o$2ob2o$2o3bo12$19b2o$11b2o5b2o$10b2o8bo$12bo3$27b2o$26b2o$28bo3$
26b3o$26bo$27bo6$24b3o$24bo$25bo12$32b2o$32bobo4b2o$32bo6bobo$39bo4$
43b3o$43bo$44bo4b3o$49bo$50bo$55b3o$55bo$56bo4$53b3o$53bo$54bo!

The good thing is that the glider is a different color than my 11-glider version.
Does anyone have a program that finds the optimal solution for P1 and P2 slow salvos hitting a block, making a glider, and restoring the block?
Only two things are constant: change and the speed of light.
User avatar
The Turtle
 
Posts: 102
Joined: May 6th, 2015, 8:14 pm
Location: Chicago, Illinois

Re: Slow Salvo Gliders

Postby dvgrn » May 12th, 2015, 7:50 pm

The Turtle wrote:The good thing is that the glider is a different color than my 11-glider version.
Does anyone have a program that finds the optimal solution for P1 and P2 slow salvos hitting a block, making a glider, and restoring the block?

Yes. Almost. I gave you the link to chris_c's Python-script search program a few messages up, which can easily be adapted to that task.

However... why do you want to restore the block to its exact original location every time? Seems to me that that will almost always be a waste of gliders, because then you'll have to move the block somewhere else anyway to fire the next glider on some different lane.

Just getting a block back anywhere nearby will let you continue with producing the next 90-degree glider. Just need to work out the most efficient way to produce each possible sequence of two lanes, or three lanes, or maybe more... and pick out some efficient sideways block moves for whenever the target slow-elbow block drifts too far to one side or the other. (Whoever is building the toolkit gets to define what "too far" means.)
User avatar
dvgrn
Moderator
 
Posts: 5820
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Slow Salvo Gliders

Postby The Turtle » May 13th, 2015, 4:49 pm

dvgrn wrote:Yes. Almost. I gave you the link to chris_c's Python-script search program a few messages up, which can easily be adapted to that task.

I have chris_c's program, but I don't get what it does. (I didn't learn Python yet) There is a slow salvo hitting a block, and at the end, a glider coming in a different direction than the salvo produces a glider. What purpose does that accomplish?
dvgrn wrote:However... why do you want to restore the block to its exact original location every time? Seems to me that that will almost always be a waste of gliders, because then you'll have to move the block somewhere else anyway to fire the next glider on some different lane.

I haven't thought about that.
I see your reasoning, but when I put together the pattern, it will make it easier for me to count glider lanes and position things accordingly.
Only two things are constant: change and the speed of light.
User avatar
The Turtle
 
Posts: 102
Joined: May 6th, 2015, 8:14 pm
Location: Chicago, Illinois

Re: Slow Salvo Gliders

Postby dvgrn » May 13th, 2015, 6:06 pm

The Turtle wrote:
dvgrn wrote:Yes. Almost. I gave you the link to chris_c's Python-script search program a few messages up, which can easily be adapted to that task.

I have chris_c's program, but I don't get what it does. (I didn't learn Python yet) There is a slow salvo hitting a block, and at the end, a glider coming in a different direction than the salvo produces a glider. What purpose does that accomplish?

As it's currently written, it's looking for one-time turners and splitters that can be cheaply constructed by gliders, where the input and output gliders may come from any direction. A database of these results would allow us to build various useful toolkits.

For example, using this database, a script could build a chain of still lifes that would take an input glider at (0,0) and produce an output glider at (X,Y), going in direction D, at any time [T, T+1, T+2...T+N]... for any N above some minimum T. This search program allows an easy-to-construct chain to be designed, no matter what direction the actual input and output gliders will be coming from.

This definitely is not what you want, as it stands. However, the code is simple enough that a while back I was able to modify it very easily to look for output spaceships (LWSS, MWSS, HWSS) or multiple output gliders (splitters). When/if I get a chance, I can set a search running for invariant turners and find a guaranteed minimum recipe (given a choice of invariant targets).

The Turtle wrote:
dvgrn wrote:However... why do you want to restore the block to its exact original location every time? Seems to me that that will almost always be a waste of gliders, because then you'll have to move the block somewhere else anyway to fire the next glider on some different lane.

...I see your reasoning, but when I put together the pattern, it will make it easier for me to count glider lanes and position things accordingly.

You're also worried about keeping the recipes short, though. Between the various block-move tables and glider turner reactions, you already have everything you need to do a slow^N construction around multiple elbows -- just use your 11- and 12-glider invariant turner recipes.

If minimizing the number of gliders is important, though, it's almost certainly better to

  • 1) use the block-move table to find the cheapest place along your target output lane to move your elbow block to. There's a whole line of possible locations that will all work equally well, so you can just take the shortest recipe.
  • 2) use the 5-glider turner recipe to produce the glider you want.
  • Repeat #1 and #2 until you've fired all the gliders in the recipe you're constructing.

If you move the block back to its old location as part of the turner recipe every time, it doesn't really save you anything -- just arbitrarily changes where you're moving the block from in step #1, and (usually) eats up extra gliders.

If the block has wandered a little to the left of where you want it, you'll generally use a recipe that moves the block a little to the right. If it's already too far right, you can use the mirror-image recipe. It should be possible to come up with a complete toolkit that guarantees that the elbow, and all its intermediate reactions, will stay within a specific bounded area.

It will be interesting to see how small that area can be made, with more expensive choices of block moves or turner reactions. The cheapest possible recipes will probably allow the elbow to wander around quite a bit...!
User avatar
dvgrn
Moderator
 
Posts: 5820
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Slow Salvo Gliders

Postby dvgrn » May 13th, 2015, 6:23 pm

simsim314 wrote:
dvgrn wrote: Any set of recipes with an invariant block can be converted to an equivalent set with an invariant honeyfarm -- usually by simply moving the first glider in each recipe to the end.

It's not exactly correct. Many recipes start from moving block by (2,1). Of course you could add this movement to the end of the previous recipe as well, but this could make the recipes a bit longer than recipes with only block. And because we're limited by memory in the depth that we can search for recipes, so always starting with HF will cause us actually lose some of the recipes, that we wouldn't lose if we would start from block.

The block-move searches have already been done up to 9 gliders -- and they're all "atomic" recipes, so there aren't any that start with a (2,1) move. They're all trivially transformable to honeyfarm-target recipes.

Interestingly, there's a honeyfarm-target turner with only four gliders!

x = 26, y = 31, rule = B3/S23
6bo$5bobo$5bobo$6bo2$b2o7b2o$o2bo5bo2bo$b2o7b2o2$6bo$5bobo$5bobo$6bo2$
15b3o$7b3o5bo$7bo8bo$8bo3$23b3o$23bo$24bo6$23b3o$23bo$24bo!
User avatar
dvgrn
Moderator
 
Posts: 5820
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Slow Salvo Gliders

Postby chris_c » May 13th, 2015, 6:24 pm

I made some very minimal changes to the script to get it to do something like what you want: all salvos are p1 and a recipe is output if the final pattern has 9 cells and seems to contain a glider moving SE or NW.

Note that it is quite possible that the final pattern could be tub + glider and the script doesn't care if the block has returned to its original position or not. Also it only allows a glider to be produced at the final step. For example, it won't find recipes where a glider is produced at step 3 and then the remaining debris is converted back into a block during later steps.

It seems like there are plenty of 5 glider solutions under these restrictions. (EDIT: Ooops, no it only starts churning out solutions that contain 6 gliders, and for reasons mentioned above it misses dvgrn's 5 glider solution in the other thread). Finally, here is the code:

import golly as g
from hashlib import sha256
from itertools import chain

#arbitrary numbers
MAX_GENERATIONS = 256
MAX_POPULATION = 40
MAX_GLIDERS = 6

#NE glider
GLIDER = g.parse('3o$2bo$bo!')

#put any ad-hoc patterns that you want to bombard with slow gliders here.
TARGET_PATTERNS = []#('known_splitter', 'bo$obo$b2o$5bo$4bobo$5bobo$6b2o!')]

#put simple targets here, along with rotational symmetry
SIMPLE_TARGETS = [
  ('block', '2o$2o!', 4),
#  ('blinker', '3o$!', 4),
#  ('tub', 'bo$obo$bo!', 4),
#  ('boat', 'b2o$obo$bo!', 1),
#  ('hive', 'b2o$o2bo$b2o!', 2),
#  ('ship', 'b2o$obo$2o!', 2),
#  ('loaf', 'b2o$o2bo$bobo$2bo!', 1),
#  ('lboat', '2b2o$bobo$obo$bo!', 1),
#  ('pond', 'b2o$o2bo$o2bo$b2o!', 4),
# ('tlight', '4bo$4bo$4bo2$3o3b3o2$4bo$4bo$4bo!', 4),
# ('hfarm', '6bo$5bobo$5bobo$6bo2$b2o7b2o$o2bo5bo2bo$b2o7b2o2$6bo$5bobo$5bobo$6bo!', 4),
]

def get_pattern_variants(cells, symmetry):
  variants = []
  for t in range(0, 4, symmetry):
    variants.append(cells)
    cells = g.transform(cells, 0, 0, 0, -1, 1, 0)
  return variants

TARGETS = []
for name, pattern in TARGET_PATTERNS:
  cells = g.parse(pattern)
  p = len(cells) / 2
  TARGETS.append((name, cells, p))

for name, pattern, sym in SIMPLE_TARGETS:
  cells = g.parse(pattern)
  variants = get_pattern_variants(cells, sym)
  for i, v in enumerate(variants):
    p = len(v) / 2
    TARGETS.append((name+str(i), v, p))

def patterns_identical(cells1, cells2):
  if len(cells1) != len(cells2):
    return False
  if sum(cells1) != sum(cells2):
    return False
  return sorted(zip(cells1[::2], cells1[1::2])) == sorted(zip(cells2[::2], cells2[1::2]))

def get_pattern_period(cells):
  temp_cells = cells
  for p in range(0, 2):
    temp_cells = g.evolve(temp_cells, 1)
    if patterns_identical(cells, temp_cells):
      return p+1
  return None

def get_shooting_range(cells):

  min_d1 = max_d1 = cells[0] + cells[1]
  min_d2 = cells[0] - cells[1]

  for i in range(2, len(cells), 2):
    min_d1 = min(min_d1, cells[i] + cells[i+1])
    max_d1 = max(max_d1, cells[i] + cells[i+1])
    min_d2 = min(min_d2, cells[i] - cells[i+1])

  min_lane = min_d1 - 6
  max_lane = max_d1 + 3
  shift = 6 - min_d2 // 2

  return min_lane, max_lane, shift

def get_pattern_to_try(cells, lane, parity, offset=50):
  glider = g.transform(GLIDER, lane - lane // 2 - offset, lane // 2 + offset)
  if parity % 2:
    glider = g.evolve(glider, 1)
  return list(chain(cells, glider))

offset = 0

def display_solution(start, lanes, debug, last_cells):

  global offset

  cells = [c for n, c, _ in TARGETS if n == start][0]
  i = 100
  for lane in lanes:
    lane_num, parity = lane
    cells = get_pattern_to_try(cells, lane_num, parity, i)
    i += 100
  g.putcells(cells, 0, offset)
  for i, p in enumerate(debug):
    g.putcells(p, 100 + 100 * i, offset)
  g.putcells(last_cells, 100 + 100 * len(debug), offset)
  g.fit()
  g.update()
  g.show(' '.join(chain([str(start), str(len(lanes))], [str(lane) for lane in lanes])))
  offset += 400


randoms = []
for i in range(4096):
  randoms.append(int(sha256(str(i)).hexdigest()[:16], 16))

def to_hashable(cells):
  if not cells:
    return 0

  minx = min(cells[::2])
  miny = min(cells[1::2])

  hash = 0
  for i in range(0, len(cells), 2):
    hash ^= randoms[64 * (cells[i] & 63) + (cells[i+1] & 63)]

  return hash

def deltas(cells):
  return len(cells), sum(cells[::2]), sum(cells[1::2])

def bombard_final(start, lanes, cells, period, debug, flipx, flipy):

  cells = g.transform(cells, 0, 0, flipx, 0, 0, flipy)

  min_lane, max_lane, shift = get_shooting_range(cells)

  for lane_num in range(min_lane, max_lane + 1):

    for parity in range(period):
     
      lane = (lane_num, parity)
      start_cells = get_pattern_to_try(cells, lane[0], lane[1], shift)
      new_cells = g.evolve(start_cells, MAX_GENERATIONS)

      if len(new_cells) == 18:
        n1, dx1, dy1 = deltas(new_cells)
        n2, dx2, dy2 = deltas(g.evolve(new_cells, 4))
        if n1 != n2:
          continue
        dx = dx2-dx1
        dy = dy2-dy1
        if (dx, dy) == (5, 5) or (dx, dy) == (-5, -5):

          #Success??

          #flip back for display purposes
          start_cells = g.transform(start_cells, 0, 0, flipx, 0, 0, flipy)
          new_cells = g.transform(new_cells, 0, 0, flipx, 0, 0, flipy)
          #add
          debug.append(start_cells)
          lanes.append(lane)
          #display
          display_solution(start, lanes, debug, new_cells)
          #remove
          lanes.pop()
          debug.pop()

g.new('')

new_queue = []
for name, cells, _ in TARGETS:
  period = get_pattern_period(cells)
  new_queue.append( (name, [], cells, period, []) )

seen = set()

for n in range(MAX_GLIDERS):

  queue = new_queue
  new_queue = []

  count = 0

  for start, lanes, last, period, debug in queue:

    g.show(str((n+1,count,len(queue))))
    count += 1

    min_lane, max_lane, shift = get_shooting_range(last)

    for lane_num in range(min_lane, max_lane + 1):

      for parity in range(period):
       
        lane = (lane_num, parity)
        start_cells = get_pattern_to_try(last, lane[0], lane[1], shift)
        new_cells = g.evolve(start_cells, MAX_GENERATIONS)

        if not new_cells or len(new_cells) > 2 * MAX_POPULATION:
          continue

        new_period = get_pattern_period(new_cells)
        if new_period != 1:
          continue

        new_hashable = to_hashable(new_cells)       

        if new_hashable in seen:
          continue

        seen.add(new_hashable)
        if new_period > 1:
          seen.add(to_hashable(g.evolve(new_cells, 1)))
       
        new_lanes = lanes + [lane]
        new_debug = debug + [start_cells]
         
        bombard_final(start, new_lanes, new_cells, new_period, new_debug, 1, 1)
#       bombard_final(start, new_lanes, new_cells, new_period, new_debug, 1, -1)
#        bombard_final(start, new_lanes, new_cells, new_period, new_debug, -1, -1)

        if n + 1 < MAX_GLIDERS:
          new_queue.append( (start, new_lanes, new_cells, new_period, new_debug) )
chris_c
 
Posts: 905
Joined: June 28th, 2014, 7:15 am

Next

Return to Patterns

Who is online

Users browsing this forum: No registered users and 3 guests