Sunday, February 28, 2010

Find2Largest Problem

Problem: Expand the problem from the preceding exercise "Find Largest" so that it finds both the largest and the second largest values in the list." (Robers ch 4, problem 13).

Basically, you start with two placeholder variables, "top" and "second." You set them initially to 0, but their values will change. As the user enters in new integers, you want a program that looks at each new input and says "If the input value is greater than the top, then replace the current top with the new input. If the input value is less than the current top AND greater than the current second, then reset second to equal the new input."

Renee's Code:
/*
* File: Find2ndLargest.java
* Name: Renee
* Section Leader:
* ------------------
This program uses three variables to find the two-largest values in an indefinite
list of integers entered by the user: "value", which is the variable given to the user
inputs, and "top" and "second," which are storage variables that start off at a value of 0. As the user
enters inputs, we compare the inputs to the current "top" and "second." Whenever the value
the user enters is greater or equal to the current "top," then we reassign the value
of "top" to the new input (but first we have to move the old "top" to "second" place).
This keeps going until the user enters the sentinel, when we end the inner loop and print the
reigning "top" and "second."
*/

import acm.program.*;

public class Find2ndLargest extends ConsoleProgram{
public void run () {
println ("This program finds the 2 largest of a list of integers.");
println("Enter integers, one per line, entering 0 to signify the end of the list.");

int top = 0;
int second = 0;

while (true){
int value = readInt("Enter integer: ");
if (value == SENTINEL) break;

if (value >= top) {
second = top;
top = value;
}else if (value >= second){
second = value;
}

}

println("The highest is " + top + ".");
println("The second highest is " + second + ".");
}
//private constants
private static final int SENTINEL = 0;


}

What it looks like:


Time it took: 35 min

What made it difficult: Not super-difficult this time. I did have a funny blooper. The first time I ran the code, I entered "7, 9, 6, 0" and got "The highest is 9. The second-highest is 6." What! The problem was, I had forgotten to state, "if you get a new 'top,' make the old 'top' equal to the 'second' and then make the new 'value' equal to the new 'top.'" Leaving out that line, then if your second-highest gets entered before your highest, you won't capture the second-highest.

This program also shows you the importance of "greater than" versus "greater than or equal to." At first I thought it was a wash whether I used ">=" or ">" as my operator, but running the program by hand with a couple test inputs clarified the difference.

Let's say the user enters "2, 2, 1, 0" as the inputs. What's the right answer? "The highest is 2. The second-highest is 1", right? However, if the operator is ">", which is wrong, here's how the program runs (going through it by hand):

Initial: top = 0, second = 0
1st loop: value = 2. The program thinks, "Is 2 greater than my current top, 0? Yes. Then top = 2, second = 0."
2nd loop: value = 2. The program thinks, "Is 2 greater than my current top, 2? NO! Well, is it greater than my current second, 0? Yes! Then reassign "second" to equal 2. top = 2, second = 2."
3rd: value = 1. The program thinks "1 is not greater than my current top or my current second, so keep the status as top = 2, second = 2."
4th: value = 0. Zero is the sentinel. Program stops, print "The highest is 2. The second-highest is 2."

This bug is solved by making the operator >=, because if the current top is 2 and the user enters 2, the program will replace the old 2 with the new 2, instead of moving it to the "second" variable.

Wednesday, February 24, 2010

FindLargest Problem

Problem: "Write a ConsoleProgram that reads in a list of integers, one per line, until the users a sentinel value of 0. When the sentinel is read, your program should display the largest value in the list" (Robers ch4, problem 12).

Renee's Code:

/*
* File: FindLargest.java
* Name: Renee
* Section Leader: Me! I did this one before breakfast, =D
* ------------------
We use two variables, "value" and "top", to solve this problem. "Top" is
declared at the beginning of the run method and arbitrarily gets assigned
-1. "Value" comes from the user's imput. Every time the user enters
Value comes the user's input. For every input, we check the input value against
the current "top," and if it's greater, we replace "top" with the "value."
Then once the user enters the sentinel, we print the current "top."
*/

import acm.program.*;

