Advent of Code day 11 was an example of a problem which gets exponentially harder as you do more iterations. Essentially there are a series of elements and functions are performed on those elements based on their state, including creating more elements. A similar problem was the Lanternfish problem of 2021. In this case 25 iterations were fairly trivial giving the solution to part 1, but part 2 asked for 75 iterations. By iteration 35 my computer was slowing to a crawl.

Producing the entire sequence would be impossible, but this problem just asks for the sum of all the elements. A careful examination reveals that the same numbers keep appearing in the sequence, so it is possible to reduce the number of calculations greatly by saving prior results in a cache and just reusing those results when the numbers come up again. This can be done in a function call that might have an expensive or recursive calculation behind it, but should always yield the same result with the same inputs. Adding such a cache is called memoization. I have used memoization before in procedural languages. Usually I create a dictionary or map of parameters or states to results. I just need to keep a pointer to that structure in each call of the function I am memoizing, and over time it will speed up the function by immediately returning results for values that have been seen before. An example I wrote in go can be seen in my solution to Advent of Code 2023 day 12.

The difficulty I encountered using Gleam is that all the data structures are immutable. I can use recursion to build a data structure, but it is tricky to traverse a tree of possibilities and continuously pass a modified cache back up through the call stack. Gleam is built to run on the Erlang virtual machine, and has libraries which take advantage of the Erlang Open Telecom Platform (OTP) which allows the spawning of processes that can send and receive messages. I can save the state of a cache in a process and send and receive updates from that cache using OTP messages. One simple way to take advantage of this is using a Gleam actor.

An actor is defined by a single function which is called when a message is received. The actor can respond to the message (if the sender provides a return mailbox) and can update its state in response to the message. This means I can use an actor as the agent of memoization in my program. I ended up separating this functionality into a small library within my Advent of Code project. The meat of the actor is its handler function which is called whenever it receives a message. It’s state is managed by a dict.Dict type. The stone_count_memoized makes use of this cache. My initial stab at this looked much less organized, but when I was discussing the problem on the Gleam discord I found out that someone had already written a library which does memoization called rememo. This library had such an elegant API that I decided to copy it. Unlike my library, this one actually makes use of Erlang’s ETS tables when targeting the BEAM, or mutable javascript references when targeting javascript. Although I like using an actor for this, the rememo library is definitely the right way to do it.