Many AoC problems required some sort of path finding - shortest path, cheapest path according to the rules of the world.
- 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/
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
To answer this we need to maintain two pieces of data
seen: the nodes we have visitedfrontier: 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))))- loop/recur
- .contains
- subvec
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))))- no literal syntax for
PersistentQueue peek~/~pop~/~conj
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)))))))))
priority-map- like a queue, but sorts on value (sorted map sorts on key)
peekandpopand work as expectedassocadds 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
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}))))))))
priority-map-keyfn, using:distanceas priority keymerge-withuses the:distanceto the next node- chooses the path with the shortest distance
- in this example, it will always be the already known path
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}]))))))))
path-infohas:jumps,:costand:prev- keyfn (priority) is
:cost
- keyfn (priority) is
merge-withselects the item withmin-keycost
Piak to 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")