;;; A solution for http://programmingpraxis.com/2013/08/16/monkey-grid-puzzle
;;;
;;; The solution originally posted as http://pastebin.com/fyQ4BNSD generates
;;; a lazy sequence of all positions reachable by the monkey, determining the
;;; number of such positions by simply counting the length of the sequence.
;;;
;;; This solution computes the number of squares reachable by the monkey
;;; starting at [0,0] without generating an intermediate sequence and is
;;; correspondingly faster.
(def monkey-count
(letfn [(neighbors [[x y]]
[[(inc x) y]
[x (inc y)]])
(sum-of-digits [^long n]
(loop [n n, s 0]
(if (zero? n)
s
(recur (quot n 10) (+ s (rem n 10))))))
(accessible? [[x y]]
(>= 19 (+ (sum-of-digits x)
(sum-of-digits y))))
(score [[x y]]
(if (zero? x)
(if (zero? y) 1 2)
(if (zero? y) 2 4)))]
(fn monkey-count
([] (monkey-count [0 0]))
([origin] (monkey-count #{} #{origin}))
([visited candidates]
(if (empty? candidates)
(reduce + 0 (map score visited))
(recur (into visited candidates)
(set (filter (every-pred (complement candidates)
(complement visited)
accessible?)
(set (mapcat neighbors candidates))))))))))