As usual the holidays really started to take off and I didn’t take time to work on updates. The upshot is I did finish Advent of Code 2024, but I didn’t finish Day 24 until the new year. However, before we get to that, let’s talk about some of the more interesting problems.

Day 14: Picture of a Christmas Tree?

Part 1 of day 14 was pretty straightforward. Essentially we follow the location of a number of robots with initial positions and velocities over a number of time steps, however part 2 threw in a significant wrinkle. Find the timestep when the robots form a picture of a Chritmas tree. Since we have no sample of what this should look like, it is tricky. I figured the image might have fairly sharp vertical and horizontal boundaries, so I decided to look for timesteps where the robots formed vertical and horizontal structures what were not randomly distributed. To do this I used an edge detector which scans 4 rows or columns at a time and then compares the number of robots in the two rows or columns on one side with the two columns on the other. Generally, if the robots are randomly distributed this should be a small number, however if there are vertical or horizontal structures there would be a few regions with very high numbers.

After some tuning I was able to find the instant where the robots formed a tree. My solution is available on github.

Day 17: Analysis of Code

This problem involved creating an interpreter to run programs for a three-bit computer with 8 instructions and 3 registers. The first part involved just running the program provided, but the second part required finding a register value that would result in the program outputting a copy of itself. There are too many possible register values to test each one, so some code analysis was required.

I noticed that my code took the value from the lowest three bits of the A register, manipulated it, mixed it with some other bits from the A register, shifted A right 3 bits, and output the result. The manipulations were hard to follow, but it would always depend on the lowest three bits of A and some other bits, if there were any, in register A.

I realized that the first byte of the program would depend only on the first byte of A. Then the second byte of the program would depend on the first two bytes of A, and so on. I could solve for A one byte at a time, moving to lower order bits as I matched more and more of the program. Since each byte in this computer is three bits, there are only 8 possibilities for each byte, and I just check each one to see which will provide the next match. The routines that do this matching are on github.

Day 19: Unnecessary Search Trie

This problem involved searching for the number of ways a sequence of colors could be made from a set of towels. The towels had various length subsequences on them. This reminded me of a search trie, so I implemented one to use as the basis of the search. A search trie combines sequences into a single stucture. Searching was done using the following steps:

1. Find any subsequences that match the beginning of the sequence returning a list of tuples of the matching subsequence and the remaining sequence to be matched.
2. Recursively count up the number of subsequences that match the start of that new list of remaining sequences until the remaining sequence length goes to zero.
3. Add up all the recursive subcounts and total them up.
4. Accelerate the process by memoizing the count for sequences, as sequences will often repeat.

I think my code is a little hard to follow here. I have the function find_possible_heads which matches any subsequences in the Trie to the head of the sequence. The function recurse_counter which combines the count of a list of sequences and calls the function cached_count on each of those sequences in turn to actually do the counting for individual sequences. All these functions end up recursively calling one another.

Day 21: I Need to Think About This

This problem was very tricky. The idea is that you must find the motions a robot finger has to make above a keypad in order to enter a code. Those motions are controlled by another robot with a directional keypad, which is controlled by another robot with a directional keypad, and so on. At each stage the number of button pushes increases exponentially, and there are multiple paths to get from one position to another. For example to move from the A key to the left key can be done by going down, then left two times, or by going left, down, and left. There are two rules to minimize the amount of motion required to order a robot to click a button. They are:

1. If there are multiple steps in one direction, do them as a group. This means don’t split up two left moves with a down move.
2. Start with motions that are furthest from the A key.

• Left takes three moves to get to from the A key.
• Down takes two moves to get to from the A key.
• Right and Up take one move.

This had me believing that Right and Up were equivalent, however it turns out that Right should be done before Up! The reason for this is that ordering a robot to take one step to the right key requires using the Left key, which is farther from the A than the down key. So the optimal ordering to move across the keypad is:

• Up then Right
• Left then Up
• Down then Right
• Left then Down

This is complicated by the fact that there is one square with no button and the robot is not allowed to move its finger into this square. If this is the case then you cannot choose the optimal ordering for that move.

My code is available on github for review.

Day 23: Growing from a Seed

This problem had a list of connections between nodes, and for the first part you had to find sets of three nodes all connected to one another. In order to do this, I just found cycles of length three that passed from a starting node back to the starting node hitting two other nodes on the way.

The second part was to find the largest set of nodes all connected to one another. It turns out that this could be done starting with the seeds of groups of three. For each node I found the set of all connected nodes. I then found the intersection of these sets for all the nodes in my group and removed the nodes currently within the group from the set. That left nodes which were connected to all the nodes currently in the group. I picked one of these nodes to add to the group and then did the process again until the intersection of connected nodes for all the nodes in the group only contained those nodes already within the group.

The next step is to purge from the starting seeds any group of three nodes that are a subset of the group. These seeds would grow to find the same group already found. I kept track of the largest group I found as I ran through all the seed groups and when I was done with the seed groups I had the largest set of nodes.

My code shows how I made extensive use of the set library for this problem, but using that library made the problem very easy.

Day 24: Days Without Progress

The first part of this problem is to simulate the outputs of a collection of logic gates, but the second part reveals this is a miswired circuit which is supposed to add two 44 bit integers to get a 45 bit integer. Some examination reveals that the circuit is made up of a half adder and 43 full adders, however four outputs are miswired and swapped with one another.

The half adder should contain two gates:

• \(x_{0}\ \mathrm{XOR}\ y_{0} \rightarrow z_{0}\)
• \(x_{0}\ \mathrm{AND}\ y_{0} \rightarrow c_{0}\) (carry bit)

The full adders should be a set of 5 logic gates:

• \(x_{N}\ \mathrm{XOR}\ y_{N} \rightarrow a_{N}\)
• \(x_{N}\ \mathrm{AND}\ y_{N} \rightarrow b_{N}\)
• \(a_{N}\ \mathrm{XOR}\ c_{N-1} \rightarrow z_{N}\)
• \(a_{N}\ \mathrm{AND}\ c_{N-1} \rightarrow d_{N}\)
• \(b_{N}\ \mathrm{OR}\ d_{N} \rightarrow c_{N}\) (carry bit)

which depend on the carry bit of the previous group (\(c_{N-1}\)). The last carry bit will go to the output \(z_{45}\).

I spent a few days thinking about how to do this, but in the end I decided to just use some editor macros to sort and rearrange the gates into groups and look for incorrect outputs. One thing I noticed was that all the swapped output groups are from the same full adder. Therefore it is sufficient to look for any output which is not going into the correct gate within that group.

I actually used this reddit post and a tremendous example from the Gleam discord to create my own solution which highlights how flexible pattern matching is with Gleam, allowing me to even match for partial strings within custom types.

On Gleam

I really like Gleam, and it is a good language for tackling Advent of Code. I still have trouble getting away from procedural thinking, but it is pretty amazing what you can do with this functional language. I thought some of the solutions looked very good and were easy to follow, but I also had a number of solutions whose implementation looks fairly tortured and hard to follow. There are some solutions I wrote which involve recursion over two lists which gave me a lot of trouble, and I am sure there are probably better ways to express those problems.

As I became more familiar with the language, I think I did get better at writing it. I think I would still reach for Go if I were writing a CLI tool as it compiles to a single binary and I like the templating system it offers, however I am interested in seeing how Gleam evolves.