无限的棋盘：康威的生命游戏Python

Question

我被分配了这个项目，指示如下：

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.

我真的不太了解这个概念。你能给我一个简单的描述（如果不是简单的代码）一个外行可以理解吗？我会很感激的。在

在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 

这是我的主要档案

^{pr2}$

Answer 1

这是Python2.x中一个简单的基于稀疏矩阵的生活游戏解决方案。您可以将大小设置为系统能够处理的最大大小。它在x和y方向上都绕着：

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

用法：

^{pr2}$

Answer 2

稀疏矩阵是矩阵的一种表示，其中只有不等于默认值（通常为0）的值的位置存储在内存中。在Python中表示这样一个矩阵的一个简单方法是使用字典，其中键是一个坐标(x, y)的元组，值是矩阵值。在

例如，该矩阵：

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

可能有以下表示：

^{pr2}$

你可以访问这样的值：

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

这应该足够让你开始了。您的练习希望您将这样一个稀疏矩阵包装在一个类中，该类将提供与传统矩阵相同的接口。在

有更高级的方法来存储这样的sparse matrix，每种方法都在复杂度、内存使用率、。。。在