Подтвердить что ты не робот

Проверьте, существует ли круг

Мне было предложено это во время интервью Google. Нам задана строка, состоящая из букв F, L, R. - это инструкция, которую робот следует за

F - идет вперед на один шаг.

L-поворот влево.

R-поворот вправо.

Длина строки может быть до 2500 символов.

Строка запускается бесконечно. Нам нужно определить, существует ли круг с радиусом, r (r может быть любым вещественным числом), так что робот никогда не покидает круг. Я застрял в этой точке. Я думал об использовании выпуклого корпуса, но как проверить его на бесконечные времена. Изучение с кодом будет оценено. Пожалуйста помоги. Спасибо заранее

4b9b3361

ОТВЕТЫ

Ответ 1

  • Каждый запуск (один запуск выполняет все команды данной строки один раз) изменяет две вещи: направление, на которое смотрит робот, и его положение (т.е. каждый пробег сдвигает его на некоторый вектор (направление этого вектора зависит на его начальном направлении перед запуском) и вращает его).

  • Количество возможных направлений - 4. Таким образом, после запуска моделирования 4 раза он выглядит в том же направлении, что и вначале (каждый тр поворачивает его на один и тот же угол).

  • Вот почему 4 последовательных прогона просто сдвигают его на какой-либо вектор без какого-либо вращения.

  • Таким образом, мы можем просто запустить симуляцию 4 раза подряд и посмотреть, остановлена ​​ли она в исходной точке. Если это так, мы можем найти минимальный круг, содержащий его путь. В противном случае такой круг не существует.

Ответ 2

Вы должны запустить 1 итерацию, чтобы вычислить новую позицию, например newx, newy. Затем вы вычислите еще 4 итерации, чтобы узнать, вернулся ли робот к newx-newy. Если это так, то существует круг, иначе нет.

Радиус будет максимальным расстоянием, на котором робот отважился на свою итерацию.

Выполнение кода -

//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

Запустите строку, посмотрите, где находится робот, и в каком направлении он выглядит.

Если он вернулся в начало координат, возьмите максимальное расстояние от начала, которое он имел во время выполнения, и сравните с r.

Если он не вернулся в начало координат, проверьте его ориентацию:

Если он имеет ту же ориентацию, что и в начале, то он будет отходить от начала бесконечно, поэтому такой r не существует.

Если он имеет другую ориентацию, чем в начале, тогда он вернется в начало после 4 или 2 итераций строки, в зависимости от того, ориентирована ли она влево/вправо от исходной ориентации или наоборот, соответственно. Теперь возьмите максимальное расстояние, которое оно получило после двух исполнений строки. (Простые случайные различия покажут, что он посетит свое максимальное расстояние после двух исполнений, независимо от того, является ли период 2 или 4 исполнения.)

Ответ 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

Это может сработать:

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 _ in range(4):
        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]
            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

Итерации через заданную строку один раз и обратите внимание на смещение и направление, в котором вы закончите. Если смещение отличное от нуля, а начальное и конечное направления для робота для одной итерации одинаковы, ваш робот не может содержаться в круге, иначе он может быть.

Рисунок:
На рисунке предположим, что робот переходит из точки A в точку B после одной итерации данной строки. Теперь угол ABC равен (90 - тета), что делает угол ABD равным 90 градусам. Со всеми сторонами равными, и каждый угол, равный 90 градусам, четырехугольник ABDE является квадратом. Это верно для любого значения тета (острый или тупой). Доказательство будет аналогичным, если оставить конечное направление после одной итерации. Для юга робот будет колебаться между точками A и B.

Следовательно, в качестве решения вашей проблемы вы можете просто проверить, совпадают ли начальное и конечное направления, а начальная и конечная позиции не совпадают, после того как робот завершит одну итерацию данной строки.