Advent of Code 2024 [Days 6 to 8]

Advent of Code 2024 [Days 6 to 8]#

Welcome Back!. I’ve decided to use Advent of Code 2024 as a platform to improve my C++ skills, and in the previous part I covered Days 1 to 5.

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 second part of my progress log covering Days 6 to 8.

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

Day 6: Guard Gallivant#

Solution Overview#

 8void Guard::move(std::vector<std::string>& map)
 9{
10    map[position.x][position.y] = 'X';
11    Point temp = position+direction;
12
13    if (temp.x < 0 || temp.y < 0 || temp.x >= map.size() || temp.y >= map[0].size())
14    {
15        can_move = false;
16        cout << "Guard left the map" << endl;
17        return;
18    }
19
20    if (map[temp.x][temp.y] == '#' || map[temp.x][temp.y] == 'O')
21    {
22        // Guard hit an obstacle, turn right
23        turnRight();
24        move(map);
25        return;
26    }
27
28    if(is_looping(temp, direction))
29    {
30        can_move = false;
31        stuck_in_loop = true;
32        cout << "Guard stuck in a Loop" << endl;
33        return;
34    }
35
36    position = temp;
37
38    visited.emplace(position, direction);
39}
40
41void Guard::turnRight()
42{
43    //-1,0  -> 0,1
44    // 0,1  -> 1,0
45    // 1,0  -> 0,-1
46    // 0,-1 -> -1,0
47    direction = Point(direction.y, -direction.x);
48}
49
50bool Guard::is_looping(Point p, Point d) const
51{
52    PointMap::const_iterator it = visited.find(p);
53    if (it != visited.end() && it->second == d)
54        return true;
55    return false;
56}

Part 1: Predict the Guard’s Route#

