Simple Game Of Life with infinite size

Question

I decided to try make a version of the Game Of Life that'd be infinitely big. The idea was to store a dictionary of each Y value, which contain a set of X values (for fast lookup), as opposed to creating a 2D grid, and searching for the coordinate.

I've no way if this idea would scale well or not since I've not done any fancy optimisations. For each generation, it will build a list of every cell and adjacent cell, check how many are adjacent to each of those, and create or remove a cell accordingly.

Currently it's just limited to printing the result, though I'll try get it linked up with pygame sometime if it doesn't turn out horribly slow.

class GameOfLife(object):

    adjacent = ((-1,-1), (0,-1), (1,-1),
                (-1, 0),         (1, 0),
                (-1, 1), (0, 1), (1, 1))

    alive_cell = 'o'
    dead_cell = '.'

    def __init__(self, rule='B3/S23'):
        """Setup an empty Game Of Life object."""
        self._reset()
        self.new_rule()

    def _reset(self):
        self.game_data = {}
        self.generations = 0

    def new_rule(self, rule='B3/S23'):
        """Store the information for a new rule."""
        rules = rule.split('/')

        for i in range(len(rules)):
            if rules[i].lower().startswith('b'):
                self.rule_born = map(int, list(rules[i][1:]))

            elif rules[i].lower().startswith('s'):
                self.rule_alive = map(int, list(rules[i][1:]))

    def paste(self, cells, offset=(0, 0), clear=False):
        """Paste a string to act as cells.

        Use 'o' to bring a cell to life, and '.' to kill a cell.
        An empty space will not modify the cell under it.
        """
        if clear:
            self._reset()

        y = None
        for line in cells.splitlines():

            #Ignore any initial empty lives
            if y is not None:
                y += 1
            elif line and y is None:
                y = 0

            for x in range(len(line)):
                if line[x] == self.alive_cell:
                    self.add((x + offset[0], y + offset[1]))
                elif line[x] == self.dead_cell:
                    self.remove((x + offset[0], y + offset[1]))


    def add(self, coordinate):
        """Add a cell."""

        #Add to dictionary
        if coordinate[1] not in self.game_data:
            self.game_data[coordinate[1]] = set([coordinate[0]])

        elif coordinate[0] not in self.game_data[coordinate[1]]:
            self.game_data[coordinate[1]].add(coordinate[0])


    def remove(self, coordinate):
        """Delete a cell.""" 

        #Remove point from dictionary
        if (coordinate[1] in self.game_data
            and coordinate[0] in self.game_data[coordinate[1]]):
            self.game_data[coordinate[1]].remove(coordinate[0])

            #Delete column if no more values
            if not self.game_data[coordinate[1]]:
                del self.game_data[coordinate[1]]


    def find_all_adjacent(self):
        """Find the number of adjacent cells to each cell.

        It will build a list of all the cells currently alive or
        touching something alive, then iterate through each one to
        find how many they are touching.
        """
        all_coordinates = set()
        adjacent_amount = {}

        #Iterate through dictionary to build list of all cells
        for y in self.game_data:
            for x in self.game_data[y]:
                num_adjacent = 0

                for i in self.adjacent:
                    c = (x + i[0], y + i[1])
                    if (c[1] in self.game_data
                        and c[0] in self.game_data[c[1]]):
                        num_adjacent += 1

                    all_coordinates.add(c)
                adjacent_amount[(x, y)] = num_adjacent

        #Find neighbours for each cell
        for coordinate in all_coordinates:
            if coordinate not in adjacent_amount:
                num_adjacent = 0

                for i in self.adjacent:
                    c = (coordinate[0] + i[0],
                         coordinate[1] + i[1])
                    if (c[1] in self.game_data
                        and c[0] in self.game_data[c[1]]):
                        num_adjacent += 1

                adjacent_amount[coordinate] = num_adjacent

        return adjacent_amount

    def step(self, n=1):
        """Move forward n steps in the generation."""

        for i in range(n):

            self.generations += 1
            adjacent_blocks = self.find_all_adjacent()

            for cell in adjacent_blocks:
                neighbours = adjacent_blocks[cell]
                alive = (cell[1] in self.game_data
                         and cell[0] in self.game_data[cell[1]])

                if (not alive and neighbours in self.rule_born
                    or alive and neighbours in self.rule_alive):
                    self.add(cell)
                else:
                    self.remove(cell)

    def __str__(self):
            """Print the current state of the cells."""

            output = []
            min_x = '' #String so it will always be larger than a number

            #Fix for if game_data is empty
            if not self.game_data:
                y_range = ()
            else:
                y_range = range(min(self.game_data), max(self.game_data) + 1)

                #Find lowest X value to offset the printing by
                for y in y_range:
                    if y in self.game_data:
                        min_x_value = min(self.game_data[y])
                        if min_x_value < min_x:
                            min_x = min_x_value

            #Generate each cell a line at a time
            for y in y_range:
                last_x = min_x

                if y in self.game_data:
                    x_list = sorted(self.game_data[y])
                else:
                    x_list = []

                output_text = ''
                for x in x_list:
                    output_text += ' ' * max(0, 2 * (x - last_x) + 1) + 'o'
                    last_x = x + 1
                output.append(output_text)

            return '\r\n'.join(output)

