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 degrees 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.
Example 1:
Input: instructions = "GGLLGG" Output: true Explanation: 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.
Example 2:
Input: instructions = "GG" Output: false Explanation: The robot moves north indefinitely.
Example 3:
Input: instructions = "GL" Output: true Explanation: The robot moves from (0, 0) -> (0, 1) -> (-1, 1) -> (-1, 0) -> (0, 0) -> ...
Constraints:
1 <= instructions.length <= 100instructions[i] is 'G', 'L' or, 'R'.
The description was taken from https://leetcode.com/problems/robot-bounded-in-circle/.
#O(N) Time, O(1) Spaceclass Solution: def isRobotBounded(self, instructions: str) -> bool: directions = [(0,1), (-1,0), (0,-1), (1,0)] row, col = 0, 0 direction = 0 for move in instructions: if move == "G": row += directions[direction%4][0] col += directions[direction%4][1] elif move == "R": direction += 1 elif move == "L": direction -= 1 return (row,col) == (0,0) or direction%4 != 0In order to find whether the robot is bounded in a circle, we can just look at its final destination after the first iteration through the instructions it is given.
If it ends up in the same place it started at, then it is bounded in a circle, as it is in example one. If it moves in one direction more than the other, then it will make a circle eventually, like in example three.
The only thing that we need to check to see if the robot is not bounded in a circle is if the circle ends up in the final destination or the circle isn't still moving in the initial direction when the first round of instructions is completed.
Let's make a list of possible directions the robot could move in.
directions = [(0,1), (-1,0), (0,-1), (1,0)]
Each number in each tuple represents a row and a coordinate value.
If the robot were to be given an "R" instruction, its row coordinate wouldn't change, but its column value would be by one, it would move one to the right. If it were given another "R" instruction, its column value wouldn't change, but its row value would, it would move one to the right but facing right, so it would move one down. If it were given it again, its row value wouldn't change, but its column value would, it would move one to the right but facing downward which would be one to the left. Lastly, if it were given it again, only its row value would change, it would move one to the right but facing left, so it would move upward.
If we were given strictly "L" instructions, it would be the same thing but the reverse.
Those are the directions in the directions list respectively. Also notice that if you were to add all of these values together it would equal zero, zero, which is the initial point.
By utilizing that, we will create a row, column, and direction pointers to keep track of these coordinates.
row, col = 0, 0 direction = 0
Now we can just go through the set of instructions the robot is given.
If the instruction is to go forward, then we will need to look at the directions list to see which way "forward" is from the current point. To do that, we will add whichever direction coordinates from the current direction we are at to our current coordinates.
for move in instructions: if move == "G": row += directions[direction%4][0] col += directions[direction%4][1]
The modular sign is helpful in maintaining rotations in arrays. If we had a direction value that is greater than four, this would let us rotate around so we don't get an out-of-bounds error.
If the instruction is to go right, we will just increase our place in the directions list, as mentioned earlier.
elif move == "R": direction += 1
If the instruction is to go left, we just decrease our place in the instructions list.
elif move == "L": direction -= 1
Once we have gone through the instruction we will check if we are still at the same place, or the direction isn't still the first direction. If that were the case, the robot would have only gotten "G" instructions or an even number of "L" and "R" instructions that canceled each other out.
return (row,col) == (0,0) or direction%4 != 0