Last week, a colleague pointed out to my team an online developer recruitment challenge. As I find it fun and there was no need to disclose one’s email, I decided to try, just to check if I could to it.
The problem is quite simple but not easy: consider a rectangular maze of finite size. One has to find a specific cell on the board - the exit, starting from the origin. One has 2 move options: one cell at a time in one of the 4 cardinal points or jumping to any previously visited cell. Of course, it wouldn’t be a maze if there was no obstacle: each cell provides information on the 4 adjacent cells, whether it’s unvisited, blocked by a wall or already explored. There’s one final constraint: each maze is alive for a finite amount of time. If the end cell is not reached after the timeout, it’s a failure.
After reading the page dedicated on maze solving algorithms on Wikipedia, I decided to implement the wall follower. It’s very simple, basically, you always follow the left (or right) wall.
My first implementation did just that. The problem with this solution is once a dead end has been reached - a cell with one visited direction and all other blocked, one has to move back again cell by cell. This implementation always failed because of the timeout.
I tried to be smarter for my second try. Instead of going back cell by cell, I thought about jumping to the last cell which offered a choice between at least 2 unexplored adjacent cells. In order to do that, I put such cells on a stack when I moved in one. When in a dead end, I just need to pop the top cell on the stack and jump to it in one single move. It’s queried again and updated as one less direction is considered unexplored and the process continues.