Modern C++ in Advent of Code: Day 3

On the third day of Advent of Code, we are taking on the role of TSA and checking the elves' rucksacks. With the power of C++ algorithms, we can at least make it efficient.

I recommend you try to solve the problems yourself: https://adventofcode.com.

Input

Our input is a series of strings, each encoding the content of a rucksack using lower- and upper-case letters. We will take this input as std::vector<std::string>.

Part1: the mixed up content

In this part, our goal is to find the one item category that has not been correctly partitioned into one of the two parts of each rucksack. This means we are looking for an item that is present in both halves of the rucksack. We can use standard algorithms to achieve this:

1. we need to sort both halves

2. we can use std::set_intersection to find the common items

Note that while there is always only one type of item incorrectly partitioned, there can be multiple copies of that item. Once we know which item is incorrectly partitioned, we can calculate the priority value.

Putting this together, we get the following solution:

Part2: missing badges

In part two, we need to determine a badge/category for each group of three elves. The badge/category is the only item they have in common in their rucksacks.

We can use the same algorithm as before, std::set_intersection to determine the common elements between the first two elves and then between the common elements and the final third elf.

We will be getting a chunk_view in C++23, so for now, we need to iterate over the elves in groups of three manually, accumulating the priority number as we go.

Putting this together, we get the following solution. Note that we take the input by-value, which is desirable if we would make a copy anyway. Importantly, if the caller doesn’t need the data after the call, this can still be a cheap move: auto result = badges(std::move(data));.

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.