Advent of Code: Day 15 - Chiton · Andrey Listopadov

We’ve almost reached the exit of the cave! But there’s another problem, the walls are getting closer together, and the walls are covered with chitons, and we need to find the safest way so we wouldn’t damage any. Our input is a map of risk values, and we need to reach the bottom right coordinate:

The highlighted numbers are the shortest path with the lowest risk level total of 40. Our task is to find such a path.

Well… Now I’m completely lost! I’ve never written a path-finding algorithm before, and unfortunately the university where I studied completely skipped anything related to graphs. I’m not sure why, though, as I was studying to become a bare-metal programmer, maybe they don’t need graphs, I don’t know. But we need some kind of algorithm to deal with this as a graph of points with weights. After a bit of searching, I’ve found that the Dijkstra’s algorithm is likely what I need.

Now, this algorithm works something like this (or at least how I understand it):

We choose the first node with the lowest value and mark it as visited
Next, we choose neighbor nodes and select the one which has a lower weight.
If this node is the end node, we exit, if not we mark it as visited and freeze its weight to the sum of previous weights up to this node and node’s weight.
We repeat the process, changing frozen weights if the new weight is smaller than the current one.

A better explanation can be found on the Wikipedia page I’ve linked, so if you’re interested, I suggest you read it there, as I could mess the explanation in some places. Let’s start by parsing the input:

day14> (ns day15 (:require [aoc-commons :refer [parse-long slurp-lines]]))
nil
day15> (defn read-input []
         (->> "inputs/day15-ex"
              slurp-lines
              (map seq)
              (mapv #(mapv parse-long %))))
#'day15/read-input
day15> (read-input)
[[1 1 6 3 7 5 1 7 4 2]
 [1 3 8 1 3 7 3 6 7 2]
 [2 1 3 6 5 1 1 3 2 8]
 [3 6 9 4 9 3 1 5 6 9]
 [7 4 6 3 4 1 7 1 1 1]
 [1 3 1 9 1 2 8 1 3 7]
 [1 3 5 9 9 1 2 4 2 1]
 [3 1 2 5 4 2 1 6 3 9]
 [1 2 9 3 1 3 8 5 2 1]
 [2 3 1 1 9 4 4 5 8 1]]

Nice. Now, we need to implement the algorithm. The Wikipedia page has some pseudo-code examples, and also mentions a priority queue. The algorithm actually computes the path, but we’re only interested in the total path weight, so we can potentially make it simpler:

day15> (defn dijkstra [world end]
         (loop [points (sorted-set [0 [0 0]]) ; our priority queue
                visited #{}]
           (let [[total [x y] :as point] (first points)]
             (if (= [x y] end)
               total ; total is the weight up to this point
               (let [visited (conj visited [x y]) ; we only care about visited points,
                     points (reduce               ; but not their weights
                             (fn [paths [new-x new-y]]
                               (if-let [risk (and (not (visited [new-x new-y]))
                                                  (get-in world [new-x new-y]))]
                                 (conj paths [(+ total risk) [new-x new-y]])
                                 paths))
                             (disj points point)
                             [[(dec x) y] [(inc x) y]
                              [x (inc y)] [x (dec y)]])]
                 (recur points visited))))))
#'day15/dijkstra
day15> (dijkstra (read-input) [9 9])
40

Maybe not the best implementation, but it works! And it computes the correct value, so that’s good.

We use sorted-set as our priority queue, as its semantics match our needs perfectly. Elements are ordered, and getting first element returns the smallest one. We store points in the following format [weight [point-x point-y]], which can be easily sorted by the set implementation.

Plugging the real input also works out correctly, let’s see part two now.

Part two

Part two says that the cave is actually a lot bigger! But we need to compute the rest of the cave ourselves.

To do so, we need to take the current cave and repeat it five times to the right. Each repetition has each value increased by 1 and values greater than 9 overlap back starting from 1 again. For example, if we had a cave with a single [0 0] coordinate with a weight 8 after repeating the first column five times we would get this:

Now we need to repeat this row five times downwards to get the completed cave:

We need to write such function and feed it our current input, then find the same path from top left to bottom right. First, let’s write a function that does the correct addition, overlapping values as described:

day15> (defn add-to-field [field x]
         (let [add-to-row
               (fn [row]
                 (mapv #(let [x (+ % x)]
                          (if (> x 9)
                            (- x 9)
                            x))
                       row))]
           (mapv add-to-row field)))
#'day15/add-to-field
day15> (add-to-field [[4 5] [6 7]] 5)
[[9 1] [2 3]]

Next, we need to repeat the original world four times to the right, adding 1, 2, 3, 4 to the original one on each repetition. Then repeat this new world four times down, adding the same numbers:

day15> (defn extend-field [input]
         (let [new-world (reduce (fn [world n]
                                   (let [new-world (add-to-field input n)]
                                     (mapv #(into %1 %2) world new-world)))
                                 input (range 1 5))]
           (reduce (fn [world n]
                     (let [new-world (add-to-field new-world n)]
                       (into world new-world)))
                   new-world (range 1 5))))
#'day15/extend-field
day15> (extend-field [[8]])
[[8 9 1 2 3]
 [9 1 2 3 4]
 [1 2 3 4 5]
 [2 3 4 5 6]
 [3 4 5 6 7]]

Exactly as in the example. Now, we can plug the real input, and see if it works:

day15> (let [world (extend-field (read-input))
             end-x (dec (count (first world)))
             end-y (dec (count world))]
         (dijkstra world [end-x end-y]))
315

And indeed it does.

Day 15 thoughts

The first part was very interesting. I’m very new to this kind of stuff, and learning about Dijkstra’s algorithm surely was very useful. The second part was a bit too easy, as the only change was that we needed to compute the new field. But I suppose that perhaps someone tried to use some other path-finding algorithm, which was checking all possible paths, so similarly to the previous day, it would have choked on the increased field. Luckily for us, our implementation performed well.

Now I feel that we’re getting to the point, where the tasks may become way too difficult for me, so I’m not sure how long I’ll be able to continue solving both parts or even any. Last year I was exhausted on day 14, but mainly due to the fact that I’ve started late, and tried to keep up with everyone. We’ll see what will happen this year. But for now, see you tomorrow!

Comment via email