Robot Room Cleaner

Hard

Robot Room Cleaner

You're given a room that a robot needs to clean. The room is conceptually a grid, but the robot doesn't know the dimensions or layout beforehand. The robot can:

move(): Attempts to move one cell forward in its current direction. Returns true if the move was successful (the cell is clean and not blocked), and false otherwise.
turnLeft(): Turns the robot 90 degrees to the left.
turnRight(): Turns the robot 90 degrees to the right.
clean(): Cleans the current cell.

The robot starts at an unknown location within the room, facing an unknown direction. The room may contain obstacles.

Your task is to write an algorithm to clean every reachable cell in the room.

Example:

Imagine a simple 3x3 room where the robot starts in the center, and there's an obstacle to the north.

    _ _ _
   |_|_|_|
   |_|R|_|
   |_|_|_|

The robot (R) must traverse and clean all the _ cells. If the top-middle cell was an obstacle, the robot's move() function would return false if it attempted to move north from the center cell. However, the robot must still navigate to all other available cells.

Constraints:

The room is rectangular.
The robot cannot move outside the boundaries of the room.
The robot can only sense whether the cell in front of it is clean or blocked.

Write a function cleanRoom(robot) that takes the robot object as input and instructs the robot to clean the entire room.

Robot Room Cleaner

Hard

Robot Room Cleaner

You're given a room that a robot needs to clean. The room is conceptually a grid, but the robot doesn't know the dimensions or layout beforehand. The robot can:

move(): Attempts to move one cell forward in its current direction. Returns true if the move was successful (the cell is clean and not blocked), and false otherwise.
turnLeft(): Turns the robot 90 degrees to the left.
turnRight(): Turns the robot 90 degrees to the right.
clean(): Cleans the current cell.

The robot starts at an unknown location within the room, facing an unknown direction. The room may contain obstacles.

Your task is to write an algorithm to clean every reachable cell in the room.

Example:

Imagine a simple 3x3 room where the robot starts in the center, and there's an obstacle to the north.

    _ _ _
   |_|_|_|
   |_|R|_|
   |_|_|_|

The robot (R) must traverse and clean all the _ cells. If the top-middle cell was an obstacle, the robot's move() function would return false if it attempted to move north from the center cell. However, the robot must still navigate to all other available cells.

Constraints:

The room is rectangular.
The robot cannot move outside the boundaries of the room.
The robot can only sense whether the cell in front of it is clean or blocked.

Write a function cleanRoom(robot) that takes the robot object as input and instructs the robot to clean the entire room.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the room (number of rows and columns), and what is the maximum size the room can be?
How is the room represented? Is it a 2D array or some other data structure, and what values represent a clean vs. an obstacle?
When the robot encounters an obstacle, should it attempt to move forward indefinitely, or is there a limit to the number of times it can attempt to move in the same direction before trying another direction?
Is the robot's initial position always guaranteed to be a clean cell, and do I need to ensure the robot returns to its starting position at the end?
If the room is already completely clean, what should the algorithm do?

Brute Force Solution

Approach

The robot needs to clean every room. The brute force method makes the robot try every possible path, moving forward, turning, and backtracking until it has explored everywhere it can possibly go. It's like trying every single maze solution until one works.

Here's how the algorithm would work step-by-step:

Start the robot at its initial position.
Make the robot move forward one step if it can.
If it hits a wall, make it turn to the right.
After turning right, try moving forward again.
If it still can't move forward after turning, make it turn right again, and repeat until it has turned all the way around.
If it has turned all the way around and still can't move, make it backtrack one step to where it came from.
Keep track of all the rooms the robot has visited to avoid cleaning the same room twice unnecessarily.
Continue these steps until the robot has no more unvisited rooms to reach and cannot move anywhere new.

Code Implementation

def robot_room_cleaner_brute_force(robot): 
    visited_cells = set()
    current_direction = 0  # 0: up, 1: right, 2: down, 3: left
    current_row = 0
    current_col = 0

    def move_forward():
        nonlocal current_row, current_col
        if current_direction == 0:
            current_row -= 1
        elif current_direction == 1:
            current_col += 1
        elif current_direction == 2:
            current_row += 1
        else:
            current_col -= 1

    def move_back():
        nonlocal current_row, current_col
        if current_direction == 0:
            current_row += 1
        elif current_direction == 1:
            current_col -= 1
        elif current_direction == 2:
            current_row -= 1
        else:
            current_col += 1

    def get_current_cell():
        return (current_row, current_col)

    while True:
        current_cell = get_current_cell()
        if current_cell not in visited_cells:
            robot.clean()
            visited_cells.add(current_cell)

        can_move_forward = robot.move()

        if can_move_forward:
            move_forward()
            continue
        else:
            # Try all directions by turning right
            turned_count = 0
            while turned_count < 4:
                robot.turn_right()
                current_direction = (current_direction + 1) % 4
                turned_count += 1
                can_move_forward = robot.move()

                if can_move_forward:
                    move_forward()
                    break

            # If we can't move anywhere, backtrack
            if turned_count == 4:
                move_back()

                robot.turn_right()
                robot.turn_right()
                if not robot.move():
                  break
                move_forward()
                robot.turn_right()
                robot.turn_right()

        all_cleaned = True
        for row_delta in range(-10, 11):
            for col_delta in range(-10, 11):
                test_row = current_row + row_delta
                test_col = current_col + col_delta
                if (test_row, test_col) not in visited_cells and robot.is_valid_move(row_delta, col_delta):
                    all_cleaned = False
                    break
            if not all_cleaned:
                break

        if all_cleaned and not can_move_forward:
            break

    return list(visited_cells)

