Daily bit(e) of C++ | Advent of Code: Day 1
Daily bit(e) of C++ #334, Advent of Code 2023 using Modern C++: Day 1.
Welcome to day 1 of Advent of Code using Modern C++. Before you start reading, I highly encourage you to try to solve the two problems yourself: https://adventofcode.com/2023/day/1.
If you missed it, I have prepared a template repository for C++, with a development environment (through a devcontainer) with a bleeding edge version of the C++ toolchain: https://github.com/HappyCerberus/aoc-2023-cpp.
Our goal for today is to extract information from lines of text.
Part One
In part one, our goal is to extract the first and last decimal digit present in each line. These digits will then form a two-digit decimal number, which we want to accumulate (across all lines) to arrive at our result.
Our input is line-based, so our first task is to process the input by line. For that, we can use views::split. Importantly, we use views::split and not views::lazy_split since we want to maintain the bidirectional nature of our input.
Because we aim to return the sum of the results for each line, we can wrap the by-line view in a left fold, accumulating the results.
This leaves us with the final puzzle piece, extracting the first and last letters. We can again rely on views and truncate each line's forward and reversed views until we reach a digit, which we can then extract.
Part two
For part two, we now have to deal with multi-character representations of digits. We can re-use the outer fold and views::split; however, the way we extract digits has to change.
The proper way to implement this functionality would be to use a state machine/parser, which would minimize the number of comparisons. Which honestly, felt like a bit too much, so here is a very straightforward approach with cubic complexity (line_length*digit_length*digits).
The simplest approach is to consider each possible suffix of our line and check whether it begins with a digit. We can determine whether a string begins with a digit by using the find algorithm over the digits, using the starts_with method to determine a match.
Conclusion
How do you find today’s problems? Did you implement a proper state machine or parser for the second part?
Share your solutions and insights. Check out the repository with solutions and links to all articles: https://github.com/HappyCerberus/aoc-2023-cpp-solutions.