Let’s go all the way back to 1970 and to the Game of Life. Also known simply as Life, this program is based on cellular automaton and was devised by British mathematician John Horton Conway.
The rules of Life
The rules of Life are simple: The universe in which Life is played is an infinite, two-dimensional grid of square cells. Each cell has one of two possible states, on or off, filled or empty, live or dead.
Each cell interacts only with its eight neighbours. Neighbour cells are adjacent horizontally, vertically, and diagonally.
Cells stay alive when they have two or three neighbours. Live cells with fewer than two, or more than three, live neighbours die, as if by underpopulation or overpopulation. Dead cells with exactly three live neighbours become live cells, as if by reproduction.
The Goal of the LEDAS Life Contest
The goal is to build minimal configurations. Using several iterations (>0), we want to arrive at a configuration that gets as close to the target as possible.
Each live cell in an initial configuration costs three points. Each difference of the resulting configuration with the target one (Hamming distance) costs 11 points. So the goal is to find the cheapest configuration.
If we have two configurations with the same number of points, we compare the number of iterations: more steps is better.
Making LEDAS the Target
Let’s start the competition! In our case, the target configuration looks like this:
The target configuration
Here we have 48 live cells surrounded by an infinite number of empty (dead) cells. It costs 48 * 11 = 528 points to arrive at L E D A S from an empty field. You determine the number of points like this: The target configuration has 48 cells that differ from empty ones, and changing one costs 11 points.
But we can do better by starting with a non-empty field. If we start with an initial configuration that looks like the figure below, then it costs us 27 * 3 = 81 points to place the initial live cells (we start with 27 live cells, with each one costing us three points to place).
Starting configuration costing 81 points
After just one iteration of Life, we arrive at the following configuration:
The result of the first iteration
Let’s compare this result and the target:
First iteration shown in black, and difference with the target shown in red
This result costs us just 27 * 11 = 297 points, because we have 27 differences from the target configuration.
So, this one at 81 + 297 = 378 points is better than the 528 points it took to start from an empty field. Moreover, this configuration achieves the minimum cost within 378-point configurations, because it infinitely cycles between initial and final states. I.e. we arrive at the same result after 1, 3, or 5, and any odd number of steps.
LEDAS Life Contest
Can you achieve a lower score? You can start trying different configurations on sites like playgameoflife.com, but after this you’ll need Golly or another powerful system.
We invite readers of our blog to submit an original solution. Send your configurations to quiz@ledas.com. In your email, please include the number of iterations and the number of points.
We will post the names of all of you who submit a correct solution. (If you don't want your name posted, then please say so in your submission.) We look forward to seeing what you can come up with!
The table of results
1. Mikhail (5 * 11 + 43 * 3 = 184 points) - 14-Sep-2020
2. Polina (7 * 11 + 39 * 3 = 194 points) - 15-Sep-2020
3. Alex (7 * 11 + 40 * 3 = 197 points) - 10-Sep-2020
4. Mikhail (7 * 11 + 41 * 3 = 200 points) - 11-Sep-2020
5. Daria (18 * 11 + 34 * 3 = 300 points) - 3-Sep-2020
6. Nine line segments (27 * 11 + 27 * 3 = 378 points) - 1-Sep-2020
7. Empty field (48 * 11 = 528 points) - 1-Sep-2020