Advent of Code presents an opportunity. Whether it’s a chance to learn something new, test and reinforce your abilities, or get smacked in the face by a problem that should have been simple. Day 2 may be a walk in the park for some, but any day can trip you up for one reason or another. Note to self: Heed this warning.
Day 2 starts with a set of reports. These reports are broken up into separate lines and represent levels. Each report may or may not be considered safe. There are two rules to make a report safe. The first is that each report must consist of either ascending or descending levels. The second rule states that there must be at least 1 level difference and at most 3. Easy enough. Let’s write a test.
#[cfg(test)]
mod tests {
use super::*;
use crate::DefaultOutputSignal;
#[test]
fn test_solve_part_one() {
let input = String::from(
r#"7 6 4 2 1
1 2 7 8 9
9 7 6 2 1
1 3 2 4 5
8 6 4 4 1
1 3 6 7 9"#,
);
let red_nosed = RedNosed {
output_signal: Box::new(DefaultOutputSignal),
};
let result = red_nosed.solve_part_one(input);
assert_eq!(result, Ok("2".to_string()));
}
}
Now we know these two rules. We could go straight in and manually implement the check for descending or ascending levels, but there are some simple tricks we can use. We can sort a duplicate list and compare it to the original. If they are the same, then we know the direction. Do the same between an ascending and a descending list, and we can determine if the list is safe. Almost. There is one last edge case to consider for direction. If the list has two values that are the same, then it’s not a valid report either. For that, we can clone and deduplicate the list and compare the length. If it’s the same, then we know there are no duplicates.
Finally, we need to know the difference between each level, or at least the maximum difference. There is likely a smarter way to do this, but for now, we can just iterate over each report and take note of the maximum difference. We then sum the successful reports for our answer. Let’s write the code to make this test pass.
mod part_one {
use crate::utils::split_multiline_string;
use crate::y2024::day2::RedNosed;
impl RedNosed {
pub fn part_one_process(&self, input: String) -> Result<String, ()> {
let input_as_lines = split_multiline_string(input);
let safe_count = input_as_lines
.iter()
.map(|line| {
line.trim()
.split(" ")
.map(|x| x.parse::<i32>().unwrap())
.collect()
})
.filter(|row: &Vec<i32>| {
let mut sortAsc = row.clone();
sortAsc.sort();
let mut sortDecs = row.clone();
sortDecs.sort_by(|a, b| b.cmp(a));
self.output_signal.write(&format!("Input: {:?}", *row));
self.output_signal.write(&format!("Acc: {:?}", sortAsc));
self.output_signal.write(&format!("Desc: {:?}", sortDecs));
let mut dedup = row.clone();
dedup.dedup();
let mut row_result =
(row.eq(&sortAsc) || row.eq(&sortDecs)) && dedup.len() == row.len();
if row_result {
let mut last = row[0];
for i in 1..row.len() {
if num::abs(last - row[i]) > 3 {
row_result = false;
break;
} else {
last = row[i];
}
}
}
row_result
})
.count();
Ok(safe_count.to_string())
}
}
}
This is not the cleanest solution. Generally, I would argue against the use of break in loops, and if this was production code, I would break this up into smaller functions. But for now, this is a simple solution that works. We can now move on to part two.
And this is where I stumbled on day 2. The rules have changed. One bad level does not ruin a report. If we have numbers 1, 3, 4, 9, 6, 8, we can consider this a valid report as it’s ascending, and the 9 can be ignored. If there is more than one bad level, or if the transition is something like 3, 4, 8, 9, 10, then it’s a bad report. Not a significant change, so let’s jump into a test.
#[cfg(test)]
mod tests {
...
#[test]
fn test_solve_part_two() {
let input = String::from(
r#"7 6 4 2 1
1 2 7 8 9
9 7 6 2 1
1 3 2 4 5
8 6 4 4 1
1 3 6 7 9"#,
);
let red_nosed = RedNosed {
output_signal: Box::new(DefaultOutputSignal),
};
let result = red_nosed.solve_part_two(input);
assert_eq!(result, Ok("4".to_string()));
}
}
Now we have a test. Where did I stumble? There was a simple solution to this second part. We will get to that shortly. But I jumped on the first idea I had. If one level is bad, then that level could be one of the following cases:
Having solved the first part with ease, I thought, how could I extend that solution to account for these cases? How about we sort the list as we did before, and then diff the lists? If we get a difference of 1, then we know it’s valid! If we get a difference of 0 and the deduplication difference is 1 or 2, then we know it’s a valid report. If we get a difference of 2 or more combined between the deduplication and the diff, then it’s a bad report. So what went wrong?
I wanted to make use of the tools Rust provides us. As such, I went hunting for a function that could diff the two vectors. I stumbled upon a thread that suggested using a function called symmetric_difference. The problem is that this function will happily tell you what is different between the two sets, but sets are unordered. These mistakes happen in the heat of the moment. We can easily rush into a solution without fully thinking it through. The logic was sound, but the implementation was flawed. After spending roughly an hour on this problem before realising my mistake, I realised a simpler solution was staring me in the face the whole time.
We proved with part 1 that we can use sorted lists to determine if a report is valid. What if that’s almost all we need to do for part 2? What if we iterate over each level in the report, temporarily remove it, and then check if the report is valid? Simple! But first, let’s refactor our previous solution, pulling our primary logic into a helper function.
mod part_two {
use crate::utils::split_multiline_string;
use crate::y2024::day2::RedNosed;
impl RedNosed {
...
fn is_valid_row(&self, row: &Vec<i32>) -> bool {
let mut sortAsc = row.clone();
sortAsc.sort();
let mut sortDecs = row.clone();
sortDecs.sort_by(|a, b| b.cmp(a));
self.output_signal.write(&format!("Input: {:?}", *row));
self.output_signal.write(&format!("Acc: {:?}", sortAsc));
self.output_signal.write(&format!("Desc: {:?}", sortDecs));
let mut dedup = row.clone();
dedup.dedup();
let mut row_result =
(row.eq(&sortAsc) || row.eq(&sortDecs)) && dedup.len() == row.len();
if row_result {
let mut last = row[0];
for i in 1..row.len() {
if num::abs(last - row[i]) > 3 {
row_result = false;
break;
} else {
last = row[i];
}
}
}
row_result
}
}
}
Now we have our helper function, we can use it to solve part 2. We iterate over each level in the report, temporarily remove it, check if the new report is valid, and then count the number of valid reports. Let’s write the code to make this test pass.
mod part_two {
use crate::utils::split_multiline_string;
use crate::y2024::day2::RedNosed;
impl RedNosed {
pub fn part_two_process(&self, input: String) -> Result<String, ()> {
let input_as_lines = split_multiline_string(input);
let safe_count = input_as_lines
.iter()
.map(|line| {
line.trim()
.split(" ")
.map(|x| x.parse::<i32>().unwrap())
.collect()
})
.filter(|row: &Vec<i32>| {
let mut row_result = self.is_valid_row(row);
if !row_result {
for i in 0..row.len() {
let mut subRow = row.clone();
subRow.remove(i);
row_result = row_result | self.is_valid_row(&subRow);
}
}
self.output_signal
.write(&format!("Result: {:?}", row_result));
row_result
})
.count();
Ok(safe_count.to_string())
}
...
}
And we have a winner. So what are some key learnings from this day? Primarily, don’t rush into a solution. Take a step back, look at what we have done already, and see if we can extend that solution. If we can’t, then we can look at other solutions. And other solutions will be what we need. Sometimes we come up with something that works fine for part 1 but not for part 2. Other times, there is very little we need to do to extend our solution. And that’s the great thing about AoC; there are many ways to solve a problem. And sometimes, the simplest solution is the best one. Why pre-emptively optimise when you don’t need to?