Advent of Code 2024, some notes

For four years, I tried to participate in the Advent Of Code challenge each December. While waiting for my Christmas gift, I lose myself in these puzzles which improve my skills in algorithms and help me discover new things.

I find the exercise very interesting, especially since it is possible to solve the problems with any programming language, or even with just paper and pencil. Basically, each puzzle provides an input, and the player must validate the puzzle by creating the machine that produces the output. Some use this challenge to learn a new language; in my case, I find it challenging enough to simply solve the problems with a language I already know. 😄

I found the 2024 puzzles harder right from the start of the challenge, I must certainly be lacking practice as these are problems that I generally don't encounter in my work as a front-end developer (sorry, vibe-front-end developer).

I couldn't get past the first 10 puzzles (it really starts to take me a long time to solve from the 10th or 12th puzzle over the past four years). However, I did note a few interesting things that I want to share and archive at the same time. So, this post is more of a note than an article to share with you. I will not go into detail about the puzzles, but I will share some code snippets that I found interesting and that I used to solve the problems.

All puzzles are available on Advent of Code 2024. You can also find all my solutions on GitHub.

Chaining approach

After completing a puzzle, I enjoy looking at the solutions of other participants. And that's precisely what serves as a school for me. I often discover much smarter ways than mine to solve the problem, both in terms of the logical approach and how the algorithm is organized.

I noticed that not all participants write their solutions in the same way. Some are very explicit, naming their functions, splitting the logic, and writing abstractions. Personally, I enjoy trying to solve problems with a Chaining approach, staying as much as possible within the main thread to avoid working outside the provided arguments or returned values. It could be compared to a functional programming approach in some ways.

Chaining Approach:

return fs
  .readFileSync(path.resolve(__dirname, filename), "utf8")
  .split("\n")
  .filter(Boolean)
  .map((e) => e.split(",").map((e) => parseInt(e)))
  .map((x) => x * 2)
  .filter((x) => x > 10)
  .reduce((acc, x) => acc + x, 0)

An "imperative way" to write the same code:

const data = fs
  .readFileSync(path.resolve(__dirname, filename), "utf8")
  .split("\n")
  .filter(Boolean)
  .map((e) => e.split(",").map((e) => parseInt(e)))

let result = 0
for (let i = 0; i < data.length; i++) {
  const x = data[i] * 2
  if (x > 10) result += x
}
return result

The second approach requires mutating a variable outside the loop's scope, which is, of course, valid. But I prefer to play the game of the single chaining approach as long as it is possible, maybe just because it looks pretty in the end and make it more concise. When it's not possible (and this is often the case), I try to stay functional, using pure functions, avoiding side effects and mutations.

Javascript is very permissive and sometimes it is tempting to use its weaknesses to go faster by making code golfing. Finally, what's also cool about this game is that we can do pretty much whatever we want to reach our goal.

Day 2

Day 2 is about to determine if a list of numbers is safe or unsafe according to a set of rules. I did not use the functions below to solve the problem, but they could have been used to make the solution more concise.

zip function

A zip function is a function that combines elements from two arrays using a provided combinator function. A curried zip function example:

const zipWith =
  <A, B, C>(f: (a: A, b: B) => C) =>
  (as: A[], bs: B[]): C[] =>
    as.map((a, i) => f(a, bs[i]))

// usage
const add = (a: number, b: number) => a + b
zipWith(add)([1, 2, 3], [4, 5, 6]) // [5, 7, 9]

All positive

Check if all numbers are positive in a list of numbers.

const allPositive = (numbers: number[]): boolean => numbers.every((n) => n > 0)

Day 3

Day 3 puzzle involves processing a grid of characters to identify patterns and calculate scores based on specific rules. Regex is needed And it's a good opportunity to learn more about it.

Search a pattern in a string

In this one, you need to use Regex to extract the selected pattern and get their position in the string.

const input = "abc123abc456abc"
const pattern = /abc/g
const matches = [...input.matchAll(pattern)]
console.log(matches) // [["abc", index: 0], ["abc", index: 6], ["abc", index: 12]]

In the puzzle context, extract all mul(x,x) occurrences in a string.

const input = "xmul(2,4)%&mul[3,7]!@^do_not_mul(5,5)"
input.match(/mul\(\d{1,3},\d{1,3}\)/g)

In the regex, d{1,3} means a digit with at least 1 and at most 3 digits.

match and matchAll

match returns an array with the first match and the groups
matchAll returns an iterator with all matches and groups

Day 6

Day 6 is about moving a "guard" inside a 2d matrix. The guard moves in 4 directions (up, down, left, right) and changes direction upon encountering obstacles. Count the visited coordinates until he leaves the area.

Parsing a 2D matrix

Parsing a 2D matrix is often required, as in this puzzle. We need to identify the coordinates of specific elements. Here's what the example input looks like:

....#.....
.........#
..........
..#.......
.......#..
..........
.#..^.....
........#.
#.........
......#...

The ^ symbol represents the starting position of the guard. Here's how to parse the matrix and obtain its coordinates. First, iterate through the columns y, then through the rows x within each column until the desired symbol is found.

const findGuard = (input: string[][]): [number, number] => {
  for (let y = 0; y < input.length; y++)
    for (let x = 0; x < input[y].length; x++)
      if (input[y][x] === "^") return [y, x]
}

Nothing complex from an algorithmic point of view; however, the challenge in this type of problem is not to get lost in reasoning and to organize your code well. This brings us back to a functional approach. By outlining the requirements, we achieve our segmentation:

