Lobby

Advent of Code 2025 Day 3

Part 1

Considering my options, from worst to best

Each line is an ordered list of positive digits.

I must identify the largest 2-digit number made from any two digits appearing in order.

I can think of a few ways to do this, from brute-force to better.

Brute force

Compare every possible combination of digits:

Set an initial value, max, to 0
For each digit except the last
  For each subsequent digit
    If the ordered concatenation of digits is greater than 'max'
      Update max to reflect this 2-digit number

Measuring performance:

• Given line length, L
• This will run L + L-1 + L-2 + L-3 + ... times
• Example: L = 10 - runs 10 times for first number, 9 times for second number, etc. - 55 times

Not great. But still should complete quickly even for line lengths less than 100. My puzzle input lines are roughly 40 digits long.

Brute force but optimized

Compare digit pairings for increasing 10s-place digits

Set an initial value, max, to 0
Set an initial value, lower, to 0
Set an index tracker to 0
While index is less than line length
  If current digit is less than or equal to lower
    Increment index
  Else
    For each subsequent digit
        If the ordered concatenation of digits is greater than 'max'
        Update max to reflect this 2-digit number
  Increment index

Measuring performance:

• Ideally, this algorithm will skip several digits
• So, still L + L-1 + L-2... but with several L-N skipped
• It could be as fast as only comparing digits for the first digit
• Or as slow as the one above if all digits appear in increasing order, 123456789

Getting creative: find the two biggest numbers

I'm ultimately trying to identify a pair of digits as close to 99 as possible.

Sounds like a great use case for finding the two biggest digits in a line.

Here are a few scenarios:

1. A line has two instances of a high number
2. A line has one instance of a high number, and it is not the last digit in the line
3. A line has one instance of a high number, but it is the last digit in the line

Scenario 1 is ideal because the answer there is the two numbers combined in order.

Scenario 2 is easy because the answer is that high number paired with the next highest number appearing anywhere after it.

Scenario 3 is harder because it is essentially a red herring, and I will have to check for the next highest number.

Still, this feels way more performant than the two options above.

So, I'm going to proceed with thinking through and coding this algorithm.

Building the creative algorithm

I'll wrap it all in a reduce() since I must eventually calculate a sum.

First step, though, is the find the biggest digit in a line.

input.split('\n').reduce((sum, line) => {
    let digits = line.split('').map(Number)
    let biggest = Math.max(...digits)
    return sum
}, 0)

Next, see if there are two of that biggest number:

let biggest = Math.max(...digits)
let firstBiggest = digits.indexOf(biggest)
let lastBiggest = digits.lastIndexOf(biggest)

If both of those index-based values are equal, there's only one of the biggest number, and my search continues.

But if they are different, then the biggest number is that number twice!

if (firstBiggest !== lastBiggest) {
    sum += +(biggest.toString() + biggest.toString())
}

Next, preparing the other two possible outcomes:

if (firstBiggest !== lastBiggest) {
    sum += +(biggest.toString() + biggest.toString())
} else if (lastBiggest < digits.length - 1) {
    // Biggest digit is not the last digit
    // Find the subsequent biggest digit
} else {
    // Biggest digit is the last digit
    // Find the next biggest digit and proceed
}

For the second condition, I just need to find the highest number in the substring of digits after the highest number, and pair it with the highest number:

if (firstBiggest !== lastBiggest) {
    sum += +(biggest.toString() + biggest.toString())
} else if (lastBiggest < digits.length - 1) {
    sum += +(biggest.toString() + Math.max(...digits.slice(lastBiggest + 1)).toString())
} else {
    // Biggest digit is the last digit
    // Find the next biggest digit and proceed
}

The last condition is actually the same, but opposite.

By that I mean I need the substring of characters including all but he last one.

if (firstBiggest !== lastBiggest) {
    sum += +(biggest.toString() + biggest.toString())
} else if (lastBiggest < digits.length - 1) {
    sum += +(biggest.toString() + Math.max(...digits.slice(lastBiggest + 1)).toString())
} else {
    sum += +(Math.max(...digits.slice(0, lastBiggest)).toString() + biggest.toString())
}