The Guard moves in a 2D grid, turning right upon hitting an obstacle (# or O). The goal is to find the number of distinct positions visited before the Guard exits the map. Key Logic:

  • Create an unordered set (\(O(1)\) insert) for visited positions.

  • If using a vector, check for duplicates before inserting (\(O(n)\)).

  • Move the Guard until it exits the map.

  • On obstacle collision → turn right → retry movement.

  • Return visited.size() for number of distinct positions.

Part 2: Trap the Guard in a Loop#

You need to get the guard stuck in a loop by adding a single new obstruction. How many different positions could you choose for this obstruction?

Brute force solution would be to iterate over all possible position on the map. A better solution would be to only place obstacles on path that the guard travels.

  • Created an unordered_map to store each visited position with its corresponding direction. (visited.emplace(position, direction))

  • A loop occurs on visiting same position and have same direction as before

33using PointMap = std::unordered_map<Point, Point, PointHash>;
34...
35
36    PointMap guardVisitedPositions = g.getVisited();  // from part 1
37    for(const std::pair<Point, Point>& v: guardVisitedPositions)
38    {
39        int i(v.first.x), j(v.first.y);
40        
41        if(i==gx && j==gy) continue;
42        
43        map[i][j] = 'O';
44        g = Guard(Point(gx, gy), Guard::dirUp);
45        
46        while (g.canMove())
47        {
48            g.move(map);
49        }
50        if(g.stuckInLoop())
51        {
52            ++numObstacles;
53        }
54        map[i][j] = 'X';
55    }

Concepts Learned#

Operator Overload#

Example Operator Overloading for Point Class
 1struct Point
 2{
 3    int x,y;
 4    Point(int x, int y): x(x), y(y) {}
 5
 6    Point operator+(const Point& p)
 7    {
 8        return Point(x + p.x, y + p.y);
 9    }
10    bool operator==(const Point& p) const
11    {
12        return x == p.x && y == p.y;
13    }
14
15}
16std::ostream& operator<<(std::ostream& os, const Point& p)
17{
18    os << "(" << p.x << ", " << p.y << ")";
19    return os;
20}

const Correctness#

We bind type modifiers and qualifiers to the left

—Modern C, Jens Gustedt (Page 18)

  1. const X* p

    1const int* p;  // p points to a constant int (can't modify the value it points to)
    2int a = 5;
    3p = &a;  // okay, p can point to another int
    4*p = 10;  // error, can't modify the value of a through p
    
  2. X const* p

    1int const* p;  // Same as `const int* p`
    
  3. X* const p

    1int* const p = &a;  // p is a constant pointer, it always points to the same location
    2*p = 10;  // okay, the value of the object p points to can be modified
    3p = &b;  // error, can't change p to point to another object
    
  4. const X* const p

    1const int* const p = &a;  // p is a constant pointer to a constant int
    2*p = 10;  // error, can't modify the value of the object p points to
    3p = &b;  // error, can't change p to point to another object
    
  5. The const at the end of member function does not modify the state of object.

 1class Fred {
 2public:
 3  void inspect() const;   // This member promises NOT to change *this
 4  void mutate();          // This member function might change *this
 5};
 6void userCode(Fred& changeable, const Fred& unchangeable)
 7{
 8  changeable.inspect();   // Okay: doesn't change a changeable object
 9  changeable.mutate();    // Okay: changes a changeable object
10  unchangeable.inspect(); // Okay: doesn't change an unchangeable object
11  unchangeable.mutate();  // ERROR: attempt to change unchangeable object
12}
  1. const Point& Return type

 1class Guard
 2{
 3public:
 4    // Getter functions to access position and direction
 5    const Point& getPosition() const { return position; }
 6    const Point& getDirection() const { return direction; }
 7    /**
 8    By returning a constant reference (const Point&), you provide read-only access to the position and direction. 
 9    This ensures that the caller cannot modify the values.
10    */

Dangling References#

1const int& getTemp() {
2    int temp = 10;  // Local variable
3    return temp;  // Dangling reference (temp goes out of scope)
4}
5
6Point p1(1, 2);
7const int& a = p1.getX();
8p1 = Point(3, 4);  // a now refers to a destroyed object!

In C++, there is no built-in way to directly check if a reference is dangling

Unordered set#

Used Hash Table to store elements Steps to use unordered_set with a custom class:

  1. Define a hash function for your Point class.

  2. Override == operator to check for equality, as unordered_set uses it to compare elements.

  3. Use the custom hash function in unordered_set.

Example Code
 1struct Point
 2{
 3    int x,y;
 4    Point(int x, int y): x(x), y(y) {}
 5    Point() : x(0), y(0) {}
 6
 7    Point operator+(const Point& p) const
 8    {
 9        return Point(x + p.x, y + p.y);
10    }
11    bool operator==(const Point& p) const
12    {
13        return x == p.x && y == p.y;
14    }
15};
16struct HashPoint {
17    std::size_t operator()(const Point& p) const {
18        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
19    }
20};
21std::unordered_set<Point, HashPoint> visited;

For unordered_set of std::pair<Point, Point>

Code
 1// Define a custom hash for std::pair<Point, Point>
 2struct PairHash {
 3    size_t operator()(const std::pair<Point, Point>& pair) const {
 4        PointHash pointHash;
 5        // Combine the hash values of the two points in the pair
 6        return pointHash(pair.first) ^ (pointHash(pair.second) << 1);
 7    }
 8};
 9
10// Overload equality operator for std::pair<Point, Point>
11struct PairEqual {
12    bool operator()(const std::pair<Point, Point>& a, const std::pair<Point, Point>& b) const {
13        return a.first == b.first && a.second == b.second;
14    }
15};
16/** This can also be omitted
17The == operator for std::pair is already defined (since std::pair is a standard library type).
18It compares both elements of the pair for equality.
19*/
20
21std::unordered_set<std::pair<Point, Point>, PairHash, PairEqual> pointPairs;
22std::unordered_set<std::pair<Point, Point>, PairHash> point_pairs;
23
24// Aliases 
25using PointSet = std::unordered_set<Point, PointHash>;
26using PointPairSet = std::unordered_set<std::pair<Point, Point>, PairHash>;

Unordered Map#

 1std::unordered_map<Point, Point, PointHash> visited;
 2
 3// ### Check if value is in HashMap
 4std::map<char,int> mymap;
 5std::map<char,int>::iterator it;
 6
 7if (visited.find(current) != visited.end() && visited[current] == direction) {
 8    return true; 
 9}
10// If current is not already in the map, accessing visited[current] will insert a new entry
11
12auto it = visited.find(current);
13if (it != visited.end() && it->second == direction) {
14    return true; 
15}
16
17// ### Looping through HashMap
18for(const std::pair<Point, Point>& v: visited)
19{
20    cout << v.first << ":" << v.second << endl;
21}

Static Constant Members in C++ Classes#

  • static const is used for class-level constants, meaning these constants are shared across all instances of the class.

  • The static keyword ensures the constant is a class-wide (not instance-specific) member, while const ensures the values cannot be modified.

  • Static members must be defined outside the class, even if they’re const.

  • You cannot initialize static members within constructors. Integral types you can initialize inline at their declaration.

1class Guard{
2public:
3    static const Point dirUp, dirDown, dirLeft, dirRight;
4    static const int a = 4; // works
5};
6const Point Guard::dirUp(-1, 0);
7const Point Guard::dirDown(1, 0);
8const Point Guard::dirLeft(0, -1);
9const Point Guard::dirRight(0, 1);

References and Resources#


Day 7: Bridge Repair#

Solution Overview#

Part 1: Given a test value and a list of numbers, determine whether the numbers can be combined using the operators + (addition) and * (multiplication) to produce the test value

Operators are always evaluated left-to-rightnot according to precedence rules.

Part 2: Introduces a third operator: concatenation (||), alongside + and *.

Using a recursive call, with using one operator from left at each call.

 68using ll = long long;
 69
 70bool check_target1(const std::vector<int>& operands, int index, ll current_value, ll target)
 71{
 72    // reached end and found thr test value
 73    if(index==(int)operands.size()) return current_value == target;
 74
 75    // If current value is already greater than the target, no point in continuing
 76    // small improvement by short circuiting
 77    if(current_value > target) return false;
 78
 79    // subtle Bug! You only want to check for equality when list is exhausted
 80    //if(current_value == target) return true;
 81
 82    return check_target1(operands, index+1, current_value + operands[index], target) 
 83        || check_target1(operands, index+1, current_value * operands[index], target);
 84}
 85
 86bool check_target2(const std::vector<int>& operands, int index, ll current_value, ll target)
 87{
 88    if(index==(int)operands.size()) return current_value == target;
 89
 90    if(current_value > target) return false;
 91
 92    return check_target2(operands, index+1, current_value + operands[index], target) 
 93        || check_target2(operands, index+1, current_value * operands[index], target)
 94        || check_target2(operands, index+1, concat(current_value, operands[index]), target);
 95}
 96
 97void part(const std::vector<std::pair<ll, std::vector<int>>>& data)
 98{
 99    ll result = 0;
100    for(const std::pair<ll, std::vector<int>>& d: data)
101        if(check_target(d.second, 0, 1, d.first))
102}

The time complexity is \(O(n^2)\) for Part 1and \(O(n^3)\) for Part 2. While this works, it can be optimized.

Optimization#

With each recursive call the current_value increases. One way to optimize is to process the operations in reverse order, starting from the right, and try to undo the operations to see if the target value can be constructed. resulting in current value to be 0 at the end.

For example: Given 292: 11 6 16 20, the goal is to check if 292 can be made from these numbers. The left-to-right approach:

  • [11+6, 16, 20][17*16, 20][292] The right-to-left approach:

  • [11, 6, 16, 292-20][11, 6, 272/16][11, 17-6][11-11][0] To undo concatenation (||), the check_int_contains function is used to check if an integer is present in another integer.

134bool check_target1_v2(const std::vector<int>& operands, int index, ll target)
135{
136    if(index < 0) return target == 0 || target == 1;
137
138    if(target < 0) return false;
139
140    if(target % operands[index] == 0)
141    {
142        if(check_target1_v2(operands, index-1, target/operands[index]))
143            return true;
144        // Here too there can be a subtle Bug
145        // if you return check_target1_v2(i-1, target/operands[i])
146        // it fails to account for check_target1_v2(i-1, target-operands[i])
147        // example: 103304: 269 4 96 8
148    }
149
150    return check_target1_v2(operands, index-1, target-operands[index]);
151}
152bool check_int_contains(ll target, ll subint, ll& new_target)
153{
154    int lt, ls;
155    while(subint > 0)
156    {
157       lt = target % 10;
158       target /= 10;
159       ls = subint % 10;
160       subint /= 10;
161       if(lt != ls)
162       {
163           return false;
164       }
165    }
166    new_target = target;
167    return true;
168}
169
170bool check_target2_v2(const std::vector<int>& operands, int index, ll target)
171{
172    if(index < 0) return target == 0 || target == 1;
173
174    if(target < 0) return false;
175
176    if(target % operands[index] == 0)
177    {
178        if(check_target2_v2(operands, index-1, target/operands[index]))
179            return true;
180    }
181    
182    ll new_target;
183    if(check_int_contains(target, operands[index], new_target))
184    {
185        if(check_target2_v2(operands, index-1, new_target))
186            return true;
187    }
188
189    return check_target2_v2(operands, index-1, target-operands[index]);
190}

While the time complexity still remains the same, there is significant improvement in the time taken. {emphasize-lines=”5,7,9,11”}

[100%] Linking CXX executable day7.exe
Copying input.txt to input7.txt
[100%] Built target day7
Part 1: 6392012777720
Elapsed time: 2283 us
Part 2: 61561126043536
Elapsed time: 121022 us
Part 1 (Version 2): 6392012777720
Elapsed time: 1268 us
Part 2 (Version 2): 61561126043536
Elapsed time: 1498 us
[100%] Built target run7

Concepts Learned#

Subsets of an array/vector using bit manipulation#

  • For an array of size \(n\), there are \(2^n\) possible subsets.

  • Each subset corresponds to a binary number between 0 and \(2^n - 1\).

Example
 1// ### Problem: Find All Subsets That Sum to a Target Value
 2#include <iostream>
 3#include <vector>
 4using namespace std;
 5
 6void findSubsetsThatSumToTarget(vector<int>& nums, int target) {
 7    int n = nums.size();
 8    vector<vector<int>> result;
 9
10    // Iterate over all possible subsets
11    for (int mask = 0; mask < (1 << n); mask++) {
12        vector<int> subset;
13        int sum = 0;
14
15        // Generate the subset for the current bitmask
16        for (int i = 0; i < n; i++) {
17            if (mask & (1 << i)) { // If the i-th bit is 1, include nums[i]
18                subset.push_back(nums[i]);
19                sum += nums[i];
20            }
21        }
22
23        // Check if the subset sum equals the target
24        if (sum == target) {
25            result.push_back(subset);
26        }
27    }
28
29    // Print the result
30    cout << "Subsets that sum to " << target << ":\n";
31    for (auto& subset : result) {
32        cout << "[ ";
33        for (int num : subset) {
34            cout << num << " ";
35        }
36        cout << "]\n";
37    }
38}
39
40int main() {
41    vector<int> nums = {2, 3, 5};
42    int target = 5;
43    findSubsetsThatSumToTarget(nums, target);
44    return 0;
45}

References and Resources#


Day 8: Resonant Collinearity#

Solution Overview#

The grid is parsed into a dictionary (unordered_map<char, vector<Vec2<int>>>) with antenna labels as the key and a list of all the label’s positions as values.

Part 1: Find the Antinodes#

an antinode occurs at any point that is perfectly in line with two antennas of the same frequency - but only when one of the antennas is twice as far away as the other.

The words are complicated, see the diagram below. Basically, an antinode is a point that lies on the line extending from a pair of antennas at an equal distance beyond one of them

..........
...#......
..........
....a.....
..........
.....a....
..........
......#...
..........
..........

Logic:

  • iterate over each pair of antennas with the same frequency.

  • for each pair, compute the distance between the two antennas and calculate the potential antinode positions on either side of the pair.

  • Check if the antinodes lie within the grid boundaries, and if they do, add them to an unordered_set to ensure uniqueness.

128std::unordered_set<int> antinodes;
129for(const std::pair<const char, std::vector<V2>>& antenas: data)
130{
131    const std::vector<V2>& a = antenas.second;
132    for(int i = 0; i < static_cast<int>(a.size()); ++i)
133    {
134        for (int j = i + 1; j < static_cast<int>(a.size()); ++j)
135        {
136            // Calculate distance and antinode positions
137            V2 dist = a[i] - a[j];
138            V2 antinode1(a[i] + dist), antinode2(a[j] - dist);
139            
140            // Check if antinode positions are within bounds
141            if(antinode1.x < maxX && antinode1.y < maxY && antinode1.x >= 0 && antinode1.y >= 0)
142            {
143                antinodes.insert(antinode1.x * maxY + antinode1.y);
144            }
145            if(antinode2.x < maxX && antinode2.y < maxY && antinode2.x >= 0 && antinode2.y >= 0)
146            {
147                antinodes.insert(antinode2.x * maxY + antinode2.y);
148            }
149        }
150    }
151}

To track the unique antinode positions, we need to map each (x, y) coordinate to a unique integer value. This is done by using a simple mathematical formula: antinode1.x*maxY + antinode1.y

Part 2: I mean Harmonic Antinodes#

it turns out that an antinode occurs at any grid position exactly in line with at least two antennas of the same frequency, regardless of distance. This means that some of the new antinodes will occur at the position of each antenna (unless that antenna is the only one of its frequency).

Again, the words doesn’t explain much, see the diagram. Similar to Part 1, but instead of stopping at the first antinode, continue along the line of collinearity to count all antinodes.

T....#....
...T......
.T....#...
.........#
..#.......
..........
...#......
..........
....#.....
..........

Logic:

  • for each pair, compute the distance between the two antennas and calculate the potential antinode positions on either side of the pair.

  • expand the antinode positions by moving along the calculated distance in both directions until we reach the boundary of the grid.

176while(antinode1.x < maxX && antinode1.y < maxY && antinode1.x >= 0 && antinode1.y >= 0)
177{
178    antinodes.insert(antinode1.x * maxY + antinode1.y);
179    antinode1 += dist;  // Move along the distance
180}
181while(antinode2.x < maxX && antinode2.y < maxY && antinode2.x >= 0 && antinode2.y >= 0)
182{
183    antinodes.insert(antinode2.x * maxY + antinode2.y);
184    antinode2 -= dist;  // Move along the distance
185}

Concepts Learned#

Operator Overloading for custom class#

Operator overloading to work with the custom Vec2 class representing a 2D vector. This allows to simplify the code when working with positions and distances, such as adding, subtracting, or comparing positions.

Example
 1template <typename T>
 2struct Vec2
 3{
 4    T x, y;
 5    Vec2(T x_val, T y_val) : x(x_val), y(y_val) {}
 6};
 7
 8using V2 = Vec2<int>;
 9using mapV2 = std::unordered_map<char, std::vector<Vec2<int>>>;
10
11template <typename T> Vec2<T> constexpr operator+(Vec2<T> a, Vec2<T> b) { return {a.x + b.x, a.y + b.y}; }
12template <typename T> Vec2<T> constexpr operator-(Vec2<T> a, Vec2<T> b) { return {a.x - b.x, a.y - b.y}; }
13template <typename T> Vec2<T> constexpr operator-(Vec2<T> a) { return {-a.x, -a.y}; }
14template <typename T> Vec2<T> constexpr operator*(Vec2<T> a, Vec2<T> b) { return {a.x * b.x, a.y * b.y}; }
15template <typename T> Vec2<T> constexpr operator*(Vec2<T> a, T b) { return {a.x * b, a.y * b}; }
16template <typename T> Vec2<T> constexpr &operator+=(Vec2<T> &a, Vec2<T> b) { a = a + b; return a; }
17template <typename T> Vec2<T> constexpr &operator-=(Vec2<T> &a, Vec2<T> b) { a = a - b; return a; }
18template <typename T> bool constexpr operator==(Vec2<T> a, Vec2<T> b) { return a.x == b.x && a.y == b.y; }
19template <typename T>
20std::ostream& operator<<(std::ostream& os, const Vec2<T>& v)
21{
22    os << "(" << v.x << "," << v.y << ")";
23    return os;
24}
25
26template <typename T>
27std::ostream& operator<<(std::ostream& os, const std::vector<T>& v)
28{
29    os << "[";
30    for (auto i = v.begin(); i != v.end(); ++i) {
31        if (i != v.begin()) os << ", ";
32        os << *i;
33    }
34    os << "]";
35    return os;
36}

Constexpr#

Enable compile-time evaluation of simple functions, improving performance. # TODO: write in detail

this pointer#

# TODO

Unique Number for each element in 2D grid#

for \(arr[i][j]\) \(\rightarrow\) \(i\times Cols + j\), where \(Cols\) is number of columns.


This marks the second 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. Feel free to check out my solutions on GitHub.

Comments