The GridWorldUtilities and JumpingCritter problem from the 2013 AP Computer Science Exam is typical of free response problems that test GridWorld: The AP Computer Science Case Study. The problem requires you to loop through each location in a bounded grid. The problem also requires you to extend the Critter class, determine which methods to override, and implement the entire subclass.

GridWorldUtilities & JumpingCriter is #3 from the from the 2013 AP Computer Science A Free Response problems.

https://secure-media.collegeboard.org/digitalServices/pdf/ap/apcentral/ap13_frq_comp_sci.pdf

Part (a) getEmptyLocations method

public static ArrayList<Location> getEmptyLocations(Grid<Actor> grid)
{
    ArrayList<Location> emptyLocs = new ArrayList<Location>();

    for(int row = 0; row < grid.getNumRows(); row++)
    {
        for(int col = 0; col < grid.getNumCols(); col++)
        {
            Location loc = new Location(row, col);
            if(grid.isValid(loc) && grid.get(loc) == null) // validity check not strictly necessary
                emptyLocs.add(loc);
        }
    }

    return emptyLocs;
}

Since grid is bounded (as specified in the problem description), getEmptyLocations uses nested loops to visit each location. A Location object is required to determine whether the location is empty. The most direct way to determine whether a location in the grid is empty is the get method of Grid. get returns null if the specified location is empty.

Alternatively, it is possible to check ( ! grid.getOccupiedLocations().contains(loc) ) to determine whether loc is empty.

Part (b) JumpingCritter class

public class JumpingCritter extends Critter
{
    public ArrayList<Location> getMoveLocations()
    {
        return GridWorldUtilities.getEmptyLocations(getGrid());
    }

    public Location selectMoveLocation(ArrayList<Location> locs)
    {
        if(locs.size() == 0)
            return null;
        else
            return super.selectMoveLocation(locs);
    }
}

getMoveLocations is responsible for returning the list of possible locations to which the Critter might move. The JumpingCritter can move to any empty location in the grid. A list of empty locations in the grid can be obtained by calling getEmptyLocations from Part (a).

selectMoveLocation is responsible for selecting the location to which the Critter will move. If there are no empty locations in the grid the JumperCritter removes itself from the grid. The only way for a Critter to remove itself from the grid without violating a postcondition is to return null from selectMoveLocation. makeMove will then perform the removal. The selectMoveLocation method from Critter returns a random location from the non-empty list locs.

My Critter class explanation explains each method of Critter.

2013 AP CS Exam Free Response Solutions

Help & comments

Get help from AP CS Tutor Brandon Horn

Comment on GridWorldUtilities