GridPath is #4 from the from the 2024 AP Computer Science A Free Response problems.
https://apcentral.collegeboard.org/media/pdf/ap24-frq-comp-sci-a.pdf
Part (a) getNextLoc method
public Location getNextLoc(int row, int col)
{
Location belowLoc = new Location(row + 1, col);
Location rightLoc = new Location(row, col + 1);
if(row == grid.length - 1)
return rightLoc;
if(col == grid[0].length - 1)
return belowLoc;
if(grid[row + 1][col] < grid[row][col + 1])
return belowLoc;
else
return rightLoc;
}
This is a revised solution. My original getNextLoc solution contained a subtle error.
Part (b) sumPath method
public int sumPath(int row, int col)
{
int sum = grid[row][col];
Location loc = getNextLoc(row, col);
while(loc != null)
{
sum += grid[loc.getRow()][loc.getCol()];
if(loc.getRow() < grid.length - 1 ||
loc.getCol() < grid[0].length - 1)
loc = getNextLoc(loc.getRow(), loc.getCol());
else
loc = null;
}
return sum;
}
Java files with test code
FourTest.java includes JUnit 5 test code with the examples from the problem. See Running JUnit 5 tests. Location.java includes working equals, toString, and hashCode methods.
Location.java
GridPath.java
FourTest.java
2024 AP CS Exam Free Response Solutions
Help & comments
Get help from AP CS Tutor Brandon Horn
See an error? Question? Please comment below.
2024-05-13 comment
Ray Stuckey
What about doing part b recursively?
** spoilers below**
Something like this
public int sumPath(int row, int col) {
//part b
if (grid[0].length - 1 == col && grid.length - 1 == row) {
return grid[row][col];
}
Location next = getNextLoc(row, col);
return grid[row][col] + sumPath(next.getRow(), next.getCol());
}
Response
Yes. This works.
I didn’t post a recursive solution since I didn’t personally see it adding anything, but I could certainly see it being more intuitive for others.
2024-05-17 comment
Mike Crudele, APCS Teacher at Doral Academy
//my recursive solution:
public int sumPathRec(int row, int col) {
if (row == grid.length-1 && col == grid[0].length-1) {
return grid[row][col];
}
else {
Location loc = getNextLoc(row, col);
int nextRow = loc.getRow();
int nextCol = loc.getCol();
return grid[row][col] + sumPath(nextRow, nextCol);
}
}
Response
Yep. This works. Thanks for sharing.
2024-07-03 comment
Anonymous
Answer to part (a) uses a confusing mixed approach. Either you first define the below and right locations and then use getRow() and getCol() to access the grid, or you use the given row and col values and only create the location you need to return.
Answer to part (b) could start with a sum of zero and loc = new Location(row, col).
Response
Sure, for part (a) I could see:
public Location getNextLoc(int row, int col)
{
Location belowLoc = new Location(row + 1, col);
Location rightLoc = new Location(row, col + 1);
if(belowLoc.getRow() == grid.length)
return rightLoc;
if(rightLoc.getCol() == grid[0].length)
return belowLoc;
if(grid[belowLoc.getRow()][belowLoc.getCol()] <
grid[rightLoc.getRow()][rightLoc.getCol()])
return belowLoc;
else
return rightLoc;
}
It’s been a few months, but if I remember correctly, I used the variables to avoid the long condition. I agree the approach immediately above is clearer.
Yes, part (b) could start as you describe. My solution matches how I thought about the problem. There are also a few solutions floating around with the condition written pretty cleanly in its normal place (instead of the artificial use of null).
2024-07-05 comment
Email withheld
Comment edited for formatting
The 2 recursive implementations in the comments rely on providing the last cell location to sumPath (the base case in each solution). The preconditions clearly state the function is not called with this specific location (the following code taken from the problem statement):
/**
* Computes and returns the sum of all values on a path through grid, as described in
* part (b)
* Preconditions: row is a valid row index and col is a valid column index in grid.
* row and col do not specify the element in the last row and last column of grid.
*/
public int sumPath(int row, int col)
so to meet the preconditions the recursive solution could look like this:
public int sumPathRec(int row, int col) {
Location loc = getNextLoc(row, col);
int nextRow = loc.getRow();
int nextCol = loc.getCol();
if (nextRow == grid.length-1 && nextCol == grid[0].length-1) {
return grid[row][col] + grid[nextRow][nextCol];
}
else {
return grid[row][col] + sumPath(nextRow, nextCol);
}
}
Response
A precondition for a recursive method is often interpreted as applying to client code calling the method. Although it is certainly possible to write a recursive solution that adheres to its own precondition here, I don’t see that as a requirement.