3
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Sorry, that was a posting error. The for loop should have been indented. I fixed it \$\endgroup\$ – Cyn Nov 17 '14 at 3:24
  • \$\begingroup\$ 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)] \$\endgroup\$ – smac89 Nov 17 '14 at 3:25
  • \$\begingroup\$ You might find this interesting : youtube.com/watch?v=o9pEzgHorH0 . \$\endgroup\$ – Josay Nov 17 '14 at 9:00
2
\$\begingroup\$

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".

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.