Advent of Code 2024 | Writing Developer

As in previous years, from December 1st to 25th, the Advent of Code took place — a coding competition in which a new puzzle is revealed daily and solved through programming. Each puzzle is divided into two parts, and each correct answer earns a gold star. With 25 puzzles, the maximum is 50 stars.

I first attempted it in 2020 but abandoned it after a few days. This year, however, I decided to be systematic and collect as many stars as possible. I set myself some personal rules:

No competing in the leaderboards to preserve my sanity.
Use Rust as the sole programming language to solve the puzzles.
Try to write idiomatic code and embrace functional programming concepts (after all, I come from a Scala background).

By the end, I earned 43 stars out of 50. The remaining puzzles would have taken too much time, which I preferred to spend elsewhere.

You can find the code for all solved puzzles (with example inputs) in this repository: https://github.com/boh717/advent-of-code-2024/.

Let’s go! 🏃

Day 1

The first day is always the simplest, and there are many ways to solve it. The first idea that came to mind was using a Min Binary Heap — a data structure that ensures the smallest element is always at the top. Of course, another approach could have been loading each list into a vector, sorting it, and then using zip() to pair up the elements. Either way, my approach worked.

The second part, however, required counting the occurrences of elements, and the only sensible choice was to use a Hashmap.

Day 2

The task for Day 2 was to verify whether sequences of numbers met specific criteria. Each sequence had to either increase or decrease, and each number had to differ from the previous one by at least 1 and at most 3.

The solution was straightforward: iterating through all reports and filtering out the invalid ones.

fn is_report_safe(levels: &Vec<u32>) -> bool {
    are_adjacent_levels_safe(&levels)
        && (levels.is_sorted_by(|a, b| a < b) || levels.is_sorted_by(|a, b| a > b))
}

fn are_adjacent_levels_safe(levels: &Vec<u32>) -> bool {
    levels
        .windows(2)
        .map(|w| is_permitted_adjacency(w[0], w[1]))
        .fold(true, |acc, e| acc && e)
}

fn is_permitted_adjacency(left: u32, right: u32) -> bool {
    let adj = left.abs_diff(right);
    1 <= adj && adj <= 3
}

The second part stated that, in some cases, removing just one number would make the sequence valid. There are undoubtedly more efficient solutions than mine, but using brute force with short-circuiting was fast enough.

Day 3

The day started with regular expressions! A simple regex was enough to extract well-formed multiplication instructions for the first part.

I also used a regex for the second part, but it took more effort to make it work correctly. It was crucial to consider the wildcard’s laziness and construct the regex to match across multiple lines.

    let enablers = RegexBuilder::new(r"(?s)don't\(\)(.*?do\(\)|.*$)")
        .multi_line(true)
        .build()
        .unwrap();

Once I had a working regex, I used it to remove the superfluous parts, and boom! It was solved!

Day 4

It was time to search for the word XMAS in all directions within a 2D input. To avoid out-of-bounds issues, I loaded the puzzle into a HashMap and relied on get() to check whether I was stepping out of bounds.

The solution was simple: whenever I encountered an X character, I checked in all eight directions (horizontal, vertical, and diagonal) to see if I could form the word XMAS.

The second part was similar but faster since it only required checking the diagonals (although the code isn’t the prettiest, in my opinion).


fn right_diagonal(
    line_index: usize,
    column_index: usize,
    matrix: &HashMap<(usize, usize), String>,
) -> bool {
    let (diagonal_up_right, diagonal_down_left) = (
        matrix.get(&(line_index - 1, column_index + 1)),
        matrix.get(&(line_index + 1, column_index - 1)),
    );

    (diagonal_up_right.is_some_and(is_m) && diagonal_down_left.is_some_and(is_s))
        || (diagonal_up_right.is_some_and(is_s) && diagonal_down_left.is_some_and(is_m))
}

fn left_diagonal(
    line_index: usize,
    column_index: usize,
    matrix: &HashMap<(usize, usize), String>,
) -> bool {
    let (diagonal_up_left, diagonal_down_right) = (
        matrix.get(&(line_index - 1, column_index - 1)),
        matrix.get(&(line_index + 1, column_index + 1)),
    );

    (diagonal_up_left.is_some_and(is_m) && diagonal_down_right.is_some_and(is_s))
        || (diagonal_up_left.is_some_and(is_s) && diagonal_down_right.is_some_and(is_m))
}

