Ceres Search: Advent of Code 2024 (Day 4)
The questions are getting more interesting as the days go on. While the earlier ones felt like a warm-up, today we’re tackling something more involved — a matrix problem. It’s called “Ceres Search,” where you help an elf find a word in a block of text.
You can read the full story here and find the code in my GitHub.
Processing the data
The input for this puzzle is a matrix of letters, which we need to store in a 2D vector for further processing. Here is the code that does this:
vector<vector<char>> word_search;
void loadData() {
string line = "";
ifstream ip("ip.txt");
if (ip.is_open()) {
while (getline(ip, line)) {
vector<char> row;
for(char c: line) {
row.push_back(c);
}
word_search.push_back(row);
}
ip.close();
}
}This function reads each line from the input file, converts it into a vector of characters, and adds it to the 2D vector word_search. At the end, word_search contains the entire grid, row by row.
Part 1: Search all the occurrences of the word
In essence, in your word_search input, you have to find all occurrences of the word XMAS in the matrix. The word can appear in any direction: horizontally, vertically, diagonally, backwards, or overlapping other words.
My Approach:
To solve this, I used a helper function, checkDirection, to search for the word in all directions. The plan is straightforward:
- From each character, attempt to find the word
XMASin eight possible directions
size_t LEN = 4;
char XMAS[5] = "XMAS";
bool checkDirection(int x, int y, int dx, int dy) {
int boundX = x + (LEN - 1) * dx;
int boundY = y + (LEN - 1) * dy;
if(boundX < 0 || boundY < 0 || boundX >= word_search.size() || boundY >= word_search[0].size()) {
return false;
}
for (int k = 0; k < LEN; k++) {
int nx = x + k * dx;
int ny = y + k * dy;
if (word_search[nx][ny] != XMAS[k]) {
return false;
}
}
return true;
}This function verifies if the word fits in the current direction, considering both matrix boundaries and character matches. The dx and dy values determine the direction:
(0, 1)for right,(0, -1)for left,(1, 0)for down,- and so on.
If the word goes out of bounds or a mismatch occurs, the function exits early.
To find all occurrences, iterate through the entire matrix and apply checkDirection in all eight directions for each cell.
int main() {
loadData();
int n = word_search.size();
int cnt = 0;
for (int i = 0; i < n; i++) {
int m = word_search[i].size();
for (int j = 0; j < m; j++) {
if (checkDirection(i, j, 0, 1)) cnt++; // right
if (checkDirection(i, j, 0, -1)) cnt++; // left
if (checkDirection(i, j, 1, 0)) cnt++; // down
if (checkDirection(i, j, -1, 0)) cnt++; // up
if (checkDirection(i, j, 1, 1)) cnt++; // diagonal right-down
if (checkDirection(i, j, -1, -1)) cnt++; // diagonal left-up
if (checkDirection(i, j, 1, -1)) cnt++; // diagonal left-down
if (checkDirection(i, j, -1, 1)) cnt++; // diagonal right-up
}
}
cout << "total count: " << cnt << endl;
return 0;
}The code above keeps a count of all valid occurrences of the word XMAS. At the end, cnt will hold the total count of XMASoccurrences in the matrix.
Part 2: Finding word crosses
The second part of the challenge steps up in complexity. Instead of finding the word XMAS, you now need to find two instances of MAS arranged in the shape of an X.
My Approach:
The task is to locate the character A and check if it serves as the center of an X-shaped arrangement of MAS. To do this, I implemented another helper function, checkMas, that verifies whether the A at a given position is part of a valid cross.
Here’s the function:
bool checkMas(int x, int y) {
// bounds
if(x - 1 < 0 || x + 1 >= word_search.size() || y - 1 < 0 || y + 1 >= word_search[0].size()) {
return false;
}
// M.S
// .A.
// S.M
if ((word_search[x - 1][y - 1] == 'M' && word_search[x + 1][y + 1] == 'S') &&
(word_search[x - 1][y + 1] == 'M' && word_search[x + 1][y - 1] == 'S')) {
return true;
}
// S.M
// .A.
// S.M
if ((word_search[x - 1][y - 1] == 'S' && word_search[x + 1][y + 1] == 'M') &&
(word_search[x - 1][y + 1] == 'S' && word_search[x + 1][y - 1] == 'M')) {
return true;
}
// S.S
// .A.
// M.M
if ((word_search[x - 1][y - 1] == 'S' && word_search[x + 1][y + 1] == 'M') &&
(word_search[x - 1][y + 1] == 'M' && word_search[x + 1][y - 1] == 'S')) {
return true;
}
// M.M
// .A.
// S.S
if ((word_search[x - 1][y - 1] == 'M' && word_search[x + 1][y + 1] == 'S') &&
(word_search[x - 1][y + 1] == 'S' && word_search[x + 1][y - 1] == 'M')) {
return true;
}
return false;
}The function starts by ensuring that the potential X-shape won’t go out of the matrix’s bounds. This avoids accessing invalid indices.
There are four possible valid patterns for the MAS arrangement, depending on the orientation of the M and S characters around the central A.
- Each pattern is explicitly checked with logical conditions.
- If any pattern matches, the function returns
true.
The conditional statements could be refactored for conciseness by grouping patterns or using pairs for symmetry. For now, I prioritized clarity.
To use this function, iterate over the matrix to find all occurrences of MAS crosses:
int main() {
loadData();
int cnt = 0;
// all part-1 code
for(int i = 0; i < word_search.size(); i++) {
for(int j = 0; j < word_search[0].size(); j++) {
if(word_search[i][j] == 'A' && checkMas(i, j)) cnt++;
}
}
cout << "count of cross MAX: " << cnt << endl;
return 0;
}For every cell containing A, the program checks whether it forms a valid MAS cross using checkMas
Conclusion
As you can see, today’s challenge is just the beginning of exploring 2D array or matrix-based traversals. The solutions I implemented are straightforward, brute-force methods that get the job done efficiently. In both cases combined, the program executed in under 200 ms, which I consider a success. 😁
If you’re looking to improve your matrix manipulation skills, I highly recommend trying out some common LeetCode problems below.
Feel free to check out the code on my GitHub for more details.
