MidpointFindingKarel Solution

25 Oct

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?
Advertisements

14 Responses to “MidpointFindingKarel Solution”

  1. Daniel November 20, 2011 at 5:32 am #

    Hi Natasha,

    I think I found another solution using recursion.

    http://pastebin.com/WQJQvHt6

    -daniel

    • natasha the robot November 20, 2011 at 10:49 am #

      I am sure there are a ton of other solutions to this. The recursion one looks interesting, not sure how it works though, with calling the method you’re creating within the method. Definitely way less code than I have though.

  2. Lorin February 1, 2012 at 12:31 pm #

    Hi Natasha,
    Just started this course the other day. The StoneMasonKarel problem took me 3 days! Then the Checkerboard one day, then this MidPointKarel about 20 minutes! I was really surprised, believe me. But I thought of it as a “shuttle run” like I used to do in high school gym class.

    So I first placed two shuttle blocks (one at each end of the course), then proceeded to run the course, picking up the shuttle blocks (beeper(s)) and moving it/them closer to the center until they were next to each other. You then pick the one that’s the furthest along the direction you’re facing, pick it up, turn around, then move one space to sit on the last shuttle block.

    Here’s my code: http://pastebin.com/5ByEXL2M

    Yeah, sorry. Not many notes/comments. I’m kinda lazy that way…

    I’m sure you’ve left this far behind, but I only know how other people’s solutions help me so if someone is stuck and searches for this solution to Midpoint Finding Karel, maybe it’ll help them.

    Oh, I looked at the recursion solution that David posted above. WOW. Blew my mind. Really, really clever!

    ; )
    Lorin

    • Natasha Murashev February 1, 2012 at 1:03 pm #

      Thanks for posting Lorin! Always love hearing of new ways of solving these that I hadn’t though of 🙂

  3. Matt June 16, 2012 at 1:06 am #

    My solution, tested against worlds of any size, including 1×8, 8×1, 7×7 and 8×8.

    import stanford.karel.*;
    
    public class MidpointFindingKarel extends SuperKarel {
    
    	/* Algorithm:
    	 * Drop beepers along first row
    	 * Pick beepers up one at a time from each end working towards the middle
    	 * Ensure a beeper is on the middle or first middle for even length row
    	 */
    	
    	public void run() {
    		dropAllBeepers();
    		getFurthestBeeper();
    		putBeeper();
    	}
    
    	private void getFurthestBeeper() {
    		while(frontIsClear() && beepersPresent()) {
    			move();
    		}
    		if (noBeepersPresent()) {
    			turnAround();
    			move();
    			turnAround();
    		}
    		if (beepersPresent()) {
    			pickBeeper();
    			turnAround();
    			if (frontIsClear()) {
    				move();
    				getFurthestBeeper();				
    			}
    		}
    	}
    
    	private void dropAllBeepers() {
    		while (frontIsClear()) {
    			putBeeper();
    			if (frontIsClear()){
    				move();
    			}
    		}
    		putBeeper();
    	}
    }
    
  4. Krys July 14, 2012 at 12:03 am #

    Wow, I just started going through this course, and im glad i found this site. It’s good to know that this problem also took you a few hours to solve. I tried doing this on my own, and my solution ended up being pretty long. I guess I should have tried to do this in simpler way like you and the others did, but you know how sometimes your brain is just stuck on this one idea. Anyways, great site, and well, it may not be pretty, but here is how I solved this: http://pastebin.com/Jra0WYMq

  5. Stephen September 14, 2012 at 1:02 pm #

    Here is my solution. Just used some math instead of using beepers to find the middle.

    import stanford.karel.*;
    
    public class MidpointFindingKarel extends SuperKarel {
    
    	public void run() {
    		int i = 1;
    		int stepsToMoveToMiddle = 0;
    		while(frontIsClear()){
    			move();
    			i++;
    		}
    		stepsToMoveToMiddle = i / 2;
    		turnAround();
    		for (int j = 0; j &lt; stepsToMoveToMiddle; j++){
    			move();
    		}
    		putBeeper();
    	}
    }
    
    • Natasha Murashev September 16, 2012 at 7:41 am #

      Haha, super clever and simple 🙂 Love it!

    • Todd October 24, 2012 at 10:14 pm #

      I believe the Karel the Robot language does not include the use of variables. It will run correctly in Java, but is outside the scope of this “learner” programming language.

      In a real-world programming environment, I’d use something like Stephen’s method. But, for the CS106A class, we are more limited, for learning purposes.

      • Natasha Murashev October 25, 2012 at 8:51 am #

        Great point! The purpose of Karel the Robot is to get you thinking like a programmer 🙂

  6. Todd October 24, 2012 at 10:54 pm #

    Here is my solution. I put a beeper at each corner, stacked up the beepers, divided it into two stacks, then used the size of one of the stacks to mark my way to the midpoint.

    I find the shuttle-run and especially the recursion solutions to be quite clever, but harder to think through when designing and debugging. Also, I like having a “variable” to reference, and the beeper stacks basically function as variables.

    /*
     * 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() {
    
    		if (frontIsClear()) {
    		
    			fillAllCornersWithCountingBeepers();
    			consolidateCountingBeepers();
    			splitConsolidatedBeepers();
    			removeBeeperStack1();
    			moveBeeperStack2();
    			spreadBeeperStack2();
    			movePastEndOfBeepers();
    			putBeeper(); // this is the midpoint marker
    			removeSpreadBeepersFromStack2();
    
    		} else {
    		
    			putBeeper(); // special case of a world with width = 1
    
    		}
    	}
    	
    	private void fillAllCornersWithCountingBeepers() {
    		
    		// this method places a beeper on each corner of the bottom row of the world
    		
    		putBeeper();
    		while (frontIsClear()) {
    			move();
    			putBeeper();
    		}
    		returnToStart();
    	}
    	
    	private void returnToStart() {
    
    		turnAround();
    		while (frontIsClear()) {
    			move();
    		}
    		turnAround();
    	}
    
    	private void consolidateCountingBeepers() {
    		
    		// this method consolidates all the "counting" beepers
    		//   (meaning, the beepers placed initially on each corner)
    		// into a stack on the corner above the start
    		
    		while (frontIsClear()) {
    			moveCountingBeeperToStack();
    		}
    		moveCountingBeeperToStack();
    		returnToStart();
    	}
    
    	private void moveCountingBeeperToStack() {
    
    		pickBeeper();
    		returnToStart();
    		putBeeperAbove();
    		while (noBeepersPresent() &amp;&amp; frontIsClear()) {
    			move();
    		}
    	}
    
    	private void putBeeperAbove() {
    
    		turnLeft();
    		move();
    		putBeeper();
    		turnAround();
    		move();
    		turnLeft();
    	}
    	
    	private void splitConsolidatedBeepers() {
    		
    		// this method splits the "counting" beepers into two stacks
    		//
    		// if there is an odd number of beepers, stack #1 gets the extra
    
    		turnLeft();
    		move();
    		turnRight();
    
    		while (beepersPresent()) {
    			putBeeperInStack1();
    			if (beepersPresent()) {
    				putBeeperInStack2();
    			}
    		}
    
    		turnRight();
    		move();
    		turnLeft();
    	}
    	
    	private void putBeeperInStack1() {
    
    		pickBeeper();
    		turnRight();
    		move();
    		putBeeper();
    		turnAround();
    		move();
    		turnRight();
    	}
    	
    	private void putBeeperInStack2() {
    
    		pickBeeper();
    		move();
    		turnRight();
    		move();
    		putBeeper();
    		turnAround();
    		move();
    		turnLeft();
    		move();
    		turnAround();
    	}
    	
    	private void removeBeeperStack1() {
    		
    		while (beepersPresent()) {
    			pickBeeper();
    		}
    	}
    	
    	private void moveBeeperStack2() {
    
    		// we need beeper stack #2 off of the first row,
    		//  so it is moved to the second row
    		
    		move();
    		while (beepersPresent()) {
    			pickBeeper();
    			returnToStart();
    			putBeeperAbove();
    			move();
    		}
    		returnToStart();
    	}
    	
    	private void spreadBeeperStack2() {
    
    		// we will use the second stack to find the midpoint,
    		//   because we move to the midpoint starting at corner 1,
    		//   and when stack #1 is larger
    		//    (e.g for 9 corners, stack #1 = 5, stack #2 = 4)
    		//   we only want to move 4 times to reach the midpoint (corner 5)
    		//
    		// for an even number of corners, the midpoint can be offset
    		//   to the east or west, per the problem instructions
    		//    (e.g. 6 corners, each stack has 3, we move from 1, +3,
    		//     leaves us at corner 4)
    
    		turnLeft();
    		move();
    		while (beepersPresent()) {
    			pickBeeper();
    			turnAround();
    			move();
    			turnLeft();
    			movePastEndOfBeepers();
    			putBeeper();
    			returnToStart();
    			turnLeft();
    			move();
    		}
    		turnAround();
    		move();
    		turnLeft();
    	}
    	
    	private void movePastEndOfBeepers() {
    
    		while(beepersPresent()) {
    			move();
    		}
    	}
    	
    	private void removeSpreadBeepersFromStack2() {
    		
    		turnAround();
    		move();
    		while (frontIsClear()) {
    			pickBeeper();
    			move();
    		}
    		pickBeeper();
    		turnAround();
    	}
    }
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s