It’s kind of weird how often that game has occured to me recently :)
The last ‘contact’ was a coding kata on codewars. This platform is worth a try especially because of the supported languages:
The first time I spent some thoughts about that game was about a year ago when I attended a coderetreat (Global Day of Coderetreat) in Berlin. During a coderetreat you solve the same problem again and again from scratch every 45 minutes in a Pair-Programming-TDD style. Usually no team is able to solve that problem. Back then I saw two main approaches the attendees used to solve the problem with. One was to start implementing the concept of an infinite board with living and dead cells… the other approach tackled the rule set.
In the coderetreat I should have spent a hole session or more to think about the problem instead of starting as soon as my pairing partner and I agreed on a strategy, which seemed to be good enough. Why? Because good enough is not necessarily good. That might sound weird, but sometimes during TDD here and incremental (baby step wise) developement there, we seem to forget about the bigger picture. But that’s another topic…
Instead of thinking about a board and rules let’s try to think about the problem again. At the end it’s all about neighbors. If a cell has exactly two and three living neighbors everything is good, otherwise bad. That’s it! So - what does it mean? Let’s start with the in my opinion very elegant solution:
A Clojure implementation
That’s neat isn’t it? For those who are not familiar with Clojure let me explain what the code does:
It defines a neighbors function which takes a cell (list with two elements: coordinates) and returns all neighbor cells (coordinates)
- line 1: we use Clojures list destruction to access the first element of the cell and store it in a x variable and the second for the y variable
- line 2,3: generates eight tuples ([-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]) and uses them for the calculation of the neighbor cells by simple addition
It defines the next-gen function which takes a sequence of living cells and returns a sequence of the next generation cells in respect to the game rules
- line 6: this line does several things:
- (mapcat neighbor cells) this applies the neighbor function on each element of cells and concat the results - in other words: for each cell compute its neighbors and store the neighbor cells in a sequence which might include duplicates
- (frequencies …) take this list l with all the concatenated neighbor cells and creates a map with each cell as key (no duplicates) and with the number of occurences of that cell in l - in other words: count for each of the neighbor cells how often they occur
- for [[cell n] (frequencies …)] iterates over the frequencies results and uses Clojures map destruction to access the key and store it in a variable cell and the same for the value (n)
- line 7: apply the game rules
- (cells cell) returns true if the previous cell generation (cells) contains the cell - in other words: we have to be careful, we just created a lot of neighbor cells and counted their occurrences which is fine for cells with three neighbors (if the cell wasn’t part of the previour generation then it’s a new born cell). The same goes not for newly created neighbor cells (which weren’t part of the previour generation) with only two neighbors -> if they weren’t part of the previour generation then they’re not allowed to be born -> we have to filter them out with (cells cell) -> this is a very important part of the algorithm you have to understand.
- line 6: this line does several things:
The key for this solution is to understand why counting just the neighbor cells and after that applying the rules is all you need - think about it…
- I need to be able to store the frequencies of a cell which needs some kind of map structure where I can use a cell (Array) as a key.
- Unfortunately this is not possible (at least as I know - please comment if you found something to use an object or array as key).
- To work around that, I use two convert functions which convert a cell to a string and vice versa. And I use a plain object literal as the map structure with the stringified cell as property name. It works but’s it’s hacky and the code gets ugly and overloaded!
- I need to lookup a collection whether it contains a cell (line 34). As long as you’re not looking simple type like strings or numbers you have to specify an extra ‘match function’.
- you can not use the indexOf function for Arrays because it’s using the strict equals operator and you can do nothing like __eq__ in Python (I guess that’s why you can not use the new ECMAScript6 build-in type Map for our needs)
- it’s even hard to extract that ‘match’ function (line 34) because you need to access the cell_as_string variable -> you can do that with a clojure but again that feels a little bit overloaded…
- Line 2-5: List comprehensions would be nice.
A Python3 implementation
As we can see we don’t have big problems to write the same algorithm in Python thanks to the powerful list comprehensions and a powerful API. The only thing where I wasn’t able to find something elegant (please comment if you have something better) was the needed function compostion in line 8 (the problem here is that I needed to unpack the list of neighbor lists…).
Obviously there’s a very simple algorithm to solve that game and I’m kind of surprised that during my previous sessions I was too eager to get something done instead of thinking about it. I’m not sure whether I would have found that solution on my own, but the good thing is that once I know it, I will never forget :) And even better: I hope that I’m able to adapt this solution to similar problems. So I think it’s important to solve a lot of different problems and compare your solution with others. Coding Kata Platforms like codewars or Checkio or USA Computing Olympiad are great to improve your skills and to increase your repertoire :)