Collision de robots

Deux robots sont parachutés sur une ligne de longueur infinie. Ils atterrissent chacun à un endroit au hasard sur cette ligne et laissent leur parachute à l'endroit où ils ont atterrit.

Votre but est de rédiger un programme pour les robots qui les amènent à rentrer en collision l'un avec l'autre.
Pour ce faire, vous disposez de 4 types d'instruction :
(1) Se déplacer d'une unité vers la droite
(2) Se déplacer d'une unité vers la gauche
(3) Sauter l'instruction suivante s'il n'y a pas de parachute à cet endroit
(4) Aller à l'instruction n°...
Chaque instruction met une seconde pour être exécutée.

Essayez de faire le programme le plus court possible.
Il peut être le même pour les 2 robots.

Précision :
- Le programme doit évidemment être de taille finie.
- Les instructions du programme sont numérotées.
- Quand le robot doit effectuer l'instruction (3), si un parachute se trouve là où le robot est, il effectue l'instruction suivante. Sinon, il saute l'instruction suivante et effectue l'instruction d'après.
- Voici un exemple de programme pour montrer comment s'utilise l'instruction (4) :
1. Aller à l'instruction 3.
2. Se déplacer d'une unité vers la droite
3. Se déplacer d'une unité vers la gauche
4. Allez à l'instruction 3.
Le robot commence par exécuter la première instruction. Elle lui dit d'aller à l'instruction 3.
L'instruction 2. n'est donc pas exécutée. Le robot passe à la 3.
Il se déplace d'une unité vers la gauche. L'instruction suivante est la 4., qui lui indique d'aller à l'instruction 3.
Le robot exécute l'instruction 3. et se déplace vers la gauche, puis exécute l'instruction suivante qui est la 4., qui le ramène à l'instruction 3.
Et ainsi de suite...
Ce programme fait se déplacer le robot indéfiniment vers la gauche.

A vous de jouer pour trouver un programme qui fasse se cogner les 2 robots !

La solution de cette énigme est la suivante :

Vous avez peut-être pensé à essayer de faire faire aux robots des "va-et-vient" de plus en plus long. Le problème est qu'avec les instructions dont on dispose, on ne peut faire de "compteur" qui servirait à stopper le robot au bout d'un moment pour le faire aller dans l'autre sens. Il faut donc chercher ailleurs la solution.

L'idée est de faire aller les 2 robots dans la même direction, par exemple tous les 2 vers la droite (ou tous les 2 vers la gauche, peu importe) à une certaine vitesse. A un moment donné, le robot qui était à gauche de l'autre au départ va rencontrer le parachute de l'autre robot. On va alors faire "accélérer" ce robot pour qu'il rattrape l'autre, qui, lui, aura continué à la même allure puisqu'il n'aura pas croisé de parachute.

Voilà ce que cela donne en pseudo-programmation (les 2 robots ont le même programme) :
1. Se déplacer d'une unité vers la droite
2. Sauter l'instruction suivante s'il n'y a pas de parachute à cet endroit
3. Aller à l'instruction n°5
4. Aller à l'instruction n°1
5. Se déplacer d'une unité vers la droite
6. Aller à l'instruction n°5

Le comportement de chaque robot sera le suivant avec ce programme :
Tant qu'il n'a pas rencontré de parachute, il boucle sur les instructions 1, 2 et 4, il se déplace donc d'une unité vers la droite toutes les 3 secondes.
A partir du moment où il rencontre un parachute, il boucle sur les instructions 5 et 6, il se déplace donc d'une unité vers la droite toutes les 2 secondes.
Le robot qui rencontre un parachute va plus vite que l'autre robot et finit donc par le rattraper à un moment donné, d'où la collision. Gagné !

N'hésitez pas à nous signaler si la réponse n'est pas claire !