Find a Glider Synthesis (Game of Life)

11

1

Challenge Summary

In summary, the challenge is to provide the glider synthesis for a Game of Life configuration, which is your input.

What does this mean?

Well, firstly, let me explain a few terms.

By Game of Life, I mean Conway's Game of Life. If you don't know what this is, you can read the Wikipedia article at https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life. It explains it pretty well.

If you don't know what a glider synthesis is, it's pretty much a bunch of gliders that will form a specific configuration after a certain number of steps. Read http://www.conwaylife.com/wiki/Glider_synthesis for more details.

Okay, what are the rules?

  • Standard Loopholes Apply
  • The glider synthesis must only consist of the standard 5-cell gliders, but they can start in any of their 4 states/colors.
  • The glider synthesis is allowed to create other things, as long as they do not share a neighbor with and are not a neighbor of any living cell within the desired outcome. Moving structures can be created as byproducts as well.
  • The desired outcome will be at most 10x10.
  • The desired outcome will be achievable with a glider synthesis.

Actual Specifics

Input will be given as a 2D array of truthy/falsy values, which indicates the desired outcome (the desired outcome will be reachable). The array will be at most 10 by 10 in size. The desired outcome will not necessarily be a stable configuration. Output will also be given in the same format, indicating a valid glider synthesis (as defined by the rules above) to produce this outcome (the output can be as large as necessary). The output doesn't have a size limit. It doesn't necessarily need to be the fastest or the smallest; as long as it's valid, it's fine.

Summary of Everything

You will be given input as a 10x10 or smaller 2D array of truthy/falsy values of some sort. This could be a 2D array of something, an array of strings, a multi-line string, etc. Your task is to find a configuration using only standard 5-cell diagonal gliders that will eventually result in this outcome, where other byproducts are permitted so long as they do not interact in any way with the desired outcome. Given this configuration, you are to output a 2D array of truthy/falsy values in some format.

Winning

This is a code-golf challenge, so the shortest program will win. Tiebreak is by earlier submission.

In terms of test cases, you can just put the program output into a GoL emulator and run it and see if you get the desired output eventually.

Tips/Ideas

I don't have many well developed ideas myself, but what you could try to do is find all possible reverses of a GoL scenario (i.e. find all configurations that could evolve to the current one), though that's going to take a lot of power quickly.

HyperNeutrino

Posted 2017-01-23T13:19:30.527

Reputation: 26 575

14What makes you think that this is even possible? – orlp – 2017-01-23T13:21:21.863

1Can the input be unreachable? What the max size of the array we are allowed to output (if any)? – Sefa – 2017-01-23T13:23:32.573

1@orlp Nothing is impossible... – user41805 – 2017-01-23T13:40:37.623

@orlp Nothing. I'm not sure this is possible. However, brute-forcing will technically work, but it will take practically forever to get a solution. – HyperNeutrino – 2017-01-23T14:33:46.783

@Sefa Edited answers into question. The input will always be possible, and the output has no limit. – HyperNeutrino – 2017-01-23T14:34:13.480

12@KritixiLithos Solve the halting problem. Go. – mbomb007 – 2017-01-23T14:57:29.150

1@mbomb007 It's possible if you have infinite time, which is probably what you'll need for this one too. – PurkkaKoodari – 2017-01-23T16:01:50.873

1https://cgl.herokuapp.com/?rule=23/3&seed=bo%24o%243o If you want, you can use this program to verify solutions. seed is formatted as standard RLE encoding for automaton files. For example, like the last 3 lines on this one: https://cgl.herokuapp.com/patterns/gosperglidergun Exclamation to terminate the seed is unnecessary in the query parameter though – Patrick Roberts – 2017-01-23T16:49:17.777

Someone with more time on their hands than I have might find http://www.conwaylife.com/wiki/Category:Pattern_constructible_by_a_given_number_of_gliders useful.

– Mitchell Spector – 2017-01-23T20:33:31.560

a 10x10 array of black/white squares is not 100 test cases, it is 2^100 test cases which is a slightly larger number ;) – Sparr – 2017-01-23T21:07:45.070

@Sparr Yeah... I just realized that too... I don't think my brain was working earlier. – HyperNeutrino – 2017-01-23T21:13:06.080

We cant even reverse game of life, do you think this is possible? – Matthew Roh – 2017-01-24T00:16:10.873

@MatthewRoh Given enough time, it is possible, though it's probably NP-complete (which is why I said given enough time). – HyperNeutrino – 2017-01-24T02:02:46.760

This is not possible, for all configurations at least: some GoL configurations have no predecessor. See garden of eden. And if you're given only gliders as a starting point, you're certainly even more limited. Finally, solving this for the configurations where it is possible is non trivial. A more feasible challenge would be to output the initial gliders to draw a still character string given as input on the grid.

– dim lost faith in SE – 2017-03-03T15:01:47.033

@dim I realize now that the challenge is rather unfeasible challenge. And thanks for the link! But in this challenge, you can assume everything has a valid glider synthesis. – HyperNeutrino – 2017-03-03T20:41:43.783

You would have to allow that programs don't need to terminate for this to be possible – MilkyWay90 – 2019-01-14T04:06:34.160

@MilkyWay90 how so – HyperNeutrino – 2019-01-14T17:11:07.743

@HyperNeutrino Conway's Game of Life has been proven to be Turing-Complete, hence unsolvable without infinite time (A Turing Machine needs infinite time to solve the halting problem for it, because the Busy Beaver function is uncomputable) – MilkyWay90 – 2019-01-14T17:19:10.973

1@MilkyWay90 I'm sorry, you're going to have to explain that in simpler terms. You just threw like three concepts that I only vaguely know that don't seem related to each other or the challenge in any way to me. – HyperNeutrino – 2019-01-15T16:21:44.533

@HyperNeutrino Wait nevermind, I was wrong – MilkyWay90 – 2019-01-16T00:07:52.580

No answers