2023 Free Response

Write the findFreeBlock method, which searches for the first block of free minutes in period for the first block of free minutes that is duration minutes long. If a block is found, findFreeBlock returns the first minute in the block. Otherwise, findFreeBlock returns -1. The findFreeBlock method uses the helper method isMinuteFree, which returns true if a particular minute is able to be included in a new appointment and returns false if the minute is unavailable.

Consider the following list of unavailable and available minutes in period 2.

The method call findFreeBlock(2, 15) would return 30 to indicate that a 15-minute block starting with minute 30 is available. No steps should be taken as a result of the call to findFreeBlock to mark those 15 minutes as unavailable.

The method call findFreeBlock(2, 9) would also return 30. Whenever there are multiple blocks that satisfy the requirement, the earliest starting minute is returned.

The method call findFreeBlock(2, 20) would return -1, since no 20-minute block of available minutes exists in period 2.

Complete method findFreeBlock. You must use isMinuteFree appropriately in order to receive full credit.

/**
 * Searches for the first block of duration free minutes during period, as described in
 * part (a). Returns the first minute in the block if such a block is found or returns -1 if no
 * such block is found.
 * Preconditions: 1 <= period <= 8; 1 <= duration <= 60
 */
public int findFreeBlock(int period, int duration)

Write the makeAppointment method, which searches the periods from startPeriod to endPeriod, inclusive, for the earliest block of duration available minutes in the lowest-numbered period. If such a block is found, the makeAppointment method calls the helper method reserveBlock to mark the minutes in the block as unavailable and returns true. If no block is found, the makeAppointment method returns false.

Consider the following list of unavailable and available minutes in periods 2, 3, and 4 and three successive calls to makeAppointment.

The method call makeAppointment(2, 4, 22) returns true and results in the minutes 5 through 26, inclusive, in period 4 being marked as unavailable.

The method call makeAppointment(3, 4, 3) returns true and results in the minutes 0 through 2, inclusive, in period 3 being marked as unavailable.

The method call makeAppointment(2, 4, 30) returns false, since there is no block of 30 available minutes in periods 2, 3, or 4.

The following shows the updated list of unavailable and available minutes in periods 2, 3, and 4 after the three example method calls are complete.

Complete method makeAppointment. Assume that findFreeBlock works as intended, regardless of what you wrote in part (a). You must use findFreeBlock and reserveBlock appropriately in order to receive full credit.

/**
 * Searches periods from startPeriod to endPeriod, inclusive, for a block
 * of duration free minutes, as described in part (b). If such a block is found, and
 * calls reserveBlock to reserve the block of minutes and returns true; otherwise
 * returns false.
 * Preconditions: 1 <= startPeriod <= endPeriod <= 8; 1 <= duration <= 60
 */
public boolean makeAppointment(int startPeriod, int endPeriod,
                                int duration)

[Class information for this question box:]

public class AppointmentBook
private boolean isMinuteFree(int period, int minute)
private void reserveBlock(int period, int startMinute,
    int duration)
public int findFreeBlock(int period, int duration)
public boolean makeAppointment(int startPeriod, int endPeriod,
    int duration)

Write the cleanData method, which modifies the temperatures instance variable by removing all values that are less than the lower parameter and all values that are greater than the upper parameter. The order of the remaining values in temperatures must be maintained.

For example, consider a WeatherData object for which temperatures contains the following.

99.1 | 142.0 | 85.0 | 85.1 | 84.6 | 94.3 | 124.9 | 98.0 | 101.0 | 102.5

The three shaded values shown would be removed by the method call cleanData(85.0, 120.0).

[Table of the same 10 values with three cells shaded gray: 142.0, 84.6, and 124.9]

99.1 | 142.0 | 85.0 | 85.1 | 84.6 | 94.3 | 124.9 | 98.0 | 101.0 | 102.5

The following shows the contents of temperatures after the three shaded values are removed as a result of the method call cleanData(85.0, 120.0).

99.1 | 85.0 | 85.1 | 94.3 | 98.0 | 101.0 | 102.5