Here is my full algorithm:

let part1 = input.split('\n').reduce((sum, line) => {
    let digits = line.split('').map(Number)
    let biggest = Math.max(...digits)
    let firstBiggest = digits.indexOf(biggest)
    let lastBiggest = digits.lastIndexOf(biggest)
    if (firstBiggest !== lastBiggest) {
        sum += +(biggest.toString() + biggest.toString())
    } else if (lastBiggest < digits.length - 1) {
        sum += +(biggest.toString() + Math.max(...digits.slice(lastBiggest + 1)).toString())
    } else {
        sum += +(Math.max(...digits.slice(0, lastBiggest)).toString() + biggest.toString())
    }
    console.log(sum)
    return sum
}, 0)

Thankfully, it generates the correct sum for the example input!

I now wonder if my conditions account for all of the possible scenarios that could example in my puzzle input.

...

They did!

My answer was correct!!!

Rock on.

Onward to Part 2.

Part 2

More digits, more problems

Now the challenges are:

• Which 12 digits do I pick?
• What order are they in?

That last challenge is important.

To see why, take this 6-digit line:

981891

Say I had to pick 5 numbers to keep.

Depending on which 1 I keep, I would get two different numbers. And I want the bigger number.

98891
98189

But wait, there's more!

The example lines are poor examples of the real challenge here.

My input lines are over 40 digits long.

The 12 digits that comprise the largest 12-digit number of possibly non-contiguous digits may appear anywhere in that string.

For example, this comes from my input:

1341524443834221222553325236443534253327533543493534348242333119334424249244524325448544522322512344

There are three 9s well before the end of the string

1341524443834221222553325236443534253327533543493534348242333119334424249244524325448544522322512344
                                               *               *        *

I will want to include all three 9s in the joltage number to maximize it's amount.

From there, I will want to include the next largest number, and so on, as long as there are enough digits that follow to amass 12 digits.

So, I could start it with 999855.

In fact, it could contain the last 5 and the remaining digits: 999855512344.

How could I programmatically - and performantly - deduce the same largest 12-digit number from that string?!

Maybe my Part 1 algorithm was on to something

One way to solve this is using recursion:

• Explore all continually reducing substrings
• Removing one number at a time
• Until arriving at a 12-digit string
• Update a global 12-digit number only when the new string is greater

But that is ridiculousness.

There's gotta be a better way, right?

After much thought, it turns out my logic from Part 1 may be highly applicable here, too!

Allow me to step through it and attempt to explain.

I'll stick with the same example from above:

1341524443834221222553325236443534253327533543493534348242333119334424249244524325448544522322512344

Recall that the answer I arrived at was:

999855512344

First, I look for the highest number. It's 9.

There are a few.

I target the earliest 9.

It has at least 11 digits after it, so it's a safe choice as the first of 12 digits.

I move to the next 9.

Same situation: 10 digits after it, so a safe choice.

Same for the last 9.

The next highest number is 8.

It, too, is a safe choice because there are at least 8 digits after it.

This continues with the 5s, of which there are 3.

Now for the tricky part.

The next highest number is a 4. There are 2.

But there are not enough digits that come after them to eventually create a 12-digit number.

The next highest number is a 3. There's 1.

Same problem.

Next is a 2.

Same problem.

Next is a 1.

There are enough digits after it to make it a safe choice.

In fact, there are exactly enough digts to make 12.

So I can select each subsequent digit and end this journey.

In summary, the algorithm:

• Knows how many digits are remaining to select
• Finds the earliest instance of the next highest digit
• Confirms whether there are enough digits to fill all remaining slots
• If so, it selects the current digit and it proceeds with the next iteration of the current number
• If not, it decrements the highest digit and continues the search
• And if there are exactly enough digits, it fills all remaining slots then and there

This has a real chance of working!

