Cafeteria

Advent of Code 2025 Day 5

Part 1

Working from brute-force to anything better

A brute-force algorithm would work as follows:

Set counter to 0
For each ID
  While true
    Check the next range for inclusion of the current ID
    If ID is included
      Increment counter
      Break out of this loop

My puzzle input includes 1000 ingredient IDs and almost 200 ranges.

That's as many as 200k operations...assuming each iteration checked every range.

It's not many - it would probably finish in miliseconds.

But there must be a better way, right?

Sorting: sort of helpful or super helpful?

Would sorting help?

I could do one or both of these:

Sort the ingredient IDs in ascending order
Sort the ranges in ascending order by lower boundary

How would that speed things up, if at all?

Here's my idea:

Having a sorted ID list
For each range
  Search the list for each ID within the range

There are fewer ranges.

Finding an item in a sorted list should be faster than finding in an unsorted list - even if the performance improvement is negligible.

So:

Down from 1000 iterations of a loop to sub-200
Down from 200 checks each iteration to only as many needed to reach a number inside the range or surpassing and stopping

This feels like it should be much faster.

I feel good about this algorithm.

Time to write it!

Writing my chosen algorithm

I need to parse and sort two lists from the input string:

let [ranges, ids] = input.split('\n\n')
ranges = ranges
  .split('\n')
  .map(str => str.split('-').map(Number))
  .sort((a,b) => a[0] - b[0])
ids = ids
  .split('\n')
  .map(Number)
  .sort((a,b) => a - b)

Both lists are achieved by:

Chopping each string up at newline characters
Coercing strings into numbers
And sorting in ascending order by comparing a number or the first numbers in an array

Thankfully, I see the expected output for both lists using the example input:

[ [ 3, 5 ], [ 10, 14 ], [ 12, 18 ], [ 16, 20 ] ] [ 1, 5, 8, 11, 17, 32 ]

Now for the fun part - finding any ids that are within each range.

It should be as simple as filtering the list of IDs for any matches.

Then, to avoid re-counting an ID when checking a future range, I'll remove matched IDs from the list.

Here's how my algorithm looks:

ranges.reduce((count, range) => {
    let matches = ids.filter(el => el >= range[0] && el <= range[1])
    ids.splice(ids.indexOf(matches[0]), matches.length)
    count += matches.length
    return count
}, 0)

When running it on the example input, I get the correct number and I see the correct IDs being matched.

I also see one ID matching twice when I temporarily remove the splice() operation.

The question is, will running on my puzzle input generate the correct answer?

Running and hoping

I made sure to log all matches along with the final count.

I see increasing numbers, no duplicates, and many matches.

My final count is 3/4 of the list are fresh.

Submitting...

Correct answer!

Woohoo!!!

What kind of twist will Part 2 bring? And will it be a performance test?

Part 2

Certainly a test of working with the bookends and not the pages

As I understand it, I need to count every number in all the ranges.

Given the enormity of most numbers, this isn't solvable using a list of all the numbers of which I can eventually get the length.

Thankfully, I am already working from a sorted list of ranges ordered by the minimum number.

The way I see it:

Create a variable to track pairs of numbers as lists...inside a list
For each range in the ordered list of ranges
  If the lower boundary is less than the newest upper boundary
    Update the newest upper boundary to equal the current upper boundary
  Else
    Add a new list inside the list with the same two numbers in this range

How I expect this to play out:
Using the example input's ranges in sorted order...

[ [ 3, 5 ], [ 10, 14 ], [ 12, 18 ], [ 16, 20 ] ]

My new list will start with the first range:

[ [3, 5] ]

When checking [10, 14], it will see that 10 is greater than 5 and add a new list:

[ [3,5] , [10, 14] ]

When checking [12, 18], it will see that 12 is less than 14 and update 14 to 18:

[ [3,5] , [10, 18] ]

It will do the same when checking [16, 20]:

[ [3,5] , [10, 20] ]

Once finished, I can use each list's pair to calculate the total numbers:

   3
+ 11
----
  14

That's the correct answer!

This should work, and it should be very performant!

Writing my algorithm

I'll start with the same setup as Part 1:

let [ranges, ids] = input.split('\n\n')
ranges = ranges.split('\n').map(str => str.split('-').map(Number)).sort((a,b) => a[0] - b[0])
ids = ids.split('\n').map(Number).sort((a,b) => a - b)

Next, I need a list that starts with the first range, having been removed from the list of ranges:

let part2 = []
part2.push(ranges.splice(0,1).flat())

Now, I can iterate through the remaining ranges and perform my check:

ranges.forEach(range => {
    if (range[0] <= part2[part2.length - 1][1]) {
        part2[part2.length - 1][1] = range[1]
    } else {
        part2.push(range)
    }
})

In English:

For each range
If the first number is less than or equal to the second number in the last sub-list of the bigger accumulating list
Then set that number equal to the second number in the current range pair (the upper boundary)
Otherwise, add the range as the new last sub-list

That's at least how it should work.

Let's see if it does.

It does! I see the expected pairs in my output!

Ok, and now for the last step: counting all included numbers.

Well, For 3-5 there should be 3: 3, 4, 5.

If I subtract 3 from 5 I get 2.

I assume that for any two numbers I can:

For [a, b]
  Perform b - a
  And add 1

Time for a reducer!

let answer = part2.reduce((total, range) => {
    total += range[1] - range[0] + 1
    return total
}, 0)

Running and hoping it works

It does with the example input!

As for my puzzle input...

Bummer. Answer is too low.

What could the reason be?

Debugging in search of an oversight

I checked the original sorted list of ranges. They're in order.

I checked the accumulated list of ranges. They're in order and appear to be correct aggregations.

I noticed some duplicate range mins and maxes. That was interesting.

I didn't notice anything else that was suspicious.

Until...thankfully, something stood out:

[ 20656954187719, 29282595277568 ],
[ 23070165593770, 26446231348661 ],

Neither range is remarkable.

But when taken together and processed by my algorithm, I see what happened.

My algorithm assumes that each subsequent range will contain a higher upper boundary than the previous range.

But this example proves that to be incorrect.

By incorrectly updating the upper boundary here, my algorithm is erasing approximately three trillion fresh IDs!

The fix? Update the line where I update a value so that it first does a comparison and always picks the higher value:

if (range[0] <= part2[part2.length - 1][1]) {
  part2[part2.length - 1][1] = Math.max(range[1], part2[part2.length - 1][1])
}

When running again, I get a slightly higher answer.

I have good feelings and crossed fingers.