Complete method cleanData.

/**
 * Cleans the data by removing from temperatures all values that are less than
 * lower and all values that are greater than upper, as described in part (a)
 */
public void cleanData(double lower, double upper)

Write the longestHeatWave method, which returns the length of the longest heat wave found in the temperatures instance variable. A heat wave is a sequence of two or more consecutive days with a daily high temperature greater than the parameter threshold. The temperatures instance variable is guaranteed to contain at least one heat wave based on the threshold parameter.

For example, consider the following contents of temperatures.

100.5 | 98.5 | 102.0 | 103.9 | 87.5 | 105.2 | 90.3 | 94.8 | 109.1 | 102.1 | 107.4 | 93.2

In the following sample contents of temperatures, all heat waves based on the threshold temperature of 100.5 are shaded. The method call longestHeatWave(100.5) would return 3, which is the length of the longest heat wave.

[Table of 12 values with some cells shaded gray to mark heat-wave membership; shaded values are 102.0, 103.9 (one heat wave) and 109.1, 102.1, 107.4 (the longest heat wave, length 3); the value 100.5 is not shaded because it is not part of a run of two or more consecutive values greater than 100.5]

100.5 | 98.5 | 102.0 | 103.9 | 87.5 | 105.2 | 90.3 | 94.8 | 109.1 | 102.1 | 107.4 | 93.2

In the following sample contents of temperatures, all heat waves based on the threshold temperature of 95.2 are shaded. The method call longestHeatWave(95.2) would return 4, which is the length of the longest heat wave.

[Table of the same 12 values with some cells shaded gray; shaded values are 100.5, 98.5, 102.0, 103.9 (the longest heat wave, length 4) and 109.1, 102.1, 107.4 (a heat wave of length 3); the values 87.5, 105.2, 90.3, 94.8, 93.2 are not shaded]

100.5 | 98.5 | 102.0 | 103.9 | 87.5 | 105.2 | 90.3 | 94.8 | 109.1 | 102.1 | 107.4 | 93.2

Complete method longestHeatWave.

/**
 * Returns the length of the longest heat wave found in temperatures, as described in
 * part (b)
 * Precondition: There is at least one heat wave in temperatures based on threshold.
 */
public int longestHeatWave(double threshold)

[Class information for this question box:]

public class WeatherData
private ArrayList<Double> temperatures
public void cleanData(double lower, double upper)
public int longestHeatWave(double threshold)

Write the moveCandyToFirstRow method, which ensures that the box element at row 0 of column col contains a piece of candy, as described by the following steps.

• If the element at row 0 and column col already contains a piece of candy, then box is unchanged and the method returns true.
• If the element at row 0 and column col does not contain a piece of candy, then the method searches the remaining rows of column col for a piece of candy. If a piece of candy can be found in column col, it is moved to row 0, its previous location is set to null, and the method returns true; otherwise, the method returns false.

In the following example, the grid represents the contents of box. An empty square in the grid is null in box. A non-empty square in the grid represents a box element that contains a Candy object. The string in the square of the grid indicates the flavor of the piece of candy.

[Grid diagram, 4 rows x 3 columns, column headers 0, 1, 2: row 0: col0 = "lime" (candy icon), col1 = empty, col2 = empty row 1: col0 = "orange" (candy icon), col1 = empty, col2 = empty row 2: col0 = empty, col1 = empty, col2 = "cherry" (candy icon) row 3: col0 = "lemon" (candy icon), col1 = "grape" (candy icon), col2 = empty]

The method call moveCandyToFirstRow(0) returns false because the box element at row 0 and column 0 does not contain a piece of candy and there are no pieces of candy in column 0 that can be moved to row 0. The contents of box are unchanged.

The method call moveCandyToFirstRow(1) returns true because the box element at row 0 and column 1 already contains a piece of candy. The contents of box are unchanged.

The method call moveCandyToFirstRow(2) moves one of the two pieces of candy in column 2 to row 0 of column 2, sets the previous location of the piece of candy that was moved to null, to row 0 of column 2, and returns true. The new contents of box could be either of the following.

