Page 1 of 2

[Forum Game] CA Puzzles

PostPosted: December 16th, 2016, 9:01 am
by Rhombic
I wish to create a forum game to entertain the community for those periods of time when you're waiting for the result of zfind, apgsearching for the idleness and having nothing better to do.

Rules:
  • A puzzle will be posted, based entirely on Cellular Automata, clear and well-presented so that the intended result is understood clearly (i.e. no parallel-thinking loopholes)
  • The first person to solve the puzzle, ideally posting the solution, gets to post the next puzzle
  • Ideally, the puzzle should be one that allows the solution to be seen as correct by anyone and not just by the OP
  • If a particular puzzle does allow the use of scripts, it must be clearly stated in bold for that individual puzzle
  • At least one solution should be known by the OP, and it should not require an absurd amount of time (so no "find the 1024x1024 soup that results in this ridiculously huge mess"!)

I will start.
---

Scripts are not allowed for this puzzle.

Remove a single glider from the following pattern in a way that the final population is 0.
x = 114, y = 132, rule = B3/S23
bo$2bo$3o3$4bo$5bo$3b3o3$27bo$28bo$26b3o3$36bo$37bo$35b3o3$88bo$88bobo
6bo$88b2o6bo$96b3o2$50bo$51bo$49b3o3$55bo$56bo36bo$54b3o36bobo$93b2o2$
70bo12bo$70bobo10bobo$70b2o11b2o2$65bo$65bobo$48bo11bo4b2o$49bo10bobo$
47b3o10b2o3$46bo$47b2o$46b2o9$74b3o$74bo$42b2o31bo$41bobo$43bo$78b3o$
78bo$79bo2$32b2o$31bobo54b3o$33bo54bo$89bo3$90b3o$90bo$91bo3$91b3o$91b
o$37b2o53bo$36bobo$38bo3$92b3o$92bo$93bo4$25b2o$26b2o$25bo3$20b2o$21b
2o$20bo3$16b3o$18bo$17bo$106b2o$106bobo$15b2o89bo$16b2o83b2o$10bo4bo
84b2o$10b2o90bo$9bobo2$17b3o$19bo$18bo3$14b2o$13bobo$15bo3$8b3o$10bo$
9bo3$9b3o$11bo$10bo$111b2o$111bobo$111bo!

Re: [Forum Game] CA Puzzles

PostPosted: December 16th, 2016, 9:05 am
by GUYTU6J
Removing two bottommost gliders results nothing.

Re: [Forum Game] CA Puzzles

PostPosted: December 16th, 2016, 9:32 am
by dvgrn
GUYTU6J wrote:Removing two bottommost gliders results nothing.

Has to be a single glider, I take it. The top left glider can be removed:

x = 111, y = 127, rule = B3/S23
bo$2bo$3o3$24bo$25bo$23b3o3$33bo$34bo$32b3o3$85bo$85bobo6bo$85b2o6bo$
93b3o2$47bo$48bo$46b3o3$52bo$53bo36bo$51b3o36bobo$90b2o2$67bo12bo$67bo
bo10bobo$67b2o11b2o2$62bo$62bobo$45bo11bo4b2o$46bo10bobo$44b3o10b2o3$
43bo$44b2o$43b2o9$71b3o$71bo$39b2o31bo$38bobo$40bo$75b3o$75bo$76bo2$
29b2o$28bobo54b3o$30bo54bo$86bo3$87b3o$87bo$88bo3$88b3o$88bo$34b2o53bo
$33bobo$35bo3$89b3o$89bo$90bo4$22b2o$23b2o$22bo3$17b2o$18b2o$17bo3$13b
3o$15bo$14bo$103b2o$103bobo$12b2o89bo$13b2o83b2o$7bo4bo84b2o$7b2o90bo$
6bobo2$14b3o$16bo$15bo3$11b2o$10bobo$12bo3$5b3o$7bo$6bo3$6b3o$8bo$7bo$
108b2o$108bobo$108bo!

... Now I have to think of a half-decent CA puzzle. May take a while, unless I recycle something from ten years ago -- more shortly.

EDIT: Okay, this will do for now:

Move just one cell in the following stable constellation by the minimum distance (one step orthogonally, not diagonally) so that when the pattern is run 200 ticks, the result is a loafer traveling to the right, and nothing else:

