Infinite Board: Conway's Game of Life - Python

Question

I was assigned this project with instructions below:

The game of Life is defined for an infinite-sized grid. In Chapter 2, we defined the Life Grid ADT to use a fixed-size grid in which the user specified the width and height of the grid. This was sufficient as an illustration of the use of a 2-D array for the implementation of the game of Life. But a full implementation should allow for an infinite-sized grid. Implement the Sparse Life Grid ADT using an approach similar to the one used to implement the sparse matrix.

I honestly don't really understand the concept that well. Could you please give me a brief description (if not brief code) that a layman can understand? I would appreciate it.

Sparselifegrid.py

""" My initial GameOfLife code
    Feb 27, 2013
    Sparse Matrix code specially designed for Game of Life
"""
class SparseLifeGrid:

    def __init__(self):
        """
        "pass" just allows this to run w/o crashing.
        Replace it with your own code in each method.
        """
        pass 

    def minRange(self):
        """
        Return the minimum row & column as a list.
        """
        pass

    def maxRange(self):
        """
        Returns the maximum row & column as a list.
        """
        pass 

    def configure(self,coordList):
        pass 

    def clearCell(self,row, col):
        pass 

    def setCell(self,row, col):
        pass 

    def isValidRowCol(val1,val2):
        pass 

    def isLiveCell(self,row, col):
        pass 

    def numLiveNeighbors(self, row,col):
        pass 


    def __getitem__(self,ndxTuple):
        pass 

    def __setitem__(self,ndxTuple, life):
        """
        The possible values are only true or false:
        True says alive, False for dead.
        """
        pass 

    def _findPosition(self,row,col):
        pass 

    def __repr__(self):
        pass 

    def __str__(self):
        """
        This method will only print the non-empty values,
        and a row and column outside the non-empty values.
        """
        pass 

    def evolve(self):
        """
        Return the next generation state.
        """
        pass 

    def hasOccurred(self):
        """
        Check whether  this current state has already occured.
        If not, return False.  If true, return which generation number (1-10).
        """
        pass 

    def __eq__(self,other):
        """
        This is good method if we want to compare two sparse matrices.
        You can just use sparseMatrixA == sparseMatrixB because of this method. 
        """
        pass

    def printLifeGrid(lifeGrid):
        """
        Print a column before and after the live cells
        """
        s=""
        maxRange=lifeGrid.maxRange()
        minRange=lifeGrid.minRange()
        for i in range(minRange[0]-1,maxRange[0]+2):
            for j in range(minRange[1]-1,maxRange[1]+2):
                s+=" "+str(lifeGrid[i,j])
            s+="\n"
        print(s)


class _GoLMatrixElement:
    """
    Storage class for one cell
    """
    def __init__(self,row,col):
        pass 

    def __str__self(self):
        pass 

    def __eq__(self,other):
        pass 

Here's my main file

""" Marcus Brown's  initial GameOfLife code
    Feb 27, 2013
"""
from SparseLifeGrid_Key import SparseLifeGrid
import sys


# You'll probably need to add some other stuff like global variables


""" ####################################################
        Don't change anything below this line: readPoints or main
""" ####################################################

def readPoints(lifeGrid):
    """
    Reads the locations of life and set to the SparseMatrix
    """
    print("1. Enter positions of life with row,col format (e.g., 2,3).")
    print("2. Enter empty line to stop.")

    life=input()
    coordList=[]
    while life:
        points=life.split(",")
        try:    
            coord=[int(points[0]),int(points[1])]
            coordList.append(coord)
        except ValueError:
            print("Ignored input:" + life+ ", row, col not valid numbers")
        except:
                print("Unexpected error:", sys.exc_info()[0])
        print("added, keep entering or enter empty line to stop.")
        life=input()
    print("Thanks, finished entering live cells")
    lifeGrid.configure(coordList)




