Advent of Code 2018 - Day 1
Tags: clojure, challenges, adventofcode
Published: 2018-12-01 18:43:57

---
title: Advent of Code 2018 - Day 1
published: true
tags: ["clojure", "challenges","adventofcode"]
canonical_url: https://www.ballpointcarrot.net/posts/advent-of-code-2018-1/
series: "advent-of-code-2018"
---

*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](https://twitter.com/ASpittel/status/1068869815333527557?s=20) by [Ali Spittel](https://www.alispit.tel/#/),

I decided that doing this ["Advent of Code"](https://adventofcode.com/) 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.

<!-- more -->

### Problem the First

The [first problem](https://adventofcode.com/2018/day/1) 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:

```clojure
(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`](https://clojuredocs.org/clojure.core/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::

```clojure
(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](https://www.reddit.com/r/adventofcode/comments/a20646/2018_day_1_solutions/) where people were posting solutions, and came across a separate Clojure
solution by [zqvt](https://www.reddit.com/r/adventofcode/comments/a20646/2018_day_1_solutions/eau9gjm/) (slightly
modified to fit my input parameters below):

```clojure
(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.