x = 46, y = 45, rule = B3/S23
22b2o$21bo2bo$21bo2bo$22b2o3$33b2o$33b2o$29b2o$22bo5bobo$21bobo4b2o$
21b2o4$b2o$obo17b2o$bo17bo2bo$19bo2bo19b2o$20b2o3b2o15bo$25b2o16b3o$
45bo2$14b2o$14bobo$10b2o3bobo$9bobo4bo$10bo9bo$19bobo$20b2o3$21b2o$13b
2o6bobo$13bobo6bo$14b2o$b2o$bobo$2bobo$3bo2$15b2o$14bobo$14bo$13b2o!

... Really I'd happily accept a loafer traveling in any direction, but I'll be really surprised if it's not traveling to the right!

It would be pretty painful to solve this by trying all possible single-cell moves (scripts being forbidden) -- but a lot of options don't have to be tried because they would only modify one of the still lifes. Seems like it should also be possible to guess at the purpose of several of the still lifes in the constellation, to eliminate them from consideration...?

Re: [Forum Game] CA Puzzles

PostPosted: December 16th, 2016, 8:27 pm
by gameoflifeboy
dvgrn wrote:Move just one cell in the following stable constellation by the minimum distance (one step orthogonally, not diagonally) so that when the pattern is run 200 ticks, the result is a loafer traveling to the right, and nothing else:


Here:
x = 46, y = 45, rule = LifeHistory
22.2A$21.A2.A$21.A2.A$22.2A3$33.2A$33.2A$29.2A$22.A5.A.A$21.A.A4.2A$
21.2A4$.2A$A.A17.2A$.A17.A2.A$19.A2.A19.2A$20.2A3.2A15.A$25.2A16.3A$
45.A2$14.2A$14.A.A$10.2A3.A.A$9.A.A4.A$10.A9.A$19.A.A$20.2A3$21.2AC$
13.2A6.A.D$13.A.A6.A$14.2A$.2A$.A.A$2.A.A$3.A2$15.2A$14.A.A$14.A$13.
2A!

Re: [Forum Game] CA Puzzles

PostPosted: December 16th, 2016, 11:07 pm
by Saka
What does this say?
x = 11, y = 11, rule = B3/S23
5bo$5bo$5bo$bo3bo$b3obob3o$bo6b2o2$bo$bo7bo$2ob4ob3o$o4bo3bo!

Hint: Conway

Re: [Forum Game] CA Puzzles

PostPosted: December 16th, 2016, 11:46 pm
by drc
Saka wrote:What does this say?
x = 11, y = 11, rule = B3/S23
5bo$5bo$5bo$bo3bo$b3obob3o$bo6b2o2$bo$bo7bo$2ob4ob3o$o4bo3bo!

Hint: Conway

Top syx?

Edit: That's a nice long long boat you got there.

Re: [Forum Game] CA Puzzles

PostPosted: December 17th, 2016, 12:39 am
by Saka
drc wrote:
Saka wrote:What does this say?
x = 11, y = 11, rule = B3/S23
5bo$5bo$5bo$bo3bo$b3obob3o$bo6b2o2$bo$bo7bo$2ob4ob3o$o4bo3bo!

Hint: Conway

Top syx?

There was no I pentomino in conway's alphabet so I had to resort to syx :cry:

Re: [Forum Game] CA Puzzles

PostPosted: December 17th, 2016, 1:17 pm
by Rhombic
Let's follow the order, it's gameoflifeboy's turn to post a puzzle

Re: [Forum Game] CA Puzzles

PostPosted: December 17th, 2016, 1:49 pm
by gameoflifeboy
Oh, I have a good one. It's pretty hard, though.

If multiplication is defined for patterns such that the following relations hold...

x = 51, y = 56, rule = B3/S23
8bo5bo$9bo3bo$2b2o6bobo6b2o4b7o5bobo$2b2o7bo6bo2bo14bo3bo$10bobo6b2o4b
7o4bo3bo$9bo3bo23bobo$8bo5bo20$7bo5bo19b3o$3bo4bo3bo$3bo5bobo5b3o3b7o
3b3o$3bo6bo6b3o13b3o$3bo5bobo5b3o3b7o3b3o$3bo4bo3bo$7bo5bo19b3o14$9bo
5bo$10bo3bo25bobobobobobo$b6o4bobo5b6o3b7o$o5bo5bo5bo5bo13bo11bo$6bo4b
obo10bo3b7o$o4bo4bo3bo3bo4bo26bo$2b2o5bo5bo4b2o$38bo9bo2$42bobo!


