CareerCup

function FindFlag() {
	if IsFlag() {alert("Got it"); exit}
	if HasBreadCrumb() {return}
	if !IsWall() {PutBreadCrumb(); Go(); FindFlag()}
	Turn(90);
	if !IsWall() {PutBreadCrumb(); Go(); FindFlag()}
	Turn(180);	
	if !IsWall() {PutBreadCrumb(); Go(); FindFlag()}
	}

recursive depth first search is the way to go (with extra checks for wall, corresponding to leaf nodes of a graph).

The solution has to be recursive because the API's provided has to be used, Adjacent node generation is done by 'turning' and bread crumb is used to visit.

Although DFS is the way to go, the solution can't be recursive. The reason is that the robot do not have a memory of the previous cell. Unlike a recursive function, that when exits to an upper level, and retains its previous value, the robot cannot do it. Instead, each time the robot advances to a new cell, the angles have to be pushed into a stack.

this is my solution, although I had the liberty to modify names of the robot function (without adding anything to the robot API).

class MazeWalker {
  int mAngle;
  std::stack<int> s;
  Maze &mMaze;
  
  
    public: 
        MazeWalker(Maze &maze): mAngle(0), mMaze(maze) {
        }

        void traverse(bool stopOnFlag);
  
    private:
    
        int left() { mAngle = (mAngle - 90) % 360; return 270; }
        int forward() { mAngle = 0; return 0; }
        int right() { mAngle = (mAngle + 90) % 360; return 90; }
        int reverse(int angle) { mAngle = (360 - angle) % 360; return mAngle; }
        
        bool goLeft() {
            
        }
};

#define MAZE_WALKER_MOVE(f)   \
    mMaze.turn(f);       \
        if (!mMaze.wall()) {  \
            s.push(mAngle);   \
            mMaze.move();   \
            continue;         \
        }
        
void MazeWalker::traverse(bool stopOnFlag) {
    bool stop = false;
    int step = 1;

    while (!stop) {
        
        cout << "Current step: " << step++ << " ";
        mMaze.printCurrentCell();
        
        if (stopOnFlag && mMaze.isFlag())
        {
            cout << "Found flag: ";
            mMaze.printCurrentCell();
            cout << endl;
            return;
        }
            
        if (mMaze.isBreadcrumb()) {
            if (s.empty())
                return;
            
            int angle = s.top();
            s.pop();
            mMaze.turn(angle);
            mMaze.move();
            continue;
        }
            
        MAZE_WALKER_MOVE(left())
        MAZE_WALKER_MOVE(right())
        MAZE_WALKER_MOVE(right())
        
        mMaze.putBreadcrumb();
    }
};


/*
 * 
 */
int main(int argc, char** argv) {
    Maze m(5);
    m.init();
    m.print();
    
    MazeWalker mw(m);
    mw.traverse(true);
    return 0;
}

class MazeWalker {
  int mAngle;
  std::stack<int> s;
  Maze &mMaze;
  
  
    public: 
        MazeWalker(Maze &maze): mAngle(0), mMaze(maze) {
        }

        void traverse(bool stopOnFlag);
  
    private:
    
        int left() { mAngle = (mAngle - 90) % 360; return 270; }
        int forward() { mAngle = 0; return 0; }
        int right() { mAngle = (mAngle + 90) % 360; return 90; }
        int reverse(int angle) { mAngle = (360 - angle) % 360; return mAngle; }
        
        bool goLeft() {
            
        }
};

#define MAZE_WALKER_MOVE(f)   \
    mMaze.turn(f);       \
        if (!mMaze.wall()) {  \
            s.push(mAngle);   \
            mMaze.move();   \
            continue;         \
        }
        
void MazeWalker::traverse(bool stopOnFlag) {
    bool stop = false;
    int step = 1;

    while (!stop) {
        
        cout << "Current step: " << step++ << " ";
        mMaze.printCurrentCell();
        
        if (stopOnFlag && mMaze.isFlag())
        {
            cout << "Found flag: ";
            mMaze.printCurrentCell();
            cout << endl;
            return;
        }
            
        if (mMaze.isBreadcrumb()) {
            if (s.empty())
                return;
            
            int angle = s.top();
            s.pop();
            mMaze.turn(angle);
            mMaze.move();
            continue;
        }
            
        MAZE_WALKER_MOVE(left())
        MAZE_WALKER_MOVE(right())
        MAZE_WALKER_MOVE(right())
        
        mMaze.putBreadcrumb();
    }
};


/*
 * 
 */
int main(int argc, char** argv) {
    Maze m(5);
    m.init();
    m.print();
    
    MazeWalker mw(m);
    mw.traverse(true);
    return 0;

}

I have solved it using non recursive DFS. The solution cannot be recursive. Unlike recursive function, where exiting the function retains its previous value, the robot cannot retain its previous value when going out of recursion. It must be told explicitly to turn in the opposite direction. So instead of recursion I used a stack for the angles of the robot.

class MazeWalker {
  int mAngle;
  std::stack<int> s;
  Maze &mMaze;
  
  
    public: 
        MazeWalker(Maze &maze): mAngle(0), mMaze(maze) {
        }

        void traverse(bool stopOnFlag);
  
    private:
    
        int left() { mAngle = (mAngle - 90) % 360; return 270; }
        int forward() { mAngle = 0; return 0; }
        int right() { mAngle = (mAngle + 90) % 360; return 90; }
        int reverse(int angle) { mAngle = (360 - angle) % 360; return mAngle; }
        
        bool goLeft() {
            
        }
};

#define MAZE_WALKER_MOVE(f)   \
    mMaze.turn(f);       \
        if (!mMaze.wall()) {  \
            s.push(mAngle);   \
            mMaze.move();   \
            continue;         \
        }
        
void MazeWalker::traverse(bool stopOnFlag) {
    bool stop = false;
    int step = 1;

    while (!stop) {
        
        cout << "Current step: " << step++ << " ";
        mMaze.printCurrentCell();
        
        if (stopOnFlag && mMaze.isFlag())
        {
            cout << "Found flag: ";
            mMaze.printCurrentCell();
            cout << endl;
            return;
        }
            
        if (mMaze.isBreadcrumb()) {
            if (s.empty())
                return;
            
            int angle = s.top();
            s.pop();
            mMaze.turn(angle);
            mMaze.move();
            continue;
        }
            
        MAZE_WALKER_MOVE(left())
        MAZE_WALKER_MOVE(right())
        MAZE_WALKER_MOVE(right())
        
        mMaze.putBreadcrumb();
    }
};


/*
 * 
 */
int main(int argc, char** argv) {
    Maze m(5);
    m.init();
    m.print();
    
    MazeWalker mw(m);
    mw.traverse(true);
    return 0;
}

there is nothing preventing you from implementing this with recursion. The APIs have nothing to do with the ability of using DFS recursively or not.