[Forum Game] CA Puzzles

A forum where anything goes. Introduce yourselves to other members of the forums, discuss how your name evolves when written out in the Game of Life, or just tell us how you found it. This is the forum for "non-academic" content.
User avatar
Rhombic
Posts: 1057
Joined: June 1st, 2013, 5:41 pm

Re: [Forum Game] CA Puzzles

Post by Rhombic » March 11th, 2017, 1:41 pm

I'll go ahead with a very easy puzzle:
Add or remove one non-totalistic birth/survival condition and remove one cell to turn this pattern into a xq4.
Please don't use Catagolue to find the actual ship.

Code: Select all

x = 6, y = 4, rule = B2c3-ey4q/S23-a
b2o$obo2bo$3b3o$5bo!
SoL : FreeElectronics : DeadlyEnemies : 6a-ite : Rule X3VI
what is “sesame oil”?

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

Re: [Forum Game] CA Puzzles

Post by Rhombic » April 5th, 2017, 8:56 am

Place THREE state-2 B-heptominoes in the bounded box to destroy the state 1 cells completely (no escaped gliders), reacting with all state 2 blocks and without any state 1 cells touching the blocks at the back at any point.

Code: Select all

x = 164, y = 147, rule = DeadlyEnemies
.2B2.2B$.2B2.2B4$5.2B3.2B3.2B2.2B$2B3.2B3.2B3.2B2.2B$2B$5.2B$5.2B$2B
17.2B3.2B$2B12.2B3.2B3.2B$14.2B$19.2B$19.2B48$84.A$82.2A$81.A.A$81.2A
7$73.A$71.2A$70.A.A18.2A$70.2A19.2A$98.2A$91.2A4.A2.A$91.2A4.A2.A$98.
2A3$94.A$94.2A$86.2A6.2A$86.2A7.A$68.A$66.2A$65.A.A31.2A$65.2A32.2A$
107.A11.A11.A11.A11.A7.A$90.2A3.2A$90.2A3.2A66.A2$87.2A74.A$87.2A$94.
2A67.A$87.2A4.A2.A$87.2A4.A2.A66.A$94.2A$163.A2$90.A16.A55.A$90.2A$
82.2A6.2A71.A$82.2A7.A$163.A2$95.2A66.A$95.2A$163.A$86.2A3.2A$86.2A3.
2A70.A2$107.A55.A2$163.A2$163.A2$163.A2$163.A2$163.A2$107.A55.A2$163.
A2$163.A2$163.A2$163.A2$163.A2$107.A55.A2$163.A2$163.A4$107.A.A.A.A.A
.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A3.A!
One solution SPOILERALERT:

Code: Select all

x = 164, y = 147, rule = DeadlyEnemies
.2B2.2B$.2B2.2B4$5.2B3.2B3.2B2.2B$2B3.2B3.2B3.2B2.2B$2B$5.2B$5.2B$2B
17.2B3.2B$2B12.2B3.2B3.2B$14.2B$19.2B$19.2B48$84.A$82.2A$81.A.A$81.2A
7$73.A$71.2A$70.A.A18.2A$70.2A19.2A$98.2A$91.2A4.A2.A$91.2A4.A2.A$98.
2A3$94.A$94.2A$86.2A6.2A$86.2A7.A$68.A$66.2A$65.A.A31.2A$65.2A32.2A$
107.A11.A11.A11.A11.A7.A$90.2A3.2A$90.2A3.2A41.2B23.A$137.2B$87.2A49.
2B23.A$87.2A23.B26.B$94.2A15.3B49.A$87.2A4.A2.A13.2B.B$87.2A4.A2.A66.
A$94.2A$163.A2$90.A16.A55.A$90.2A$82.2A6.2A71.A$82.2A7.A$163.A2$95.2A
66.A$95.2A15.B$111.2B50.A$86.2A3.2A17.2B$86.2A3.2A18.2B50.A2$107.A55.
A2$163.A2$163.A2$163.A2$163.A2$163.A2$107.A55.A2$163.A2$163.A2$163.A
2$163.A2$163.A2$107.A55.A2$163.A2$163.A4$107.A.A.A.A.A.A.A.A.A.A.A.A.
A.A.A.A.A.A.A.A.A.A.A.A.A.A.A3.A!
SoL : FreeElectronics : DeadlyEnemies : 6a-ite : Rule X3VI
what is “sesame oil”?

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

