The universe of the Game of Life is an infinite two-dimensional orthogonal grid of square cells, each of which is in one of two possible states, alive or dead. Every cell interacts with its eight neighbours, which are the cells that are horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:
- Any live cell with fewer than two live neighbours dies, as if caused by underpopulation.
- Any live cell with two or three live neighbours lives on to the next generation.
- Any live cell with more than three live neighbours dies, as if by overpopulation.
- Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.
The initial pattern constitutes the seed of the system. The first generation is created by applying the above rules simultaneously to every cell in the seed—births and deaths occur simultaneously. The rules continue to be applied repeatedly to create further generations. (Source: Wikipedia )
For this challenge, we will modify a few rules:
- The grid is not infinite. We will provide in the inputs the size of the grid. It will not act as a Torus nether.
- The game stops when the grid reach a state it has already reached before. This prevents patterns infinite loop and can manage empty grids too.
Write a program/function that takes four positive integer as input:
x: starting pattern width
y: starting pattern height
n: grid width
m: grid height
and finds the starting pattern that will generate the most amount of cells through the whole game, and outputs that number. (You can also outputs the corresponding pattern if needed)
The patterns is always centered on the grid. If you need to center with odd numbers, the pattern should be slightly closer to the upper left corner. Refer to that drawing for better understanding where the green area is the pattern already centered:
- Standard I/O rules apply.
- Standard loopholes are forbidden.
- This challenge is not about finding the shortest approach in all languages, rather, it is about finding the shortest approach in each language.
- Your code will be scored in bytes, usually in the encoding UTF-8, unless - specified otherwise.
- Explanations, even for "practical" languages, are encouraged.
Let's do a small example together. For this example, the pattern size will be
x = y = 3 and the grid size will be
n = m = 3
The program will test any possible starting pattern. After running it, we find that the maximum amount of generated cells during one whole game is
It is obtained following those steps:
Green cells are alive, lime cells are newborn and brown cells just died. One out of two grid is just the transition between two states. The starting pattern is the first state of the game, in the upper left corner. The game ended when there was no living cells left, but most of the time the game end with a repeating infinite pattern.
Here we can get to
11 by counting every lime cells during the transitions. It corresponds to the total amount of generated cells through the whole game.
Input Output 3 3 3 3 11, *[[0, 0, 1], [1, 1, 0], [0, 0, 1]] 3 3 5 5 46, *[[0, 0, 1], [1, 1, 1], [0, 0, 1]] 3 3 12 12 596, *[[1, 0, 1], [1, 1, 1], [1, 1, 1]] 2 3 6 3 18, *[[0, 1], [1, 1], [0, 1]] 3 2 5 5 34, *[[0, 1, 0], [1, 1, 1]] 4 4 9 9 1067, *[[1, 0, 1, 1], [1, 1, 0, 1], [0, 0, 0, 1], [1, 0, 1, 1]]
* not needed, just here to help you debugging
Thank you @totallyhuman for your Fibonacci Sequence post, from which I borrowed the presentation style. I found it very clear and I hope you don't mind me using the same layout ;)
This challenge differs from basic Game of Life implementation since it asks to test out every starting pattern possible, count the number of generated cells for each of those and check for infinite repeating pattern.