Conways's Game of Life: Most newborn generating starting pattern

Question

General rules

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 )

---

Specific rules

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.

---

Challenge

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:

---

Specifications

• 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.

---

Example

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 11.

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.

---

Test cases

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

Good luck..

---

Disclaimer

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.

Answer 1

Pyth, 65 63 bytes

M}3-BGHeSm+F.n<VVM.:.ugVVuCmsM.:++0k03G2NNd)2muCm.[Hk0GQd^^U2EE

Test suite

Input is taken as:

n,m
x
y

On the input 3,3,12,12, I got 594, not 596, with the same grid as the OP, so I'm not sure what's up.

How it works:

^^U2EE: Generate all possible patterns

muCm.[Hk0GQd: Pad them to the appropriate size. Written as pad, rotate, repeat.

uCmsM.:++0k03G2N: Generate the number of live neighbors for each cells. Written as pad, take subsequences of size 3, sum them, rotate, repeat.

M}3-BGH ... gVV ... N: Pair that with the original grid, use both to calculate the new cells. We do this by checking whether live neighbors including the center, optionally minus whether it was alive, contains a 3. I really like this VV trick, so I wrote a helper function (M}3-BGH) so I could do it twice. (see below)

.u ... d): Do that until it stops changing, return all intermediate steps.

.: ... 2: Take all consecutive pairs.

<VVM: Map each pair to the number of new cells born. I'm particularly proud of <VVM, I thought that was very clever.

m+F.n: Map each grid to its total number of cells born.

eS: Max