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 = '*'
DEAD = '.'

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.