Guard Gallivant: Advent of Code 2024 (Day 6)

Today’s challenge is about helping historians explore a lab without getting caught by guards. The lab map is shown as a grid, where guards and obstacles are marked. Your goal is to figure out all the places the guard visits during their patrol and find spots to place blocks that trap the guard in a loop. It’s a fun puzzle about matrix traversal and strategy.

Guard Gallivant

Read the full story here and you can find the working code in my GitHub.

Processing the data

To begin, the input data represents the lab as a grid of characters. Each character shows a part of the map: ^ marks the guard’s starting position, and # indicates obstacles. The code below loads the map into a 2D vector of characters labMap.

vector<vector<char>> labMap;
pair<int, int> guard(-1, -1);

void loadData() {
    string line = "";
    ifstream ip("ip.txt");
    int i = 0;

    if (ip.is_open()) {
        while (getline(ip, line)) {
            vector<char> row;
            int j = 0;
            for (char c : line) {
                row.push_back(c);
                if (c == '^') {
                    guard = make_pair(i, j);
                }
                j++;
            }
            labMap.push_back(row);
            i++;
        }
        ip.close();
    }
}

We also need the guard position. That is where we’ll start our traversal.

Part 1: Finding Guard Positions

In Part 1, the task is to determine all the unique positions the guard visits while following a strict patrol protocol. According to the rules,

• if the guard encounters an obstacle directly ahead, they turn right by 90 degrees
• Otherwise, they step forward

This continues until the guard exits the map’s boundaries.

My Approach:

• Use a while loop to simulate the guard’s movement and kept track of all visited positions in a set visited
• If the guard’s next step hits an obstacle, they change direction using a predefined list directions
• If the guard moves out of the map, the loop stops
• The size of the set gives the total number of unique positions visited

struct pair_hash {
    template <class T1, class T2>
    size_t operator()(const pair<T1, T2>& p) const {
        auto hash1 = hash<T1>{}(p.first);
        auto hash2 = hash<T2>{}(p.second);
        return hash1 ^ hash2;
    }
};
unordered_set<pair<int, int>, pair_hash> visited;

pair<int, int> directions[4] = {
    make_pair(-1, 0), // up
    make_pair(0, 1), // right
    make_pair(1, 0), // down
    make_pair(0, -1) // left
};

void checkGuardPath(int i, int j) {
    int direction = 0;
    while (true) {
        visited.insert(make_pair(i, j));
        int nextI = i + directions[direction].first;
        int nextJ = j + directions[direction].second;

        if (nextI < 0 || nextI >= labMap.size() || nextJ < 0 || nextJ >= labMap[0].size()) {
            break;
        }

        if (labMap[nextI][nextJ] == '#') {
            direction = (direction + 1) % 4;
        } else {
            i = nextI;
            j = nextJ;
        }
    }
}

Note: Here, I used a custom hash function (pair_hash) to allow the unordered_set to store pair<int, int> elements, because the default hash function doesn't know how to handle pairs of integers. The custom hash combines the hashes of both elements in the pair, ensuring that each unique pair has a unique hash value in the set.

The size of the visited set will be our answer.

int main() {

    loadData();
    checkGuardPath(guard.first, guard.second);

    cout << "total positions: " << visited.size() << endl;

    return 0;
}

Part 2: Get the Guard Stuck in a Loop

Here, the task is to figure out how many places you can add a single obstacle to trap the guard in a loop.

My Approach:

• Loop through all the positions where the guard can roam. For each position, I place an obstacle and check if it causes the guard to get stuck in a loop
• The guard is stuck in a loop if they revisit the same position with the same direction

To detect loops, I used a tuple to track the guard’s position and direction — this was my first time using tuples in C++ after frequently using them in Python.

Lets make a function to check if a guard will enter a loop if the obstruction at a particular position (i, j).

struct tuple_hash {
    template <class T1, class T2, class T3>
    size_t operator()(const std::tuple<T1, T2, T3>& p) const {
        auto hash1 = std::hash<T1>{}(std::get<0>(p));
        auto hash2 = std::hash<T2>{}(std::get<1>(p));
        auto hash3 = std::hash<T3>{}(std::get<2>(p));
        return hash1 ^ (hash2 << 1) ^ (hash3 << 2);
    }
};

bool checkLoop(int oi, int oj) {
    unordered_set<tuple<int, int, int>, tuple_hash> currVisited;

    if (labMap[oi][oj] == '#') {
        return false;
    }

    labMap[oi][oj] = '#';
    int i = guard.first;
    int j = guard.second;
    int direction = 0;

    while (true) {
        if (currVisited.find(make_tuple(i, j, direction)) != currVisited.end()) {
            labMap[oi][oj] = '.';
            return true;
        }

        currVisited.insert(make_tuple(i, j, direction));

        int nextI = i + directions[direction].first;
        int nextJ = j + directions[direction].second;

        if (nextI < 0 || nextI >= labMap.size() || nextJ < 0 || nextJ >= labMap[0].size()) {
            labMap[oi][oj] = '.';
            return false;
        }

        if (labMap[nextI][nextJ] == '#') {
            direction = (direction + 1) % 4;
        } else {
            i = nextI;
            j = nextJ;
        }
    }
}

In the above code, we are placing the new obstruction at oi, oj and checking if there will be any loop in his path. Finally, the program loops through all valid positions, checks for loops, and counts them. Though this approach takes time, it ensures accurate results.

int main() {
    loadData();
    checkGuardPath(guard.first, guard.second);

    cout << "total positions visited: " << visited.size() << endl;

    int cnt = 0;
    for (const auto& t : visited) {
        if (t.first == guard.first && t.second == guard.second) {
            continue;
        }

        if (checkLoop(t.first, t.second)) {
            cnt++;
        }
    }

    cout << "total positions for new obstruction: " << cnt << endl;

    return 0;
}

Placing obstacles in 5534 positions and traversing every time through the grid will take some time, but will give us the correct answer. 🙂

Conclusion

This problem showcases how matrix traversal can be used to simulate real-world patterns, like a guard following a specific path based on obstacles. This is why I try to solve Advent of Code every year. You can try to further optimise the code but this gave me 2 stars of the day. Things I learned today:

• Using storing custom data types in unordered_set using custom hash function
• How to use tuple in C++

Below are some LeetCode questions you can try:

• 36. Valid Sudoku
• 37. Sudoku Solver