Dec 1, 2024

Advent of Code 2024 - Day 1: Historian Hysteria

Attention!

Check Advent of Code for the full challenge details. They created everything we need to know about the challenge - give them your support.
My solutions are not ‘the’ solutions - I target one of the possible solutions. They might not be the most efficient, but they are a way to solve the problem. I do not plan to spend too much time doing the challenges.
Every challenge = different language - just for fun and learning.
I do not include the input data, but you can find it on the Advent of Code website or in the repository of the code.

The holidays are almost here, and with them comes another round of puzzles in the Advent of Code challenge. Day 1’s puzzle, “Historian Hysteria”, brought me into the world of the Chief Historian at the North Pole, who has mysteriously vanished. The task was to help a group of Senior Historians reconcile two lists of historically significant location IDs that they found in the Chief’s office. However, the lists were mismatched, and it was up to me to help find some meaningful insights by solving a couple of interesting challenges.

Let me walk you through my “journey” solving this puzzle, explaining my approach, and the code I wrote to tackle both parts of the challenge.

For the first day, I decided to use JavaScript to solve the puzzle.

Problem Breakdown:

I was provided with two lists of numbers, one from the “left” group and one from the “right” group.
I needed to match the smallest numbers from each list, the second smallest, and so on, calculating the absolute difference between each pair of numbers.
Part one solution was the total distance between two lists.
Part two solution was the similarity score between two lists.

Example Input:

18244   68298
13337   38665
21418   93374
83955   83955
50722   83955

Part One: Calculating the Total Distance

In the first part of the puzzle, I was given two lists of location IDs—one for each group of historians. These lists were mismatched, and the goal was to compute a total distance between the two lists. The distance between corresponding elements in the two lists is calculated as the absolute difference between each pair. Then I needed to sum up all these distances to get the final total.

Solution:

Sorting the Lists: The first step was to sort both lists in ascending order. This ensures that the smallest numbers from each list are paired together, as required.
Calculating the Distance: For each pair, I calculated the absolute difference and summed them to get the total distance.

I started with reading the input file and splitting the columns of numbers into two sorted arrays. The totalDistance and similarity score are two parts of the solution that took the same input data.

// index.js
readFile("input.txt", "utf-8").then(input => {
    const numbers = input.trim().split("\n").map((line) => line.trim().split(/\s+/).map(Number));
    let left = [];
    let right = [];
    for (let i = 0; i < numbers.length; i++) {
        left.push(numbers[i][0]);
        right.push(numbers[i][1]);
    }
    [left, right] = [left, right].map(arr => arr.sort((a, b) => a - b));
    const totalDistance = calculateTotalDistance(left, right); // part one
    console.log({ partOne: totalDistance });
    const similarityScore = calculateSimilarityScore(left, right); // part two
    console.log({ partTwo: similarityScore });
    }).catch(err => console.error(err));

The calculateTotalDistance function takes two sorted arrays, left and right, and calculates the total distance by iterating through both lists, calculating the absolute difference for each pair, and summing them.

// index.js
/**
 * @param {number[]} left
 * @param {number[]} right
 * @returns {number} totalDistance
 */
function calculateTotalDistance(left, right) {
	return left.map((num, i) => Math.abs(num - right[i])).reduce((a, b) => a + b);
}

Example Walkthrough:

Let’s take an example where:

After sorting both lists:

Sorted Left List: [13337, 18244, 21418, 50722, 83955]
Sorted Right List: [38665, 68298, 83955, 83955, 93374]

I calculated the absolute differences between corresponding elements:

|13337 - 38665| = 25328
|18244 - 68298| = 50054
|21418 - 83955| = 62537
|50722 - 83955| = 33233
|83955 - 93374| = 9419

The total distance is the sum: 25328 + 50054 + 62537 + 33233 + 9419 = 180571.

Thus, the total distance for this example was 180571.

Part Two: Calculating the Similarity Score

