## Monday, August 15, 2011

### CS106A Programming Methodology Problem Solutions: Assignment 1

Assignment one has four problems, and to be honest none of them is hard. Still, it took me quite a long time to complete all of them, for there were such strict restrictions on the operators and programming structures that I could use. For instance, I wasn't even allowed to have variables, do-while loops, or the ! and && operators! As a result, some of the solutions weren't as neat as they could have been.

Anyway, here are my solutions to the problems:
Problem 1: Collect Newspaper Karel (CollectNewspaperKarel.java)

This problem is extremely simple. As shown in the image above, you basically have to write a program that will let Karel pick up the beeper and return to his orginial position. The world will always be the same, so there's no need to include any if structure at all. Just a straight-forward program that directly tells Karel what to do.
```import stanford.karel.*;

public class CollectNewspaperKarel extends SuperKarel {

public void run() {
moveToNewsPaper();
pickUpNewsPaper();
returnToStartingPoint();

}

//Karel picks up the newspaper
private void pickUpNewsPaper() {
pickBeeper();

}

//Karel returns to original position
private void returnToStartingPoint() {
turnAround();
for (int i=0; i<3; i++) {     move();   }      turnRight();   move();   turnRight();     }    //Karel exits the room and gets to the newspaper  private void moveToNewsPaper() {   turnRight();   move();   turnLeft();      for (int i=0; i<3; i++) {     move();   }     }  }  ```

Problem Two: Stone Mason Karel (StoneMasonKarel.java)

This problem is also very straight-forward. You basically have to create a program that will make Karel fill up the columns (i.e., 1,5,9,13...).
```import stanford.karel.*;

public class StoneMasonKarel extends SuperKarel {

public void run() {
repairCurrentColumn();
while (frontIsClear()){
repairNextColumn();
}
}

//Pre-condition: Karel is at the upper-end of a column, facing North
//Post-condition: Karel is at the lower-end of a column, facing east
public void backToOriginalPosition(){
turnAround();
while(frontIsClear()){
move();
}
turnLeft();
}

//Pre-condition: Karel is at the lower-end of a column that may needs to be repaired, facing east
//Post-condition: Karel is at the same position, and the entire column is repaired
public void repairCurrentColumn (){
turnLeft();

while (frontIsClear()){
if (noBeepersPresent()){
putBeeper();
}
move();
}
//This is to repair the last bit of the column
if (noBeepersPresent()){
putBeeper();
}

backToOriginalPosition();

}

/*Pre-condition: Karel is at the lower-end of a certain column that has already
been repaired, and there is an unrepaired column to the right
*Post-condition: Karel is has moved to and repaired the adjacent column that is
east of that certain column, and is at the lower-end of it
*/
public void repairNextColumn(){
goToNextColumn();
repairCurrentColumn();
}

//Pre-condition: Karel is facing east, at the bottom on a column, and there is another
//column to the right
//Post-condition: Karel has moved eastward, onto the next column
public void goToNextColumn(){
for (int i=0; i<4; i++){
move();
}
}
}

```

Problem 3: Checkerboard Karel (CheckerboardKarel.java)