Big(O) Analysis

Time Complexity

O(n) – The robot explores each reachable room at most a constant number of times (due to backtracking and turning). The input size, n, represents the number of reachable rooms in the grid. Since each room is visited a limited number of times, the total number of operations grows linearly with the number of rooms. Thus, the time complexity is O(n).

Space Complexity

O(N) – The algorithm keeps track of all visited rooms to avoid redundant cleaning. This implies using a data structure, such as a set or hash map, to store the coordinates of each visited room. In the worst-case scenario, the robot might need to visit every room in the environment. Therefore, if we consider N to be the number of rooms in the environment, the space complexity is proportional to the number of visited rooms, resulting in O(N) space complexity.

Optimal Solution

Approach

The problem involves simulating a robot cleaning a room. Instead of exhaustively exploring every possible path, the efficient solution relies on a depth-first search strategy combined with backtracking to systematically explore the room and ensure complete cleaning.

Here's how the algorithm would work step-by-step:

Imagine the robot starts at a known location and direction.
The robot tries to move forward. If it can't (because of a wall), it turns right.
If the robot *can* move forward, it cleans the current cell, marks it as visited, and then moves forward.
After moving forward, the robot repeats the process of trying to move in all directions.
Once the robot has tried all four directions from its current location (meaning it's surrounded by visited cells or walls in every direction), it needs to go back to where it came from.
To go back, the robot turns around and moves forward. It keeps doing this until it finds a cell with unexplored directions.
The robot keeps exploring and backtracking until it returns to its starting position and has explored all possible paths. This guarantees the entire room has been cleaned.

Code Implementation

class Robot:
    def move(self): 
        return True
    def turn_left(self): 
        return
    def turn_right(self): 
        return
    def clean(self): 
        return

def clean_room(robot):
    visited = set()
    # Directions: up, right, down, left
    directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]

    def go_back():
        robot.turn_right()
        robot.turn_right()
        robot.move()
        robot.turn_right()
        robot.turn_right()

    def explore(row, col, current_direction):
        visited.add((row, col))
        robot.clean()

        for index in range(4):
            new_direction = (current_direction + index) % 4
            new_row = row + directions[new_direction][0]
            new_col = col + directions[new_direction][1]

            #Avoid exploring already cleaned or obstacle cells
            if (new_row, new_col) not in visited:
                robot.turn_right()

                if robot.move():
                    # Explore in the new direction.
                    explore(new_row, new_col, new_direction)
                    # Backtrack after exploring the new direction.
                    go_back()

    explore(0, 0, 0)

Big(O) Analysis

Time Complexity

O(n) – The algorithm essentially visits each cell in the room at most a constant number of times. n represents the number of cells in the room. The robot explores each cell, cleans it, and backtracks when necessary. Each cell's four directions are checked, but that's a constant factor. Therefore, the time complexity is directly proportional to the number of cells, making it O(n).

Space Complexity

O(N) – The space complexity is dominated by the recursion depth and the visited set. The maximum recursion depth corresponds to the longest path the robot can take without revisiting a cell. In the worst-case scenario, the robot may need to visit all N cells in the room before returning to the starting position, leading to a recursion depth of O(N). Additionally, we store visited cells in a set to avoid re-cleaning. This set can grow to a size proportional to the number of cells, also O(N). Therefore, the overall auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty room (no cells)	The base case for the recursion should immediately return, avoiding any processing.
Room with a single cell	The robot cleans it and returns without any further movements.
Room is a straight line (1xn or nx1)	The algorithm should handle this by moving along the line, cleaning each cell, and turning around at the end if necessary.
Room is a fully walled-in space (no exits)	The robot might get stuck in the initial cell if it cannot move, requiring a check for this and immediate termination.
Robot starts in a dirty cell with no cleanable adjacent cells	The robot cleans the current cell and algorithm will backtrack immediately as there is nowhere else to go.
Circular room layout where returning to the starting cell doesn't indicate full exploration	Maintain a set of visited cells to avoid infinite loops and ensure full exploration, regardless of cyclic paths.
Integer overflow in distance calculations (if applicable)	Use appropriate data types to prevent overflow (e.g., long) or ensure calculations are done in a way that prevents overflow.
Maximum recursion depth exceeded for very large rooms	While unlikely given reasonable room sizes, consider iterative solution instead of recursive or implement tail-call optimization.