AdventOfCode2024

Solver for Advent of Code 2024 puzzles. https://adventofcode.com/2024/

This is a single command line application for the puzzles written in C++23 with CMake.

Puzzle Input

This project does not contain the puzzle or example inputs as per the copyright notice of Advent of Code. In order to run the compiled application, the puzzle inputs have to be downloaded from the Advent of Code 2024 puzzle pages, and placed as text files into the AdventOfCode2024\data directory, e.g. AdventOfCode2024\data\historian_hysteria.txt, or AdventOfCode2024\data\example\historian_hysteria.txt for the unit tests. The application will output an error message with details if it cannot find an input file.

Tests

The solution contains a unit test project to help troubleshoot issues and prevent regressions in the solver class framework. These tests cover the solutions for provided examples and full data inputs. I did not find a definitive source for it, but the full data inputs seem to be user-specific, so adding my solutions as tests does not spoil the solutions.

Solutions

Day 1: Historian Hysteria

🔎 Puzzle: https://adventofcode.com/2024/day/1, ✅ Solver: HistorianHysteria.cpp

I'm using a std::multiset to collect and sort the values for both lists. This allows to use a single iteration of the left list and two iterations of the right list simultaneously to solve both parts. Nice application of iterators.

Day 2: Red-Nosed Reports

🔎 Puzzle: https://adventofcode.com/2024/day/2, ✅ Solver: RedNosedReports.cpp

Here, we have a few conditionals to determine on the fly which of the numbers would make the report safe if dropped. The amount of cases is actually quite manageable.

Day 3: Mull It Over

🔎 Puzzle: https://adventofcode.com/2024/day/3, ✅ Solver: MullItOver.cpp

A simple finite state machine crawling along the input character by character solves both parts nicely. The algorithm tracks whether mul instructions are enabled or not, but ignores this setting for part 1.

Day 4: Ceres Search

🔎 Puzzle: https://adventofcode.com/2024/day/4, ✅ Solver: CeresSearch.cpp

For this puzzle I added a class for points in two-dimensional space, so I can use these for simplifying directional computations. With that, the algorithm looks for all X and A for part 1 and 2, respectively, and tries to find the remaining characters, starting from that X or A.

Day 5: Print Queue

🔎 Puzzle: https://adventofcode.com/2024/day/5, ✅ Solver: PrintQueue.cpp

My implementation uses an ordering matrix (a two-dimensional boolean array) to track which page combinations are ordered, and then queries that matrix for each ordered combination of pages in a single line. The same matrix can then also be used for a custom sort function for part 2.

Day 7: Bridge Repair

🔎 Puzzle: https://adventofcode.com/2024/day/7, ✅ Solver: BridgeRepair.cpp

The algorithm recursively tries the different operators from left to right until all the calibration numbers have been used. Since the result from any of the operator cannot be less than its operands, any branch of the recursion that surpasses the test value can be aborted.

Day 8: Resonant Collinearity

🔎 Puzzle: https://adventofcode.com/2024/day/8, ✅ Solver: ResonantCollinearity.cpp

For any pair of antennas of the same frequency, the algorithm adds the difference of their positions to one of these positions and subtracts it from the other to find the antinodes. For part 2, this process is repeated for each of the two directions until the found antinodes leave the defined area. Counting duplicate antinodes is prevented by keeping track of their locations in a two-dimensional array covering the area.

Day 9: Disk Fragmenter

🔎 Puzzle: https://adventofcode.com/2024/day/9, ✅ Solver: DiskFragmenter.cpp

The input string is processed simultaneously from both ends to calculate the checksums of files or file blocks without actually moving them. The algorithm does not have to keep track of positions for specific files or file blocks. For part two, a list of empty spaces is maintained, but only up to the point where the front and back processing meets. An array of indices per possible file size, where each index tracks the first empty space that could hold a file of that size and advances as needed, is also kept to speed up the search in the list of empty spaces.

Day 10: Hoof It

🔎 Puzzle: https://adventofcode.com/2024/day/10, ✅ Solver: HoofIt.cpp

The algorithm starts at the trail ends (the 9's) and searches all options from there downwards until trail heads are reached. For each visited map location, it tracks unique reachable end points (for part 1) and number of possible paths to end points (for part 2). These values are accumulated, if during the search the same map location is encountered again.

Day 11: Plutonian Pebbles

🔎 Puzzle: https://adventofcode.com/2024/day/11, ✅ Solver: PlutonianPebbles.cpp

Since the order of the pebbles does not actually matter, we can simply blink from one line of pebbles to the next and count only cardinalities of each number in the current line.

Day 12: Garden Groups

🔎 Puzzle: https://adventofcode.com/2024/day/12, ✅ Solver: GardenGroups.cpp

The algorithm uses two stacks to flood-fill each garden region; one stack for all plots inside the region, and one stack to collect all other plots encountered during the flood-fill. Once a region has been traversed, it just pops the next plot from the latter stack. This gives us naturally the area of a region.

The perimeter of a region is the sum of neighbors for all plots encountered during the traversal, that are not in the same region, also counting neighbors outside the defined area. The number of sides of a region is equal to the number of corners of a region, which can also be counted per plot while doing the region traversal. A corner occurs for each pair of adjacent cardinal neighbors if they are either both outside of the current region, or if they are both inside the region and the diagonal neighbor in between them is not.

Adding up the products of area and perimeter, or area and corner count, per region gives us the solution.

Day 13: Claw Contraption

🔎 Puzzle: https://adventofcode.com/2024/day/13, ✅ Solver: ClawContraption.cpp

For each claw machine, we have to solve a simple linear equation system to get the number of required button pushes. Conveniently, for the given data, all of these systems have a unique solution. However, some solutions have to be excluded because the number of button pushes is not integer, or because the solutions are too high for part 1. The required integer tests are done by performing integer division, and comparing the dividend with the product of the integer quotient and the divisor.

Thanks

• Alexander Brouwer for getting the project set up with CMake.

License

Copyright (C) 2024 Stefan Müller

This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program. If not, see http://www.gnu.org/licenses/.