Advent of Code 2024 - Day 4

Ceres Search

December 19th, 2024

Tags:Advent of CodeC++

This is where I thought things were starting to get interesting. It took a little bit more thinking and some tinkering to get the solution right, but it worked out in the end.

# Part 1

This is basically just a word search at the most basic level. We have some X by Y grid of letters containing only Xs, Ms, As, and Ss, and we have to find the number of occurrences of the word “XMAS” in the grid. The word can be found in any direction, backwards, and can even overlap with other occurrences. The following is an example of a grid:

1MMMSXXMASM
2MSAMXMSMSA
3AMXSXMAAMM
4MSAMASMSMX
5XMASAMXAMM
6XXAMMXXAMA
7SMSMSASXSS
8SAXAMASAAA
9MAMMMXMMMM
10MXMXAXMASX

And here's the same thing but letters not involved with any XMASes are replaced with periods. There are 18 occurrences total in this example:

1....XXMAS.
2.SAMXMS...
3...S..A...
4..A.A.MS.X
5XMASAMX.MM
6X.....XA.A
7S.S.S.S.SS
8.A.A.A.A.A
9..M.M.M.MM
10.X.X.XMASX

It took a little bit for me to figure this out. I knew that the most straightforward method would be to use some sort of graph data structure to represent the grid and then search for all occurrences, but figuring out the specific algorithm was a little tricky. However, I realized that:

All the instances start with X, meaning we can search for Xs only initially to find the possible word roots.
From there, the direction of possible valid instances is set by all adjacent Ms that neighbour all root Xs.
Finally, we know what neighbours must come sequentially, so we can just search down that direction to determine if we found a valid instance of XMAS.

To implement this, I created a class to represent a node. Within each class is a hash table of pointers to all adjacent nodes, where the key is the direction of the adjacent node relative to the current node.

1enum class Direction { N, NE, E, SE, S, SW, W, NW };
2
3struct Node 
4{
5  char letter;
6  std::unordered_map<Direction, Node*> neighbours;
7  Node(char letter) : letter(letter) 
8  {
9    for (Direction dir = Direction::N; dir <= Direction::NW; dir = static_cast<Direction>(static_cast<int>(dir) + 1))
10    {
11      neighbours[dir] = nullptr;
12    }
13  }
14};

We can then read in the file to assemble the graph—first by creating all the nodes, then linking them together by assigning the appropriate pointers.

1std::vector<Node*> build_graph(std::ifstream& file)
2{
3  std::string line;
4  std::vector<std::vector<Node*>> temp_grid; // store positional info
5  std::unordered_map<int, Node*> node_map; // quick access to nodes
6  std::vector<Node*> nodes; // the actual return vector
7  int node_id = 0;
8
9  int row = 0;
10  while (std::getline(file, line))
11  {
12    std::vector<Node*> row_nodes;
13    std::istringstream iss(line);
14    char letter;
15    int col = 0;
16    while (iss >> letter)
17    {
18      Node* node = new Node(letter);
19      row_nodes.push_back(node);
20      node_map[node_id++] = node;
21      nodes.push_back(node);
22      ++col;
23    }
24    temp_grid.push_back(row_nodes);
25    ++row;
26  }
27
28  int num_rows = temp_grid.size();
29  int num_cols = temp_grid.at(0).size();
30  for (int i = 0; i < num_rows; ++i)
31  {
32    for (int j = 0; j < num_cols; ++j)
33    {
34      int id = i * num_cols + j;
35      if (i > 0) node_map.at(id)->neighbours.at(Direction::N) = node_map.at(id - num_cols);
36      if (i > 0 && j < num_cols - 1) node_map.at(id)->neighbours.at(Direction::NE) = node_map.at(id - num_cols + 1);
37      if (j < num_cols - 1) node_map.at(id)->neighbours.at(Direction::E) = node_map.at(id + 1);
38      if (i < num_rows - 1 && j < num_cols - 1) node_map.at(id)->neighbours.at(Direction::SE) = node_map.at(id + num_cols + 1);
39      if (i < num_rows - 1) node_map.at(id)->neighbours.at(Direction::S) = node_map.at(id + num_cols);
40      if (i < num_rows - 1 && j > 0) node_map.at(id)->neighbours.at(Direction::SW) = node_map.at(id + num_cols - 1);
41      if (j > 0) node_map.at(id)->neighbours.at(Direction::W) = node_map.at(id - 1);
42      if (i > 0 && j > 0) node_map.at(id)->neighbours.at(Direction::NW) = node_map.at(id - num_cols - 1);
43    }
44  }
45
46  temp_grid.clear();
47  node_map.clear();
48  return nodes;
49}

