Advent of Code 2024 is finally here. We kick day one off with a relatively straightforward set of puzzles. The Chief Historian is missing, and the elves are scrambling through notes to work out where they are. Split in two, the elves have come up with two lists of numbers. These numbers are location IDs. Problem is, the lists should match but they do not.
Part one is relatively simple. To solve this puzzle, the request is to match numbers between the lists, going smallest to largest, find the difference between each list element, and sum them up. AoC is great early on for providing us with a simple challenge to get our feet wet. Let's get started. But first, 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#"3 4
4 3
2 5
1 3
3 9
3 3"#,
);
let hysteria = Hysteria {
output_signal: Box::new(DefaultOutputSignal),
};
let result = hysteria.solve_part_one(input);
assert_eq!(result, Ok("11".to_string()));
}
}
This is nice and simple. We got our input from the AoC site directly, and we know the result will be 11. The task we have is to essentially take two lists, order them, and then find the difference between each element at each index. Now given it's the first day, we could build our own sorting algorithm, but Rust gives us an implementation that we can use anyway. Why reinvent the wheel this early on? Let's write the code to make this test pass.
pub struct Hysteria {
output_signal: Box<dyn OutputSignal>,
}
impl AoCImplementation for Hysteria {
fn new(output_signal: impl OutputSignal + 'static) -> Self {
Hysteria {
output_signal: Box::new(output_signal),
}
}
fn solve_part_one(&self, input: String) -> Result<String, ()> {
self.part_one_process(input)
}
fn solve_part_two(&self, input: String) -> Result<String, ()> {
self.part_two_process(input)
}
}
mod part_one {
use crate::utils::split_multiline_string;
use crate::y2024::day1::Hysteria;
impl Hysteria {
pub fn part_one_process(&self, input: String) -> Result<String, ()> {
let input_as_lines = split_multiline_string(input);
let mut left_list = Vec::<i32>::new();
let mut right_list = Vec::<i32>::new();
for line in input_as_lines.iter() {
let (left, right) = line.trim().split_once(" ").unwrap();
left_list.push(left.trim().parse().unwrap());
right_list.push(right.trim().parse().unwrap());
}
left_list.sort();
right_list.sort();
let mut diff_list = Vec::<i32>::new();
for i in 0..left_list.len() {
diff_list.push(right_list[i] - left_list[i]);
}
Ok(diff_list.iter().sum::<i32>().to_string())
}
}
}
Here we have a simple implementation. We split each line into a left and a right, parse it to an i32 since we do not know for sure if the numbers will all be positive, and then dump it into one of two vectors. We sort both, find the difference, and sum the final list for our result. If we run our test, we get a pass. However, when we run the input from AoC, we get the wrong answer... "Answer too low." This is what is great about AoC—you think you have a simple solution, but then you find you missed something.
For us, we made an assumption where we diff each index. We assumed that the right list will always be greater than the left list. The problem is that is not true. The right could be less than the left, or equal. No matter—it's an easy fix. We can use the num::abs function to get the absolute value of the difference. Let's make that change.
pub fn part_one_process(&self, input: String) -> Result<String, ()> {
...
let mut diff_list = Vec::<i32>::new();
for i in 0..left_list.len() {
diff_list.push(num::abs(right_list[i] - left_list[i]));
}
Ok(diff_list.iter().sum::<i32>().to_string())
}
Rerun, and we have our answer! On to part two.
Part two is a nice little step up. Before, we proved that there was a significant difference between the two lists. Now we need to work out how similar they are. The request is simple: Take the first list, iterate over it, multiplying the value by the number of times it appears in the second list. Then sum all the values together. Let's start with a test.
#[cfg(test)]
mod tests {
use super::*;
use crate::DefaultOutputSignal;
...
#[test]
fn test_solve_part_two() {
let input = String::from(
r#"3 4
4 3
2 5
1 3
3 9
3 3"#,
);
let hysteria = Hysteria {
output_signal: Box::new(DefaultOutputSignal),
};
let result = hysteria.solve_part_two(input);
assert_eq!(result, Ok("31".to_string()));
}
}
Now we have a test, let's plan out how we can solve this problem. We have our two lists. We need to find the distinct count of values in the second list, then iterate over the first list, multiplying the value by the distinct count from the second, and finally sum it all together. There are methods to optimise this approach, but considering how small the input is relatively, we can keep the solution simple. As such, my plan is to use a hashmap to store the count and iterate over the second vector, incrementing the count. Once done, we can iterate over the first list, multiply the value by the count, and sum it all together.
mod part_two {
use crate::utils::split_multiline_string;
use crate::y2024::day1::Hysteria;
use std::collections::HashMap;
impl Hysteria {
pub fn part_two_process(&self, input: String) -> Result<String, ()> {
let input_as_lines = split_multiline_string(input);
let mut left_list = Vec::<i32>::new();
let mut right_list = Vec::<i32>::new();
for line in input_as_lines.iter() {
let (left, right) = line.trim().split_once(" ").unwrap();
left_list.push(left.trim().parse().unwrap());
right_list.push(right.trim().parse().unwrap());
}
left_list.sort();
right_list.sort();
let mut count_bin = HashMap::<i32, i32>::new();
for i in 0..right_list.len() {
*count_bin.entry(right_list[i]).or_insert(0) += 1;
}
let result = left_list
.iter()
.filter(|left| count_bin.contains_key(left))
.map(|left| count_bin.get(left).unwrap() * left)
.sum::<i32>();
Ok(result.to_string())
}
}
}
All in all, the first half of this solution is identical to the previous part, but the second half is where things change. First, we need to build a hashmap to keep track of the count of each value in the right list. For this, I used an i32 type for both the key and value. While we could use u32, the small input size makes this unnecessary. We then iterate over the right list, incrementing the count for each value as we go.
The line that increments the count uses the value from right_list[i] to access or insert an entry in the hashmap using .or_insert(0). This ensures that if the key does not exist, it starts at zero. Finally, we dereference the value to increment it directly. After building our count hashmap, we iterate over the left list, filter out values that do not appear in the hashmap, and then multiply each value by its corresponding count. Summing these products gives us the final answer. Running the test confirms the correctness of our solution. If we run our test, we get a pass, and if we run the input from AoC, we get the correct answer.
Day 1 of Advent of Code was a fantastic warm-up to get us back into problem-solving mode. The puzzles provided a nice simple introduction while reinforcing the need to be careful. Part 1 gave me the opportunity to understand assumptions and make adjustments when things do not quite go as planned. Part 2 took it up a notch, requiring us to think about similarities and using tools like hashmaps to effectively solve the problem.
What makes Advent of Code so enjoyable is the journey from initial attempts and mistakes to the final solution. Even simple problems have the power to teach us something new or remind us of core programming concepts. It is a great opportunity to challenge ourselves, approach problems in unique ways, or just enjoy the process of software development. Come tomorrow we should have a nice new challenge to look forward to. And if you have not already, give today's challenge a go yourself. Pick any language or tool you like, I know of people completing some days in Excel of all things.