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 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.

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) */
    
}

Tanay’s solution:

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());
        System.out.println("removeNextByFlavor(\"grape\"): " + candyBox.removeNextByFlavor("grape"));
    }
}
CandyBoxTester.main(null);

moveCandyToFirstRow(0): true
moveCandyToFirstRow(1): true
moveCandyToFirstRow(2): true
removeNextByFlavor("cherry"): cherry
removeNextByFlavor("lime"): lime
removeNextByFlavor("grape"): REPL.$JShell$14$Candy@316fbe9e