DEV Community

Christopher Kruse
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)))
Enter fullscreen mode Exit fullscreen mode

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))))))
Enter fullscreen mode Exit fullscreen mode

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))))));
Enter fullscreen mode Exit fullscreen mode

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.

Top comments (9)

Collapse
 
maksadbek profile image
maksadbek

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 ?

Collapse
 
ballpointcarrot profile image
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!

Collapse
 
maksadbek profile image
maksadbek

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.

Collapse
 
rhymes profile image
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

Collapse
 
aspittel profile image
Ali Spittel

🙌 this is awesome! Super excited to follow along and learn more clojure!

Collapse
 
slipset profile image
Erik Assum

Have a look at github.com/borkdude/advent-of-cljc...
reductions is a really cool function :)

Collapse
 
ballpointcarrot profile image
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 😁)

Collapse
 
rpalo profile image
Ryan Palo

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

Collapse
 
ballpointcarrot profile image
Christopher Kruse

Im gonna try to keep it frequent. 👍