Modern C++ in Advent of Code: Day 7

It is the seventh day of Advent of Code, and we are analyzing the terminal output of our communication system device.

I encourage you to solve it yourself first https://adventofcode.com.

Input

Our input is the text from a terminal. Therefore our first goal is to make sense of this and parse it into a usable format.

The first observation is that the output from the $ ls command is something we want to store as information about a directory. The other part of the information we need is the $ cd somewhere commands that will tell us which of the $ ls outputs belong to what directories. So, finally, we need a data structure to store this information.

The Tree stores all the data, allowing us to use raw (unowning) pointers in the rest of the data structure. These pointers will be valid as long as the Tree instance that gave them out is alive.

As mentioned, the output of $ ls will be stored in Directory, we can therefore implement it using the stream extraction operator. Other than that, we will need an enclosing function that will return the parsed instance of Tree and traversal implementation for the $ cd command.

We rely on the std::istream::peek method to detect the end of $ ls output and end of the file and distinguish between directories and files in the $ ls output.

We read each command and act accordingly, skipping over directory information in the $ ls output as a directory is only relevant once we $ cd into it.

Summing up sizes of small directories

For part one, we are tasked to process the parsed information and sum up the sizes of small directories.

To facilitate that, we first need to add a way to calculate a directory's recursive size and to make repeated calls fast, and we will cache the calculated value.

Putting this together, all we need is a recursive sum that skips over the directories over the threshold.

Note that a std::reduce of an empty range is 0, therefore, the local sum is always correctly initialized.

The smallest directory that is large enough

In part two, we are tasked to identify (by size) the smallest directory over a given threshold.

We can use a similar approach to part one, except now we need to filter.

Note that we do not need to check whether our current directory is within the threshold, as this will be filtered one layer up.

Links

The repository with a complete solution (including input parsing) is available here: https://github.com/HappyCerberus/moderncpp-aoc-2022.

I post daily Modern C++ content on Twitter, LinkedIn, Mastodon, Medium and Substack.