public class FindLargest extends ConsoleProgram{
public void run () {
println ("This program finds the largest of a list of integers.");
println("Enter integers, one per line, entering 0 to signify the end of the list.");

int top = -1;

while (true){
int value = readInt("Enter integer: ");
if (value == SENTINEL) break;

if (value >= top) top = value;

}

println("The highest is " + top + ".");

}
//private constants
private static final int SENTINEL = 0;


}
What it looks like:


How long it took: 25 min

Lingering Questions: I solved this by using two variables ("Top" and "Value") whose value changed, as the comment for the code describes. The question is: What are alternative approaches to solving this?

Friday, February 12, 2010

The Pyramid Saga Continues

Finally I draw my pyramid. Before I post the actual code, a second addition to the blooper reel. Have a look at the blooper code and tell me why we're getting a rhombus. And what the correction in the code should be:

Rhombus pyramid:



public class Pyramid extends GraphicsProgram {

public void run() {

//X and Y coordinates for the starting (bottom-left) brick:
double xstart = getWidth()/2 -(1/2)*(BRICK_WIDTH)*(BRICKS_IN_BASE);
double ystart = getHeight()/2 + (1/2)*(BRICK_HEIGHT)*(BRICKS_IN_BASE);

//Outer loop to make a new row. The pyramid has as many rows as bricks in base.
for(int i = 0; i < BRICKS_IN_BASE; i++) {

double BricksInRow = BRICKS_IN_BASE;

double x = xstart;
double y = ystart;

//Inner loop to place bricks in a row
for(int j = 0; j < BricksInRow; j++) {

GRect brick = new GRect (x, y, BRICK_WIDTH, BRICK_HEIGHT);
add(brick);

x += BRICK_WIDTH; //place next brick forward

}

BricksInRow -= 1; //Make the next row 1 brick shorter
ystart = ystart - BRICK_HEIGHT; //and one brick higher
xstart += BRICK_WIDTH / 2; //and start 1/2 a brick to the right


}
}

//Width of each brick in pixels
private static final int BRICK_WIDTH = 15;

//Width of each brick in pixels
private static final int BRICK_HEIGHT = 6;

//Number of bricks in the base of the pyramid
private static final int BRICKS_IN_BASE = 14;



(I once asked my friend Ryan, who took CS in college, what CS exams look like, since clearly it's difficult to write many entire programs during an exam. He said that there is lots of tracing and troubleshooting of code, so I imagine this must be what taking a little test in CS class is like :] )


Here is the actual pyramid:



Here is the code:


/*
* File: Pyramid.java
* Name:
* Section Leader:
* ------------------
* First, you have an outer loop that says, "Start the next row". It does this by,
* once you've made a row, removing one of the bricks from Bricks_In_Base so that
* the second row is one brick shorter, and by moving the starting brick up by
* 1 brick-height up and 1/2 brick-width to the right.
*
* Second, you have an inner loop that says "Make a row." It does this by
* placing down a brick in the starting location, then adding Brick_Width to
* the x coordinate and laying another brick at the new x-coordinate, repeated
* until you get to the end of the number of bricks in your row
* (or, until the index j gets to Bricks_In_Base.)
*
*/

import acm.graphics.*;
import acm.program.*;
import java.awt.*;

public class Pyramid extends GraphicsProgram {

public void run() {

//X and Y coordinates for the starting (bottom-left) brick:

double xstart = getWidth()/2 - (1/2)*(BRICK_WIDTH)*(BRICKS_IN_BASE);
double ystart = getHeight()/2 + (1/2)*(BRICK_HEIGHT)*(BRICKS_IN_BASE);

double BricksInRow = BRICKS_IN_BASE;

//Outer loop to make a new row. The pyramid has as many rows as bricks in base.
for(int i = 0; i < BRICKS_IN_BASE; i++) {

double x = xstart;
double y = ystart;

//Inner loop to place bricks in a row
for(int j = 0; j < BricksInRow; j++) {

GRect brick = new GRect (x, y, BRICK_WIDTH, BRICK_HEIGHT);
add(brick);

x += BRICK_WIDTH; //place next brick forward

}

BricksInRow -= 1; //Make the next row 1 brick shorter
ystart = ystart - BRICK_HEIGHT; //and one brick higher
xstart += BRICK_WIDTH / 2; //and start 1/2 a brick to the right


}
}

//Width of each brick in pixels
private static final int BRICK_WIDTH = 15;

//Width of each brick in pixels
private static final int BRICK_HEIGHT = 6;

//Number of bricks in the base of the pyramid
private static final int BRICKS_IN_BASE = 14;

}




What made it difficult: Algebra. The triangle has to be centered, and it should be flexible so that you can change the size of the bricks and the number of bricks in the pyramid. That means that the coorddinates of the starting brick have to vary depending on what the size constants are. If you have a look at the original coordinates for xstart and ystart (the x and y coordinates for the first brick of the bottom row), you'll see how much it depended on the constants.

The other thing that was tough for me is that I didn't figure out until much later that I should have two pairs of variables for the X and Y coordinates of the bricks. Arram tackled this problem in another language and did it with two pairs, and once I saw this I felt stupid for not having thought of that! You have xstart and ystart, which are the coordinates for the first brick of each row, and then x and y, the coordinates for every brick. (When you're making the first brick of the row in your inner loop, you set x =xstart, and then when you're ready to go up a row, you change xstart.) The whole time, I was in a tizzy trying to figure out how to go back to the left side of the pyyramid from the right once I've finished a row. So obvious now!

Lingering questions:

Well, the pyramid is supposed to be centered.

To make it centered, this is how I found the coordinates for the starting X: I found the center (using the getWidth method divided by 2) and then subtracted half the length of the pyramid. Same goes for the starting X, except for that I used the getHeight/d and added half the height of the pyramid.

However, if the pyramid is very big and needs the viewer to maximize the window, the pyramid is not centered and goes off the screen on one side. For example, this is what the screen looks like if I set the pyramid to be 200 bricks wide and tall:

Big pyramid:

I think that the bottom-left brick is actually in the CENTER of the view window! I thought I had written xstart and ystart so that the bottom brick would be appropriately off-center...What's going on?

Wednesday, February 10, 2010

Stuck Stuck Stuck like a Duck



/*
* File: Pyramid.java
* Name:
* Section Leader:
* ------------------
* First, you have an outer loop that says, "Start the next row". It does this by,
* once you've made a row, removing one of the bricks from Bricks_In_Base so that
* the second row is one brick shorter, and by moving the starting brick up by
* 1 brick-height up and 1/2 brick-width to the right.
*
* Second, you have an inner loop that says "Make a row." It does this by
* placing down a brick in the starting location, then adding Brick_Width to
* the x coordinate and laying another brick at the new x-coordinate, repeated
* until you get to the end of the number of bricks in your row
* (or, until the index j gets to Bricks_In_Base.)
*
*/

import acm.graphics.*;
import acm.program.*;
import java.awt.*;

public class Pyramid extends GraphicsProgram {

public void run() {

//X and Y coordinates for the starting (bottom-left) brick:
double xstart = getWidth()/2 -(1/2)*(BRICK_WIDTH)*(BRICKS_IN_BASE);
double ystart = getHeight()/2 + (1/2)*(BRICK_HEIGHT)*(BRICKS_IN_BASE);

double x = xstart;

double y = ystart;
double BricksInRow = BRICKS_IN_BASE;


//Outer loop to make a new row. The pyramid has as many rows as bricks in base.
for(int i = 0; i < BRICKS_IN_BASE; i++) {


//Inner loop to place bricks in a row
for(int j = 0; j < BricksInRow; j++) {

GRect brick = new GRect (x, y, BRICK_WIDTH, BRICK_HEIGHT);
add(brick);

x += BRICK_WIDTH; //place next brick forward

}

BricksInRow -= 1; //Make the next row 1 brick shorter
y = y - BRICK_HEIGHT; //and one brick higher
xstart += BRICK_WIDTH / 2; //and start 1/2 a brick to the right

}
}

//Width of each brick in pixels
private static final int BRICK_WIDTH = 30;

//Width of each brick in pixels
privat
e static final int BRICK_HEIGHT = 12;

//Number of bricks in the base of the pyramid
private static final int BRICKS_IN_BASE = 14;

}

If I built pyramids, all my mummies would have disintegrated long ago.