Conway's Game of Life without objects

Question

I was wondering if anyone could provide some feedback on my solution to Conway's game of life. I tried to solve it without using objects. It returns a dictionary of living points on a grid and points that were alive at some point. I'm wondering if there is a better way to check the surrounding points or if storing the active points in a dictionary is a bad idea.

def list_to_check(x,y):
 return [(x + 1, y),
 (x - 1, y),
 (x +1, y +1 ),
 (x -1, y -1 ),
 (x +1, y -1 ),
 (x -1, y +1 ),
 (x, y+1),
 (x, y-1)]
def neighbors_count(x,y,cells):
 count = 0
 for item in list_to_check(x,y): 
 if item in cells:
 count += cells[item]
 return count 
def next_state(cells):
 next_state = {}
 for point in cells.keys():
 alive = cells[point] == 1
 neighbors = neighbors_count(point[0],point[1],cells)
 if not alive and neighbors == 3:
 next_state[point] = 1
 elif neighbors > 3 or neighbors < 2:
 next_state[point] = 0
 return next_state
def add_to_grid_alive(cells):
 to_check = []
 to_add = {}
 for item in cells.keys():
 checking = [ x for x in list_to_check(item[0],item[1]) if x not in to_check and x not in cells ]
 to_check += checking
 for item in to_check:
 if neighbors_count(item[0],item[1],cells) == 3:
 to_add[(item[0],item[1])] = 1
 return to_add
def tick(cells):
 changes = next_state(cells)
 expansions = add_to_grid_alive(cells)
 cells.update(changes)
 cells.update(expansions)
 [ cells.pop(point,None) for point in cells.keys() if cells[point] == 0 ]
def print_grid( size, cells):
 grid = []
 for y in range(size):
 grid.append([])
 for x in range(size):
 grid[y].append(0)
 for point in cells.keys():
 if 0 <= point[0] < size and 0 <= point[1] < size:
 grid[point[1]][point[0]] = cells[point] 
 return grid
#testing
def load_list(inputs):
 point_dict = {}
 for point in inputs:
 point_dict[point] = 1
 return point_dict
inputs = [(1,2),(2,2),(3,2),(2,3),(3,3),(4,3),(13,2),(13,3),(12,3),(13,4)]
test_array_dict = load_list(inputs)
for x in range(20):
 print '>>>>>>>>>>>>>>>>>>>>', x + 1
 for item in print_grid(20,test_array_dict)[::-1]:
 print item
 tick(test_array_dict)

Update

I added [ cells.pop(point,None) for point in cells.keys() if cells[point] == 0 ] to the tick function and it really sped up the the code on higher iterations

• Cyn: Sorry, that was a posting error. The for loop should have been indented. I fixed it
• smac89: Ok got it, just wanted to add that you can shorten both for-loops to something like this grid = [[0] * size for _ in range(size)]
• SylvainD: You might find this interesting : youtube.com/watch?v=o9pEzgHorH0 .

Answer 1

You're representing the cells mainly using a dictionary of coordinates, converting to a two-dimensional array only for the purposes of printing the output. That is a good representation for sparse boards, but not so much for crowded boards.

The algorithm that you use, though, is cumbersome, particularly illustrated by these few lines:

for item in cells.keys():
 checking = [ x for x in list_to_check(item[0],item[1]) if x not in to_check and x not in cells ]
 to_check += checking

In other words, make a list of the neighbors of each cell, but make sure that each coordinate is listed just once. Then, once you have that list to_check, what do you do with it?

for item in to_check:
 if neighbors_count(item[0],item[1],cells) == 3:
 to_add[(item[0],item[1])] = 1

You count each cell's neighbors! But the number of neighbors is precisely the amount of overlapped processing that would have occurred had you not bothered to deduplicate the to_check list to begin with! So, instead of drawing a list of interesting cells and counting their neighbors, why not just have each existing cell increment the neighbor count of each neighboring coordinate?

In addition to the change in algorithm, I also recommend:

• Take advantage of list/set/dict comprehensions more.
• Represent the board as a set of live cells, rather than a dict.
• Rename list_to_check() to neighbors().
• Rename print_grid() to grid(), since it actually doesn't print anything.
• Construct the next state from scratch rather than by mutation: test_array_dict = tick(test_array_dict)

I'd rewrite three functions as follows (and eliminate neighbors_count(), next_state(), and add_to_grid_alive():

def tick(live_cells):
 """ Takes a set of coordinates of live cells, and returns a set of
 coordinates of the live cells in the next generation. """
 neighbor_count = {}
 for xy in live_cells:
 for neighbor in neighbors(*xy):
 neighbor_count[neighbor] = 1 + neighbor_count.get(neighbor, 0)
 return set(xy for xy in neighbor_count
 if neighbor_count[xy] == 3
 or xy in live_cells and neighbor_count[xy] == 2)
def grid(size, cells):
 return [[int((x, y) in cells) for x in range(size)] for y in range(size)]
def load_list(inputs):
 return set(inputs)

Actually, tick() would be even better written using a collections.Counter. I don't know if you consider that "using an object".