FGNO: Game of Life

I stole borrowed adapted reused code for FGNO. Let’s review it. CW: Live, dead, LLMs are not your friend.

Our FGNO¹ sessions go better with code, and GeePaw Hill suggested Conway’s Game of Life as a small exercise. For my contribution I studied examined ripped off the somewhat over-cooked version on RealPython, to which I subscribe and which I recommend. (That may be a page requiring membership: as I am a member, I’m not sure.)

Let’s summarize the rules of the game.

• We have a grid of integer x and y coordinates.
• At each integer location there is a “cell”. That cell can be occupied, or empty.
• The grid evolves iteratively. In each iteration:
• Any occupied cell which is surrounded by 2 or 3 other occupied cells stays alive.
• An occupied cell surrounded by less than two occupied cells dies of loneliness.
• An occupied cell surrounded by more than three occupied cells dies of crowding.
• Any empty cell that is surrounded by exactly three occupied cells will be occupied i n the next iteration.

Commonly, occupied cells are called “alive” and unoccupied, the opposite. “Dead”, not to put too fine a point on it.

The patterns that can be produced by these simple rules are quite amazing. In fact, it has been shown that the game is Turing complete: it is possible to create a pattern that will compute any function that can be programmed. (This does not suggest that it’s easy to do that.)

I’ll leave it to you to study the game further if you care to. It is fascinating. I’d suggest starting with the Wikipedia Article, and give them a donation while you’re there, if you’re able and so inclined. Our purpose here is to review the code that I um reused, to see what we think of it a few days after making it work.

Patterns in Life can grow without bound and things seem to move around, so, in effect, the grid is potentially infinite. It can quickly grow to be quite large: it’s easy to set up four “gliders” moving in four different directions, which grows the grid by one cell in every direction something like once every four iterations. It follows that a key notion in any decent Life game is to have a sparse grid.

I have done Life before, many times over the decades, and so I am aware that one needs a sparse grid, and I even knew that there was a clever Python way of doing that, which is why I looked for the code. Let’s start looking at my tests and code.

Python Game of Life

I did begin with tests, first my standard hookup and then a test of the basic data structure adopted from the RealPython example:

class TestHookup:
    def test_hookup(self):
        assert True == True

    def test_grid_set(self):
        grid: set[tuple[int, int]] = set()
        assert len(grid) == 0
        cell = (10,20)
        grid.add(cell)
        assert len(grid) == 1
        assert cell in grid

We see the grid structure right there, because I wanted to exercise it in a test before using it in the code. It is a set of tuples, each tuple having two integer elements. We think of it as a set of x, y coordinates. Because it’s a set, it contains any given pair only once, and doesn’t contain anything “in between”. Just what we need, and very conveniently, Python treats tuples as hashable, which means they are a perfectly good key for a set.

Our grid will be a set of live cells. There will be no “dead” cells:L they just won’t show up in the grid.

So those tests served to get my fingers and mind somewhat warmed up. Next, I decided to write a test that found the neighbors of a given cell. Those will be the eight cells surrounding it, and their coordinates will be plus or minus one, or zero, plus the coordinates of the cell in question. As you can see, before I even finished the test, I wasn’t fond of it:

    def test_neighbors(self):
        neighbors = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]
        assert len(neighbors) == 8
        grid: set[tuple[int, int]] = set()
        for neighbor in neighbors:
            grid.add((10+neighbor[0], 20+neighbor[1]))
        # this seems stupid

One would never add all the neighbors to the grid, and adding the offsets to the coordinates doesn’t need much testing. So I moved on:

    def test_grid_class(self):
        grid = Grid()
        assert len(grid.live_cells) == 0

Here I finally begin to express a bit of design for Life. I propose to have a Grid class with a member live_cells, which will start out empty. That drove out a simple class:

class Grid:
    def __init__(self):
        self.live_cells:set[tuple[int, int]] = set()

Not too exciting. And that’s good. I am totally OK with a test that drives out two lines of code, or even just one. Takes no time, sets a nice rhythm, and even I can only make a few mistakes in one or two lines: there just isn’t room for very many mistakes.

Then I decided to have a method that counts neighbors, and wrote this test:

    def test_grid_neighbor_count(self):
        grid = Grid()
        neighbors = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]
        for neighbor in neighbors:
            grid.add(10+neighbor[0], 20+neighbor[1])
        assert grid.number_of_neighbors(10,20) == 8
        grid.remove(10,19)
        assert grid.number_of_neighbors(10,20) == 7

This test assumes three new methods on Grid, add, remove, and number_of_neighbors. It will turn out that exactly one of these is useful: add. But the test drove out this code:

