Advent of Clojure — Day 1

This is part of my series on the Advent of Clojure.

Day 1 provides a story and an associated puzzle. I am including it here:

— — Day 1: Inverse Captcha — -

The night before Christmas, one of Santa’s Elves calls you in a panic. “The printer’s broken! We can’t print the Naughty or Nice List!” By the time you make it to sub-basement 17, there are only a few minutes until midnight. “We have a big problem,” she says; “there must be almost fiftybugs in this system, but nothing else can print The List. Stand in this square, quick! There’s no time to explain; if you can convince them to pay you in stars, you’ll be able to — “ She pulls a lever and the world goes blurry.

When your eyes can focus again, everything seems a lot more pixelated than before. She must have sent you inside the computer! You check the system clock: 25 milliseconds until midnight. With that much time, you should be able to collect all fifty stars by December 25th.

Collect stars by solving puzzles. Two puzzles will be made available on each day millisecond in the advent calendar; the second puzzle is unlocked when you complete the first. Each puzzle grants one star. Good luck!

You’re standing in a room with “digitization quarantine” written in LEDs along one wall. The only door is locked, but it includes a small interface. “Restricted Area — Strictly No Digitized Users Allowed.”

It goes on to explain that you may only leave by solving a captcha to prove you’re not a human. Apparently, you only get one millisecond to solve the captcha: too fast for a normal human, but it feels like hours to you.

The captcha requires you to review a sequence of digits (your puzzle input) and find the sum of all digits that match the next digit in the list. The list is circular, so the digit after the last digit is the first digit in the list.

For example:

1122 produces a sum of 3 (1 + 2) because the first digit (1) matches the second digit and the third digit (2) matches the fourth digit.

1111 produces 4 because each digit (all 1) matches the next.

1234 produces 0 because no digit matches the next.

91212129 produces 9 because the only digit that matches the next one is the last digit, 9.

What is the solution to your captcha?

It’s a cute story. Thank you Eric!

To approach this, we should look for the digits appearing in strings (as this will allow for unlimited length), and convert them into a sequence of digits. Clojure already treats strings as seqs of characters, so we’re most of the way there. The next step is to compare each character to the one after it.

While the map function is usually used to apply an operation to each element in a seq, it can also be used to perform an operation that takes elements from multiple seqs at once. In this case, we want to use the equality operation for each element of the sequence, with each element after it. So to do this, we can take the first element from the seq, move it to the back, and then compare this new seq to the original.

In more concrete terms, say we have a seq of:

12334556

Not that the digits “3” and “5” are repeated. If we take the first element of this and move it to the back, we get:

23345561

Then we can line this up with the original seq:

12334556
23345561

And compare each digit in the first seq with the one directly below it. In this case, we see that these are different for each column, except the 3rd and 6th elements.

To do this in Clojure, assume that the data string is in a var called data. We can drop the first element, and copy it to the back by making it a single element seq, which can be concat’ed. At the repl, this looks like:

=> (concat (drop 1 data) [(first data)])
(\2 \3 \3 \4 \5 \5 \6 \1)

Note: The REPL prompt is shown as => or #_=> and appears at the start of each line typed.

Dropping 1 element is the equivalent to using rest, but I feel that the drop function makes my intention clearer here.

Next, using map, we can create pairs between the elements of the original data and this modified one using vector:

=> (map vector data (concat (drop 1 data) [(first data)]))
([\1 \2] [\2 \3] [\3 \3] [\3 \4] [\4 \5] [\5 \5] [\5 \6] [\6 \1])

This is already getting messy, so let’s use a threading macro. We can take the results of the concat, and pass it along to be the final param for the map function. This will be particularly useful when we take these results to the next step:

  => (->> (concat (drop 1 data) [(first data)])
#_=>      (map vector data))
([\1 \2] [\2 \3] [\3 \3] [\3 \4] [\4 \5] [\5 \5] [\5 \6] [\6 \1])

The next step is to find just those elements where the first and second element are equal. The elements of a vector can be passed to the = operation as separate parameters using the apply operator. Then, using partial, a function can be created that is expecting a vector of values, and will apply the = operator on each of them. We then use filter to find these vectors with equal elements:

  => (->> (concat (drop 1 data) [(first data)])
#_=>      (map vector data)
#_=>      (filter (partial apply =)))
([\3 \3] [\5 \5])

At this point, we can just use the first element from each vector, since we know that it is equal to the second:

  => (->> (concat (drop 1 data) [(first data)])
#_=>      (map vector data)
#_=>      (filter (partial apply =))
#_=>      (map first))
(\3 \5)

These values are still characters, so we should change them into numbers. This can be done quickly by taking the difference between the ASCII value of each character and the ASCII value of 0 (which is 48). We can get an ASCII code, just by converting the character to an integer with int. So can map an anonymous function over the values, finding these differences:

  => (->> (concat (drop 1 data) [(first data)])
#_=>        (map vector data)
#_=>        (filter (partial apply =))
#_=>        (map first)
#_=>        (map #(- (int %) (int \0))))
(3 5)

The final step is to add every number in the final sequence. This can be done by using apply with +:

=> (->> (concat (drop 1 data) [(first data)])
#_=>        (map vector data)
#_=>        (filter (partial apply =))
#_=>        (map first)
#_=>        (map #(- (int %) (int \0)))
#_=>        (apply +))
8

This can be wrapped in a function called day1:

Running this over the example strings provided in the puzzle gives the expected responses, so let’s try it on the provided data. Clicking the link shows a string of digits over 2000 characters long, so this can be saved into the resources directory, and then loaded.

Resources can be found with resource in the clojure.java.io namespace. That file can be loaded with the slurp function, which brings the file in as a string. Unfortunately, there is a newline character at the end of the file, so we should use the trim function from the clojure.string namespace. From the REPL, these functions are made available with:

(require '[clojure.java.io :refer [resource]])
(require '[clojure.string :refer [trim]])
(let [data (-> (resource "day1.dat")
               slurp
               trim)]
  (day1 data))

For me, this returns the value 1171. If you get your own data, then you’ll have another result. Typing this number into the website opens up the second part of Day 1:

— — Part Two — -

You notice a progress bar that jumps to 50% completion. Apparently, the door isn’t yet satisfied, but it did emit a star as encouragement. The instructions change:

Now, instead of considering the next digit, it wants you to consider the digit halfway around the circular list. That is, if your list contains 10items, only include a digit in your sum if the digit 10/2 = 5 steps forward matches it. Fortunately, your list has an even number of elements.

For example:

1212 produces 6: the list contains 4 items, and all four digits match the digit 2 items ahead.

1221 produces 0, because every comparison is between a 1 and a 2.

123425 produces 4, because both 2s match each other, but no other digit has a match.

123123 produces 12.

12131415 produces 4.

What is the solution to your new captcha?

Following the technique from the first part, we can do exactly what we did last time, except shifting half of the data to the back, rather than just the first character.

Given that this code is illustrative, I felt that it was appropriate to rewrite the function, rather than try to re-use common code:

Line 2 counts the size of the data, and halves it. This is then the size of the data shifted from the front to the back of the data buffer on line 3. The rest of the function is identical.

My answer here was 1024, and I got my second star! Yay!

The full namespace described here can be found at:

quoll/AoC2017

Next comes Day 2…