Robots on an infinite number line.

[BMAD]

Two robots are parachuted onto a spot of a discrete number line that stretches infinitely in either direction. They are an unknown distance apart. Where they land, they drop their parachute. They begin executing the same set of instructions at the same time. Unfortunately, these are not very good robots, and they only understand commands in character form. There is only room for 10 instructions.

Possible instructions are as follows:

L: Move left one space

R: Move right one space

S: Skip the next instruction if and only if there is a parachute at my feet

0-9: Move to this position in the instructions (If the instructions are LRS1, the 1 would move the robot back to the 'R')

Every step takes the same amount of time to execute, including parachute skips and moving through the instructions. There is no variable storage. The robots begin executing from step 0. What set of instructions will result in the two robots ultimately finding each other on the infinite number line in every case? There are multiple possible answers.

[Rainman]

LS0L3. The first loop is "left, check if I should skip, move to 0", resulting in one move left per three instructions. The leftmost robot will never have a parachute at its feet when checking for a skip, so it will forever keep moving left at an average speed of 1/3 move per instruction. The rightmost robot will eventually find its partner's parachute, skipping the return to 0, and going into the second loop: "left, move to 3", which results in moving left at 1/2 move per instruction on average. Eventually the rightmost robot will catch up, since it is moving left faster.

[Pickett]

Basically we need to come up with an algorithm that will allow one robot to eventually "overtake" the other robot after some point. Since we know one parachute is always going to be "left" of the other parachute on the number line, we can basically have the robots start moving left together. When the "right" robot gets to the left parachute, he needs to start moving left faster than the left robot. This set of instructions should accomplish this:

LRLS0L5

I have actually implemented this and tested it in Java. They always end up meeting up:

public class DumbRobots {
   private static int MAX_NUMBER = 10000000;
   
   private static int robot1Pos = (int) (Math.random() * MAX_NUMBER);
   private static int robot2Pos = (int) (Math.random() * MAX_NUMBER);
   private static final int ROBOT_1_CHUTE_LOC = robot1Pos;
   private static final int ROBOT_2_CHUTE_LOC = robot2Pos;
   private static int robot1CurrInst = 0;
   private static int robot2CurrInst = 0;
   
   private static char[] instructions = {'L', 'R', 'L', 'S', '0', 'L', '5'};

   public static void main(String[] args) {
      System.out.println("Starting with robot1 at " + robot1Pos + " and robot2 at " + robot2Pos);
      int numIterations = 0;
      while (robot1Pos != robot2Pos) {
         numIterations++;
         runInstruction(true, instructions[robot1CurrInst]);
         runInstruction(false, instructions[robot2CurrInst]);
      }
      System.out.println("ROBOTS FINALLY MET AT " + robot1Pos + " AFTER " + numIterations + " INSTRUCTIONS CALLED!!");
   }
   
   private static void runInstruction(boolean robot1, char inst) {
      switch(inst) {
         case 'L':
            moveLeft(robot1);
            break;
         case 'R':
            moveRight(robot1);
            break;
         case 'S':
            skipIfAtParachute(robot1);
            break;
         default:
            goToInstructionX(robot1, Integer.parseInt("" + inst));
            break;
      }
   }
   
   private static void moveLeft(boolean robot1) {
      if (robot1) {
         robot1Pos--;
         robot1CurrInst++;
      } else {
         robot2Pos--;
         robot2CurrInst++;
      }
   }
   
   private static void moveRight(boolean robot1) {
      if (robot1) {
         robot1Pos++;
         robot1CurrInst++;
      } else {
         robot2Pos++;
         robot2CurrInst++;
      }
   }
   
   private static void skipIfAtParachute(boolean robot1) {
      if (robot1) {
         if (robot1Pos == ROBOT_1_CHUTE_LOC || robot1Pos == ROBOT_2_CHUTE_LOC) {
            robot1CurrInst += 2;
         } else {
            robot1CurrInst++;
         }
      } else {
         if (robot2Pos == ROBOT_1_CHUTE_LOC || robot2Pos == ROBOT_2_CHUTE_LOC) {
            robot2CurrInst += 2;
         } else {
            robot2CurrInst++;
         }
      }
   }
   
   private static void goToInstructionX(boolean robot1, int inst) {
      if (robot1) {
         robot1CurrInst = inst;
      } else {
         robot2CurrInst = inst;
      }
   }
}
 

EDIT: I also ran my code on Rainman's algorithm above...it appears to also always work. Nice job!

Edited November 20, 2013 by Pickett