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.

13 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. Ideal magic formula for babyliss for you to explore immediately.
    cheap new arrival marc by marc jacobs classic petal to the metal leather natasha black bag sizzling sale http://www.mimorihome.com/etc/marc-by-marc-jacobs-duffle/cheap-new-arrival-marc-by-marc-jacobs-classic-petal-to-the-metal-leather-natasha-black-bag-sizzling-sale.html

  13. Thanks for your personal marvelous posting! I definitely enjoyed reading it, you
    might be a great author. I will ensure that I bookmark your blog and definitely will come back at some point.
    I want to encourage continue your great posts,
    have a nice evening!

    Comment by lusus.com.br — 1 September 2014 @ 13 h 09 min

RSS feed for comments on this post. TrackBack URI

Leave a comment

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