Re: [Forum Game] CA Puzzles

Post by dvgrn » April 5th, 2017, 9:02 pm

Rhombic wrote:Place THREE state-2 B-heptominoes in the bounded box to destroy the state 1 cells completely (no escaped gliders), reacting with all state 2 blocks and without any state 1 cells touching the blocks at the back at any point.

Code: Select all

x = 164, y = 147, rule = DeadlyEnemies...
Seems like a link to where the DeadlyEnemies rule table is posted might be useful here.

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

Re: [Forum Game] CA Puzzles

Post by dvgrn » June 17th, 2017, 10:38 pm

Here's a puzzle that's maybe really more of an optimization problem.

With the new 0-degree Snark recipe, simeks' single-channel construction arm is now capable of bending itself around an arbitrary number of corners, then un-bending those corners again if needed. It can also throw off target blocks to either side, and shoot *WSSes in all directions -- and even Corderships and loafers and so on, if those are needed.

There appear to be universal elbow operations even when individual gliders are required to be separated by up to 213 ticks. This allows an interesting trick to be done with Guam's one-bit-spark-to-2G converter, which recovers in 164 ticks.

Starting with an empty universe, we can change the state of 35 cells at T=0, as follows:

Code: Select all

x = 66, y = 65, rule = LifeHistory
.A$2A25$22.3B$22.4B$23.4B$24.4B$25.4B$26.4B14.A$27.4B11.3A$28.4B9.A$
29.4B8.2A$30.4B2.2B.4B$31.4B.5B$31.11B$28.14B.2B$27.19B$26.20B$27.20B
$27.21B$27.21B$27.22B$26.24B$26.24B14.2A$26.23B3.B11.A$25.32B4.BA.A$
24.19BD16B.B2A$25.37B$25.19B2A16B$25.18BA2BA15B$25.19B2A14B$24.28B5.B
.B$25.2B.A7B2.14B4.3B$26.B2A8B5.8B6.B.AB$26.12B4.6B9.2A$27.6B2.4B4.4B
$29.4B3.3B2$37.2A$38.A$37.A$37.2A!
#C [[ THUMBNAIL THUMBSIZE 2 ]]
Then, as long as we have complete control of a single cell (the red cell above) we can send out single-channel recipes that can build any pattern that can be constructed with a finite number of gliders.

We can even promise to turn on the cell no more than once every 164 ticks, since we can't really do that anyway, or even only at most once every 213 ticks if we didn't mind taking twenty times as long to get constructions done. Otherwise we can leave the cell alone, never turning it OFF.

-- Okay, so that's 36 cells we have to touch, 35 at T=0 and one more that we have to be able to modify indefinitely to allow for universal construction. The questions are

1) Can we get to universal construction with fewer T=0 cells and only one permanent-control cell?

and

2) If we have permanent control over any cells we touch, how many do we need to achieve universal construction?

The upper bound for the answer to #2 seems to be 4 cells, because you can produce gliders on demand, if you have control over three cells in a banana-spark shape (among others). And then you can lie in wait for a glider out along the output channel, and convert a glider into an elbow -- and then you never need to use that fourth cell again.

The lower bound is pretty definitely 3 cells, for obvious reasons. I strongly suspect that universality can be achieved with only three controllable cells, but I'm not sure I want to try to prove it.

2b) Are there arrangements of three cells where you only need to be able to turn the cells ON or leave them alone to make a stream of single-channel gliders? The banana-spark glider generation method I found needed four ticks, and I had to turn two different cells OFF in different generations.