...which two tetraplets can this figure be factorized into?

x = 5, y = 4, rule = B3/S23
2b3o$o2b2o$4bo$4bo!


Hint: This multiplying function only deals with the initial generations of each pattern. In fact, it's independent of the rule set.

Re: [Forum Game] CA Puzzles

PostPosted: December 18th, 2016, 8:25 am
by calcyman
gameoflifeboy wrote:Oh, I have a good one. It's pretty hard, though.

If multiplication is defined for patterns such that the following relations hold...

x = 51, y = 56, rule = B3/S23
8bo5bo$9bo3bo$2b2o6bobo6b2o4b7o5bobo$2b2o7bo6bo2bo14bo3bo$10bobo6b2o4b
7o4bo3bo$9bo3bo23bobo$8bo5bo20$7bo5bo19b3o$3bo4bo3bo$3bo5bobo5b3o3b7o
3b3o$3bo6bo6b3o13b3o$3bo5bobo5b3o3b7o3b3o$3bo4bo3bo$7bo5bo19b3o14$9bo
5bo$10bo3bo25bobobobobobo$b6o4bobo5b6o3b7o$o5bo5bo5bo5bo13bo11bo$6bo4b
obo10bo3b7o$o4bo4bo3bo3bo4bo26bo$2b2o5bo5bo4b2o$38bo9bo2$42bobo!


...which two tetraplets can this figure be factorized into?

x = 5, y = 4, rule = B3/S23
2b3o$o2b2o$4bo$4bo!


Hint: This multiplying function only deals with the initial generations of each pattern. In fact, it's independent of the rule set.


You're treating these as polynomials in {x, y} with coefficients over F_2. Any semi-decent computer algebra package can factorise it into:

(1 + x y + x^2 y + y^2)(1 + x + x^2 + y)

in other words:

x = 11, y = 3, rule = B3/S23
2bo5b3o$2o8bo$2bo!


Amusingly, I had already implemented your 'multiplication' operation as a function:

pattern xor_convolve(const pattern &other)


in my CA library. (Basically, the functionality came for free once I'd implemented the ordinary convolve() used for pattern matching; the difference is whether OR or XOR is used.)

Re: [Forum Game] CA Puzzles

PostPosted: December 18th, 2016, 4:12 pm
by gameoflifeboy
That's exactly right!!! And it's how I would solve it too! (If I could, that is... I didn't know of any quick ways to factorize polynomials whose coefficients were only given mod 2.) I actually thought of the polynomial connection a few days after I thought of this way to multiply patterns. It even works when the placing of the patterns doesn't matter, all that needs to happen is for the object the polynomial represents to be invariant under multiplication by x^a*y^b.

Re: [Forum Game] CA Puzzles

PostPosted: December 19th, 2016, 5:54 am
by Saka
So, next puzzle?

Re: [Forum Game] CA Puzzles

PostPosted: December 28th, 2016, 12:04 pm
by Rhombic
Since nobody has posted the next puzzle yet, I'll do it myself to get the ball rolling:

1) Add a single cell so this pattern dies (final population=0)
2) Add another blinker to your first solution in a way that the pattern still dies.
(NB. the blinker you add should not interact with other nearby blinkers in at least 3 generations)

x = 38, y = 46, rule = B3/S23
15bo$7b3o5bo$15bo$34bo$19b3o6b3o3bo$8b3o2bo20bo$13bo$13bo$28bo$28bo$
28bo$b3o5b3o5b3o2$13bo10b3o$13bo6bo14b3o$3o10bo6bo$20bo2$8bo$bo6bo$bo
6bo11bo11b3o$bo18bo$10bo9bo$10bo4b3o$10bo$28bo$b3o24bo$28bo5bo$16bo4b
3o10bo$16bo17bo$16bo$bo4bo16bo12bo$bo4bo16bo12bo$bo4bo16bo12bo$33bo$
10b3o20bo$2bo30bo$2bo23b3o$2bo13b3o3$29bo3bo$29bo3bo$16bo6b3o3bo3bo$
16bo$16bo!

Re: [Forum Game] CA Puzzles

PostPosted: December 28th, 2016, 4:03 pm
by biggiemac
I tried TL conversions on all blinkers until I found one that worked. Then I found places a spark could destroy a distant blinker.

