Project Euler Problem 83

Ivar Thorson bio photo By Ivar Thorson

Problem 83 can be solved with A* exactly like the we did in problem 81. The only code that needs to be changed is the neighbors function neigh and the estimated cost-to-goal function est. Everything else can be reused from problem 81.

(defn euler-83 []
  (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]] 0)
        neigh (fn [[i j]]
                 (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])})
                 (when (< 1 j) {[i (dec j)] (cost [i (dec j)])})))
        path  (a*-search est neigh start goal?)]
    (reduce + (map cost path))))

(time (euler-83))

With est set to always return zero, the A* search becomes effectively a memory-hungry version of Dijkstra’s Algorithm.