## DEV Community

Christopher Kruse

Posted on • Originally published at ballpointcarrot.net on

# Advent of Code 2018 - Day 1

Originally posted at https://www.ballpointcarrot.net/posts/advent-of-code-2018-1/ - Also, obligatory "first post" points for being my first dev.to post :D

Spurred on by

1. a lack of posting in this space,
2. the chance to show off the new backend/theme to my blog (I did work on this while nobody was looking, and started building an RSS feeed!), and
3. after finding this Tweet by Ali Spittel,

I decided that doing this "Advent of Code" was something to do. First, it gives me a nice thing to practice on. Second, it gives me a reason to make some frequent posts on here (which, given the year+ lack of content, may not be a bad idea). Finally, it helps me build out some public code, which I've been bad at doing - even if they're solutions to set problems. I'll be using GitHub gists for posting my solutions, and embedding them here.

### Problem the First

The first problem is summarized as follows: you're an Elf travelling back in time to fix anomalies in history, in order to "save Christmas". However, in order to get the time travel device working correctly, it first needs calibrated.

Given a series of "frequency changes", like `+1 -2 +3 -1`, the following changes would occur:

• Current frequency `0`, change of `+1`; resulting frequency `1`.
• Current frequency `1`, change of `-2`; resulting frequency `-1`.
• Current frequency `-1`, change of `+3`; resulting frequency `2`.
• Current frequency `2`, change of `+1`; resulting frequency `3`.

This provies a resulting frequency of `3`.

With those rules in place, the Advent of Code site has you log in (thanks, Login with Github) and get a link for sample input. The input file was larger than I expected, but the rules simple enough to come up with this small Clojure snippet:

``````(defn calibrate [input-file]
(let [raw-input (slurp input-file)
freqs (map #(Integer. %) (clojure.string/split-lines raw-input))]
(reduce + freqs)))
``````

The above reads the file into a string (using `slurp`), then converts each individual number (separated with a newline character) into a Java Integer. Finally, everything is summed up via `reduce` to get the full set of adjustments for a final frequency.

### Problem the Second

Within your input, you now need to keep track of the active value, and look for the first time you encounter the same value twice. Additionally, this means that your list can loop; for example, take the input `+3, +3, +4, -2, -4`. As you run through this the first time, you generate intermediate values of `3, 6, 10, 8 4`, and there are no matches within that set. So, you take the last `4` offset, and start the original list over again, returning `7, 10, ...`. When you've reached `10` again, you have found your "twice match", and return that value. Now, using the same test input, we get to find the first value we hit twice.

Clojure gets to harness the power of lazy infinite sequences here. Using the clojure `cycle` function, the list of frequencies gets to be repeated indefinitely. Obviously, we can't eager load a list of infinite values - there's not
enough memory space to do that; what we can do, however, is let that list populate as needed, only providing the next
number until we need it.

I built a function that generates a list of the intermediate points, and loops to find a solution::

``````(defn frequency-adjustments [freqs]
(reductions + (cycle freqs)))

(defn calibrate [freqs]
(loop [n 2]
(let [steps (take n (frequency-adjustments freqs))
step-counts (frequencies (rest steps))
repeats (filter (fn [[k v]] (if (= v 2) k)) step-counts)]
(if-not (empty? repeats)
(first (keys repeats))
(recur (inc n))))))
``````

I was happy with how things looked. I went to a REPL and tested the logic with some of the samples, which seemed to get
the answer I was looking for. `frequency-adjustments` was nice, actually, because you could see effectively a new list
of how each step processes, which was great for visual analysis. I then fired it off with the test data.

And waited. Quite a while in fact.

Turns out that, when you have a high enough input, trying to build the list over and over again is somewhat taxing on
the system doing that calculation. Obviously, this wasn't the solution I was looking for. At this point, I did a little
bit of cheating (hey, it's the Internet, and I'm not proud) and checked the reddit post where people were posting solutions, and came across a separate Clojure
solution by zqvt (slightly
modified to fit my input parameters below):

``````(defn calibrate2 [freqs]
(loop [xs (cycle freqs) seen #{} total 0]
(if (contains? seen total)
total
(recur (rest xs) (conj seen total) (+ total (first xs))))));
``````

This generates a set of values we've come across, as well as keeps a running total of where we're at while we're
generating. The key here that I didn't even think about (let alone thought possible) was the use of `rest` to generate
further sequences while not including the items processed. That was clever, and this solution very quickly provided a
response.

Lessons learned:

1. My initial thought was to build a set of values that I'd seen going through the list calculated with `reductions`, but I really wanted to try something that I could do without maintaining state outside of the loop. That led me down the path of regenerating the list each time, which made it impossible to run effectively. I probably should've gone with that easier thought process, as it would've worked faster (and I would've spent less time on the solution).
2. Good to be posting stuff again, and practice always helps.
3. Honesty - it hurt to come clean about looking for solutions, but sometimes you have to suck it up. Also, I felt really dumb after seeing the painful performance of my implementation vs. the one that I found. But I wanted to highlight a successful implementation, both to show that there are good ways to do it, and to give myself something to look forward to improving upon. I'm hoping to not need the crutch next time.

take the input +3, +3, +4, -2, -4. As you run through this the first time, you generate intermediate values of 3, 6, 10, 8 4, and there are now matches within that set

I did not get this point. There is no any match within the set `3, 6, 10, 8, 4`, all numbers are different.

Can someone explain me what I missed ?

Christopher Kruse

Looks like an unfortunate typo - it should say "and there are no matches within that set." Because it doesn't match, you'll keep the offset, but repeat processing the list - the first two `+3` then change the offset to `7` and `10`, which finally gives you the second repeat.

Hope that helps!

Yep. Now it is clear.
I was confused with the problem statement and had exactly the same confusement as described here: reddit.com/r/adventofcode/comments....

Thanks.

rhymes

Thank you Christopher for the assist, I had almost got it

github.com/rhymes/aoc2018/commit/6...

Tomorrow I'll try to setup a proper Clojure environment on my computer

Ali Spittel

Erik Assum

`reductions` is a really cool function :)

Christopher Kruse

Nice! I liked how `reductions` gives you the intermediate steps, but my mind this AM was not going to give me a way to dig through it easily.

Thanks for the snippet - that's really cool and a good read (gonna be following that repo 😁)

Ryan Palo

Nice post! Hopefully this is the first of many! 😁

Christopher Kruse

Im gonna try to keep it frequent. 👍