8.4.11. Free Response - Grid World A

The following is a free response question from 2013. It was question 3 part A on the exam. You can see all the free response questions from past exams at https://apstudents.collegeboard.org/courses/ap-computer-science-a/free-response-questions-by-year.

This question involves reasoning about the GridWorld case study that was formerly required knowledge for the APCSA exam. It is no longer expected that you know this information and it will be provided to you in this question. Because there is a lot of extra material that you need to read and understand, this question may seem more challenging and will require more time than a typical FRQ you would expect on your AP exam. It is still good practice nonetheless. In part (a) you will write a method to return an Arraylist of all empty Location objects in a given grid. The GridWorldUtilities class contains static methods. A partial declaration of the GridWorldUtilities class is shown below.

../_images/2013gridA1.png

In this question, you will write the GridWorldUtilities method getEmptyLocations. If there are no empty locations in grid, the method returns an empty Arraylist. Otherwise, it returns an Arraylist of all empty locations in grid. Each empty location should appear exactly once in the Arraylist.

8.4.11.1. Necessary Preliminary Information

The GridWorld case study provided a graphical environment where visual objects inhabited and interacted in a two-dimensional grid (similar to GreenFoot). In this case study, students designed and created Actor objects, added them to Grid objects, and determined whether the Actor objects behaved according to their specifications. Since this case study is no longer in the AP Java curriculum, all the necessary documentation is provided below.

The first necessary class is the Location class. Every actor that appears in the Grid has a Location. The Location class encapsulates the coordinates for an Actor object’s position in a Grid.

../_images/2013locDoc.png

The next important part is the Grid Interface. You may be unfamiliar with interfaces so don’t worry too much about how they work. What you need to know is that the interface Grid<E> specifies the methods for any grid that contains objects of the type E which you choose at its initialization. For part A we will be working with the class BoundedGrid<E> which implements the Grid Interface. For this question, “E” will be a “Location”

../_images/2013gridDoc.png

8.4.11.2. Check your understanding of the question

The problems in this section are to help you check your understanding and guide you towards a solution. You can skip these if you think you know what to do already. Click the buttons to reveal the problems if you want to do them.

8.4.11.3. How to Solve Part A

Here is the question again.

Write the GridWorldUtilities method getEmptyLocations. If there are no empty locations in grid, the method returns an empty Arraylist. Otherwise, it returns an Arraylist of all empty locations in grid. Each empty location should appear exactly once in the Arraylist.

7-4-11-6: Explain in plain English what your code will have to do to answer this question. Use the variable names given above.

This section contains a plain English explanation of one way to solve this problem as well as problems that test your understanding of how to write the code to do those things. Click on the buttons to reveal the questions.

8.4.11.4. Write the Code

In this question, you will write the GridWorldUtilities method getEmptyLocations. If there are no empty locations in grid, the method returns an empty Arraylist. Otherwise, it returns an Arraylist of all empty locations in grid. Each empty location should appear exactly once in the Arraylist.

Write the method getEmptyLocations in the code below.

Complete the getEmptyLocations() method below.

Data file: GridWorld.jar
import java.util.ArrayList;

/**
 * Grid provides an interface for a two-dimensional, grid-like
 * environment containing arbitrary objects.
 */
public interface Grid
{
    /**
     * Returns the number of rows in this grid.
     * @return the number of rows, or -1 if this grid is unbounded
     */
    int getNumRows();

    /**
     * Returns the number of columns in this grid.
     * @return the number of columns, or -1 if this grid is unbounded
     */
    int getNumCols();

    /**
     * Checks whether a location is valid in this grid.
     * Precondition: loc is not null
     * @param loc the location to check
     * @return true if loc is valid in this grid,
     * false otherwise
     */
    boolean isValid(Location loc);

    /**
     * Puts an object at a given location in this grid.
     * Precondition: (1) loc is valid in this grid (2)
     * obj is not null
     * @param loc the location at which to put the object
     * @param obj the new object to be added
     * @return the object previously at loc (or null
     * if the location was previously unoccupied)
     */
    E put(Location loc, E obj);

    /**
     * Removes the object at a given location from this grid.
     * Precondition: loc is valid in this grid
     * @param loc the location of the object that is to be removed
     * @return the object that was removed (or null if the location
     *  is unoccupied)
     */
    E remove(Location loc);

