Advent of Code 2024, Day 6

Maps! I mean literally, it’s like a mini 2d game. HashMaps are again important, but also an infinite loop with a single break condition, walks, and a state machine of sorts.

Links below, and spoilers after the header.

adventofcode2024/day06 at main · javorszky/adventofcode2024

Contribute to javorszky/adventofcode2024 development by creating an account on GitHub.

GitHubjavorszky

Spoilers

Part 1

I did it the uh... object way I think. I created a bunch of enums: 4 of them for the direction (Up, Down, Left, Right), 8 of them for the kind of tiles I might encounter on the map (floor, visited, obstacle, guard in 4 orientations, and outside), created a type alias Coordinate for (i32, i32) instead of usize, so I can handle cases like (-1, 0) without Rust throwing a hissy fit.

Then a map, which is a HashMap<Coordinate, Tile>, then another for visited, which is the same shape, then a current coordinate and current direction to store what we ended up with after each step.

When parsing the input, I also take note where the guard is and what orientation she’s facing, and store that on the Day06 struct as current coordinates and directions, and add that coordinate to the visited tiles list.

And then a loop where we get the next coordinate based on current coordinate and current direction, then grabbing the tile at the new coordinate with the rules:

• if she encounters an Outside tile, i.e. the Coordinate is not in the list of coordinates in the map, I return the default, then break and we’re free!
• if she encounters an Obstacle, do not change the current coordinate, turn right 90 degrees and change the current direction, do not record anything in the visited list
• if she encounters anything else (floor, visited, any of the 4 guard tiles), move onto there, and mark it as a visited coordinate

At the end I have a HashMap of entries for visited tiles. It’s a map rather than a vec because if a key already exists, so the guard visits a tile she’s been on already, it will overwrite the entry with the same data rather than insertin a new entry creating duplicates.

The solution is returning the length of the map. Or the .count() of the map.

Part 2

Man, I spent like a full day on this. Ugh. Okay, so this is the classic case of let’s branch out from EVERYWHERE making the problem exponentially hard. And slow to complete.

The basic idea of detecting a loop is you keep track of where you’ve been, what direction you were going in at that place, and if you encounter the same tile going the same direction again, congrats, you’re in a loop!

Keeping track of that with a HashSet<(Coordinate, Direction)> is fairly straightforward.

I learned that the difference between a HashMap and a HashSet is essentially just the presence of values. Maps have keyed values, sets only have keys. In Go I would keep track of unique values by using a map[<type>]struct{}. Using empty struct as a value is a space efficient way of using the properties of map keys for uniqueness. In Rust we have HashSets, so yay!

After I solved part 1, I tried to be clever and detect relative positions of four obstacles, seeing whether I can match on two, three, what the rules were. In order for a loop to happen in a rectangle, I need one obstacle at the bottom right corner below, one at the top right corner to the right, one at the top left corner above, and one at the bottom left corner to the left. Kinda like this:

 #
 +------->------+#
 |              |
 ^              v
 |              |
#+-------<------+
                # // wedges added to signify travel direction

That way it doesn’t matter where the Guard starts, as long as she goes clockwise, we’re good.

This approach very quickly became unwieldy, so I scrapped it. The next approach was the correct one, with some refinement.

I modified the code a bit so that when it’s doing its part 1 loop, I also record and keep track of where she’s been, with directions, in order. Vec<(Coordinate, Direction)> to the rescue!

Then for part 2, I replay that, but this time I’m also creating Candidates. These hold three information: where the guard is at the moment, which way the guard is facing, and what the next coordinate is. I only do this if turning right on the current tile – because there’s an obstacle in front of the guard – would result in hitting an obstacle rather going off the map.

Then once I have all the candidates, I create another HashSet to hold the positions of confirmed paradox obstacles, loop through all the candidates, create a new copy of the existing struct, insert the new obstacle where the candidate says it should be, update the starting position to where the candidate says the guard starts, and the starting direction also from the candidate. All that’s left is walk and detect a loop. If there’s a loop, we’re good, add the coordinate the HashSet, and return the final length of that, and boom, solution!

... except it’s wrong. I tried so many things, rewrote the entire part 2, separated parts 1 and 2 into their own files, learned about mod and crate separation, difference between pub fn and pub (crate) fn, and even though the code is in the same directory but a different file, I still need to import from the other file using use crate::{...}. This was weird coming from Go where all files in the same directory either belong to the same package, or to its _test package. The compiler will throw an error if you mix packages in the same directory. I guess the analogy to Rust is a crate? But a crate seems like it has the ability to span multiple directories within the src/. I’m still hazy on this.

The two assumptions that broke this were:

• I moved the starting position in the copies, which masked over the fact that
• if I place an obstacle on a tile that the guard has previously passed through, then I changed her path, and she wouldn’t have been able to get to the position she’s in when I make the decision to place the obstacle

I added another HashSet to keep track of the path she’s taken when I check a candidate, and when the candidate wants to place an obstacle on a tile that’s in the past path set, I skip over it.

And that gave me the correct solution. Here’s a test case you can try:

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

Out of the box the guard would exit on the left after doing this path:

   ..#....
   ......#
   .#.....
   .↱---↴#
bye-+---↲.
   .|...#.
   .^.....

However if you put an obstacle here, and move the guard so her starting position is right in front of the obstacle, you get a loop:

..#....
..↱--↴#
.#|..|.
..|..|#
.O<--↲.
.....#.
.......

Except this doesn’t work when the guard starts on her usual place:

..#....
......#
.#.....
......#
.O.....
.↱--↴#.
.^..|..
   bye

Which is why you gotta filter out wanting to put an obstacle to a place she needs to go through to get to where she is when you’re trying to check whether an obstacle would cause a loop.

Spoiler photo by Ryan on Unsplash.