Another Day, another AoC challenge. This one is based off a classic formula. We are given a block of text. We need to do a
simple word search. Find all examples of XMAS in the input text. Only problem is that we need to find every instance of XMAS.
These instances could be how we read them, but they could also be reversed, or going up or down the page, or even diagonally.
So long as the letters are in the correct order, and they don't deviate in direction, it's a valid instance.
Every year there is a challenge that is about the relationship of data in a grid. If there is a day to really learn from, it's this day. Let's start with a test.
#[cfg(test)]
mod tests {
use super::*;
use crate::DefaultOutputSignal;
#[test]
fn test_solve_part_one() {
let input = String::from(
r#"MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX"#,
);
let ceres_search = CeresSearch {
output_signal: Box::new(DefaultOutputSignal),
};
let result = ceres_search.solve_part_one(input);
assert_eq!(result, Ok("18".to_string()));
}
}
Now matrix problems where the relationship of data in a 2D or 3D grid has bitten me before. As such, I find it key to lay out the solution is a structured manor. As such I lean into though don't strictly follow single responsibility principle. This allows me to structure the code in a way that helps me understand what I am doing. Let's start with parsing the input.
pub fn part_one_process(&self, input: String) -> Result<String, ()> {
let input_as_lines = split_multiline_string(input);
let mut matrix = Vec::new();
input_as_lines.iter().for_each(|line| {
let row = line.chars().collect::<Vec<char>>();
matrix.push(row);
});
...
}
This is relatively straight forward. We take the input, and split it by line. We then split each line into a vector of chars,
and finally store it all as in another vector. This represents our matrix. We don't need to manipulate the data anymore.
Next I know I need to check for the word XMAS. To do this, I'm going to brute force it a bit. I am going to treat every index
as a possible starting point. for that I finish my first method with the following.
pub fn part_one_process(&self, input: String) -> Result<String, ()> {
...
let mut count = 0usize;
for i in 0..matrix.len() {
for j in 0..matrix[i].len() {
count += check_for_xmas(i, j, &matrix);
}
}
Ok(count.to_string())
}
This gives me the framework to iterate over the content. No getting confused here. I have also specified a function check_for_xmas
which takes in the two indexes and the matrix. This function will check if the word XMAS is present at the given index. We
don't care at this level about that functions implementation, only that it follows a contract. That contract is for the specified
index, it will return the total count of XMAS found to start at that index. In theory this method could return a count of 0 through to 8.
Let's jump into this function.
fn check_for_xmas(i: usize, j: usize, matrix: &Vec<Vec<char>>) -> usize {
let mut count = 0usize;
count += check_east(i, j, matrix);
count += check_west(i, j, matrix);
count += check_north(i, j, matrix);
count += check_south(i, j, matrix);
count += check_north_east(i, j, matrix);
count += check_south_east(i, j, matrix);
count += check_north_west(i, j, matrix);
count += check_south_west(i, j, matrix);
count
}
This simple function does what it says on the tin. It checks for xmas. Internally we can see it's calling 8 different methods,
each method checks a different direction. I have used compass points to name the methods for clarity. Each method will return 1 if
it finds XMAS in the given direction, and 0 if it does not.
Jumping into the first method, we can see the following.
fn check_east(i: usize, j: usize, matrix: &Vec<Vec<char>>) -> usize {
if j > matrix[0].len() - 4 {
0
} else {
if format!(
"{}{}{}{}",
matrix[i][j],
matrix[i][j + 1],
matrix[i][j + 2],
matrix[i][j + 3]
)
.eq("XMAS")
{
1
} else {
0
}
}
}
The first part is a check to see whether we can even check in this direction. In some languages, you could use a try-catch block
but for rust, any index out of bounds will be met with a panic. So we need to check if we are at the end of the row. The same
is applied to columns. If j is greater than the length of the row minus 4, or less than 3, we know it cannot be XMAS. for
i, we apply the same logic but to the column count. Then all we do is a bit of cherry-picking of chars, formulate a string, and
check if it's the string we care about. Then return a usize representing a boolean. Now replicate this 7 more times, for each
direction, and we are done with part 1. It's a little simple, and I'm sure there are more efficient ways to do this, but it's
also worth getting part 1 out of the way as fast as you can so that you give yourself time for part 2.
And so part 2. We have been told that we did part 1 wrong! it's not XMAS we are looking for, but MAS in a cross pattern.
This at first glance may seem a little more complex, but because we took the simple approach in part 1, we can easily adapt
to support part 2. Let's start with a test.
#[test]
fn test_solve_part_two() {
let input = String::from(
r#"MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX"#,
);
let ceres_search = CeresSearch {
output_signal: Box::new(DefaultOutputSignal),
};
let result = ceres_search.solve_part_two(input);
assert_eq!(result, Ok("9".to_string()));
}
For part 2 we don't need ta make any changes to our first function. Our parsing and iteration are still valid. We do need to
make some changes to our check_for_xmas function. We no longer have 8 checks to make, but 4. We need to check for 'MAS' in
north-east to south-west, south-west to north-east, south-east to north-west, and north-west to south-east. We can simplify this
even further to "north-east to south-west", and "south-east to north-west", as we can check for 'MAS' and 'SAM' in the same check.
fn check_for_xmas(i: usize, j: usize, matrix: &Vec<Vec<char>>) -> usize {
let mut count = 0usize;
count += check_north_east_to_south_west(i, j, matrix);
count += check_south_east_to_north_west(i, j, matrix);
if count == 2 {
1
} else {
0
}
}
We are expecting a count of 2 coming from our functions. Any less and we don't have a cross. Anymore, and we did something wrong. Finally, the implementation of our check. It's going to follow a very similar approach to part 1, but we have to adjust our validation.
fn check_north_east_to_south_west(i: usize, j: usize, matrix: &Vec<Vec<char>>) -> usize {
if i == 0 || i == matrix.len() - 1 {
0
} else if j == 0 || j == matrix[0].len() - 1 {
0
} else {
let string = format!(
"{}{}{}",
matrix[i - 1][j - 1],
matrix[i][j],
matrix[i + 1][j + 1]
);
if string.eq("MAS") || string.eq("SAM") {
1
} else {
0
}
}
}
Previously we only needed to check the bounds in one direction. This time because we are checking all 4 directions in one check, we must check all 4 bounds. We then cherry-pick the chars, form a string, and check if it's one of the two strings we care about. Do this again for the other direction, and we are done. Yet another "brute force" solution that in the grand scheme of things, gets the job done and well within a reasonable time frame.