Advertisement
Guest User

Hamilton path in clj

a guest
Jun 1st, 2011
153
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. (def field-size 5)
  2. (def field-size-1 (- field-size 1))
  3. (def cell-count 25)
  4.  
  5. (def field [[:S  :S  :SW :W  :SW]
  6.             [:E  :SE :SE :SE :SW]
  7.             [:S  :N  :N  :W  :SW]  
  8.             [:NE :NE :NW :SW :N ]
  9.             [:E  :NE :W  :N  :Z]])
  10.  
  11. (def directions
  12.      { :NW [-1 -1], :N [0 -1], :NE [1 -1]
  13.       :W [-1 0], :E [1 0],
  14.       :SW [-1 1], :S [0 1], :SE [1 1]})
  15.  
  16. (defn in-field [x y]
  17.   (and (>= x 0) (>= y 0)
  18.        (< x field-size) (< y field-size)))
  19.  
  20. (defn waylist [x y dir]
  21.   (let [[dirx diry] (directions dir)]
  22.     (when (in-field x y)
  23.       (conj (waylist (+ x dirx) (+ y diry) dir) [x y]))))
  24.  
  25. (defn can-visit [visits x y]
  26.   (and (in-field x y)
  27.        (= (get-in visits [x y]) 0)))
  28.  
  29. (defn create-array [dim size value]
  30.   (letfn [(ca [dim current]
  31.               (if (zero? dim)
  32.                 current
  33.                 (ca (dec dim) (into [] (repeat size current)))))]
  34.     (ca dim value)))
  35.  
  36. (defn visit [visits x y n]
  37.   (letfn [(vis [x y]
  38.                (update-in visits [x y] (constantly n)))
  39.  
  40.           (unvis [x y]
  41.                  (update-in visits [x y] (constantly 0)))
  42.           (special-case? []
  43.                          (and (= x 2) (= y 3) (not (= n 17))))
  44.           (end-case? [] (and (= x field-size-1)
  45.                              (= y field-size-1)
  46.                              (= n cell-count)))]
  47.     (when (can-visit visits x y)
  48.       (let [new-visits (vis x y)]
  49.         (cond (end-case?) new-visits
  50.               (special-case?) nil
  51.               :else (some (complement nil?)
  52.                           (map (fn [[nx ny]]
  53.                                  (visit new-visits nx ny (+ 1 n)))
  54.                                (rest (waylist x y (get-in field x y))))))))))
  55.  
  56. (def result (visit (create-array 2 5 0)
  57.                    4 4 25))
  58.  
  59. (def middle-sum (reduce + (result 2)))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement