Robot cleaning algorithm


  • 0
    W

    Write code for a robot cleaner algorithm with 4 given APIs and an unknown starting position in an unknown space (with obstacles in random locations)

    The 4 APIs are:

    • clean(): clean the current location.

    • turnleft(k): turn left k*90 degrees.

    • turnright(k): turn right k*90 degrees.

    • move(): move forward for 1 position and return true, otherwise return false if that’s not possible.

    How do you clean the entire space?


  • 0
    S

    So basically we are passed in a 2D matrix representing the space. Does the function just return the cleaned version of it ? Or would ot return the paths it took to clean the entire matrix?


  • 0
    W

    The shape of the room is unknown, so we are NOT passed in a 2D matrix.
    Just clean the entire space, no need to return the paths.


  • 0
    S
    This post is deleted!

  • 0
    S

    The first step is to get the layout of the room. The simplest way to get the boundary of a closed polygon (room) is to keep the the wall (boundary) of the room along the right (left) of the robot when moving forward. Since the polygon is closed you are guaranteed to return to the starting point.

    march_forward(){
    // This Method maps the boundary of the room and any other obstacles (say table) in the room.
    if(move()){  
               //There is no obstacle in front of us. Ensure the wall is present to the right 
               turnright(1) // If the wall is present, we are staring at it.
    	   	if( !move()){
                		// We are unable to move forward because of the wall, turn left to original direction and continue 
    			map_wall_right();
    			turnleft(1)
                            march_forward()
    
    			}
    		else {
    			// The wall turned right and we turned with it. Continue marching forward.
    			march_forward()
    		}		
    	else{ // move fails 
    	      // There is an obstacle ahead of us. This means the wall turns left
    	    map_wall_ahead();	
    	    turnleft(1)
                march_forward()
    	}
    }
    

    Once the room is mapped, it is just the matter of traversing the enclosed area in the polygon and calling clean() at each step.


  • 1
    L

    @senthilramamurthy
    I don't believe that is the answer.
    Start in a clockwise pattern, any pattern is fine, top, right, left, bottom. Let's call this one cycle. For each cycle find the first un-visited position then traverse into it, then restart the cycle. The cycle will be searched in the same order every time. This will eventually visit all spaces in the room.

    Your starting point will be 0,0. Use a hash map to keep track of visited positions. The hash will be the to point, and the value is the from point. In this manner, you have a way to backtrack. Make sure you increment accordingly like when traversing a 2d matrix and save it in the hash map. Any walls and cleaned spaces will also be saved in this hash map as visited.

    The only scenario that your robot can get stuck is if it enters a space where there are 3 walls and 1 visited node. In that case, you need some logic to check that 4 spaces are already visited and escape it. You could use a queue and another hash map to keep track of un-visited spaces during your traversal. Remove the unvisited spaces from the queue as you traverse. Using both hash tables(visited and un-visited) and the queue, you can make an algorithm to go an un-visited space with the back tracking potential. Then restart your search cycle from there.

    In this way, there is no need for a 2d matrix and the potential to back-track to clean spaces where there is only one way in and out. You can also modify the queue to use a stack, so you can back-track to the nearest space.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.