DeepRest

Robot Bounded In Circle

Jan 9th, 2022 (edited)
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.00 KB | None | 0 0
  1. '''
  2. First part:
  3. Direction of robot at any point = [(count of L) - (count of R)]%4
  4. Every L is nullified by R. Thus only L-R matter
  5. Every 4 L nullify their effects
  6. Every 4 R nullify their effects resetting to initial direction
  7. Here the order of left and right does not matter, they can be separated by Gs and in any permutation.
  8. Also, 2 lefts = down and 3 lefts = right, and
  9.      2 rights = down and 3 rights = left
  10. 4 lefts = 4 rights = initial direction = up. This way the cycle restarts after 4 L or 4 R
  11. If initial direction is up
  12. Thus the final direction of n L moves depends on value of n%4 in this way:
  13. N%4 = 0 --> up
  14.    = 1 --> left
  15.    = 2 --> down
  16.    = 3 --> right
  17. for n R moves it depends on (4-n%4)%4 in same way. This can ve verified
  18. Based on the current direction, the effect of G is decided(in +ve X, -ve X, +ve Y or -veY)
  19.  
  20. Second part:
  21. 1. If final direction of robot is down then it will reach the starting point in second iteration.
  22. x, y --> x+a, y+b --> x, y (here x, y is origin a, b is resultant horizontal and vertical displacement in one cycle)
  23. 2. If final direction of robot is left or right it will reach the starting point in fourth iteration.
  24. [Just for proof]
  25. For left: x,y --> x-b, y+a --> x-b-a, y+a-b --> x-a, y-b --> x,y
  26. [If final direction is left in first cycle, it will be down in second, right in third and up in fourth)
  27. Same can be said for right
  28. 3. If a, b = 0, 0 then it will be always bounded
  29. 4. Only in case where a, b are non-zero and direction is up, it will be unbounded
  30. '''
  31. class Solution:
  32.     def isRobotBounded(self, instructions: str) -> bool:
  33.         direction = 0
  34.         x, y = 0, 0
  35.         mp = {0: (0,1), 1: (-1,0), 2: (0, -1), 3: (1, 0)}
  36.         for i in instructions:
  37.             if i == 'L':
  38.                 direction = (direction + 1)%4
  39.             elif i == 'R':
  40.                 direction = (direction - 1)%4
  41.             else:
  42.                 x += mp[direction][0]
  43.                 y += mp[direction][1]
  44.         return (x==0 and y==0) or direction != 0
Add Comment
Please, Sign In to add comment