Day 1: Secret Entrance

Aaaand we’re back!

It looks like this year we have 12 days to help Elves decorate the North Pole.

Some quick links before we start:

So, let’s dive in!

For today’s task, we’re standing next to a safe dial and we’re given a document containing a sequence of rotations which looks like this:

(def example "L68
L30
R48
L5
R60
L55
L1
L99
R14
L82")

…and we need to rotate the safe dial according to these instructions.

Input parsing

Each line of the input consists of a direction (either L or R) and a number of turns we need to take in that direction.
Since L means lowering the number on the safe dial, we’ll multiply the number of turns with -1.

One option would be to destructure each line into [direction & digits], but then we would have to do (apply str digits) to concatenate them back.
My approach is for digits we take a substring from index 1 onwards with the subs function, and then convert the resulting string of digits to a number with the parse-long function.

(defn parse-line [^String line]
  (* (if (= \L (.charAt line 0)) -1 1)
     (parse-long (subs line 1))))

Let’s see if it works as expected:

(parse-line "L234")
-234

Now we need to do that for every line of the input. This is what the parse-lines function from my aoc-utils library does: it takes a multi-line input, splits it into lines and maps a given function to each line:

(defn parse-data [input]
  (aoc/parse-lines input parse-line))

We can now parse both the example and our real input:

(def example-data (parse-data example))
(def data (parse-data (aoc/read-input 1)))

This is how the parsed data for the example looks like:

example-data
[-68 -30 48 -5 60 -55 -1 -99 14 -82]

The dial has 100 numbers on it, from 0 to 99, and it starts at number 50. Let’s define those so we don’t repeat ourselves later on:

(def ^:const size 100)
(def ^:const start 50)

Part 1

In Part 1 we need to count how many times the dial stops at the value zero after a rotation.

If we wanted to know what is the final value on the dial, we would use the reduce function, but here we want to know the values after each rotation. We can do that with the reductions function. This function, unlike reduce which produces just the final value, keeps all immediate values. Just what we need here.

(defn part-1 [data]
  (->> data
       (reductions (fn [position n]
                     (mod (+ position n) size)) ; [1]
                   start)
       (aoc/count-if zero?)))                   ; [2]

We need to stay in the 0-99 range of the dial, so we use mod [1].
The only thing remaining is to count how many times we’ve seen zero. I’m dogfeeding by using the aoc/count-if function [2], but the same can be achieved by using filter and then count.

(part-1 example-data)
3
(part-1 data)
1168

Woohoo! Our first star this year!

Part 2

We’ve realized we had made a wrong assumption (oh boy, this hits too close to home). We need to count every time we reach zero, either at the end of the rotation or during the rotation process.

Initial solution

We could do this by making one by one step of each rotation and checking if we’ve hit zero. This is doable since all numbers in the input are smaller than 1000, but I haven’t realized that when I was solving it so I opted for a “smarter” solution. Which turned out to be not-so-smart when I’ve hit several edge cases which produced a wrong result.

(defn part-2 [data]
  (-> (reduce (fn [[zeros start] n]
                (let [end (+ start n)]
                  [(+ zeros
                      (abs (mod end size))  ; [1]
                      (if (and (pos? start)
                               (<= end 0))
                        1 0))               ; [2]
                   (mod end size)]))        ; [3]
              [0 start]
              data)
      first))                               ; [4]

If the result of a turn (in absolute value) is higher than 100, e.g. -765, it means that we crossed zero at least 7 times [1].
The condition [2] covers cases where we start from a positive starting position ((>= start 1)) and we either stop at or pass through zero ((<= end 0)). If we started from a zero, we don’t cross it (and we counted it already on a previous turn).
Our end position on the dial is always positive [3].

Once we finish rotating the dial, we’re only interested in the number of times we’ve seen zero [4].

(part-2 example-data)
433
(part-2 data)
180980

Congrats! Day 1 solved!

Step-by-step solution

This is a simpler solution with a smaller possibility of hitting some edge case, but I initially opted for the solution written above. (And had 4 wrong answers in the process. But don’t tell anybody.)

First, we’ll convert the data we have (a list of rotations) into a list of step-by-step movements.
Here the mapcat function comes handy: we create a flat list, instead of a nested one.

(defn steps [data]
  (mapcat (fn [n]
            (repeat (abs n) (if (pos? n) 1 -1)))
          data))

This is how the converted data looks like:

(steps [-3 2 -1 4])
(-1 -1 -1 1 1 -1 1 1 1 1)

Now, with the step-by-step movements, we can use our solution for Part 1 to solve Part 2:

(defn part-2-simpler [data]
  (part-1 (steps data)))
(part-2-simpler example-data)
6
(part-2-simpler data)
7199

Both parts at once

We can use the idea from the initial part-2 function to solve both parts at once.
We will switch from reduce to loop to gain even more performance:

(defn both-parts [data]
  (let [n (count data)]
    (loop [i 0
           start start
           pt-1 0
           pt-2 0]
      (if (= i n)
        [pt-1 pt-2]
        (let [end  (+ start (long (data i)))
              end' (long (mod end size))]
          (recur (inc i)
                 end'
                 (if (zero? end') (inc pt-1) pt-1)
                 (+ pt-2
                    (long (abs (quot end size)))
                    (if (and (pos? start) (<= end 0)) 1 0))))))))
(both-parts example-data)
[3 6]
(both-parts data)
[1168 7199]

Performance comparison

Ok, the initial solution is more complicated. Is it at least faster than the simple solution?

To produce meaningful results, we’ll use the criterium library.

(require '[criterium.core :as c])

(c/quick-bench (part-2 data))
Evaluation count : 7068 in 6 samples of 1178 calls.
             Execution time mean : 138.072921 µs
    Execution time std-deviation : 64.983686 µs
   Execution time lower quantile : 85.491251 µs ( 2.5%)
   Execution time upper quantile : 221.668623 µs (97.5%)
                   Overhead used : 1.831777 ns)
(c/quick-bench (part-2-simpler data))
Evaluation count : 12 in 6 samples of 2 calls.
             Execution time mean : 71.898534 ms
    Execution time std-deviation : 5.535438 ms
   Execution time lower quantile : 67.693688 ms ( 2.5%)
   Execution time upper quantile : 80.372340 ms (97.5%)
                   Overhead used : 1.834727 ns)

Even though all turns are small (smaller than 1000), there is ~500x performance difference between two solutions. To be honest, I didn’t expect such a large difference.

How about the solution which solves both parts at once?

(c/quick-bench (both-parts data))
Evaluation count : 9324 in 6 samples of 1554 calls.
             Execution time mean : 63.457092 µs
    Execution time std-deviation : 559.584067 ns
   Execution time lower quantile : 62.977015 µs ( 2.5%)
   Execution time upper quantile : 64.067157 µs (97.5%)
                   Overhead used : 1.831777 ns)

Another 2x speed gain, making it three orders of magnitude faster than the simple solution from above (which only solves Part 2). Nice gains!

Conclusion

This was much harder than expected for Day 1, and I’m including there the input too, which was not just numbers (so it would’ve been easier to parse for beginners).
The advice for myself would be not to try to come up with clever solutions at 6 a.m., especially for these early days. But at least we’ve got some nice performance boost out of it.

Today’s highlights:

  • subs: take a substring
  • reductions: keep immediate values of a reduction
  • mapcat: flatten what would be a nested list
source: clojure/src/day01.clj