algorithm - applications - "computational geometry an introduction"

Marque si existe un círculo

Question

Me preguntaron esto durante una entrevista con Google. Nos dan una cadena que consiste en las letras F, L, R. - ¿Cuál es la instrucción que sigue un robot?

F- avanza por un paso.

Gire a la izquierda.

R- girar a la derecha.

La longitud de la cadena puede ser de hasta 2500 caracteres.

La cuerda se ejecuta infinitas veces. Necesitamos saber si existe un círculo con un radio, r (r puede ser cualquier número real), de modo que el robot nunca abandone el círculo. Me quedé atascado en este punto. Pensé en usar un casco convexo, pero cómo comprobarlo para tiempos infinitos. Se apreciará una explicación con código. Por favor ayuda. Gracias por adelantado

Answer 1

1. Cada ejecución (una ejecución es ejecutar todos los comandos de la cadena dada una vez) cambia dos cosas: la dirección en la que mira el robot y su posición (es decir, cada ejecución la desplaza en algún vector (la dirección de este vector depende de su Dirección inicial antes de la carrera) y la gira).

2. El número de direcciones posibles es 4. Por lo tanto, después de ejecutar la simulación 4 veces, se ve en la misma dirección que lo hizo inicialmente (cada frotación la gira en el mismo ángulo).

3. Es por eso que 4 ejecuciones consecutivas simplemente lo cambian por algún vector sin ninguna rotación.

4. Por lo tanto, solo podemos ejecutar la simulación 4 veces seguidas y ver si se detuvo en el punto original. Si lo hizo, podemos encontrar el círculo mínimo que contiene su camino. De lo contrario, no existe tal círculo.

Answer 2

Ejecutaría 1 iteración para calcular la nueva posición, digamos newx, newy. Luego, calcularía 4 iteraciones más para ver si el robot está de nuevo en newx-newy. Si es así, entonces existe el círculo, de lo contrario no.

El radio sería la distancia máxima a la que se aventuró el robot en su iteración.

Implementación de código -

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

Answer 3

Ejecute la cadena, vea dónde está el robot en su extremo y en qué dirección se ve.

Si está de regreso en el origen, tome la distancia máxima desde el origen que tuvo durante la ejecución y compare con r.

Si no está en el origen, verifique su orientación:

Si tiene la misma orientación que tenía al principio, entonces se alejará del origen indefinidamente, por lo que no existe tal r.

Si tiene una orientación diferente de la que tenía al principio, volverá al origen después de 4 o 2 iteraciones de la cadena, dependiendo de si está orientada a la izquierda / derecha de su orientación original, o al revés de la misma. , respectivamente. Ahora toma la distancia máxima que tenía después de 2 ejecuciones de la cadena. (Las distinciones de casos simples mostrarán que habrá visitado su distancia máxima después de 2 ejecuciones, sin importar si el período es 2 o 4 ejecuciones).

Answer 4

Esto podría funcionar:

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

Answer 5

Iterar a través de la cadena dada una vez y observe el desplazamiento y la dirección en la que termina. Si el desplazamiento no es cero y las direcciones de inicio y final son las mismas para el robot para la iteración única, su robot no puede estar contenido en un círculo, de lo contrario puede ser.

Figura:
En la figura, suponga que el robot va del punto A al punto B después de una única iteración de la cadena dada. Ahora, el ángulo ABC es (90 - theta), lo que hace que el ángulo ABD sea igual a 90 grados. Con todos los lados iguales y cada ángulo igual a 90 grados, el cuadrilátero ABDE es un cuadrado. Esto es cierto para cualquier valor de theta (agudo u obtuso). La prueba sería similar si se deja la dirección final después de una única iteración. Para el sur, el robot oscilará entre los puntos A y B.

Por lo tanto, como solución a su problema, simplemente puede verificar si la dirección de inicio y finalización son las mismas y que la posición de inicio y finalización no son las mismas, después de que el robot complete una iteración de la cadena dada.

Answer 6

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

Answer 7

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 )

Answer 8

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

}