Conway’s Game of Life

unsorted — cgrand, 19 August 2011 @ 20 h 01 min

APL is famous for having a 1-liner for Conway’s game of life.
Being very efficient at implementing a matrix-based solution of Conway’s game of life should come to no suprise from an array-oriented language.

The way you model data determines your code. Clojure encourages what I call relational-oriented programming. That is modeling with sets, natural identifiers (thanks to composite values) and maps-as-indexes.

If you pick the right representation for the state of the board, you end up with a succinct implementation:

(defn neighbours [[x y]]
  (for [dx [-1 0 1] dy (if (zero? dx) [-1 1] [-1 0 1])] 
    [(+ dx x) (+ dy y)]))

(defn step [cells]
  (set (for [[loc n] (frequencies (mapcat neighbours cells))
             :when (or (= n 3) (and (= n 2) (cells loc)))]
         loc)))

Let’s see how it behaves with the “blinker” configuration:

(def board #{[1 0] [1 1] [1 2]})
; #'user/board
(take 5 (iterate step board))
; (#{[1 0] [1 1] [1 2]} #{[2 1] [1 1] [0 1]} #{[1 0] [1 1] [1 2]} #{[2 1] [1 1] [0 1]} #{[1 0] [1 1] [1 2]})

Great, it oscillates as expected!

From this step can be distilled a generic topology-agnostic life-like automatons stepper factory (phew!) but this is a subject for another post or — shameless plug — a book.

12 Comments »

  1. I couldn’t believe that such a short solution could possibly work, so I copied it into my IDE to play around with it. I verified that a glider worked and that a 3 cell diagonal died off as expected.

    Very cool!

    Can’t wait for your book to come out.

    Comment by Bob Shock — 22 August 2011 @ 1 h 53 min
  2. You make your point with elegance. impressive!

    Comment by johan martinsson — 22 August 2011 @ 8 h 59 min
  3. [...] Otherwise here is a beautiful implementation of Conway’s Game of Life by Christophe Grand: [...]

  4. [...] and Rupert decided to look at someone else’s solution in Clojure, to understand how a functional approach using list comprehensions can lead to a very concise [...]

    Pingback by Adastral Park code retreat at Kerry Buckley — 1 November 2011 @ 14 h 09 min
  5. [...] 另外,下面是一个由Christophe Grand实现的生命游戏的Clojure版本: [...]

    Pingback by 过去5年编程语言的演化(下) — 15 November 2011 @ 14 h 14 min
  6. [...] session se termine par une session de coding pré-enregistrée, montrant l’implémentation du jeu de la vie de Conway. Les résultats intermédiaires sont affichés après chaque fonction développée, ce qui [...]

  7. I put together a screencast of building this solution interactively in Clojure for a presentation: check it out here if you’re interested… http://www.youtube.com/watch?v=lgsAztXDuH0

    Comment by Alex Miller — 4 December 2011 @ 16 h 53 min
  8. [...] Christophe’s Game of Life [...]

    Pingback by fogus: The best things and stuff of 2011 — 31 December 2011 @ 17 h 01 min
  9. [...] 另外,下面是一个由Christophe Grand实现的生命游戏的Clojure版本: (defn neighbours [[x y]] (for [dx [-1 0 1] dy (if (zero? dx) [-1 1] [-1 0 1])] [(+ dx x) (+ dy y)])) [...]

  10. I wrote an in-depth explanation of your solution. It should be understandable to non-Clojure programmers and newcomers.

    http://programmablelife.blogspot.com/2012/08/conways-game-of-life-in-clojure.html

    Comment by naeg — 27 August 2012 @ 18 h 08 min
  11. […] implémentation java de la solution ultra bref en […]

  12. Hi, Christophe. This beautiful solution results from the insight that everything you need is in the neighbors collection. It is not simply the result of using Clojure, although Clojure certainly makes the solution succinct. Do you agree?

    Arthur

    Comment by Arthur Gardner — 3 June 2016 @ 23 h 27 min

RSS feed for comments on this post. TrackBack URI

Leave a comment

(c) 2016 Clojure and me | powered by WordPress with Barecity