Advent of Code 2024 [Days 10 and 11]

February 21, 2025 · AoC C++ · Advent of Code

Advent of Code 2024 [Days 10 and 11]#

Welcome back to my C++ learning journey through Advent of Code 2024! Continuing from Day 9, this part covers my solutions and reflections for Days 10 and 11. The goal remains the same: using these challenges to get better at C++.

This is my attempt to document my learning journey through Advent of Code 2024. Instead of cluttering with each post for each day’s challenge, I’ll be grouping my progress into consolidated posts. This page is the fourth part of my progress log covering Days 10 and 11.

Full solutions are available on GitHub: ABD-01/AoC2024.

Day 10: Hoof It - Finding Hiking Trails on a Topographic Map#

Solution Overview #

Given a topographic map where each position’s height ranges from 0 (lowest) to 9 (highest), the goal is to find a valid hiking trail. A valid trail is one where the height increases gradually (i.e., by 1 unit at each step) from a trailhead (0-height) to a 9-height position.

Part 1 : For each trailhead, find number of distinct 9-height position that can be reached. Perform a Depth First Search (DFS) from each trailhead. When reaching a 9-height position, increment the result count. To ensure distinct target counting, keep track of visited positions.

Part 2: For each trailhead, find the number of distinct trails leading to 9-height position. Same as before, perform a DFS. However, this time, multiple trails can lead to same target (i.e. 9-height), hence will not stop exploration even if position is already visited.

void DFS(const std::vector<std::vector<int>>& map, const std::pair<int, int>& idx, std::unordered_set<int>& visited, int& result)
{
    static std::pair<int, int> dirs[4] = {
        {-1, 0}, {0, 1}, {1, 0}, {0, -1}
    };

    int curr = map[idx.first][idx.second];

#if PART_2
    if(visited.find((idx.first*map[0].size() + idx.second)) != visited.end()) return; 
    visited.insert((idx.first*map[0].size() + idx.second));
#endif

    if(curr == 9)
    {
        cout << "Found 9-height position" << endl;
        ++result;
        return;
    }

    for(const auto& dir: dirs)
    {
        int i = idx.first+dir.first, j = idx.second+dir.second;
        if(i<0||i>map.size()-1||j<0||j>map[0].size()-1)
        {
            continue;
        }
        int temp = map[i][j];
        if(temp-curr != 1)
        {
            continue;
        }
        DFS(map, {i,j}, visited, result);
    }
}

int main(int argc, char* argv[])
{
    while(!toVisit.empty())
    {
        int result = 0;
        std::unordered_set<int> visited = {};
        DFS(map, toVisit.top(), visited, result);
        toVisit.pop();
        r += result;
    }
    cout << "Part " <<  (PART_2 ? 2 : 1) <<  ": " << r << endl;
}

Optimizations#

Instead of using unordered_set<int> data structure for keeping record of visited, tried using different data structures.

Performance on Day 10 Part 2#
Data Structure	Time (µs)
vector<vector<bool>>	1044
set<int>	402
unordered_set<int>	314
vector<char>	134
vector<bool>	113

vector<vector<bool>> performs poorly due to:
- It has double indirection overhead.
- Memory layout is non-contiguous, this means elements of different rows are not stored contiguously, leading to inefficient memory access.
set<int> is relatively slower:
- Uses balanced tree (typically Red-Black Tree) with $O(\log N)$ insertion and lookups.
unordered_set<int>:
- hashing overhead
- amortized insertion time is $O(1)$, even though worst-case insertion (rehashing) is $O(n)$.
- unordered_set<int> is useful when grid is extremely sparse, meaning only a few cells need to be marked as visited. However, in dense grids, it adds hashing overhead.
vector<char> and vector<bool> are fastest:
- both use contiguous in memory, which minimizes cache misses and improves performance
- vector<bool> packs multiple boolean values (up to 8) into a single byte.

template<typename VisitedType>
void DFS(const std::vector<std::vector<int>>& map, const std::pair<int, int>& idx, VisitedType& visited, int& result);

template <typename VisitedType>
bool isVisitedAndMark(VisitedType& visited, const std::pair<int, int>& idx, int width);

// Specialization for std::unordered_set<int>
template<>
bool isVisitedAndMark<std::unordered_set<int>>(std::unordered_set<int>& visited, const std::pair<int, int>& idx, int width) {
    int pos = idx.first * width + idx.second;
    if (visited.find(pos) != visited.end()) return true;
    visited.insert(pos);
    return false;
}

