Recent Journal Comments

To answer your question, I don't recall that I've ever implemented a game of life before that day, though that day we had done 2 implementation attempts before the successful one. I had certainly known about the GoL, and played with it before, but if I did an implementation it must have been more than 20 years ago.

The first attempt was done in Ruby, and we spent around 5 minutes tracking down an issue that in the end was because one of the files was in a different directory than the others. In that attempt we were using a static array and we implemented the tests and the code for rules 1 through 3 of the GoL, and were just starting on the 4th. We were surprisingly close. This was basically one class storing both the game logic and the world.

The second attempt was in Python and we were going to try implementing it as a torus world. We didn't make a lot of progress in that one, but we did have quite a discussion about what the appropriate level of abstraction for the neighbors counting function should be. I mentioned that in my post above. I don't recall if we even implemented any of the rules of the GoL in that session, but I don't think we did. This attempt used a class for the game logic and another for the world, something that felt more natural than the first attempt.

In this attempt we decided to try an infinite world, again in Python. Greg wanted to see Python, and I'm very familiar with it and was happy to show it off. I decided to use a dictionary using the x,y position as a tuple and the value as a boolean whether that cell was alive.

Another thing that felt strained in the previous attempts was the level of tests. For this attempt, I tried making tests for the API. So the first thing implemented was "test_Set()" which tested setting a cell at a position as being alive. Then we implemented that by creating the "Game" and "World" classes, the game initializer created a world, and the world created teh dictionary and the set() function on it was just a simple dictionary call: "self.life_map[(x, y)] = is_alive".

The test for that succeeded. so we went on to the next API function with "test_Get()", which returns if the cell at the specified position is alive. The implmentation of that was initially a "return self.life_map[(x,y])", but the tests were failing for cells that had never been set. So I added a "if (x,y) not in self.life_map: return False". However, that in retrospect should have just been a "return self.life_map.get((x, y), False)". But, the first attempt at it got it working so we went on to the next test.

At around this point I realized that in the tests we were duplicaing world setup code so I refactored that code to have a "setUp()" that created the world, and modified the tests, then ran them to make sure they worked.

This test was for the API function "count_neighbors()", so we did a bunch of tests, set a cell, did those tests again with the new values, set another cell, did those tests again with the new new values...

The implementation of that was fairly simple, using the pattern Scott had come up with in the initial attempt in Ruby of two for loops walking through offsets of -1, 0, and 1, then checking if that cell was alive and incrementing the counter if so. Before running the test I realized that offset x=0,y=0 needed to be skipped in the check for life, so I put a conditional in there.

The test for that worked. The "world" class ended up being 16 lines of code, but two of those were compound "if X: Y". So, not a lot of code.

Now that we had the API working, we implemented a test for rule 1. Basically, set a cell, run the "next_generation()" metod of the game, and check to see that the cell died. The code for this walked the dictionary of x,y locations in the dictionary and if that cell was alive it wouldcheck the number of neighbors and if it was less than 1 it would "set(x,y,False)". Test ran successfully, so off we went...

Next was tests for Rule 2, which I created one for 2 neighbors and one for 3 neighbors. We ran the test before implementing the code, as we did with every attempt, and realized that this was already implemented by the code we had written, which if a cell didn't match any of the rules, it was propagated from one generation to the next. So we got rule 2 for free.

Next we added the test for rule 3 by creating a cell with 4 neighbors and then seeing that it died. The code for that was fairly simple, just kill the cell if it was alive and it had more than 3 neighbors. We ran the tests and now were seeing failures for tests that previously were working. So I looked at the new code and realized that where I intended to have added the new rule as an "elif", I had instead added it as an "if". Fixed that and now all my tests were passing again.

So finally we added a test for rule 4, if a cell is dead and it has exactly 3 neighbors, it comes alive. The implementation for this was added, and we ran the tests and they failed... I thought about it for a second and realized that we were only checking the live cells, since we were checking the cells in the dictionary. I realized that we needed to check the cells around the live cells too, so I used code similar to the "count_neighbor" code described above, and ran the rules on all the neighbors of the live cells. I realized that this would check some cells multiple times, but my goal was the simplest, most obvious code, there were no performance constraints. With this code in place, the tests succeeded.

At this point we looked at each-other and decided it passed all the rules tests, so it must be done. I said to Bill "Remember how you said there's no way to finish it?" He asked if we could show him a glider. "Yeah, what are the points that make up the glider? The copy he had on his screen was moving so it was hard to tell, but he then suggested a bar of 3 cells that just oscilates...

So we wrote a test that set a bar, checked the world for the bar, generated and tested for the line (and that the cells that should have died did die) and then generated again and tested live+dead cells again. We agreed that it was working...

So, I plugged in a "main()" part of the code, set a bar of 3 cells live, and added a function to the Game class to print out part of the world. My first attempt at that used dynamic min and max for the x and y coordinates, so it would pretty much just print "XXX" or "X\nX\nX\n", not super exciting.

So I just hard-coded it to print the first 5 rows and columns. We ran 3 generations of that and it looked good. So then we tried to figure out the coordinates of the glider. Bill too a screen print of the animated GIF on the Wikipedia page and from that we were able to poke in the coordinates. We ran 4 generations of that, and sure enough we had a glider being printed out.

Around this point, "time" was called. Unlike previous attempts, I did end up saving off a tar of this for later analysis (which is how I was able to recreate the attempt above).

In the end, the "World" class was 16 lines, the "Game" class was 19 lines plus another 9 lines to print the world, and the tests were 82 lines (many of them just repetitions of "assertEquals" lines for various locations. Another 25 lines in my "main" function with did 3 generations of the "bar" and then 5 generations of the glider and printed them out.

In retrospective, I'm quite certain that having the tests allowed me to develop the code more quickly. There were several errors I made, as outlined above, but having the tests allowed us to very quickly determine exactly where the problem was introduced, and look at exactly that code to determine the problem.

Without tests I would have *HAD* to implement the display() function earlier, and basically do test code that would spit out the world and eyeball that it was doing the right thing. I also likely would have been running testing in my head as I wrote the code, which would have slowed it down. And when I ran into the problems, I would have had to have reviewed the bulk of the code rather than exactly the last set of code I wrote.

So, those are the details as I remember them.
(go to entry which this is a comment to)