const part1 = (input: string[][]): number => {
  // Get the guard coordinates
  const guard = findGuard(input)
  // Get the obstacles coordinates
  const obstacles = findObstacles(input)
  // Move the guard and get the visited coordinates
  const { visited } = moveGuard(guard, obstacles, input)
  // Return the number of visited coordinates
  return visited.size
}

This is a good example; we are not going out of the scope. The input (the matrix) is passed as a parameter to the function, and we do not modify the state of the input. It is used in child functions that return a result, which is then utilized by the previous function.

Day 7

Day 7, we are given equations with a target value and a list of numbers; insert + or * operators (in order, left-to-right evaluation, no reordering) to see if you can reach the target. More specifically, if the input is 3267: 81 40 27 we need to test:

3267 = 81 * 40 + 27 // true
3267 = 81 + 40 * 27 // false
3267 = 81 * 40 * 27 // false
3267 = 81 + 40 + 27 // false

if one of them is true, the entry is valid. So the problem is about to test all sign order possibilities:

With only one *:

* + + +
+ * + +
+ + * +
+ + + *

Then, with two *:

* * + +
* + + *
+ * * +
+ + * *
// ...

Explained like this, it seems to be easy, but in reality, it is not at all :) One of the stategy will be to use a cartesian product function to test all possible combinations. (I din't use it in my solution, I discovered it just after).

Cartesian Product

The Cartesian product (cross product) of two lists is the set of all pairs formed by combining each element of the first list with each element of the second list. In this problem, we need to test all possible combinations of two lists to find a pair that meets a condition.

const cartesianProduct = <A, B>(listA: A[], listB: B[]): [A, B][] => {
  const result: [A, B][] = []
  for (const a of listA) 
    for (const b of listB) 
      result.push([a, b])
  return result
}

// usage
const list1 = [1, 2, 3]
const list2 = ["a", "b", "c"]
console.log(cartesianProduct(list1, list2))
// Output: [[1, 'a'], [1, 'b'], [1, 'c'], [2, 'a'], [2, 'b'], [2, 'c'], [3, 'a'], [3, 'b'], [3, 'c']]

Day 8

Day 8 involves analyzing a grid to identify unique antinode locations created by antennas of the same frequency and calculating their total count within the map's bounds.

combinations

Test all unique combinations of two elements, excluding duplicates and reversed permutations. This is a subset of the pairs from the Cartesian product often referred to as combinations (or unordered combinations).

No duplicates
No reversed permutations

Enumerate all the elements above the diagonal of a table.

const list = [1, 2, 3, 4]
for (let i = 0; i < list.length; i++)
  for (let j = i + 1; j < list.length; j++) 
    console.log(list[i], list[j])
    // 1 2, 1 3, 1 4, 2 3, 2 4, 3 4

Day 10

In Day 10, we need to use a path finder. This is not the first time we've needed DFS or BFS to solve an Advent of Code puzzle. Each year, at least one of these algorithms is necessary. Sometimes it's possible to solve without them, using brute force, but this doesn't always work depending on the input size. And that's when we need to go back to basics.

Breadth-First Search

Adds each discovered node to a queue, ensuring nodes closest to the starting point are explored first:

Finds the shortest path (in an unweighted graph) using a queue: first in, first out
Uses a queue (FIFO: First In, First Out)

Depth-First Search

Recursively explores each branch completely before moving to the next branch, essentially going "deep" before going "wide".

Finds a path, any path
Uses a stack (LIFO: Last In, First Out)

Implementation

The implementation of the DFS and BFS algorithms is very similar. The main difference is that the DFS uses a stack (LIFO) while the BFS uses a queue (FIFO). In the example below, I used a stack to implement the DFS algorithm.

const run = (grid: number[][], start: [number, number]): number => {
  // possible directions in a 2D matrix
  const directions = [
    [1, 0], // Down
    [0, 1], // Right
    [-1, 0], // Up
    [0, -1] // Left
  ]

  // Stack for DFS (LIFO) or queue for BFS (FIFO)
  const stack: [number, number][] = [start]
  const visited = new Set<string>()
  visited.add(`${start[0]},${start[1]}`)

  let result = 0

  // loop until the stack is empty
  while (stack.length) {
    // For DFS, use pop() on the "stack" to remove the last element of the list;
    // for BFS, use shift() on the "queue" to remove the first element of the list
    const [y, x] = stack.pop()

    // Process the current cell
    result += grid[y][x]

    // Explore neighbors
    for (const [dy, dx] of directions) {
      const [ny, nx] = [y + dy, x + dx]

      // Check bounds and if the cell is already visited
      if (
        ny >= 0 &&
        nx >= 0 &&
        ny < grid.length &&
        nx < grid[0].length &&
        !visited.has(`${ny},${nx}`)
      ) {
        stack.push([ny, nx])
        visited.add(`${ny},${nx}`)
      }
    }
  }

  return result
}

Others path finding algorithms exist, such as Dijkstra's algorithm I discovered in 2021, Day 15. I have spend mutch time on it and written a low level implementation for any data structure.

Inspiration

I couldn't manage to go further this year, but I tell myself that it's okay as long as I learn something from it.

If, like me, you enjoy taking a look at others' solutions, I invite you to check out these repositories whose solutions have helped me discover new algorithms and strategies over the past few years. I could mention these ones: grgrdvrt, hugosaintemarie, polux, superguigui, and MAKIO135.