// Specialization for std::vector<std::vector<bool>>
template<>
bool isVisitedAndMark(std::vector<std::vector<bool>>& visited, const std::pair<int, int>& idx, int) {
    if (visited[idx.first][idx.second]) return true;
    visited[idx.first][idx.second] = true;
    return false;
}

Concepts Learned#

vector<bool>#

std::vector<bool> is bit-packed, meaning it stores multiple bool values in a single byte, reducing memory footprint.

std::vector<bool> is a possibly space-efficient specialization of std::vector for the type bool.

Source: gcc/libstdc++-v3/include/bits/stl_bvector.h

Best for very large boolean datasets where memory efficiency is critical or need a dynamically resizable bit-array but don’t require direct bit manipulation.

Pros	Cons
Space-efficient (bit-packed), dynamic resizing.	no direct memory access.
Contiguous memory allows for efficient cache utilization.	performance issues due to bit manipulations. (Slower per-element modification)

std::vector<bool> vec = {false, false, true, false};
// std::vector<bool> does not store actual bools
for(auto& i: vec) // compilation error: cannot bind `bool&` to `std::vector<bool>::reference
{
	std::cout << i << " "; 
}

Alternatives#

std::bitset<N>: Faster but requires compile-time size.
std::vector<char>: Uses 1 byte per value, avoids bit-packing overhead, direct memory access.

Return Value Optimization#

# TODO

Example

std::vector<std::pair<int, int>> my_function() {
    std::vector<std::pair<int, int>> local_variable;
    return std::move(local_variable);
}
// warning: moving a local object in a return statement prevents copy elision [-Wpessimizing-move]

Template Specialization#

In C++, function template specialization allows you to define custom implementations of a function template for specific types. This is useful when the default behavior is inefficient or incorrect for certain data structures.

template <typename T>
bool isVisitedAndMark(T& visited, const std::pair<int, int>& idx, int width);

template <>  // explicit specialization for T = std::unordered_set<int>
bool isVisitedAndMark<std::unordered_set<int>>(std::unordered_set<int>& visited,...) {
    // Implementation for std::unordered_set<int>
}

When specializing a function template, its template arguments can be omitted if template argument deduction can provide them from the function arguments:

—Explicit specializations of function templates - cppreference.com

std::find#

Example

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> nums = {10, 20, 30, 40, 50};
    std::vector<int>::iterator it = std::find(nums.begin(), nums.end(), 30);

    if (it != nums.end())
        std::cout << "Found at index: " << std::distance(nums.begin(), it) << std::endl;
    else
        std::cout << "Not found." << std::endl;
}

Source: gcc/libstdc++-v3/include/bits/stl_algo.h

Stack in CPP#

# TODO

References and Resources#

Day 11: Plutonian Pebbles #

Solution Overview #

Given a list of pebbles, each with a numerical value. After each blink, the number of pebbles and their values change according to specific rules. The goal is to find the total number of pebbles after a set number of blinks.

