Conway’s Game of Life
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.
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.
You make your point with elegance. impressive!
[...] Otherwise here is a beautiful implementation of Conway’s Game of Life by Christophe Grand: [...]
[...] 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 [...]
[...] 另外，下面是一个由Christophe Grand实现的生命游戏的Clojure版本： [...]
[...] 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 [...]
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
[...] Christophe’s Game of Life [...]
[...] 另外，下面是一个由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)])) [...]
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
[…] implémentation java de la solution ultra bref en […]
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
[…] of the more remarkable implementations of Life that I’ve uncovered is written in Clojure, and may be found here. There is also a one line implementation written in APL, but I find it entirely […]