I recently stumbled across Google’s foo.bar challenge, and it’s quite an interesting set of problems! I got through the first couple levels without much difficultly, but level 3 is kicking my butt. I finally solved this maze problem after a day, so I’m posting it here to explain my thought process and because I’m pretty proud that I learned how to A* in the 5 hours or so I spent on the question.
Anyhow, the original challenge is twofold. First, given a maze represented by a grid of cells, find the shortest path you can take to get from the beginning to the end of the maze. Secondly, solve the maze again with the additional ability to now destroy one wall in your path. Though I’m sure there are many approaches one could take to solve this, I went with modified A*.
(No cheating on the challenge if you’re currently taking it! I really enjoyed the learning process I went though while taking the challenge, so don’t rob yourself of that opportunity! °˖✧◝(⁰▿⁰)◜✧˖°)
Still here? Great!
First, thanks to Laurent Luce for his wonderful tutorial to the A* algorithm. I basically took the A* part of his code, then added some modifications to account for wall destruction. Refer to his post for a more detailed explanation of A*, but briefly:
A* is a best-first search, meaning that it will search for along all possible solutions for the one that has the least cost to its goal. In our case, “cost” is the number of moves it takes to get from the start of the maze to the end. For a maze where S = start, and E = end:
One can see that the cheapest path is the one with the fewest turns, such as:
We can assume this approximation for calculating the cost of any cell of the maze to the end, where X is the cell for which we’re calculating cost:
So in A*, we have two lists of cells that we maintain. The open list contains coordinates of cells we plan to visit next, while the closed list contains cells that we have already evaluated. During our search, we evaluate each reachable adjacent cell to our current position and determine it’s cost. The adjacent cell with the lowest cost is added to the closed list and used for the next iteration of the search. Because our cost is determined by the distance to the end of the maze, we ultimately find a path with the lowest cost from the start of the maze to the end.
This was a fairly brief explanation of how A* works, so I’d highly recommend you read either the Wikipedia page on the algorithm, or Laurent’s explanation of how it works.
Also, here’s a neat gif courtesy of Greg Jennings at Stack Overflow!
You can see the blue squares filling in each cell of the grid, and internally this algorithm will prefer squares that are closer to the destination though our cost function. In this way, we encourage the path to develop towards the end of the maze.
Here’s some pseudo-code to illustrate how this algorithm would work:
We’ve got the maze solving part of the question done! Now, what about the wall destruction? This complicates things, because now any “unreachable” cell of the maze could technically be changed. I waaaaaay overthought this part of the problem, though the core issue is rather straightforward. We can destroy exactly one wall. Which means, any time during our
To find the smallest path possible keeping wall destruction in mind, we need to run the
The modified
Ta-da! We’re done!
Now, as an addendum to the problem, I’d consider the case where we’re allowed to destroy N number of walls instead of just 1. I’d imagine that the complexity of the question increases exponentially or something as both N or the maze size/# of walls gets larger though, since the combinations of possible destroyed walls would get rather difficult. Hey, a fun problem for you to think!
Anyhow, that’s it for A* and destruction. Can’t wait to see what the next challenge is!
-Sophie