I’m actually a little proud of this one – this simple implementation of A* search seems to be one of the prettier pieces of code I have written, and it was implemented abstractly enough to solve problems 81, 82, and 83 without changing the core algorithm.

Problem 81 asks us to find the lowest-cost path through a matrix. While the algorithm from problem 18 or 67 might work here, it wouldn’t work for problem 83, and I wanted to kill all three of these problems in one fell swoop. [A](http://en.wikipedia.org/wiki/A) was the ax that I used.

;; Thanks to cgrande for making me aware of priority-map
;; http://clj-me.cgrand.net/2010/09/04/a-in-clojure/

(use '[clojure.contrib.duck-streams :only (read-lines)]
     '[clojure.contrib.priority-map :only [priority-map]])

(defn load-matrix [file]
  (vec
   (for [l (read-lines file)]
     (->> (partition-by #(= % \,) l)
          (map #(apply str %))
          (filter #(not (= "," %)))
          (map #(Integer/parseInt %))
          vec))))

(defn a*-search
  "Performs an a* search over the data using heuristic est-cost.
  
  ARGUMENTS:
    est-cost(e)  The estimate of the cost to the goal.
    neighbors(e) Returns map of neighbors at i,j and their costs
    start        The element at which to start
    goal?(e)     Function that checks if the goal has been reached.

  RETURNS: 
    The list of elements in the optimal path. "
  [est-cost neighbors start goal?]
  (loop [open   (priority-map start [0 nil])
         closed {}]
    (let [[e [s p]] (first open)]
      (cond
       (nil? e)  "Path not found! No more elements to try!"
       (goal? e) (->> (conj (iterate #(second (closed %)) p) e)
                      (take-while #(not (nil? %)))
                      reverse)
       :else (recur
              (merge-with #(if (< (first %1) (first %2)) %1 %2)
                          (dissoc open e)
                          (into {} (for [[n ns] (neighbors e)
                                         :when (not (get closed n))]
                                     [n [(+ ns s (est-cost n)) e]])))
              (assoc closed e [s p]))))))

(defn euler-81 []
  (let [mat   (load-matrix "/zzz/work/matrix.txt")
        m     (count mat)
        n     (count (first mat))
        cost  (fn [[i j]] (nth (nth mat (dec i)) (dec j)))
        start [1 1]
        goal  [m n]
        goal? (fn [e] (= e goal))
        est   (fn [[i j]] (+ (- m i) (- n j)))
        neigh (fn [[i j]]
                (merge
                 (when (< i m) {[(inc i) j] (cost [(inc i) j])})
                 (when (< j n) {[i (inc j)] (cost [i (inc j)])})))
        path  (a*-search est neigh start goal?)]
    (reduce + (map cost path))))

(time (euler-81)) ;; "Elapsed time: 153.287587 msecs"

It was really, really tempting to keep the map from elements->parents separate from the map of elements->score, so that the children could simply be merged with (merge-with min A B) instead of the more complicated expression above, but in the end that required simultaneously processing two maps based on the contents of one map, and felt even more awkward than the above solution.

In the future, it would be interesting to modify the A* search to be concurrent – by searching the nth lowest-scoring candidates simultaneously, we could perhaps achieve some significant search speed improvement, especially for problems like this one where the heuristic information is very weak.

Also, this problem in fact very nearly reduces to Dijkstra’s algorithm because the admissible heuristic estimated-cost-to-goal function improves efficiency so little in this case.

It may also be interesting to compare this a* search function to that of cgrande’s.