Advent of Code 2024

· 1462 words · 7 minute read

The Advent of Code is one of the events that I look forward to every year. As usual, I had a lot of fun solving the problems this year.

A change in mindset 🔗

I was burnt out participating in last year’s Advent. I tried very hard to solve each problem on the day it was released. Juggling that and a day job was not easy. This year, I consciously decided against that approach. I made it clear to myself that it is a low priority project – I’ll work on the problems only if I feel like doing so. The results were good – despite having a very relaxing December, I managed to solve all of problems 1 to 19 and part 1 of problem 20 by Christmas morning.

Choice of language 🔗

Every year, I try to solve the Advent with a different programming language. Going through my repositories, I found the following languages from the past Advents:

This year, I was considering Go, Gleam, and Zig. However, because of stickers, I quickly decided to use TypeScript with Deno. I am very familiar with TypeScript, but I have not used the Deno runtime in any meaningful way. I was intrigued by the fact that Deno provides first-class support to TypeScript, which means it can run TypeScript programs without any additional library and build process (which is, to my knowledge, the case on Node). I explored using Deno for a personal project a while ago, but did not go with it because of incompatibilities with some of the libraries.

Overall, I had a pleasant experience using Deno to solve this year’s problems. I think the AoC-style problems work well with a statically-typed language, especially when I was refactoring the code between part 1 and part 2 of each problem.

Favorite problem 🔗

I have not read the problems 21 to 25 at the moment. My favorite problem so far is problem 17. The first part of the problem entails the building of a simple virtual machine to execute a program using a given initial state. The second part of the problem is the opposite – construct an initial state such the program returns a given output.

I first attempted a brute-force approach but quickly realized that the size of the search space is huge. In the end, I decided to study the given program to exploit the structure of the execution. I found that I could guess 3 bits at a time and each guess will constrain the value of up to another 3 bits, which massively reduces the search space.

Libraries 🔗

For the most part, I did not have to rely on any external libraries – the built-in JavaScript objects (such as Array, Map, Set, and RegExp) and functions (such as Math.min and parseInt) are sufficient. Some of the exceptions:

  • @std/data-structures: This is part of the Deno standard library. I pulled this library to use the binary heap as a priority queue.
  • immutable: Immutable provides efficient immutable data structures. I used this library when building recursive backtracking for problem 17 mentioned above. In the backtracking stage, we have to undo certain state updates. However, because part of an update to a 3-bit window was already done by the previous recursive step, we need to remember which of the 3 bits were actually updated in the current step. Using an immutable data structure made this simpler. Because the state was never mutated, the undo step was also not needed anymore. In theory, I do not need this library – I believe that making a shallow copy of the state should work too.

libaoc 🔗

If you have participated in the Advent before, you might be able to tell that some data structures and algorithms are used in many of the problems. I have always wanted to build a library (called libaoc) to provide these data structures and algorithms, but given that I move between languages every year, this is not easy to execute. Hence, libaoc remains a pseudo-library – one that is re-built every year in a new language.

By day 20, here are some of my favorite data structures and algorithms from this year:

Point and Grid 🔗

Point and Grid are really the MVPs of Advent of Code. A Grid is a 2D generalization of the arrays. While we index an array using integers, a Grid is indexed by a Point, which is really just a pair of integers. Some of the most-used methods:

  • Point.neighbors(): returns the neighbors of the point. The exact implementation changes with each problem, but it is usually the neighbors along the cardinal directions.
  • Grid.at(Point): returns the element at the given position in the grid.
  • Grid.isValidPoint(Point): checks if the point is within the bounds of the grid. This is often used together with Point.neighbors() to ensure that we don’t go off the grid.
  • Grid.forEach((T, Point) => void): this is the analog of Array.forEach and is used to iterate through every element in the grid.

CustomMap<K, V> and CustomSet<T> 🔗

