cs106a – Assignment #1 – Task #4

As an exercise in solving algorithmic problems, program Karel to place a single beeper at the center of 1st Street. For example, if Karel starts in the world

it should end with Karel standing on a beeper in the following position:

Note that the final configuration of the world should have only a single beeper at the midpoint of 1st Street. Along the way, Karel is allowed to place additional beepers wherever it wants to, but must pick them all up again before it finishes.
In solving this problem, you may count on the following facts about the world:

• Karel starts at 1st Avenue and 1st Street, facing east, with an infinite number of beepers in its bag.
• The initial state of the world includes no interior walls or beepers.
• The world need not be square, but you may assume that it is at least as tall as it is wide.

Your program, moreover, can assume the following simplifications:

• If the width of the world is odd, Karel must put the beeper in the center square. If the width is even, Karel may drop the beeper on either of the two center squares.
• It does not matter which direction Karel is facing at the end of the run.

There are many different algorithms you can use to solve this problem. The interesting part of this assignment is to come up with a strategy that works.

Move one row up and search the opposite wall (and mark it). Repeat as long as necessary. Then move down mark the mid point, and clean up the helper row:

	public void run() {
		moveUp();
		searchWall();
		while (beepersPresent()) {
			searchWall();
		}
		moveDown();
		putBeeper();
		cleanUp();
	}

Moving up and down, check which direction Karel is facing and act accordingly:

	private void moveUp() {
		if (facingEast()) {
			turnLeft();
			move();
			turnRight();			
		} else {
			turnRight();						
			move();
			turnLeft();
		}
	}

	private void moveDown() {
		if (facingEast()) {
			turnRight();
			move();
			turnLeft();			
		} else {
			turnLeft();
			move();
			turnRight();			
		}
	}

Searching the opposite wall, move as long as Karels front is clear or Karel reaches a beeper. Turn around, step forward. If there is already a beeper present, Karel has reached the midpoint. If not place a beeper.

	private void searchWall() {
		if (frontIsClear()) {
			move();
		}
		while(frontIsClear() && noBeepersPresent()) {
			move();
		}
		turnAround();
		if (frontIsClear()) {
			move();
			if (beepersPresent()) {
				pickBeeper(); // finished !!!
			} else {
				putBeeper();
			}			
		}
	}

To clean up, remove all beepers in one direction, turn around remove the rest. And head back for the midpoint:

	private void cleanUp() {
		moveUp();
		while (frontIsClear()) {
			move();
			if (beepersPresent()) pickBeeper();
		}
		turnAround();
		while (frontIsClear()) {
			move();
			if (beepersPresent()) pickBeeper();
		}
		moveDown();
		turnAround();
		while (frontIsClear() && noBeepersPresent()) {
			move();
		}
	}

The code for this assignment is available on github.