Time to try codifying it into a working program.

Writing my algorithm...very gradually

Setting the stage:

input.split('\n').reduce((sum, line) => {
    let picks = new Array(12).fill(null)
    let digits = line.split('').map(Number)
    let marker = 0
    return sum
}, 0)

I need

• An array with 12 slots to fill with the appropriate digits
• An array of digits made from the string
• And a way to track the remaining substring

Next, a while loop that will fill the array.

while (!picks.includes(null)) {
    // Continue filling each subsequent slot
}

How many slots are left?

let slotsLeft = picks.length - picks.indexOf(null)

Find the location of the next highest number:

while (!picks.includes(null)) {
    let slotsLeft = picks.length - picks.indexOf(null)

    let digitsLeft = digits.slice(marker)
    let biggest = Math.max(...digitsLeft)
    let firstOf = digitsLeft.indexOf(biggest)
}

If there are enough digits after the biggest digit to fill the rest of the array, slot it into the array and update the location from which to generate the next substring:

if (digitsLeft.length - firstOf >= slotsLeft) {
    picks[picks.indexOf(null)] = biggest
    marker += firstOf
}

That feels right. But is it?

I need to test it on an example.

...

I'm not seeing any evidence of the while loop running.

What's wrong?

Ooohhhhhhh...wow.

Look at that condition:

while (!picks.includes(null)) {}

It only runs when there are no null values in the final array!

That's my stopping condition, not my continue condition!

Exclamation point: removed!

Now I see it running.

Wow wow wow.

Now I see 12 9s when using the first example string.

That's obviously not right.

What's wrong?

Oh, I didn't account for the first digit in the substring being the next correct one.

When that's the case, it's index is 0 and marker doesn't increment.

To fix it, I'll use a ternary operation:

marker += firstOf > 0 ? firstOf : 1

Now I see the correct 12-digit number for the first example string!

But I don't see it move on to the next string.

Why not?

Ohhhh, because the next string has a 9 at the end, and I haven't written the condition for that yet.

This will require more tracking:

• Determine the highest number in the substring
• See if there are enough remaining digits if it is selected
• If not, remove that number as a possibility

I may need to avoid using Math.max(), since that will always find the highest number.

Instead, I may need to count down from 9 repeatedly until finding the next best number.

I don't like it, but it should work.

...

Well, after a lot of head-scratching about how to hone in on the best number, I wrote this:

let current = 9
while (true) {
    if (digitsLeft.includes(current)) {
        if (digitsLeft.length - digitsLeft.indexOf(current) < slotsLeft) {
            current--
        } else {
            break;
        }
    } else {
        current--
    }
}

• A manually-breaking while loop
• First checks for the current number in the string
• Then checks for sufficient remaining digits
• If either condition is false, decrement the number
• Otherwise, exit the loop because it found the right number

Then, proceed as normal:

picks[picks.indexOf(null)] = current
marker += digitsLeft.indexOf(current) > 0 ? digitsLeft.indexOf(current) : 1

I don't like the redundant code, but I can't save it into a variable outside the while loop.

Alas, my program generates correct numbers from each of the four example strings!

Will it do the same for some randomly selected strings in my puzzle input?

No. No it won't.

Why not?

Well, it appears to be duplicating some digits.

It looks to me like there's a problem with marker placement: it's not moving forward appropriately each iteration through the while loop.

After a lot of trial and error, I figured out where a + 1 was needed:

marker += digitsLeft.indexOf(current) > 0 ? digitsLeft.indexOf(current) + 1 : 1

And with that, it appears to be generating the correct 12-digit numbers from each string!

It may be time to try it on my puzzle input.

Running on my puzzle input

Running.

An answer appeared immediately!

And it is the correct answer!!

Woohoo!!!

That felt awesome.

What a fun challenge!

It took a ton of ruminating to arrive at a working algorithm.

And I'm so glad it paid off with the second gold star for the day.

Feels good to go into Day 4 with 6 gold stars.