def main():
    """
    Runs for ten generations if a stable (repeating) state is not found.
    """
    lifeGrid= SparseLifeGrid()
    readPoints(lifeGrid)
    lifeGrid.printLifeGrid()
    patterns=0
    i=0
    while i <10 and patterns == 0:
        """
        Evolve to the next generation
        """
        lifeGrid.evolve()
        """
        Check whether this generation is a repetition of any of the
        previous states.
        If yes return the previous matching generation (1-10).
        """
        patterns=lifeGrid.hasOccurred()
        if patterns != -1:
            break
        i+=1
        lifeGrid.printLifeGrid()

    if i==10:
        print("No pattern found")
    else: 

        print("Pattern found at: " + str(i)+ " of type: " + str(patterns))

main()

Answer 1

A sparse matrix is a representation of a matrix where only the locations of values not equal to the default (usually 0) are stored in memory. A simple way to represent such a matrix in Python is to use a dictionary where the key is a tuple of coordinate (x, y) and the value is the matrix values.

For example, this matrix:

0 0 0 0
0 0 0 0
0 1 0 0
0 0 0 0

could have the following representation:

matrix = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 1, 0, 0], [0, 0, 0, 0]]
sparse_matrix = {(1, 2): 1}

and you would access the values like that:

for x in xrange(4):
  for y in xrange(4):
      assert matrix[y][x] == sparse_matrix.get((x, y), 0)

This should be enough to get you started. Your exercise want you to wrap such a sparse matrix in a class that will give it the same interface as a traditional matrix.

There are more advanced way to store such sparse matrix, each doing a different trade off between complexity, memory usage, ...

Answer 2

Here is a simple sparse matrix based game of life solution in Python 2.x. You can set the size to as large as your system can handle. It wraps around in both the x and y direction:

class Cell():
    def __init__(self, x, y, live=True):
        self.x, self.y = x, y
        self.live = live
        self.around = 0

    def __eq__(self, other):
        return (self.x, self.y) == (other.x, other.y)

    def spawn(self):
        self.live = True
        self.around = 0
        return self

class Grid():
    def __init__(self, width, height):
        self.xMax = width
        self.yMax = height
        self.cells = []
        self.deltas = [(-1, -1), (0, -1), (1, -1), (1, 0),
                      (1, 1), (0, 1), (-1, 1), (-1, 0)]

    def tick(self):
        newCells = self.cells[:]
        ''' create potential new cells '''
        for cell in self.cells:
            for dx, dy in self.deltas:
                newCell = Cell((cell.x+dx)%self.xMax,
                               (cell.y+dy)%self.yMax, live=False)
                if newCell not in newCells:
                    newCells.append(newCell)
                newCells[newCells.index(newCell)].around += 1
        ''' spawn new cells for next grid '''
        self.cells = []
        for cell in newCells:
            if (cell.live and cell.around in [2, 3]
            or not cell.live and cell.around == 3):
                self.cells.append(cell.spawn())

    def show(self):
        for y in range(self.yMax):
            print ''.join('X|' if Cell(x, y) in self.cells
                     else ' |' for x in range(self.xMax))
        print

Usage:

>>> glider = [Cell(2,0), Cell(2,1), Cell(2,2), Cell(1,2), Cell(0,1)]
>>> g = Grid(7, 7)
>>> glider = [Cell(2,0), Cell(2,1), Cell(2,2), Cell(1,2), Cell(0,1)]
>>> g.cells = glider
>>> g.show()
 | |X| | | | |
X| |X| | | | |
 |X|X| | | | |
 | | | | | | |
 | | | | | | |
 | | | | | | |
 | | | | | | |

>>> g.tick()
>>> g.tick()
>>> g.show()
 | |X| | | | |
 | | |X| | | |
 |X|X|X| | | |
 | | | | | | |
 | | | | | | |
 | | | | | | |
 | | | | | | |

>>> g.tick()
>>> g.tick()
>>> g.show()
 | | | | | | |
 | | |X| | | |
 |X| |X| | | |
 | |X|X| | | |
 | | | | | | |
 | | | | | | |
 | | | | | | |