For this problem, you have to create a checker pattern for any given world (even a 1*1 square). Took me a little while to figure out how to decompose this problem.
```import stanford.karel.*;

public class CheckerboardKarel extends SuperKarel {

public void run() {
finishRow();
while (frontIsClear()){ //If there's a next row, then finish that row
goToNextRow();
if (frontIsClear()){ //In case that the world is a one column-world
finishRow();
}

}

}

//Pre-condition: Karel is at a square where a beeper needs to be in place
//Post-condition: The whole row that the square is in is now completed.
public void finishRow(){
putBeeper();

//Put down a beeper every other step
while (frontIsClear()){
move();

//If structure in place to ensure that
//Karel doesn't run into a wall
if (frontIsClear()){
move();
putBeeper();
}
}
faceNorth();
}

//Pre-Condition: Karel is facing east or west
//Post-Condition: Karel is facing north
public void faceNorth (){
if (facingEast()){
turnLeft();
}
else{
if (facingWest()){
turnRight();
}
}
}

//pre-condition: Karel is facing north, with at least
//a wall beside it

//Post-Conidtion: Karel is facing east or west, with a wall
//right behind it

public void turn (){

//The following assignment
if (leftIsClear()){
turnLeft();
}else{
turnRight();
}
}

//Pre-condition: There is at least one row above the row that Karel is currently in
//Post-condition: Karel has moved onto the next row, to a space that needs a beeper
//                (Exception: when it is in a one-column world, he may move by two rows

//How this method works:
//Suppose Karel is at point K. If there is a beeper at point K, Karel will move to
//point X. Otherwise, it will move to point Y
//...........XY
//............K

public void goToNextRow(){
if (noBeepersPresent()){
move();
turn();
}
else{
move();
turn();

/*If this condition is not satisfied, it means that the world is only
one-column wide. In this case, Karel will move onto the next available row
(if there is one)*/
if (frontIsClear()) {
move();
}
else{
//Move onto the next row if there is one
faceNorth();
if (frontIsClear()) {
move();
}

}

}
}

}

```

Problem Four: Midpoint Finding Karel (MidpointFindingKarel.java)

The goal of this program is to be able to let Karel find and stop at the midpoint of any given width. The first time it took me more than 1.5 hours to finish all the coding, so I was beyond miserable when the whole file got accidentally deleted. Fortunately, the second time it only took me about 10 to 15 minutes.
```import stanford.karel.*;

public class MidpointFindingKarel extends SuperKarel {
//My algorithm is quite simple. running the program and reading the comment lines
//should be enough for you to understand

public void run() {
layBeepers(); //Put one beeper in each square in the row
cleanUpBeepers(); //Alternately remove one beeper from each end. This way Karel will
//be removing the beeper at the middle square last
putBeeper(); //Put one beeper back in the middle square

}

//Put one beeper in each square of the row
public void layBeepers(){
putBeeper();
while (frontIsClear()){
move();
putBeeper();
}
turnAround(); //Turn around so that Karel is facing the center
}

//Only move if front is clear
public void moveIfSafe(){
if(frontIsClear()){
move();
}
}

//Pre-condition: Karel is facing west or east
//Post-condition: Karel is facing south
public void turnSouth(){
if(facingEast()){
turnRight();
}else{
turnLeft();
}

}

//Turn around, move one space (if possible), and then pick up the beeper (if possible)
public void turnAroundAndPickBeeper(){
turnAround();
moveIfSafe();
if (beepersPresent()){
pickBeeper();
}
}

//The purpose of this method is basically to let Karel pick up a beeper from the opposite end
public void pickUpEndBeeper(){
while (beepersPresent()){//Karel keeps walking until there isn't a beeper at his
//location or until he reaches the wall
if (frontIsClear()){
move();
}
else{
pickBeeper();
turnSouth();//Turning south is a signal for "already picked up a beeper)
}
}

if (frontIsClear()){
turnAroundAndPickBeeper();//Turn around and pick up the beeper located at the end
}
else{
if (facingSouth()) //If Karel has already picked up a beeper, then he will
//simply change direction
{
faceCenter();
}
else{
turnAroundAndPickBeeper();//If not, he will pick up the beeper at the end
}

}

}

//Let Karel face the center
public void faceCenter(){
if (rightIsClear()){
turnRight();
}else{
turnLeft();
}

}

//Karel alternately picks up a beeper from each end. Eventually, Karely will stop at the
//middle square
public void cleanUpBeepers(){
while (notFacingSouth()){

pickUpEndBeeper();
moveIfSafe();
if (noBeepersPresent()){//If this is satisfied, it means that all beepers have been
//cleared
//Move back to the middle square:
turnAround();
moveIfSafe();
turnSouth();//Since no variable can be used, facing south is the only way
//to break out of the while loop
}
}

}
}
```