## Pages

### CodeEval Game of Life

In input we get a string representing the board of the game of life at a given step, we have to give back a string representing the same board after ten iterations. For more detail on the game rules, and to submit your solution, check the CodeEval problem #161.

Before thinking on how to implement my Python 3 solution, I have converted the given sample in a test case:
```def test_provided_1(self):
data = '.........*\n' \
'.*.*...*..\n' \
'..........\n' \
'..*.*....*\n' \
'.*..*...*.\n' \
'.........*\n' \
'..........\n' \
'.....*..*.\n' \
'.*....*...\n' \
'.....**...\n'
output = '..........\n' \
'...*......\n' \
'..*.*.....\n' \
'..*.*.....\n' \
'...*......\n' \
'..........\n' \
'..........\n' \
'..........\n' \
'..........\n' \
'..........\n'
self.assertEqual(output, solution(data))
```
I am going to need a few constants:
```STEPS = 10
ALIVE = '*'
```
STEPS represents the number of iterations I want to run on the input sequence. DEAD and ALIVE should have a clear meaning.

Then I wrote a simple python function, that converts the input string in a squared matrix (remember, in the fantastic world of CodeEval we can forget about error handling), use it to start a ten times loop on a function that implements a round in the game, convert back the 2D list to a string, and return it.
```def solution(data):
step = [list(row) for row in data.rstrip().split('\n')] # 1

for i in range(STEPS):
step = next_iteration(step) # 2

result = [] # 3
for row in step:
result.append(''.join([c for c in row]))
return '\n'.join(result) + '\n'
```
1. Firstly, I have right-stripped the input data, because I want to get rid of the final newline, then I split it on new lines, getting a list of strings, each of them representing a row in the board. Finally, I convert each row in a list of single characters.
2. Call STEPS times the function implementing a round in the game. Notice it passes in input the board representation, and gets back its new status.
3. Convert back the bidimensional list to a plain string. Firstly each row is joined to a string, then all the rows are joined on a newline. Finally a last newline is added at the end.

Let's play the game!
```def next_iteration(matrix):
next_step = [] # 1
for i in range(len(matrix)):
row = []
for j in range(len(matrix[0])):
count = local_population(matrix, i, j) # 2
if matrix[i][j] == ALIVE: # 3
row.append(ALIVE if 1 < count < 4 else DEAD)
else:
row.append(ALIVE if count == 3 else DEAD)
next_step.append(row)
return next_step
```
1. I am going to push the new value for each cell to a new board.
2. For each cell, I count how many neighbors are alive. It's a bit tricky piece of code, so I put it in a function on its own.
3. Accordingly to the rules of the game, a cell gets dead or alive based on its current status and its neighbors' one. So, if it is alive, and it has 2 or 3 neighbors, it stay alive, otherwise it dies. If it is dead, and there are three neighbors, it springs to life.

And here I check the neighborhood:
```def local_population(matrix, i, j):
result = 0
for row in [i-1, i, i+1]:
for col in [j-1, j, j+1]:
if 0 <= row < len(matrix) and 0 <= col < len(matrix) \
and not (row == i and col == j) \
and matrix[row][col] == ALIVE:
result += 1
return result
```
I check the cells in the square around position [i,j]. However I don't have to check [i,j] itself, and I should avoid to go out of the board. For each cell nearby that is alive, I increase the neighbor counter.

It took some time to get the OK from CodeEval, given the O(n**2) nature of the solution, I suspect. Anyway, it worked fine and I have got full marks. So I pushed test case and python script to GitHub.