Check If there exists a Circle

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;
}

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.