Skyview Solution

Skyview might be my favorite of all the free response questions from the AP computer science exam going back to 2004. I think it hits a sweet spot on working with the topic list, in this case arrays, and giving a real world example of why you would code something.

In this problem, from the 2013 AP Computer Science exam, you’re given an array of double values that represent measurements from a telescope. You take these values and fill a matrix going back and forth rather than the normal row major or column major order that you’re probably used to working with.

For a little more on the “back and forth” part of this, let’s consider the an array with values 1.0 through 16.0, inclusive, in order.

[1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, 11.0, 12.0, 13.0, 14.0, 15.0, 16.0]

We’re going to fill in the matrix using these values, but go back and forth. Look at the matrix below. Notice how rows 0 and 2 go through the array values left to right but 1 and 3 go right to left? That’s what we’re talking about when we say back and forth.

If you’re a visual person, College Board has this problem available as a PDF on their website.

The Skyview Class

You’re given this class shell to start with.

public class SkyView {
    private double[][] view;

    public SkyView( int numRows, int numCols, double[] scanned ) {
	// Part A
    }

    public double getAverage( int startRow, int endRow, int startCol, int endCol ) {
        // Part B
    }
    
    // There may be instance variables, constructors, and methods that are not shown

}

Notice that we have an instance variable named view. That’s the matrix we’re going to be working with.

Part A

First part has you implementing the constructor to fill in view in the back and forth pattern described above. For most of my students this was the more difficult of the two parts.

There are two ways to do this. One with twin nested loops and one that’s a little more mathy. We’ll look at the twin loops version first since that’s the one that seems more inline with what a first year programmer would do.

public SkyView( int numRows, int numCols, double[] scanned ) {
    int idx = 0;
    view = new double[numRows][numCols];
    for (int r=0; r<numRows; r++) {
        if (r % 2 == 0) {
            for (int c=0; c<numCols; c++) {
                view[r][c] = scanned[idx];
                idx++;
            }
        }
        else {
            for (int c=numCols - 1; c>=0; c--) {
                view[r][c] = scanned[idx];
                idx++;
            }
        }
    }
}

First thing is to create the variables. We need one to keep track of where we are in scanned and also have to instantiate view to the correct size.

Next, we loop through each row. Then, depending on whether r is odd or even the code loops from the right or left. Even rows go left to right and odd rows go right to left.

Inside the inner loops we take a value from scanned and increment idx so that the next value pulled is from the next spot.

If I was actually writing this I would have used view[r][c] = scanned[idx++]; instead of spreading it out over two lines. But the side effects of incrementing a variable are not part of the AP Java subset so I separated them out here.

The Mathy Solution

This has all the same part, except for multiple inner loops. Instead of going forward and backwards through the row, this time it does some math to figure out the right position.

public SkyView(int numRows, int numCols, double[] scanned)     {
	int idx = 0;
	view = new double[numRows][numCols];        
	
	for(int r = 0; r < numRows; r++) {
		for(int c = 0; c < numCols; c++) {
			if(r % 2 == 0) {
				view[r][c] = scanned[idx];
			}
			else {
				view[r][numCols - c - 1] = scanned[idx];
			}
			idx++;
		}
	}
}

It works the same way, but seems like a solution that most first year programming students wouldn’t come up with under the pressure of a timed exam.

Part B

Now that we have a matrix filled with values, we need to do something with it. Part B has you implementing a method that calculates the average of a given subsection of the view matrix.

public double getAverage( int startRow, int endRow, int startCol, int endCol ) {
    double sum = 0.0;
    int cnt = 0;
    for (int r=startRow; r<=endRow; r++) {
        for (int c=startCol; c<=endCol; c++) {
            sum += view[r][c];
            cnt++;
        }
    }
    return sum / cnt; 
}

Here we need both a sum and a count variable to keep track of the running sum and also how many we found.

Next the code loops through and adds each position to sum and keeps track of how many it’s looked at with the cnt variable.

At the end the average is returned by dividing the sum by the count.

Snags

A couple of common snags on this one.

First, I’ve had many students that used int values for both the sum and the count. While it would run, Java would cast the double values from the matrix as int values when they’re added to sum and you’d wind up with the wrong values.

And more commonly students don’t loop enough. When we’ve done this in class most students use r<endRow and c<endCol instead of r<=endRow and c<=endCol and end up not pulling out enough of the values.

Leave a Reply

Your email address will not be published. Required fields are marked *