Advent of Code 2024 Day 11
Part 1
An exercise in mapping cycles
As shown, these numbers split and multiply like bunny rabbits!
Therefore, it seems like I may have luck tracking all pebbles out to 25 iterations.
But I expect Part 2 to look out hundreds or thousands of blinks.
So, it may be worth it to get ahead of that ask and try to map out different numbers' lineages.
Replacing pebbles
Rule #1: 0
becomes 1
if (num == 0) {
return 1
}
Rule #2: Evenly split even-digit numbers into two pebbles
else if (num.length % 2 == 0) {
return [num.slice(0, num.length / 2), num.slice(num.length / 2)]
}
Rule #3: Otherwise, multiply by 2024
else {
return num * 2024
}
Time to test on one number
First, setting expectations.
These should be the first 5 blinks for 0
:
0
1
2024
20 24
2 0 2 4
Debugging was fun, since each console.log()
showed me exactly where my errors were.
After fixing things, this is my working function:
function blink(num) {
let str = String(num)
if (num == 0) {
return 1
} else if (str.length % 2 == 0) {
return [+(str.slice(0, str.length / 2)), +(str.slice(str.length / 2))]
} else {
return num * 2024
}
}
The big fix is in the first else if
. I was incorrectly working with a number. I needed to convert it to a string.
The way I currently process five blinks is with a for
loop:
for (let i = 0; i < 5; i++) {
test = test.flatMap(n => blink(n))
console.log(test)
}
The use of flatMap
is important:
- Any time I split one pebble into two, it flattens the returned 2-item array into the two numbers that were inside
Time to test on the example inputs
Testing a single blink on the first input is...
...successful!
Testing six blinks on the second input is...
...successful!
Testing 25 blinks on the second input for the correct pebble count is...
...successful!
How about my input?
Will it finish running?
Will it generate the correct answer?
...
Yes and Yes!!!
Nice.
I'm still quite certain Part 2 will require some pattern identification to process a ton more blinks.
Part 2
When things double, 50 more is a lot
I'm not sure why I thought the blink amount would be way higher.
When running my program and logging the current iteration and pebble count:
- It gets sluggish at blink
35
- The count reaches the millions after
30
blinks - And 100M+ after
39
blinks - The default array object can't store many more items, so my algorithm stops running
Exploring my initial strategy before moving on
I am very curious:
- How often do numbers repeat?
- Could I catalog the next, say, five blinks for any given number?
- Would that even help boost performance?
Let's try building a catalog of numbers.
let nums = {}
Inside of my flatMap()
:
if (!(n in nums)) {
nums[n] = []
}
I then want to see how many numbers I add, and if that ever accounts for all pebbles:
console.log(
Object.keys(nums).length,
arr.length - arr.filter(el => el in nums).length
)
Running it shows me:
- Numbers are being added
- At a varying rate, often approaching a
0
difference between numbers in the catalog and all pebbles - Nothing conclusive, though
What if I just use 0
?
- After 16 blinks, 54 numbers are in the catalog and new no numbers are added beyond that
Intresting! So 0
has a finite scope of numbers generated.
And any of those 54 numbers only ever generate pebbles with those numbers on them.
But what about numbers outside those 54?
Ugh, it really depends.
I'm at a loss
I don't know how to come at this problem with a working strategy.
Every idea I have is squashed by the thought of how it might boost performance.
I'm stuck.
And I'm bummed.
But, I want to keep going.
So, off I go...with one gold star in hand.
Top comments (0)