    /**
     * Returns the object at a given location in this grid.
     * Precondition: loc is valid in this grid
     * @param loc a location in this grid
     * @return the object at location loc (or null
     *  if the location is unoccupied)
     */
    E get(Location loc);

    /**
     * Gets the locations in this grid that contain objects.
     * @return an array list of all occupied locations in this grid
     */
    ArrayList getOccupiedLocations();

    /**
     * Gets the valid locations adjacent to a given location in all eight
     * compass directions (north, northeast, east, southeast, south, southwest,
     * west, and northwest).
     * Precondition: loc is valid in this grid
     * @param loc a location in this grid
     * @return an array list of the valid locations adjacent to loc
     * in this grid
     */
    ArrayList getValidAdjacentLocations(Location loc);

    /**
     * Gets the valid empty locations adjacent to a given location in all eight
     * compass directions (north, northeast, east, southeast, south, southwest,
     * west, and northwest).
     * Precondition: loc is valid in this grid
     * @param loc a location in this grid
     * @return an array list of the valid empty locations adjacent to
     * loc in this grid
     */
    ArrayList getEmptyAdjacentLocations(Location loc);

    /**
     * Gets the valid occupied locations adjacent to a given location in all
     * eight compass directions (north, northeast, east, southeast, south,
     * southwest, west, and northwest).
     * Precondition: loc is valid in this grid
     * @param loc a location in this grid
     * @return an array list of the valid occupied locations adjacent to
     * loc in this grid
     */
    ArrayList getOccupiedAdjacentLocations(Location loc);

    /**
     * Gets the neighboring occupants in all eight compass directions (north,
     * northeast, east, southeast, south, southwest, west, and northwest).
     *
     * Precondition: loc is valid in this grid
     * @param loc a location in this grid
     * @return returns an array list of the objects in the occupied locations
     * adjacent to loc in this grid
     */
    ArrayList getNeighbors(Location loc);
}
 // End of Class Grid

// Location Class

/**
 * A Location object represents the row and column of a location
 * in a two-dimensional grid.
 * The API of this class is testable on the AP CSA and AB exams.
 */
public class Location implements Comparable
{
    private int row; // row location in grid
    private int col; // column location in grid

    /**
     * The turn angle for turning 90 degrees to the left.
     */
    public static final int LEFT = -90;
    /**
     * The turn angle for turning 90 degrees to the right.
     */
    public static final int RIGHT = 90;
    /**
     * The turn angle for turning 45 degrees to the left.
     */
    public static final int HALF_LEFT = -45;
    /**
     * The turn angle for turning 45 degrees to the right.
     */
    public static final int HALF_RIGHT = 45;
    /**
     * The turn angle for turning a full circle.
     */
    public static final int FULL_CIRCLE = 360;
    /**
     * The turn angle for turning a half circle.
     */
    public static final int HALF_CIRCLE = 180;
    /**
     * The turn angle for making no turn.
     */
    public static final int AHEAD = 0;

    /**
     * The compass direction for north.
     */
    public static final int NORTH = 0;
    /**
     * The compass direction for northeast.
     */
    public static final int NORTHEAST = 45;
    /**
     * The compass direction for east.
     */
    public static final int EAST = 90;
    /**
     * The compass direction for southeast.
     */
    public static final int SOUTHEAST = 135;
    /**
     * The compass direction for south.
     */
    public static final int SOUTH = 180;
    /**
     * The compass direction for southwest.
     */
    public static final int SOUTHWEST = 225;
    /**
     * The compass direction for west.
     */
    public static final int WEST = 270;
    /**
     * The compass direction for northwest.
     */
    public static final int NORTHWEST = 315;

    /**
     * Constructs a location with given row and column coordinates.
     * @param r the row
     * @param c the column
     */
    public Location(int r, int c)
    {
        row = r;
        col = c;
    }

    /**
     * Gets the row coordinate.
     * @return the row of this location
     */
    public int getRow()
    {
        return row;
    }

    /**
     * Gets the column coordinate.
     * @return the column of this location
     */
    public int getCol()
    {
        return col;
    }

