Advent of Code 2020: The final countdown

, 9 min read
advent of code 2020
____ / \ / / /\ | / \ * / / \ \ /~~~~~~~~~\ ( .",^.-".' ) '~~~~~~~~~' Advent of Code 2020

The Christmas lights are up, the mornings are dark, and every shop has miles of aisles filled with festive products. This can only mean one thing: it’s (almost) time for Advent of Code!

First of all, what is Advent of Code? Well, simply, it’s an advent calendar for programmers created by Eric Wastl. It’s a set of 25 puzzles released, one by one, each day in December until Christmas Day. For each puzzle, you get a personalised input, and if your code can produce the correct answers, you can earn two gold stars (⭐) each day. The puzzles are aimed at a variety of skill sets and skill levels. They can be solved in any programming language, and often without programming.

AOC 2017
2017 Advent Calendar filled with stars [Advent of Code]

There is such a large community of people who take part in Advent of Code, and many of them are active on the subreddit. This is a great resource to seek out advice and hints on any puzzles that you are completely stuck on.

. . . .

This year I’ve decided to blog every day; these posts will include my initial thoughts, the code I implemented and then my reflections. As my goal for Advent of Code is to become a better programmer, my reflections generally involve me asking myself some questions:

Was the algorithm I implemented optimal? If not, why and how could I improve it?

Regardless of the outcome of these questions, I then ask a final question:

Did I implement the algorithm in an efficient and readable way?

These questions are tough to answer on my own. However, throughout December lots of people post their solutions to each puzzle on the subreddit. I can then read through a range of diverse solutions and compare them to mine. This is a really fruitful exercise when approached with the correct mindset. Don’t beat yourself up if you didn’t find the best solution, or your implementation wasn’t as fast/efficient/readable as others, or even if you needed a clue. Instead, pick out what other people did well and add that technique to your “toolbox”. Then next time you see a similar puzzle or even a real-life problem, you will be better equipped to solve it.

I don’t have any formal qualifications in Computer Science. I’m a PhD research student in Computational Cosmology, with programming being my main hobby, and now a big part of my research. But, if you want to follow my journey anyway, then feel free to check back anytime and have a read of my thoughts. I hope to see you in December!


Preparation and history

I’ve been taking part in AoC every year since 2017 with varying discipline. In 2017 I completed all 25 puzzles, both part 1 and part 2, however, in 2018 and 2019, I only completed the first 10 puzzles (boooo).

In previous events, I’ve opted to use the high-level programming language python. Python has simple syntax, a dynamic type system and a whole host of utility libraries which contain useful data structures and algorithms. On a more personal note: Python is the primary scripting language used for data processing in astronomy; thus, I am very familiar with it.

This year, I’m mixing it up. I’m going back to my roots and attempting to solve the problems in C, well, C++. The primary motivation for this is to re-familiarise myself with C-like code, and also to get more comfortable with modern C++, namely, the STL (algorithms, containers, and iterators).

If you are familiar with C++, you should probably call it a day here, and I’ll hopefully see you again on the 1st of December. If not, then please feel free to read on. In the remainder of the post, I’ll explain a few data structures I’m expecting to use (from experience with previous years).

. . . .

In preparation, I’ve created some boilerplate material which will hopefully accelerate my puzzle solving. As most of the problems involve ingesting and cleaning data, I’ve got a few snippets which can process data in a couple of different ways. Though I’m not expecting to be able to just call generic helper functions, but more realistically paste in these snippets and adjust them to fit. I’ve also prepared a Makefile which produces both debug and optimised binaries. My solutions and extra material can be found on github!

My template solution for a given day starts with a bunch of includes. The first include I have is:

1
#include <iostream>

which allows easy output to the terminal. This is useful for basic debugging during puzzle solving.

Then next includes are

1
2
3
#include <fstream>
#include <string>
#include <sstream>

these includes contain utilities to open files as streams, read in data into string streams and then process the underlying strings. In previous puzzles, I’ve read in lines, independently, and then looped through delimited sections and processed the data.

Next, I have a whole bunch of standard data structures which are incredibly useful in puzzle solving (and competitive programming).

1
2
3
4
5
6
7
#include <vector>
#include <list>
#include <set>
#include <map>

#include <iterator>
#include <algorithm>

I’ll briefly describe some of the properties of some of these data structures and give examples of how I may use them. If you are familiar with the C++ STL, then this will all be trivial (and you should stop reading now!). These examples will not be complete, either; instead, this will be more of an introduction check to what already exists for people coming into C++ from different languages. I hope this section will serve as a reference when describing my solutions in the upcoming weeks.

» std::vector

The vector is very similar to a standard array which is present in most (all?) programming languages. This means they use contiguous storage locations for their elements; thus, elements can be accessed using offsets on regular pointers. However, unlike arrays, vectors have a whole host of functionality built into them that allows them to dynamically change size. There is also machinery to insert and remove elements which can sometimes be convenient. They can be used like so:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
std::vector<int> a;
a.reserve(10); //  Reserve space for 10 integers (not necessary)

a.push_back(7);
// a = [7]; a.size() == 1;

a.push_back(4);
// a = [7, 4]; a.size() == 2;

std::vector<int>::iterator it = a.begin();
a.insert(it, 9);
// a = [9, 7, 4]; a.size() == 3;

// we can then sort the vector
std::sort(a.begin(), a.end());
// a = [4, 7, 9]; a.size() == 3;

These were just basic operations to append values to the vector, we then inserted an element at the beginning and sorted based on value. We could also store generic types, T, in a vector and still perform all of these operations with slight modifications.

Finally, we loop through the vector and print the contents,

1
2
3
4
// Finally, let's print the vector
for(auto val : a)
	std::cout << val << ",";
std::cout << std::endl;

which outputs,

1
4, 7, 9,

as anticipated.

» std::list and std::set

The list is similar to the vector, in terms of use; however, the implementation differs as elements in a list are not necessarily contiguous. Thus, lists can support constant time, O(1), insertion and removal of elements as the whole list does not need to be copied each time. However, this insertion and removal speed comes at the price of slower random access.

Lists are handy when you need to store a collection of elements which is frequently changing, either by insertion and removal. The syntax for using lists is mostly similar to vectors. Some example usage is shown below.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
std::list<int> b;
b.push_back(7);
// b = [7]; b.size() == 1;

b.push_front(4);
b.push_front(4);
b.push_front(11);
b.push_front(9);
// b = [9, 11, 4, 4, 7]; b.size() == 5

// we can then sort the list
b.sort();
// b = [4, 4, 7, 9, 11]; b.size() == 5;

A set is similar to a list, but it only stores unique elements. By default, it will store elements in sorted order. This makes insertion and deletion slower, but keeping unique elements is often a useful tool when puzzle solving. Some example code is below.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
std::set<int> c;
c.insert(7);
// c = [7]; c.size() == 1;

c.insert(4);
c.insert(4); // This is ignored, as we already have a 4
c.insert(11);
c.insert(9);
// c = [4, 7, 9, 11]; c.size() == 4;

» std::map

Finally, the map is the final container in my toolbox, which I wanted to briefly introduce. Maps are associative containers that store keys and elements, where the key is unique and maps to a specific value. In practice, these are similar to dictionaries (if you are from a python background). Some example use cases for maps are below. In this example, I map a pair of integers to a character. This can be useful when storing a sparse dataset in memory.

1
2
3
4
5
6
7
8
9
std::map<std::pair<int, int>, char> d;
// Insert 'x' with the key {1, 1}
d[{1, 1,}] = 'x';
// Insert 'y' with the key {1, 1}
d[{1, 3,}] = 'y';

// Loop through the map, print the keys and values
for(auto &kv : d)
	std::cout << kv.first.first << "," << kv.first.second   << " : " << kv.second << std::endl;

which outputs,

1
2
1,1 : x
1,3 : y

The above examples are not a complete introduction to the C++ STL. But, I hope that if you are new to C++, then you have some appreciation of what is in the STL, how you might use them. If you want to learn more about these data structures, or beyond them, I recommend this website as a reference.

If you spot any errors, have any questions or want to give feedback, then please reach out to me on email, Twitter Github or leave a comment. It’s always great to hear from people!


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 (if you can)

Comments

Back to all posts