algorithm sort Dos robots en una línea




sorting algorithms (4)

Probablemente conozcas el problema con los dos robots caídos en una línea cuando necesitas programarlos para que se encuentren.

Se lanzan dos robots desde un avión y aterrizan en una sola línea (con posiciones discretas) usando un paracaídas que se deja en el punto de aterrizaje. Los robots están mirando hacia el norte, están separados por una distancia desconocida, y uno ha aterrizado directamente al este del otro.

Los robots ahora deben programarse de manera que se encuentren. Se les puede indicar que se muevan a la izquierda o a la derecha a una posición cercana y que verifiquen si hay un paracaídas en la ubicación actual. Si el otro robot se encuentra, ambos robots se detienen allí y viven felices para siempre.

La verificación del paracaídas puede ejecutar de manera condicional cualquier cantidad de instrucciones y cualquier bloque de instrucciones puede repetirse incondicionalmente. Escriba un programa que ambos robots puedan seguir simultáneamente y qué garrapatas puedan encontrar.

Tienes que crear un algoritmo genérico (un poco pleonástico) que aplique a ambos robots garantiza que los robots se encontrarán. Dejan su paracaídas en el lugar donde se dejan caer y pueden comprobar si en la posición actual hay un paracaídas.

La declaración original está aquí: http://en.wikibooks.org/wiki/Puzzles/Logic_puzzles/Parachuted_Robots También hay una solución que no entiendo. Si alguien puede darle sentido, ayúdenme con un poco de explicación. Cualquier otra solución sería muy apreciada.

Mi primer pensamiento sobre este problema sería programar el robot para que elija aleatoriamente para ir primero a la derecha o a la izquierda, y luego hacer algo como una búsqueda exponencial: primero ir 2 posiciones a la derecha, luego 4 a la izquierda, etc. Si está en una de estas " viajes "en la derecha o la izquierda el robot encuentra el segundo paracaídas (el que fue utilizado por el otro robot), el robot solo buscará en esa dirección. ¿Tiene esto algún sentido?

¡Muchas gracias!


Yo hice esto:

start: left
       skipNext
       goto start
fastL: left
       left
       goto fastL

La idea es simple: vamos a la izquierda un poco. Uno de los robots (el de la derecha) finalmente chocará con un paracaídas y luego se saltará del bucle del puño, e ingresará el segundo que lo hace ir a la izquierda el doble de rápido.


Me parece que tu algoritmo debería funcionar. La idea en la solución publicada es que ambos robots mantienen un patrón de derecha a derecha a izquierda, lo que significa que están avanzando a cierto ritmo. Pero cuando el robot de la izquierda encuentra el paracaídas del otro, comienza a moverse hacia la derecha a un ritmo más rápido, ya que no se mueve una vez hacia la izquierda como parte de su patrón de desplazamiento, sino que sigue hacia la derecha, alcanzando finalmente al robot en el derecho.


Ambos robots se mueven hacia la izquierda hasta que el robot derecho encuentra el paracaídas del robot izquierdo y comienza a correr hacia el robot izquierdo. Entonces chocan.

start: left
       skipNext
       goto start
       goto moveLeftFast

moveLeftFast: left
              goto moveLeftFast

mi programa es en realidad más corto, y funciona como un encanto para:

start: left
skipNext
goto start
next: left
goto next

esto funciona porque el segundo ciclo es más rápido que el primer ciclo

Puedes probar tu programa aquí: http://david-peter.de/parachuting-robots/





search