Python A* path search algorithm with wall destruction

I recently stumbled across Google’s 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! °˖✧◝(⁰▿⁰)◜✧˖°)
[Read more…]