Advent of Code 2024: Day 06

Code for solutions available on GitHub.

Guard Gallivant

Ah, what would an Advent of Code be without a grid you have to walk through somehow. Today we have a grid of empty tiles (.) and obstacles (#), and the grid is patrolled by a guard (^). The guard is initially facing up and walks in a straight line. When they can’t walk forward due to an obstacle, they turn right and keep going. This continues until the guard leaves the grid.

Here’s the given example input:

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

Initially the guard will go up, hit the obstacle at the top, turn right, hit another obstacle, turn down, and so on.

The task for part 1 is to count the number of unique positions the guard visits before exiting the grid. The grid is handily parsed into a Vec<Vec<Tile>>, where Tile is defined as

enum Tile {
    Empty,
    Obstacle,
    Visited,
}

The tile the guard starts at is marked as Tile::Visited. The rest of the puzzle information can be put into some helper types and a Map struct, defined as:

struct Map {
    guard: Guard,
    grid: Vec<Vec<Tile>>,
}

struct Guard {
    position: Point,
    facing: Direction,
}

struct Point { x: usize, y: usize }
enum Direction {
    Up,
    Down,
    Left,
    Right,
}

For brevity I will leave out some details of the implementation in the rest of this post.

Next, we need some sort of step() method on our Map so that we can run the simulation.

impl Map {
    fn step(&mut self) -> Option<Point> {
        // Point::next is a pseudo-method for this
        // post that adds 1 in the facing direction
        // of the guard, bounds-checks, and returns
        // None if out of bounds.
        let next_position = self.guard.position.next()?;

        match self.grid[next_position.y][next_position.x] {
            Tile::Obstacle => {
                self.guard.facing = self.guard.facing.turn();
                Some(self.guard.position)
            }
            _ => {
                // Self::visit sets the index of next_position
                // in the grid to Tile::Visited.
                self.visit(next_position);
                self.guard.position = next_position;

                Some(next_position)
            }
        }
    }
}

Now that we have that, we can run the whole simulation like this:

while map.step().is_some() {}

And finally, to count all the unique visited tiles, after running the simulation:

let result = map.grid
    .into_iter()
    .flatten()
    .filter(|&t| t == Tile::Visited)
    .count();

Done!

Part 2

The puzzle is crafted in such a way that from the given input, the guard will always leave the grid. The task for part 2 is to stop this from happening by inserting a single obstacle into the grid that will make the guard get stuck in a loop. Then count how many positions you can insert an obstacle into to cause the looping. Also you’re not allowed to put an obstacle on the guard’s starting tile.

I don’t think there’s a better way to do this other than running the simulation, keeping track of which tiles have been visited and in which direction the guard visited them. Then one can insert an obstacle anywhere along the path and run the simulation again, checking if the guard got stuck in a loop. What’s the definition of being stuck in a loop? Well, if you visit a tile that you have already visited and going in the same direction, you’re stuck in a loop. Everything past that point is already determined.

To keep track of visited directions, I initially added some data to the Tile::Visited variant like this:

enum Tile {
    Empty,
    Obstacle,
    Visited([bool; 4]),
}

The variant can then be indexed by the Direction enum by casting it as a usize¹.

To detect the loops, the step() method needs to return whether or not the next position has already been seen in the same direction.

impl Map {
    fn step(&mut self) -> Option<(Point, bool)> {
        let next_position = self.guard.position.next()?;

        match self.grid[next_position.y][next_position.x] {
            Tile::Obstacle => {
                self.guard.facing = self.guard.facing.turn();
                Some((self.guard.position, false))
            }
            Tile::Visited(v) => {
                // Self::visit now sets the Tile::Visited slice
                // to true for the direction the guard is facing.
                self.visit(next_position);
                self.guard.position = next_position;
                Some((next_position, v[self.guard.facing as usize]))
            }
            Tile::Empty => {
                self.visit(next_position);
                self.guard.position = next_position;
                Some((next_position, false))
            }
        }
    }
}

With that little modification, we can now add a method which detects loops like so:

impl Map {
    // ---<snip>---

    fn loops(self) -> bool {
        while let Some((_, already_visited)) = self.step() {
            if already_visited {
                return true;
            }
        }
        false
    }
}

Then to the actual solving. My initial solution involved simulating the map once, extracting the positions of visited tiles from the grid, then for each position I run the .loops() method on a copy of the original map with a single extra obstacle inserted for each position that would have been visited. This worked, but was really slow. Took about 160ms on my machine².

To speed it up, I simply tried slapping a par_iter on the whole iterator looping through the visited tiles and simulating. This brought the runtime down to 17ms. Pretty good, but I’ve always felt like it’s a kind of cheap (as in not honest) way to improve the runtime of AoC solutions. Ideally I would actually optimize the single-threaded solution.

My first idea was that running the entire simulation to extract the path, then running all other simulations was not very good. It does a lot of repeated work. So I refactored the solution to instead insert an obstacle in front of the guard on a copy of the map, running that whole simulation to determine if it loops, then stepping the original map. That way the guard’s path is cached and will speed up iterations that have gone very deep.

This brought the single-threaded runtime down to about 56ms. There were still some gains to be found.

Moving from a Vec<Vec<Tile>> to a [[Tile; 130]; 130] shaved off a few more milliseconds. The input was 130x130, so it made sense to just hard-code it.

Then, instead of having the Visited variant contain a slice, I made it contain a bitmask of directions, like this:

enum Tile {
    Empty,
    Obstacle,
    Visited(u8),
}

#[repr(u8)]
enum Direction {
    Up = 1,
    Down = 2,
    Left = 3,
    Right = 4,
}

This made the .visit() method able to just bitwise-or the facing direction of the guard into the tile. And to determine if a tile had already been visited in that direction, the .step() method can just bitwise-or the tile with the facing direction of the guard. This removed a lot of indexing, and brought the runtime down to about 25ms.

I’m not happy with having milliseconds pop up so early on, but I will leave it here. Finding a good sub-millisecond solution probably requires me to rewrite the solution from the ground up. That’s the tricky part of Advent of Code. You can get locked into your solution to part 1 in such a way that your solution for part 2 is sub-optimal. Oh well. I don’t really mind leaving this solution like this. Going from 160ms down to 25 is still decent. :)