Historian Hysteria

Advent of Code 2024 Day 1

Part 1

A softball to start the year off with a smile

Solving this seems simple:

Parse the input into two equal lists of numbers
Sort each list in ascending order
Compare both values at each index
Determine the absolute value after calculating the difference
Increment a tally by the absolute value

Step 1: make two lists of numbers

First, I'll make a list of 2-item lists where each item is a number:

input.split('\n').split(' ').map(Number)

Then, I'll extract the items into separate lists based on their index:

let [list1, list2] = [
  input.map((_,i) => i == 0),
  input.map((_,i) => i == 1)
]

Running it and fixing my mistakes

First mistake: chaining split.
I can't call split on an array.
I have to split inside an iterating method, like map:

input.split("\n").map(...);

Second mistake: not enough spaces.
The input contains several spaces between each number, not one:

input.split("\n").map((el) => el.split("   ").map(Number));

Third mistake: overthinking list access.

My code acted as if each nested list was one element, and returned boolean values based on whether the element was first or second in the list.

What???!!!

This code recognizes each list and keeps the first or second item:

let [list1, list2] = [
  input.map(list => list[0]),
  input.map(list => list[1]),
];

Alas, my algorithm now generates two lists of numbers!

Whew, I got a little rusty not having done these for ten months.

Sort each list in ascending order

This should be short and sweet.

In fact, I'll just append to the code directly above:

let [list1, list2] = [
  input.map(list => list[0]).sort((a,b) => a - b),
  input.map(list => list[1]).sort((a,b) => a - b),
];

Worked like a charm on the example input:

[ 1, 2, 3, 3, 3, 4 ]
[ 3, 3, 3, 4, 5, 9 ]

The other three steps, all at once!

let answer = 0;
for (let i = 0; i < list1.length; i++) {
  answer += Math.abs(list1[i] - list2[i]);
}

It works on the example: 11

Will it work on my puzzle input, though?

It does!

Woohoo! One gold star!

Part 2

A fun twist to test run time

The instructions would have me believe:

For each number in list 1
  For each number in list 2
    If there's a match
      Increment a tally by 1

That means list 2 will be checked list 2 length times list 1 length...times.

1000 items in each: 1 million checks

That's not bad. But that seems unnecessary.

All I care about are the counts of each number in list 2.

So, I can check all 1000 numbers once, and build up a map of numbers to their counts. Then, check that list 1000 times.

2000 < 1 million

I like this approach better. To the code!

Building the map of numbers and counts

The example list looks like:

4, 3, 5, 3, 9, 3

So I want an object that looks like:

{
  4: 1,
  3: 3,
  5: 1,
  9: 1
}

With my list2 from my Part 1 algorithm, I need to perform a reduce to build this object:

let counts = list2.reduce((obj, num) => {
  if (!(num in obj)) {
    obj[num] = 1
  } else {
    obj[num] += 1
  }
  return obj
}, {})

To my surprise, that snippet works exactly as expected!

I thought I forgot the correct syntax for num in obj, but that's it!

One simple look-up for each list item

Another reduce with a condition checking for the existence and value associated with a number:

list1.reduce((score, num) => {
  score += (num in list2) ? num * list2[num] : 0
  return score
}, 0)

Debugging forever because, well, I can't believe it

I kept seeing the wrong score.

I kept wondering why.

I kept adding console.log() statements with more and more values to print.

I kept seeing values that I didn't expect.

Then, I saw it.

I was comparing to list2 and not my custom counts object!

Huge punch to the ego. But just what I needed on Day 1.

Here's the working code:

let score = list1.reduce((score, num) => {
  if (num in counts) {
    score += num * counts[num];
  }
  return score;
}, 0);

That generates the correct answer for the example input.

Let's hope it does the same for my puzzle input.

And hopefully it runs lightning fast!

It does!

Yeeeehawwww!!!

Two gold stars to kick things off.

Along with a few beginner mistakes that keep me grounded.

It's all why I love these puzzles.

Onward too Day 2!