A cellular automaton is a model used to simulate a wide variety of systems in science. We'll look at one that's supposed to simulate life itself, Conway's Game of Life. You have a two-dimensional rectangular grid of square cells, each of which can be either alive or dead. Each cell interacts with its eight nearest neighbors and evolves according to the following rules:

A live cell with less than two live neighbours dies (due to underpopulation).

A live cell with two or three live neighbours continues to live.

A live cell with more than three live neighbours dies (due to overpopulation).

A dead cell with exactly three live neighbours becomes a live cell (due to reproduction).

To deal with the finite size of the grid we'll impose periodic (or toroidal) boundary conditions, that is, to treat the left and right edges of the grid to be stitched together so that moving across the right boundary returns you to the left boundary (and we will do the same with the top and bottom edges).

Given an initial configuration for the grid, run the Game of Life simulation for $N$ time steps (also an input) and return the state of the grid.

Input:
A 2D integer array representing the grid where the dead cells are represnted by 0's and the alive cells are 1's, and a number of time steps $N$ to run the Game of Life for.

Output:
A 2D array representing the state of the grid after $N$ time steps.

Example input

This input should reproduce the video with the still life and oscillator patterns
N=30, board=
000000000000000000000000000000000000
011000001100000000000000000000000000
011000010010000000000001110001110000
000000001010000011100000000000000000
000000000100000000000100001010000100
000110000000000000000100001010000100
001001000001000000000100001010000100
000110000010100000000001110001110000
000000000001000011100000000000000000
000000000000000111000001110001110000
011000000000000000000100001010000100
011000000000000000000100001010000100
000110000000000000000100001010000100
000110000000000000000000000000000000
000000000000000000000001110001110000
000000000000000000000000000000000000
000000000000000000000000000000000000

LifeWiki has tons more information on the Game of Life, cool patterns, and the latest news (people are still discovering completely new patterns in 2018).