Robot command sequence


  • 0
    N

    A robot is placed on a 2D grid at origin (0, 0) facing North.

    The robot receives three possible commands:

    1. M = Move forward one step in the direction it is facing.
    2. L = Rotate left 90 degrees.
    3. R = Rotate right 90 degrees.

    Given a sequence of commands, the robot will loop through these commands indefinitely.

    Given a string which describes the sequence of commands, determine if it is possible to trap the robot in a circle of finite radius.

    For example,

    Given s = "GGGL",

    Return true. Because the robot loops in a rectangle.

    Given s = "GGLGGR",

    Return false. Because the robot keeps moving toward the north west direction, farther and farther away from the origin.


  • 0
    A

    why given s = "GGGL" will return true.
    What is G command?
    is G == M?


  • 2

    I believe so. I think that very interesting case is LRLRLRLRLRLR....which returns true, robot doesn't move


  • 1
    A
    boolean isLooping(String cmds) {
        int lastDirection = ((sumUp(cmds, "L") - sumUp(cmds, "R")) mod 4);
        ruten (lastDirection != 0) ? true : false;
    }
    
    int sumUp(String cmds, char s) {
        int total = 0;
        for (int i = 0; i<cmds.length; i++) {
            if (cmds[i] == s) total++;
        }
        ruten total;
    }
    

  • 3
    G

    @astone thanks for sharing!
    However, except for none-"G" cases, other cases such as "GG, LL, GG, RR", just counting difference is also not enough.

    I'm thinking that, first we follow command and finish one cycle, and got the direction and (x,y)

    1. If robot comes back to beginning point, regardless of direction, answer is true;
    2. If robot is not at beginning point, as long as its direction is not the same when it started, answer is true;
    3. else is false;

  • 0
    V

    Use a two dimension array to simulate the actions on x and y axis actions (1,0), (0,1), (0,-1), (-1,0) and a cursor pointing to the first element moves according to the L/R action. Then on every G, add the current cursor's value to the total of X and Y respectively. At the end, returns true if both X and Y counts are zero.

    class Solution {
    public:
      bool robotCommand(string s) {
        int action[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int x = 0, y=0;
        int cur = 0;
        for (int i=0; i<s.size(); i++) {
          if (s[i] == 'R')
            cur = (cur+1)%4;
          else if (s[i] == 'L')
            cur = (cur+3)%4;
          else {
            x += action[cur][0];
            y += action[cur][1];
          }
        } 
        return x == 0 && y == 0;
      }
    };
    

  • 0
    I

    valleynerd's solution is almost there. let's consider 2 different cases:

    1. the robot come back to (0, 0) and face any direction. then the robot can always come back to (0, 0) no matter what the final direction is.

    2. the robot go to some point (dx, dy), except the origin, and face direction 'd'.

    • d is the same as the initial direction (N): the robot will not go back again cause the position after each session increases (dx, dy).
    • d is the opposite direction (S): the robot will go back to the origin and face N in the next session.
    • d is W or E: the robot will go back to the origin every 4 sessions.

    the answer should be:

    (begin_position == end_position) || (begin_direction != end_position)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.