Every year I look forward to the Advent of Code challenges. These are 25 daily challenges which can be solved in any programming language. After you've completed a puzzle, you'll be presented with a variation on that same puzzle which often can be solved using the exact same code as before, but if not, it shows you where you've missed some important refactoring or simply created an inflexible design.

Most of the challenges can be solved in just a few lines of purely functional code, but unfortunately some of these solutions will run for hours and hours without producing a result. See Zach Tellmans notes for more details.

Day 10

This challenge is an ascii version of Deaths Stranding, ie. a Walking Simulator. Given a topographic/height map, you navigate from the lowest point to the highest without taking trails that are too steep. The map could look like this:

0123

1234

8765

9876

Trails always start at 0 and end on a 9 and you can't take a step which raises the elevation (the value you're standing on), by more than 1. There are 2 common ways to load a map like this. Either as a map where the keys are coordinates and the values are the height-values, ie {[1 0] 1} or as a vector of vectors where the outer vector is a row and the inner is the column values, ie

  [[0 1 2 3]
   [1 2 3 4]
   [8 7 6 5]
   [9 8 7 6]]

For this challenge I like the double vector solution, because you can simply print it to your repl to visualize the path you're taking.

Firstly, lets find our entry-points. We do this by simply walking the grid and noting when the value is zero. Note that in Clojure's list comprehension macro 'for' you can put the 'when' clause into your bindings to skip any nil values.

  (defn find-trailheads
     [ m ]
     (for [y (range (u/height m))
           x (range (u/width m))
           :when (zero? (get-in m [y x]))]
       [x y]))

Next, we simply want to because to walk from one of these trail heads to the number 9. We can break this down even further by making a function which just takes a single step in the direction of the 9.

If we repeat this process a number of times, we'll end up on a 9 - And what's more: If we have several paths to take, we simply call ourselves on every single path using map(cat):

    (defn walk
      " Given a position this walks as far as possible
        in every direction "
      ([ m position ]
       (walk m position #{}))
      ([ m position past ]
       (let [routes (remove past (routes-from m position))]
         (if (= 9 (get-cell m position))
           [ position ]
           (mapcat #(walk m % (conj past position)) routes)))))

Disregard the first arity (the 2 arg version, thats just convenience). The meat of this function reads like this

• Which options do I have now? Remove any I've seen before
• Have I reached a 9, then return the position, meaning 'this 9 is reachable from the position I started with'
• If I'm not yet at a nine but I have options, walk from each possible position and remember where I came from

This is one of those neat recursive, purely functional, solutions that you hope and pray finds its result quickly.

To make this work, we essentially just have to write a function which finds all possible options from the position you're standing on. Given the rules, this is just a matter of finding adjacent values which equal one increment of my current value:

    (defn routes-from
      " Returns all possible moves from current
        position "
      [ m [ x y ] ]
      (let [current-elevation (get-cell m [x y])]
        (for [[nx ny] (mapv #(mapv + % [ x y ]) directions)
              :when (= (inc current-elevation)
                       (get-cell m [nx ny]))]
          [nx ny])))

If directions is just a vector of coordinate bumps, ie [[-1 0] [1 0] [1 1] [1 -1]] then mapv with 2 arguments does vector addition and gives us the adjacent coordinates. Then like before we test if it matches our requirements and only if so, return those coordinates.

A beautiful thing about Clojure is that we don't have to consider any edge-cases. If there are no options, this function returns nil or an empty list. If either of those are returned to our (mapcat #(walk ...)) then that also returns nil, ie. no path. But as long as we have non-9 options, we keep walking.

You might be surprised to learn, that that's it. That's all we need to walk a map of any size and find the trails.

Conclusions

This solution is fairly simple. Some developers take issue with recursion others revere it, I'm in the latter category. In terms of reasoning about this solution, it couldn't be simpler and you'll be happy to know that it produces the correct result for the large map (you get this at the bottom of the AOC page once you've logged in), in just

  Part I : 19 milliseconds
  Part II: 13 milliseconds

I didn't time it, but I arrived at an optimal solution for this challenge in about 10 minutes. Optimal because it gets the job done in sub-second time, it's easy to reason about, it has zero state and very low risk of bugs and saved time on:

• Manual memory management (C / C++)
• Having to force everything in to classes (Java / C#)
• Decide on and maintain static types (Rust)
• Explicitly handle edge cases (empty lists, etc)

Though there definitely is a case to be made for all of these languages, I think more and more often you'll get the job done better and faster in an opinionated high-level language like Clojure. The downside of a high-level language is that sometimes, you'll create something similar to the code above, but it'll be horribly inefficient but I would impressed if someone making a genuine attempt at this task, could write a slow solution in C.

Both languages require a bit of experience to use optimally, but where Clojure fails to the side of slowness other languages fail to the side of correctness. Choose your poison wisely and have a merry christmas :)