FRQ Mini-Lab
What is Collegeboard Looking For
- Array Traversal and Access:
- Iterate through a 2D array and perform a specific operation on each element.
- Access and print specific elements or a range of elements from the array.
- Array Initialization:
- Initialize a 2D array with specified values or a pattern.
- Populate a 2D array based on given conditions or input.
- Array Manipulation:
- Modify values in the array based on certain conditions (e.g., updating specific elements, changing row or column values).
- Perform mathematical or logical operations on elements of the array.
- Searching and Sorting:
- Implement searching algorithms (e.g., linear search, binary search) on a 2D array.
- Sort rows, columns, or the entire array using a sorting algorithm.
Question
(a) Write the moveCandyToFirstRow method, which attempts to ensure that the box element at row 0 and column col contains a piece of candy, using the following steps:
- If the element at row 0 and column
colalready contains a piece of candy, thenboxis unchanged, and the method returnstrue. - If the element at row 0 and column
coldoes not contain a piece of candy, then the method searches the remaining rows of columncolfor a piece of candy. If a piece of candy can be found in columncol, it is moved to row 0, its previous location is set tonull, and the method returnstrue; otherwise, the method returnsfalse.
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.
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, and returns true. The new contents of box could be either of the following.
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 there is 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) {
/* to be implemented in part (a) */
return false;
}
(b) 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 left to 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 the box.
The following grid shows the contents of box before any of the removeNextByFlavor method calls.
The method call removeNextByFlavor("cherry") removes and returns the Candy object located in row 2 and column 0. The following grid shows the updated contents of box.
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.
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, or
* returns null if no such piece is found, as described in part (b).
*/
public Candy removeNextByFlavor(String flavor) {
/* to be implemented in part (b) */
}
public class Candy {
private String flavor;
public Candy(String flavor) {
this.flavor = flavor;
}
public String getFlavor() {
return flavor;
}
}
public class BoxOfCandy {
private Candy[][] box;
public BoxOfCandy(Candy[][] box) {
this.box = box;
}
public boolean moveCandyToFirstRow(int col) {
if (col < 0 || col >= box[0].length) {
return false; // Invalid column index
}
if (box[0][col] != null) {
return true; // Candy already in row 0
}
// Search for candy in the column and move it to row 0
for (int row = 1; row < box.length; row++) {
if (box[row][col] != null) {
box[0][col] = box[row][col];
box[row][col] = null;
return true;
}
}
return false; // No candy found in the column
}
public Candy removeNextByFlavor(String flavor) {
for (int row = box.length - 1; row >= 0; row--) {
for (int col = 0; col < box[0].length; col++) {
if (box[row][col] != null && box[row][col].getFlavor().equals(flavor)) {
Candy candyToRemove = box[row][col];
box[row][col] = null;
return candyToRemove;
}
}
}
return null; // No candy with the specified flavor found
}
// Other methods and constructors can be added here if needed
}
public class CandyBoxTester {
public static void main(String[] args) {
// Create a 3x4 box of candy for testing
Candy[][] candyGrid = {
{new Candy("chocolate"), null, new Candy("cherry"), null},
{null, new Candy("strawberry"), null, new Candy("lime")},
{new Candy("grape"), new Candy("cherry"), new Candy("cherry"), null}
};
BoxOfCandy candyBox = new BoxOfCandy(candyGrid);
// Test moveCandyToFirstRow
System.out.println("moveCandyToFirstRow(0): " + candyBox.moveCandyToFirstRow(0));
System.out.println("moveCandyToFirstRow(1): " + candyBox.moveCandyToFirstRow(1));
System.out.println("moveCandyToFirstRow(2): " + candyBox.moveCandyToFirstRow(2));
// Test removeNextByFlavor
System.out.println("removeNextByFlavor(\"cherry\"): " + candyBox.removeNextByFlavor("cherry").getFlavor());
System.out.println("removeNextByFlavor(\"lime\"): " + candyBox.removeNextByFlavor("lime").getFlavor());
}
}
CandyBoxTester.main(null);
moveCandyToFirstRow(0): true
moveCandyToFirstRow(1): true
moveCandyToFirstRow(2): true
removeNextByFlavor("cherry"): cherry
removeNextByFlavor("lime"): lime
import java.util.Scanner;
public class Candy {
private String flavor;
public Candy(String flavor) {
this.flavor = flavor;
}
public String getFlavor() {
return flavor;
}
}
class BoxOfCandy {
private Candy[][] box;
public BoxOfCandy(Candy[][] box) {
this.box = box;
}
public boolean moveCandyToFirstRow(int col) {
if (col < 0 || col >= box[0].length) {
return false; // Invalid column index
}
if (box[0][col] != null) {
return true; // Candy already in row 0
}
// Search for candy in the column and move it to row 0
for (int row = 1; row < box.length; row++) {
if (box[row][col] != null) {
box[0][col] = box[row][col];
box[row][col] = null;
return true;
}
}
return false; // No candy found in the column
}
public Candy removeNextByFlavor(String flavor) {
for (int row = box.length - 1; row >= 0; row--) {
for (int col = 0; col < box[0].length; col++) {
if (box[row][col] != null && box[row][col].getFlavor().equals(flavor)) {
Candy candyToRemove = box[row][col];
box[row][col] = null;
return candyToRemove;
}
}
}
return null; // No candy with the specified flavor found
}
public Candy[][] getBox() {
return box;
}
}
public class CandyBoxTester {
private static void displayCandyBox(BoxOfCandy candyBox) {
Candy[][] box = candyBox.getBox();
for (int row = 0; row < box.length; row++) {
for (int col = 0; col < box[0].length; col++) {
Candy candy = box[row][col];
if (candy == null) {
System.out.print("Empty\t");
} else {
System.out.print(candy.getFlavor() + "\t");
}
}
System.out.println();
}
System.out.println();
}
public static void main(String[] args) {
// Create a 3x4 box of candy for testing
Candy[][] candyGrid = {
{new Candy("chocolate"), null, new Candy("cherry"), null},
{null, new Candy("strawberry"), null, new Candy("lime")},
{new Candy("grape"), new Candy("cherry"), new Candy("cherry"), null}
};
BoxOfCandy candyBox = new BoxOfCandy(candyGrid);
Scanner scanner = new Scanner(System.in);
// Display the initial candy box
displayCandyBox(candyBox);
// User interaction loop
while (true) {
System.out.println("Choose an action:");
System.out.println("1. Move candy to the first row");
System.out.println("2. Remove candy by flavor");
System.out.println("3. Exit");
int choice = scanner.nextInt();
switch (choice) {
case 1:
System.out.print("Enter the column to move candy to the first row: ");
int col = scanner.nextInt();
boolean moved = candyBox.moveCandyToFirstRow(col);
if (moved) {
System.out.println("Candy moved successfully.");
} else {
System.out.println("Invalid column index or candy already in row 0.");
}
break;
case 2:
System.out.print("Enter the flavor to remove: ");
String flavor = scanner.next();
Candy removedCandy = candyBox.removeNextByFlavor(flavor);
if (removedCandy != null) {
System.out.println("Candy with flavor '" + flavor + "' removed: " + removedCandy.getFlavor());
} else {
System.out.println("No candy with flavor '" + flavor + "' found.");
}
break;
case 3:
scanner.close();
return;
default:
System.out.println("Invalid choice. Please try again.");
}
// Display the updated candy box
displayCandyBox(candyBox);
}
}
}
CandyBoxTester.main(null)
chocolate Empty cherry Empty
Empty strawberry Empty lime
grape cherry cherry Empty
Choose an action:
1. Move candy to the first row
2. Remove candy by flavor
3. Exit
Enter the column to move candy to the first row: Candy moved successfully.
chocolate Empty cherry Empty
Empty strawberry Empty lime
grape cherry cherry Empty
Choose an action:
1. Move candy to the first row
2. Remove candy by flavor
3. Exit
Enter the flavor to remove: Candy with flavor 'chocolate' removed: chocolate
Empty Empty cherry Empty
Empty strawberry Empty lime
grape cherry cherry Empty
Choose an action:
1. Move candy to the first row
2. Remove candy by flavor
3. Exit
Takeaways
- 2D Array Representation: The code utilizes a 2D array (Candy[][] candyGrid) to represent a grid-like structure resembling a box of candies, where candies can be organized in rows and columns.
- Flexible Storage: The 2D array allows for flexible storage and organization of candies in rows and columns, providing a structured way to hold the Candy objects within the BoxOfCandy.
- Grid Manipulation: The 2D array is manipulated within the BoxOfCandy class to perform actions like moving candies to the first row (moveCandyToFirstRow) and finding candies by flavor (removeNextByFlavor).
- Iterating Through the Grid: Loops are used to iterate through the 2D array, enabling traversal of each cell to perform operations based on the row and column indices. Candy Movement: The moveCandyToFirstRow method operates on the 2D array to move a candy from a specific column to the first row, manipulating the positions of candies within the grid.
- Flavor-Based Candy Removal: The removeNextByFlavor method uses the 2D array to search for candies with a specific flavor, iterating through rows and columns to find and remove the desired candy based on its flavor.