{{ message }}

Instantly share code, notes, and snippets.

# orb/paths.org

Created Mar 6, 2019
path finding

# 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.

# 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))))```

• 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/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")```