After that, implementation of the search algorithm using a semi-breadth first search was pretty straight forward. We search for all Xs, then all neighbouring Ms of those Xs (keeping track of the direction). Then, we look down all possible directions (based on the neighbours we found) to see if we have a valid instance of XMAS.

1int search_for_xmas(Node* root)
2{
3  int num_xmases = 0;
4
5  std::queue<std::pair<Node*, Direction>> search_queue;
6  for (Direction dir = Direction::N; dir <= Direction::NW; dir = static_cast<Direction>(static_cast<int>(dir) + 1))
7  {
8    if (root->neighbours.at(dir) != nullptr && root->neighbours.at(dir)->letter == 'M')
9    {
10      search_queue.push({ root->neighbours.at(dir), dir });
11    }
12  }
13
14  while (!search_queue.empty())
15  {
16    auto [node, dir] = search_queue.front();
17    search_queue.pop();
18    auto letterA_node = node->neighbours.at(dir);
19    auto letterS_node = letterA_node != nullptr ? letterA_node->neighbours.at(dir) : nullptr;
20
21    if (letterA_node != nullptr && letterA_node->letter == 'A' && letterS_node != nullptr && letterS_node->letter == 'S')
22    {
23      ++num_xmases;
24    }
25  }
26
27  return num_xmases;
28}

The result is this final implementation:

1#include <bits/stdc++.h>
2
3enum class Direction { N, NE, E, SE, S, SW, W, NW };
4
5struct Node 
6{
7  char letter;
8  std::unordered_map<Direction, Node*> neighbours;
9  Node(char letter) : letter(letter) 
10  {
11    for (Direction dir = Direction::N; dir <= Direction::NW; dir = static_cast<Direction>(static_cast<int>(dir) + 1))
12    {
13      neighbours[dir] = nullptr;
14    }
15  }
16};
17
18std::vector<Node*> build_graph(std::ifstream& file)
19{
20  std::string line;
21  std::vector<std::vector<Node*>> temp_grid; // store positional info
22  std::unordered_map<int, Node*> node_map; // quick access to nodes
23  std::vector<Node*> nodes; // the actual return vector
24  int node_id = 0;
25
26  int row = 0;
27  while (std::getline(file, line))
28  {
29    std::vector<Node*> row_nodes;
30    std::istringstream iss(line);
31    char letter;
32    int col = 0;
33    while (iss >> letter)
34    {
35      Node* node = new Node(letter);
36      row_nodes.push_back(node);
37      node_map[node_id++] = node;
38      nodes.push_back(node);
39      ++col;
40    }
41    temp_grid.push_back(row_nodes);
42    ++row;
43  }
44
45  int num_rows = temp_grid.size();
46  int num_cols = temp_grid.at(0).size();
47  for (int i = 0; i < num_rows; ++i)
48  {
49    for (int j = 0; j < num_cols; ++j)
50    {
51      int id = i * num_cols + j;
52      if (i > 0) node_map.at(id)->neighbours.at(Direction::N) = node_map.at(id - num_cols);
53      if (i > 0 && j < num_cols - 1) node_map.at(id)->neighbours.at(Direction::NE) = node_map.at(id - num_cols + 1);
54      if (j < num_cols - 1) node_map.at(id)->neighbours.at(Direction::E) = node_map.at(id + 1);
55      if (i < num_rows - 1 && j < num_cols - 1) node_map.at(id)->neighbours.at(Direction::SE) = node_map.at(id + num_cols + 1);
56      if (i < num_rows - 1) node_map.at(id)->neighbours.at(Direction::S) = node_map.at(id + num_cols);
57      if (i < num_rows - 1 && j > 0) node_map.at(id)->neighbours.at(Direction::SW) = node_map.at(id + num_cols - 1);
58      if (j > 0) node_map.at(id)->neighbours.at(Direction::W) = node_map.at(id - 1);
59      if (i > 0 && j > 0) node_map.at(id)->neighbours.at(Direction::NW) = node_map.at(id - num_cols - 1);
60    }
61  }
62
63  temp_grid.clear();
64  node_map.clear();
65  return nodes;
66}
67
68int search_for_xmas(Node* root)
69{
70  int num_xmases = 0;
71
72  std::queue<std::pair<Node*, Direction>> search_queue;
73  for (Direction dir = Direction::N; dir <= Direction::NW; dir = static_cast<Direction>(static_cast<int>(dir) + 1))
74  {
75    if (root->neighbours.at(dir) != nullptr && root->neighbours.at(dir)->letter == 'M')
76    {
77      search_queue.push({ root->neighbours.at(dir), dir });
78    }
79  }
80
81  while (!search_queue.empty())
82  {
83    auto [node, dir] = search_queue.front();
84    search_queue.pop();
85    auto letterA_node = node->neighbours.at(dir);
86    auto letterS_node = letterA_node != nullptr ? letterA_node->neighbours.at(dir) : nullptr;
87
88    if (letterA_node != nullptr && letterA_node->letter == 'A' && letterS_node != nullptr && letterS_node->letter == 'S')
89    {
90      ++num_xmases;
91    }
92  }
93
94  return num_xmases;
95}
96
97int main()
98{
99  std::ifstream input("day4_input.txt");
100  auto nodes = build_graph(input);
101  auto roots = nodes | std::views::filter([&](Node* node) { return node->letter == 'X'; });
102  auto root_nodes = std::vector<Node*>(roots.begin(), roots.end());
103
104  int total_xmases = 0;
105  for (auto root : root_nodes)
106  {
107    total_xmases += search_for_xmas(root);
108  }
109
110  std::cout << "all xmases: " << total_xmases << std::endl;
111
112  input.close();
113  root_nodes.clear();
114  nodes.clear();
115  return 0;
116}

