# LeetCode 657: Robot Return to Origin

## Problem Restatement

A robot starts at position:

```text
(0, 0)
```

We are given a string called `moves`.

Each character tells the robot to move one step:

| Move | Meaning |
|---|---|
| `U` | Move up |
| `D` | Move down |
| `L` | Move left |
| `R` | Move right |

After executing all moves, return `True` if the robot returns to the origin `(0, 0)`.

Otherwise, return `False`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A string `moves` |
| Output | `True` if the robot ends at `(0, 0)`, otherwise `False` |
| Start position | `(0, 0)` |
| Movement size | Every move changes position by exactly one unit |

Example function shape:

```python
def judgeCircle(moves: str) -> bool:
    ...
```

## Examples

Consider:

```python
moves = "UD"
```

The robot moves:

1. Up to `(0, 1)`
2. Down back to `(0, 0)`

The final position is the origin.

So the answer is:

```python
True
```

Another example:

```python
moves = "LL"
```

The robot moves:

1. Left to `(-1, 0)`
2. Left to `(-2, 0)`

The final position is not the origin.

So the answer is:

```python
False
```

Another example:

```python
moves = "URDL"
```

The robot moves in a square:

```text
(0,0)
 -> (0,1)
 -> (1,1)
 -> (1,0)
 -> (0,0)
```

The robot returns to the origin.

So the answer is:

```python
True
```

## First Thought: Simulate the Movement

The robot position changes after every move.

So we can directly simulate the process.

Keep track of:

| Variable | Meaning |
|---|---|
| `x` | Horizontal position |
| `y` | Vertical position |

Then scan the string one character at a time.

Each move updates either `x` or `y`.

At the end, the robot returns to the origin exactly when:

```text
x == 0 and y == 0
```

## Key Insight

Each pair of opposite moves cancels out.

For example:

| Pair | Effect |
|---|---|
| `U` and `D` | Vertical movement cancels |
| `L` and `R` | Horizontal movement cancels |

So the robot returns to the origin if:

```text
number of U moves == number of D moves
```

and:

```text
number of L moves == number of R moves
```

The simulation approach naturally checks this.

## Algorithm

1. Start with:

```python
x = 0
y = 0
```

2. For each character in `moves`:
   - `U` increases `y`
   - `D` decreases `y`
   - `L` decreases `x`
   - `R` increases `x`

3. After processing all moves:
   - Return whether `(x, y)` equals `(0, 0)`

## Correctness

The variables `x` and `y` always represent the robot's current position.

Initially, the robot starts at `(0, 0)`.

Each move updates the position exactly according to the problem rules:

| Move | Position change |
|---|---|
| `U` | `(x, y + 1)` |
| `D` | `(x, y - 1)` |
| `L` | `(x - 1, y)` |
| `R` | `(x + 1, y)` |

Therefore, after processing all characters, `(x, y)` is the robot's final position.

The robot returns to the origin exactly when both coordinates are zero.

So returning:

```python
x == 0 and y == 0
```

is correct.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We process each move once |
| Space | `O(1)` | Only two integer variables are used |

Here, `n` is the length of `moves`.

## Implementation

```python
class Solution:
    def judgeCircle(self, moves: str) -> bool:
        x = 0
        y = 0

        for move in moves:
            if move == "U":
                y += 1
            elif move == "D":
                y -= 1
            elif move == "L":
                x -= 1
            else:
                x += 1

        return x == 0 and y == 0
```

## Code Explanation

We begin at the origin:

```python
x = 0
y = 0
```

Then we scan the moves string:

```python
for move in moves:
```

For each character, we update the coordinates.

Moving up increases the vertical position:

```python
if move == "U":
    y += 1
```

Moving down decreases the vertical position:

```python
elif move == "D":
    y -= 1
```

Moving left decreases the horizontal position:

```python
elif move == "L":
    x -= 1
```

Otherwise, the move must be `R`:

```python
else:
    x += 1
```

Finally, we check whether the robot returned to the origin:

```python
return x == 0 and y == 0
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.judgeCircle("UD") is True
    assert s.judgeCircle("LL") is False
    assert s.judgeCircle("URDL") is True
    assert s.judgeCircle("") is True
    assert s.judgeCircle("UUDDLLRR") is True
    assert s.judgeCircle("UUDDL") is False
    assert s.judgeCircle("RRDD") is False

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `"UD"` | Simple canceling movement |
| `"LL"` | Ends away from origin |
| `"URDL"` | Square path returns to origin |
| `""` | No movement keeps robot at origin |
| `"UUDDLLRR"` | Multiple canceling moves |
| `"UUDDL"` | One extra move prevents return |
| `"RRDD"` | Different nonzero final position |