MidpointFindingKarel Solution

Wow! This one took me a few hours to figure out, and I even had to look for help to get me started. Things I learned in the process:

  1. Write down the solution in normal words before getting started with the code.
  2. Run the program often to make sure it matches your expectations
Here is the MidpointFindingKarel Problem:

Here is my solution:


Ok, as I mentioned. The key here was for me to write out what my plan was. From reading what some of the othershave done, I figured out at least 3 different solutions: 1. Drop All Beepers Intially

  • Karel drops beepers along the first row
  • Then Karel picks up the beepers one at time, first from the east end, then from the west, and so on until there are no more beepers (which means Karel is in the middle)
  • Karel puts the last Beeper in the middle of the first row
2. Drop Beepers One At A Time (the solution for this one is here)
  • Karel drops a beeper one at a time, first at the west end, then all the way at the east end, and so on until the first row is filled with beepers and Karel is in the middle
  • Karel picks up the beepers to the east of the middle
  • Karel picks up the beepers to the west of the middle
  • Karel comes back to the middle
3. Drop and Collect Beepers – this is the method I used, so the solution is at the bottom
  • Karel goes all the way to the east, drops a beeper. Karel goes to the west of the dropped beeper, drops a beeper right next to it, then goes back and picks up the beeper at the very end
  • Karel goes all the way to the west, drops a beeper. Karel goes to the eats of the dropped beeper, drops a beeper right next to it, then goes back and picks up the beeper at the very end
  • Repeat the top two steps until only the middle beeper remains
Here is my solution using the Drop and Collect Beepers method:
<pre>/*
 * File: MidpointFindingKarel.java
 * -------------------------------
 * When you finish writing it, the MidpointFindingKarel class should
 * leave a beeper on the corner closest to the center of 1st Street
 * (or either of the two central corners if 1st Street has an even
 * number of corners).  Karel can put down additional beepers as it
 * looks for the midpoint, but must pick them up again before it
 * stops.  The world may be of any size, but you are allowed to
 * assume that it is at least as tall as it is wide.
 */

import stanford.karel.*;

public class MidpointFindingKarel extends SuperKarel {
	public void run () {
		putEndBeepers();
		while (frontIsClear()) {
			takeLastBeeperWest();
			takeLastBeeperEast();
		}
	}
	private void putEndBeepers() {
		move();
		putBeeper();
		while (frontIsClear()) {
			move();
		}
		turnAround();
		move();
		putBeeper();
	}
	private void takeLastBeeperWest() {
		if (facingWest()) {
			move();
			if (noBeepersPresent()) {
				putBeeper();
			}
			turnAround();
			move();
			pickBeeper();
			turnAround();
			move();
			move();
		}
			detectBeeper();
			turnAround();
		}
	private void takeLastBeeperEast() {
		if (facingEast()) {
			pickBeeper();
			move();
			if(noBeepersPresent()) {
				putBeeper();
			}
			move();
			detectBeeper();
			turnAround();
		}
	}
	private void detectBeeper() {
		while (noBeepersPresent()) {
			if(frontIsClear()) {
					move();
				}
			if(frontIsBlocked()) {
				turnAround();
				while(frontIsClear()) {
					if(noBeepersPresent()) {
						move();
					}
				}
			}
		}
	}
}</pre>
Can you think of any other solutions to this problem?

Enjoy the article? Join over 20,000+ Swift developers and enthusiasts who get my weekly updates.