Leetcode 1041. Robot Bounded In Circle

Problem Explanation

The problem is about a robot moving in an infinite plane. The robot initially stands facing north at the coordinate (0, 0). The robot can move according to three instructions 'G', 'L' and 'R'. 'G' means go straight 1 unit. 'L' means turn left by 90 degrees. 'R' means turn right by 90 degrees. The robot will repeat the given instructions indefinitely. The problem is to determine if there exists a circle in the plane such that the robot never leaves the circle based on the given instructions.

For example, if the instructions given is "GGLLGG", the robot moves from (0,0) to (0,2), turns 180 degrees, and then returns to (0,0). When repeating these instructions, the robot remains in the circle of radius 2 centered at the origin. Therefore, the output is true.

Solution Approach

The approach is to simulate the process by keeping track of the robot's position as well as direction as it follows the instructions. We use vector arrays to represent the 4 possible directions (north, east, south, west). Initially, the robot's position is at the origin (0,0) and it faces north.

As the robot performs each instruction, we update its position and direction. If the instruction is 'G', it moves forward in the direction it is facing. If the instruction is 'L', it turns left by changing the direction to the next one in anti-clockwise order. If the instruction is 'R', it turns right by changing the direction to the next one in clockwise order.

After all instructions are performed, if the robot ends up at its starting position, or it is not facing north, we return true, indicating that the robot is moving in a circle. Otherwise, we return false.

This approach takes advantage of the fact that if the robot is moving in a circle, after one cycle of instructions, it must either return to its original position or move in a different direction. Therefore, by checking the robot's final position and direction after one cycle of instructions, we can determine whether it is moving in a circle.

The main data structure used in this solution is an array to represent the 4 possible directions.

Solution in Python

1
2python
3class Solution:
4    def isRobotBounded(self, instructions: str) -> bool:
5        x, y, dx, dy = 0, 0, 0, 1  # initial position (x, y) and direction (dx, dy)
6        for i in instructions:
7            if i == 'G':
8                x, y = x + dx, y + dy  # move forward
9            elif i == 'L':
10                dx, dy = -dy, dx  # turn left
11            else:
12                dx, dy = dy, -dx  # turn right
13        return (x, y) == (0, 0) or (dx, dy) != (0, 1)  # check if it is in circle

Solution in Java

1
2java
3public class Solution {
4    public boolean isRobotBounded(String instructions) {
5        int x = 0, y = 0, dx = 0, dy = 1;
6        for (char i : instructions.toCharArray()) {
7            if (i == 'G') {
8                x += dx; 
9                y += dy;
10            } else if (i == 'L') {
11                int temp = dx; 
12                dx = -dy; 
13                dy = temp;
14            } else {
15                int temp = dx; 
16                dx = dy; 
17                dy = -temp;
18            }
19        }
20        return (x == 0 && y == 0) || (dx != 0 || dy != 1);
21    }
22}

Solution in JavaScript

1
2javascript
3var isRobotBounded = function(instructions) {
4    let x = 0, y = 0, dx = 0, dy = 1;
5    for (let i of instructions) {
6        if (i === 'G') {
7            x += dx; 
8            y += dy;
9        } else if (i === 'L') {
10            [dx, dy] = [-dy, dx];
11        } else {
12            [dx, dy] = [dy, -dx];
13        }
14    }
15    return (x === 0 && y === 0) || (dx !== 0 || dy !== 1);
16};

Solution in C++

1
2c++
3class Solution {
4public:
5    bool isRobotBounded(string instructions) {
6        int x = 0, y = 0, dx = 0, dy = 1;
7        for (char i : instructions) {
8            if (i == 'G') {
9                x += dx; 
10                y += dy;
11            } else if (i == 'L') {
12                swap(dx, dy); dy = -dy;
13            } else {
14                swap(dx, dy); dx = -dx;
15            }
16        }
17        return (x == 0 && y == 0) || (dx != 0 || dy != 1);
18    }
19};

Solution in C#

1
2c#
3public class Solution {
4    public bool IsRobotBounded(string instructions) {
5        int x = 0, y = 0, dx = 0, dy = 1;
6        foreach (char i in instructions) {
7            if (i == 'G') {
8                x += dx; 
9                y += dy;
10            } else if (i == 'L') {
11                int temp = dx; 
12                dx = -dy; 
13                dy = temp;
14            } else {
15                int temp = dx; 
16                dx = dy; 
17                dy = -temp;
18            }
19        }
20        return (x == 0 && y == 0) || (dx != 0 || dy != 1);
21    }
22}

Conclusion

The problem of determining whether a robot moves in a circle or not based on given instructions is both interesting and practical. It models real-world situations such as unmanned vehicles moving according to programmed instructions.

The problem involves control and logic, and thus is a great problem to understand and master the basics of programming. This explanation and solution should serve as a good guide for beginners in programming.

Though the provided solutions above are quite optimal, they can be improved using different algorithms and data structures. We have covered only linear solutions here because they are relatively straightforward. However, depending on the constraints of the problem, other types of solution such as dynamic programming or depth-first search could also be possible, albeit more complex.

In any case, the main goal of this problem is not merely to solve it, but to learn and understand the logic and control flow of the algorithms, which are fundamental concepts in computer science and programming. It is our hope that this explanation and guide have been helpful in achieving this goal.

Happy coding!


Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