Gift Shop

Advent of Code 2025 Day 2

Part 1

Optimizing a brute force algorithm

I don't yet recognize a pattern in the numbers to write a program that doesn't check every number.

But I do see a way to skip certain ranges, depending on a few characteristics:

• Skip any numbers containing an odd amount of digits. Those numbers can't have repeated sets of digits, since two of any number makes an even number
• Skip any numbers where the amount of changing digits is less than the amount of

How might I optimize a brute force algorithm?

I don't yet recognize a pattern in the numbers to write a program that doesn't check every number.

But I do see a way to skip certain ranges, depending on a few characteristics:

• Skip any numbers containing an odd amount of digits. Those numbers can't have repeated sets of digits, since two of any number makes an even number
• Skip any numbers where, when split in half, the second digit could never become a duplicate of the first

I originally understood invalid IDs to be digits where any digit could repeat once and the digit had to comprise only repeat digits.

I now see that an invalid ID must be made of two identical digits.

That should make this much simpler to solve.

Stepping through a few examples to plot out my algorithm

First up, 11-22.

This reveals the first challenge of checking every number in the range, including the bookends.

Step 1, confirm this could have an invalid ID:

11
- Length: 2 (even)

22
- Length: 2 (even)
- Largest unit that changes is in the 10s place: both digits can change

Are both numbers an odd length?
    If Yes, no possible invalid IDs
    If No
        Determine the largest unit that differs between the digits
            Consider doing something depending on whether it's less than or greater to half the length
                Compare the initial digits of each half of the larger digit
                    If any digits in the second half that are before the largest differing unit
                        No possible invalid IDs
                    If all digits that won't change are repeats
                        Proceed with checking each possible ID, skipping large ranges where possible

Putting that algorithm to the test:

11-22
Neither number is odd length
Largest unit is 10s place - maximum place
Safe to proceed with checking

Again:

95-115
One is an odd length
    Consider handling this with a range reducer that lowers or raises the odd length digit to match the even length digit
After doing that
95-99
Neither number is odd length
Largest unit is 1s place - not maximum place
Comparing 10s place: 9 to 9 (identical!)
Safe to proceed with checking

Again:

998-1012
One is an odd length
Increase odd to even length
1000-1012
Neither number is odd length
Largest unit that differs: 10s place
Comparing 1000s place: 1 to 1
Comparing 100s place: 0 to 0
Safe to proceed with checking

Again, with a number from my input:

86274-120443
One is an odd length
Increase odd to even length
100000-120443
Neither number is odd length
Largest unit that differs: 10000s place
Comparing 100000s place: 1 to 1
Safe to proceed with checking

As for the checking part of my algorithm...

Split apart and increment, am I right?

Invalid IDs are numbers where both halves are the same.

It should prove true that I could increment the lower half and compare to the other half for equality.

Doing this properly could save thousands of unnecessary checks.

I'll illustrate:

100000-120443

100 != 000
       +
100 == 100
  +      +

101 == 101

...

119 == 119

120120 > 120443

That was 20 invalid IDs among over 20k possible values.

That feels like optimization to me!

I feel confident I could codify this, too!

Summarizing the tasks in order

1. Compare lengths of each bounding number
2. Skip double-odd bounding number ranges
3. Adjust odd-even bounding number ranges to be even-even
4. Identify the largest unit/place that can change
5. Loop: spilt the number in half and increment each until out of range

That feels smart and doable.

Time to finally start coding!

Writing an algorithm

It all goes in a reduce()r:

input.split(',').reduce((counter, range) => {
    // All the important work
    return counter
}, 0)

Extracting the bounding numbers:

let [min, max] = range.split('-').map(Number)

Checking for varying lengths and correcting:

// Same length
if (min.length == max.length) {
    // Both odd length
    if (min.length % 2 == 1) {
        // Skip entire range
    } else {
        // Both even, proceed
        IDchecker(min, max)
    }
} else {
    // Different length
    // Adjust appropriate number to make both even
    if (min.length % 2 == 1) {
        // Increment min until its an even amount of digits
        // Achieved by changing it to the lowest number with a higher unit: NN -> 100
        min = +("1" + new Array(min.length).fill("0").join(""))
    } else {
        // Decrement max until its an even amount of digits
        // Achieved by changing it to the highest number with a lower unit: NNN -> 99
        max = +("1" + new Array(min.length - 1).fill("0").join("")) - 1
    }
    // Both even, proceed
    IDchecker(min, max)
}

As usual, I overlooked a few glaring errors.

Here's the ammended code snippet:

// Same length
if (min.toString().length == max.toString().length) {
    // Both odd length
    if (min.toString().length % 2 == 1) {
        // Skip entire range
    } else {
        // Both even, proceed
        counter += IDchecker(min, max)
    }
} else {
    // Different length
    // Adjust appropriate number to make both even
    if (min.toString().length % 2 == 1) {
        // Increment min until its an even amount of digits
        min = +("1" + new Array(min.toString().length).fill("0").join(""))
    } else {
        // Decrement max until its an even amount of digits
        max = +("1" + new Array(max.toString().length - 1).fill("0").join("")) - 1
    }
    // Both even, proceed
    counter += IDchecker(min, max)
}

What I did wrong:

• In JavaScript, I have to convert a number to a string to check its length
• I mistakenly referenced min when setting max
• I forgot I'll need to adjust counter with the result of calling my IDchecker() function

I'm now seeing exactly what I want in my logging of min and max that will be passed as arguments to my IDchecker() function call.

Examples:

Instead of:
95-115

I pass:
95-99

Instead of:
998-1012

I pass:
1000-1012

It may not seem like much of an optimization.

But it was fun to work through and build.

And I bet it will shave off some time.

Maybe it will even come in handy for Part 2!

Next up, checking for invalid IDs.

Writing IDchecker()

function IDchecker(min, max) {
    let tally = 0
    while (min <= max) {
        // Break min in half
        let str = min.toString()
        let len = str.length
        let left = str.slice(0,len / 2)
        let right = str.slice(len / 2)
        // Are they equal? Invalid!
        if (left == right) {
            tally++
            min = +((+(left) + 1).toString() + (+(left) + 1).toString())
        } else if (+right < +left) {
            // If right half is less, make both left
            // Example: 2120 -> 21 20 -> Next invalid is 2121
            min = +(left + left)
        } else if (+left < +right) {
            // If left half is less, make both one greater than left
            // Example: 2034 -> 20 34 -> Next invalid is 2121
            min = +((+(left) + 1).toString() + (+(left) + 1).toString())
        }
    }
    return tally
}

There's some kind of gross code to convert strings to numbers and vice versa.

But overall this feels optimized to skip large ranges of numbers, straight to the next invalid ID.

Correcting for one last major oversight

Per the instructions:

Adding up all the invalid IDs in this example produces 1227775554

My algorithm currently just counts how many invalid IDs there are.

Oops!

Thankfully, it's a simple fix.

From this:

if (left == right) {
    tally++
    min = +((+(left) + 1).toString() + (+(left) + 1).toString())
}

To this:

if (left == right) {
    tally += min
    min = +((+(left) + 1).toString() + (+(left) + 1).toString())
}

Instead of incrementing tally by 1, I increment it by the amount of the invalid ID.

Testing on both inputs

When I run my program on the example input, I see the expected outputs:

• Each invalid ID
• No valid IDs
• The correct sum

Now to run it on my input:

• All sorts of invalid IDs
• Seemingly no valid IDs
• A sum in hundred-billions

Everything feels good enough to submit this answer.

...

It's the correct answer!

Woohoo!!!

I'm so happy all this work to optimize an otherwise brute-force number-checking algorithm paid off!

What twist might Part 2 present?!

Part 2

Feels like this just got exponentially harder

Wow. Looking back now, Part 1 feels easy:

• If even digits, cut in half, adjust one half to match or exceed the other by one

But this? I feel like I'll have to employ several case-specific tactics to skip number ranges.

The best way to start is by diving in on an example.

Working through examples from my puzzle input by hand

The number range:

28750-44009

Using manual labor, it looks like invalid IDs are:

33333

How did I deduce that?

• The number's length is odd, can't split in half
• The number's length is prime, so it can only be split into equal parts of single digits
• The next number with equal digits is 33333
• The next number exceeds the higher bounday number

That was some specific logic - odd, prime - but fairly straightforward.

The next range:

407363-480868

Using manual labor, it looks like invalid IDs are:

407407
408408
......
444444
445445
......
454454
......
454545
......
455455
......
464464
464646
......
465465
......

How did I deduce that?

• Even number
• Length: 6
• Divisible by 6, 3 and 2
• Can change up to the 10,000's place
• Consider each next possible invalid id: 6 - 444444, 3 - 414141, 2 - 407407
• Proceed with lowest option until surpassing next lowest option: 413413 -> X - 414414
• Jump to the next lowest option: 414141
• Consider each next possible invalid id: 6 - 444444, 3 - 424242, 2 - 414414
• Proceed with lowest option until surpassing next lowest option: 423423 -> X - 424424
• Jump to the next lowest option: 424242
• Consider each next possible invalid id: 6 - 444444, 3 - 434343, 2 - 425425
• Repeat last three steps until surpassing the maximum boundary

Wow, look at that: I missed a ton of invalid IDs!

Is optimization worth the headache?

Though this algorithm seems like it will skip a lot of numbers, it also seems like a nightmare to write.