    /**
     * Gets the adjacent location in any one of the eight compass directions.
     * @param direction the direction in which to find a neighbor location
     * @return the adjacent location in the direction that is closest to
     * direction
     */
    public Location getAdjacentLocation(int direction)
    {
        // reduce mod 360 and round to closest multiple of 45
        int adjustedDirection = (direction + HALF_RIGHT / 2) % FULL_CIRCLE;
        if (adjustedDirection < 0)
            adjustedDirection += FULL_CIRCLE;

        adjustedDirection = (adjustedDirection / HALF_RIGHT) * HALF_RIGHT;
        int dc = 0;
        int dr = 0;
        if (adjustedDirection == EAST)
            dc = 1;
        else if (adjustedDirection == SOUTHEAST)
        {
            dc = 1;
            dr = 1;
        }
        else if (adjustedDirection == SOUTH)
            dr = 1;
        else if (adjustedDirection == SOUTHWEST)
        {
            dc = -1;
            dr = 1;
        }
        else if (adjustedDirection == WEST)
            dc = -1;
        else if (adjustedDirection == NORTHWEST)
        {
            dc = -1;
            dr = -1;
        }
        else if (adjustedDirection == NORTH)
            dr = -1;
        else if (adjustedDirection == NORTHEAST)
        {
            dc = 1;
            dr = -1;
        }
        return new Location(getRow() + dr, getCol() + dc);
    }

    /**
     * Returns the direction from this location toward another location. The
     * direction is rounded to the nearest compass direction.
     * @param target a location that is different from this location
     * @return the closest compass direction from this location toward
     * target
     */
    public int getDirectionToward(Location target)
    {
        int dx = target.getCol() - getCol();
        int dy = target.getRow() - getRow();
        // y axis points opposite to mathematical orientation
        int angle = (int) Math.toDegrees(Math.atan2(-dy, dx));

        // mathematical angle is counterclockwise from x-axis,
        // compass angle is clockwise from y-axis
        int compassAngle = RIGHT - angle;
        // prepare for truncating division by 45 degrees
        compassAngle += HALF_RIGHT / 2;
        // wrap negative angles
        if (compassAngle < 0)
            compassAngle += FULL_CIRCLE;
        // round to nearest multiple of 45
        return (compassAngle / HALF_RIGHT) * HALF_RIGHT;
    }

    /**
     * Indicates whether some other Location object is "equal to"
     * this one.
     * @param other the other location to test
     * @return true if other is a
     * Location with the same row and column as this location;
     * false otherwise
     */
    public boolean equals(Object other)
    {
        if (!(other instanceof Location))
            return false;

        Location otherLoc = (Location) other;
        return getRow() == otherLoc.getRow() && getCol() == otherLoc.getCol();
    }

    /**
     * Generates a hash code.
     * @return a hash code for this location
     */
    public int hashCode()
    {
        return getRow() * 3737 + getCol();
    }

    /**
     * Compares this location to other for ordering. Returns a
     * negative integer, zero, or a positive integer as this location is less
     * than, equal to, or greater than other. Locations are
     * ordered in row-major order.
     * (Precondition: other is a Location object.)
     * @param other the other location to test
     * @return a negative integer if this location is less than
     * other, zero if the two locations are equal, or a positive
     * integer if this location is greater than other
     */
    public int compareTo(Object other)
    {
        Location otherLoc = (Location) other;
        if (getRow() < otherLoc.getRow())
            return -1;
        if (getRow() > otherLoc.getRow())
            return 1;
        if (getCol() < otherLoc.getCol())
            return -1;
        if (getCol() > otherLoc.getCol())
            return 1;
        return 0;
    }

    /**
     * Creates a string that describes this location.
     * @return a string with the row and column of this location, in the format
     * (row, col)
     */
    public String toString()
    {
        return "(" + getRow() + ", " + getCol() + ")";
    }
}

// End of Class

// BoundedGrid Class

import java.util.ArrayList;

/**
 * A BoundedGrid is a rectangular grid with a finite number of
 * rows and columns.
 * The implementation of this class is testable on the AP CS AB exam.
 */
public class BoundedGrid extends AbstractGrid
{
    private Object[][] occupantArray; // the array storing the grid elements