Day 5

Today’s problem was about sequences that needed to be ordered according to precedence rules. The function is_valid_update checks for each element that all subsequent elements comply with the imposed rules.

fn is_valid_update(update: &Vec<String>, rules_set: &HashSet<String>) -> bool {
    update.iter().enumerate().all(|(i, e)| {
        let (_, subsequence) = update.split_at(i + 1);
        is_subsequence_valid(e, &subsequence.to_vec(), rules_set)
    })
}

fn is_subsequence_valid(
    head: &String,
    subsequence: &Vec<String>,
    rules_set: &HashSet<String>,
) -> bool {
    subsequence
        .iter()
        .all(|e| rules_set.contains(&format!("{}|{}", head, e)))
}

Interestingly, using a simpler implementation of is_valid_update still produces the correct result:

- fn is_valid_update(update: &Vec<String>, rules_set: &HashSet<String>) -> bool {
update.windows(2)
.all(|pair| rules_set.contains(&format!("{}|{}", pair[0], pair[1])))
}

However, I believe this is just a coincidence because the official description doesn’t mention pairs:

The first rule, 47|53, means that if an update includes both page number 47 and page number 53, then page number 47 must appear at some point before page number 53. (47 doesn’t necessarily need to be immediately before 53; other pages are allowed in between.)

Day 6

Day 6 was the first puzzle where I felt the need to use types to make my life easier later on.

The first part was pretty straightforward. The second part required identifying positions that caused the guard to enter an infinite loop. I opted for a dirty workaround: I considered it an infinite loop if the guard didn’t leave the map after 10,000 iterations.

Unsatisfied, I implemented a smarter solution that tracked the guard’s position and state. Ironically, this solution is at least twice as slow!

// The smarter and slower solution
fn is_infinite_loop(map: &HashMap<Coordinate, Status>, initial_guard: Guard) -> bool {
    let mut current_guard = initial_guard;
    let mut states: HashSet<Guard> = HashSet::new();
    states.insert(current_guard);

    while let Some(next_cell) = get_next_cell(&current_guard, &map) {
        current_guard = move_guard(current_guard, next_cell);
        if !states.insert(current_guard) {
            return true;
        }
    }
    return false;
}

Day 7

After a week of puzzles, we encounter recursion for the first time! This solution has nothing particularly special except that I had to use u64 for the result due to the large numbers generated by the multiplications.

Day 8

I found the description of this puzzle very confusing—it took me a while to fully understand it. The code isn’t particularly special; I followed the instructions to get the result. I used a more imperative rather than a functional style, as handling this way felt simpler.

Day 9

Back to the ’90s with a puzzle inspired by defragmentation! While working on the examples provided, I didn’t account for IDs with multiple digits. Once I realized this, I used a Vec<Vec<String>> to ensure sequences like 1010 would be interpreted correctly as two 10s rather than one, zero, one, zero.

I went crazy trying to get the indexes and conditions right. Again, I used a more imperative style rather than a functional one.

Day 10

A reasonably simple day—recursion to the rescue again! I had to be careful with the correct termination conditions since I got a lovely stack overflow.

The second part was easier: it was just a matter of relaxing one constraint!

Day 11

The first part of this day was a huge trap! Since I didn’t want to modify the vector in place, I decided to generate a new sub-vector at every “blink” and flatten everything at the end. This certainly wasn’t the most efficient solution due to all the allocations, but it worked and was very concise:

// First solution I tried, good for part 1, impossible for part 2
fn main() {
    let content = std::fs::read_to_string("src/puzzles/puzzle-day11.txt").unwrap();

    let stones_number_1 = part1(content.clone());

    println!("After 25 blinks, I have {:?} stones", stones_number_1);
}

fn part1(content: String) -> usize {
    let stones: Vec<u64> = content
        .split_whitespace()
        .map(|c| c.parse::<u64>().unwrap())
        .collect();

    (0..25)
        .fold(stones, |stones, _| stones.iter().flat_map(blink).collect())
        .len()
}

