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

The Hunting of the Elementary Conduits

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

Re: The Hunting of the Elementary Conduits

Postby Jormungant » March 24th, 2018, 3:34 pm

Came to claim my pointless improvement award:

x = 156, y = 81, rule = LifeHistory
7$132.A$130.3A$85.2A.A28.A11.A$85.A.2A28.3A9.2A$120.A9.B$86.5A16.2A
10.2A9.3B$81.2A2.A4.A12.2A3.A10.5B5.6B$81.A2.A.BAB14.A4.A.AB9.4B3.10B
10.4B$82.A.A.2AB11.BA.A5.2AB.3B4.6B2.11B3.2B2.7B$81.2A.A.4BA9.B2A8.7B
.9BD3B2A15BD3B$61.A22.A3.BABA6.3B10.17B2D2B2A15BDBDB$59.3A22.2A2.A2BA
3.6B11.17B2D18B3DB$7.4B35.A11.A30.2A10B10.18BD21BDB$8.3BA34.3A9.2A31.
8B10.19BD24B$9.3BA36.A9.B26.B4.8B3.23B.B3.10B$10.3AB22.2A10.2A9.3B23.
3B3.10BD7BD13B7.7B.B$11.4B22.A10.5B5.6B19.6B2.11BD6BDBD4B.6B$12.4B21.
A.AB9.4B3.10B10.4B2.7B.11B2D5B3D4B2.B.5B$13.4B10.A10.2AB.3B4.6B2.11B
3.2B2.26B2D8BD4B7.2A$14.4B7.3A12.7B.9BD3B2A15BD22BD13B8.A$15.4B5.A15.
17B2D2B2A15BDBD27B16.3A$16.4B4.2A15.17B2D18B3DB2A23B19.A$9.2A6.9B14.
18BD21BDB2A22B$10.A7.6B14.19BD48B$10.A.2A5.6B3.B2.2B2.19B.B3.13B.B5.
26B$11.A2.A4.19BD13B7.7B15.B2.19B$12.2AB3.20BDBD4B.6B31.19B$13.14B2A
9B3D4B2.B.5B28.20B$14.13B2A11BD4B7.2A27.10B.10B3.2A$15.29B8.A27.2A8B
2.11BA2.A$15.17B.B.2B16.3A23.ABA7B4.10B3A$16.15B4.3B17.A16.A6.A8B5.7B
2.B3.3A$16.15B5.A2B.2A30.3A3.2A2B.4B5.8B3.2A3.A$17.13B5.A.A2B.A33.AB
5.4B5.4B3.3B3.A.2A$19.13B2.A.AB2.A33.2AB4.4B5.4B4.2A.A2.A.A$18.8B4.2A
.A.A3.A34.4B2.4B5.4B6.A.4A.A$18.6B6.2ABA2.4A.A34.B2.4B5.4B5.A.A5.A$
18.5B8.B2.A.A3.A.A33.B.4B5.4B6.2A.A.3A$18.B.B9.2A.2A2.A2.A.A31.7B5.4B
10.A.A$19.3B9.A.A2.2A3.A32.6B5.4B2.B8.2A$18.B2AB9.A.A31.A7.8B3.4B2.6B
$19.2A11.A32.3A5.9B.8B2A4B$68.A3.18BA2BA3B$67.2A.21B2A4B$67.29B$69.
26B$68.26B$69.24B$68.24B$67.25B$67.24B$67.10B2A9B$66.11B2A4B$66.17B$
66.16B$67.14B$67.14B$71.11B$71.10B$71.9B$71.7B$69.2A3B$64.2A2.A2BA$
64.A3.BABA$61.2A.A.4BA$62.A.A.2AB$61.A2.A.BAB$61.2A2.A4.A$66.5A2$65.A
.2A$65.2A.A!


repeat time -32
Jormungant
 
Posts: 68
Joined: May 27th, 2016, 1:01 am

Re: The Hunting of the Elementary Conduits

Postby Kazyan » April 5th, 2018, 5:44 pm

New R-to-G, though it seemingly doesn't connect to anything useful:

