Finally, an application for my FSM library! Advent of Code 2024 day 11
We’ve finally completed 10 puzzles, surpassing my previous record (though I still have days 24 and 25 to tackle, and I’ll likely need to revisit day 12 for part two). Coincidentally, I was able to adapt my FSM library to solve day 11. While it’s not the most efficient solution, I’m eager to share it.
We begin by parsing the input, a seemingly simple list of space-separated numbers. As we’ve learned by now, a small input file size often hints at a more complex challenge elsewhere. Nevertheless, the parsing function is straightforward:
def parse(input: str) -> tuple[int, ...]:
return tuple(int(item) for item in input.strip().split(" "))Part 1
Let’s begin with a naive implementation, directly translating the puzzle’s description into code. This requires implementing the three transformation rules. In this puzzle, each stone is represented by the engraved number. The first rule we’ll implement is a function to split a stone if the number has an even number of digits:
def len_digit(number: int) -> int:
return floor(log10(number) + 1)
def stone_split(stone: int) -> tuple[int, int]:
assert len_digit(stone) % 2 == 0
return (
int(stone / (10 ** (len_digit(stone) / 2))),
int(stone % (10 ** (len_digit(stone) / 2))),
)The len_digit function, a technique we also used for day 7, calculates the number of digits in a number using the floor and log10 functions. This function is used by stone_split to determine if a stone should be split. The stone_split function splits the stone into two equal parts if the number of digits is even.
The first transformation rule applies only when a stone’s value is 0. In this specific case, the stone’s value is incremented to 1. To maintain consistency and simplify later processing, all transformation functions will return tuples. This is achieved using a decorator, as shown below:
def to_tuple(func: Callable[..., int]) -> Callable[..., tuple[int]]:
def inner(*arg: Any, **kwargs: Any) -> tuple[int]:
return (func(*arg, **kwargs),)
return inner
@to_tuple
def stone_increment(stone: int) -> int:
assert stone == 0
return 1The reason for having each transformation function return a tuple is to easily combine the results of applying the transformations to multiple stones. This allows us to represent the state of all stones after each “blink” (a complete set of transformations) as a single tuple. This will become clearer when we implement the blink logic.
Finally, the third transformation rule is to multiply the stone’s value by 2024. This rule applies only if neither of the previous rules apply (i.e., the stone is not 0 and does not have an even number of digits).
@to_tuple
def stone_multiply(stone: int) -> int:
return stone * 2024Again, this returns the result as a tuple.
Now that we have implemented the individual transformation rules, we combine them into a single stone_transform function. This function takes a stone's value as input and applies the appropriate transformation based on the rules defined previously.
def stone_transform(stone: int) -> tuple[int, ...]:
result = ()
if stone == 0:
result = stone_increment(stone)
elif len_digit(stone) % 2 == 0:
result = stone_split(stone)
else:
result = stone_multiply(stone)
return resultNow we can perform a blink to all the stones. For this, I want to introduce the pipe function from toolz. Similar to the pipe operator in Linux, the toolz.pipe function allows us to redirect the output of one function to the input of the next. For example, when you want to read the first few lines of the HTML source of a website, you download and print the source with
curl https://example.com/ | headIf curl and head were available as functions, the equivalent code using toolz.pipe would be:
from toolz import pipe
pipe("https://example.com", curl, head)While the curl | head example could be rewritten as head(curl("https://example.com")) in Python, this puzzle requires us to apply the same transformation repeatedly. While a reduce statement could achieve a similar result, I prefer this approach using pipe and repeat, which applies stone_transform to each stone for each blink:
from collections.abc import Iterator
from itertools import chain, repeat
def blink(stones: tuple[int, ...], iterations: int = 1) -> Iterator[int]:
return pipe(
stones,
*repeat(
lambda current: chain.from_iterable(
stone_transform(stone) for stone in current
),
iterations,
),
)Now we can assemble the solution for part 1, which asks for the number of stones after 25 iterations.
def part1(input: str) -> int:
return len(tuple(blink(parse(input), 25)))Those familiar with the puzzle may anticipate a potential contradiction within its description, which we will address in Part 2.
Part 2
The puzzle description states:
No matter how the stones change, their order is preserved, and they stay on their perfectly straight line.
However, both Part 1 and Part 2 only ask for the count of stones, not their order. This raises an interesting question: was the emphasis on preserving order a deliberate misdirection?
I’ll leave it to the reader to interpret the author’s comment on this.
For now, we’ll proceed with the assumption that the order is irrelevant. If this is the case, our only concern after each blink is the count of each distinct stone value. In essence, we need to aggregate the results of each blink and multiply the counts by the corresponding counts from the previous blink.
For example, if we previously had two stones with the value 2024, after one blink, they would become two stones with the value 20 and two stones with the value 24. We therefore have two of each of the new stone values.
To efficiently aggregate counts, I’ll introduce merge_with from toolz. This function merges multiple dictionaries. In the case of duplicate keys, it uses a provided function to combine the corresponding values. For example:
from toolz import merge_with
foo = {"meow": 1}
bar = {"meow": 2}
baz = merge_with(sum, foo, bar)
print(baz) # prints {"meow", 3}To implement the more efficient blink, we’ll replace the original lambda function:
lambda current: chain.from_iterable(
stone_transform(stone)
for stone in current
)This lambda function tracked the order of individual stones. Our new approach focuses solely on the counts of each distinct stone value. We’ll use a “stone-count mapping” — a dictionary where keys are stone values and values are their corresponding counts. For each blink, we transform the keys (stone values) and aggregate the resulting counts into a new stone-count mapping.
def blink_get_index(current: dict[int, int]) -> dict[int, int]:
return merge_with(
sum,
*(
{stone: count_current}
for stone_current, count_current in current.items()
for stone in stone_transform(stone_current)
),
)Using the blink_get_index function, we can now implement a much more efficient blink_to_count function that directly calculates the final number of stones:
def blink_to_count(stones: tuple[int, ...], iterations: int = 1) -> int:
return sum(
pipe(
Counter(stones),
*repeat(blink_get_index, iterations),
).values()With our efficient blink_to_count function, we can now easily calculate the number of stones after 75 iterations for Part 2:
def part2(input: str) -> int:
return blink_to_count(parse(input), 75)What about Genstates, the FSM library?
At the beginning of this post, I mentioned that this puzzle provides a good opportunity to showcase my FSM library, Genstates. If we represent the stone transformations as a state machine, the graph would look like this:
To demonstrate how Genstates could be applied to this puzzle, we’ll define the functions that would be used by the state machine to determine which transition to take. These functions act as guards or conditions for the transitions.
First, a check to see if a stone’s value is 0:
def check_is_zero() -> Callable[[int], bool]:
return lambda value: value == 0Second, a check to see if a stone’s value has an even number of digits:
def check_is_split() -> Callable[[int], bool]:
return lambda value: len_digit(value) % 2 == 0Third, a check to determine if the multiply transformation should be applied:
def check_is_multiply() -> Callable[[int], bool]:
return lambda value: not (check_is_split()(value) or check_is_zero()(value))These checks must be exhaustive, as the current design of Genstates only allows for a single transition to be taken at a time. This exhaustive checking contributes to the relative inefficiency of this approach compared to our count-based solution.
We can reuse the stone_split, stone_increment, and stone_multiply functions we defined earlier as the actions that occur when transitioning between states. With this in mind, we can define the state machine using Genstates:
from genstates import Machine
STATE_MACHINE = Machine(
{
"machine": {"initial_state": "start"},
"states": {
"start": {
"transitions": {
"to_increment": {
"rule": "(check_is_zero)",
"destination": "incremented",
},
"to_split": {
"rule": "(check_is_split)",
"destination": "split",
},
"to_multiplied": {
"rule": "(check_is_multiply)",
"destination": "multiplied",
},
}
},
"incremented": {"action": "stone_increment"},
"split": {"action": "stone_split"},
"multiplied": {"action": "stone_multiply"},
},
},
sys.modules[__name__],
)With Genstates, we can model the stone transformations as state transitions, effectively replacing our stone_transform function. Instead of:
stone_transform(0) # returns (1,)
stone_transform(10) # returns (1, 0)
stone_transform(3) # returns (6144, )We can use the Genstates STATE_MACHINE we defined earlier:
initial_state = STATE_MACHINE.initial
STATE_MACHINE.progress(initial_state, 0).do_action(0) # returns (1,)
STATE_MACHINE.progress(initial_state, 0).do_action(10) # returns (1, 0)
STATE_MACHINE.progress(initial_state, 0).do_action(3) # returns (6144,)To use this with our original, order-preserving blink logic, we need to pass the state machine instance to the blink function:
def blink(stones: tuple[int, ...], fsm: Machine, iterations: int = 1) -> Iterator[int]:
return pipe(
stones,
*repeat(
lambda current: chain.from_iterable(
fsm.progress(fsm.initial, stone).do_action(stone) for stone in current
),
iterations,
),
)We can now create a Genstates-based version of part1 that uses our state machine to perform the transformations:
def part1(input: str) -> int:
return len(tuple(blink(parse(input), STATE_MACHINE, 25)))It’s also possible to apply Genstates to our count-based approach from Part 2. This requires a slight modification to blink_get_index to incorporate the state machine and using partial to pass the state machine to the function. The updated functions are shown below:
from functools import partial
def blink_to_count(stones: tuple[int, ...], fsm: Machine, iterations: int = 1) -> int:
return sum(
pipe(
Counter(stones),
*repeat(partial(blink_get_index, fsm=fsm), iterations),
).values()
)
def blink_get_index(current: dict[int, int], fsm: Machine) -> dict[int, int]:
return merge_with(
sum,
*(
{stone: count_current}
for stone_current, count_current in current.items()
for stone in fsm.progress(fsm.initial, stone_current).do_action( # type: ignore
stone_current
)
),
)This Genstates implementation is primarily for my own amusement and testing purposes, as I’m the library’s developer. While not the most efficient approach for this puzzle, it provided a valuable opportunity to explore how Genstates could be applied to a “real-world” problem (even if that “world” is Advent of Code).
One significant factor contributing to the performance difference is the way Genstates handles transitions. The library’s design enforces that only a single transition can be taken at any given time. This means that all guard conditions (the check_is_zero, check_is_split, and check_is_multiply functions) must be evaluated, even if an earlier condition is already met. This prevents the short-circuiting behaviour that would be possible with a more direct implementation.
That wraps up my discussion of this Advent of Code puzzle. It was a fun one, with a clever bit of misdirection. Things have been a bit hectic with job applications lately, which is why I didn’t get to another puzzle last week, but I’m hoping to get back on track and discuss another one next week. Please feel free to reach out if you’re looking for developers.