fn blink(n: &u64) -> Vec<u64> {
    match n {
        0 => vec![1],
        n => get_even_length(&n)
            .map(|(s, length)| {
                let (first, last) = s.split_at(length / 2);
                vec![first.parse().unwrap(), last.parse().unwrap()]
            })
            .unwrap_or_else(|| vec![n * 2024]),
    }
}

fn get_even_length(n: &u64) -> Option<(String, usize)> {
    let s = n.to_string();
    let length = s.len();

    if length % 2 != 0 {
        return None;
    }

    Some((s, length))
}

However, increasing the number of iterations to 75 in part 2 made this method unusable due to its space complexity and execution time. I had to change my strategy and use a Hashmap instead.

Day 12

Day 12 marked a milestone in my adventure: I hit half of the competition, but it was also the first puzzle for which I only solved the first part.

I identified the garden regions and calculated their area and perimeter using a code that I didn’t like. For the number of sides required in the second part, I would have needed to introduce the concept of direction changes (since a side corresponds to a corner). I couldn’t find a quick and direct way to implement this with my current code, so I gave up. Too bad.

Day 13

Remembering the trap from two days earlier, this puzzle made me think carefully before rushing to write a solution.

It turned out that the puzzle could be solved with a system of two equations with two unknowns, and the suggestion of “100 iterations” in the description was a red herring. Approaching the problem this way meant that the second part required practically no changes.

Day 14

Modulo operation is the show’s star today, allowing me to quickly solve the first part of the puzzle.

However, there was a slight problem: I initially used the % operator, but since the calculations also involved negative numbers, I had to switch to rem_euclid to get the correct result.

The second part was unexpected: find the iteration where drones draw a Christmas tree on the map. I peeked at some advice on Reddit, and it turned out the solution was to find a configuration of drones where each one was in a different position. See image here.

Day 15

Like other puzzles, this one required us to track a robot’s movements. The biggest difference was that the robot could push boxes on the map—even multiple boxes in a single move—as long as they were in a line and there was an empty space to move into.

Since moving multiple boxes would require updating multiple positions for every move, I moved the first box to the first available empty space, which did the trick for the first part.

However, this approach didn’t help in the second part, where the boxes became twice as large, occupying two coordinates each. It was late at night, and I reluctantly decided to skip the second part.

Day 16

Today’s puzzle involved applying Dijkstra’s algorithm and being careful about neighbors’s weights. I used the pathfinding crate to speed things up, and the first part went smoothly.

For the second part, I used Yen’s algorithm to find the k-shortest paths while keeping track of the tiles included in those paths. I set k iteratively until no new tiles were found in the new paths. While this wasn’t the most efficient solution, it worked!

Day 17

The first part was fun and relatively straightforward. The second part required more thought, as brute-forcing wasn’t feasible due to the high number to compute.

Analyzing the output, I discovered that the program generation had a pattern that could be exploited. Specifically, the register starting value could be increased by multiplying it by 8 every time the correct output was found.

0 - 0
1 - 0
2 - 0
3 - 0
4 - 0
5 - 0
6 - 0
7 - 0
8 - 1,0
9 - 1,0
10 - 1,0
11 - 1,0
12 - 1,0
13 - 1,0
14 - 1,0
15 - 1,0
16 - 2,0
17 - 2,0
18 - 2,0
19 - 2,0
20 - 2,0
21 - 2,0
22 - 2,0
23 - 2,0
24 - 3,0

Day 18

Surprisingly simple for Day 18. I reused Dijkstra’s algorithm from Day 16 for the first part. For the second part, I didn’t do anything exciting: I corrupted one byte at a time and reused Dijkstra’s algorithm repeatedly until no valid path was found.

Day 19

The problem was straightforward, and Part 1 was solvable without memoization. Part 2, however, required it.

The fun part was that I initially used u32 for the result, and I couldn’t understand why the solution was wrong. Only after some thinking did I realize that the result overflowed due to the huge number. Switching to u64 fixed the issue and solved the puzzle 🤦

Day 20

