Mousing Around
When I first wrote my previous post Interview Question: The Mouse, I did not expect to get so many responses. I have been literally deluged with mail filled with code samples and algorithms. It's taken me a while to sift through them and determine which if any would succeed at hunting down the cheese. Fortunately, a few of them actually did so I can now share them with you.
But first, lets discuss the problem again so we can understand the solutions in context. A robot mouse is dropped into a maze where somewhere there is placed a piece of cheese. You must write an algorithm to control the mouse and successfully find the cheese. Unfortunately, the mouse is blind so the only feedback you have is the paltry information coming back from the mouse 'interface'. The maze is a regular grid of cells, where each cells may have zero or more walls that impede movement, except for the outer edge that is completely sealed. At the start you don't know where the walls are, you don't know where the cheese is and you definitely don't know where the mouse is. All you do know that the maze is limited to some particular size.
What this should tell you is that you need to exhaustively and deterministically search the maze, stopping only when you find the cheese. What it doesn't tell you is the pitfalls you may encounter when doing so, things like cycles, paths that lead back onto themselves, and open expanses that have no walls around them at all. A successful solution will avoid these areas of trouble. A good solution will do it in a nominal number of moves.
- You must avoid walking randomly. There is no way of knowing whether the series of suggested directions will actually cause you to traverse the entire maze. You may just bob back and forth forever.
- You must avoid walking in circles. You need to employ some mechanism to remember where you have been. Since the mouse cannot tell you where it is or where it has been, and offers no model of the world other than success or failure to move, you must invent your own model and a means to keep track.
- You must avoid getting stuck at a dead end. Going back the way you came is a good idea, but make sure you have a way to keep going, that path up to the end might have been narrow and long.
- At the edges of your explored space will be all the places you have not yet been. In order to exhaustively search the maze you need a way to get back there and try them.
So successful solutions employs cycle detection and backtracking. Let's take a look at the winners.
Tim Fries was the first with a successful solution. It does everything it needs to do and deterministically finds the cheese. Even Tim, however, would admit that his use of a string hashtable to remember where the mouse has been was not the most elegant. You can see the source code to his Cheese Appropriator here.
Ralf Westphal had the most elaborate solution. A complete VB application with GUI so you can watch the mouse on its trek through the maze. You can get ahold of the entire project here and run it yourself.
Honorable mention should go to Brad Corbin for his strange, though oddly successful solution of keeping least-visit statistics for each cell. This allows the mouse to re-tromp over previously visited cells without a more explicit backtracking mechanism, teasing the mouse toward areas yet unvisited. I have not been able to find a scenario that this meandering mouse would not eventually succeed at, save for the maze with no cheese at all.
How about my own solution? Everyone always asks for that after the interview. So here it is below.
public class CheeseFinder {
struct Cell {
public byte next;
public byte prev;
}
public static bool FindCheese(IMouse mouse, int rows, int cols) {
Cell[,] grid = new Cell[rows, cols];
int r = 0;
int c = 0;
// set terminal, so we don't backtrack past the origin
grid[r, c].prev = 4;
while (!mouse.IsCheeseHere()) {
byte d = grid[r,c].next;
if (d < 4) {
// increment so we know what to try next
grid[r,c].next++;
// determine next relative position
int nr = (r + dr[d] + rows) % rows;
int nc = (c + dc[d] + cols) % cols;
// only try to move to cells we have not already visited
if (grid[nr,nc].next == 0 && mouse.Move((Direction)d)) {
r = nr;
c = nc;
// remember how to get back
grid[r, c].prev = (byte)((d + 2) % 4);
}
}
else {
// backtrack
d = grid[r, c].prev;
if (d == 4)
return false;
mouse.Move((Direction)d);
r = (r + dr[d] + rows) % rows;
c = (c + dc[d] + cols) % cols;
}
}
return true;
}
static int[] dr = new int[] { -1, 0, 1, 0 };
static int[] dc = new int[] { 0, 1, 0, -1 };
}
I also have a recursive solution that is much simpler. Though, you would generally want to avoid recursion.
Matt
Comments
- Anonymous
February 11, 2005
Ok, I'm glad to get an honorable mention, but seeing the other solutions, I can't believe I dismissed the "keeping track of the path" technique everyone else seemed to use.
For some reason I was thinking that I'd have to keep track of a complex tree of paths, not just the "current path". Seems obvious, now.
On the other hand, I've further refined the effectiveness of my "crumb dropping" mouse. More likely to not retrace paths in a loop. Hehe. He might get there slow, but he's fun to watch! - Anonymous
February 28, 2005
Nice question! My first thought was just a 'keep your left hand on the wall' solution, but when I realised how unconstrained the maze could be it clicked that it's basically a flood fill algorithm hidden in a distracting scenario.
I think in an interview I would definately have gone with recursion though because it's easier to visualise under pressure. Would you have prefered a working recursive solution or a looping one with some bugs, but the right principle? I guess either says something positive about the candidate... - Anonymous
February 28, 2005
A recursive algorithm is fine, in that it is a good starting point for talking about how a non-recursive solution would work. So no points off. :-) - Anonymous
March 06, 2005
The comment has been removed