Advent of Code, Day 1

A couple of friends and I decided to start doing the Advent of Code, discussing solutions on our mailing list. Basically, every day in the advent (the first 25 days of December), there's a new two-part puzzle as part of an ongoing story. It's been going on for a while, but this is the first year I'm trying it out.

The repo for this is on Github; as part of each day I'm going to try to write up the solutions. The posts here will basically be verbatim copies from the solution.txt for each day.

I decided to start trying to do these in C++: although I'm a little rusty at it, I know it fairly well. That being said, I'm not guaranteeing all solutions will be in C++ and I'm also trying to go back and do Rust (and optionally Haskell) versions later.

For the first problem, I took the approach of treating this as a streaming problem. Given a stream, just keep a running tally of the deltas, and that's your frequency. My interface takes a base frequency because I wasn't sure it was always going to start from 0. Turns out it does, but no harm there.

I approached it this way because I was concerned about performance --- though it was premature. In the streaming approach, I really only need to track two ints: one is the current delta being read off the stream, and one is the adjusted frequency. All well and good, and I also turned the examples into a self-check system that runs on startup.

The second one threw me for a loop a bit. At that point, I wrote a duplicate detector, and read the entire list of deltas off the stream into a vector, using a standard set<int> to track the frequencies I've seen. This could get a little inefficient, and if I ran into performance problems I could do something like a bitfield or a bloom filter.

Then I got to the end and instead of creating a new program, I just run both parts at the same time. This won't work with an input stream, so I had to read the list of deltas at the beginning of the program, refactor my running tally to work off a vector (I basically created _vec versions of both functions), and then passed that vector to both functions.


Tags: