It’s that time of the year again! After finishing up 2017 and 2021’s Advent of Code this year, I had to make sure that I didn’t lag behind by not completing this year’s. Since I’m doing C_++ as my full day job, I decided to tackle the full project as C++. I knew I wouldn’t be as fast as I would in Python, but I had a few goals:
- Reinforce my C++17 knowledge. I last did an Advent of Code in C++ in 2017, when my knowledge of C++17 was still rudimentary.
- Try to work on more readable C++ (no, that’s not an oxymoron)
- Work on C++ 20/23 features such as ranges, modules, print/fmt, spaceship, generators, and more
- Everything from scratch, with only the standard lib.
Well, as I worked on it, how did I do?
- Advent of Code does not need a ton of advanced language features, but I did use optional, variant, and string view quite liberally.
- I think my C++ became a bit more idiomatic, so I consider this a win
- I was excited to use print/fmt and generators, but guess what. My compiler didn’t support them. Also, no importing std module, and I did not write enough common code for my own modules or concepts. I played around a little bit to learn, but I need to do more. However, spaceship operator was awesome, I used spans on almost every problem, and ranges were definitely nice for collection pipeline. I need to do more with ranges though as I found out about some nice views half-way through that would make things way easier.
With that said, let’s look at the challenges. I have my thoughts about each problem listed below, as well as how hard I thought they were, and my personal rating out of 5. You can find the repository at https://github.com/pviafore/AdventOfCode2022.
Day 1
Type of Problem: Iteration
Difficulty: Easy
Rating: 4/5
This felt real easy for a day 1. I want a chunk_by for C++ to make this even easier( Spoiler, I didn’t know about it, but it does exist: https://en.cppreference.com/w/cpp/ranges/chunk_by_view). You had to sum up values delineated by blank lines, and then just sort and sum. However, I just wrote a custom streaming in operation to read in an elf as a class, then sort and print out the sum of the first X elves.
friend std::istream& operator>>(std::istream& stream, Elf& elf) {
while(stream.good()) {
std::string calorieCount;
std::getline(stream, calorieCount);
if (calorieCount.empty()) {
break; // hit a space
}
elf.totalCalories += std::stoi(calorieCount);
}
return stream;
}
Day 2
Type of Problem: Game Simulation
Difficulty: Easy
Rating: 5/5
For an early problem, I liked this one. We were simulating rock-paper-scissors, and the first half was just emulating a simple translation of a game. Then for part 2, you had to infer what the best move was to get a certain outcome.
When writing C++, I wanted to try to get my code to “just work” if I compile, so I had static-analysis (which I had to eventually turn off for parsing errors with C++20 features), eventually turned on sanitizers, and anything else I could do. I also like writing static types to use to make things more readable
enum class Move {
Rock,
Paper,
Scissors
};
enum class Outcome {
Loss,
Draw,
Win
};
const std::unordered_map<char, Move> moveMapping = {
{'A', Move::Rock},
{'B', Move::Paper},
{'C', Move::Scissors},
{'X', Move::Rock},
{'Y', Move::Paper},
{'Z', Move::Scissors}
};
const std::unordered_map<Move, unsigned int> scoreMapping = {
{Move::Rock, 1U},
{Move::Paper, 2U},
{Move::Scissors, 3U}
};
const std::unordered_map<Outcome, unsigned int> outcomeMapping = {
{Outcome::Loss, 0U},
{Outcome::Draw, 3U},
{Outcome::Win, 6U}
};
Day 3
Type of Problem: Iteration / Set Operation
Difficulty: Easy
Rating: 3/5
This was quick, but uneventful in my eyes. Given a bag, we have to find what element is in the wrong section. Std::find_first_of makes it really easy, and it’s easy to pass in iterators (such as beginning and midpoint) to find the first element that’s in both halves of a string. The second part was to just find a common element in a group of 3, where set operations make it trivial.
unsigned int getPriority() const {
std::set<char> firstMatch;
std::ranges::set_intersection(bag1, bag2, std::inserter(firstMatch, firstMatch.begin()));
assert(!firstMatch.empty());
std::set<char> commonLetter;
std::ranges::set_intersection(firstMatch, bag3, std::inserter(commonLetter, commonLetter.begin()));
assert(commonLetter.size() == 1);
return ::getPriority(*commonLetter.begin());
}
Day 4
Type of Problem: Iteration
Difficulty: Easy
Rating: 3/5
Another meh level, but it’s a good opener for the first week. At first glance, it might be easy to just figure out the overlaps with set operations, but you can figure it all out numerically.
bool doesOnePairContainOther() const {
auto [firstElf,secondElf] = ((elf1.first < elf2.first) || (elf1.first == elf2.first && elf1.second > elf2.second)) ? std::pair{elf1, elf2} : std::pair{elf2, elf1};
return secondElf.first >= firstElf.first && secondElf.second <= firstElf.second;
}
bool doesOverlap() const {
auto [firstElf,secondElf] = ((elf1.first < elf2.first) || (elf1.first == elf2.first && elf1.second > elf2.second)) ? std::pair{elf1, elf2} : std::pair{elf2, elf1};
return firstElf.second >= secondElf.first;
}
Day 5
Type of Problem: Iteration
Difficulty: Medium
Rating: 5/5
This involved a quite interesting puzzle input, as it was a graphical representation of a stack of boxes. Honestly, parsing it was the toughest, but if you just read the blocks from bottom to top, you can use the indices of the stack number to know what to parse. From there, the actual algorithms aren’t too bad (either popping up a stack, or grabbing an entire iterator range at a time
Stacks applyMoves(const Moves& moves, Stacks stacks) {
for(const auto& move: moves){
for(unsigned int counter = 0; counter < move.amount; ++counter){
stacks[move.to].push_back(stacks[move.from].back());
stacks[move.from].pop_back();
}
}
return stacks;
}
Stacks apply9001StyleMoves(const Moves& moves, Stacks stacks) {
for(const auto& move: moves){
auto& toStack = stacks[move.to];
auto& from = stacks[move.from];
toStack.insert(toStack.end(), from.end() - move.amount, from.end());
from.erase(from.end() - move.amount, from.end());
}
return stacks;
}
Day 6
Type of Problem: Iteration / Set Operation
Difficulty: Easy
Rating: 3/5
So far all of these have been pretty easy. This one is looking for a non-unique window in a string of letters of different sizes. Not much to say past that, it was a quick program
bool isUnique(const std::deque<char>& str){
const std::set<char> set{ str.begin(), str.end()};
return str.size() == set.size();
}
std::string::size_type getStartOfPacketPosition(std::string_view str, std::string::size_type num){
std::deque<char> candidate{str.begin(), str.begin()+num};
if (isUnique(candidate)){
return 0;
}
const auto* charIter = str.begin() + num;
for(; charIter != str.end() && !isUnique(candidate); ++charIter) { // NOLINT(cppcoreguidelines-pro-bounds-pointer-arithmetic)
candidate.pop_front();
candidate.push_back(*charIter);
}
return std::distance(str.begin(), charIter);
}
Day 7
Type of Problem: Recursion
Difficulty: Medium
Rating: 5/5
I think this was the first difficulty people would have trouble with. It deals with funky parsing, and with recursion. Based on all the commands, I constructed a file tree using a composite pattern, and then just recursively checked through it.
Here are my commands to go through my file tree recursively
size_t getSmallFileSum() const {
auto mySize = getSize();
auto current = (mySize < 100'000) ? mySize : 0U;
return current + std::accumulate(leaves.begin(), leaves.end(), static_cast<size_t>(0), [](size_t sum, const auto& keyvalue){
auto [_, leaf] = keyvalue;
return sum + std::visit(overloaded { // NOLINT(clang-diagnostic-error)
[](const FileTree& fileTree) { return fileTree.getSmallFileSum(); },
[](size_t ) { return static_cast<size_t>(0);}
}, leaf);
});
}
size_t findSmallestDirectorySizeToDelete(size_t target) const {
auto mySize = this->getSize();
if(mySize == 0) {
return UINT64_MAX;
}
std::vector<size_t> sizes;
std::transform(leaves.begin(), leaves.end(), std::back_inserter(sizes), [target](const auto& keyvalue){
auto [_, leaf] = keyvalue;
return std::visit(overloaded { // NOLINT(clang-diagnostic-error)
[target](const FileTree& fileTree) { return fileTree.findSmallestDirectorySizeToDelete(target); },
[](size_t ) { return static_cast<size_t>(UINT64_MAX);}
}, leaf);
});
return std::min(*std::min_element(sizes.begin(), sizes.end()), (mySize > target) ? mySize : UINT64_MAX);
}
Day 8
Type of Problem: Grid manipulation
Difficulty: Medium
Rating: 4/5
Given a grid of heights, we had to find out how many trees we can see from the outside, and then see which tree could see the most other trees. It probably would have been find to iterate through every part of the grid, but I wanted to see if I could (pre-)optimize (Shame on me).
I wanted to see if I could figure out my answers with trees only looking at their neighbors. For seeing trees, I could do two passes through the grid, one from the top-left and one from the bottom-right. The top-left would track which trees were visible from top and left, and bottom-right pass will take care of its respective directions. Each tree on the edge is marked as visible, and then for each tree, I just check if the neighbor is visible and if I’m taller. This is actually slower because I check every tree, but the pattern works well for the second part.
For the second part, I still do two passes, but keep a map of (Direction, Coord) to tallest tree. Then for any tree, I look for the tallest tree it’s neighbor can see. If my current tree is larger than that tree, I look at that tree’s tallest tree it can see. And I keep looping until I get to an edge or I am blocked. This gives me a really easy count of how many trees I can see.
unsigned int getScoreForMostScenicTree(auto& grid){
std::map<std::pair<Direction, Grid::Coord>, Grid::Coord> lineOfSightPerTree;
auto getFurthestTree = [&grid, &lineOfSightPerTree](std::byte tree, Direction direction, Grid::Coord pos){
while(tree > grid[pos] && pos != lineOfSightPerTree[{direction, pos}]){
pos = lineOfSightPerTree[{direction, pos}];
}
return pos;
};
for( const auto& [coord, tree]: grid){
auto [xPos, yPos] = coord;
// mark yourself as the furthers that you can see
if (yPos == 0) {
lineOfSightPerTree[{Direction::Top, coord}] = coord;
continue;
}
if (xPos == 0) {
lineOfSightPerTree[{Direction::Left, coord}] = coord;
continue;
}
lineOfSightPerTree[{Direction::Left, coord}] = getFurthestTree(tree, Direction::Left, {xPos - 1, yPos});
lineOfSightPerTree[{Direction::Top, coord}] = getFurthestTree(tree, Direction::Top, {xPos , yPos - 1});
}
for( const auto& [coord, tree]: std::ranges::reverse_view(grid)){
auto [xPos, yPos] = coord;
// mark yourself as the furthers that you can see
if (yPos == grid.getMaxY()) {
lineOfSightPerTree[{Direction::Bottom, coord}] = coord;
continue;
}
if (xPos == grid.getMaxX()) {
lineOfSightPerTree[{Direction::Right, coord}] = coord;
continue;
}
lineOfSightPerTree[{Direction::Right, coord}] = getFurthestTree(tree, Direction::Right, {xPos + 1, yPos});
lineOfSightPerTree[{Direction::Bottom, coord}] = getFurthestTree(tree, Direction::Bottom, {xPos , yPos + 1});
}
auto getScenicScore = [&lineOfSightPerTree](const auto& coordTreePair){
auto [coord, tree] = coordTreePair;
return Grid::getManhattanDistance(coord, lineOfSightPerTree[{Direction::Top, coord}]) *
Grid::getManhattanDistance(coord, lineOfSightPerTree[{Direction::Bottom, coord}]) *
Grid::getManhattanDistance(coord, lineOfSightPerTree[{Direction::Right, coord}]) *
Grid::getManhattanDistance(coord, lineOfSightPerTree[{Direction::Left, coord}]);
};
auto scores = grid | std::views::transform(getScenicScore);
return *std::ranges::max_element(scores);
}
Day 9
Type of Problem: Grid Manipulation
Difficulty: Medium
Rating: 5/5
There are a lot of grid manipulation problems this year, so I’m glad I had extracted a grid class to handle a lot of the nitty-gritty of grids (nitty-griddy?) Coordinates, directions, parsing, and manhattan distances were all resused across a lot of problems.
For this problem, we are tracking the trail of knots as they swing based on their position. I created a mapping from offset to next move, and then simulating the rope was a piece of cake
struct Move {
Grid::Direction direction = Grid::Direction::Up;
unsigned long moves = 0;
};
size_t getPositionsVisitedByTail(std::span<Move> moves, size_t numberOfKnots){
Grid::Coord initial { 0, 0 };
std::vector<Grid::Coord> positions {numberOfKnots, initial};
std::set<Grid::Coord> tailPositions{ initial };
for(const auto& move: moves){
for(unsigned int counter = 0; counter < move.moves; ++counter){
positions[0] = positions[0] + move.direction;
for (size_t knot = 1; knot < numberOfKnots; ++knot){
positions[knot] = positions[knot] + getMoveTowards(positions[knot], positions[knot - 1]);
}
tailPositions.insert(positions[numberOfKnots - 1]);
}
}
return tailPositions.size();
}
Day 10
Type of Problem: Computer Simulation
Difficulty: Easy-Medium
Rating: 5/5
As I’m retroactively rating these, I’m surprised to see how many of these I legitimately enjoyed. We’re in day 10 and this is my 4th 5/5. This puzzle involved computer simulation of opcodes, albeit with no jumps, which does make things easier. Checking registers was pretty straight forward, but I thought it was cool to actually use this information to print it out to screen in part 2. There’s something so primally satisfying of seeing ASCII letters show up on your screen with a successful algorithm.
Here’s my draw algorithm, given what the value of x was at each tick:
void drawScreen(std::span<int> valuesDuringCycle){
for(int tick=0; tick<=240; ++tick){
if(tick % 40 == 0){
std::cout << "\n";
}
auto index = tick%40;
std::cout << ((valuesDuringCycle[tick] >= index-2 && valuesDuringCycle[tick] <= index ) ? "#" : ".");
}
std::cout << "\n";
}
Day 11
Type of Problem: Game Simulation / Modular Arithmetic
Difficulty: Medium-Hard
Rating: 5/5
This was the first problem that gave me a pause for part 2. Part 1 wasn’t too bad, except the amount of parsing was not fun with C++ (hooray std::regex though). Once parsed, part 1 was pretty much just a run through of simulation of some numeric operations. However, part 2 threw me. Some quick back-of-the-envelope math showed that I could not store the values, even in 64 bit operations.
I looked through the input, and noticed something about my monkeys. Each monkey was always checking divisibility based on a prime number. The prime-ness of a number ended up not being relevant, but it kickstarted me thinking about factors and division, which got me to the final answer.
Since we are only needing to know if we are evenly divisible , I should be able to just track my value modulus the divisor. But since any item can go to any monkey, I treat each item as a mapping between divisor and current value modulus that divisor. This way, as I do operations such as adding or multiplying on that value, and it never grows bigger than my divisor, but because of modular arithmetic, I never lose what I care about. When I saw the correct answer on my screen, I have to say, this problem made me feel smart.
template<typename Monkeys>
unsigned long getTwoMostActiveMonkeyProduct(Monkeys monkeys, unsigned int numberOfRounds) {
for(unsigned int round = 0; round < numberOfRounds; ++round) {
//std::cout << "Round #" << round << "\n";
for(auto& monkey: monkeys) {
while(monkey.hasItems()) {
auto [item, to] = monkey.inspectAndThrow();
monkeys[to].addItem(item);
}
}
}
Monkeys monkeyCopy{monkeys.begin(), monkeys.end()};
using MonkeyType = typename Monkeys::value_type;
std::partial_sort(monkeyCopy.begin(), monkeyCopy.begin() + 2, monkeyCopy.end(), [](const MonkeyType& monkey1, const MonkeyType& monkey2){
return monkey1.getNumberOfInspections() > monkey2.getNumberOfInspections();
});
return monkeyCopy[0].getNumberOfInspections() * monkeyCopy[1].getNumberOfInspections();
}
Day 12
Type of Problem: Graph Theory
Difficulty: Medium
Rating: 4/5
Good old path-finding on day 12. We’re trying to get from one point to another, but we can only go up one level with each step. A simple Djikstra’s algorithm makes quick work of it.
Part 2 involved finding the shortest path from a set of different values. I considered an all-shortest-paths algorithm such as Floyd-Warshall’s but I was lazy and just did Djikstra’s for each pair of points.
unsigned int findShortestPathFrom(const auto& grid, Grid::Coord start, Grid::Coord end){
std::set<Grid::Coord> seen {start};
std::set<Grid::Coord> currentPositions {start};
unsigned int steps = 0;
while(currentPositions.find(end) == currentPositions.end()){
std::set<Grid::Coord> newPositions;
for(auto position: currentPositions) {
auto neighbors = grid.getNeighbors(position);
for(auto& neighbor: neighbors){
if (grid[neighbor] <= grid[position]+1 && seen.find(neighbor) == seen.end()){
newPositions.insert(neighbor);
}
}
}
++steps;
if(newPositions.empty()) {
// no way forward, return a large amount
return UINT32_MAX;
}
currentPositions = newPositions;
seen.insert(currentPositions.begin(), currentPositions.end());
}
return steps;
}
Day 13
Type of Problem: Parsing / Recursion
Difficulty: Medium
Rating: 3/5
Well, if you are working in Python, you can just eval your input or treat it as input and then write your algorithm. I unfortunately, need to parse it out in C++. This wasn’t too bad of a problem, but I did have to deal with recursive parse. This would normally trip me up, but I’ve done it enough for AoC problems that I was ready this year. My big hang-up was when comparing values, I was just returning a boolean, however when working recursively, there are three options: We are less than, we are greater than, or we are equal and need to look at next element.
When dealing with iterators in C++, you unfortunately need to do some std::distance hijinks to figure out indices. I’ve shown my part 2 implementation below, which uses a compare function I wrote for part 1.
unsigned int getDecoderIndicesProduct(std::span<PacketPair> packetPairs) {
std::vector<Packet> packets;
for(const auto& packetPair: packetPairs){
packets.push_back(packetPair.p1);
packets.push_back(packetPair.p2);
}
std::string decoder1 = "[[2]]";
std::string decoder2 = "[[6]]";
auto start1 = decoder1.begin();
Packet decoderPacket1(start1, decoder2.end());
auto start2 = decoder2.begin();
Packet decoderPacket2(start2, decoder2.end());
packets.push_back(decoderPacket1);
packets.push_back(decoderPacket2);
std::sort(packets.begin(), packets.end(), [](const auto& p1, const auto& p2){
return p1.compare(p2) == Result::LessThan;
});
return (1+std::distance(packets.begin(), std::find(packets.begin(), packets.end(), decoderPacket1))) * (1+std::distance(packets.begin(), std::find(packets.begin(), packets.end(), decoderPacket2)));
}
Day 14
Type of Problem: Grid Manipulation / Simulation
Difficulty: Medium-hard
Rating: 4/5
This reminded me of a (imo, more fun) problem from a few years back that dealt with falling sand. It was still pretty fun visualizing it, but it wasn’t nearly as complex as that one. This puzzle dealt with deterministic flow of sand as it navigated around a cavern.
For part 1, I created a lookup per column of sand that tracked all the top grains of sand with space above it. So if I have a sand at column x, and at vertical position y, then find the first sand directly below me. Then I figure out if I need to move diagonally left, right, or stay at rest and act accordingly. This way, I don’t have to track every grain of sand (most AoC problems you need to look for ways of storing the least amount of information as possible).
Part 2 was just making sure that we hit a floor instead of going off the edge, so I handled that with an if/else. Here’s my code for placing sand (take note of std::lower_bound for checking where my sand is).
bool placeSand() {
if(sandAtOrigin) {
return false;
}
auto sand = ORIGIN;
bool atRest = false;
while(!atRest) {
// check for drop straight down
auto straightDown = blockedAreas[sand.xPos].lower_bound(sand.yPos+1);
auto diagonalLeft = blockedAreas[sand.xPos-1].lower_bound(sand.yPos+1);
auto diagonalRight = blockedAreas[sand.xPos+1].lower_bound(sand.yPos+1);
assert(!blockedAreas[sand.xPos].contains(sand.yPos));
if(straightDown == blockedAreas[sand.xPos].end() || diagonalLeft == blockedAreas[sand.xPos - 1].end() || diagonalRight == blockedAreas[sand.xPos +1].end()){
if(floor){
if(straightDown == blockedAreas[sand.xPos].end()){
blockedAreas[sand.xPos].insert(floor.value() - 1);
}
else if(diagonalLeft == blockedAreas[sand.xPos-1].end()){
blockedAreas[sand.xPos-1].insert(floor.value() - 1);
}
else if(diagonalRight == blockedAreas[sand.xPos+1].end()){
blockedAreas[sand.xPos+1].insert(floor.value() - 1);
}
atRest = true;
}
else {
return false;
}
}
else if(*straightDown == sand.yPos + 1 && *diagonalLeft == sand.yPos + 1 && *diagonalRight == sand.yPos+1){
blockedAreas[sand.xPos].insert(sand.yPos);
atRest = true;
}
else if(*straightDown != sand.yPos + 1) {
sand.yPos = *straightDown-1;
}
else if(*diagonalLeft != sand.yPos + 1) {
sand.yPos = *diagonalLeft-1;
--sand.xPos;
}
else if(*diagonalRight != sand.yPos + 1) {
sand.yPos = *diagonalRight-1;
++sand.xPos;
}
if(sand == ORIGIN) {
sandAtOrigin = true;
}
}
return true;
}
Day 15
Type of Problem: Grid Manipulation
Difficulty: Medium-Hard
Rating: 3/5
This was a problem of trying to find where holes were in a sensor coverage map. You were given a set of sensors which could tell you the closest beacons. You know there are no beacons closer, but you can’t say anything about any other beacon. I gave this a medium-hard instead of hard because even if you do it a slow way, you still get an answer before the heat death of the universe.
The difficulty with this problem is the sheer scale of it, we’re dealing with a 4 million by 4 million grid. There’s no sense of checking every point. What I did instead was for each row, sort the sensors by their x position, and then look for the first place where there is a gap in coverage ( where their max x in that row is more than 2 away from the next sensors min x. If this happens, there’s a gap. There’s probably a faster way checking for square overlaps that has a computational complexity based on sensors than points, but I got my answer in 10 seconds, so I was fine.
Here is my aforementioned Part 2 code:
unsigned long findSensorTuningFrequency(std::vector<Sensor> sensors){
std::ranges::sort(sensors, [](const auto& s1, const auto& s2) { return s1.sensor.xPos < s2.sensor.xPos; });
for(int row = 0; row < 4'000'000; ++row){
std::vector<std::pair<long, long>> sortedRanges;
auto sensorPair = [row](const auto& sensor){ return std::make_pair(sensor.getMinXInRangeAtRow(row), sensor.getMaxXInRangeAtRow(row)); };
std::ranges::copy(std::views::transform(sensors, sensorPair), std::back_inserter(sortedRanges));
std::ranges::sort(sortedRanges);
long min = 0;
for(auto& range: sortedRanges) {
if (range.second < 0){
continue;
}
if(range.first > 4'000'000){
break;
}
if(range.first <= min + 1){
min = std::max(range.second, min);
}
else {
// there is a gap
assert(range.first == min + 2);
return static_cast<unsigned long>(range.first-1) * 4'000'000 + row;
}
}
}
assert(false);
return 0;
}
Day 16
Type of Problem: Graph Theory
Difficulty: Medium Hard
Rating: 3/5
I have an inkling that there is an interesting way to do dynamic programming for this one (I did not crack it with dynamic programming, so mien is a much slower way). The idea is that you’re trying to find the maximum flow you can achieve by moving through a graph and opening valves. I don’t have much to say, but that I used Djikstra’s again (I could have used A* to go faster, but oh well).
When doing Djikstra’s, you have to be able to identify seen states, so it’s important to know all of your inputs (in this case, my room, the elephant’s room, and the set of open valves).
Then, for each action of you and the elphant, you have to cartesian product through the options. Here’s the workhorse of my ugly code that takes minutes to run:
bool isMyValveOpen = (room.flowRate != 0 && !position.isValveOpen(position.valve) );
bool isElephantValveOpen = (elephantRoom.flowRate != 0 && !position.isValveOpen(position.elephantValve) );
auto myTunnels = room.tunnels;
auto elephantTunnels = elephantRoom.tunnels;
if(isMyValveOpen && isElephantValveOpen && position.valve != position.elephantValve){
unsigned int newRate = totalFlow + (26 - minutes) * (room.flowRate + elephantRoom.flowRate);
auto openValves = position.openValves;
openValves.insert(position.valve);
openValves.insert(position.elephantValve);
auto key = Position{position.valve, position.elephantValve, std::move(openValves)};
insertRate(newPositions, key, newRate);
}
else if(isMyValveOpen){
unsigned int newRate = totalFlow + (26 - minutes) * (room.flowRate);
auto openValves = position.openValves;
openValves.insert(position.valve);
for(const auto& tunnel: elephantRoom.tunnels){
auto key = Position{position.valve, tunnel, openValves};
insertRate(newPositions, key, newRate);
}
}
else if(isElephantValveOpen){
unsigned int newRate = totalFlow + (26 - minutes) * (elephantRoom.flowRate);
auto openValves = position.openValves;
openValves.insert(position.elephantValve);
for(const auto& tunnel: room.tunnels){
auto key = Position{tunnel, position.elephantValve, openValves};
insertRate(newPositions, key, newRate);
}
}
else {
for(const auto& tunnel: room.tunnels){
for(const auto& elephantTunnel: elephantRoom.tunnels){
auto key = Position{tunnel, elephantTunnel, position.openValves};
insertRate(newPositions, key, totalFlow);
}
}
}
Day 17
Type of Problem: Game Simulation
Difficulty: Medium-Hard
Rating: 4/5
I never thought I’d be playing Tetris as part of AoC, but here we are. The goal was to place tetrominoes and quintominoes in a grid and see how high they stack. I had a few off-by-one errors that threw me, but I ultimately got it. To track my grid, I made a vector of arrays of 7 bools: true for a block, false for not. From there, it was easy to track how they stacked. I also tracked the shapes of depth from bottom, left, and right, and height of each column of each shape. This made it much more straightforward to know if something can fit.
I correctly predicted part 2, where we had to run an absurdly long time. Whenever this comes up, you have to find out some minimal state that you can reference, and be able to figure out when that cycles around. For this case, my input set was {currentShape, currentJetDirection, contours}. The shape and direction made sure that I was at the same point of the input (I knew those were cyclical), so how do I tell when the tetris stack is cyclical? Well, I track the contours of the shape from the top down. I really don’t care about shapes beyond the top layer. Here’s my contour calculation;
std::array<unsigned int, 7> getContours(const auto& spaces) {
std::array<unsigned int, 7> out = {0,0,0,0,0,0,0};
std::set<unsigned int> numbersToCheck = {0,1,2,3,4,5,6};
auto iter = spaces.rbegin();
unsigned int depth = 0;
while(!numbersToCheck.empty()){
std::vector<unsigned int> toDelete;
for(auto num: numbersToCheck){
if((*iter)[num]) {
out[num] = depth;
toDelete.push_back(num);
}
}
for(auto num: toDelete){
numbersToCheck.erase(num);
}
++depth;
++iter;
}
return out;
}
Day 18
Type of Problem: Graph Theory / 3d Simulation
Difficulty: Medium
Rating: 4/5
This was another problem that reminded me of a harder previous year problem. I remember fretting over that one, which was quite hard. I was happy to see this be a much easier one, and I was able to get the answer quite quickly.
At first, you’re just checking how many exposed faces there are, given a list of cubes in 3d space. If two cubes share a face, you just count their other 5 faces. So for me, I just iterated each cube, adding it to a list and adding 6 faces to my counter. For each cube that new cube touched, I subtracted two cubes (see code below).
The second part was a bit easier. At first I was worried there would be face merging, but instead, it just said you had to count externally exposed faces. I just started one space beyond the upper left front cube, and did a DFS across air to see which are touching cube spaces and which aren’t. This way, I would ignore any internal pockets of air.
unsigned int getExposedFaces(std::span<Cube> cubes){
std::vector<Cube> seenCubes;
unsigned int exposedFaces = 0;
for(const auto& cube1: cubes) {
for (const auto& cube2: seenCubes){
if (cube1.isAdjacentTo(cube2)){
exposedFaces -= 2;
}
}
seenCubes.push_back(cube1);
exposedFaces += 6;
}
return exposedFaces;
}
Day 19
Type of Problem: Graph Theory
Difficulty: Hard
Rating: 3/5
I probably would have liked this one more if I figured out hte dynamic programming solution, but I didn’t. Thus, I had to go through a BFS, and most of my time was just waiting for my BFS to go through and figure out best candidates.
My first attempt at part 2 took 90 minutes before running out of memory, so I had to make some simple optimizations : Optimize for {number of geodes, number of geode robots}, and prune any branch that would not produce enough geodes (assuming maximal production for remaining turns) each minute. I probably could have been smarter about how I pruned to really cut the time down, but I had an answer and was running behind at this point.
Day 20
Type of Problem: Data Structure / Optimization
Difficulty: Medium
Rating: 3/5
Whenever you work on circular structures, you have to be smart about how you find elements in that list. You don’t want to shift something one million times, it’s better to find the intended position and just shift to that. This means you need to be smart with modular math.
In order to do this smartly, I also added a lookup: from number to Node pointer. This way, it was really easy fror me to find a node (I kept the list of input separate from my nodes so that it wouldn’t change). I could then calculate the number of shifts, and just make that shift through use of swaps
for(size_t time = 0; time < times; ++time){
for(size_t index = 0; index < numbers.size(); ++index){
auto number = numbers[index] * multiplier;
auto node = indexToNodeLookup[index];
auto shifts = number % static_cast<int>(numbers.size() - 1);
for(unsigned int shift = 0; shift < abs(shifts); ++shift){
if(number < 0){
std::swap(node->left->value, node->value);
std::swap(node->left->index, node->index);
std::swap(indexToNodeLookup[index], indexToNodeLookup[node->index]);
node = node->left;
}
if(number > 0){
std::swap(node->right->value, node->value);
std::swap(node->right->index, node->index);
std::swap(indexToNodeLookup[index], indexToNodeLookup[node->index]);
node = node->right;
}
}
}
}
Day 21
Type of Problem: Recursion
Difficulty: Medium-Hard
Rating: 5/5
I liked this one specifically for part 2. The first part was just standard tree operations, but the second part made me pause. I really had to think about what to do. In the problem, you had to track a variable through algebra up and down the tree. I set up a map of powers to coefficients so that I could add, subtract, multiply or divide polynomials. From there, it was just balancing an equation and making sure I could determine what a human should shout.
I had a few false starts, as I started with ints (needed to be longs), then found out that not every divide was even (Thank you asserts throughout my code), so made it a float. Then figured I didn’t have enough precision, so I made my own Fraction class. Here’s my recursive resolve of polynomials
const std::unordered_map<char, std::function<Coefficients(const Coefficients&, const Coefficients&)>> coefficientOperationLookup = {
{'+', addCoefficients},
{'-', subtractCoefficients},
{'*', multiplyCoefficients},
{'/', divideCoefficients}
};
Coefficients resolve(const std::string& name, const auto& monkeyLookup, auto& answerLookup) {
if(name == "humn") {
return Coefficients { { 1, Fraction { 1 } } };
}
if(answerLookup.find(name) == answerLookup.end()){
auto& monkey = monkeyLookup.at(name);
if(std::holds_alternative<long>(monkey.opOrNumber)) {
answerLookup[name] = Coefficients{ {0, Fraction { std::get<long>( monkey.opOrNumber )}} };
}
else {
Operation op = std::get<Operation>(monkey.opOrNumber);
Coefficients c1 = resolve(op.arg1, monkeyLookup, answerLookup);
Coefficients c2 = resolve(op.arg2, monkeyLookup, answerLookup);
answerLookup[name] = coefficientOperationLookup.at(op.operation)(c1, c2);
}
}
return answerLookup[name];
}
Day 22
Type of Problem: Grid Manipulation / 3d Simulation
Difficulty: Hard
Rating: 4/5
Based on some chatter in my local dev Slack channel, I knew this would be the beast of the year. There’s always one in the last five days that is a showstopper and this one took me the better part of three days. I got most of my code written up pretty fast, but was plagued by a lot of tedium (I have a ton of if statements hardcoding edge mappings and face transitions). I counted up 11 stupid errors, such as off by one errors, misparsing input, correcting face transitions, and ended up testing every single face transition, with a wall and without. I even rewrote my code in Python to see if I’d get a different answer. I was stuck. I finally broken down and looked up a solution on the subreddit. I did not look at their answer or use their code to get an answer, but just printed out each move they made. Unfortunately, their moves were the exact same as mine. I found a bug in their code, but it didn’t end up changing the steps at all. Well, it turns out, I had the right answer for at least a day, but just assumed it was wrong and never input it (don’t ask me why). I was glad that I solved it on my own, but mad that I wasted a day.
Day 23
Type of Problem: Cellular Automata
Difficulty: Medium
Rating: 3/5
I was glad to have a quick one after Day 22. It was pretty standard cellular automata / moving around a grid based on specific rules. I made one stupid boo-boo where I didn’t reset my directions to check between part 1 and part 2 (that’s what I get for using shared mutable state – serves me right). Part 2 runs forever for me, and I could probably optimize by tracking only elves near another left (no need to calculate if they don’t get near anybody, and over time, more will be static)
I can definitely tell that I’m nearing the end, as my code is getting sloppier and I care about performance less. Here’s how I run a round
bool runRound(std::span<Elf> elves) {
std::map<Grid::Coord, unsigned int> proposedMoves;
for(const auto& elf: elves){
auto move = elf.getProposedMove(elves);
proposedMoves.try_emplace(move, 0U);
proposedMoves[move]++;
}
std::vector<Elf> oldElves(elves.begin(), elves.end());
for(auto& elf: elves) {
auto move = elf.getProposedMove(oldElves);
if(proposedMoves.at(move) == 1){
if(move != elf.position()){
elf.setNewPosition(move);
}
}
}
std::rotate(offsetDirectionPairs.begin(), offsetDirectionPairs.begin() + 1, offsetDirectionPairs.end());
std::vector<Elf> newElves(elves.begin(), elves.end());
return oldElves != newElves;
}
Day 24
Type of Problem: Iteration / Set Operation
Difficulty: Easy
Rating: 4/5
I liked this problem, as it dealt with a path finding algorithm ,while dealing with figuring out where blizzards would be. For me, my bulk of my time was figuring out a blizzard prediction equation, (seen below). From there, I do my normal BFS of positions and prune out any position that had a blizzard at it.
I liked the there and back again idea, and it was easy enough to do it that this problem went by quickly.
Grid::Coord projectedPosition(size_t maxX, size_t maxY, Grid::Coord coord, Grid::Direction direction, unsigned int tick) {
if(direction == Grid::Direction::Right) {
int value = coord.xPos - 1 + tick;
return Grid::Coord{static_cast<int>(value % (maxX - 1) + 1), coord.yPos};
}
if(direction == Grid::Direction::Left) {
int value = coord.xPos - 1 - tick ;
while(value < 0) {
value += (maxX-1);
}
return Grid::Coord{static_cast<int>(value % (maxX - 1) + 1), coord.yPos};
}
if(direction == Grid::Direction::Up) {
int value = coord.yPos - 1 - tick ;
while(value < 0) {
value += (maxY-1);
}
return Grid::Coord{coord.xPos, static_cast<int>(value % (maxY-1) + 1)};
}
if(direction == Grid::Direction::Down) {
int value = coord.yPos - 1 + tick ;
return Grid::Coord{coord.xPos, static_cast<int>(value % (maxY-1) + 1)};
}
assert(false);
return Grid::Coord{0,0};
}
Day 25
Type of Problem: Parsing / Algebra
Difficulty: Medium
Rating: 5/5
This was a nice mathematical problem to finish the year on. It was a unique way of thinking about numbers, and it took me a short while to figure out how to effectively parse back. I actually ran into a few problems my first go-around, and it ended up being a signed vs unsigned problem and 32-bit vs 64-bit mismatches. After figuring that out, the code worked like a charm. Here it is in its entirety
std::string toSnafuNumber(int64_t number) {
std::string out = "";
while(number != 0) {
auto remainder = number % 5;
if(remainder < 3){
out += std::to_string(remainder);
number -= remainder;
}
else if(remainder == 3) {
out += "=";
number += 2;
}
else {
out += "-";
number += 1;
}
number /= 5LL;
}
return std::string(out.rbegin(), out.rend());
}
int64_t fromSnafuNumber(const std::string& str) {
int64_t sum = 0U;
int64_t factor = 1;
for(char c: std::views::reverse(str)) {
switch(c) {
case '=': sum -= 2LL*factor; break;
case '-': sum -= factor; break;
case '1': sum += factor; break;
case '2': sum += 2LL*factor; break;
default: break;
}
factor *= 5;
}
assert(toSnafuNumber(sum) == str);
assert(sum > 0);
return sum;
}
int main() {
auto numbers = input::readLines("input/input25.txt") | std::views::transform(fromSnafuNumber);
int64_t total = std::accumulate(numbers.begin(), numbers.end(), 0LL);
std::cout << fromSnafuNumber("1=10-0001=--==2") << " " << total << " " << toSnafuNumber(total) << "\n";
}
Pat Viafore 