Attention!

• Check Advent of Code for the full challenge details. They created everything we need to know about the challenge - give them your support.

• My solutions are not ‘the’ solutions - I target one of the possible solutions. They might not be the most efficient, but they are a way to solve the problem. I do not plan to spend too much time doing the challenges.

• Every challenge = different language - just for fun and learning.

• I do not include the input data, but you can find it on the Advent of Code website or in the repository of the code.

---

Day 4. Ceres monitoring station. This time, my task is to help an elf search for the word XMAS hidden in a grid of letters. The challenge includes both horizontal and vertical word searches, and even diagonal and backward searches. Part Two introduces a twist, where I need to search for the X-MAS pattern in a more intricate form.

Let’s break down the problem and dive into my solution in C++.

---

Part One: Word Search for XMAS

I was given a grid, and the goal is to find how many times the word XMAS appears in various orientations. These orientations include:

• Horizontal (left to right)
• Vertical (top to bottom)
• Diagonal (from top-left to bottom-right, and bottom-left to top-right)
• Backward (all of the above, but reversed)

I need to find every instance of the word XMAS that fits any of these orientations. The task is to count all these occurrences within the grid.

---

To tackle Part One, I wrote a function that loops through each position in the grid, checking all possible directions (horizontal, vertical, diagonal, and backward) for the word XMAS. I also account for grid boundaries, ensuring that the word doesn’t extend outside the grid.

Code for Part One

The part_one function iterates over every possible position in the grid and checks all four directions for occurrences of XMAS.

// main.cpp
int part_one(const vector<string>& grid) {
    const string target = "XMAS";
    vector<pair<int, int>> directions = {
        {0, 1}, {1, 0}, {1, 1}, {1, -1}
    };
    int count = 0;
    for (int row = 0; row < grid.size(); row++)
    for (int col = 0; col < grid[0].size(); col++)
    for (const auto& dir : directions) {
        if (grid_lookup(grid, row, col, target, dir)) {
            count++;
        }
        const auto& rev_dir = make_pair(-dir.first, -dir.second);
        if (grid_lookup(grid, row, col, target, rev_dir)) {
            count++;
        }
    }
    return count;
}

The grid_lookup function checks whether the word XMAS appears starting at a given position (row, col) and follows a specific direction (horizontal, vertical, or diagonal).

// main.cpp
bool grid_lookup(
    const vector<string>& grid,
    int row,
    int col,
    const string& target,
    const pair<int, int>& direction
) {
    for (int i = 0; i < target.length(); i++) {
        int new_row = row + i * direction.first;
        int new_col = col + i * direction.second;
        if (new_row < 0 || new_row >= grid.size()) return false;
        if (new_col < 0 || new_col >= grid[0].size()) return false;
        if (grid[new_row][new_col] != target[i]) return false;
    }
    return true;
}

---

Part Two: Searching for X-MAS Shape

In Part Two, the task changes slightly. Instead of searching for the full word XMAS, I now need to look for the X-MAS shape. Specifically, I’m looking for the pattern:

M.S
.A.
M.S

This pattern can also appear in reverse, and I need to identify all the occurrences of it within the grid.

The trick here is that the pattern can be found in any rotation (normal or reversed). I use a method that checks the four points forming the “X” shape at every position in the grid, ensuring the correct letters form the pattern.

Code for Part Two

// main.cpp
int part_two(const vector<string>& grid) {
    int count = 0;
    vector<pair<int, int>> directions = { {-1, -1}, {1, 1} };
    for (int row = 1; row < grid.size() - 1; row++)
    for (int col = 1; col < grid[0].size() - 1; col++) {
        if (grid[row][col] != 'A') continue;
        // |a|   |b|
        // | |'A'| |
        // |c|   |d|
        char a = grid[row - 1][col - 1];
        char b = grid[row + 1][col + 1];
        char c = grid[row + 1][col - 1];
        char d = grid[row - 1][col + 1];
        if ((a == 'M' && b == 'S' || a == 'S' && b == 'M')
            && (c == 'M' && d == 'S' || c == 'S' && d == 'M')) {
            count++;
        }
    }
    return count;
}

Here, I check every possible center (the ‘A’ in the middle of the shape) and verify whether the surrounding characters match the “M.S” pattern both forwards and backwards.

---

Final Solution Code

The final solution code can be found on my GitHub repository.

If you like the content, don’t forget to give it a star ⭐.

• Time Complexity:
  • Part One: O(nm4), where n and m are the grid dimensions. I check each position and test up to four directions for each starting point.
  • Part Two: O(n*m), where I check the surrounding letters at each position for the X-MAS shape.
• Space Complexity: The space complexity is O(n) due to storing the input data in a buffer.
  • O(n*m), where n and m are the grid dimensions (both cases).

---

Conclusion

The Day 4 challenge took me through the complexities of word search puzzles, with Part One requiring a straightforward approach to finding all instances of XMAS and Part Two presenting a more intricate challenge with the X-MAS shape. The second part, though more complex… looks easier to solve than the first one (fact is, the solution it is not generic at all and that’s the reason).

Stay tuned for the next day’s challenge! I’m going to use PHP for Day 5.