    /**
     * Constructs an empty bounded grid with the given dimensions.
     * (Precondition: rows > 0 and cols > 0.)
     * @param rows number of rows in BoundedGrid
     * @param cols number of columns in BoundedGrid
     */
    public BoundedGrid(int rows, int cols)
    {
        if (rows <= 0)
            throw new IllegalArgumentException("rows <= 0");
        if (cols <= 0)
            throw new IllegalArgumentException("cols <= 0");
        occupantArray = new Object[rows][cols];
    }

    public int getNumRows()
    {
        return occupantArray.length;
    }

    public int getNumCols()
    {
        // Note: according to the constructor precondition, numRows() > 0, so
        // theGrid[0] is non-null.
        return occupantArray[0].length;
    }

    public boolean isValid(Location loc)
    {
        return 0 <= loc.getRow() && loc.getRow() < getNumRows()
                && 0 <= loc.getCol() && loc.getCol() < getNumCols();
    }

    public ArrayList getOccupiedLocations()
    {
        ArrayList theLocations = new ArrayList();

        // Look at all grid locations.
        for (int r = 0; r < getNumRows(); r++)
        {
            for (int c = 0; c < getNumCols(); c++)
            {
                // If there's an object at this location, put it in the array.
                Location loc = new Location(r, c);
                if (get(loc) != null)
                    theLocations.add(loc);
            }
        }

        return theLocations;
    }

    @SuppressWarnings("unchecked")
    public E get(Location loc)
    {
        if (!isValid(loc))
            throw new IllegalArgumentException("Location " + loc
                    + " is not valid");
        return (E) occupantArray[loc.getRow()][loc.getCol()]; // unavoidable warning
    }

    public E put(Location loc, E obj)
    {
        if (!isValid(loc))
            throw new IllegalArgumentException("Location " + loc
                    + " is not valid");
        if (obj == null)
            throw new NullPointerException("obj == null");

        // Add the object to the grid.
        E oldOccupant = get(loc);
        occupantArray[loc.getRow()][loc.getCol()] = obj;
        return oldOccupant;
    }

    public E remove(Location loc)
    {
        if (!isValid(loc))
            throw new IllegalArgumentException("Location " + loc
                    + " is not valid");

        // Remove the object from the grid.
        E r = get(loc);
        occupantArray[loc.getRow()][loc.getCol()] = null;
        return r;
    }
}

// End of Class

// Class AbstractGrid

import java.util.ArrayList;

/**
 * AbstractGrid contains the methods that are common to grid
 * implementations.
 * The implementation of this class is testable on the AP CS AB exam.
 */
public abstract class AbstractGrid implements Grid
{
    public ArrayList getNeighbors(Location loc)
    {
        ArrayList neighbors = new ArrayList();
        for (Location neighborLoc : getOccupiedAdjacentLocations(loc))
            neighbors.add(get(neighborLoc));
        return neighbors;
    }

    public ArrayList getValidAdjacentLocations(Location loc)
    {
        ArrayList locs = new ArrayList();

        int d = Location.NORTH;
        for (int i = 0; i < Location.FULL_CIRCLE / Location.HALF_RIGHT; i++)
        {
            Location neighborLoc = loc.getAdjacentLocation(d);
            if (isValid(neighborLoc))
                locs.add(neighborLoc);
            d = d + Location.HALF_RIGHT;
        }
        return locs;
    }

    public ArrayList getEmptyAdjacentLocations(Location loc)
    {
        ArrayList locs = new ArrayList();
        for (Location neighborLoc : getValidAdjacentLocations(loc))
        {
            if (get(neighborLoc) == null)
                locs.add(neighborLoc);
        }
        return locs;
    }

    public ArrayList getOccupiedAdjacentLocations(Location loc)
    {
        ArrayList locs = new ArrayList();
        for (Location neighborLoc : getValidAdjacentLocations(loc))
        {
            if (get(neighborLoc) != null)
                locs.add(neighborLoc);
        }
        return locs;
    }

    /**
     * Creates a string that describes this grid.
     * @return a string with descriptions of all objects in this grid (not
     * necessarily in any particular order), in the format {loc=obj, loc=obj,
     * ...}
     */
        public String toString()
        {
            String s = "{";
            for (Location loc : getOccupiedLocations())
            {
                if (s.length() > 1)
                    s += ", ";
                s += loc + "=" + get(loc);
            }
            return s + "}";
        }
}
You have attempted of activities on this page