4
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Ah thanks for the reply, the idea for new_rule was that you'd be able to update it at any time, I must have forgotten what I was doing halfway through integrating it aha. Likewise for rule in rules, I should have probably noticed that, I think I initially had a reason but can't see it looking back. Validation is a good idea, I've been told don't validate too much, though I like your suggestion of catching any errors then raising them again with a new message, and I had a quick google and it appears enumerate is slower than range, does it just look nicer or does it have any advantages? \$\endgroup\$ – Peter Oct 23 '15 at 12:29
  • \$\begingroup\$ I think enumerate would be a bit slower except that your method requires calling range(len(list)) so the speed gain is lost, not that it's a big difference. You can definitely over validate, but if the script doesn't even notice it got bad data til later then it's worth validating. Particularly as you don't explain what is valid input. \$\endgroup\$ – SuperBiasedMan Oct 23 '15 at 13:17
  • \$\begingroup\$ Building on your validate idea btw, I made a separate function to do it, so I can also validate before step is called (it's all good raising an error if the new rules are invalid, but it doesn't stop the rest of the function). I'm also going to change the rules to not need a slash, and instead just read the numbers between each letter, makes for a much easier input that way. I was halfway through adding your suggestions when I ran 999 iterations of a B2/S23 rule thinking that was the default one, it's still going after 45 minutes and I've not saved any changes so I've gotta sit it out haha. \$\endgroup\$ – Peter Oct 23 '15 at 13:37
  • \$\begingroup\$ Added a link to the updated version btw, not massively different but I fixed the bits you mentioned \$\endgroup\$ – Peter Oct 24 '15 at 23:53

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.