Kata

Conway's Game of Life

... is a 2d cellular automaton where each cell has 8 neighboors and one of two states: alive or dead.
After a generation passes each cell either stays alive, dies or is born according to the following rules:

• if a living cell has 2 or 3 neighboors it stays alive
• if a dead cell has exactly 3 neighboors it will be born
• otherwise a cell will stay dead or die

An example:

. X . .                     . . . .                     . . . .
. . X .        --->         X . X .        --->         . . X .
X X X .      X = alive      . X X .                     X . X .
. . . .      . = dead       . X . .                     . X X .

... In Reverse?

While determining the successor to a given pattern is straight forward, the reverse process is not. There is no simple rule to calculate a predecessor.
Also most patterns have multiple predecessors and some have no predecessors at all, so called 'Garden of Edens'.

The Task

You're given a pattern, represented as a list of lists of integers, where 1 = alive and 0 = dead.
Write a function that returns one valid predecessor.
Since most predecessors have a larger bounding box than their successors, your solution should have dimensions (m+2) x (n+2) for an input with dimensions m x n.
If there is no such predecessor return None.
Your solution is valid, if it's successor is the goal pattern with only dead cells surrounding it.

find_predecessor(goal: List[List[int]]) -> List[List[int]]


input_output_format = [[1,0,0,1,0]
                      ,[0,1,1,0,0]
                      ,[1,0,0,1,0]
                      ,[0,0,0,0,1]]

Notes

• For readability the patterns in the description and in the log are displayed with '.' and 'X', instead of 0 and 1
• The input pattern has dimensions mxn, m rows and n columns, 2 <= m,n < 8
• The world is finite. A corner cell for example has only 3 neighboors

Examples

                                               . . . . X . X
goal:  . . X X .      find_predecessor(goal):  . . . . . . .
       X X X X .                               . X X . X X .
       . . X X X                               X . . X . . .
                                               . . X . . . X
                                               
                                               
                                               X . . . . .
goal:  . . . .        find_predecessor(goal):  . . X . . .
       . X X .                                 . . . X . .
       . X X .                                 . . . X . .
       . . . .                                 . . X . . .
                                               X . . . . X

Some inspiration: https://nbickford.wordpress.com/2012/04/15/reversing-the-game-of-life-for-fun-and-profit/