Thursday, November 20, 2014

Refactoring Conway's Game of Life in Clojure

In the previous post I presented a solution of Conway's Game of Life in Clojure.

I've refactored that code in order to eliminate some duplication from the game rules.

First of all, I coded using TDD a new function will-have-a-cell? that later substituted both will-go-on-being-a-cell? and will-be-a-cell?.

These are the tests for the game rules after deleting the obsolete functions (will-go-on-being-a-cell? and will-be-a-cell?):

;...
(facts
"about game of life rules"
(fact
"a location with a cell will have a cell in next generation
if it has the right number of neighbors"
(will-have-cell? [1 2] [[1 2] [1 1] [1 3]]) => true
(will-have-cell? [1 2] [[1 2] [1 1]]) => false
(will-have-cell? [1 2] [[1 2] [1 1] [1 3] [2 2]]) => true
(will-have-cell? [1 2] [[1 2] [0 2] [1 1] [1 3] [2 2]]) => false)
(fact
"a location without a cell will have a cell in next generation
if it has the right number of neighbors"
(will-have-cell? [1 2] [[1 1] [1 3]]) => false
(will-have-cell? [1 2] [[1 1] [1 3] [2 2]]) => true
(will-have-cell? [1 2] [[1 1]]) => false))
;...
and this is the new function's code:

