GridWorldUtilities and JumpingCritter free response answer 4

The GridWorldUtilities and JumpingCritter problem from the 2011 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.

http://media.collegeboard.com/digitalServices/pdf/ap/apcentral/ap13_frq_comp_sci.pdf

GridWorldUtilities Part (a): getEmptyLocations

    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 location specified is empty.

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

Part (b): JumpingCritter

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.

Get AP CS Help

2013 AP CS Exam Free Response Solutions

4 thoughts on “GridWorldUtilities and JumpingCritter free response answer

  1. Reply Ebube Chuba May 9,2013 4:15 pm

    I don’t totally agree with you on the selectMoveLocation method. In one of the examples the JumpingCritter ate a bug. The GridWorldUtilities.getEmptyLocations() method only gets empty locations. This excludes where bugs are. Also the makeMove() method should probably be updated to removeItselfFromGrid() if getLocation() is returned by the act() method.

    • Reply Brandon Horn May 9,2013 4:22 pm

      Adjacent bugs are eaten by the processActors method. By the time getMoveLocations is run, adjacent locations that previously contained bugs are empty. makeMove already removes the Critter from the grid if loc == null.

      The postcondition for makeMove is getLocation() == loc. makeMove should not remove the Critter from the grid if loc != null.

  2. Reply John Banworth May 18,2013 10:21 pm

    Is modifying the makeMove() method of the Critter class necessary in this situation or can it be left to the super-class to do? From what I see, if there isn’t an empty location, it just returns null which makeMove() handles appropriately.

Leave a Reply