x = 26, y = 30, rule = LifeHistory
4B$.4B$2.4B$3.4B$4.4B$5.4B$6.4B$7.4B$8.8B$9.8B$10.7B6.BA$11.10B.BA.A$
11.13BA$11.2BC10B$11.2B2C8B$11.B2C9B$11.11B$12.12B$12.8B2.2A$10.B.6B
4.A$9.2A6B6.3A$9.2A7B7.A$9.B.7B2A$7.3A.AB4.BA.A$6.A3.2AB5.B.A2.A$7.2A
5.A4.2A.A.A$9.6A5.A2.A$9.A8.A.A$10.3A5.2A$12.A!
Tanner Jacobi
User avatar
Kazyan
 
Posts: 747
Joined: February 6th, 2014, 11:02 pm

Re: The Hunting of the Elementary Conduits

Postby dvgrn » May 2nd, 2018, 5:32 pm

Elementary Conduit Repeat Times
A few elementary conduits, with the naming convention used in this thread, have started showing up on the LifeWiki, mostly due to imports from the Life Lexicon.

The LifeWiki has a place to put a repeat time for each elementary conduit -- and I've been meaning to collect that information for all known elementary conduits at some point anyway, with the idea of eventually producing some kind of Hersrch For The Modern Age.

Wishful Thinking about a New Hersrch
-- It would sure be nice to be able to select an output and an input, and tell a search program "I want a stable mechanism to turn this output into that input in T ticks, and it should fit in the empty space in the current pattern, and the recovery time should be R ticks or less." The search should allow H-to-Gs and syringes, and tandem gliders (rarely useful these days but you never know) and G-to-MWSS-to-G conversions and every other reasonable-sized mechanism that we can throw into the library -- along with all the traditional Herschel conduits.

A Small Annoying Problem with Statistics
Unfortunately, the repeat time for converters turns out to not be a terribly easy thing to calculate. You can run a conduit with an R-pentomino input, for example, and then draw in another R-pentomino as soon as the sparks clear, and call that the repeat time -- but in a lot of cases there's not really any way to get an R-pentomino to that location that quickly in practice, because the just-faded sparks would have gotten in the way of the stages leading up to the R-pentomino.

The Same Thing for Herschels
Come to think of it, it really isn't easy for Herschel conduits either, in some cases, but we've gotten along with an approximation so far.

The approximation is that the input Herschel is considered to be "coming from infinity", meaning that the conduit is supposed to work if you prepend something standard to it -- usually a BFx59H. In other words, we're not doing the testing as if the Herschel just magically appears in the input position at T=0.

This really does make a difference a lot of times. If the first natural glider is going to be allowed to escape, especially, then the repeat time is higher because the usual way of evolving a Herschel will conflict with the previous outgoing glider. If it weren't for that detail, several Herschel conduits would have a lower repeat time.

Hypothetical Hiccups
This means that if a new conduit ever shows up that creates a Herschel really quickly, and/or from a different angle than the BFx59H, then we'll have to reduce the ratings of a bunch of existing conduits. Not that that would be so terrible, but -- ugh.

However, until a conduit like that actually shows up, mechanisms with a nominally faster recovery are really going to be useless almost all of the time if they can't recover that quickly when connected to BFx59H. So repeat times measured in a BFx59H context are really very usable in practice.

There's More Trouble If It Ain't A Herschel
The problem is a bit worse for converters in general, because nobody even really knows what the "default" conduit is for supplying, say, a B-heptomino to the BNE14T30, or (better example) an R-pentomino to the RF28B. Quite possibly future conduits will show up that will do a better job of making those deliveries quickly and staying out of the way.

"Instant Appearance" Recovery Time -- a lower bound
So... what should I put down for the recovery time of all these converters from the new Life Lexicon? What I've done so far is to record the IA "instant appearance" recovery time, as I mentioned above. The IA-recovery is the lowest N where an input X can magically appear at the input position at T=0 and then again at T=N ticks (or any number greater than N), and the conduit reliably will work and recover... twice.

I'm not entirely happy with this method, because it gives an unreasonably small number for the RF28B recovery time. If we use IA-recovery numbers everywhere, it seems like it will turn out sometimes that you'll combine two conduits X and Y, with recovery times rX and rY, and you'll find that the recovery time rZ of the combined mechanism will be *higher* than either rX or rY, instead of just trivially equal to max(rX, rY).

