path finding

paths.org

pathfinding in Clojure

Help, I’m stuck in a maze

Motivation

Many AoC problems required some sort of path finding - shortest path, cheapest path according to the rules of the world.

Example: elves vs goblins

• https://lamperi.name/aoc/
• https://www.youtube.com/watch?v=-VDudVOM8As
• https://www.reddit.com/r/adventofcode/comments/a6kuwv/day_15_visualization_using_kenneynl_sprites/

Representation

Often the representation is a 2D/3D grid and sometimes we can only compute the positions and transitions, but logically we can usually easily represent the world as a directed grid of nodes and edges

• keys are the nodes (name/
• values are a vector of connected nodes

(def edges
  {:node1 [:node2 :node3]
   :node2 [:node3 :node4]
   :node5 []})

We can ask if an edge exists:

(edges :node1)

[:node2 :node3]

Or take an action on them:

(doseq [neighbor (edges :node1)]
  (println (format "%s is connected to %s" :node1 neighbor)))

:node1 is connected to :node2
:node1 is connected to :node3

Is there a path from :a to :b?

To answer this we need to maintain two pieces of data

• seen: the nodes we have visited
• frontier: the nodes we still want to visit

Algorithm:

• until we have visited the destination or have nowhere else to do
• select the next unvisited node
  • find all the neighbors that we don’t know about yet
  • add them to the frontier

(defn path? [jumps from to]
  (loop [seen #{}
         frontier [from]]
    (if (seen to)
      true
      (if-let [next-system (first frontier)]
        (let [neighbors (->> (jumps next-system)
                             (remove seen)
                             (remove #(.contains frontier %)))]
          (recur (conj seen next-system)
                 (into (subvec frontier 1)
                       neighbors)))
        false))))

implementation details

• loop/recur
• .contains
• subvec

persisent queue

Vector is the wrong structure here. We are pushing on one end and popping off the other.

(defn pathq? [jumps from to]
  (loop [seen #{}
         frontier (conj (clojure.lang.PersistentQueue/EMPTY)
                        from)]
    (if (seen to)
      true
      (if-let [next-system (peek frontier)]
        (let [neighbors (->> (jumps next-system)
                             (remove seen)
                             (remove #(.contains frontier %)))]
          (recur (conj seen next-system)
                 (into (pop frontier)
                       neighbors)))
        false))))

notes

• no literal syntax for PersistentQueue
• peek~/~pop~/~conj

How many steps are there from :a to :b

Similar to path? except we need to track the distance to each node and not just whether we have seen it.

(defn path-length [jumps from to]
  (loop [visited {}
         frontier (pm/priority-map from 0)]
    (let [[next-system distance] (peek frontier)]
      (if (or (nil? next-system)
              (= to next-system))
        distance
        (recur (assoc visited next-system distance)
               (merge-with min
                           (pop frontier)
                           (zipmap (remove visited
                                           (jumps next-system))
                                   (repeat (inc distance)))))))))

misc notes

• priority-map
  • like a queue, but sorts on value (sorted map sorts on key)
  • peek and pop and work as expected
  • assoc adds new item
• merge-with to choose the new path to the frontier or the old path based on distance
  • note with our system here the new distance will never be less than a known distance, so we merge-with (fn [x y] x) would also work

But how do I actually get from :a to :b

We’d like to be able to construct the actual path. To do that, replace the distance with a path-info structure that will save the distance as well as the system we came from. We can use this back link to reconstruct the final path

(defn bfs-path [jumps from to]
  (loop [visited {}
         frontier (pm/priority-map-keyfn :distance
                                         from
                                         {:distance 0 :prev nil})]
    (let [[next-system path-info] (peek frontier)
          next-visited (assoc visited next-system path-info)]
      (if (or (nil? next-system)
              (= to next-system))
        (reverse (backpath next-visited next-system))

        (recur next-visited
               (merge-with #(min-key :distance %1 %2)
                           (pop frontier)
                           (zipmap (remove visited
                                           (jumps next-system))
                                   (repeat
                                    {:distance
                                       (inc
                                         (:distance path-info))
                                     :prev next-system}))))))))

notes

• priority-map-keyfn, using :distance as priority key
• merge-with uses the :distance to the next node
  • chooses the path with the shortest distance
  • in this example, it will always be the already known path

Optimizing for things other than path length

suppose instead of computing the minimal path, we compute the “easiest” path. In our data set, each system has a security status. There are “High Security”, “Low Security” and “Null Security” systems. We’ll assign a cost of 1, 3, and 7, respectively to represent how easy or hard it is to cross the system:

(defn jump-cost [system]
  (if-let [sec (system-sec system)]
    (cond
      (>= sec 0.5) 1
      (>= sec 0)   3
      :else        7)
    Integer/MAX_VALUE))

(defn djkstra [jumps from to]
  (loop [visited {}
         frontier (pm/priority-map-keyfn :cost
                                         from
                                         {:jumps 0
                                          :cost 0
                                          :prev nil})]
    (let [[next-system info] (peek frontier)
          next-visited (assoc visited next-system info)]
      (if (or (nil? next-system)
              (= to next-system))
        (reverse (backpath next-visited next-system))

        (recur next-visited
               (merge-with #(min-key :cost %1 %2)
                           (pop frontier)
                           (into {}
                                 (for [system
                                       (remove visited
                                         (jumps next-system))]
                                   [system
                                    {:jumps (inc (:jumps info))
                                     :cost (+ (:cost info)
                                              (jump-cost system))
                                     :prev next-system}]))))))))

notes

• path-info has :jumps, :cost and :prev
  • keyfn (priority) is :cost
• merge-with selects the item with min-key cost

Some examples

Piak to Elanoda

• http://evemaps.dotlan.net/map/Lonetrek#sec

http://evemaps.dotlan.net/route/Piak:Elanoda

(bfs-path gate-map "Piak" "Elanoda")

("Piak" "Onnamon" "Kinakka" "Raihbaka" "Ohbochi" "Elanoda")

http://evemaps.dotlan.net/route/2:Piak:Elanoda (similar, but not the same)

(djkstra gate-map "Piak" "Elanoda")

("Piak" "Elonaya" "Nonni"
 "Aunenen" "Otalieto" "Endatoh"
 "Aivoli" "Uesuro" "Elanoda")

(djkstra gate-map "Piekura" "Usi")

("Piekura" "Saatuban" "Isanamo"
 "Alikara" "Kaimon"  "Kausaaja"
 "Auviken" "Ohvosamon" "Jeras"
 "Usi")

http://evemaps.dotlan.net/route/373Z-7:SVB-RE