[Grid diagram option 1, 4 rows x 3 columns: row 0: col0 = "lime", col1 = empty, col2 = "cherry" row 1: col0 = "orange", col1 = empty, col2 = empty row 2: col0 = empty, col1 = empty, col2 = empty row 3: col0 = "lemon", col1 = "grape", col2 = empty]

or

[Grid diagram option 2, 4 rows x 3 columns: row 0: col0 = "lime", col1 = empty, col2 = "grape" row 1: col0 = "orange", col1 = empty, col2 = empty row 2: col0 = empty, col1 = empty, col2 = "cherry" row 3: col0 = "lemon", col1 = empty, col2 = empty]

Complete the moveCandyToFirstRow method.

/**
 * Moves one piece of candy in column col, if necessary and possible, so that the box
 * element in row 0 of column col contains a piece of candy, as described in part (a).
 * Returns false if no piece of candy in column col and returns true otherwise.
 * Precondition: col is a valid column index in box.
 */
public boolean moveCandyToFirstRow(int col)

[Class information for this question box:]

public class Candy
public String getFlavor()
public class BoxOfCandy
private Candy[][] box
public boolean moveCandyToFirstRow(int col)
public Candy removeNextByFlavor(String flavor)

Write the removeNextByFlavor method, which attempts to remove and return one piece of candy from the box. The piece of candy to be removed is the first piece of candy with a flavor equal to the parameter flavor that is encountered while traversing the candy box in the following order: the last row of the box is traversed from left to right, then the next-to-last row of the box is traversed from right, etc., until either a piece of candy with the desired flavor is found or until the entire candy box has been searched.

If the removeNextByFlavor method finds a Candy object with the desired flavor, the corresponding box element is assigned null, all other box elements are unchanged, and the removed Candy object is returned. Otherwise, box is unchanged and the method returns null.

The following examples show three consecutive calls to the removeNextByFlavor method. The traversal of the candy box always begins in the last row and first column of box.

The following grid shows the contents of box before any of the removeNextByFlavor method calls.

[Grid diagram, 3 rows x 5 columns, column headers 0,1,2,3,4: row 0: col0 = "lime", col1 = "lime", col2 = empty, col3 = "lemon", col4 = empty row 1: col0 = "orange", col1 = empty, col2 = empty, col3 = "lime", col4 = "lime" row 2: col0 = "cherry", col1 = empty, col2 = empty, col3 = empty, col4 = "orange"]

The method call removeNextByFlavor("cherry") removes and returns the Candy object located at row 2 and column 0. The following grid shows the updated contents of box.

[Grid diagram after removal, 3 rows x 5 columns: row 0: col0 = "lime", col1 = "lime", col2 = empty, col3 = "lemon", col4 = empty row 1: col0 = "orange", col1 = empty, col2 = empty, col3 = "lime", col4 = "lime" row 2: col0 = empty, col1 = empty, col2 = empty, col3 = empty, col4 = "orange"]

The method call removeNextByFlavor("lime") removes and returns the Candy object located in row 1 and column 3. The following grid shows the updated contents of box.

[Grid diagram after second removal, 3 rows x 5 columns: row 0: col0 = "lime", col1 = "lime", col2 = empty, col3 = "lemon", col4 = empty row 1: col0 = "orange", col1 = empty, col2 = empty, col3 = empty, col4 = "lime" row 2: col0 = empty, col1 = empty, col2 = empty, col3 = empty, col4 = "orange"]

The method call removeNextByFlavor("grape") returns null because no grape-flavored candy is found. The contents of box are unchanged.

Complete the removeNextByFlavor method.

/**
 * Removes from box and returns a piece of candy with flavor specified by the parameter,
 * flavor. Returns null if no such piece is found, as described in part (b)
 */
public Candy removeNextByFlavor(String flavor)

[Class information for this question box:]

public class Candy
public String getFlavor()
public class BoxOfCandy
private Candy[][] box
public boolean moveCandyToFirstRow(int col)
public Candy removeNextByFlavor(String flavor)