User avatar
A for awesome
Posts: 1942
Joined: September 13th, 2014, 5:36 pm
Location: 0x-1
Contact:

Re: [Forum Game] CA Puzzles

Post by A for awesome » June 17th, 2017, 11:13 pm

dvgrn wrote:1) Can we get to universal construction with fewer T=0 cells and only one permanent-control cell?
Well, here's a trivial optimization (33 T=0 cells):

Code: Select all

x = 66, y = 65, rule = LifeHistory
.A$2A25$22.3B$22.4B$23.4B$24.4B$25.4B$26.4B14.A$27.4B11.3A$28.4B9.A$
29.4B8.2A$30.4B2.2B.4B$31.4B.5B$31.11B$28.14B.2B$27.19B$26.20B$27.20B
$27.21B$27.21B$27.22B$26.24B$26.24B14.2A$26.23B3.B11.A$25.32B4.BA.A$
24.19BD16B.B2A$25.37B$25.19BA17B$25.19B2A16B$25.20BA14B$24.28B5.B.B$
25.2B.A7B2.14B4.3B$26.B2A8B5.8B6.B.AB$26.12B4.6B9.2A$27.6B2.4B4.4B$
29.4B3.3B2$37.2A$38.A$37.A$37.2A!
x₁=ηx
V ⃰_η=c²√(Λη)
K=(Λu²)/2
Pₐ=1−1/(∫^∞_t₀(p(t)ˡ⁽ᵗ⁾)dt)

$$x_1=\eta x$$
$$V^*_\eta=c^2\sqrt{\Lambda\eta}$$
$$K=\frac{\Lambda u^2}2$$
$$P_a=1-\frac1{\int^\infty_{t_0}p(t)^{l(t)}dt}$$

http://conwaylife.com/wiki/A_for_all

Aidan F. Pierce

User avatar
biggiemac
Posts: 504
Joined: September 17th, 2014, 12:21 am
Location: California, USA

Re: [Forum Game] CA Puzzles

Post by biggiemac » June 20th, 2017, 9:57 pm

Is there a way using the banana spark configuration to also make some methuselah? Have it explode a bit, but when stable remain clear of the three control cells? Then use that debris as an elbow of sorts, with at least sufficient clearance to build a snark?

I expect with active control over three cells one can achieve a lot of different explosions so long as one can get started.
Physics: sophistication from simplicity.

wildmyron
Posts: 1312
Joined: August 9th, 2013, 12:45 am

Re: [Forum Game] CA Puzzles

Post by wildmyron » June 21st, 2017, 12:02 am

dvgrn wrote:2) If we have permanent control over any cells we touch, how many do we need to achieve universal construction?

The upper bound for the answer to #2 seems to be 4 cells, because you can produce gliders on demand, if you have control over three cells in a banana-spark shape (among others). And then you can lie in wait for a glider out along the output channel, and convert a glider into an elbow -- and then you never need to use that fourth cell again.

The lower bound is pretty definitely 3 cells, for obvious reasons. I strongly suspect that universality can be achieved with only three controllable cells, but I'm not sure I want to try to prove it.
Here is a sequencce to get to an R after 3 ticks with only modifications of the three cells in a banana spark (Gen 0: 3 On; Gen 1: 1 On; Gen 2: 1 On; Gen 3: 1 On, 1Off)

Code: Select all

x = 23, y = 62, rule = B3/S23
b2o18bo$o20bo19$bo18b2o$2o18b2o18$21bo$3o17bobo$2o18bobo18$bo$3o$2bo!
It doesn't exactly throw debris away from the control site as biggiemac suggests, but it certainly shows there is a potential path to universal construction with full control of only three cells.
dvgrn wrote:2b) Are there arrangements of three cells where you only need to be able to turn the cells ON or leave them alone to make a stream of single-channel gliders? The banana-spark glider generation method I found needed four ticks, and I had to turn two different cells OFF in different generations.
Here's a sequence which takes longer, but only requires turning three cells On at any time:

Code: Select all

x = 27, y = 182, rule = B3/S23
3b2o18bo$2bo20bo19$3bo18b2o$2b2o18b2o18$23bo$2b3o17bobo$2b2o18bobo18$
3bo18b3o$2b3o17bobo$2bobo17bobo17$23bo$2b3o17bobo$2bobo16b2ob2o$2bobo
17$3bo19bo$2bobo16bo3bo$b5o15b2ob2o$22b3o17$3bo$bo3bo15bo3bo$b5o15bo3b
o$2b3o16bo3bo$23bo17$bo3bo18b2o$bo2b2o14b3ob3o$bo3bo16bo2bo$3bo17$4b2o
15b2o3bo$7o14b2o3bo$2bo2bo16bo2b2o18$b2o3bo$b2obobo$2bo2b2o!
And here's an example explosion with only control to turn On three cells at any time:

Code: Select all

x = 27, y = 163, rule = B3/S23
3b2o18bo$2bo20bo19$3b2o17b3o$2b2o18b3o18$23bo$2b3o17bobo$2b3o17bobo$
23bo17$3bo18b3o$2b3o17bobo$2bobo17bobo$3bo19bo16$23bo$2b3o17bobo$2bobo
16b2ob2o$2bobo17bobo$3bo19bo16$3bo19bo$2bobo16b2ob2o$b2ob2o15b2ob2o$2b
obo16b2ob2o$3bo19bo16$3bo18b3o$b2ob2o15bo3bo$b2ob2o14bo5bo$b2ob2o15bo
3bo$3bo18b3o36$2b3o$bo3bo$o3bobo$b2o2bo$2b3o!
It doesn't really throw out its debris in the right place but there's no shortage of ways to interact with it to achieve that outcome.
The latest version of the 5S Project contains over 226,000 spaceships. There is also a GitHub mirror of the collection. Tabulated pages up to period 160 (out of date) are available on the LifeWiki.

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

Re: [Forum Game] CA Puzzles

Post by dvgrn » June 21st, 2017, 12:58 am

biggiemac wrote:Is there a way using the banana spark configuration to also make some methuselah? Have it explode a bit, but when stable remain clear of the three control cells? Then use that debris as an elbow of sorts, with at least sufficient clearance to build a snark?

I expect with active control over three cells one can achieve a lot of different explosions so long as one can get started.
Yes, it doesn't seem like there will be any problem -- just have to find a methuselah that leaves relatively sparse ash including something on a diagonal (fairly common) and also doesn't happen to throw off any gliders (a little less common). Once we have a working elbow, it can be moved to a safe distance and single-channel programmed to send back 180-degree gliders, to do any cleanup we might want to do.

Here's a little script that accepts BananaCode recipes, to make it maybe (I'm not sure yet) a little easier to record interesting recipes. It would probably be good to add support for RLE encoding of these strings... I found three out of four glider output directions fairly quickly, so that's the sample pattern:

Code: Select all

import golly as g
from time import sleep
g.setrule("LifeHistory")
g.addlayer()
delay=0.1
s=g.getstring("Enter base 27 string (@ABC...Z) encoding a banana-spark activation pattern, and comma-separated optional speed",
              "MJBU@@@@@@@@@@@@@MJBU@@@@@@@@@@@@@MJRE@@@@@@@@@@@@@MJRE@@@@@@@@@@@@MJHA@@@@@@@@@@@MJHA@@@@@@@@@@@,.05")

pieces=s.upper().split(",")
if len(pieces)==2:
  delay=float(pieces[1])
s=pieces[0]
t=0
for i in s:
  base3val = ord(i)-64
#  g.note(str(base3val))
  if base3val<0 or base3val>26: base3val = 0
  spark0 = base3val%3
  spark1 = ((base3val-spark0)/3)%3
  spark2 = base3val/9
  if spark0!=0: g.setcell(0,0,spark0+2)
  if spark1!=0: g.setcell(0,1,spark1+2)
  if spark2!=0: g.setcell(1,2,spark2+2)
  g.run(1)
  t+=1
  g.show(i + " at T= " + str(t))
  g.update()
  sleep(delay)
