Finally, an application for my FSM library! Advent of Code ay 11

This Advent of Code puzzle presented a fascinating challenge, cleverly disguised within its seemingly simple premise. My solution explored multiple approaches, highlighting the trade-offs between efficiency and the elegance of employing a Finite State Machine (FSM) library.

The puzzle involved manipulating a sequence of numbers representing stones, applying three distinct transformation rules based on the number's properties (value, number of digits). Initially, I implemented a naive solution directly translating the rules into code. This involved functions to split even-digit numbers, increment zeros, and multiply others by 2024. These transformations were chained together using toolz.pipe and itertools.repeat to simulate the "blink" process—repeated application of the transformations. The solution for Part 1, requiring 25 blinks, was straightforward.

However, the puzzle's description subtly hinted at a potential optimization. While emphasizing the preservation of stone order, both parts only requested the count of stones after the blinks. This observation led to a more efficient approach. Instead of tracking individual stones, I aggregated their counts using toolz.merge_with, directly calculating the final stone count after each blink. This count-based solution significantly improved performance, especially for Part 2's 75 blinks.

For illustrative purposes (and to test my own library), I also implemented the solution using my FSM library, Genstates. This involved defining guard conditions (functions checking for each transformation rule) and actions (the transformation functions themselves). Genstates allowed modeling the stone transformations as state transitions. While this approach provided a clean representation of the problem's logic, it proved less efficient than the count-based method due to the library's design, which doesn't allow short-circuiting of condition checks. The exhaustive nature of checking all conditions in each step impacted performance.

The comparison between the naive, count-based, and FSM-based solutions highlighted the importance of choosing the right algorithm and data structures for optimal performance. The count-based approach clearly outperformed the others, especially for a large number of iterations. The FSM implementation, while elegant, served mainly as a demonstration of Genstates' capabilities.

The puzzle's subtle misdirection regarding stone order added an interesting layer of complexity, prompting reflection on the importance of carefully considering all aspects of a problem's description.

A very cryptic illustration generated by Microsoft Copilot

State machine diagram illustrating the stone transformations.

The author concludes by mentioning the time constraints imposed by job applications, highlighting the real-world pressures that often influence coding practices and project choices.

The above is the detailed content of Finally, an application for my FSM library! Advent of Code ay 11. For more information, please follow other related articles on the PHP Chinese website!