Building blocks of Life

Question

I'm learning Clojure, and decided to write a Conway's Game of Life clone as my starting project. I ended up dicking around for a bit before diving in, and came up with a few functions that I'd like looked over. Mainly, I'm concerned about writing them more concisely and idiomatically.

---

I'm planning on using a 1D vector to represent a 2D field. The typical equation to get the index of a vector corresponding to an (x,y) coordinate is y * width + x. Here are my first attempts:

; A 2D point representing a coordinate, or any pair of numbers
(defrecord Point [x y])

; Represents the Game of Life world.
; cells is a vector representing a 2D matrix of cells
; dims is the dimensions of the world as a Point
(defrecord Enviro [cells dims])

(defn index-of [width x y]
  (+ (* y width) x))

(defn enviro-index-of [enviro x y]
  (let [width (:x (:dims enviro))]
    (index-of width x y)))

(defn enviro-index-of-2 [enviro x y]
  (let [width (-> enviro :dims :x)]
    (index-of width x y)))

index-of is straight forward. My issue is the 2 convenience functions to get an index by supplying the Enviro instead of the width directly. I tried deconstructing the record directly in the argument list, but it complained that it didn't recognize the keyword record keys. The work-around was to just "navigate" the records manually, and bind "width" in a let. My first attempt was kind of naïve; using the accessor functions to get the Enviro, then the dimensions Point. Then I remembered the thread macro! For my second attempt, I used -> to find the width. It seems to be much cleaner, but is this as idiomatic as it gets?

---

Next, I decided to try writing a function that returns a vector containing all the points surrounding a given point. I can then check the cell at each neighboring point to see whether or not the center point should be dead or alive:

(defn generate-neighbor-points
  ([cx cy r]
   (let [start-x (- cx r)
         end-x (+ cx r 1) ; Adding 1 so it's inclusive
         start-y (- cy r)
         end-y (+ cy r 1)]
     (for [y (range start-y end-y)
           x (range start-x end-x)
           :when (and (not= x cx) (not= y cy))] ; Should actually be `or` instead of `and`
       (Point. x y))))

  ([center-point r]
   (let [cx (:x center-point)
         cy (:y center-point)]
     (generate-neighbor-points cx cy r))))

There's a couple things that I'm not happy about here:

1. The fact that this generates a list of cells, just so it can be checked. I might see if I can just make this a higher-order function that takes a callback that's executed on each Point surrounding the cell. That might be thinking too javascript-y though.

2. The fact that this requires the creation of 2 "range"s, which are really full lists. This seems to be the best way of "iterating" a range of numbers and returning a list. I'm open for suggestions on how to make this more efficient and idiomatic though.

Answer 1

There's a lot that you can streamline here. For your Point record:

; A 2D point representing a coordinate, or any pair of numbers
(defrecord Point [x y])

If you were only going to use a Point to represent a 2D Cartesian coordinate pair, this record may have some value, but not very much. The problem is the "or any pair of numbers" part. If you want to represent a pair of numbers in Clojure, just use a vector:

[4 2]

Vectors are very easy to destructure:

(defn prettify [point]
  (let [[x y] point]
    (str "(" x ", " y ")")))

(prettify [4 2])
;=> "(4, 2)"

Or if you want to just get the first or second element in a pair, you can do that as well:

(first [4 2])
;=> 4

(second [4 2])
;=> 2

You're creating a fair bit of extra work (e.g. the index-of functions) for yourself by representing your 2D world as a 1D vector. Using a 2D vector instead would eliminate the need for all three of those functions, as well as the Enviro record itself:

(def enviro (vec (repeatedly 10 (fn [] (vec (repeatedly 10 (fn [] (rand-int 10))))))))

(pprint enviro)
;; [[3 7 6 2 9 8 5 7 0 2]
;;  [0 6 4 7 1 7 0 7 1 9]
;;  [1 8 0 5 6 9 7 7 8 3]
;;  [7 9 0 8 4 3 3 7 8 6]
;;  [8 9 3 5 1 4 6 5 0 2]
;;  [6 2 3 2 9 4 8 0 3 1]
;;  [0 5 7 7 7 9 0 0 9 5]
;;  [3 8 9 8 2 0 6 3 1 9]
;;  [9 7 4 1 5 8 0 5 1 2]
;;  [9 9 1 9 4 6 3 1 8 2]]
;=> nil

(get-in enviro [4 2])
;=> 3

Or, if your matrix is sparse, you could use a map from points to values instead:

(def enviro (into {} (repeatedly 10 (fn [] [[(rand-int 10) (rand-int 10)] (rand-int 10)]))))

(pprint enviro)
;; {[2 8] 7,
;;  [5 4] 2,
;;  [4 2] 6,
;;  [7 8] 1,
;;  [9 6] 5,
;;  [1 7] 2,
;;  [2 6] 3,
;;  [6 0] 5,
;;  [3 5] 4,
;;  [0 1] 5}
;=> nil

(get enviro [4 2])
;=> 6

If you just use a plain hash map for this, you'll lose some of the spatial query capabilities of a vector, but you could get some of those back by using a quadtree or some other spatially indexed data structure. I'll leave it up to you to decide how to go about doing that in Clojure if you want to take that route.

Your generate-neighbor-points function looks pretty good. Since range and for return lazy sequences, your implementation doesn't have any real performance issues. If I were to write it myself, though, I would probably be a bit more terse:

(defn neighbors [point radius]
  (let [[xs ys] (map #(range (- % radius) (+ % radius 1)) point)]
    (for [y ys x xs :when (not= point [x y])]
      [x y])))

There's nothing wrong with just returning the sequence of neighbor points and then leaving it up to the caller to decide what to do with them. I wouldn't recommend complecting the "find all the neighbor points" logic and the "do something with each of those neighbor points" logic into the same function, because I think it would make more sense to put that second bit in a separate function:

(defn update-all [enviro points f]
  (reduce #(update-in %1 %2 f) enviro points))

Example (using the 2D vector enviro example above):

(pprint (update-all enviro (neighbors [4 3] 2) #(mod % 2)))
;; [[3 7 6 2 9 8 5 7 0 2]
;;  [0 6 4 7 1 7 0 7 1 9]
;;  [1 0 0 1 0 1 7 7 8 3]
;;  [7 1 0 0 0 1 3 7 8 6]
;;  [8 1 1 5 1 0 6 5 0 2]
;;  [6 0 1 0 1 0 8 0 3 1]
;;  [0 1 1 1 1 1 0 0 9 5]
;;  [3 8 9 8 2 0 6 3 1 9]
;;  [9 7 4 1 5 8 0 5 1 2]
;;  [9 9 1 9 4 6 3 1 8 2]]
;=> nil