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:

1. Sort Both Lists: Align both lists in ascending order.
2. Pair Smallest to Smallest: Match the smallest number in list1 with the smallest number in list2, the second smallest with the second smallest, and so on.
3. Calculate Pair Distances: Compute the absolute difference for each pair.
4. 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:

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:

1. Count Frequencies in list2: Create a frequency map for each number in list2.
2. Multiply and Add: For each number in list1, multiply it by its frequency in list2 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:

The similarity score is:

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 in list2.

Steps:

1. Read the input file and split each line into two lists: list1 and list2.
2. Sort both lists in ascending order.
3. Compute the total distance:
   • Pair numbers from list1 and list2 by their sorted order.
   • Calculate the absolute difference for each pair and sum them up.
4. Compute the similarity score:
   • Count how often each number appears in list2.
   • Multiply each number in list1 by its frequency in list2 and sum the results.
5. 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!