Game of Life Implementations

clojure, javascript, python

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:

  • Python, Ruby, JavaScript, Java, Haskell, CoffeeScript and Clojure (there might be some more right now)

Sadly you can not select an arbitrary language for every kata. For Conway’s game of life at codewars you can only select Javascript and Python.

I tried to implement a solution in Javascript and after the 10th line of code it got a little bit annoying - I remembered a really elegant solution in Clojure (Clojure Programming). I think the Clojure, or we could say “functional” solution, is so elegant and so consise (a few lines of code) that it’s worth a blog entry :)

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…

I struggled with myself whether I should present the ‘weird’ Javascript implementation first and after that - ta da (drama queen) - present the elegant and shining Clojure implementation as a reward for inspecting the Javascript mud. I don’t know what’s the best style, but tomorrow is new year - let’s start with the shining part :)

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

(defn neighbors [[x y]]
(for [dx [-1 0 1] dy [-1 0 1] :when (not= 0 dx dy)]
[(+ x dx) (+ y dy)]))
(defn next-gen [cells]
(for [[cell n] (frequencies (mapcat neighbors cells))
:when (or (= n 3) (and (= n 2) (cells cell)))]
loc))

That’s neat isn’t it? For those who are not familiar with Clojure let me explain what the code does:

  1. 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
  2. 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.

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…

A Javascript implementation

Once you know the ‘functional’ solution I can not think about a better way of doing that - so let’s try this in Javascript:

function neighbours(cell) {
return [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]].map(
function (pos) {
return [pos[0] + cell[0], pos[1] + cell[1]]
}
);
}
function asString(cell) { // cell coordinates -> string
return cell[0] + "," + cell[1];
}
function asCell(string) { // cell coordinates as string -> cell
var parts = string.split(',');
return [parseInt(parts[0]), parseInt(parts[1])];
}
function next_gen(cells) {
var all_neighbours = cells.reduce(function (nb, cell) {
return nb.concat(neighbours(cell));
}, []);
var frequencies = all_neighbours.reduce(function (fr, cell) {
fr[asString(cell)] = 1 + (fr[asString(cell)] || 0);
return fr;
}, {});
var next_generation = [];
for (cell_as_string in frequencies) {
if (frequencies.hasOwnProperty(cell_as_string)) {
if (frequencies[cell_as_string] == 3) {
next_generation.push(asCell(cell_as_string))
} else if (frequencies[cell_as_string] == 2 && cells.some(function (cell) { return asString(cell) === cell_as_string})) {
next_generation.push(asCell(cell_as_string))
}
}
}
return next_generation;
}

Puh - to implement the same algorithm in Javascript I faced on some problems which caused this kind of messy code:

  1. 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!
  2. 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…
  3. Line 2-5: List comprehensions would be nice.

Javascript is definitely not my number one language to solve that problem… Let’s try to do it in Python which seems to be promising, because Python has support for tuples and list comprehension:

A Python3 implementation

As we saw what’s missing in Javascript, Python seems to be very promising so let’s try it:

from itertools import chain
from collections import Counter
def neighbors(cell):
return [(cell[0] + x, cell[1] + y) for x in [-1, 0, 1] for y in [-1, 0, 1] if not x == y == 0]
def next_gen(cells):
c = Counter(chain(*[neighbors(cell) for cell in cells]))
return [cell for cell, freq in c.items()
if freq == 3 or (freq == 2 and cell in cells)]

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…).

Conclusion

Why the different implementations? I don’t know anymore, but as I said - I started with Javascript and as we can see, that implementation is kind of annoying. In my opinion the Clojure implementation is still the most consise and elegant solution, but I didn’t expect Python to be so close (when I started this blog entry I hadn’t started a Python implementation yet). If Python is so close, then Ruby will be even closer and Haskell may be even more consise and elgant - who knows (samples are welcome). Maybe everything is too close (at least for the game of live) to get something out of it…

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 :)