Month: September 2012

Conway’s Game of Life in Scala

Posted by – September 2, 2012

… or, Cool Uses of flatMap and Sets

Via Hacker News I found a blog post about  Conway’s Game of Life in Scala, claiming to solve it in 10 lines. The author’s aim was to translate from a short piece of Clojure. The result is… well, take a look at that blog and judge for yourself.

Now this might be the inevitable result of trying to translate from a dynamic syntaxless language made up of S-expressions (whatever the heck they are), but surely Scala is capable of something more comprehensible. So, stepping into my Code Golf slacks and wielding the book of Wikipedia, here’s what I came up with:

def vicinity (p: (Int, Int)) = for { dx <- Set(-1,0,1)
                                     dy <- Set(-1,0,1) } yield (p._1 + dx, p._2 + dy)

def next (ps: Set[(Int, Int)]) = ps flatMap vicinity filter { p =>
  val ns = vicinity(p) - p count ps
  ns == 3 || ns == 2 && ps(p)

def display (width: Int, height: Int, ps: Set[(Int, Int)]) =
  Seq.tabulate(height, width) { (y, x) => if (ps(x, y)) 'X' else '.' } map (_.mkString)

Not optimized, but hopefully that’s not too unreadable (and it’s only like 5 lines, if my lines were as long as Original Blogger’s). Some explanation, if required:

vicinity takes a grid point and returns the 3×3 set of points centred on that one.

next takes a Set of points and outputs the next set. Instead of looking at every point on our infinite plane, we just consider the ones surrounding our set of points (since these are the only ones that can have neighbours), which is `ps flatMap vicinity`.

The points alive in the next generation are determined by the number of neighbours (ns), which is the points in the vicinity minus itself (`vicinity(p) – p`), counted if they were alive in the previous generation. See how we can use the Set `ps` as a function, since Set extends Function. If there are 3 neighbours, the point is alive. If there are 2, the point is alive only if it was already alive. Otherwise the point is dead (filtered out).

display just turns a set of points into something displayable, a sequence of Strings

Now, this isn’t exactly equivalent to the other version, since that requires you to supply functions for the number of neighbours, whereas I’ve already incorporated them. (It would be easy enough to do it like that – exercise for reader etc – but I didn’t really see the point.)

Anyway, by now I’m sure you’ve pasted the above into your REPL and are disappointed that no gliders have yet started whizzing around your screen. Worry not, young Grasshopper! You just need to supply some data and iterate:

  val g = Set((2, 0), (2, 1), (2, 2), (1, 2), (0, 1))
  val frames = Seq.iterate(g, 100)(next)
  frames foreach { f => display(25, 25, f) foreach println; println(); Thread.sleep(100) }

Recognise that? Yes, it’s a glider, the universal symbol of people with too much time on their hands.

Now, go and build a GUI.