HorseBarn free response answer 2012

The HorseBarn problem from the 2012 AP Computer Science Exam is typical of free response problems that test arrays.

HorseBarn is #3 from the 2012 AP Computer Science A Free Response.

https://secure-media.collegeboard.org/apc/ap_frq_computerscience_12.pdf

Part (a) findHorseSpace method

public int findHorseSpace(String name)
{
    for(int i = 0; i < spaces.length; i++)
    {
        Horse h = spaces[i];
        if(h != null && name.equals(h.getName()))
            return i;
    }

    return -1;
}

Part (b) consolidate method

public void consolidate()
{
    int nextSpace = 0;

    for(int i = 0; i < spaces.length; i++)
    {
        if(spaces[i] != null)
        {
            spaces[nextSpace] = spaces[i];
            nextSpace++;
        }
    }

    for(int i = nextSpace; i < spaces.length; i++)
        spaces[i] = null;
}

See Consolidate an array for an explanation of this algorithm and additional related resources.

Part (b) consolidate method (alternate solution 1)

public void consolidate()
{
    int nextSpace = 0;

    for (int i = 0; i < spaces.length; i++)
    {
        if (spaces[i] != null)
        {
            spaces[nextSpace] = spaces[i];

            if(i != nextSpace)
                spaces[i] = null;

            nextSpace++;
        }
    }
}

It is possible to set each space from which a horse was moved to null during the initial traversal. The condition i != nextSpace ensures that each horse that remained in its original position is not set to null.

Part (b) consolidate method (alternate solution 2)

public void consolidate()
{
    Horse[] newSpaces = new Horse[spaces.length];
    int newIndex = 0;

    for(int oldIndex = 0; oldIndex < spaces.length; oldIndex++)
    {
        if(spaces[oldIndex] != null)
        {
            newSpaces[newIndex] = spaces[oldIndex];
            newIndex++;
        }
    }

    spaces = newSpaces;
}

This approach makes a new array instead of moving the elements within the existing array. The algorithm is the same. This approach does not require a second loop, since all unused positions in the new array will already be null. The instance variable spaces must be updated to refer to the new array.

This approach would not work if the array to be modified was a parameter (instead of an instance variable).

Part (b) consolidate method (alternate solution 3)

public void consolidate()
{
    for(int i = 0; i < spaces.length; i++)
    {
        if(spaces[i] == null)
        {
            int nextHorse = i + 1;
            while(nextHorse < spaces.length && spaces[nextHorse] == null)
                nextHorse++;

            if(nextHorse < spaces.length)
            {
                spaces[i] = spaces[nextHorse];
                spaces[nextHorse] = null;
            }
        }
    }
}

The problem can also be solved by identifying each null position then finding the Horse that belongs there, if any. This approach is unnecessarily complex and error prone.

2012 AP CS Exam Free Response Solutions

Help & comments

Get help from AP CS Tutor Brandon Horn

Comment on HorseBarn