# Project Euler Problem 82 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 []
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 []
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.