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 17,500+ Swift developers and enthusiasts who get my weekly updates.

  • Hi Natasha,

    I think I found another solution using recursion.

    http://pastebin.com/WQJQvHt6

    -daniel

    • 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.

  • Lorin

    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

    • Thanks for posting Lorin! Always love hearing of new ways of solving these that I hadn’t though of πŸ™‚

  • Matt

    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();
    	}
    }
    
  • Krys

    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

  • Stephen

    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 < stepsToMoveToMiddle; j++){
    			move();
    		}
    		putBeeper();
    	}
    }
    
    • Haha, super clever and simple πŸ™‚ Love it!

    • Todd

      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.

      • Great point! The purpose of Karel the Robot is to get you thinking like a programmer πŸ™‚

    • RosaLinda C

      I agree with the math part although mine is a bit different

      import stanford.karel.*;

      public class MidpointFindingKarel extends SuperKarel {

      // You fill in this part

      public void run()
      {
      int count = 0;
      while(frontIsClear())
      {
      move();

      count++;

      }

      turnAround();

      count = count/2;

      for(int i = 0; i <= count; i++)
      {
      move();
      }
      turnAround();
      move();
      putBeeper();
      }

      }

  • Todd

    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();
    	}
    }
    
  • Mario

    This was a challenge to get started, once I scribbled out a solution on paper though the code all came together within minutes which was nice.

    public class MidpointFindingKarel extends SuperKarel {

    public void run(){

    //First place two beepers at opposite ends of the world
    putBeeper();
    placeLastBeeper();

    //Continually bring those beepers in one step at a time towards the center
    while(noBeepersPresent()){
    moveBeeper();
    }

    //Pickup the final beeper, leaving one in the centermost position
    pickBeeper();
    }

    //Walk towards and place a beeper in the final column, then turnaround.
    private void placeLastBeeper(){
    while(frontIsClear()){
    move();
    }
    putBeeper();
    turnAround();
    move();
    }

    //Pickup beeper, turn around, move one column towards center & drop beeper
    private void moveBeeper(){
    while(noBeepersPresent()){
    move();
    }

    pickBeeper();
    turnAround();
    move();
    putBeeper();
    move();
    }
    }

  • Hi,

    Now I’ve only just started CS106A so all this is old hat to you now. However, I just wanted to say that your words have inspired me to continue when I found it hard – even it this early stage. Especially when you mentioned some trial-and-error maybe needed, as first I thought this a sign of failure, but your having mentioned that you went through it on occasion kept me going. Finally getting these solutions right(ish) gives me a serious, and out-of-proportion sense of achievement πŸ™‚

    Now onto my solution. I thought there must be some relevance to the assignment mentioning the world being at least as high as wide so my solution (which as far as I know is unique approach here) was to place a diagonal line of beepers first, then come down and do another, opposing, diagonal to test for the overlap. It is at this point that the midpoint can be found. Then all that’s needed is Karel to drop to the bottom to place a marker beeper there and then clean-up the diagonal of beepers. Finally put Karel on the marker facing east as the post condition.

    If you have time please let me know what you think, it works for all qualifying worlds.

    Regards and thanks for your blog,

    Richard. (sorry if the formatting hasn’t worked, I tried to follow your advice).

    [ sourcecode language = “ruby”]

    /*

    * 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 {

    // You fill in this part

    public void run() {

    diagonalLeftToRight();

    downToBottom();

    checkRightToLeftDiagonalForBeepers();

    goDownAndLeaveMarker();

    goToBottomLeft();

    collectUsedBeepers();

    returnToBottomAndMoveToMarker();

    }

    //Create diagonal of beepers from bottom-left to top-right

    private void diagonalLeftToRight() {

    putBeeper();

    while (frontIsClear()) {

    move();

    turnLeft();

    move();

    putBeeper();

    turnRight();

    }

    }

    //Move Karel to bottom right. Post condition facing west

    private void downToBottom() {

    turnRight();

    while (frontIsClear()) {

    move();

    }

    turnRight();

    }

    //Check for intersecting beeper this should be halfway along row

    //Nested if is necessary as beeper is not checked otherwise when

    //even number of columns

    private void checkRightToLeftDiagonalForBeepers() {

    while (noBeepersPresent()) {

    move();

    if (noBeepersPresent()) {

    turnRight();

    move();

    turnLeft();

    }

    }

    }

    private void goDownAndLeaveMarker() {

    turnLeft();

    while (frontIsClear()) {

    move();

    }

    putBeeper();

    turnRight();

    }

    //Return to bottom left with facing east as post condition

    private void goToBottomLeft() {

    while (frontIsClear()) {

    move();

    }

    turnAround();

    }

    //Follow bottom-left to top-right diagonal picking-up beepers

    private void collectUsedBeepers() {

    pickBeeper();

    while (frontIsClear()) {

    move();

    turnLeft();

    move();

    pickBeeper();

    turnRight();

    }

    }

    //Down to bottom and move to marker, facing east as post condition

    private void returnToBottomAndMoveToMarker() {

    downToBottom();

    while (noBeepersPresent()) {

    move();

    }

    turnAround();

    }

    }

    [ /sourcecode ]

  • Guest

    It’s awesome how different people can come up with such different methods for solving the same problem. The solution that came naturally to me was to use trig. To have Karel move up once right once and so on until he hit the wall, and then travel twice down and once left on the way back down thereby arriving at the bottom in half the moves it would take to get back to the west side. This is predicated on the world being as tall as it is wide, but that was included in the presumptions. My code:

    
    import stanford.karel.*;
    
    public class MidpointFindingKarel extends SuperKarel {
    
        public void run() {
    
            travelNorthEast();
    
            travelSouthWest();
    
            putBeeper();
    
        }
    
        private void travelNorthEast() {
    
            while (frontIsClear()) {
    
                move();
    
                turnLeft();
    
                move();
    
                turnRight();
    
            }
    
        }
    
        private void travelSouthWest() {
    
            turnRight();
    
            while (frontIsClear()) {
    
                move();
    
                if (frontIsClear()) {
    
                    move();
    
                    turnRight();
    
                    move();
    
                    turnLeft();
    
                }
    
            }
    
        }
    
    }
    • sorry about the formatting. I see now I was supposed to put “sourcecode” not “code”. I tried to delete and repost, but it won’t let me delete it πŸ™

      • No worries, its actually different int the comments. I formatted it for you!

    • guest

      Wow this is simple and ingenious. Great!

    • Darren Stanley

      Nice idea, but,I dont think this would always work.
      because,
      “The world need not be square, but you may assume that it is at least as tall as it is wide.”

  • mazal bohbot berrie

    if anyone is still following..

    i took the lead to drop and pickup beepers across the row.. but i +1 @stephan for the counter method. we learned that, i’m sure! (? in the first week?). my method took a lot of graphical debugging, which shows up in my comment blocks.

    happy coding
    mazal

    [ sourcecode language = “java” ]
    /*
    * 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() {
    /*
    * pre-condition: |_| _ _ _ _
    * post condition: _ _ |x| _ _
    *
    */
    putBeeper();
    while (!frontIsBlocked()) { // drop beepers eastbound along 1st Street
    dropAndMove();
    }
    qualifyMid();
    }

    // METHODS //

    /*
    * dropAndMove:
    * pre-condition: |x| _ _ _ _
    * post condition: x x x x |x|
    *
    */
    private void dropAndMove() {
    clearToMove();
    putBeeper();
    }

    /*
    * qualifyMid:
    * pre-condition: x x x x |x| //
    * post-condition: x x x |x| _ // after first iteration
    *
    * pre-condition: _ |x| x x _ // start of second iteration
    * post-condition: _ _ |x| x _ // continues to pass method while two beepers in a row are detected.
    *
    * pre-condition: _ _ x |x| _ // …
    * post-condition: _ _ |x| _ _ // two beepers were detected at start of this iteration, so midpoint is false
    *
    * pre-condition: _ _ |x| _ _ // final interation, detect one beeper, begins sequence to put beeper and find home.
    * post-condition: _ _ |x| _ _ // final iteration for odd avenues grid; works w/ even grid as well, albeit w/ variance
    */
    // qualifyMid method detects two beepers in a row, midpoint is false, else midpoint is true
    // if midpoint is false, karel moves to end of beeper line and “counts” again
    private void qualifyMid() {
    if (beepersPresent()) {
    pickBeeper();
    }
    if (frontIsBlocked()) { // first pass, karel needs help to turning around
    turnAround();
    clearToMove();
    } else {
    clearToMove();
    }
    if (beepersPresent()) {
    moveLastBeeper();
    } else {
    turnAround();
    clearToMove();
    putBeeper(); // NO BEEPER AHEAD turn home/end.
    returnHome();
    }
    }

    /*
    * moveLastBeeper
    * pre-condition: x x x x |_|
    * post condition: _ |x| x x _ // and so forth.. until test for midpoint is true
    *
    */
    private void moveLastBeeper() {
    while (beepersPresent() && !frontIsBlocked()) {
    clearToMove();
    }
    turnAround();
    if (beepersPresent()) {
    pickBeeper();
    }
    clearToMove();
    qualifyMid();
    }

    /*
    * returnHome:
    * pre-condition: _ _ _ _ _
    * post condition: _ _ _ _ _
    *
    */
    private void returnHome() {
    if (notFacingWest()){
    turnAround();
    }
    while (!frontIsBlocked()) {
    clearToMove();
    }
    turnAround();
    }

    private void clearToMove() {
    if (!frontIsBlocked()) {
    move();
    }
    }

    /* end of class */
    }

    [ /sourcecode ]

  • Brady

    Well Im glad this code is up because I am having so much trouble doing this with SuperKarel commands. Yet sense I already know Java I attempted this using a simple counter variable and managed to succeed in 2 minutes.

  • guido

    Hello there, here is mine, similar to others actually , i find the one posted earlier really awsome(travelNorthEast();…etc) !! sorry formatting is bad…

    import stanford.karel.*;

    public class MidpointFindingKarel extends SuperKarel {

    public void run(){

    layBeepers();

    pickCornerBeepers();

    move();

    pickAllBeepers();

    putLastBeeper();

    }

    private void layBeepers(){

    while (frontIsClear()){

    putBeeper();

    move();

    }

    putBeeper();

    turnAround();

    }

    private void pickCornerBeepers(){

    while(frontIsClear()){

    move();

    if (frontIsBlocked()){

    pickBeeper();

    }

    }

    turnAround();

    while(frontIsClear()){

    move();

    if (frontIsBlocked()){

    pickBeeper();

    }

    }

    turnAround();

    }

    private void pickAllBeepers(){

    while(beepersPresent()){

    move();

    if(noBeepersPresent()){

    turnAround();

    move();

    pickBeeper();

    move();

    }

    }

    }

    private void putLastBeeper(){

    turnAround();

    move();

    putBeeper();

    }

    }

  • Dekaide

    import stanford.karel.*;

    public class MidpointFindingKarel extends SuperKarel {
    public void run() {

    //Filling first row with Beepers
    fillRow();

    //resetting Karel where he began
    turnAround();
    while (frontIsClear()) {
    move();
    }
    turnAround();

    //Stacking each piece on last corner
    pickBeeper();
    moveToWall();
    putBeeper();
    turnAround();
    move();
    while (beepersPresent()) {
    gimmeAnother();
    }
    // Reset Karel so he’s on top of the stack of Beepers facing West.
    turnAround();
    move();
    turnAround();

    /*Put twice as many Beepers down as you picked up. You will have exactly enough to get
    you halfway + 2 corners west */

    while (beepersPresent()) {
    pickBeeper();
    if (noBeepersPresent()) {
    putBeeper();
    }
    pickBeeper();
    move();
    moveToEndOfLine();
    putBeeper();
    putBeeper();
    turnAround();
    moveToWall();
    turnAround();
    }
    move();
    while (beepersPresent()) {
    pickBeeper();
    pickBeeper();
    move();
    }
    /*For some reason this program over shoots the midpoint by 2 on odd maps and 1 on
    * even maps. Fortunately I think the official rules allowed this bug.
    */
    turnAround();
    move();
    move();
    putBeeper();

    }
    private void fillRow() {
    putBeeper();
    while (frontIsClear()) {
    move();
    putBeeper();
    }
    }

    private void moveToWall() {
    while (frontIsClear())
    move();
    }

    private void gimmeAnother() {
    while (beepersPresent()) {
    move();
    }
    turnAround();
    move();
    pickBeeper();
    moveToWall();
    putBeeper();
    turnAround();
    move();
    }

    private void moveToEndOfLine() {
    while (beepersPresent()) {
    move();
    }
    }
    }

    • Dekaide

      Eek so sorry for the formatting. I haven’t seen anyone use this so I posted it quick like. Maybe people don’t come here ever but I think its cool that there’s a community who has went through this course. Anyway this “solution” (and I use that term loosely) took me about 20 minutes to think about and about 30 hours to find out how to code. A lot of band-aiding. I would like to hear some feedback because I’m only half sure I didn’t break any of the rules. PS If anyone can tell me how to repost legibly I will certainly do so.

  • Big Earl

    Working with my son on this — this was our solution:

    public class MidpointFindingKarel extends SuperKarel {

    public void run () {
    SetupKarel();
    while(beepersPresent()) {
    ZigZagKarel();
    }
    CleanUpKarel();
    }

    private void SetupKarel () {
    while (frontIsClear()) {
    move();
    putBeeper();
    }
    turnAround();
    pickBeeper();
    move();
    }

    private void ZigZagKarel () {
    while(beepersPresent()) {
    move();
    }
    turnAround();
    move();
    pickBeeper();
    move();
    }

    private void CleanUpKarel() {
    turnAround();
    move();
    turnAround();
    putBeeper();
    }
    }

  • guest

    that trig solution is awesome. my own was kinda funny/ridiculous. I made a diagonal line of beepers till I hit the top right corner, then I went to the top left corner and worked my way down the other diagonal until I hit a beeper, so I knew I was at the centre point.
    then I went to the south to leave the required beeper, cleared up the other beepers and then returned to the remaining beeper!

  • atay

    http://pastebin.com/9sTHNUsy

    first, fills the line with beepers, then picks up one from each end by turn.
    however let me add that, this algorithm is built to work even in a 1×1 row..

  • Nick Sophocleous

    Method – drop two beepers at the ends of the row and then bring them in one at a time – each time removing one marker and checking if there is still one there, if there is then centre has been found – if not replace removed beeper, goto the end and bring the other beeper in – rinse and repeat until centre has been found. works for rows with just one column and places centre just past centre on rows with an even number of columns.

    import stanford.karel.*;

    public class MidpointFindingKarel extends SuperKarel {

    public void run () {
    placeMarkers();
    pickBeeper();
    while (noBeepersPresent()){

    moveCentre();

    }
    pickBeeper();

    }

    private void placeMarkers(){
    putBeeper();
    while (frontIsClear()){
    move();
    }
    turnAround();
    putBeeper();
    }

    private void moveCentre(){
    move();
    putBeeper();
    while (frontIsClear()){
    move();
    }
    turnAround();
    while (noBeepersPresent()){
    move();
    }
    pickBeeper();
    if (noBeepersPresent()){
    move();

    }
    }

    }

  • Yijie Xu

    Your idea is great! I simplify the code using recursion, and it solve for even width 1 or 2 grid.

    /*

    * 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 () {

    putBeeper();

    while(frontIsClear()) {

    move();

    }

    turnAround();

    findMid();

    if(facingWest()) {

    turnAround();

    }

    }

    private void findMid() {

    if (noBeepersPresent()) {

    putBeeper();

    move();

    while(noBeepersPresent()) {

    if(frontIsClear()) {

    move();

    }

    }

    pickBeeper();

    turnAround();

    move();

    findMid();

    }

    }

    }

  • Stars

    Just want to say thank you for making this blog post! Even in 2015, it’s really helpful!

    • Leo Toydog

      I’m working at home. Here’s my answer. Had to change it some to allow for the possibility that the world might be only 3 blocks wide.
      –>

      /*

      * 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()

      {

      firsttoWall();

      firsttoWall();

      testForThree();

      while
      (noBeepersPresent())

      {

      placeMarker();

      }

      pickBeeper();

      turnAround();

      move();

      if (frontIsBlocked())

      {

      turnLeft();

      turnLeft();

      move();

      putBeeper();

      }

      }

      private void firsttoWall()

      {

      while
      (frontIsClear())

      {

      move();

      }

      if (frontIsBlocked())

      {

      turnAround();

      move();

      if (noBeepersPresent())

      putBeeper();

      }

      // You fill in this part

      }

      private void placeMarker()

      {

      while
      (noBeepersPresent())

      move();

      if (beepersPresent())

      pickBeeper();

      turnAround();

      move();

      putBeeper();

      move();

      }

      private void testForThree()

      {

      move();

      if (frontIsBlocked())

      { turnAround();

      move();

      }

      }

      }

  • Saul

    My solution, spiraling around the whole board πŸ™‚
    http://pastebin.com/f4iH48VR

    • Leo Toydog

      Wow Saul cool!!

  • Naomi Saltis

    public void run(){
    ….findMidPointByNaomiSaltis();
    ….putBeeper();
    }
    private void findMidPointByNaomiSaltis(){
    ….while(frontIsClear()){
    ……..move();
    ……..while(frontIsClear()){
    …………move();
    …………findMidPointByNaomiSaltis();
    …………move();
    ……..} else {
    …………turnAround();
    ……..}
    ….} else {
    ……..turnAround();
    ….}
    }

  • dgr
  • Fausto Davila Centanaro

    Hey! I’m a big fan of your blog ^_^ helps me see what exercises I can teach my students.

    Well this is how I tackled it:

    You aren’t supposed to use variables, so no math.

    No trig because the world can be a rectangle.

    I immediately came with a solution that I think you mention as the first way:

    /**

    * @author Fausto Davila Centanaro

    */

    import stanford.karel.*;

    public class MidpointFindingKarel extends SuperKarel {

    public void run(){

    move();

    fillRow();

    turnAround();

    move();

    findMiddlePoint();

    turnAround();

    move();

    putBeeper();

    }

    private void fillRow() {

    while(frontIsClear()){

    putBeeper();

    move();

    }

    }

    private void findMiddlePoint() {

    while(beepersPresent()){

    while(beepersPresent() && frontIsClear()){

    move();

    }

    turnAround();

    move();

    pickBeeper();

    move();

    }

    }

    }

  • Jason Wigle

    I had a slightly different solution. So for any others following after (as I am)… πŸ™‚

    In my solution I put down a row of beepers, and then began to move all the beepers inward, moving one edge in at a time, until there was one large stack left.

    [ code language = β€œcss” ]

    /*

    * 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() {

    MakeRowOfBeepers();

    CenterBeepers();

    ReduceBeeperStackToOne();

    }

    //puts down a row of beepers and moves to a wall.

    private void MakeRowOfBeepers() {

    while (noBeepersPresent()) {

    putBeeper();

    if (frontIsClear()) {

    move();

    } else {

    FindWall();

    }

    }

    }

    //this will pick up the beeper(s) on an edge and move them in one space.

    //It will then go to the other end of the row.

    private void CenterBeepers() {

    while (beepersPresent()) {

    MoveBeeperPileForward();

    FindWall();

    FindBeeperEdge();

    }

    }

    //moves to the beepers edge and turns around to face inward.

    private void FindBeeperEdge() {

    while (noBeepersPresent()) {

    if (frontIsClear()) {

    move();

    }

    }

    if (frontIsClear()) {

    move();

    }

    //This allows karel to recognize if it’s on the last stack or not. By always going one past to see if a beeper is there.

    if (beepersPresent()) {

    turnAround();

    move();

    turnAround();

    }

    }

    //This moves the stack of beepers Karel is standing on forward one space. Eventually ending on an empty square.

    private void MoveBeeperPileForward() {

    while (beepersPresent()) {

    pickBeeper();

    move();

    putBeeper();

    turnAround();

    move();

    turnAround();

    }

    }

    //Removes all beepers and places one. This is run at the end of the routine when there is only one stack of beepers.

    private void ReduceBeeperStackToOne() {

    FindWall();

    FindBeeperStack();

    RemoveAllBeepers();

    putBeeper();

    }

    //This will find the closest stack of beepers. This assumes Kerel is at a wall.

    private void FindBeeperStack() {

    while (noBeepersPresent()) {

    move();

    }

    }

    //Safely moves Karel to the closest wall and turns it around.

    private void FindWall() {

    while (frontIsClear()) {

    move();

    }

    turnAround();

    }

    //removes all beepers in a stack

    private void RemoveAllBeepers() {

    while (beepersPresent()) {

    pickBeeper();

    }

    }

    }

    [ /code ]