Advent of Code 2024 — Day 1: Historian Hysteria

12/6/2024

Part One

The Chief Historian of the North Pole is missing, and his team of Elvish Senior Historians need my help! Their office is filled with notes, including lists of important historical locations, but the lists don't match up. They need to compare location IDs to fix this, and that's where I come in. In this blog, I'll show you how I tackled this challenge and share my solution.

The Problem

The challange asks us to reconcile two lists of location IDs by calculating how far apart the IDs are within the two lists. The process of reconciling is easy and straightforward, which can be implied for challenge it self.

We are given two lists of numbers. The goal is the following:

Pair up the smallest number in the first list with the smallest number in the second list, the second smallest with the second smallest, and so on.
Measure the distance betwween each pair of numbers (the absolute difference) and sum these distances.
The solution will be the result of that, which is the total sum of the distances.

Example Walkthrough

Let's consider the following example:

Full List:

The first step is to sort both lists from smallest to largest number, so we can measure the distance like intended. Once sorted:

Left List Sorted: 1, 2, 3, 3, 3, 4 Right List Sorted: 3, 3, 3, 4, 5, 9

Now, we can culculate t he distance between each corresponding pair of numbers:

Pair 1: 1 and 3 → |1 - 3| = 2
Pair 2: 2 and 3 → |2 - 3| = 1
Pair 3: 3 and 3 → |3 - 3| = 0
Pair 4: 3 and 4 → |3 - 4| = 1
Pair 5: 3 and 5 → |3 - 5| = 2
Pair 6: 4 and 9 → |4 - 9| = 5

The total distance is: 2 + 1 + 0 + 1 + 2 + 5 = 11

For part 1, 11 is the right solution the challenge asks for using the example input.

Code Implementation

def solve_part_1():
    pairs = []
    with open("input.txt", "r") as f:
        lines = f.read().strip().split("\n")
        for l in lines:
            pairs.append(list(map(int, l.split("   "))))

    pairs.sort()

    l = [p[0] for p in pairs]
    r = [p[1] for p in pairs]

    l.sort()
    r.sort()

    spairs = list(zip(l, r))
    sol = 0

    for p in spairs:
        sol += abs(p[0] - p[1])

    return sol

Part Two

Your analysis only confirmed what everyone feared: the two lists of location IDs are indeed very different. Or are they?

The Historians can't agree on which group made the mistakes or how to read most of the Chief's handwriting, but in the commotion you notice an interesting detail: a lot of location IDs appear in both lists! Maybe the other numbers aren't location IDs at all but rather misinterpreted handwriting.

This time, you'll need to figure out exactly how often each number from the left list appears in the right list. Calculate a total similarity score by adding up each number in the left list after multiplying it by the number of times that number appears in the right list.

For the second part, we are given two lists of numbers. The goal is the following:

For each number in the left list, count how many times it appears in the right list.
Multiply the number in the left list by the count from step 1.
Sum all the results from step 2 to get the total similarity score.

Example Walkthrough

Let's use the same example as before:

Full List:

The first step is to count how many times each number in the left list appears in the right list:

Number 1 appears 0 times
Number 2 appears 0 times
Number 3 appears 3 times
Number 4 appears 1 time

Now, we can calculate the total similarity score:

1 * 0 = 0
2 * 0 = 0
3 * 3 = 9
4 * 1 = 4

The total similarity score is: 0 + 0 + 9 + 4 = 13

For part 2, 13 is the right solution the challenge asks for using the example input.

Code Implementation

def solve_part_2():
    pairs = []
    with open("input.txt", "r") as f:
        lines = f.read().strip().split("\n")
        for l in lines:
            pairs.append(list(map(int, l.split("   "))))

    l = [p[0] for p in pairs]
    r = [p[1] for p in pairs]
    c = 0
    sol = 0
    for v in l:
        sol += v * count_occurrences(v, r)

    return sol

And that's it for the first day of the Advent of Code 2024!