{
  "$type": "site.standard.document",
  "canonicalUrl": "https://unnecessary.tech/posts/aoc-2024-day11",
  "path": "/posts/aoc-2024-day11",
  "publishedAt": "2024-12-12T15:35:14.000Z",
  "site": "at://did:plc:jx54v4rmscfwzit7fmgz24ba/site.standard.publication/3mnrsqmzz3w2e",
  "tags": [
    "gleam",
    "programming"
  ],
  "textContent": "Advent of Code day 11 was an example of\na problem which gets exponentially harder as you do more iterations. Essentially\nthere are a series of elements and functions are performed on those elements\nbased on their state, including creating more elements. A similar problem was\nthe Lanternfish problem of 2021. In this\ncase 25 iterations were fairly trivial giving the solution to part 1, but part 2\nasked for 75 iterations. By iteration 35 my computer was slowing to a crawl.\n\nProducing the entire sequence would be impossible, but this problem just asks\nfor the sum of all the elements. A careful examination reveals that the same\nnumbers keep appearing in the sequence, so it is possible to reduce the number\nof calculations greatly by saving prior results in a cache and just reusing those\nresults when the numbers come up again. This can be done in a function call that\nmight have an expensive or recursive calculation behind it, but should always\nyield the same result with the same inputs. Adding such a cache is called\nmemoization. I have used memoization\nbefore in procedural languages. Usually I create a dictionary or map of parameters\nor states to results. I just need to keep a pointer to that structure in each\ncall of the function I am memoizing, and over time it will speed up the function\nby immediately returning results for values that have been seen before. An\nexample I wrote in go can be seen in my solution\nto Advent of Code 2023 day 12.\n\nThe difficulty I encountered using Gleam is that all the\ndata structures are immutable. I can use recursion to build a data structure,\nbut it is tricky to traverse a tree of possibilities and continuously pass a\nmodified cache back up through the call stack. Gleam is built to run on the\nErlang virtual machine, and has libraries which take advantage of the Erlang\nOpen Telecom Platform (OTP) which allows the spawning\nof processes that can send and receive messages. I can save the state of a cache\nin a process and send and receive updates from that cache using OTP messages.\nOne simple way to take advantage of this is using a Gleam actor.\n\nAn actor is defined by a single function which is called when a message is\nreceived. The actor can respond to the message (if the sender provides a\nreturn mailbox) and can update its state in response to the message. This means\nI can use an actor as the agent of memoization in my program. I ended up\nseparating this functionality into a small library\nwithin my Advent of Code\nproject. The meat of the actor is its handler function\nwhich is called whenever it receives a message. It's state is managed by a\ndict.Dict type. The stone_count_memoized\nmakes use of this cache. My initial stab at this looked much less organized, but\nwhen I was discussing the problem on the Gleam discord I found out that someone\nhad already written a library which does memoization called rememo.\nThis library had such an elegant API that I decided to copy it. Unlike my library,\nthis one actually makes use of Erlang's ETS tables when targeting the BEAM, or\nmutable javascript references when targeting javascript. Although I like using\nan actor for this, the rememo library is definitely the right way to do it.",
  "title": "Advent of Code 2024 - Day 11"
}