Advent of Code 2020: Week 2 Summary

, 7 min read
advent of code 2020

The second week of Advent of Code has been great fun. You can find links to all my posts and solutions here. In this summary I will mainly focus on the advent of code problems, and briefly touch on my thoughts on C++ and the analytics of my blog.

AoC 2020: time to solution
AoC 2020- Time to solution [Advent of Code]

The figure above shows the time to solution for the 1st and 100th person on the Advent of Code leaderboard. There is a general trend which suggests the problems this week have generally gotten progressively harder, and are certainly more challenging than the average problem last week. I also felt the puzzles had been increasing in difficulty, but I wasn’t sure if this was due to my reduced time to work on them this week.

The puzzles this week started off with writing an emulator for a byte-code-like interpreter. This was great fun, and really approachable. I think part 2 of the puzzle struck a perfect balance between being solvable by brute force, but also giving clues that there may be more efficient techniques. I actually updated my blog the day after to showcase a reduced complexity, bread-first solution which was incredibly satisfying.

The second day tested our ability to implement loop logic. The data parsing was simple and was comparable to previous days which helped make this problem approachable. My conversations with other Advent of Coders yielded positive reviews all round. Both parts of the puzzle had a variety of optimisations which are satisfying to identify.

The third day almost wholly changed the puzzle focus. Both parts of the solution involved almost no code; personally, my answer was a handful of lines. However, the second part of the puzzle required either a lot of thought to identify an almost analytic solution. Or, an intelligent tree search with memoization.

Day 4 and 5 were both very procedural. By this, I mean that the puzzles laid out several clear instructions of how to read in the input and evolve until solution. Well, aren’t all puzzles like this? Not entirely, typically each puzzle can be solved in a variety of very different ways, these puzzles felt like there was only 1 solution. I found both of these puzzles slightly bland, however, I still very much enjoyed solving them. By bland, I mean that after solving them, I quickly forgot about them. In contrast, I usually spend several hours on-off thinking about alternative, more optimal solutions.

While day 4 and 5 may have been slightly too procedural for my taste, day 6 was a corker! Absolutely amazing. Part 1 was very tame, easy to solve and approachable. Part 2, on the other hand, wow! I personally found it to be a complicated problem, and for me, very unique. I saw that some people solved it using Chinese remainder theorem, however that is not a tool in my toolbox. After an hour of zero progress, I gave up and went for a run. I spent several hours thinking on my run and came up with a solution I was convinced would work. I got home, implemented the solution in 5 minutes, and under 10 lines, and it worked! This was an incredibly satisfying puzzle, which really stretched me. What did you think about it?

Day 7 was a further change of emphasis. Instead of modular maths, the focus was now on binary numbers and bit manipulation. I’ve been intending to work on my bit manipulation problem-solving. I’m generally able to solve these types of puzzles, but I never feel entirely comfortable. Thus, day 7 was an excellent day for experience and confidence. I really enjoyed both parts of the puzzle.

Language

This year I’ve been solving the Advent of Code puzzles using C++; in particular, I’m generally using C++14 features, and earlier. I decided to use C++ to re-familiarise myself with the syntax whilst also taking a bit of a dive into the standard library data containers and algorithms.

For most of the Advent of Code puzzles, it is not necessary to write functions, and when it is, only a few small functions are required. As a consequence of this my solutions are generally written in a very imperative style with most of the code being in the main function, which rarely exceed 50 lines. Thus, I haven’t taken advantage of a lot of the object-orientated features within C++. As such, the further comments that I give about the language should be considered with this in mind.

I’ll break down my current discussion into two brief sections: library features and ergonomics, and compile times.

Library features and ergonomics

I’ve used very few of the algorithmic features in the standard library. Still, I’ve used a plethora of data containers: maps, sets, vectors, arrays, pairs along with many of their unordered counterparts. I’m certainly beginning to feel more comfortable with the syntax, and C++ “house rules”. I typically write a lot of Python in my day job, and so it has a been an unnatural transition to iterator’s as the main container interface. However, after a few weeks I would say I quite like the iterator framework.

In my experience so far I’ve found that the vast majority of the containers and (limited) algorithms that I’ve used to have fairly simple, and more importantly, unified API’s. Thus, after learning a lot of the list methods I was able to intuitively guess the equivalent for a set.

With this said, I can see that some of the template types will get almost unreadably long in larger applications. Additionally, the error messages that the compiler yields, even for small trivial bugs, are genuinely horrific. I’ve regularly scrolled through 60+ lines of meaningless messages to discover I tried to use an operator which hasn’t been overloaded for the current type.

Compile times

As previously stated, the vast majority of my solutions are less than 100 lines. These are single, monolithic files with the following includes, iostream, fstream string, sstream, vector, map, unordered_map, set, list, algorithm, iterator, regex. These are small and simple programs which do not directly use templates (there are of course many templates in the headers). Let’s consider day 7, to build this from scratch with no optimisations outputs the following:

1
2
3
4
5
g++ -std=c++11 -O0 ... solution.cpp -o solution

real	0m2.740s
user	0m2.480s
sys	0m0.137s

and if I compile with aggressive optimisations,

1
2
3
4
5
g++ -std=c++11 -O3 solution.cpp -o solution_opt

real	0m4.206s
user	0m4.059s
sys	0m0.139s

So that is almost 3 seconds for a standard build and 4 seconds for an optimised build! I can slightly reduce the compile times by pre-compiling all of the includes into a “.gch” file. This pre-compilation reduces by standard build to 2 seconds. But, this is an 80 line program that uses a map and set! Why does the compilation take so long? I dread to think about the compile times of large production applications written in C++. Of course, incremental builds will reduce the cost, but this still seems unwieldy high to me.

Please let me know in the comments if there is something I’m doing wrong, or if I’ve just set my expectations too high!

Meta

Finally, I thought I’d share some of my analytics again. This week my viewers have decreased slightly, but I’m not too surprised as the number of participants in Advent of Code has also decreased. This week has also been a difficult week for me personally, with a lot less free time. As a result, a lot of my write-ups have been posted later in the day, and so that could also have contributed.

Unique visitors
Unique visitors

I’m still very happy with the viewers and will be continuing to post each day. See you all in the rest of December!

I have no affiliation with AoC. I’m just a fan of the programming puzzles. If you enjoy them too, please feel free to join in and support the creators

Comments

Back to all posts