# Robot

## 489. Robot Room Cleaner

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

```python
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

```python
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).&#x20;

```python
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.

```python
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)

```python
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 
```