class Grid:
    def __init__(self):
        self._neighbors = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]
        self.live_cells:set[tuple[int, int]] = set()

    def add(self, x: int, y: int) -> None:
        self.live_cells.add((x, y))

    def remove(self, x: int, y: int) -> None:
        self.live_cells.remove((x, y))

    def number_of_neighbors(self, x: int, y: int) -> int:
        count = 0
        for n_x, n_y in self._neighbors:
            if (x+n_x, y+n_y) in self.live_cells:
                count += 1
        return count

Now it turns out that the only two uses of number_of_neighbors, and the only use of remove, are in that test, so you could argue that it was a total waste, but in fact there’s value in that code, namely that it’s the first time I wrote code processing the live_cells set, and I even use the neighbor offsets. So there was a bit of learning in there, if nothing for production.

We don’t always go straight to the answer when we work in small steps. We don’t even try to go straight to the answer. We try to make a small step toward the answer, and this is a step toward what we need.

Then I wrote this test, including the comment, added after the rest of the test:

    def test_stop_light(self):
        # probably too hard
        grid = Grid()
        grid.add(5,4)
        grid.add(5,5)
        grid.add(5,6)
        grid.evolve()
        assert len(grid.live_cells) == 3
        assert (4,5) in grid.live_cells
        assert (5,5) in grid.live_cells
        assert (6,5) in grid.live_cells

Note that I felt that test was too hard, and so I belayed it and wrote this one:

    def test_grid_neighbor_cells(self):
        grid = Grid()
        neighbors = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]
        cells = grid.neighbor_cells(10,20)
        for nx, ny in neighbors:
            assert((10+nx, 20+ny)) in cells

To make that run, I wrote:

    def neighbor_cells(self, x, y):
        return [(x+nx, y+ny) for nx, ny in self._neighbors]

I don’t remember now why that made me feel ready to go ahead with evolve but it did, and of course I had the RealPython code to refer to.

(I should have called test-stop_light test_blinker, because that’s the conventional name for that pattern. I forgot.)

Here’s a picture of the two states implied there:

grid
..........
..........
..........
..........
.....*....
.....*....
.....*....
..........
..........
..........

grid
..........
..........
..........
..........
..........
....***...
..........
..........
..........
..........

The pattern oscillates between the three vertical live cells and three horizontal.

test_stop_light calls for the evolve method, which I typed in after studying the RealPython method of the same name.

    def evolve(self):
        neighbor_counts = collections.defaultdict(int)
        for x, y in self.live_cells:
            for dx, dy in self._neighbors:
                neighbor_counts[(dx+x, dy+y)] += 1

        stay_alive = {cell for cell, num in neighbor_counts.items() \
            if num in {2, 3} }
        stay_alive = stay_alive & self.live_cells

        born = {cell for cell, num in neighbor_counts.items() \
            if num == 3}
        born = born - self.live_cells

        self.live_cells = stay_alive | born

Let’s go through that to explain it, then we’ll want to refactor it.

The defaultdict neighbor_counts will return what’s in the dictionary if there is anything, and other wise will create an int, i.e. return a zero. The first segment of code in the method creates a dictionary with keys consisting of grid coordinates, and value containing the number of live neighbors that cell has.

Why? Because we iterate all the live cells and for each of their neighbors, we increment that neighbor’s count. Do you find that hard to grok? I did, and I did a tiny example on paper, making tick marks in cells. Anyway that’s what it does and you can convince yourself of that with a test or by any other means.

Quite probably there should be a test for that. My existing tests test near that idea but do not test it directly. I think we’ll get there this morning.

So anyway, we have neighbor_counts for all the live cells. We need to determine which cells stay alive and which new ones are born. the next two lines do stayin alive:

stay_alive = {cell for cell, num in neighbor_counts.items() \
    if num in {2, 3} }
stay_alive = stay_alive & self.live_cells

That’s not good. This might be better:

twos_and_threes = {cell for cell, num in neighbor_counts.items() \
    if num in {2, 3} }
stay_alive = twos_and_threes & self.live_cells

The first line finds the set of cells that have neighbor counts of two or three. The second intersects that set with the live cells, resulting in the live cells that stay alive.

Same idea with the next two lines, which find the cells needing to be born:

born = {cell for cell, num in neighbor_counts.items() \
    if num == 3}
born = born - self.live_cells

This would also benefit from some renaming:

threes = {cell for cell, num in neighbor_counts.items() \
    if num == 3}
born = threes - self.live_cells

What I like about those renamings is that when we used born, for example, the first assignment wasn’t really the cells to be born, it was just all the cells with three neighbors. Could the name be better than threes? Probably, but this is an improvement.

Then we compute the new set of live cells:

        self.live_cells = stay_alive | born

Live cells are just the ones that say alive union with the ones that are born. Done.

