The while Statement - off by one errors

Consider the following example: There is a row of beepers up to a wall, the robot shares the same cell as the furthest beeper from the wall and is facing the wall (see below).

The robot must pick up all the beepers. So how should we approach this problem, it seems to require a loop. One idea is to have the robot keep moving forward until it encounters a wall and pick up beepers along the way.

public class OffByOneError
{
   public static void main(String [] args)
   {
      World field = new World();
      OneOuter out = new OneOuter();

      field.addWall(12, 4, 8, "north");

      field.add(out, 7, 6, "east");
      field.addBeeper(7, 6);
      field.addBeeper(8, 6);
      field.addBeeper(9, 6);
      field.addBeeper(10, 6);
      field.addBeeper(11, 6);

      out.go();
   }
}

public class OneOuter extends Robot
{
   void go()
   {
      while(frontIsClear())
      {
         move();
         pickBeeper();
      }
   }
}

Our first attempt is shown below: but it doesn't work; it misses the first beeper.

Note: some people might ask why test the condition frontIsClear() instead of the condition beeperPresent(). The reason is that we know we have finished when we reach the wall. Also there is no need to check for a beeper because we know that there is one beeper in every cell between the robot and the wall (we were told as part of the problem specification).

Rearrange the loop

Many programmers like to fiddle with a program in the hope that they will be able to make it work, so let's fiddle with this program: we'll change the order of the statements in the while loop

OuterOne.java public class OuterOne extends Robot { void go() { while(frontIsClear()) { // this time we pick up the beeper and then move pickBeeper(); move(); } } }

Unfortunately, this doesn't work (as is frequently the case when we fiddle with code). It does pick up the first beeper but doesn't pick up the last beeper.

In fact simple counting will reveal the problem. After four moves, the robot will have reached the wall, whereas there are five beepers. Therefore there should be one more pickBeeper() instruction than move() instruction. In the while loop however, the two instructions will each be executed the same number of times. A simple solution is to use the first loop and pick up a beeper before you enter the loop, or use the second loop and pick up the beeper at the end. I.e.

OneOuter.java

public class OneOuter extends Robot { void go() { // pick up the first beeper pickBeeper(); while(frontIsClear()) { move(); pickBeeper(); } } }

OneOuter.java

public class OneOuter extends Robot { void go() { while(frontIsClear()) { pickBeeper(); move(); } // pick up the last beeper pickBeeper(); } }

This off by one error occurs in many loops. You should be very careful to avoid 'off by one' errors in your loops.