Rompecabezas | Dos robots con paracaídas en línea.

Problema
Dos robots aterrizan con sus paracaídas en una recta numérica unidimensional infinita. Ambos lanzan sus paracaídas tan pronto como aterrizan y comienzan a moverse. Solo se les permite hacer uso de las siguientes funciones.

I. moveLeft() // el robot se mueve hacia la izquierda 1 unidad en 1 unidad de tiempo

II. moveRight() // el robot se mueve a la derecha 1 unidad en 1 unidad de tiempo

tercero noOperation() // el robot no se mueve y tarda 1 unidad de tiempo

IV. onTopOfParachute() // devuelve verdadero si el robot está parado encima de cualquiera de los paracaídas, de lo contrario, es falso

V. didWeMeet() // devuelve verdadero si el robot se encuentra con el otro robot, de lo contrario falso

Escribe una función para que los robots se encuentren. Los robots ejecutarán la misma copia de esta función.

Solución:
Enfoque 1:
Mueva ambos robots en direcciones opuestas y en cada paso verifique si se encuentran o no.
Pero esto no funcionará . Considere el robot 1 en la posición 0 y el robot 2 en la posición 100. Si el robot 1 se mueve en la dirección correcta y el robot 2 se mueve en la dirección izquierda, se encontrarán en la posición 50. Pero si el robot 1 se mueve en la dirección izquierda y el robot 2 se mueve en la dirección correcta, nunca se encontrarán. Como no tenemos ningún medio para averiguar la coordenada del robot. Este enfoque no funcionará.

Enfoque 2:
Mueva ambos robots en la dirección izquierda. Si un robot cruza un paracaídas. Invierta la dirección del segundo robot y continúe moviendo el primer robot en la misma dirección.
Pero esto no funcionará . Porque ambos robots ejecutan una copia separada de su programa. Un programa solo puede influir en el robot que ejecuta este programa y no en el otro robot, ya que lo ejecuta una copia del mismo programa por separado. Y su movimiento se rige por ese programa, las variables asignadas en uno no funcionarán en otro, es decir, no es posible cambiar la dirección de otro robot desde el programa ejecutado por este robot.

Enfoque 3:
Siga este patrón moveLeft() 1 vez, moveRight() 2 veces, moveLeft() 3 veces y así sucesivamente. En cada iteración, el robot pasará por encima de su propio paracaídas una vez. Pero después de cierto tiempo, un robot pasará por encima de su propio paracaídas y también del paracaídas de otro robot. En este punto, se ha encontrado con el otro robot.

Enfoque 4:
mantenga una bandera si el robot ha alcanzado el paracaídas del otro o no. Si ha alcanzado, llame a moveLeft() dos veces, de lo contrario, llame a moveLeft() y noOperation(). De esta manera, un robot duplicará su velocidad tan pronto como alcance el paracaídas del otro y eventualmente se encontrarán.
Nota: No mueva un robot con el doble de velocidad que otro desde el punto de aterrizaje en adelante. Como no tenemos ninguna información sobre qué robot está detrás y qué robot está al frente. Entonces, si el robot delantero se mueve con el doble de velocidad que el robot rezagado, nunca podrá atraparlo, por lo tanto, nunca se encontrará.

Pseudocódigo:

 void roboMeet()
{
  // set flag as false.
  bool reachedParachute = false;

  // Till both robots meet
  while( !didWeMeet() )
  {
    // If flag is set, move left twice.
    if(reachedParachute)
    {
        moveLeft();
        moveLeft();
    }
        
    // Else walk left for 1 unit of time
    // and stop for 1 unit.   
    else
    {
        moveLeft();
        noOperation();
    }
                  
    // If reach on top of parachute, set flag as true.
    if( onTopOfParachute() )
    {
      reachedParachute = true;
    }
  }
}

Referencia: https://www.geeksforgeeks.org/amazon-interview/
https://www.geeksforgeeks.org/one97-interview-experience-set-2/
Este artículo es una contribución de Anuj Chauahan . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.