So that code passes the stop light / blinker test and I was sure at that point that the game code was complete and correct. My tests gave me sufficient confidence, so I stopped and was ready to present at FGNO. That went just fine. (We were being pretty easy last Tuesday and it may be that I closed the code window and made a leading comment that drew us off the code. I didn’t mean to … but it happened.)

I think the evolve method would like to be refactored, with some Extract Method refactorings:

    def evolve(self):
        neighbor_counts = self.count_neighbors()

        twos_and_threes = {cell for cell, num in neighbor_counts.items() \
            if num in {2, 3} }
        stay_alive = twos_and_threes & self.live_cells

        threes = {cell for cell, num in neighbor_counts.items() \
            if num == 3}
        born = threes - self.live_cells

        self.live_cells = stay_alive | born

    def count_neighbors(self):
        neighbor_counts = collections.defaultdict(int)
        for x, y in self.live_cells:
            for dx, dy in self._neighbors:
                neighbor_counts[(dx + x, dy + y)] += 1
        return neighbor_counts

There’s one. I’ll do the other two:

    def evolve(self):
        neighbor_counts = self.count_neighbors()
        stay_alive = self.get_staying(neighbor_counts)
        born = self.get_born(neighbor_counts)
        self.live_cells = stay_alive | born

    def get_born(self, neighbor_counts):
        threes = {cell for cell, num in neighbor_counts.items() \
            if num == 3}
        born = threes - self.live_cells
        return born

    def get_staying(self, neighbor_counts):
        twos_and_threes = {cell for cell, num in neighbor_counts.items() \
            if num in {2, 3}}
        stay_alive = twos_and_threes & self.live_cells
        return stay_alive

Now I think we can inline the returns without loss of clarity:

    def get_born(self, neighbor_counts):
        threes = {cell for cell, num in neighbor_counts.items() \
            if num == 3}
        return threes - self.live_cells

    def get_staying(self, neighbor_counts):
        twos_and_threes = {cell for cell, num in neighbor_counts.items() \
            if num in {2, 3}}
        return twos_and_threes & self.live_cells

We could inline further but I prefer the “explaining temporary variable”. YMMV.

Just for fun, now that I have committed that, let’s inline as far as we can.

Part way there and it’s already pretty awful:

    def evolve(self):
        neighbor_counts = self.count_neighbors()
        stay_alive = {cell for cell, num in neighbor_counts.items() \
            if num in {2, 3}} & self.live_cells
        born = {cell1 for cell1, num1 in neighbor_counts.items() \
            if num1 == 3} - self.live_cells
        self.live_cells = stay_alive | born

A couple more:

    def evolve(self):
        neighbor_counts = self.count_neighbors()
        self.live_cells = ({cell for cell, num in neighbor_counts.items() if num in {2, 3}} & self.live_cells
                           | {cell for cell, num in neighbor_counts.items() if num == 3} - self.live_cells)

The fact that you have to scroll that sideways to read it tells you all you need to know. Roll back. I think this one is just fine:

    def evolve(self):
        neighbor_counts = self.count_neighbors()
        stay_alive = self.get_staying(neighbor_counts)
        born = self.get_born(neighbor_counts)
        self.live_cells = stay_alive | born

Further Improvements?

We could, and in production code probably would remove the unused methods remove, number_of_neighbors and neighbor_cells. I see no future for them, no reason to save them. They’re easy to write if needed and will of course be in the repo as well.

There might be other matters. Arguably the list of neighbor offsets should be a class variable or even some kind of local variable in the module. Perhaps other things. But I want to make a different point:

Use of LLMs.

What we see here is some rather carefully chosen code, from an actual tutorial implementing the very program we needed. And that code needed tests and it needed refactoring to be truly clear. It was perhaps good tutorial code but at least by my standards it was not well factored.

If you use a coding LLM, my second-best advice is to review the code carefully, and to surround it with tests. Ideally, tests that you wrote. Failing that, tests that the LLM wrote and that you have very carefully reviewed. The LLM code is by design only what code for the task might look like, and it is based on a wide-ranging average of code that it has read, modified probabilistically by the nature of the LLM implementation.

The code will not be good code and it will not necessarily do what you asked it to do, and even if you told it to code like Kent Beck, it will nonetheless be unproven. And if you just accept it, you won’t understand it and if you don’t understand it, what good are you?

My best advice is not to use an LLM. The companies creating them are not your friends. A company demanding that you use them is not your friend. The LLM itself is flawed, and its flaws are hard to detect. The companies creating them are consuming the power and water of entire cities.

If you possibly can avoid using them, do not use them. If you must, use with care, and try to prepare a safety net for when some fool decides to replace a human with “AI”, and that human turns out to be you.

These things are not good for humans. They’re fascinating, and they are programmed to be appealing. But they are not good for humans.

LLMs are not good for you.