# Conway's Game of Life without objects

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,point,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,item) if x not in to_check and x not in cells ]
to_check += checking

for item in to_check:
if neighbors_count(item,item,cells) == 3:
to_add[(item,item)] = 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 < size and 0 <= point < size:
grid[point][point] = 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

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

## 1 Answer

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,item) 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,item,cells) == 3:
to_add[(item,item)] = 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".