Day 24 - Graph Problem Redemption

I don't have enough time for a full write-up at the moment, but I did complete today's problem, so I'll share the key insights and you can take a look at my final code on GitHub. I actually feel very good about this solution since I finally managed to solve one of the challenging graph problems (see Days 16 and 19) without needing help.

My first naive try at the problem was, of course, too slow. but I came up with a couple optimizations I hadn't employed before to bring it to a reasonable speed. I get the final solution in about 2-3 minutes, so some optimization might still be possible, but that's still way better than my 30-40 minute solution on Day 16.

Solution code on GitHub

All 2022 Problems

Subscribe to Monday Morning Haskell!

Problem Overview

Full Description

This is a 2D grid navigation problem, but we're now dealing with moving obstacles. Luckily, each obstacle moves in a very predictable pattern. We're navigating a valley with "blizzards", and each blizzard moves either up, down, left, or right one tile with each passing turn.

#.######
#>>.<^<#
#.<..<<#
#>v.><>#
#<^v^^>#
######.#

When a blizzard hits the wall of the valley (#), it wraps back around, traveling in the same direction along the same row starting from the other side. Blizzards do not affect each other's path, so it's possible for multiple blizzards to share a tile for a turn before continuing. We want to get from the top empty space (.) to the bottom space while avoiding the blizzards.

Each turn we move simultaneously with the blizzards. So we are trying to step into a space that will be empty on the next step. This means it is possible to move into a space that appears to be currently occupied by a blizzard. In the first step from the starting position above, it is legal for us to move down, because the blizzard there will have moved right during our move, and no other blizzard takes its place. Importantly, it is also legal for us to stand still for a turn and wait for the blizzards around us to pass (as long as a blizzard isn't coming into our space that turn).

In Part 1, we must find the shortest path to the end. Then in Part 2, we have to find the subsequent shortest path from the end back to the start and then once again proceed from the start to the end (the elves forgot their snacks). Because of the blizzards shifting, the three paths do not necessarily look the same.

Naive Approach

We can combine a simple Breadth-First-Search with the principles of state evolution. We have to track all the coordinates that currently contain a blizzard. But we do this in 4 different sets, so we can move the blizzards in the right direction each turn.

But essentially, we look at our neighboring tiles, see which ones will be empty, and treat all those as our neighboring options, until we complete the search.

However, this isn't sufficient to deliver an answer to the large input in a reasonable amount of time.

Optimization 1: Bit Vectors!

The first observation we can make with the naive approach is that for every state evolution, we're spending time updating each individual blizzard. In my "large" input, blizzards take up about 3/4 of the grid space, so we're essentially spending O(n^2) time on each state update.

We can reduce this to O(n) by using an Integer to represent each row of left/right blizzards and each column of up/down blizzards, and treating this integer as a bit vector. Imagine the following binary representation of the integer 18:

010010

We can do a bitwise "left shift", and our number doubles, becoming the integer 36:

100100

Likewise, we can "right shift" our original number to get 9:

001001

Notice how these operations resemble the shifting of a set of blizzards along a row (or column). A "1" bit represents the location of a blizzard, and "0" is a clear space.

So we might represent the "up blizzards" of column 5 with the number 9, since the up blizzards exist at rows 1 and 4:

1001

Since they go up, we shift "right", moving each bit. The trick is that we have to define our own shift function to handle that wrap around! The number should become 24, since the least significant bit wraps to the most significant:

1100

Haskell's Bits typeclass (from Data.Bits) provides all the tools you need to accomplish these tasks with the Integer type that implements the class:

setBit :: Integer -> Int -> Integer
clearBit :: Integer -> Int -> Integer
testBit :: Integer -> Int -> Bool
shiftR :: Integer -> Int -> Integer
shiftL :: Integer -> Int -> Integer

The testBit function is what you'll ultimately need to determine if a space has a blizzard or not in your search function. The others are needed for updates. But all these functions are extremely efficient and the shifting allows us to perform bulk updates!

You still need one array of integers for each column or row for each direction of blizzards. But updating these is still O(n) time compared to O(n^2) for the original approach.

This optimization is sufficient to bring the first part down to a tractable amount of time (3-5 minutes). But I had another idea to help.

Optimization 2: A-Star

We're still stuck with the fact that to find an optimal path of length 18, BFS will blindly explore every path up length 18. However, the A algorithm can give us a more directed search if* we provide a reasonable heuristic.

I had tried to apply A on the earlier graph problems. But for those problems, it was difficult to provide a good heuristic because of how the cost worked. A requires a heuristic that underestimates the final cost. But in the prior problems, the distance traveled wasn't actually the graph cost, making it difficult to provide an underestimate.

This time, we can simply use the manhattan distance to the end coordinate as a reasonable heuristic. This will direct our search more actively towards the end of the grid. It's not always optimal to do so, but it's a better guess that will prevent a lot of wasted time on branches that just retreat to the beginning unnecessarily.

This cut down my solution time by about half. So I could now get the first solution in less than a minute, and the final part in less than 3 minutes, which I'm satisfied with for now.

The only further optimization I can think of would be to observe that the blizzard paths are so predictable that we should be able to find a closed form math solution for the question of "does space X have a blizzard at time t", perhaps involving modulus and LCM operations. I might explore this idea later.

I'll also get into more details on the code later. For now, there's one more problem remaining tonight!