Ta-da!
x = 98, y = 46, rule = B3/S23
15bo59bo$7b3o5bo51b3o5bo$15bo59bo$34bo59bo$19b3o6b3o3bo44b3o6b3o3bo$8b
3o2bo20bo33b3o2bo20bo$13bo59bo$13bo59bo$28bo59bo$28bo59bo$28bo59bo$b3o
5b3o5b3o41b3o5b3o5b3o2$13bo10b3o46bo10b3o$13bo6bo14b3o35bo6bo14b3o$3o
10bo6bo39b3o10bo6bo$20bo59bo2$8bo59bo$bo6bo52bo6bo$bo6bo11bo11b3o26bo
6bo11bo11b3o$bo18bo40bo18bo$10bo9bo49bo9bo$10bo4b3o52bo4b3o$10bo59bo$
28bo59bo$b3o24bo32b3o24bo$28bo5bo53bo5bo$16bo4b3o10bo41bo4b3o10bo$16bo
17bo41bo17bo$16bo59bo$bo4bo16bo12bo24bo4bo16bo12bo$bo4bo16bo12bo24bo4b
o16bo12bo$bo4bo16bo12bo24bo4bo16bo12bo$33bo59bo$10b3o20bo21bo14b3o20bo
$2bo30bo21bo6bo30bo$2bo23b3o26bo6bo23b3o$2bo13b3o43bo13b3o2$17bo59bo$
29bo3bo55bo3bo$29bo3bo55bo3bo$16bo6b3o3bo3bo42bo6b3o3bo3bo$16bo59bo$
16bo59bo!


I'll edit this momentarily with another puzzle.

Re: [Forum Game] CA Puzzles

PostPosted: January 5th, 2017, 11:32 am
by Rhombic
Have you made the puzzle yet?

Re: [Forum Game] CA Puzzles

PostPosted: January 5th, 2017, 2:01 pm
by biggiemac
I have had an idea for the puzzle for a while but have been busy moving and haven't gotten around to making a concrete problem.

CGoL has no preferred cell - it has discrete translational and rotational symmetry. However, say we made a slight modification. Add a preferred cell that doesn't behave correctly. That particular cell, instead of following B3/S23, follows the exact opposite rule B01245678/S0145678. Evolution of this style can be achieved without scripts in golly by pressing space to advance the generation, then clicking the preferred cell to toggle its state. Let's call the preferred cell the origin.

Clearly in this universe, any patterns which never come close to the origin behave exactly as they do in CGoL. My hopes were to use some predecessor finding script to give a distant predecessor to a loafer in this rule, but leave it unclear which cell was the origin. The puzzle would be to find out where to place the predecessor such that a loafer escaped. But I never set up the tools to find that predecessor.

Instead, have the following. In the rule above, the ash of a particularly-placed stairstep hexomino includes an oscillator not present in CGoL. Find the placement of the stairstep hexomino, and give the result in the form below where the red dot denotes the origin. (The example evolves into a beehive and dot rather than a new oscillator, so is not a solution).

x = 4, y = 3, rule = LifeHistory
2A.D$.2A$2.2A!


There may be more than one solution but I know there is at least one.

NB: Just for clarity, the following two patterns are not oscillators in this rule, but rather still lives.
x = 12, y = 5, rule = LifeHistory
9.A$8.A.A$AD5.A.C.A$2A6.A.A$9.A!

Re: [Forum Game] CA Puzzles

PostPosted: January 6th, 2017, 8:20 am
by Gamedziner
That would be a three-state rule.

Re: [Forum Game] CA Puzzles

PostPosted: January 6th, 2017, 1:06 pm
by _zM
Four-state!

Re: [Forum Game] CA Puzzles

PostPosted: January 6th, 2017, 3:45 pm
by biggiemac
It can be implemented as a four-state rule, in which the origin only ever has states 2 and 3 while the rest of the universe is always states 0 and 1. However, the multistate rule would allow starting configurations with more than one cell in state 2 or 3. I prefer to think of it as just standard CGoL with a single defect for symmetry breaking.

You can certainly write the rule table for it as a 4-state rule to aid in solving the problem. You can also write scripts to aid in evolving patterns, such as the one I have been using:
import golly as g
for _ in range(100):
   g.run(1)
   g.setcell(0, 0, 1 - g.getcell(0, 0))
   g.update()

Re: [Forum Game] CA Puzzles

PostPosted: January 17th, 2017, 7:02 am
by Rhombic
In case anyone wants a rule file (so that apart from this challenge you can play around with more mirror cells)
@RULE Mirrors

