202412010000 Advent of Code 2024 Day 01

Historian Hysteria

This year finds us helping elf historians track down their chief historian who has gone missing and needs to be back for the sleigh launch on Christmas. Today we're comparing lists of numbers for historians.

The Puzzle

This year finds us helping elf historians track down their chief historian who has gone missing and needs to be back for the sleigh launch on Christmas. I have a feeling this premise is going to be a trip down memory lane where we'll revisit places and puzzles we've seen in the past (hopefully with a nice twist). It would make sense since this is the 10th year of Advent of Code.

Our puzzle gives us two lists of numbers, presented side by side in the input lines.

3   4
4   3
2   5
1   3
3   9
3   3

We need to sort each list in ascending order and then find the distance between each left/right pair, i.e. the absolute value of the difference of the two.

1   3   => 2
2   3   => 1
3   3   => 0
3   4   => 1
3   5   => 2
4   9   => 5
------------
          11

Solution

Day 1 of AoC is always straight forward and today was no exception.

const parse = (input) => [
  input.map((l) => +l.split('   ')[0]).asc(),
  input.map((l) => +l.split('   ')[1]).asc(),
];

export const solutionOne = (input) =>
  zip(...parse(input))
    .map((p) => Math.abs(p[0] - p[1]))
    .sum();

I did make one refactor to my parse function after my initial quick version. I initially parsed the input line by line and built up two arrays at the same time in one pass, but it turned out to look and feel simpler as well as be a little faster on my machine to just make the right and left lists each with a different pass over the input.

I think ultimately (as is typically the case in JS) if I abandoned my initial reduce version and built up two arrays with one pass mutably, maybe that would have been faster than either other method. But this version feels good to me and AoC is mostly about vibes and the ⋆˙⟡ aesthetic ⟡˙⋆ anyway. For example, look at that beautiful unary number operator that I'd probably never use in production code, but always use in AoC. Gotta love it.

Some Navel Gazing

Hmmm, I’m realizing something else now as I look at this. I could have maybe gone with a map of split and cast, and then did a transpose on the array of arrays, which would let me map the sort function more naturally.

const parse = (input) =>
  input
    .map((l) => l.split('   ').nums())
    .transpose()
    .map((l) => l.asc());

Looks like it's just about the same speed as the version above.

Yet another way might be to do the split and cast into a flat array and then to take every second value and then take every second value with an offset of 1.

const parse = (input) => {
  const ns = input.map((l) => l.split('   ').nums()).flat();
  return [ns.takeEvery(2).asc(), ns.takeEvery(2, 1).asc()];
};

This was marginally slower than either of the other two methods, maybe not statistically significantly though.

Part Two

We're supposed to multiply the number in the first list by the count of its occurrences in the second. For instance, in the sample input, the number 3 from the left list occurred 3 times in the right list. So we iterate through the left list and each time we see 3 we add 3 * 3 = 9 to the running sum. If the number in the left list didn't occur in the right, we add 0.

export const solutionTwo = (input) => {
  const [a, b] = parse(input);
  const counts = counter(b);
  return a.reduce((acc, n) => acc + (counts[n] ?? 0) * n, 0);
};

The counter function counts the occurrences of values in an array and comes from my library of array extensions. Here's the new implementation.

Array.prototype.counter = function () {
  let c = {};
  for (let v of this) {
    c[v] = (c[v] || 0) + 1;
  }
  return c;
};

Interestingly, before today it looked like this

Array.prototype.counter = function () {
  return this.reduce((c, v) => ({ ...c, [v]: (c[v] || 0) + 1 }), {});
}

Which, while elegantly functional, was unbelievably slow. I only thought to change the implementation because I noticed that part 1 was under 1ms to solve and part 2 was taking 65ms! Fixing that brought it back down under 1ms where it should be.

I was a little slow out of the gate tonight. There's definitely some rust to be shaken off for these kinds of programming puzzles. But ultimately, it was still a short solve to start us off. I'm excited to be back in it! Looking forward to the rest of the year.

You can find the full solutions to today's AoC puzzles in my AoC GitHub repo.