# Part 2

This second part gets a little trickier as now we're trying to look for “X-MAS”es instead, the distinction being that an X-MAS is an X made of two MASes, like shown below:

1M.S
2.A.
3M.S

We can use a similar line of reasoning as before to solve this part. We search for all the As as the roots this time (since there's always an A in the middle of an X-MAS), then look for neighbouring Ms. From there, each neighbouring M must have an opposing S relative to the root A. If a given root has two such pairs, it's a valid X-MAS. This leads to the following modified search function:

1int search_for_x_mases(Node* root)
2{
3  std::queue<std::pair<Node*, Direction>> search_queue;
4  std::vector<Direction> valid_m_directions = { Direction::NE, Direction::SE, Direction::SW, Direction::NW };
5  for (auto const dir : valid_m_directions)
6  {
7    if (root->neighbours.at(dir) && root->neighbours.at(dir)->letter == 'M')
8    {
9      search_queue.push(std::make_pair(root->neighbours.at(dir), dir));
10    }
11  }
12
13  if (search_queue.size() < 2)
14  {
15    return 0;
16  }
17
18  while (!search_queue.empty())
19  {
20    auto [node, dir] = search_queue.front();
21    search_queue.pop();
22    auto opposing_neighbour_dir = [&](){
23      switch(dir){
24        case Direction::NE:
25          return Direction::SW;
26          break;
27        case Direction::SE:
28          return Direction::NW;
29          break;
30        case Direction::SW:
31          return Direction::NE;
32          break;
33        case Direction::NW:
34          return Direction::SE;
35          break;
36        default:
37          // smth terribly bad happened
38          throw std::runtime_error("uh oh");
39      }
40    }();
41    auto opposing_neighbour = root->neighbours.at(opposing_neighbour_dir);
42    if (opposing_neighbour == nullptr || opposing_neighbour->letter != 'S') {
43      return 0;
44    }
45  }
46
47  return 1;
48}

And the final implementation for part 2:

1#include <bits/stdc++.h>
2
3enum class Direction { N, NE, E, SE, S, SW, W, NW };
4
5struct Node 
6{
7  char letter;
8  std::unordered_map<Direction, Node*> neighbours;
9  Node(char letter) : letter(letter) 
10  {
11    for (Direction dir = Direction::N; dir <= Direction::NW; dir = static_cast<Direction>(static_cast<int>(dir) + 1))
12    {
13      neighbours[dir] = nullptr;
14    }
15  }
16};
17
18std::vector<Node*> build_graph(std::ifstream& file)
19{
20  std::string line;
21  std::vector<std::vector<Node*>> temp_grid; // store positional info
22  std::unordered_map<int, Node*> node_map; // quick access to nodes
23  std::vector<Node*> nodes; // the actual return vector
24  int node_id = 0;
25
26  int row = 0;
27  while (std::getline(file, line))
28  {
29    std::vector<Node*> row_nodes;
30    std::istringstream iss(line);
31    char letter;
32    int col = 0;
33    while (iss >> letter)
34    {
35      Node* node = new Node(letter);
36      row_nodes.push_back(node);
37      node_map[node_id++] = node;
38      nodes.push_back(node);
39      ++col;
40    }
41    temp_grid.push_back(row_nodes);
42    ++row;
43  }
44
45  int num_rows = temp_grid.size();
46  int num_cols = temp_grid.at(0).size();
47  for (int i = 0; i < num_rows; ++i)
48  {
49    for (int j = 0; j < num_cols; ++j)
50    {
51      int id = i * num_cols + j;
52      if (i > 0) node_map.at(id)->neighbours.at(Direction::N) = node_map.at(id - num_cols);
53      if (i > 0 && j < num_cols - 1) node_map.at(id)->neighbours.at(Direction::NE) = node_map.at(id - num_cols + 1);
54      if (j < num_cols - 1) node_map.at(id)->neighbours.at(Direction::E) = node_map.at(id + 1);
55      if (i < num_rows - 1 && j < num_cols - 1) node_map.at(id)->neighbours.at(Direction::SE) = node_map.at(id + num_cols + 1);
56      if (i < num_rows - 1) node_map.at(id)->neighbours.at(Direction::S) = node_map.at(id + num_cols);
57      if (i < num_rows - 1 && j > 0) node_map.at(id)->neighbours.at(Direction::SW) = node_map.at(id + num_cols - 1);
58      if (j > 0) node_map.at(id)->neighbours.at(Direction::W) = node_map.at(id - 1);
59      if (i > 0 && j > 0) node_map.at(id)->neighbours.at(Direction::NW) = node_map.at(id - num_cols - 1);
60    }
61  }
62
63  temp_grid.clear();
64  node_map.clear();
65  return nodes;
66}
67
68int search_for_x_mases(Node* root)
69{
70  std::queue<std::pair<Node*, Direction>> search_queue;
71  std::vector<Direction> valid_m_directions = { Direction::NE, Direction::SE, Direction::SW, Direction::NW };
72  for (auto const dir : valid_m_directions)
73  {
74    if (root->neighbours.at(dir) && root->neighbours.at(dir)->letter == 'M')
75    {
76      search_queue.push(std::make_pair(root->neighbours.at(dir), dir));
77    }
78  }
79
80  if (search_queue.size() < 2)
81  {
82    return 0;
83  }
84
85  while (!search_queue.empty())
86  {
87    auto [node, dir] = search_queue.front();
88    search_queue.pop();
89    auto opposing_neighbour_dir = [&](){
90      switch(dir){
91        case Direction::NE:
92          return Direction::SW;
93          break;
94        case Direction::SE:
95          return Direction::NW;
96          break;
97        case Direction::SW:
98          return Direction::NE;
99          break;
100        case Direction::NW:
101          return Direction::SE;
102          break;
103        default:
104          // smth terribly bad happened
105          throw std::runtime_error("uh oh");
106      }
107    }();
108    auto opposing_neighbour = root->neighbours.at(opposing_neighbour_dir);
109    if (opposing_neighbour == nullptr || opposing_neighbour->letter != 'S') {
110      return 0;
111    }
112  }
113
114  return 1;
115}
116
117int main()
118{
119  std::ifstream input("day4_input.txt");
120  auto nodes = build_graph(input);
121  auto roots = nodes | std::views::filter([&](Node* node) { return node->letter == 'A'; });
122  auto root_nodes = std::vector<Node*>(roots.begin(), roots.end());
123
124  int total_xmases = 0;
125  for (auto root : root_nodes)
126  {
127    total_xmases += search_for_x_mases(root);
128  }
129
130  std::cout << "all xmases: " << total_xmases << std::endl;
131
132  input.close();
133  root_nodes.clear();
134  nodes.clear();
135  return 0;
136}

Definitely starting to get a little trickier now, but I'm still enjoying the challenge. There's some kind of charm with these particular questions that you don't get with LeetCode problems and the like and I wish I had done this sooner. Here's hoping that I fair just as well with the other problems.