; ...
(defn num-neighbors-being-a-cell [cell cells]
(count (filter (neighbors cell) cells)))
(defn has-cell? [loc cells]
(= loc (some #{loc} cells)))
(defn will-have-a-cell? [loc cells]
(let [num-neighbors (num-neighbors-being-a-cell loc cells)]
(or (= num-neighbors 3)
(and (= num-neighbors 2)
(has-cell? loc cells)))))
;...
Once I had the new function I used it inside both keep-being-cells and new-cells functions to highlight the duplication between them:

;...
(defn keep-being-cells [cells]
(set
(filter
#(will-have-a-cell? % cells)
cells)))
(defn new-cells [cells]
(set
(filter
#(will-have-a-cell? % cells)
(candidates-to-be-a-cell cells))))
(defn next-cells [cells]
(clojure.set/union
(keep-being-cells cells)
(new-cells cells)))
;...
Then I eliminated that duplication by using will-have-a-cell? directly in next-cells function, which made both keep-being-cells and new-cells obsolete:

;...
(defn all-neighbors-locations [cells]
(reduce clojure.set/union
(map neighbors cells)))
(defn next-cells [cells]
(set
(filter
#(will-have-a-cell? % cells)
(all-neighbors-locations cells))))
;...
Notice how will-have-a-cell? is used to filter all the possible locations (the current cells and their neighbors) which are given by the new all-neighbors-locations function.

Then I eliminated all the obsolete functions and their tests and did some renaming of the remaining functions, local bindings and parameters.

These are the resulting tests:

(ns game-of-life.core-test
(:use midje.sweet)
(:use [game-of-life.core]))
(facts
"about Game of Life"
(facts
"about neighbors"
(fact
"the neighbors of a given location can be known"
(neighbors [1 1]) => #{[0 0] [0 1] [0 2] [1 0] [1 2] [2 0] [2 1] [2 2]}
(neighbors [0 0]) => #{[-1 -1] [-1 0] [-1 1] [0 -1] [0 1] [1 -1] [1 0] [1 1]})
(fact
"the number of neighbors of a given location which have a cell can be known"
(num-neighbors-with-a-cell [1 2] [[1 2] [4 5] [1 3]]) => 1
(num-neighbors-with-a-cell [1 2] [[1 2] [1 1] [1 3]]) => 2
(num-neighbors-with-a-cell [10 20] [[1 2] [1 1] [1 3]]) => 0))
(facts
"about game of life rules"
(fact
"a location with a cell will have a cell in next generation
if it has 2 or 3 neighbors"
(will-have-cell? [1 2] [[1 2] [1 1] [1 3]]) => true
(will-have-cell? [1 2] [[1 2] [1 1]]) => false
(will-have-cell? [1 2] [[1 2] [1 1] [1 3] [2 2]]) => true
(will-have-cell? [1 2] [[1 2] [0 2] [1 1] [1 3] [2 2]]) => false)
(fact
"a location without a cell will have a cell in next generation
if it has 3 neighbors"
(will-have-cell? [1 2] [[1 1] [1 3]]) => false
(will-have-cell? [1 2] [[1 1] [1 3] [2 2]]) => true
(will-have-cell? [1 2] [[1 1]]) => false))
(facts
"about Still lifes"
(fact
"a Block is a still life
(http://en.wikipedia.org/wiki/Still_life_%28cellular_automaton%29#Blocks)"
(let [a-block #{[0 0] [0 1] [1 1] [1 0]}
five-gens (game-of-life a-block 5)]
(nth five-gens 1) => a-block
(nth five-gens 2) => a-block
(nth five-gens 3) => a-block
(nth five-gens 4) => a-block))
(fact
"a Beehive is a still life
(http://www.conwaylife.com/wiki/Beehive)"
(let [a-beehive #{[0 1] [0 2] [1 0] [1 3] [2 1] [2 2]}
five-gens (game-of-life a-beehive 5)]
(nth five-gens 1) => a-beehive
(nth five-gens 2) => a-beehive
(nth five-gens 3) => a-beehive
(nth five-gens 4) => a-beehive))
(fact
"a Loaf is a still life
(http://en.wikipedia.org/wiki/Still_life_%28cellular_automaton%29#Loaves)"
(let [a-loaf #{[0 1] [0 2] [1 0] [1 3] [2 1] [2 3] [3 2]}
five-gens (game-of-life a-loaf 5)]
(nth five-gens 1) => a-loaf
(nth five-gens 2) => a-loaf
(nth five-gens 3) => a-loaf
(nth five-gens 4) => a-loaf))
(fact
"a Boat is a still life
(http://commons.wikimedia.org/wiki/File:Game_of_life_boat.svg)"
(let [a-boat #{[0 0] [0 1] [1 0] [1 2] [2 1]}
five-gens (game-of-life a-boat 5)]
(nth five-gens 1) => a-boat
(nth five-gens 2) => a-boat
(nth five-gens 3) => a-boat
(nth five-gens 4) => a-boat)))
(facts
"about Oscillators"
(fact
"a Blinker oscillates with period two
(http://en.wikipedia.org/wiki/File:Game_of_life_blinker.gif)"
(let [a-blinker #{[0 1] [0 2] [0 0]}
a-blinker-next #{[0 1] [1 1] [-1 1]}
five-gens (game-of-life a-blinker 5)]
(nth five-gens 1) => a-blinker-next
(nth five-gens 2) => a-blinker
(nth five-gens 3) => a-blinker-next
(nth five-gens 4) => a-blinker))
(fact
"a Toad oscillates with period two
(http://en.wikipedia.org/wiki/File:Game_of_life_toad.gif)"
(let [a-toad #{[0 3] [1 0] [1 2] [0 2] [1 1] [0 1]}
a-toad-next #{[0 3] [1 0] [0 0] [-1 2] [1 3] [2 1]}
five-gens (game-of-life a-toad 5)]
(nth five-gens 1) => a-toad-next
(nth five-gens 2) => a-toad
(nth five-gens 3) => a-toad-next
(nth five-gens 4) => a-toad)))
(facts
"about Gliders"
(fact
"a Glider moves diagonally with period 4
(http://en.wikipedia.org/wiki/File:Game_of_life_animated_glider.gif)"
(let [a-glider #{[0 0] [0 1] [0 2] [1, 0] [2, 1]}
five-gens (game-of-life a-glider 5)]
(nth five-gens 1) => #{[0 0] [0 1] [1 0] [-1 1] [1 2]}
(nth five-gens 2) => #{[0 0] [1 0] [-1 1] [-1 0] [0 2]}
(nth five-gens 3) => #{[0 0] [-1 1] [-1 0] [1 1] [0 -1]}
(nth five-gens 4) => #{[-1 1] [-1 0] [0 -1] [1 0] [-1 -1]}))))
and this is the resulting code:

(ns game-of-life.core)
(defn neighbors [[x-cell y-cell]]
(set (for [x (range (dec x-cell) (+ x-cell 2))
y (range (dec y-cell) (+ y-cell 2))
:when (not (and (= x x-cell) (= y y-cell)))]
[x y])))
(defn num-neighbors-with-a-cell [loc cells]
(count (filter (neighbors loc) cells)))
(defn has-cell? [loc cells]
(= loc (some #{loc} cells)))
(defn will-have-cell? [loc cells]
(let [num-neighbors (num-neighbors-with-a-cell loc cells)]
(or (= num-neighbors 3)
(and (= num-neighbors 2)
(has-cell? loc cells)))))
(defn locations [cells]
(reduce clojure.set/union (map neighbors cells)))
(defn next-cells [cells]
(set (filter #(will-have-cell? % cells) (locations cells))))
(defn game-of-life [cells num-iter]
(take num-iter (iterate next-cells cells)))
which is slightly shorter than the one in the previous version.

As usual I commited the code after every passing test and every refactor.

You will notice a problem I had with Midje :autotest not reacting properly after some of the renamings I did. I had to restart it so that it could take into account the changes.

If you want to follow the whole process, you can find the commits step by step here.

You can also find the resulting code in GitHub.

No comments:

Post a Comment