Advent of Code 2018 - Day 1

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:

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 offset of 4, 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.

/Programming/ /AoC2018/ /advent-of-code/