The first solution for Part 1 involved tracking internal walls, removing them one at a time, running Dijkstra’s algorithm, measuring the results, and restoring the wall. I got the correct result, but it was unsurprisingly slow (~9 seconds).

Before moving to the next part, I refactored this approach and considered only walls adjacent to the optimal path, skipping unnecessary checks. This reduced execution time significantly to ~1.2 seconds.

fn part1(
    track: &HashMap<Coordinate, Status>,
    internal_walls: &HashSet<Coordinate>,
    start: Coordinate,
    end: Coordinate,
    picoseconds_to_save: i32,
) -> u64 {
    let mut track_copy = track.clone();
    let initial_path = dijkstra(
        &start,
        |c| get_successors(c, &track),
        |end_coord| *end_coord == end,
    )
    .unwrap();
    let initial_score = initial_path.1;
    let optimal_path = initial_path.0;

    let mut distances: HashMap<Coordinate, u32> = HashMap::new();
    let mut current_dist = 0;
    for coord in &optimal_path {
        distances.insert(*coord, current_dist);
        current_dist += 1;
    }

    internal_walls
        .iter()
        .map(|wall| (wall, get_adjacent_points_on_path(wall, &distances)))
        .filter(|(wall, adjacent_path_points)| {
            if adjacent_path_points
                .windows(2)
                .any(|w| (w[0] as i32 - w[1] as i32).abs() >= picoseconds_to_save)
            {
                track_copy.insert(**wall, Status::Free);
                let new_score = dijkstra(
                    &start,
                    |c| get_successors(c, &track_copy),
                    |end_coord| *end_coord == end,
                )
                .map_or(0, |(_, s)| s);
                track_copy.insert(**wall, Status::Wall);

                initial_score as i32 - new_score as i32 >= picoseconds_to_save
            } else {
                false
            }
        })
        .count() as u64
}

fn get_adjacent_points_on_path(
    wall: &Coordinate,
    distances: &HashMap<Coordinate, u32>,
) -> Vec<u32> {
    let directions = [(-1, 0), (1, 0), (0, 1), (0, -1)];
    directions
        .iter()
        .filter_map(|(dx, dy)| {
            let adj = Coordinate {
                line: wall.line + dx,
                column: wall.column + dy,
            };
            distances.get(&adj).copied()
        })
        .collect()
}

For Part 2, this approach wasn’t scalable. After looking for hints, I saw some people used Manhattan distance instead of repeatedly running Dijkstra. This method also avoids to differentiate external and internal walls and simply checks:

If the time saved (that’s path_distance minus manhattan_distance) is at least the required picoseconds_to_save
Whether the wall can be reached within a certain number of allowed steps (max_cheat_steps).

Day 21

This puzzle required running Dijkstra repeatedly (yes, again!) and changing the start and end points on every iteration.

Using constant weights for neighbors didn’t work, so I tweaked them to minimize the number of turns with priority rules taken from hints. This approach worked for every input, but for the last number, the solution still isn’t working :(

After spending an insane amount of time on this, I skipped this puzzle entirely. You can still find the code I tried, and if you understand why it’s not working, please let me know!

Day 22

Part 1 of this puzzle was straightforward and easy: follow the instructions and get the correct result. With Christmas day approaching with its frenzy, I read part 2 but hadn’t time to implement it.

Day 23

Today, I learned the clique problem. Brute forcing part 1 was feasible, so I went for it.

For Part 2, instead, I decided to build the next clique size starting from the previous one and stop when only one clique was found (this is equivalent to “the largest set of computers that are all connected to each other” from the description).

Day 24

Welcome to the Christmas Eve puzzle with logic gates!

The input for Part 1 was mixed with gates ready to be computed and others with pending values. I used a queue (VecDeque in Rust) to process available data and push back any incomplete items for later resolution. Eventually, all data became available, and the correct result was submitted.

Do you remember what I said about the Christmas frenzy? Well, I only had time for the first part.

Day 25

And this is the end of the race! Part 1 was simple enough; some magic with iterators allowed me to achieve the correct result quickly.

Unfortunately, I couldn’t attempt Part 2 because I did not have enough stars.