Check If there exists a Circle

问题:

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

回答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.

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

回答3:

Run the string, see where the robot is at its end and in which direction it looks.

If it is back at the origin, take the maximum distance from the origin it had during the execution and compare to r.

If it isn't back at the origin, then check its orientation:

If it has the same orientation as it had in the beginning, then it will move away from the origin indefinitely, so no such r exists.

If it has a different orientation than it had in the beginning, then it will return to the origin after 4 or 2 iterations of the string, depending on whether it is oriented to the left/right of its original orientation, or the reverse of it, respectively. Now take the maximum distance it had after 2 executions of the string. (Simple case distinctions will show that it will have visited its maximum distance after 2 executions, no matter whether the period is 2 or 4 executions.)

回答4:

string doesCircleExists(string commands) {
    int dir=1; //1 is east; 2 north etc.
    pair<int,int> pos; 
    pos = make_pair(0,0);  //start at origin
    for(int i=0;i<4;i++) {
    for(int i=0;i<commands.size(); i++)
    {
       if(commands[i]=='F')
       {
        if(dir==1) pos.first++;  if(dir==2) pos.second++; 
        if(dir==3) pos.first--; if(dir==0) pos.second--; 
       }
       if(commands[i]=='L') {dir++; dir = dir%4;}
       if(commands[i]=='R') {dir--; dir = dir%4;}
    }
    }
    if(pos.first==0 && pos.second==0 && dir=1) return "YES"; else return "NO";

}

回答5:

This might work:

def encircular(string):

    ini_pos = [0,0]
    position = [0,0]
    direction = 'N'
    directions = {'NL':'W','NR':'E','EL':'N','ER':'S','SL':'E','SR':'W','WL':'S','WR':'N'}
    forward = {'N':[0,1],'E':[1,0],'S':[0,-1],'W':[-1,0]}
    for i in range(4):
        for i in string:
            if i == 'F':
                position = [x+y for x,y in zip(position,forward[direction])]
            else:
                #print(direction+i)
                direction = directions[direction+i]
                #print (direction)
    if ini_pos == position: return 'YES'
    else : return 'NO'

回答6:

def robot_bot(string): 
    face= 0
    pos=[0,0]
    string= string.upper() 
    dirc={0:[1,0],90:[0,1],180:[-1,0],270:[0,-1],360:[1,0],-90:[0,-1],-180:[-1,0],-270:[0,1]}
    for ch in string:
        if ch == "R": face -= 90
        elif ch == "L": face += 90
        if ch == "G":
            pos[0]+=dirc[face][0]
            pos[1]+=dirc[face][1]
        print(pos,face)
        if abs(face) == 360: face=0
    return(True if pos==[0,0] else False )

回答7:

#include <bits/stdc++.h>
using namespace std;
struct point
{
    int x;
    int y;
    int dir;
};
int mod4(int a)
{
    if(a%4 < 0)
        return (a%4 + 4);
    else
        return a%4;
}
int main()
{
    struct point p;
    p.x = 0;
    p.y = 0;
    p.dir = 0;
    string s;cin>>s;
    int j;
    for(int i=0;i<4*s.size();i++)
    {
        j = i%s.size();
        if(s[j] == 'F')
        {
            if(p.dir == 0)//north
                p.y++;
            if(p.dir == 1)//east
                p.x++;
            if(p.dir == 2)//south
                p.y--;
            if(p.dir == 3)//west
                p.x--;
        }
        if(s[j] == 'L')
        {
            p.dir--;
            p.dir = mod4(p.dir);
        }
        if(s[j] == 'R')
        {
            p.dir++;
            p.dir = mod4(p.dir);
        }
        //cout<<p.x<<" "<<p.y<<" "<<p.dir<<endl;
    }
    if(p.x == 0 && p.y ==0 && p.dir == 0)
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;   
}

回答8:

Iterate through the given string once and note the displacement and direction in which you end up. If the displacement is non-zero and the starting and ending directions are the same for the robot for the single iteration, your robot cannot be contained in a circle, else it can be.

Figure:
In the figure, assume that the robot goes from point A to point B after a single iteration of the given string. Now, angle ABC is (90 - theta), which makes angle ABD equal to 90 degrees. With all sides equal, and each angle equal to 90 degrees, quadrilateral ABDE is a square. This is true for any value of theta (acute or obtuse). The proof would be similar if the ending direction after a single iteration is left. For south, the robot will oscillate between points A and B.

Hence, as a solution to your problem, you could just check if the starting and ending direction are the same and that the starting and the ending position are not the same, after the robot completes one iteration of the given string.