What I learned doing Advent of code 2024

For the first time I was able to complete Advent of Code completely (and on time). It is a yearly challenge that will present a new puzzle every day from December 1st to December 25th. You can do it in any language you want as you are only required to provide the solution to the puzzle given your input, but you don’t have to actually submit code.

I love using AoC as a learning and practicing opportunity. Today I would like to share what I discovered during this year’s edition.

Little note : I am going to talk about Go in this post because that is the language I used, however you don’t need an advanced knowledge of the language to follow through. The only things you might need to know is that in Go, the slice type is a dynamic array and the map type is an associative array (like dictionnaries in Python for example)

1. Go’s generics

I was already familiar with how generics, can work in other languages. Basically, instead of giving a specific type to a function or a struct definition you can give a generic one. You can also specify constraints on which types should be allowed.

For example to define a Heap type that can work with different types:

type Heap[] []int // Specific implementation
type Heap[T Comparable] []T // Generic one

In any case, while I never really needed generics when working with Go at my job, it was really useful for AoC as it allowed me to define a Grid-like type that I could use throughout all puzzles.

type Grid[T any] struct {
	Nodes         map[Point]T
	Height, Width int
}

It included functions such as finding neighbors which is a VERY common pattern in AoC. All the memes on the r/adventofcode subreddit about 2D grids are a testament to that.

func (grid *Grid[T]) CarthesianNeighbors(point Point) iter.Seq[T] {
	return func(yield func(T) bool) {
		for _, dir := range CarthesianDirections {
			neighbor := point.Add(dir)
			if node, ok := grid.Nodes[neighbor]; ok {
				if !yield(node) {
					break
				}
			}
		}
	}
}

It is very useful because in all the puzzles you might have to represent very different data. With generics, no matter what data you want to work with, you can reuse the same function implementation.

While not really a concern for AoC, it is worth noting that this also does not have any performance penalty at runtime. Behind the scenes, the compiler will figure out on which type this function will be used on and automatically generate a copy of that function for each of those types.

2. Go’s iterators

Go is definitely not the best language to pick up for Advent of Code. While it’s a great tool for some use cases (servers or DevOps tooling for example), for Advent of code you want a lot of functions that works on containers such as slices and maps.

You often get an input in a form of a list, each item on this list must be parsed, some computation must be applied to deduce a value for each element and then you must filter out some outputs or take the sum or product of those outputs. Go does not have map, filter or reduce functions in its standard library.

Of course you can use loops, but that can make the code a little bit longer to write and to navigate. While I know that functional patterns are really not idiomatic in Go (probably due to to the lack of generics until recently), I wanted to try to build them myself to try out generics and iterators as they are a perfect fit for such use cases.

It can make some days really easier. For example here is my part 1 for day 22 :

func part1(input []string) int {
	deriveSecret := func(secret int) int {
		for range 2000 {
			secret = nextSecret(secret)
		}
		return secret
	}
	initialSecrets := functions.Map(slices.Values(input), functions.MustAtoi)
	results := functions.Map(initialSecrets, deriveSecret)
	return functions.Sum(results)
}

This code will simply parse every line in the input and apply a functions to convert strings to int (functions.MustAtoi). Then it will apply the deriveSecret function to each of these entries and sum them.

Iterators were a bit hard to wrap my head around following the official documentation so I’ll try to explain them.

Basically an iterator in Go is a function that takes another function as its argument (named yield, by convention). You then must apply this function to every element in the collection, BUT, you should stop if this function returns false.

So if you want to apply a function to every element you would write something like this :

// Map iterates a sequence by applying a function to each
// element in the input sequence
func Map[T any, U any](input iter.Seq[T], operation func(T) U) iter.Seq[U] {
	return func(yield func(U) bool) {
		for element := range input {
			if !yield(operation(element)) {
				break
			}
		}
	}
}

Another iterator that I wrote, “Pairs”, whose purpose is to take two sequences as input and form pairs by taking each time the next element in both sequences:

// Pair will make pair from two iterators and stop once
// the shortest is exhausted
func Pairs[T any](s1, s2 iter.Seq[T]) iter.Seq[Pair[T]] {
	return func(yield func(Pair[T]) bool) {
		next1, stop1 := iter.Pull(s1)
		defer stop1()
		next2, stop2 := iter.Pull(s2)
		defer stop2()
		for {
			v1, ok1 := next1()
			v2, ok2 := next2()
			if !ok1 || !ok2 {
			    break	
			}
			if !yield(Pair[T]{A: v1, B: v2}) {
				break
			}
		}
	}
}

You can do whatever operation you want inside the iterator function, you just need to call yield on each element unless it returns false. I’m glad that I took the time to learn more about how this concept works in Go.

2. Using profiling tools

At some point I started adding benchmarks to my solutions, just to know if what I did was okay in term of performance.

Now on day 12 I got my working solution pretty quickly. But when browsing the subreddit, I noticed that my runtime was particularly slow compared to what other users with similar setups were reporting. Here is what I had :

❯ go test -bench=.
goos: linux
goarch: amd64
pkg: advent-of-go/solutions/2024/12
cpu: AMD Ryzen 5 5600 6-Core Processor              
BenchmarkPart1-12             10         122588965 ns/op
BenchmarkPart2-12              9         136754725 ns/op
PASS
ok      advent-of-go/solutions/2024/12  2.724s

This means that my runtime was 136ms for part 2. Not necessarily terrible but I wondered if I could do better without changing my approach too much. So while I had no experience with it I started the go profiler just to see if I could get a hint as to what was slowing me down. Here is what I got :

I had to search a little bit to find out what this meant but basically I was spending a lot of time in two things :

