# The Game of Life

The Game of Life is a popular celular automaton that simulates the births and deaths of a population over time. Your task is to code an efficient implementation of the transition function. The rules of the game are the following.

The game models the population by means of a grid. Although the original game considers the infinite grid, we consider a finite grid so that anything outside the corresponding bounds is ignored. Consider the following example.

The cells marked with a dot are alive and the cells that are empty are dead.

Every cell, alive or dead, has up to 8 alive neighbors. The following diagram shows the neighbor cells of the cell marked with the green dot.

Time pases in discrete steps and each step corresponds to a configuration of the grid. The rules that govern the transition from one configuration to another are the following.

- When a cell is alive and
- it has less than 2 neighbors, it dies.
- it has more than 3 neighbors, it dies.
- it has 2 or 3 neighbors, it remains the alive.

- When a cell is dead and
- it has 3 neighbors, it becomes alive.
- it has more or less than 3 neighbors, it remains dead.

For example, the following configuration is the successor of our previous example grid.

Because we find configurations that are have few alive cells more interesting, anything that you can do to improve performance for very large grids is welcome.

**Input.**
The input consists of the size of the grid, followed by an initial
configuration, followed by a number indicating the amount of steps to
take from the initial step. The size of the grid is given on a single
line as a pair of numbers, the The initial configuration begins with a
number `n`

on a separate line, the amount of cells that are alive.
The rest of the initial configuration consits of `n`

pairs of numbers,
each on a separate line. The first number of each pair indicates the
row and the second the column of a cell that is alive. The last line
of the input is the amount of steps `s`

to take from the initial
configuration.

**Output.**
The output consists of a sequence of pairs of row and column that
corresponds to the cells that are alive after `s`

steps. Each pair
appears on a separate line.

# Naive solution

A naive approach consists in counting the neighbors of each cell in the grid and then applying the rules to each cell. Consider the following configuration.

The count neighbors that correspond to each cell of the current configuration are the following.

When we consider each count of neighbors, we find that only the following two cells are alive in the next configuration.

The following is the configuration we obtain by considering each count of neighbors.

The following is a Ruby implementation of our naive approach.

The main function takes care of reading the initial configuration and
number of steps. Function `step`

implements the transition function
for the automaton. Function `step`

considers the count of neighbors
and the state for each cell and acts accordingly. Function
`neighbors`

counts the neighbors for a given cell. Function
`neighbors`

uses function `populated_cells`

to count alive cells out
of the indicated cells in the given row.

The time and space complexity of this approach is `O( rows * cols )`

.

# Efficient solution

A more efficient approach is to only consider the neighbors of cells that are alive to determine the cells that are alive in the next configuration. Consider the following configuration.

For each alive cell, we increase the count of neighbors for the corresponding neighbors. The following diagram shows the count of neighbors for neighbors of the cells that are alive.

In the diagram, the neighbors corresponding to each alive cell are marked with lines of the same color as the alive cell.

Given the counts of neighbors, we consider each and the corresponding cell in the current configuration to determine if the cell should be alive in the successor configuration. The circled counts in the next diagram correspond to alive cells in the successor configuration. Note that it is unnecessary to consider the cell in the bottom-left corner, something we would have done in the naive approach.

The following is a Ruby implementation of our efficient approach.

Function `step`

computes the counts of neighbors using function `increase_cells`

. Function `increase_cells`

increases the cells on the given row as long as they are within bounds.

The time and space complexity of this approach is ```
O( alive
cells )
```

.