Advent of Code 2024 - Day 11: Plutonian Pebbles

• Table of Contents
• Github
• Day 11

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

from advent import parse, ints, cache

@cache
def blink(stone, blinks):
    if blinks == 0:
        return 1
    elif stone == 0:
        return blink(1, blinks - 1)
    else:
        s    = str(stone)
        l, r = divmod(len(s), 2)
        if r == 0:
            return blink(int(s[:l]), blinks - 1) + blink(int(s[l:]), blinks - 1)
        else:
            return blink(stone * 2024, blinks - 1)

def solve(blinks):
    return sum(blink(stone, blinks) for stone in parse(11, ints)[0])

# ---------------------------------------------------------------------------------------------

assert solve(25) == 183484
assert solve(75) == 218817038947400

Solution

This is a typical “part 1 was easy, part 2 takes too long!” Advent of Code puzzle :)

My first attempt for part 1 was to create a list of stones, and then create a new list of new stones for each blink. This worked fine for part 1, but was too slow for part 2. Then I realized, I don’t need to create lists, I just need to count the stones, so my second solution was the code above without the @cache decorator. I thought that might be fast enough, but it wasn’t.

I started to write my own caching code, which is simple, but then I remembered Python’s @cache decorator from functools, so the only difference for part 2 was adding that decorator.

New Python Concepts

• @cache decorator
• divmod()

Conclusion

I thought Python did very well for this puzzle. Given my experience with Advent of Code, I had a hunch that part 2 was going to be identical to part 1, but would require a non-naive solution, so I probably should’ve anticipated that!