• Accessing element in a map (which I used as the underlying type for working with 2D grids)
• Garbage collection

I didn’t really know how to solve that, maybe I was doing too much allocations, so I looked at my make calls. In Go, the make functions is used to allocate memory for slices and maps among other things. It was the perfect culprit. Here is what I wrote at some point :

    crops := make(map[ds.Point]bool, len(grid.Nodes))

The second argument of the make function is the amount of memory to allocate. Here the length of grid.Nodes was 19600 with my input, but in reality the crops map contained only about 100 elements.

In go, maps are backed by buckets. To store or access a key,value pair in the map, Go will hash the key of the element to find out which bucket holds that data. When I reserve enough space to store 196000 key,value pairs, Go will create a lot more buckets that will need to be garbage collected, which will take some time.

Changing this to :

    crops := make(map[ds.Point]bool, 0)

Made the program run almost 10x faster.

❯ go test -bench=.
goos: linux
goarch: amd64
pkg: advent-of-go/solutions/2024/12
cpu: AMD Ryzen 5 5600 6-Core Processor              
BenchmarkPart1-12             96          11678739 ns/op
BenchmarkPart2-12             78          14791988 ns/op
PASS
ok      advent-of-go/solutions/2024/12  2.306s

Lesson learned : Trying to size correctly for maps is good, but overshooting by such a large margin is a mistake. I will consider this more carefully in the future.

3. Recursion and Memoization

On some days, like day 19 and day 21 the part 2 requires to explore a much bigger solution space than in part 1. So using the same approach usually won’t work if you want an answer before the end of the universe.

There is a technique that is relatively simple to use and can help in those case and that is : Memoization

Memoization is a technique that makes perfect sense once you know it, but back when I started doing AoC, I did not really think about it. Basically the idea is that you want to store the result of expensive computations. Here is what it can look like in practice. I’ll take the day 19 as an example so you might want to skip this part if you plan to do it at a later date.

On that day you were given a list of string such as gbbr and a list of pattern you could use to make up that string : r, wr, b, g, bwu, rb, gb, br. The task was to find all of the possible way to make each string using only the pattern you were given.

When you think about it, you may realize that you can divide this problem into smaller sub-problems which makes it a perfect candidate for a recursion. Which is the idea of calling a function inside itself, the process is as follows :

1. Try to find all the pattern that can be used to make the string, here we have gb and g
2. For each pattern that matches try to solve the sub-problem where the pattern is removed and sum those values, here this is bbr and br

If we apply this process we can find that there are two ways to do bbr (b,br and b,b,r) and two ways to do br (b,r and br). That makes 4 in total. Here is the code that does that

func possibleOptions(patterns []string, design string) int {
	sum := 0
	for _, pattern := range patterns {
		if pattern == design {
			sum += 1
			continue
		}
		if strings.Index(design, pattern) == 0 {
			var result, count int
			var cached bool
			subDesign := design[len(pattern):]
			result = possibleOptions(patterns, subDesign)
			sum += result
		}
	}
	return sum
}

You may have noticed that we found how many combination exists for br twice. But under no circumstances would the result for that substring change. So instead of computing this every time, we can just store this in a map. And use this in our function

var cache map[string]int

func possibleOptions(patterns []string, design string) int {
	sum := 0
	for _, pattern := range patterns {
		if pattern == design {
			sum += 1
			continue
		}
		if strings.Index(design, pattern) == 0 {
			var result, count int
			var cached bool
			subDesign := design[len(pattern):]
      // Avoid computation if we already know the result
			if count, cached = cache[subDesign]; cached { 
				result = count
			} else {
				result = possibleOptions(patterns, subDesign)
			}
			sum += result
		}
	}
  // Save the result
	cache[design] = sum
	return sum
}

In general recursion is a very good way to tackle problems that can be easily divided in sub-problems like this one. You can always write a recursive function in an iterative way, but I find that depending on the problem structure, recursion makes it easier to reason about.

As for memoization, the structure is often the same so it’s a good tool to keep in mind when an AoC problem is taking too long to solve.

4. Thought process

I’ve now done almost two events worth of puzzle (20 days in 2023 and the 25 in 2024). So I developed habits, some of which really helped me in the long run :

• Read the problem carefully : I don’t know how many times I’ve misread the instructions and lost a lot of time because of that.
• Set-up tests with the provided examples : The small example provided in each puzzle are smaller and easier to reason about. And a good proportion of the time, if you get the correct answer for these examples, you will get the correct answer for the puzzle.
• Don’t try to do part 2 before part 1 : When I was doing my first puzzles I would always try to anticipate what part 2 could be and this would often make me write more complicated code for part 1 which more often than not was more difficult to troubleshoot, even for part 2. So now I’m solving the problem for part 1, even if it seems unoptimized and not scalable. This will allow me to test my assumptions about the problem quicker and worry about optimizing it only if needed.
• Look for help : On day 21 and 24 part 2 I had to see what others were doing as I was really stuck. And while it’s gratifying to solve the puzzle without guidance, it’s not necessarily worth it staying stuck for hours (especially if you’re short on time like I was). The r/adventofcode subreddit is a really great place to ask for help or to see what others are doing.

Closing words

Doing the Advent of Code was a good excuse to write some Go and learn some stuff while also having fun. I don’t have that many opportunities to use Go at my current job so it was really refreshing. That’s the thing about AoC, it’s there, a lot of people are solving it as well, and you can use it for whatever reason such as discovering a new language, challenging yourself or just have some fun on the first few days.

If you did AoC as well I hope you enjoyed it as much as I did, and if you didn’t I encourage you to take a look.

Thanks for reading. Don’t hesitate to give me your feedback on this article on my Bluesky: @dhawos.bsky.social.

See you next time.