Modern C++ in Advent of Code: Day 13

Day thirteen of Advent of Code got the parsing curse again as we are analyzing packets of data. I do encourage you to try to solve it yourself first https://adventofcode.com.

Input

Today’s input is a series of pairs of packets. Our first task is, therefore, to parse the input.

We will represent each input element as a Node, either a list or a value. On top of that, we will create a type for a Packet, which will provide storage and parsing of the nodes and refer to a root node representing the outermost list.

Out-of-order packets

For part one, our goal is to determine which packets are out of order. To do that, we need to implement the comparison operators for our tree-like data structure of nodes.

Since this is modern C++, we will implement the spaceship operator. The way our comparison needs to operate is very similar to std::lexicographical_compare_three_way, which, unfortunately, isn’t implemented in libc++ yet.

On top of needing to implement our range comparison, we have complications when we compare a value against a list. Simply put, the comparison needs to recurse until we compare a value against another value or an empty list.

Finding the decoding key

Fortunately, for part two, we have very little work.

We need to sort a std::vector<Packet> and determine the indexes of where our two divider packets would slot in.

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.