Solving Advent of Code 2024 Puzzle 1

Advent of Code is one of my favorite programming pastimes! According to The New Stack, this is celebrating its 9th year!

In the past I've participated in the SANS Holiday Hack Challenge as well (think Project Euler, but with holiday themes). PoCs are great for keeping up in my preferred programming languages, but the usage of those languages tends to be more domain specific. I absolutely love katas and other programming puzzles as a way to practice more general problems and keep problem solving and analytical skills sharp.

Here's how I solved it. WARNING - SPOILERS BELOW!

For part 1, setup took longer than the actual implementation (at least, in JavaScript). After exporting the sorted sample data into two arrays, a quick implementation takes the absolute value of the difference between each element at the respective array index and adds them to a state variable:

const {sortedFirstNumbers, sortedSecondNumbers} = require('./input.js')

const getDistanceDifference = (arr1, arr2) => {
    let acc = 0;

    for (let i = 0; i != arr1.length; i++) {
         acc += Math.abs(arr1[i] - arr2[i])
    }

    return acc;
 );
}

But we can do better! The time complexity for this algorithm is O(n) already, but a nice, elegant alternative is to use reduce, which turns this into a one liner:

const {sortedFirstNumbers, sortedSecondNumbers} = require('./input.js')

const getDistanceDifference = (arr1, arr2) => {
    return arr1.reduce((acc, val, index) => acc + Math.abs(val - arr2[index]), 0);
}

Which yields the answer!

For the second gold star, I instinctively reached for filter to get a new array whose length would match the instance count that is asked for in the puzzle:

let total = 0

for (let i = 0; i != sortedFirstNumbers.length; i++) {
    let instanceCount = sortedSecondNumbers.filter(sample => sample === sortedFirstNumbers[i]).length
    total += sortedFirstNumbers[i] * instanceCount
}

but while this works, we can do better with another reduce function:

let total = sortedFirstNumbers.reduce((acc, num) => {
    let instanceCount = sortedSecondNumbers.filter(sample => sample === num).length;
    return acc + num * instanceCount;
}, 0);

We can do even better with a frequency map:

const frequencyMap = sortedSecondNumbers.reduce((map, num) => {
    map[num] = (map[num] || 0) + 1;
    return map;
}, {});

// Calculate the total using the frequency map
let total = sortedFirstNumbers.reduce((acc, num) => {
    let instanceCount = frequencyMap[num] || 0;
    return acc + num * instanceCount;
}, 0);

Which turns this from O(n x m) to O(n + m), is expressive and readable.

I would not have thought to use frequency maps here, and this is where these katas have value! It's tempting to try to optimize right away, but it's much easier to take the Addy Osmani approach: first do it, then do it right, then do it better!