- Published on
Day 1 - Historian Hysteria
I know I’m a little late to the party, but better late than never, right? Advent of Code has always intrigued me with its mix of storytelling, puzzles, and problem-solving challenges. This year, I’ve decided to dive in and use it as an opportunity to hone my skills in Rust.
Day 1 didn’t disappoint—it brought together sorting, mapping, and iterating, all wrapped in a fun narrative about reconciling the Elves’ lists. Let’s break it down and see how I approached the problem.
Problem Context
The Chief Historian, an integral part of the Christmas sleigh launch tradition, has gone missing! The Senior Historians believe he might be at one of the historically significant locations near the North Pole. Unfortunately, the list of potential locations is messy, and the Elves need help reconciling two conflicting lists.
Our mission? Solve the discrepancies and get the Elves fifty stars by December 25th to save Christmas!
Part One: Calculating the Total Distance
The two lists, list1
(left) and list2
(right), contain Location IDs. The task is to calculate the total distance between these two lists. Here's the process:
- Sort Both Lists: Align both lists in ascending order.
- Pair Smallest to Smallest: Match the smallest number in
list1
with the smallest number inlist2
, the second smallest with the second smallest, and so on. - Calculate Pair Distances: Compute the absolute difference for each pair.
- Sum Distances: Add up the differences.
For example, given the lists:
list1: 3, 4, 2, 1, 3, 3
list2: 4, 3, 5, 3, 9, 3
After sorting:
sorted list1: 1, 2, 3, 3, 3, 4
sorted list2: 3, 3, 3, 4, 5, 9
The distances are:
Pair | Distance |
---|---|
1 and 3 | 2 |
2 and 3 | 1 |
3 and 3 | 0 |
3 and 4 | 1 |
3 and 5 | 2 |
4 and 9 | 5 |
Total Distance: 2 + 1 + 0 + 1 + 2 + 5 = 11
.
Part Two: Calculating the Similarity Score
The Senior Historians realized that some numbers appear in both lists multiple times. To measure this overlap, we compute a Similarity Score:
- Count Frequencies in list2: Create a frequency map for each number in
list2
. - Multiply and Add: For each number in
list1
, multiply it by its frequency inlist2
and sum the results.
Using the same example lists:
list1: 3, 4, 2, 1, 3, 3
list2: 4, 3, 5, 3, 9, 3
The frequency map of list2
is:
Number | Frequency |
---|---|
3 | 3 |
4 | 1 |
5 | 1 |
9 | 1 |
The similarity score is:
Number in list1 | Frequency in list2 | Contribution to Score |
---|---|---|
3 | 3 | 3 * 3 = 9 |
4 | 1 | 4 * 1 = 4 |
2 | 0 | 2 * 0 = 0 |
1 | 0 | 1 * 0 = 0 |
3 | 3 | 3 * 3 = 9 |
3 | 3 | 3 * 3 = 9 |
Total Similarity Score: 9 + 4 + 0 + 0 + 9 + 9 = 31
.
Solution (in Rust)
Here’s how to implement both parts in Rust:
use std::fs;
use std::collections::HashMap;
fn main() {
let file_path = "./input.txt";
let contents = fs::read_to_string(file_path)
.expect("Should be able to read the file.");
let mut list1 = Vec::new();
let mut list2 = Vec::new();
for line in contents.lines() {
if let Some((first, second)) = line.split_whitespace()
.collect::<Vec<_>>().split_first() {
if let Some(second) = second.first() {
list1.push(first.parse::<i32>().unwrap());
list2.push(second.parse::<i32>().unwrap());
}
}
}
list1.sort();
list2.sort();
let distance_list: Vec<i32> = list1.iter()
.zip(&list2)
.map(|(a, b)| (a - b).abs())
.collect();
let total_distance: i32 = distance_list.iter().sum();
println!("Total distance : {}", total_distance);
let mut frequency_map = HashMap::new();
for &num in &list2 {
*frequency_map.entry(num).or_insert(0) += 1;
}
let similarity_scores: Vec<i32> = list1.iter()
.map(|&num| num * frequency_map.get(&num).unwrap_or(&0))
.collect();
let total_similarity_score: i32 = similarity_scores.iter().sum();
println!("Total similarity score : {}", total_similarity_score)
}
Algorithm
Input:
- A file containing pairs of integers, with one pair per line.
Output:
- Total Distance: The sum of absolute differences between corresponding sorted pairs.
- Similarity Score: The sum of each number in
list1
multiplied by its frequency inlist2
.
Steps:
- Read the input file and split each line into two lists:
list1
andlist2
. - Sort both lists in ascending order.
- Compute the total distance:
- Pair numbers from
list1
andlist2
by their sorted order. - Calculate the absolute difference for each pair and sum them up.
- Pair numbers from
- Compute the similarity score:
- Count how often each number appears in
list2
. - Multiply each number in
list1
by its frequency inlist2
and sum the results.
- Count how often each number appears in
- Print both results.
With this, the Senior Historians can reconcile their lists and continue the search for the Chief Historian. Thank you for reading my blog!