@TABLE

n_states:4
neighborhood:Moore
symmetries:permute

var a={0,1,2,3}
var a2=a
var a3=a
var a4=a
var a5=a
var a6=a
var a7=a
var a8=a
var l={1,3}
var l2=l
var l3=l
var l4=l
var l5=l
var l6=l
var l7=l
var l8=l
var d={0,2}
var d2=d
var d3=d
var d4=d
var d5=d
var d6=d
var d7=d
var d8=d

#BIRTH
0,l,l2,l3,d,d2,d3,d4,d5,1
2,a,a2,d,d2,d3,d4,d5,d6,3
2,l,l2,l3,l4,a,a2,a3,a4,3

#SURVIVE
1,l,l2,a,d,d2,d3,d4,d5,1
3,a,d,d2,d3,d4,d5,d6,d7,3
3,l,l2,l3,l4,a,a2,a3,a4,3

#CAT
1,a,a2,a3,a4,a5,a6,a7,a8,0
3,a,a2,a3,a4,a5,a6,a7,a8,2

@COLORS

1 255 255 255
2 35 35 35
3 225 255 255


Trans-boat with tail
x = 8, y = 10, rule = Mirrors
7.C6$A$2A$.2A$2.A!

Re: [Forum Game] CA Puzzles

PostPosted: January 17th, 2017, 5:07 pm
by drc
Found it:
x = 8, y = 4, rule = Mirrors
C$6.2A$5.2A$4.2A!


what do i win?

EDIT: pass

Re: [Forum Game] CA Puzzles

PostPosted: January 17th, 2017, 5:58 pm
by Kiran
drc wrote:what do i win?

The right to post the next puzzle, or to name someone else if you want to pass it up.

Re: [Forum Game] CA Puzzles

PostPosted: January 31st, 2017, 12:11 am
by dvgrn
Seeing a "pass" above, I'll sneak in with a puzzle that I ran into today, and found very entertaining:

The attached ZIP file is an attempt at making Calcyman's stable megacell pattern simulate the Just Friends rule. It doesn't quite work at the moment -- if you run megafier.lua, you get nothing but OFF megacells forever. I've also thrown in a megafier.py, so anyone who isn't running Golly 2.9b1 can try it out.

megacell-AlmostFriends.zip
Remove one cell from megacell-ON.rle, save the file, and megafier.lua/py should work...
(353.33 KiB) Downloaded 95 times

The question is: how can you remove one cell from megacell-ON.rle to make a megafier.lua that works correctly? Careful comparison with the original B3/S23 megacells may be useful here.

[Hint 1: However, it's better to compare the old OFF cell with the new ON cell: the problem is not the differences between the Life and Just-Friends ON cells, but the similarities!]

Code: Select all
x = 10, y = 15, rule = B2-a/S12
$6bo$6bo$2b3o$6bobo$8bo2$4bo2$2bo3bo2$3bobo2$b7o!
#C [[ THUMBNAIL AUTOSTART GPS 20 ]]

Hint 2: The architectural details described here should give plenty of pointers in the right direction.
Hint 3: there are two equally good solutions. I don't think there are more than two.

Re: [Forum Game] CA Puzzles

PostPosted: March 7th, 2017, 2:21 pm
by Rhombic
Did anyone have a go?

Re: [Forum Game] CA Puzzles

PostPosted: March 8th, 2017, 5:28 pm
by dvgrn
Rhombic wrote:Did anyone have a go?

Apparently not. Anyone who spends a little time figuring out how the megacell works -- e.g., where exactly NEIGHBOR-ON signals from adjoining megacells are stored until they're needed -- shouldn't have much trouble with this puzzle... though there is an entertaining extra detail about the megacell being programmed to simulate the non-totalistic isotropic Just Friends rule.

I can certainly give more hints if anyone wants them, but there are plenty in the original post. Was mostly just trying to stop the thread from dying due to an edited-in "pass", but it seems that didn't work out!

If anyone wants to post a different challenge, please go ahead. Maybe it would work better to have easy, medium, and difficult challenges going on simultaneously, so the thread doesn't get stuck on tough cases...?

If this idea meets with the approval of the Thread Creator, then perhaps my Almost Friends puzzle could be dumped into the "medium" slot. (It's just not hard enough to be "difficult", though it would certainly take a long time to solve it by removing randomly chosen cells...)