I felt privileged to receive an invitation for the Google Foo Bar Challenge, a discreet hiring process by Google (https://www.turing.com/kb/foobar-google-secret-hiring-technique).

Although I've nearly completed all the exercises, there's one in particular that I found quite intriguing.

You can access it here: https://github.com/mathias-vandaele/google-foobar-challenge/blob/master/src/main/java/dev/mathias/exercise_3_2/Solution.java

Prepare the Bunnies' Escape

You're awfully close to destroying the LAMBCHOP doomsday device and freeing Commander Lambda's bunny prisoners, but once they're free of the prison blocks, the bunnies are going to need to escape Lambda's space station via the escape pods as quickly as possible. Unfortunately, the halls of the space station are a maze of corridors and dead ends that will be a deathtrap for the escaping bunnies. Fortunately, Commander Lambda has put you in charge of a remodeling project that will give you the opportunity to make things a little easier for the bunnies. Unfortunately (again), you can't just remove all obstacles between the bunnies and the escape pods - at most you can remove one wall per escape pod path, both to maintain structural integrity of the station and to avoid arousing Commander Lambda's suspicions.

You have maps of parts of the space station, each starting at a prison exit and ending at the door to an escape pod. The map is represented as a matrix of 0s and 1s, where 0s are passable space and 1s are impassable walls. The door out of the prison is at the top left (0,0) and the door into an escape pod is at the bottom right (w-1,h-1).

Write a function answer(map) that generates the length of the shortest path from the prison door to the escape pod, where you are allowed to remove one wall as part of your remodeling plans. The path length is the total number of nodes you pass through, counting both the entrance and exit nodes. The starting and ending positions are always passable (0). The map will always be solvable, though you may or may not need to remove a wall. The height and width of the map can be from 2 to 20. Moves can only be made in cardinal directions; no diagonal moves are allowed.

The solution

Many online solutions employ a dual Dijkstra's algorithm and utilize a double for loop to discover the shortest paths both from the starting point to the endpoint and vice versa. The objective is to identify the optimal location for breaking a wall, allowing the determination of the overall shortest path.

I believe this solution is not only inefficient, but can not be generalized, what if we are allowed to break more than one wall this algorithm becomes useless. This solution also has an early return, meaning the best solution can be found really really fast.

My chosen approach diverges significantly; I intend to transform the maze into a heat map. As the bunny takes more steps, the corresponding points on the map become hotter.

I subsequently determine the threshold for considering a non wall-crossing path as worthwhile. I arbitrarily set this threshold at 100,000 steps. This implies that I find it acceptable to explore a path that avoids wall crossings but is still at least 100,000 steps behind a path that did involve wall crossings.

I will make it into steps to give an example:

Here is the maze:

{
        {0, 1, 1, 0},
        {0, 0, 0, 1},
        {1, 1, 0, 0},
        {1, 1, 1, 0}
}

Here is the heating map associated (Note that I am using MAX_INTEGER to represent an unexplored node):

[[0, 2147483647, 2147483647, 2147483647],
[2147483647, 2147483647, 2147483647, 2147483647],
[2147483647, 2147483647, 2147483647, 2147483647],
[2147483647, 2147483647, 2147483647, 2147483647]]

Few steps after, we are ending up with this:

[0, 100000, 2147483647, 2147483647]
[1, 2, 2147483647, 2147483647]
[100001, 2147483647, 2147483647, 2147483647]
[2147483647, 2147483647, 2147483647, 2147483647]

When a wall is destroyed, I increase the value in the heatmap for the preceding cell by 100,000 and update the current cell accordingly. In the absence of a wall, I simply increment the value by one. This approach enables the re-exploration of a path as long as a better score is achieved.

[0, 100002, 100003, 100004]
[1, 2, 3, 100005]
[100001, 100004, 4, 5]
[2147483647, 2147483647, 100004, 6]

And when we finally found the end of the maze, we return early with the number of steps we have achieved.

Conclusion

I believe that employing a combination of a heatmap and Dijkstra's algorithm enhances the effectiveness of resolving this LeetCode problem compared to the conventional technique. This approach boasts a simpler time complexity and is capable of determining the shortest paths even when breaking more than one wall, possibly up to two or three walls.