Game Of Life : How to keep track of active cells

Question

Now I have read the other stackoverflow Game of Life questions and also Googled voraciously.I know what to do for my Python implementation of the Game Of Life.I want to keep track of the active cells in the grid.The problem is I'm stuck at how should I code it.
Here's what I thought up but I was kinda at my wit's end beyond that:

• Maintain a ActiveCell list consisting of cell co-ordinates tuples which are active
  dead or alive.
• When computing next generation , just iterate over the ActiveCell list,compute cell state and check whether state changes or not.
• If state changes , add all of the present cells neighbours to the list
• If not , remove that cell from the list
• Now the problem is : (" . "--> other cell)
  B C D
. A .
. . .
  If A satisfies 3) then it adds B,C,D
  then if B also returns true for 3) ,which means it will add A,C again (Duplication)

I considered using OrderedSet or something to take care of the order and avoid duplication.But still these I hit these issues.I just need a direction.

Answer 1

don't know if it will help you, but here's a quick sketch of Game of Life, with activecells dictionary:

from itertools import product

def show(board):
    for row in board:
        print " ".join(row)

def init(N):
    board = []
    for x in range(N):
        board.append([])
        for y in range(N):
            board[x].append(".");
    return board

def create_plane(board):
    board[2][0] = "x"
    board[2][1] = "x"
    board[2][2] = "x"
    board[1][2] = "x"
    board[0][1] = "x"

def neighbors(i, j, N):
    g1 = {x for x in product([1, 0, -1], repeat=2) if x != (0, 0)}
    g2 = {(i + di, j + dj) for di, dj in g1}
    return [(x, y) for x, y in g2 if x >= 0 and x < N and y >= 0 and y < N]

def live(board):
    N = len(board)
    acells = {}
    for i in range(N):
        for j in range(N):
            if board[i][j] == "x":
                for (x, y) in neighbors(i, j, N):
                    if (x, y) not in acells: acells[(x, y)] = board[x][y]

    while True:
        print "-" * 2 * N, len(acells), "cells to check"
        show(board)
        raw_input("Press any key...")
        for c in acells.keys():
            a = len([x for x in neighbors(c[0], c[1], N) if board[x[0]][x[1]] == "x"])
            cur = board[c[0]][c[1]]
            if a == 0:
                del acells[c]                       # if no live cells around, remove from active
            elif cur == "x" and a not in (2, 3):
                acells[c] = "."                     # if alive and not 2 or 3 neighbors - dead
            elif cur == "." and a == 3:
                acells[c] = "x"                     # if dead and 3 neighbors - alive
                for x in neighbors(c[0], c[1], N):  # add all neighbors of new born
                    if x not in acells: acells[x] = board[x[0]][x[1]] 

        for c in acells:
            board[c[0]][c[1]] = acells[c]

N = 7
board = init(N)
create_plane(board)

live(board)

Answer 2

You have two lists, I'll name them currentState, and newChanges. Here will be the workflow:

1. Iterate over currentState, figuring out which are newly born cells, and which ones are going to die. Do NOT add these changes to your currentState. If there is a cell to be born or a death, add it to the newChanges list. When you are finished with this step, currentState should look exactly the same as it did at the beginning.
2. Once you have finished all calculations in step 1 for every cell, then iterate over newChanges. For each pair in newChanges, change it in currentState from dead to alive or vice versa.

Example:

• currentState has {0,0} {0,1} {0,2}. (Three dots in a line)
• newChanges is calculated to be {0,0} {-1,1} {1,1} {0,2} (The two end dots die, and the spot above and below the middle are born)
• currentState recieves the changes, and becomes {-1,1} {0,1} {1 ,1}, and newChanges is cleared.