The conditions are: $$ f(n+1) = \left\{ \begin{array}{ll} 1 & \text{if } n = 0 \\ \text{HIGH}(n), \text{LOW}(n) & \text{if numDigits($n$) is even} \\ n \times 2024 & \text{else} \end{array} \right. $$

where $\text{HIGH}(n)$ refers to the first half of digits., $\text{LOW}(n)$ refers to the second half of digits.

Example: If $n = 123456 ,\ \text{HIGH}(n) = 123, \ \text{LOW}(n) = 456$

My solution was to use a recursive function where each call represents a single blink. It has a depth parameter that terminates the recursion when the desired number of blinks is achieved.

Part 1: 25 Blinks Part 2: 75 Blinks

void blink(ull value, ull& result, int numBlinks,  int depth)
{
    if(depth > numBlinks - 1) // depth start with 0
        return;
    
    if(value == 0) 
    {
        value = 1;
        return blink(value, result, numBlinks, depth+1);
    }
    int n = numDigits(value);
    if (!(n%2)) // n is even
    {
        ull splitValue = 0;
        int lastDigit = 0;
        int base10 = 1;
        for(auto i = 0; i < n/2; ++i)
        {
            lastDigit = value % 10;
            value /= 10;
            splitValue += (lastDigit * base10);
            base10 *= 10;
        }
        result++;
        blink(value, result, numBlinks, depth+1);
        blink(splitValue, result, numBlinks, depth+1);
        return;
    }
    value = value * 2024;
    return blink(value, result, numBlinks, depth+1);
}

This approach works well for Part 1, but for Part 2, the sheer number of recursive calls makes the program infeasible. The exponential growth in the number of pebbles causes excessive memory usage and function calls, leading to stack overflow.

We cannot store the entire list of stones, however we can store the count of each different stone instead. I could make a map that store value as key, and it’s count as the value, but I was unsure of how many different stones are possible. To get a very rough upper bound assume, in the worst case each pebble split into 2 every blink, we will have $2^{numBlinks}$ pebbles at the end. How many distinct?? I don’t know… Help me with that if you solved it that way. If you’ve computed this bound more rigorously, let me know in the comments!

Since, I was skeptical about the memory used to store each stone and it’s count. I used a different method, just caching the result for stones with values 0 to 9 for $numBlinks$. {lineno-start=42}

std::vector<std::vector<ull>> cache(10, std::vector<ull>(MAX_NUM_BLINKS, 0));
// stores the resulting number of stones for values from 0 to 9
// cache[v][b-1] represent number of pebbles after blinking b times starting with pebble of value v

void fill_cache(int numBlinks)
{
    for(auto nb = 0; nb < numBlinks; ++nb)
    {
        for(ull i = 0; i < 10; ++i)
        {
            ull r = 1;
            blink(i, r, nb+1);
            cache[i][nb] = r;
        }
    }
}

So before I start solving, I already know that cache[3][55] is what would happen if stone with value $3$ is blinked $56$ times. This will help short-circuit the entire blink calls for that value.

While pebbles may have values greater than 9, many will eventually be reduced to a single-digit value due to repeated splitting. Thus, caching results for numbers 0-9 is a memory-efficient approximation

This caching enabled finding the number of stones for large values. {lineno-start=141}

    if(value < 10)
    {
        if (cache[value][numBlinks - depth - 1] != 0)
        {
            numShortCircuited++;
            DEBUG("Short circuited (" << g_numShortCircuited << ")" << endl);
            DEBUG("Pebble " << value << " after " << numBlinks - depth << " blinks will be split into " << cache[value][numBlinks-1 - depth] << endl);
            result += (cache[value][numBlinks-1 - depth] - 1); 
            // that -1 is there because the current stone is being counted twice.
            return; // no more recursive call again
        }
    }

Also, a bit about numDigits See file: Day11_Plutonian_Pebbles/numDigits.cpp {lineno-start=108}

int numDigits(unsigned long long i)
{
    int n = 1;
    if ( i >= 10000000000000000 ) { n += 16; i /= 10000000000000000; }
    if ( i >= 100000000         ) { n += 8; i /= 100000000; }
    if ( i >= 10000             ) { n += 4; i /= 10000; }
    if ( i >= 100               ) { n += 2; i /= 100; }
    if ( i >= 10                ) { n += 1; }

    return n;
    // ref: https://stackoverflow.com/a/6655759
}

Performance on Day 11 Part 2#
Approach	g++ (No -O3)	g++ -O3	Clang -O3	Speedup (g++ No -O3 → Clang -O3)
StackOverflow (Bitwise Check)	4,148,573 ns	2,298,124 ns	120 ns	~34,500x Faster
Logarithmic (`log10`)	14,081,701 ns	10,078,787 ns	40 ns	~350,000x Faster
Iterative Division (`/ 10`)	38,035,651 ns	11,254,840 ns	30 ns	~1.26M× Faster
String Conversion (`std::to_string`)	73,341,935 ns	34,854,592 ns	31,866,131 ns	~2.3x Faster
Builtin CLZ (`__builtin_clzll`)	2,909,022 ns	2,799,729 ns	30 ns	~72,000x Faster

Concepts Learned#

Constant Expression#

Introduced in C++11.

can be evaluated at compile time
give the compiler deep insight
constexpr is by design thread safe (A data race requires shared mutable state, something which is const is not mutable).

References and Resources#

This marks the fourth part of my Advent of Code 2024 journey. More updates soon. If you’re also learning C++ or participating in Advent of Code, I’d love to hear about your experiences! Share your thoughts, tips, or solutions in the comments below.

Learning CPP via Advent of Code 2024 [Day 9]

Advent of Code 2024 [Days 10 and 11]

Advent of Code 2024 [Days 10 and 11]#

Day 10: Hoof It - Finding Hiking Trails on a Topographic Map#

Solution Overview#

Optimizations#

Concepts Learned#

vector<bool>#

Alternatives#

Return Value Optimization#

Template Specialization#

std::find#

Stack in CPP#

References and Resources#

Day 11: Plutonian Pebbles#

Solution Overview#

Concepts Learned#

Constant Expression#

References and Resources#

Comments

Solution Overview #

Day 11: Plutonian Pebbles #

Solution Overview #