The strange part is that every time you blink, the stones change.
After a good night sleep, I woke up to read that we’re dealing with stones that change when you blink. My mind immediately went to the terrifying Doctor Who enemies Weeping Angels. Maybe their origin is in Plutonium pebbles?
Anyway, these stones so far haven’t been reported of killing any one so maybe blinking is safe. So despite the good advice from the Doctor, let’s blink.
This puzzle reminded me also of Day 9 of 2016 where the problems (and especially the challenge constraint) was very similar.
Read input
Today’s input is a single line with numbers separated by spaces:
1 2024 1 0 9 9 2021976Each number represents a stone.
def map_fn(line):
return [int(n) for n in line.split()]We split the line on white space and turn every number into an integer.
Easy part done.
Part 1
The stones change on each blink according to three rules:
- If the number is
0, it becomes1 - If the amount of digits is even, it splits (
2024→20and24) - Otherwise it is multiplied by
2024
All the other stuff in the description about them keeping their positions and being in straight line is just distraction.
The first idea might be to store the numbers in a list or dictionary and update their locations and values accordingly. By reading the descriptions, we learn that the number of stones becomes large real fast so that won’t be feasible.
If something is likely to grow exponentially, my Advent of Code experience tells me to go recursive.
Since no stone affects any other existing stones, we can look at each stone on their own, follow its splits and changes and keep track of how many stones exist at the end.
First, we need to keep track of the iteration we currently are and how many we are going to go through so we can have our base case:
if iteration == max_iteration:
return 1Once we reach the end, we record 1 for each stone.
Then, we codify the rules into three different branches of recursion:
First, if the stone is zero, we change it to 1:
if stone == 0:
return blink(1, iteration + 1, max_iteration)We give the next iteration the new number and we bump up the iteration count by one.
Second, if the stone has even number of digits, we split it:
stone_str = str(stone)
digits = len(stone_str)
if digits % 2 == 0:
mid = digits // 2
left = int(stone_str[:mid])
right = int(stone_str[mid:])
return blink(left, iteration + 1, max_iteration) + blink(
right, iteration + 1, max_iteration
)Here we needed to do a bit of int-to-string-back-to-int shenanigans to split the integer.
We calculate the length to see if its length is even. Then we get the mid point by dividing its length to 2.
Note
a//bin Python is integer division and means all the decimal points are chopped off from the result.
1//2results in0(0.5, chop off decimals) and4//2results in2(2.0, chop off decimals).
Using Python’s string slicing, we can split the text in two by taking everything until the mid point (not including mid point) with stone_str[:mid]) and everything from mid point (included) to the end with stone_str[mid:].
We then do the recursion to both of them and sum the number of stones each one turns into.
Thirdly, if neither of the two earlier rules apply, we multiply the stone with 2024:
return blink(stone * 2024, iteration + 1, max_iteration)To put all these together, our recursive function looks like this:
def blink(stone, iteration=0, max_iteration=25):
if iteration == max_iteration:
return 1
if stone == 0:
return blink(1, iteration + 1, max_iteration)
digits = len(str(stone))
if digits % 2 == 0:
left = int(str(stone)[: digits // 2])
right = int(str(stone)[digits // 2 :])
return blink(left, iteration + 1, max_iteration) + blink(
right, iteration + 1, max_iteration
)
return blink(stone * 2024, iteration + 1, max_iteration)We follow each stone to its final number, then collect all the counts back.
As we already learned, this leads to a lot of stones. If we look carefully at the rules, we notice that there will be a lot of operations that will repeat. Every 0 turns to 1, every 1 to 2024 and every 2024 to 20 and 24.
This means this is a prime case for caching. Caching is when we keep track of already calculated values and avoid repeating slow calculations later.
If we have a stone that reads 0, it will down the line end up becoming N number of stones with K iterations. We then know that every time we get a stone 0, it will lead to the same result if K is same.
We can keep track of these by storing the result of (0, iteration, max_iterations) and if we run into the same set of variables again, we skip the calculation and get the result from the cache.
In Python, we can use functools.cache. It does all of the bookkeeping for us.
Here’s how to use it:
from functools import cache
@cache
def blink(stone, iteration=0, max_iteration=25):
# Function body stays the sameWhat’s that @cache above the function definition? It’s a decorator and they are a fantastic piece of Python. Bite code! has a nice three-part Christmas themed article series about decorators that can work as a nice primer of the topic.
To calculate how many stones there are after 25 blinks, we do:
def part_1():
stones = read_input(11, map_fn)[0]
stone_count = 0
for stone in stones:
stone_count += blink(stone)
print(f"Part 1: {stone_count}")Part 2
In the second part, the only change is to increase the number of iterations from 25 to 75. So there will be a lot of blinking and waaaaay more stones. Like a lot more.
I got this for free. The only thing we need to change is to provide a new max_iteration:
def part_2():
stones = read_input(11, map_fn)[0]
stone_count = 0
for stone in stones:
stone_count += blink(stone, max_iteration=75)
print(f"Part 2: {stone_count}")Our code is already efficient as its recursive and it’s even better because it’s cached so the calculations are almost instantaneous.
We’re almost half way to 50. I’ve been having a great time so far.