Robot

489. Robot Room Cleaner

Given a robot cleaner in a room modeled as a grid by using 4 APIs

class Robot:
    def move(self)"
    """
    Returns true and robot moves into the cell.
    Returns false if the cell in front is blocked.
    """
    def turnLeft(self)
    def turnRight(self)
    def clean(self)

• Backtrack

• O (4 ^ (n-m)), n is # of grid, m is # of blocks. Every grid can chose 4 directions

def cleanRoom(self, robot):
    """
    :type robot: Robot
    :rtype: None
    """
    dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))
    visit = set()
    
    def goBack():
        robot.turnRight()
        robot.turnRight()
        robot.move()
        robot.turnRight()
        robot.turnRight()
        
    def backtrack(x = 0, y = 0, d = 0):
        visit.add((x, y))
        robot.clean()
        for i in range(4):
            newD = (d + i) % 4
            newX = x + dirs[newD][0]
            newY = y + dirs[newD][1]
            if (newX, newY) not in visit and robot.move():
                backtrack(newX, newY, newD)
                goBack()
            robot.turnRight()
    backtrack()

657. Robot Return to Origin

There is a robot starting at position (0, 0), the origin, on a 2D plane. Given a sequence of its moves, judge if this robot ends up at (0, 0) after it completes its moves.

The move sequence is represented by a string, and the character moves[i] represents its ith move. Valid moves are R (right), L (left), U (up), and D (down).

def judgeCircle(self, moves: str) -> bool:
    step = collections.Counter(moves)
    return step['R'] == step['L'] and step['U'] == step['D']

874. Walking Robot Simulation

A robot on an infinite grid starts at point (0, 0) and faces north. The robot can receive one of three possible types of commands:

• -2: turn left 90 degrees

• -1: turn right 90 degrees

• 1 <= x <= 9: move forward x units

Return the square of the maximum Euclidean distance that the robot will be from the origin.

def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
    obsSet = set(map(tuple, obstacles))
    dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))
    d = 0
    x, y = 0, 0
    ans = 0
    
    for c in commands:
        if c == -2:
            d = (d + 3) % 4
        elif c == -1:
            d = (d + 1) % 4
        else:
            while (x + dirs[d][0],  y + dirs[d][1]) not in obsSet and c != 0:
                x += dirs[d][0]
                y += dirs[d][1]
                c -= 1
                ans = max(ans, x**2 + y**2)
    return ans

1041. Robot Bounded In Circle

On an infinite plane, a robot initially stands at (0, 0) and faces north. The robot can receive one of three instructions:

• "G": go straight 1 unit;

• "L": turn 90 degrees to the left;

• "R": turn 90 degress to the right.

The robot performs the instructions given in order, and repeats them forever.

Return true if and only if there exists a circle in the plane such that the robot never leaves the circle.

• It can be a cycle iff 1. It comes back to the starting point 2. It is not toward to starting position (North)

def isRobotBounded(self, instructions: str) -> bool:
    dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    d = 0
    x, y = 0, 0
    
    for ins in instructions:
        if ins == 'R':
            d = (d + 1) % 4
        elif ins == 'L':
            d = (d + 3) % 4
        else:
            x = x + dirs[d][0]
            y = y + dirs[d][1]
            
    return (x == 0 and y == 0) or d != 0