knight's random walk

knight.clj

;; http://www.johndcook.com/blog/2012/05/08/a-knights-random-walk/
;;
;; Start a knight at a corner square of an otherwise-empty chessboard. Move the
;; knight at random by choosing uniformly from the legal knight-moves at each
;; step. What is the mean number of moves until the knight returns to the
;; starting square?

(def MAXPOS 7)

; (pos, move) -> pos
(defn move-knight 
  [[posX posY] [moveX moveY]] 
    [(+ posX moveX) (+ posY moveY)])

(defn valid-move?
  "determine if a proposed move stays on the board"
  [pos move]
   (let [[x y] (move-knight pos move)]
     (and (<= 0 x)
          (<= x MAXPOS)
          (<= 0 y)
          (<= y MAXPOS))))

;; tempted to generate this more slickly, but this is clear enough
(def all-moves [[ 2  1] [ 2 -1] [-2  1] [-2 -1] 
                [ 1  2] [ 1 -2] [-1  2] [-1 -2]])

(defn valid-moves [pos]
  (filter (partial valid-move? pos) all-moves))

(defn random-select 
  "return a randomly-selected element from a collection, or nil if coll is empty"
  [coll]
   (if (empty? coll) 
     nil 
     (nth coll (rand-int (count coll)))))

(defn step
  [pos] (move-knight pos (random-select (valid-moves pos))))

(defn game-states
  "returns an infinite stream of game states given an initial position"
  ([]    (game-states [0 0]))   ; default ic
  ([pos] (iterate step pos)))

(defn moves-until-returned []
  (count (take-while (partial not= [0 0])
                     (rest (game-states)))))

(defn mean [coll]
  (if (empty? coll) 
    0.0
    (/ (reduce + coll) (double (count coll)))))
; `double` here is a cast so that i don't end up with a rational

(defn mean-moves-until-returned [n]
  (mean (for [x (range n)]
          (moves-until-returned))))

; might as well try a parallel version
(defn mmur-par [n]
  (mean (pmap (fn [x] (moves-until-returned)) (range n))))

; shits/giggles
(defn benchmark [n] 
   (do 
     (time (mean-moves-until-returned n)) 
     (time (mmur-par n))))

; quad core i5 laptop
; user=> (benchmark 10000)
; "Elapsed time: 12964.985 msecs"
; "Elapsed time: 2529.414911 msecs"
; 169.4122
; the analytic answer is 168