In the second part of the puzzle, instead of calculating distances, I needed to find a similarity score between the two lists. This score was calculated by checking how often each number from the left list appears in the right list. For each number in the left list, I multiplied it by the number of times it appears in the right list and summed these results to get the similarity score.

Solution:

Counting Occurrences: First, I needed to count how many times each number from the right list appeared. I did this efficiently using a hash map (or Map in JavaScript).
Calculating the Similarity Score: For each number in the left list, I looked it up in the hash map to find how many times it appeared in the right list and multiplied the two values (not present was considered as 0).

// index.js
/**
 * @param {number[]} left
 * @param {number[]} right
 * @returns {number} similarityScore
 */
function calculateSimilarityScore(left, right) {
	const hash = new Map();
	for (let i = 0; i < right.length; i++) {
		hash.set(right[i], (hash.get(right[i]) ?? 0) + 1);
	}

	let similarityScore = 0;
	for (let i = 0; i < left.length; i++) {
		similarityScore = similarityScore + left[i] * (hash.get(left[i]) ?? 0);
	}
	return similarityScore;
}

Example Walkthrough:

Consider the same lists:

Left List:  [18244, 13337, 21418, 83955, 50722]
Right List: [68298, 38665, 93374, 83955, 83955]

First, I built the frequency map for the right list:
```
Frequency Map for Right List: { 38665: 1, 68298: 1, 83955: 2, 93374: 1 }
```
If a number doesn’t appear in the right list, its count is considered 0.

For each element in the left list, I multiplied it by the count from the right list:

18244 does not appear in the right list -> 18244 * 0 = 0
13337 does not appear in the right list -> 13337 * 0 = 0
21418 does not appear in the right list -> 21418 * 0 = 0
83955 appears 2 times in the right list -> 83955 * 2 = 167910
50722 does not appear in the right list -> 50722 * 0 = 0

The total similarity score is the sum of these values: 0 + 0 + 0 + 167910 + 0 = 167910.

Thus, the similarity score for this example was 167910.

Big O Analysis

To understand the performance of my solution, let’s analyze the time complexity for both parts of the puzzle.

Part One (Total Distance Calculation):

Sorting both lists requires O(n log n) time complexity, where n is the length of the lists.
Calculating the absolute differences requires a single pass through the lists, which is O(n).

So, the total time complexity for part one has an overall complexity of O(n).

Part Two (Similarity Score Calculation):

Building the frequency map for the right list takes O(n) time because we iterate through the right list once and store each number in the map.
Calculating the similarity score involves iterating through the left list and performing lookups in the hash map, which is O(n).

Thus, the total time complexity for part two is O(n), since the hash map operations (insert and lookup) are average-case constant time, i.e., O(1).

Why I Coded It This Way

I chose to solve Part One by sorting both lists because sorting guarantees that the smallest elements from both lists are paired together. This is key to ensuring the distance calculation is correct. Sorting is efficient enough for this problem, and it simplifies the logic of pairing the numbers. Once the lists are sorted, calculating the total distance is straightforward and efficient, with a time complexity of O(n).

For Part Two, I used a hash map to count the occurrences of each number in the right list. This allows me to efficiently look up the count for each element in the left list, avoiding the need for nested loops (which would be slower). Using a map ensures that the time complexity for counting and lookup is linear, O(n).

And finally, I want to solve the problem without spending too much time on it. You should solve the problem first, and then optimize it if needed. In this case, the problem is small enough that the initial solution is efficient and doesn’t require further optimization.

Final Solution Code

The final solution code can be found on my GitHub repository.

If you like the content, don’t forget to give it a star ⭐.

Conclusion

In Day 1’s puzzle, “Historian Hysteria”, I was tasked with reconciling two lists of location IDs.

By sorting the lists and leveraging efficient algorithms like frequency counting (using hash maps), I was able to solve both parts of the puzzle efficiently. The solution helped the Senior Historians get one step closer to finding the Chief Historian and saving Christmas!

Honestly, this problem was not hard, and the language I chose to start with was one of my strongest.

Tomorrow, Golang. Stay tuned.