Check If there exists a Circle

Question

I was asked this during a Google Interview. We are given a string consisting of letters- F,L,R. - which is the instruction a robot follows

F- goes forward by one step.

L-turn left.

R- turn right.

String length can be upto 2500 characters.

The string runs itself infinite times. We need to tell if there exists a circle with a radius, r( r can be any real number), such that the robot never leaves the circle. I was stuck at this point.I thought of using convex hull, but how to check it for infinite times.Explanation with code will be appreciated. Please help. Thanks in advance

Answer 1

1. Each run(one run is executing all commands of the given string once) changes two things: the direction which the robot looks to and its position(that is, each run shifts it by some vector(the direction of this vector depends on the its initial direction before the run) and rotates it).

2. The number of possible directions is 4. Thus, after running the simulation 4 times it looks in the same direction as it did initially(each rub rotates it by the same angle).

3. That's why 4 consecutive runs just shift it by some vector without any rotation.

4. Thus, we can just run the simulation 4 times in a row and see if it stopped in the original point. If it did, we can find the minimum circle that contains its path. Otherwise, no such circle exists.

Answer 2

You would run 1 iteration to compute the new position, say newx, newy. Then you would compute 4 more iterations to see if the robot is back to newx-newy. If so, then the circle exists, else not.

The radius would be the maximum distance the robot ventured out in its iteration.

Code implementation -

//North, South, East, West directions #define N 0  #define S 1 #define E 2 #define W 3  // Function to compute the new pos (x, y, dir) after completing one iteration of the string. // It will also update the max radius. void findNewPos(char *str, int *origdir, int *origx, int *origy, double *maxrad) {   int i, len, x, y, dir;     dir = *origdir;   x = *origx;   y = *origy;    len = strlen(str);   i=0;    //Iterate through each character   while(i < len) {     char c = str[i];      switch(c) {     case 'L': // Turn left       switch(dir) {       case N:          x--;          dir = W;          break;       case S:          x++;          dir = E;          break;       case E:          y++;          dir = N;          break;       case W:          y--;          dir = S;          break;       }       break;      case 'R': // Turn right       switch(dir) {       case N:          x++;          dir = E;          break;       case S:          x--;          dir = W;          break;       case E:          y--;          dir = S;          break;       case W:          y++;          dir = N;          break;       }       break;      case 'F': // Go forward       switch(dir) {       case N:          y++;          dir = N;          break;       case S:          y--;          dir = S;          break;       case E:          x++;          dir = E;          break;       case W:          x--;          dir = W;          break;       }       break;     }      // Update max radius till now     double rad = x*x + y*y;     if(rad > *maxrad)       *maxrad = rad;     i++;   }    *origx = x;   *origy = y;   *origdir = dir; }  // Function to compute the max radius of movement, if bounded double findCircle(char *str) {   int x=0, y=0, dir=N;   int refx, refy;   double radius = 0, maxrad = 0;    // Starting from origin(x=0, y=0), find new pos after single iteration   findNewPos(str, &dir, &x, &y, &maxrad);    refx = x;   refy = y;    // Find new positions after 4 more iterations   findNewPos(str, &dir, &x, &y, &maxrad);   findNewPos(str, &dir, &x, &y, &maxrad);   findNewPos(str, &dir, &x, &y, &maxrad);   findNewPos(str, &dir, &x, &y, &maxrad);    // Are we back to position where we were after 1st iteration?   if(x == refx && y == refy) {     printf("Circle exists %f!\n", maxrad);     radius = sqrt(maxrad);   }   else {     printf("Circle does not exist!\n");     radius = -1;   }    return radius; }