In JavaScript, the built-in Map uses the SameValueZero equality to compare the keys. In most parts, it means that two values are considered equal only if they are === to each other (with some exceptions around +0, -0, and NaN). This is good for integers and strings, but bad for almost everything else since an object is === only to itself. For example:

const map = new Map<Point, number>();

const pt = new Point(1, 2);
map.set(pt, 10);
map.get(pt); // 10
map.get(new Point(1, 2)); // undefined

A common trick that I used is to serialize the keys to strings and used the serialization as the key in the map:

const map = new Map<string, number>();

const pt = new Point(1, 2);
const ptToString = (point: Point) => `${pt.i},${pt.j}`;

map.set(ptToString(pt), 10);
map.get(ptToString(pt)); // 10
map.get(ptToString(new Point(1, 2))); // 10

This works but it gets old very quickly. Hence, I formalized this as CustomMap<K, V>, which is really not a great name. A CustomMap<K, V> takes a key function to convert K to a string as input to its constructor. CustomMap<K, V> (largely) implements the same interface as Map<K, V>. Internally, its data is stored in a Map<string, [K, V]>. Roughly, this is how it is implemented and used:

class CustomMap<K, V> {
  private data = Map<string, [K, V]>();

  constructor(private keyFn: (key: K) => string) {

  }

  get(key: K): V | undefined {
    const keyStr = this.keyFn(key);
    return this.data.get(keyStr)?.[1];
  }

  set(key: K, value: V): CustomMap<K, V> {
    const keyStr = this.keyFn(key);
    this.data.set(keyStr, [key, value]);
    return this;
  }
}

const map = new CustomMap<Point, number>(
  (point: Point) => `${point.i},${point.j}`,
);

const pt = new Point(1, 2);
map.set(pt, 10);
map.get(pt); // 10
map.get(new Point(1, 2)); // 10

I have also used CustomSet<T>, which is the analog for Set<T> but with the same convert-to-string mechanism. Internally, it uses a CustomMap<T, boolean>.

once<T> 🔗

Again, not a great name. once<T> is a higher-order function that ensures that a given function is executed only once for each input as determined by a key function:

const logOnce = once(
  (point: Point) => console.log(point),
  (point: Point) => `${point.i},${point.j}`,
)

logOnce(new Point(1, 2)); // Logs (1, 2)
logOnce(new Point(2, 3)); // Logs (2, 3)
logOnce(new Point(2, 3)); // Logs nothing

Internally, once<T> serializes the input using the key function and check against a Set to see if it has seen that string before.

Show me the code 🔗

Let’s say we want to find the shortest distance from every cell in a maze to a given point. We will represent the maze as a Grid where a cell is accessible if its value is .. The target point is represented as a Point. The output should be a CustomMap<Point, number>, which associates every reachable point to its distance to the target. This is how I would implement a breadth-first search to solve this problem:

interface State {
  point: Point;
  distance: number;
}

function computeShortestDistances(grid: Grid, target: Point): CustomMap<Point, number> {
  const output = new CustomMap<Point, number>(
    (point: Point) => `${point.i},${point.j}`,
  );

  const queue: Array<State> = [];

  const enqueue = once(
    (state: State) => queue.push(state),
    (state: State) => `${state.point.i},${state.point.j}`,
  );

  enqueue({
    point: target,
    distance: 0,
  });

  while (queue.length > 0) {
    const { point, distance } = queue.shift()!;

    output.set(point, distance);

    point.neighbors()
      .filter((neighbor) => grid.isValidPoint(neighbor) && grid.at(neighbor) === '.')
      .forEach((neighbor) => enqueue({
        point: neighbor,
        distance: distance + 1,
      }));
  }

  return output;
}

Notice that the key function for enqueue considers only the point. Hence, during the traversal, we do not have to explicitly check if a point is enqueued before.

Closing thoughts 🔗

In the past, I was very involved in the competitive programming scene in Malaysia. I know how difficult it is to organize such an event. Mad props to Eric Wastl for pulling off yet another excellent Advent of Code.

advent-of-code javascript typescript