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.

  1. 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.
  2. 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. 
  3. 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.
  4. 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 (4)

  1. Brad Corbin says:

    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!

  2. 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…

  3. Matt Warren says:

    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. 🙂

  4. Milt Meeds says:

    Matt,

    I apologize for barging in this way, but I couldn’t find any other….

    I was searching for Ayock Beach on the internet and came across your blog from last August. My father was raised on Ayock Point in the 20s/30s when the whole point belonged to his foster mother and her doctor husband. (He was born in 1912 and worked at Cushman Dam for the Civilian Conservation Corp when it was built.) My folks used to take my sister and me there to visit in the late 40s/50s when there was only his foster mother and her nurse living there in the only house on the point. I don’t really know what her name was; my folks referred to her as "The Lady." I believe she sold the point sometime in the 60s.

    My wife and I drove through the community today trying to ascertain if her house was still standing or if they tore it down during development of the point. I saw one likely candidate, but what would have been the front of the house and porch now faces away from the street. I couldn’t see the front porch, which is what I remeber best and appears to face north as it did then. There was a sign in the drive that said "Terry and Cindi," and it looks like they would have had to walk around the covered porch (on the north and west) to enter. The house is right in the middle of the point, which is where the old house had been. There wasn’t a sole in the community visible outside with whom I could stop and talk.

    Is there any chance you would know if the original house on the point IS still standing or know anyone else out there who might know?

    I really appreciate any help you can give me.

    Thanks!

    Milt Meeds

    milt700@wavecable.com