The numbers in my input are of lengths 1-10.

I would need a dictionary to map length to divisibility.

Something like this that I could run on each number:

{
    // length of number: length of equal parts
    1: [1],
    2: [1],
    3: [1],
    4: [1, 2],
    5: [1],
    6: [1, 2, 3],
    7: [1],
    8: [1, 2, 4],
    9: [1, 3],
    10: [1, 2, 5]
}

That could be simpler if I remove prime number lengths:

{
    4: [1, 2],
    6: [1, 2, 3],
    8: [1, 2, 4],
    9: [1, 3],
    10: [1, 2, 5]
}

What else will I likely have to account for?

• Determining whether and where to increment a portion of a number

That feels like a monumental, condition-based nightmare of a task.

All of this begs the question:

• Why don't I just brute force this challenge?

In other words, just check every possible number.

That just feels so wasteful, especially when I see ranges like these:

2424167145-2424278200

That includes only one invalid ID:

2424242424

An optimized algorithm could help avoid processing 100k numbers!

There are a few similar ranges like this!

Or this:

9945560-9993116

That doesn't appear to include any invalid IDs on account of:

• Seven digits
• Can only split at single digit numbers
• Only possible digit is 9
• 9999999 is out of range

Why include that if it doesn't contain an invalid ID for parts 1 or 2? Seems like I may be missing something.

Ugh, what a dilemna!

How many numbers will a brute force algorithm have to check?

I want to gauge performance.

input.split(',').reduce((sum, range) => {
    let [min, max] = range.split('-').map(Number)
    let checked = 0
    let curr = min
    while (curr <= max) {
        checked++
        curr++
    }
    return sum += checked
}, 0)

The answers I get:

• Example input: 106
• My puzzle input: ~1.7M

That's not bad at all.

I feel less afraid of building an every-number-checking algorithm now.

I just need to start coding

I think accounting for prime number lengths will be the easiest task to code for.

That's because I just have too split the stringified number and check whether every value matches the first.

Here's that code:

let part2 = input.split(',').reduce((sum, range) => {
    let [min, max] = range.split('-').map(Number)
    while (min <= max) {
        let str = min.toString()
        let len = str.length
        if (!(len in divisors)) {
            // prime number length
            if (str.split('').every(el => el == str[0])) {
                sum += min
            }
        } else {
            divisors[len].map(size => {
                // More complicated
            })
        }
        min++
    }
    return sum
}, 0)

Thankfully - and as expected - I see the correct numbers logged when I run my program.

Now for the more complex part: dividing into multiple portions.

I dove in head-first, then troubleshooted, and eventually arrived at this algorithm:

let part2 = Array.from(input.split(',').reduce((uniques, range) => {
    let [min, max] = range.split('-').map(Number)
    while (min <= max) {
        let str = min.toString()
        let len = str.length
        if (!(len in divisors) && len > 1) {
            // prime number length
            if (str.split('').every(el => el == str[0])) {
                console.log(min)
                uniques.add(min)
            }
        } else if (len in divisors && len > 1) {
            divisors[len].forEach(size => {
                // Build a nested array with groups of length 'size'
                let arr = []
                for (let i = 0; i < len; i += size) {
                    arr.push(str.slice(i, i + size))
                }
                // Check whether every item in a group is equal
                if (arr.every(el => el == arr[0])) {
                    console.log(min, arr)
                    uniques.add(min)
                }
            })
        }
        min++
    }
    return uniques
}, new Set())).reduce((a,b) => a + b)

Noteworthy snippets:

• The reduce() returns a Set() of unique numbers
• Since I need to further reduce() that Set(), I use Array.from() to spread the set's values out
• The while loop has two branches: first process prime-number lengths, then process lengths with divisors greater than 1
• Both branches require avoidance of single digit numbers
• In the second branch, I turn the array of divisors mapped to the number's length into arrays of equal length strings, then compare each string for equality to the first string. Only if all strings match do I attempt to add the number to the unique set of invalid IDs
• I need a Set() because for a number like 333333 I don't want to add it three times, once each for [3,3,3,3,3,3], [33,33,33] and [333,333]

Testing and celebrating

I ran it on my puzzle input twice.

The first time my answer was too high.

That's because I overlooked adding single-digit numbers.

The second time my answer was about 50 less.

And it was the correct answer!

Woohoo!!!

What a trip this challenge was.

I'm so glad I didn't attempt to optimize it.

That probably would have taken a ton more time and introduced loads of headaches.

What matters is I gave both parts my full brainpower, and came away with two gold stars!

This may have been my toughest Day 2 challenge yet out of all 10 years of AoC!

Can't wait to see what Day 3 has in store.

Please no shortest path nonsense. Not yet, at least.