GridPath free response answer 2024

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.

Comment on GridPath

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).