(Just like in the Herschel case, it will quite often happen that the slowest-recovering part of the mechanism is right at the connection point between the two joined conduits -- and the IA-recovery measurement doesn't test that connection point.)

I Can't Think of Anything Better -- Can You?
But I don't see what to do about it. If I use the current "best known connection" to feed in a converter's input, and measure the recovery time based on that, then we'll likely end up with the opposite problem -- someone will come up with a new conduit X, and now the combination of X and Y will have a recovery rate *lower* than either rX or rY, because rY's recovery rating is outdated as soon as conduit X is invented.

We're safe from this second problem, as long as I use the "instant appearance" method to calculate recovery times. So I might just have to stick with that -- unless anyone has other suggestions. (?)
User avatar
dvgrn
Moderator
 
Posts: 4686
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: The Hunting of the Elementary Conduits

Postby Extrementhusiast » May 3rd, 2018, 2:09 pm

dvgrn wrote:I Can't Think of Anything Better -- Can You?
But I don't see what to do about it. If I use the current "best known connection" to feed in a converter's input, and measure the recovery time based on that, then we'll likely end up with the opposite problem -- someone will come up with a new conduit X, and now the combination of X and Y will have a recovery rate *lower* than either rX or rY, because rY's recovery rating is outdated as soon as conduit X is invented.

We're safe from this second problem, as long as I use the "instant appearance" method to calculate recovery times. So I might just have to stick with that -- unless anyone has other suggestions. (?)

Although it would increase the amount of needed data from O(n) to O(n^2), perhaps we could label the conduit connections by recovery time, instead of the conduits themselves. Measurement of recovery time would start with instant appearance of the first input, proceed through the first output/second input, and end with instant disappearance (or perhaps just suitable eating) of the second output.

(I seem to have a thought process behind this, but I unfortunately can't put it into anything coherent right now.)
I Like My Heisenburps! (and others)
User avatar
Extrementhusiast
 
Posts: 1703
Joined: June 16th, 2009, 11:24 pm
Location: USA

Re: The Hunting of the Elementary Conduits

Postby Jormungant » May 3rd, 2018, 2:39 pm

Well, I think single conduit requires annotations. Even if you move to n^2, there is still 2 ends to your conduits, so the other connection will also have variable recovery times. I dont think there is a simple solution, either we ignore the problem and define the recovery time as a lower bound, or we explicitly find the best legal connection, as drgrn suggested. My take is that we could acknowledge that defining such a number is arbitrary, and instead define a range (min-max) of recovery time for the best and worse links. This allows us to be reminded of the lack of guaranty on what recovery time of a finished track is by looking at its components alone. Even if we have a single number displayed, it does not tell us what is the optimal connection that allows it anyways. By defining a range instead, you gain a guaranty that any connection have a upper bound on the recovery time. Well, these require to generate *all* *valid* connections, as input and output, which are bound to change with new tracks, but I doubt the range will need to be updated often since the set of precursor for B or H are relatively limited.

I also expect that most tracks are boring (aka min = max >150)
Jormungant
 
Posts: 68
Joined: May 27th, 2016, 1:01 am

Re: The Hunting of the Elementary Conduits

Postby dvgrn » May 3rd, 2018, 3:21 pm

Extrementhusiast wrote:Although it would increase the amount of needed data from O(n) to O(n^2), perhaps we could label the conduit connections by recovery time, instead of the conduits themselves.

Jormungant wrote:Well, I think single conduit requires annotations. Even if you move to n^2, there is still 2 ends to your conduits, so the other connection will also have variable recovery times.

Thanks -- this is good short feedback for a painfully long question.

These responses suggest to me that it might be time to put together a semi-automated tester script to build conduit connections. For each X-to-Y conduit, the script should attempt to place every known Y-to-Z conduit... and then drop in an X, simulate for the required length of time, and see if there's a Z in the output location.

So for each X-to-Y conduit, the script will be able to produce a list of all Y-to-Z conduits that trivially connect to it. It will be interesting to see if doing this turns up any useful connections that we haven't noticed.

Similar to Hersrch, we'll need a long list of special cases, where two conduits explode or are otherwise not functional if you naively drop them next to each other, but there's a weld or other adjustment that allows the connection to work after all. So probably the script should also produce a pile of RLE for each conduit, showing failed connections -- and anyone who combs through the failures and can find workable welds, can contribute those solutions to a "CustomConnections" folder.

Anyway, once we have a tester script, it probably makes sense to take the shortest recovery time for all connections starting with Conduit C, and the shortest recovery time for all connections ending with Conduit C. Whichever number is larger, call that the recovery time of Conduit C. There might still be a few weird cases, but they'll be so few and far between that they won't cause a lot of trouble.

-- See any problems with this plan, except for the obvious one where someone has to write the tester script?
User avatar
dvgrn
Moderator
 
Posts: 4686
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: The Hunting of the Elementary Conduits

Postby Jormungant » May 3rd, 2018, 3:37 pm

Well, if you do not worry about over-clocking (ex syringe, 74,75,78+) I think this should be fine except for rare tracks such as:

x = 48, y = 34, rule = LifeHistory
$32.A$30.3A$29.A$29.2A$27.4B$26.3B$25.4B.3B.B2.4B$18.18B.4B$17.4BD11B
2A5B2A$17.4B3D9B2A5B2A$17.4BDBD15B.B$15.8BD12B2AB$14.13B2.7B2A$14.10B
6.8B$15.7B7.7B$13.8B6.10B$13.2A7B2.13B$12.B2A12BC8B$10.B.15BCBC4B$9.
2A5B2A9B3C4B$9.2A5B2A11BC4B$10.4B.18B$10.4B2.B.3B.4B$22.3B$20.4B$20.
2A$21.A$18.3A$18.A!
Jormungant
 
Posts: 68
Joined: May 27th, 2016, 1:01 am

Re: The Hunting of the Elementary Conduits

Postby dvgrn » May 17th, 2018, 6:48 pm

I've updated the top of the thread with a fresh copy of the Elementary Conduits collection.

This 17 May 2018 update includes the update by calcyman, plus everything that I was able to go back and find since November that seems able to connect to anything. The conduit compiler script is now officially back in action. It's included in the ZIP file, and it rebuilds the stamp collection when you run it.

The largest number of new additions are in the H-to-G category, which was woefully incomplete. It's probably still woefully incomplete, but less so than before.

-- Anyone care to cross-check the actual H-to-G collection and other sources of H-to-Gs, and point out whatever is still missing? Pretty please with a knightship on top thanks in advance!

Here are my rough change notes for the new 2018 ECC:
H-to-G converters added:
  SW28T1784
  SW15T116
  SE10T19
  SE-1T41
  NW36T128
  NE34T49
  SE18T9
  NW16T124
  SW3T118
  SW13T112
  NW17T90  H-to-2G
  SW15T118 H-to-2G
  NW36T126
  NE37T12
  SE10T29
  NW2T196
  NW1T192
  NE-27T176 H-to-3G with SE5T23 and SW-2T21

pi-to-2G PNW6T114_NE17T206
PF35W, PFx35W became PF35Wa, PFx35Wa (added updated PF(x)35Wb)

2 R-to-G:  RSW15T32 RSW13T28

3 semi-cenarks (G0-to-G)
tremi-Snark (G00-to-G)
quadri-Snark (G000-to-G)

Added semi-cenark G0-to-C

Added NW31T120_NW30T234 (H-to-G1)  (_SE-2T80_SW-2T21)

Added NW31T120_NW29T210 (H-to-G2)

Added NW31T120_NW26T163_SE23T108 (H-to-G5)

Added SW3T118_SW-2T21 (H-to-G5)

Added H-to-G9:  SW7T94_SW-2T21..._SW-1T110

Added H-to-G SW7T94

Fixed H-to-G8 and H-to-G9#2, making third glider an optional comment

Added HF73R

Added BFx59H with shillelagh (and hat, and two ways of using eater1s... didn't include aircraft carrier or a bajillion larger still lifes that would work -- one has to stop somewhere.  These are all commonly used variants.)

Added H-to-G7 HSW5T105_SW-2T21

Added HNE15T22(90)

Added HF123B

Maybe the most controversial change is that I simplified the names of most of the G(n) input conduits. Without defining which of the two gliders is the "standard" glider that measurements are made from, it's hard to unambiguously define a relative output lane. Recording output timing is similarly difficult because the input is not fixed -- gliders in a tandem pair can come in at many different relative timings.

Even output orientation is hard to define, because gliders can usually come in in either order, and you add or remove the junk still life accordingly. You can mirror G(n)-to-X converters along the input diagonal to switch from one type to the other, and that will change the output orientation.

So for the collection to be complete with the 2016 naming, it would have been necessary to duplicate most of the converters -- original, and then mirror-image, with different names. It seemed simpler to just record the type of the output, and leave it at that. (Maybe we should go back and rethink pi-input conduit naming, along the same lines.)
User avatar
dvgrn
Moderator
 
Posts: 4686
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Previous

Return to Patterns

Who is online

Users browsing this forum: No registered users and 6 guests