Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

Maze-Walking Algorithm

DZone's Guide to

Maze-Walking Algorithm

Maze-walking algorithms seem straight forward enough. Author Nicolas Frankel "walks" us through his experience of attempting to implement some.

· Performance Zone
Free Resource

Download our Introduction to API Performance Testing and learn why testing your API is just as important as testing your website, and how to start today.

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.

It happened to be a good enough solution: I succeeded 2 times (and failed a few times too), got both the secret message and the URL of the page you could apply to. Too bad it’s in Canada but it was fun. To make it even more fun, I developed in Kotlin with the Fuel library.

Find scaling and performance issues before your customers do with our Introduction to High-Capacity Load Testing guide.

Topics:
algorithm ,implementation ,challenges ,kotlin

Published at DZone with permission of Nicolas Frankel, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

THE DZONE NEWSLETTER

Dev Resources & Solutions Straight to Your Inbox

Thanks for subscribing!

Awesome! Check your inbox to verify your email so you can start receiving the latest in tech news and resources.

X

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}