The Skyview problem from the 2013 AP Computer Science Exam is typical of free response problems that test 2 dimensional arrays.
SkyView is #4 from the from the 2013 AP Computer Science A Free Response problems.
http://media.collegeboard.com/digitalServices/pdf/ap/apcentral/ap13_frq_comp_sci.pdf
SkyView Part (a): constructor
public SkyView(int numRows, int numCols, double[] scanned)
{
view = new double[numRows][numCols];
int scannedIndex = 0;
for(int row = 0; row < numRows; row++)
{
for(int col = 0; col < numCols; col++)
{
if(row % 2 == 0)
view[row][col] = scanned[scannedIndex];
else
view[row][numCols - col - 1] = scanned[scannedIndex];
scannedIndex++;
}
}
}
Transferring elements from one array to another requires traversing both structures. SkyView traverses the 1D array (scanned) in conventional order from front to back. SkyView uses conventional nested loops to traverse the 2D array (view) as well.
Within each row of the 2D array, the position of the next element is determined based on whether row is even or odd. If row is even, the row is traversed in conventional order. If row is odd, the loop proceeds in conventional order but the elements are placed into the row from right to left.
SkyView Part (a): constructor – alternate solution
public SkyView(int numRows, int numCols, double[] scanned)
{
view = new double[numRows][numCols];
int scannedIndex = 0;
for(int row = 0; row < numRows; row++)
{
if( row % 2 == 0)
{
for(int col = 0; col < numCols; col++)
{
view[row][col] = scanned[scannedIndex];
scannedIndex++;
}
}
else
{
for(int col = numCols - 1; col >= 0; col--)
{
view[row][col] = scanned[scannedIndex];
scannedIndex++;
}
}
}
}
It is possible to reverse the order of the loop that traverses each row (the loop with col as the control variable). This is an alternative to calculating the position within the inner loop.
SkyView Part (b): getAverage
public double getAverage(int startRow, int endRow, int startCol, int endCol)
{
double sum = 0;
int count = 0;
for(int row = startRow; row <= endRow; row++)
{
for(int col = startCol; col <= endCol; col++)
{
sum += view[row][col];
count++;
}
}
return sum / count;
}
Conventional nested loops are used to traverse the 2D array. The bounds of each loop are the starting and ending indexes specified by the parameters.
As an alternative to maintaining count it is possible to compute the number of elements as (endRow – startRow + 1) * (endCol – startCol + 1).
2013 AP CS Exam Free Response Solutions |
Thanks so much for posting these free response. For the distributeCurrentPlayerTokens() to move to next index I did currentIndex+1%board.length. Would that work? Also I was in a hurry with gridWorld so for part a I had a triple nested for loop, the outer 2 loops were iterating to create a grid structure and the inner most loop would check weather or not the potential location created by the outer loops exists within grid.getOccupiedLocations(). If it didn’t then I would add the newly created location to the local ArrayList variable which I would return at the end. Thanks so much!
Sure. The conditional statement was the first thing that came to my mind. Since the question did not specify a minimum runtime efficiency, I can’t see how a getOccupiedLocations() check could be penalized.
Thanks for doing this. Will I get penalized if my updateDownloads(List titles) functions correctly but I did not use the getDownloadInfo(String title) method. Thank You!
Past scoring guidelines have specified penalties for writing a significant amount of code that could be replaced by a call to an accessible method. I’m not privy to the scoring guideline for this problem.
Thanks for your post. For Skyview, do you think I would get taken off if I added the values to the grid the regular way (using 2 for loops for row and column) and then inverted the element order on all the odd rows? The final 2D array was arranged as was asked for in the question.
If you inverted the values in the odd rows correctly and coherently I would not expect a deduction. The code to invert the values would be more complex than the code to place them in the correct order originally though.
These are awesome! When does the college board usually post full scoring guidelines?
No clue.
Is it okay for the token pass when it asks for random to use : Random rand = new Random(); and then say rand.nextInt(10) ?
Yes, as long as you add 1 to the result.
My much more concise answer:
public SkyView(int numRows, int numCols, double[] scanned){
view = new double[numRows][numCols];
for(int x=0; x<scanned.length; x++){
view[x/numCols][(numCols-1)-((Math.abs((x%(numCols*2))*2-(numCols*2-1))-1)/2)] = scanned[x];
}
}
Calculating the index in the 2D array is certainly possible. The code you’ve proposed is significantly more difficult to follow than my original solutions. On the AP CS Exam students should strive write code that is clear and easy to understand.
Mr. Horn, you are a life saver. Thank you for posting this and other free response problems!