Then you can use it like this:

x = GameOfLife()
x.paste("""
        o.o.o
        o...o
        o...o
        o...o
        o.o.o
        """)

x.step(999)
print x

Which should print:

         o           o
         o           o
         o o       o o

 o o o     o o   o o     o o o
     o   o   o   o   o   o
         o o       o o

         o o       o o
     o   o   o   o   o   o
 o o o     o o   o o     o o o

         o o       o o
         o           o
         o           o

I did get the idea that dict[(x,y)] = True; dict[(x2, y)] = True would be more efficient than my dict[y] = set(x, x2) way, for both lookups and setting values, but I just tried it out, and it's actually slower which is quite strange.

Link to the latest version is here.

Answer 1

Good work wrapping it as an object, this makes a ton of things easier. adjacent, alive_cell and dead_cell should all be UPPER_SNAKE_CASE though, as they're constants.

You call for a rule parameter in __init__ but then ignore it by not passing it to new_rule and always defaulting that parameter. You also never call new_rule again. Is it intended to be usable on an object at any other time? If not then you should really put all the code from that function into __init__.

Also you can do a much easier loop if you just do for rule in rules. You then access each rule directly rather than using an index. This does technically overwrite the original rule value, but you don't need it any more so it's not going to make a big difference. You don't need to call list since map returns a list. And you should use lower() at the start, before you even split, to save on calling it multiple times later.

You don't validate the rule value at all. What if I passed the rule "You should duplicate if there's 5 spaces around you but die if there's less than 3". Of course that can't work, but you don't tell me that anywhere. Instead the object will be created and move on with no rules to call on. You should raise ValueError if it turns out that at the end of the function either of the rules have not been set and explain what values need to be in the string.

def __init__(self, rule='B3/S23'):
    """Setup an empty Game Of Life object."""
    self._reset()

    rules = rule.lower().split('/')
    for rule in rules:
        if rule.startswith('b'):
            self.rule_born = map(int, rule[1:])

        elif rule.startswith('s'):
            self.rule_alive = map(int, rule[1:])

    try:
        if not (self.rule_born and self.rule_alive):
            raise AttributeError
    except AttributeError:
        raise ValueError("rule must be of format 'B#/S#'.")

This block attempts to test the truthiness of your rules. Python can coerce most objects to boolean values. In the case of lists, an empty list will be False but a list containing any values at all will be True. So, if either of your values is empty then we'll get False here and that will lead us to raising an AttributeError. Why an AttributeError? Because we want to catch that in case we've never even set one of the attributes. If your rule string doesn't include a B in it, then your rule_born wont even exist and trying to access it will cause an AttributeError. This way we can catch the error whether it's due to the relevant letter missing or the letter not setting satisfactory values. You do also have the problem that map(int) can raise a ValueError of its own, I would similarly wrap that in try: except ValueError and re-raise a ValueError with a relevant error message.

Another note about __init__. Why not allow the user to pass a string there to call paste immediately? There's little point to having the object without any values, so adding that string as an optional value would save an added line of code without a lot of complexity.

In your paste function, you could avoid having to use y at all. To ignore the opening blank line/s then just use strip('\n'). Unlike before, this will only remove blank lines and leave spaces intact. Now you can use enumerate to get the index of the line you're on.

    cells = cells.strip('\n')
    for y, line in enumerate(cells.splitlines()):
        for x, char in enumerate(line):
            if char == self.alive_cell:
                self.add((x + offset[0], y + offset[1]))
            elif char == self.dead_cell:
                self.remove((x + offset[0], y + offset[1]))

I did the same with line, this is a neater way to simultaneously get the values from your string and the index location of each element.