As I mentioned in the previous post (#81), we can use [A](http://en.wikipedia.org/wiki/A) to easily solve problem 82 as well.

One way to solve this problem is to perform the A* search from each element on the leftmost column, and then take the minimum length path amongst all these results.

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


(time (euler-82)) ;; "Elapsed time: 8053.744512 msecs"

Note how we can memoize the functions passed to A* to improve the speed of A* searches slightly. We possibly could probably have come up with a faster solution by memoizing the collections internal to A, but that would have meant exposing the details of the A to the outside world, which I don’t think is advisable in this case.

A better approach towards improving performance is to start thinking outside the box – or in this case, outside the grid. If we redefine the cost and neighbor functions to have a special ‘leftmost’ starting point that has all the elements in the first column as children, we can solve the problem in a single A* search. Let’s mark this new starting point with the coordinate [0 0], to mark that it is ‘off the grid’.

(defn euler-82-better []
  (let [mat   (load-matrix "/path/to/matrix.txt")
        m     (count mat)
        n     (count (first mat))
        start [0 0] ;; special node left of the whole matrix
        goal? (fn [e] (= (second e) n))
        cost  (fn [[i j]]
                (if (= [i j] [0 0])
                  0
                  (nth (nth mat (dec i)) (dec j))))
        est   (fn [[i j]] (+ (- m i) (- n j)))
        neigh (fn [[i j]]
                (if (= [i j] [0 0])
                  (map (fn [i] [[i 1] (cost [i 1])]) (range 1 (inc m)))
                  (merge
                   (when (< i m) {[(inc i) j] (cost [(inc i) j])})
                   (when (< j n) {[i (inc j)] (cost [i (inc j)])})
                   (when (< 1 i) {[(dec i) j] (cost [(dec i) j])}))))
        path  (a*-search est neigh start goal?)]
    (reduce + (map cost path))))

(time (euler-82-better)) ;; "Elapsed time: 244.770152 msecs"

This really shows the versatility of the A* search method.