Finding path in Maze

Question

I recently gave an interview and was asked the following question. I posted this here Finding path in Maze also, and someone suggested I should try Code Review. So here it goes.

A maze is a group of linked Places. Each Place has a North, South, East, and West Place adjacent to it. There are two special pre-defined Place's: Place Wall represents a wall - the mouse can't go there. Place Cheese is ... cheese! The connections between Places are symmetrical - if you start from any Place and go North and then South, you return to where you were.

To simplify things, the maze has no closed loops - that is, if you start in any Place and follow any path, you eventually either hit a wall or find cheese - you never come back to the Place you started unless you actually retrace your steps.

A mouse starts off in some Place and searches around for Cheese. When it finds Cheese, it returns a set of directions - a string of the letters NSEW that lead from where it started to the Cheese.

The following framework defines the classes and functions. Some other code not included here generates a maze by creating a bunch of Place's and linking them. It then calls mouse(), passing some starting Place from the maze:

interface Place {

// Return the adjacent Place in the given direction
public Place goNorth();
public Place goSouth();
public Place goEast();
public Place goWest();

// Returns true only for the special "Wall" place
public bool isWall();

// Returns true only for the special "Cheese" place
public bool isCheese();
};

class Mouse {
  public Mouse() {}

  // Return a string of the letters NSEW which, if used to traverse the
  // the maze from startingPoint, will reach a Place where isCheese() is
  // true.  Return null if you can't find such a path.
  public String findCheese(Place startingPoint) {
    ... fill this in ...
  }
}

Implement findCheese(). You can add any fields or helper methods you need to Mouse. Extra credit: Eliminate the "no closed loops" restriction. That is, change your code so that it works correctly even if there might be a path like SSNEEW that leads the mouse back to the Place it started from.

This is what I tried. I understand this won't be the best or optimized solution, and wanted feedback as to what I else I could try. I have not considered the extra credit part

public String findCheese(place startingPoint)
{
    //Call helper function in all 4 directions;
    return findCheeseHelper(startingPoint,new StringBuilder("N")).append(
        findCheeseHelper(startingPoint,new StringBuilder("S"))).append(
            findCheeseHelper(startingPoint,new StringBuilder("E"))).append(
                findCheeseHelper(startingPoint,new StringBuilder("W"))).toString();
}


public StringBuilder findCheeseHelper(place startingPoint, StringBuilder direction)
{
    StringBuilder nDir=new StringBuilder("");
    StringBuilder sDir=new StringBuilder("");
    StringBuilder eDir=new StringBuilder("");
    StringBuilder wDir=new StringBuilder("");

    //Rerturn which direction this step came from if cheese found
    if(startingPoint.isCheese())
    {
        return direction;
    }
    //Specify this is not a correct direction by returning an empty String
    else if(startingPoint.isWall())
    {
        return "";
    }

    //Explore all other 3 directions (except the one this step came from)
    if(direction=="N")
    {
        sDir=findCheeseHelper(startPoint.goSouth(), new StringBuilder("N"));
        eDir=findCheeseHelper(startPoint.goEast(), new StringBuilder("E"));
        wDir=findCheeseHelper(startPoint.goWest(), new StringBuilder("W"));
    }
    else if(direction=="E")
    {
        nDir=findCheeseHelper(startPoint.goNorth(), new StringBuilder("N"));
        sDir=findCheeseHelper(startPoint.goSouth(), new StringBuilder("S"));
        wDir=findCheeseHelper(startPoint.goWest(), new StringBuilder("E"));
    }
    else if(direction=="W")
    {
        nDir=findCheeseHelper(startPoint.goNorth(), new StringBuilder("N"));
        sDir=findCheeseHelper(startPoint.goSouth(), new StringBuilder("S"));
        eDir=findCheeseHelper(startPoint.goEast(), new StringBuilder("W"));
    }
    else if(direction=="S")
    {
        nDir=findCheeseHelper(startPoint.goNorth(), new StringBuilder("S"));
        eDir=findCheeseHelper(startPoint.goEast(), new StringBuilder("E"));
        wDir=findCheeseHelper(startPoint.goWest(), new StringBuilder("W"));
    }

    //If I hit wall in every direction, I will get empty string and so specify to calling 
    //function that this is not a correct direction
    if(nDir.equals("") && sDir.equals("") && eDir.equals("") && wDir.equals(""))
        return new StringBuilder("");

    //If Cheese was found in even 1 direction, return direction to come to this step, appended with the path
    // forward to the calling function
    return direction.append(nDir).append(sDir).append(eDir).append(wDir);
}

Answer 1

I'm sorry, but that code is really convoluted.

First off, does this actually work? The comparisons direction == "N"(etc.) should fail at compile time due to incomparable types (String and StringBuilder) and nDir.equals("") would always return false.

Generally you can't use use == to compare strings in Java. You have to use equals (for strings. StringBuilder doesn't have an implemention of equals).

You really are overdoing it with the StringBuilders. You should only need a single one (one new StringBuilder() call in the entire code) to which you append Strings.

To be honest in practice code like this, you don't need use a StringBuilder at all. Just use string concatenation. It's slow and a memory hog, so it's not something you should do in real life code, but it would make this code much more simpler and easier to read.

There is much more, but I believe that would be good for a first step in the right direction.

Answer 2

@RoToRa has some good points. Creating so many StringBuilders while recursing is really an overkill, and assuming even if the algorithm works (albeit inefficiently), I will be more inclined to use enums representing the direction instead of StringBuilders.

Also, the logic needs more clarification in the example below... if I'm heading/headed(?) north of my starting point, then I'll head in the opposite direction but with my direction "North" still...?

if(direction=="N")
{
    sDir=findCheeseHelper(startPoint.goSouth(), new StringBuilder("N"));
    eDir=findCheeseHelper(startPoint.goEast(), new StringBuilder("E"));
    wDir=findCheeseHelper(startPoint.goWest(), new StringBuilder("W"));
}