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_step1. 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 resultI 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.

## No comments:

## Post a Comment