The first puzzle of 2024's AoC (available at https://adventofcode.com/2024/day/1) kicks off with a mystery: the chief historian has gone missing. Where did he go? Two groups of historians have compiled lists of location IDs to check, but the lists don't match up.
The input gives us two columns of numbers — left list and right list — separated by spaces.
Parsing the Input
The format looks simple, but there's a catch: the spacing isn't consistent. Some inputs have two spaces between columns, others have three. I hardcoded the split on the spaces I saw:
type Pair = [number[], number[]];
const processInput = (day: number): Pair => {
const lines = readInputLines(day);
const first: number[] = [];
const second: number[] = [];
for (const line of lines) {
const [left, right] = line.split(" "); // Three spaces
first.push(Number(left));
second.push(Number(right));
}
return [first, second];
};
A regex split on \s+ would be more robust, but this worked for the actual input.
Part One: Total Distance
We need to pair up the smallest number in the left list with the smallest in the right list, then the second-smallest with second-smallest, and so on. For each pair, calculate the distance (absolute difference) and sum them all.
The approach: sort both lists, then iterate through them in parallel.
const partOne = (input: Pair, debug: boolean) => {
const [first, second] = input;
const fSorted = first.toSorted((a, b) => a - b);
const sSorted = second.toSorted((a, b) => a - b);
let totalDistance = 0;
for (let index = 0; index < fSorted.length; index++) {
const distance = Math.abs(fSorted[index] - sSorted[index]);
totalDistance += distance;
}
return totalDistance;
};
JavaScript Sorting Gotcha
If you just call array.sort() on numbers in JavaScript, you get lexicographic sorting:
[1, 2, 5, 4, 10].sort() // Returns [1, 10, 2, 4, 5] — wrong!
The string "10" comes before "2" alphabetically. Always provide a comparison function for numeric sorting: (a, b) => a - b.
The Absolute Value Trap
The puzzle talks about "distance," which is always positive. But if you compute first - second without Math.abs(), you'll get negative values when the right number is larger. Those negative values will cancel out positive ones in your sum, giving the wrong answer.
This wasn't explicitly stated in the puzzle, but "distance" implies absolute value. A trap waiting to catch the unwary.
Part Two: Similarity Score
Part two changes the metric entirely. Now we calculate a "similarity score" by multiplying each number in the left list by how many times it appears in the right list.
This screams "histogram" — build a frequency map of the right list, then iterate through the left list:
const histogram = (input: number[]): Map<number, number> => {
const result = new Map<number, number>();
for (const num of input) {
const count = result.get(num) ?? 0;
result.set(num, count + 1);
}
return result;
};
const partTwo = (input: Pair, debug: boolean) => {
const [first, second] = input;
const fHist = histogram(first);
const sHist = histogram(second);
let similarity = 0;
for (const [key, times] of fHist) {
const occurrences = sHist.get(key) ?? 0;
const score = key * times * occurrences;
similarity += score;
}
return similarity;
};
Note: we iterate over the histogram of the first list, not the list itself. If 3 appears three times in the left list and three times in the right list, we compute 3 * 3 * 3 = 27 once, rather than computing 3 * 3 = 9 three separate times. Same result, cleaner logic.
Performance
Both parts run instantly. Part one is O(n log n) for the sorting. Part two is O(n) for building histograms and iterating.
Takeaways
JavaScript sorting is lexicographic by default: Always provide a numeric comparison function when sorting numbers. This trips up even experienced developers.
Distance means absolute value: When a puzzle says "distance," think
Math.abs(). The difference between two numbers can be negative; the distance cannot.Histograms for frequency counting: When you need to count occurrences, build a frequency map first. It's cleaner than nested loops and often more efficient.
toSorted()vssort(): The newertoSorted()returns a new array, leaving the original unchanged. Use it when you don't want to mutate your input.Test your input parsing: The inconsistent spacing between columns was a minor gotcha. Always verify you're reading the data correctly before diving into the algorithm.
The full solution is available in the repository.