BananaCode.png
BananaCode.png (14.17 KiB) Viewed 1710 times
Red = no change, green = turn ON, blue = turn OFF. Any character not in @ABCD...Z will be assumed to be @ (zero, no effect).

What's the shortest recipe for the fourth glider output direction?

There's quite a difference between these two recipes:

Code: Select all

MJ..CC.....M....MD.......................................................................................A.......
MJ..CC.....M....MD........................................................................................A.......
There will be much quicker and better mess-maker recipes, of course, this is just a random sample.

I'm not sure how far it will be possible to get with an exhaustive enumeration, though. Random text tends to do nothing at all, because only the M's followed by a few other possibilities will ever amount to anything. Even the entire Gettysburg Address with spaces removed manages only a few sparks that last slightly longer than the banana spark. I wonder which of the works of Shakespeare are the sparkiest?

Code: Select all

FourscoreandsevenyearsagoourfathersbroughtforthonthiscontinentanewnationconceivedinlibertyanddedicatedtothepropositionthatallmenarecreatedequalNowweareengagedinagreatcivilwartestingwhetherthatnationoranynationsoconceivedandsodedicatedcanlongendureWearemetonagreatbattlefieldofthatwarWehavecometodedicateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfittingandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravemenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorpowertoaddordetractTheworldwilllittlenotenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheunfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattaskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth,0

wildmyron
Posts: 1312
Joined: August 9th, 2013, 12:45 am

Re: [Forum Game] CA Puzzles

Post by wildmyron » June 21st, 2017, 2:02 am

BananaCodes - I love it.

For Turn On operations only (which seems an arbitrary limitation, but then that's what this exercise is all about) the allowed characters are:
@ACDIJLM

The glider producing sequence I posted happens to be in the fourth orientation, so here is its banana code - even though it's far from optimal due to avoidance of Turn Off operations (2 gliders shown at minimum repeat time).

Code: Select all

MIAC.CCACA.....MIAC.CCACA.....
The latest version of the 5S Project contains over 226,000 spaceships. There is also a GitHub mirror of the collection. Tabulated pages up to period 160 (out of date) are available on the LifeWiki.

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

Re: [Forum Game] CA Puzzles

Post by dvgrn » June 21st, 2017, 12:30 pm

wildmyron wrote:BananaCodes - I love it.

For Turn On operations only (which seems an arbitrary limitation, but then that's what this exercise is all about) the allowed characters are:
@ACDIJLM

The glider producing sequence I posted happens to be in the fourth orientation, so here is its banana code - even though it's far from optimal due to avoidance of Turn Off operations (2 gliders shown at minimum repeat time).

Code: Select all

MIAC.CCACA.....MIAC.CCACA.....
Wow, 15-tick separation -- that's pretty good given the ON-only limitation.

I haven't run into any recipes yet that allow for the minimum 14-tick separation, but then there aren't any single-channel libraries that need anything less than 90 ticks anyway. 14- or 15-tick single-channel constructions would be quite a lot more efficient than 90-tick or 153-tick or 213-tick or whatever, but we don't have any good "real-Life" ways to create and maintain such streams.

<tangent type="wild">Technically we can store and reflect streams of gliders that include p14 separations now, as long as there's some additional guarantee, along the lines of "any string of seven or more p14-spaced gliders must be immediately preceded by a gap of at least 87 ticks". Even then we'd have to use a gang of seven highway robbers carefully connected to an equal number of inserters, every time we had to turn the glider stream... would need a lot more than seven highway robbers, actually, since we don't have highway robbers that can manage anything near a 112-tick repeat time.

(Also if I remember right we don't actually have complete highway robber mechanisms that can handle 14-tick separation, just 15-tick. There are "bait" structures that could be made to work, but they'd be a lot slower to rebuild.)</tangent>

Post Reply