• Clojure
  • 37 lines
  • 39 views
  • Pasted by anonymous on August 18, 2013
;;; 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))))))))))

Did you know? CLOSE

  • There are keyboard shortcuts!
    • When Creating A Paste
      • ALT+P Toggle Private
      • CTRL+Enter Create Paste
      • ALT+W Toggle word wrap
    • When Viewing A Paste
      • ALT+G Go to a line
      • ALT+CTRL+E Edit the paste
      • ALT+R Show the raw code
  • There are URL options!
    • When Creating A Paste
      • ?lang=Javascript to default to javascript
    • When Viewing A Paste
      • #L-N Jump to line number N
?