Your (Recursive) Loop Needs Reducing

I've decided to spend a bit of time on the "Advent of Code" puzzles from 2018. This post is a report of what I learned solving the following puzzle:

2018, Day 1.

If you're new to the Advent of Code, well, you're in for a real treat! Go read up on it and come back. Anyway, I'd like to walk through my initial solution for parts 1 and 2 of this puzzle, then show a reworking of part 2 inspired by my perusal of the wonderful subreddit, absolutely full of amazing solutions.

Ok, for this puzzle you are given:

• a list of integers representing distances
• a starting location of 0 (imagine a 1-dimensional number line)

Part 1 requires you to calculate where you end up after 'apply'-ing the list of distances to your starting position. The solution is rather simple:

(defn lines->ints [input]
  (->> (string/split-lines input)
       (map #(Integer/parseInt %))))

(defn part1 [input]
  (->> (lines->ints input)
       (apply +)))

This code is pretty simple:

1. Split the raw input string into lines
2. Parse each as an integer
3. Apply the + operator to them all

The above code passes the provided examples and also gives the right answer for my input (each participant is provided a generated input file with the advent of code system expecting the correpsonding correct answers!):

(describe "2018 Day 1"
  (context "Part 1"
    (it "solves simple examples"
      (should= 3, (sut/part1 (convert-example "+1, +1, +1")))
      (should= 0, (sut/part1 (convert-example "+1, +1, -2")))
      (should= -6 (sut/part1 (convert-example "-1, -2, -3"))))

    (it "solves with real input"
      (should= 406 (sut/part1 real-input))))
  ...

Part 2 is more difficult (these puzzles ratchet up in difficult rather quickly). You must identify the first place on the number line visited twice, which actually requires that you cycle through the list of distances multiple times. A straightforward approach is to use a recursive loop:

(defn part2-loop [input]
  (let [original (lines->ints input)]
    (loop [at    0
           seen  #{}
           steps (cycle original)]
      (if (contains? seen at)
        at (recur (+ at (first steps))
                  (conj seen at)
                  (rest steps))))))

As is typical when I have to reach for loop-recur, I am always left wondering if there's a better, more 'functional' way. So, off to the "Solution Megathread"! Someone on that thread references a solution which makes use of a mysterious reductions function. Closer inspection of the code alse reveals a single usage of the reduced function.

I recently wrote about the reduce function so I immediately wanted to see these related functions worked.

Let's say you had the following distances: 3 -1 -2 3

If you start at 0, then these instructions would take you first to 3, then 2, then back to 0, and finally back to 3. So, the first location on the number line to be visited twice by applying the distances is 0. So, it's like you need to apply or reduce the distances up until a certain point (where you have to notice that you've already been) and then stop reducing.

Well, guess what, that's just what reductions and reduced allow you to do, and rather elegantly at that.

user=> (reductions + [3 -1 -2 3])
(3 2 0 3)

The second-to-last item in the returned list above is what we are after. The reductions functions returns a lazy-seq. We can feed its result to the reduce function, which requires some sort of reducing function:

user=> (as-> (reductions + [3 -1 -2 3]) $
             (reduce ??? #{0} $))

Normally we pass somethign like + to reduce, but we've already passed it to reductions. In this case the purpose of the reducing function is two-fold:

1. conj the results of reduce onto the provided set (#{0}) which contains our starting location (0)...
2. but only do that until we identify a location that's already in the set!

(defn until-seen-in [seen x]
  (if (contains? seen x)
    (reduced x)
    (conj seen x)))

See that call to (reduced x)? That's a special function that's meant to short-circuit a 'lazy' reduce operation with the provided value (x)!

Now that we have that function in place, part 2 is a snap!

(defn part2-reductions [input]
  (as-> (cycle (lines->ints input)) $
        (reductions + $)
        (reduce until-seen-in #{0} $)))

No more recursive loop! Clojure is amazing.

---

The saving grace of the loop-recur solution was that it allowed for easily discovering to what extent the input list had to be cycled. Here's some println output of a previous run of that recursive loop code:

Returned to 312 after cycling through 139324 input numbers, of which there were 1014

---

Full code listings:

• Production Code
• Test Code