Problem Set 3

due by 11:59 p.m. on Tuesday, February 13, 2018

Preliminaries

In your work on this assignment, make sure to abide by the collaboration policies of the course.

If you have questions while working on this assignment, please come to office hours, post them on Piazza, or email cs112-staff@cs.bu.edu.

Make sure to submit your work on Apollo, following the procedures found at the end of the assignment.

Part I

40 points total

Problem 1: Memory management and arrays

16 points; individual-only

Put all of your work for this problem in a plain-text file named ps3pr1.txt.

In this problem, you will draw a series of diagrams that illustrate the execution of a simple program that operates on arrays. We worked on a similar problem in Lab 2, and you may find it helpful to review our solutions to that problem before continuing. We also used similar memory diagrams in our discussion of the ArrayBag class.

Consider the following Java program:

public class ArrayTest {
    public static void foo(int[] a, int[] b) {
        // part 2: what do things look like when we get here?
        int[] c = {3, 5, 7, 9};
        a = c;
        for (int i = 0; i < b.length; i++) {
             b[i] = a[i];
        }
        // part 3: what do things look like when we get here?
    }

    public static void main(String[] args) {
        int[] a = {2, 4, 6, 8};
        int[] b = new int[a.length];
        int[] c = b;

        // part 1: what do things look like when we get here?
        foo(a, b);
        // part 4: what do things look like when we get here?

        System.out.println(a[2] + " " + b[2] + " " + c[2]);
    }
}

1. Construct a single memory diagram that shows what things look like in memory just before the call to foo(). Include both the stack and the heap in your diagram. Begin by copying the following template into your text file, and then use text characters to complete the diagram.

       stack        |     heap
   +------------+
   | main       |
   |   +----+   |          +---+---+---+---+
   | a |  --|---+--------->| 2 | 4 | 6 | 8 |
   |   +----+   |          +---+---+---+---+
   |            |
   |   +----+   |
   | b |    |   |
   |   +----+   |
   |            |
   |   +----+   |
   | c |    |   |
   |   +----+   |
   +------------+
   

2. Construct a single memory diagram that shows what things look like in memory at the start of the execution of foo() – just before its first statement is executed. Include both the stack and the heap in your diagram.

3. Construct a single memory diagram that shows what things look like in memory at the end of the execution of foo() – just before it returns. Include both the stack and the heap in your diagram.

4. Construct a single memory diagram that shows what things look like in memory after the call to foo() has returned – just before the print statement executes in main().

Problem 2: Inheritance and polymorphism

14 points total; individual-only

Put all of your work for this problem in a plain-text file named ps3pr2.txt.

Imagine that you have a set of related classes that have been defined using inheritance. Here are the key facts about these classes:

• Class Gee doesn’t explicitly extend a class (i.e., it doesn’t have an extends clause in its class header). Its class members (i.e., its fields and methods) include:

  • integer fields x and y
  • a non-static method called foo() that takes no parameters and returns a String
  • its own toString() method that overrides the inherited one.

• Class Zee extends Gee. In addition to the members that it inherits, it has:

  • a String field called par
  • a non-static method called moo that takes an integer and returns a String
  • its own toString() method that overrides the inherited one.

• Class Yee extends Gee. In addition to the members that it inherits, it has:

  • an integer field z
  • its own toString() method that overrides the inherited one.

• Class Tee extends Yee. In addition to the members that it inherits, it has:

  • a String field called bar
  • an equals method that overrides the inherited one.

In addition, you should make the following assumptions:

• All of the classes employ appropriate encapsulation.

• Each class has a constructor that takes no parameters and initializes the newly created object’s fields.

• Each class includes an appropriate accessor method for each field that is declared in that class. For example, the Gee class would have accessor methods called getX() and getY().

• Each class includes an appropriate mutator method for each field that is declared in that class. For example, the Gee class would have mutator methods called setX() and setY().

Answer the following questions in light of the above information about these classes. Before you begin, you may find it helpful to draw an inheritance hierarchy for these classes, although doing so is not required.

1. The information above states that the Gee class has its own toString() method that overrides the inherited one. Where does the toString() method that Gee overrides come from? Be as specific as possible, and explain your answer briefly.

2. List all of the fields in a Tee object – both the ones that it declares and the ones (if any) that it inherits.

3. Consider the following code fragment:

   Tee t1 = new Tee();
   System.out.println(t1.equals(t1));
   System.out.println(t1.foo());
   System.out.println(t1);
   System.out.println(t1.moo());
   

   Each of the print statements in this code fragment displays the result of a method call. (This includes the third print statement, in which the Java interpreter calls a method on our behalf.) However, it is possible that one or more of these methods calls would fail to compile because the necessary method is neither defined in the Tee class nor inherited from a superclass of Tee.

   Copy the table below into your ps3pr2.txt file, and complete it with appropriate information about each of the method calls. We have filled in the first row for you.

                 |              | will the call | if the call compiles,   
     which print | which method | compile       | which version of the    
     statement   | is called    | (yes/no)?     | method will be called?  
   =======================================================================
   | first one   | equals()     | yes           | the Tee version        |
   +-------------+--------------+---------------+------------------------+
   | second one  |              |               |                        |
   +-------------+--------------+---------------+------------------------+
   | third one   |              |               |                        |
   +-------------+--------------+---------------+------------------------+
   | fourth one  |              |               |                        |
   +-------------+--------------+---------------+------------------------+
   

4. Now imagine that you want to add a non-static method to the Yee class. It should be called yow(), it should take no parameters, and it should return the sum of the integer fields in the called Yee object. Add a full definition of that method to your ps3pr2.txt file. Make sure to take into account the fact that the classes employ proper encapsulation.

5. For each of the following assignment statements, indicate whether it would be allowed according to the rules of polymorphism, and explain briefly why or why not.

   1.     Yee y = new Tee();

   2.     Zee z = new Gee();

   3.     Tee t = new Zee();

   4.     Gee g = new Tee();

Problem 3: Recursive printing

10 points; individual-only

We will review recursion in lecture on Thursday or Friday of this week.

Consider the following recursive method:

public static void printPattern(int m, int n) {
    if (m == n) {
        return;
    }

    if (m < n) {
        System.out.println("(");
        printPattern(m + 1, n);
        System.out.println("\\");     /* prints a single backslash */
    } else {
        System.out.println("/");
        printPattern(m, n + 1);
        System.out.println(")");
    }
}

To experiment with this method, you should take the following steps:

• Download the file Problem3.java and open it in DrJava. You should see a class named Problem3 that contains the printPattern method.
• Compile the class.
• This class doesn’t include a main method, so you can’t run it. Instead, you should invoke the printPattern method in the Interactions Pane, preceding the method name with the class name, as we do whenever we call a static method from outside the class. For example:

  > Problem3.printPattern(2, 6)
  

Try several different parameters and see what output is produced in each case. Then answer the following questions:

1. Trace the execution of printPattern(1, 4). Use indentation to indicate which statements are performed by a given invocation of the method, following the approach used in the lecture notes to trace printSeries.

2. Will the method ever produce infinite recursion? In other words, is there a combination of initial parameters that would produce a series of recursive calls that never reaches the base case? Explain your answer briefly.

3. Modify the method so that the patterns that it prints are reversed. For example, if calling the method above with a given combination of parameters prints the following:

   /
   /
   /
   )
   )
   )
   

   calling the revised method with the same combination of parameters should print this instead:

   )
   )
   )
   /
   /
   /
   

   The new method must also be fully recursive. The use of loops is not allowed.

   Once you have the modified method working, put it in your ps3pr3.txt file.

Part II

60 points total

Problem 4: Completing the game of Buno

30 points; pair-optional

This is the only problem of the assignment that you may complete with a partner. See the rules for working with a partner on pair-optional problems for details about how this type of collaboration must be structured.

Overview
In Problem Set 2, you implemented a Card class for the game of Buno. In this problem, you will finish your implementation of the game.

The version of the game that you will complete allows a single human player (the user) to compete against a single computer player.

Rules of the game
Buno cards have a color (blue, green, red, or yellow) and a value between 0 and 9. At the start of the game, each player is dealt a hand of five cards, and a single card is turned over to form the beginning of a discard pile.

Players take turns attempting to discard a single card from their hands. The card to be discarded must match either the color or the value of the card at the top of the discard pile. For example, if the card at the top of the discard pile is a blue 3, a player could play a blue card of any value, or a 3 card of any color. If a player has no cards that match the top of the discard pile, he or she must draw a card and wait until his or her next turn.

The game continues until a player has no cards left or until a player accumulates 10 cards. At the end of the game, the player whose final hand has the smallest total value wins the game and earns the total value of the other players’ final hands. To reduce the likelihood of a player winning with 10 cards, a penalty of 25 points is added to the value of any hand with 10 cards. If there is a tie (two or more players with hands that have the same smallest final value), no one wins any points.

For example, let’s say that there are two players and one of them accumulates 10 cards, ending the game. Assume that the final hands of the players are:

player 1: red 2, yellow 3, blue 1
player 2: green 3, red 1, blue 2, red 2, yellow 1, yellow 3, red 1, blue 0, green 1, red 3

Player 1 ends up with the final hand with the smallest total value (2+3+1 = 6) and thus wins the game. Player 2’s final hand value is 3+1+2+2+1+3+1+0+1+3 = 17, plus the added 25-point penalty, to give 42. Player 1 earns 42 points.

Because the player with the smallest total value wins, players have an incentive to discard cards with a high value.

Sample runs
The version of the game that you will implement will allow a human player to play against the computer. Here are some sample runs of the game:

• first sample run (random seed = 429)
• second sample run (random seed = 111)
• third sample run (random seed = 99)

Notes about the sample runs:

• See the section below entitled Testing your code for information about how to specify a random seed.
• In each sample run, user inputs are underlined.
• When selecting a card to play, the computer player in the sample runs uses the minimal approach described in Task 3 below. If there is more than one matching card, it selects the one with the highest value. If there are multiple matching cards that are tied for the highest value, it selects the one that comes closest to the beginning of the hand (i.e., the one with the smallest index).
• If you use a different algorithm for selecting the computer’s discard, you may get somewhat different results.

Structure of the program
The code for your Buno program will be divided into a number of different classes. In particular, you will use the Card class that you wrote for Problem Set 2.

In addition, we are giving you complete or nearly complete implementations of the following classes:

• Deck.java
  This class is a blueprint for objects that represent a deck of Buno cards. These objects have several methods, the most useful of which are the shuffle and dealCard methods. It uses a random-number generator when shuffling the cards to get a different ordering of the deck each time. When testing your code, it’s possible to control the numbers generated by the random-number generator so that you can get repeatable hands of cards. See the section below entitled Testing your code for more details. You should not modify the code in this class.

• Buno.java
  This class contains the main method of the program; you will run this class to start the program. In addition, this class serves as a blueprint for objects that maintain the state of a Buno game. It includes fields for things like the deck, the players, and the card at the top of the discard pile, and it includes methods that are used to execute the various stages of the game. You should not make any modifications to this class except for the single change specified in Task 3.

Download these files, storing them in the folder that you are using for this assignment. In addition, make sure that you put a copy of your Card.java file from Problem Set 2 in the same folder.

Task 1: review the provided code
Begin by reading over the code that we have given you. In particular, you should look at how the Buno class will make use of the types of objects that you will create below. You do not need to fully understand how the Deck class works, but we encourage you to look it over.

Task 2: create a blueprint class for a player
Write a class named Player that serves as a blueprint for objects that represent a single Buno player. Save it in the same folder as the classes that you downloaded above. Import the java.util package at the start of the file.

Each Player object should have the following components:

1. fields to keep track of the player’s name (a single string) and the cards in the player’s hand. Make sure that your field definitions prevent direct access by code from outside the class.

   • You should use an array to store the cards in the player’s hand.
   • In addition, you will need a field to keep track of how many cards are currently in the player’s hand.

2. a constructor that takes a single parameter for the name of the player. It should initialize all of the fields. Among other things, it should create the array that will store the cards. Make the collection big enough to store the maximum number of cards in a given hand (10). Use the class constant Buno.MAX_CARDS to specify this value, rather than hard-coding the integer 10.

3. an accessor named getName that returns the player’s name.

4. an accessor named getNumCards that returns the current number of cards in the player’s hand.

5. a toString method that just returns the player’s name.

6. a mutator named addCardToHand that takes a Card object as a parameter and adds the specified card to the player’s hand, filling the array from left to right. It should return a boolean to indicate success or failure: true if there is room to add the Card, and false if the player already has the maximum number of cards. It should throw an IllegalArgumentException if the parameter is null.

7. an accessor named getCardFromHand that takes an integer index as a parameter and returns the Card at the specified position in the player’s hand, without actually removing the card from the hand. For example, if p is a Player, p.getCardFromHand(0) should return the card at position 0 in p‘s hand – i.e., the first/leftmost card. If the specified index does not correspond to one of the cards in the hand, the method should throw an IllegalArgumentException.

8. an accessor method named getHandValue that computes and returns the total value of the player’s current hand – i.e., the sum of the values of the individual cards, plus an additional 25-point penalty if the hand has the maximum number of cards. Use the class constants given in Buno.java for the maximum number of cards and for the penalty associated with having that many cards.

9. an accessor method named printHand that prints the current contents of the player’s hand, preceded by a heading that includes the player’s name. Each card should be printed on a separate line, preceded by the index of its position in the hand. For example:

   John's hand:
     0: red 7
     1: green 2
     2: blue 3
   

   For full credit, you should include two spaces before each index value. You should also make sure that you do not have any extra spaces at the end of a given line.

   See the sample runs for additional examples.

10. a mutator method named removeCardFromHand that takes an integer index as a parameter and both removes and returns the Card at that position of the player’s hand. If the specified index does not correspond to one of the cards in the hand, the method should throw an IndexOutOfBoundsException.

    After the card has been removed, the remaining cards (if any) should be rearranged as needed so that they occupy the leftmost positions of the array. To do so, you must move the rightmost card into the position of the card that is being removed. For example, if the hand is currently the four cards {blue 3, red 2, yellow 7, green 1} and you are removing the card at position 1 (the red 2), you must replace it with the last card (the green 1), and thus the resulting hand would be: {blue 3, green 1, yellow 7}. In addition, you should assign a value of null to the position of the array that used to hold the rightmost card.

11. an accessor method named getPlay that determines and returns the number corresponding to the player’s next play: either -1 if the player wants to draw a card, or the number/index of the card that the player wants to discard from his/her hand. The method should take two parameters: a Scanner object that can be used to read from the console, and a Card object representing the card that is currently at the top of the discard pile.

    • The method should print the appropriate prompt and read an integer from the console. If the number entered is invalid (i.e., if it is neither -1 nor an index of one of the cards in the hand), the method should continue asking for a new value until the player enters a valid one.

    • You do not need to worry about whether the specified card matches the top of the discard pile, because the code that we have given you in the Buno class already checks for that.

    • You may assume that the player never enters a non-integer.

    • Because this version of the method is for a human player, it can ignore the second parameter (the card at the top of the discard pile). The version of this method that you will write in Task 3 will be for a computer user, and it will use the second parameter.

After completing all of Task 2, you should be able to open and compile the Buno class, and run it to play the game. At this point, the computer will be represented by a Player object, which means that you will be able to see the contents of its hand, and that its plays will be determined using the getPlay method that you implemented above. In other words, you will need to enter the plays for both players!

If the Buno class doesn’t compile, that probably means that there are problems in the headers of one or more of your Player methods. Change your Player class as needed until the Buno class compiles. Remember that you are not allowed to change the Deck class in any way. In addition, you should not change the Buno class at this point in the process.

When running the program, you must highlight Buno.java in the list of files before clicking the Run button.

Task 3: create a blueprint class for a computer player
The Player class that you wrote for Task 3 serves as a blueprint for the human player — since its getPlay method asks the user of the program to enter the next play from the console. In this task, you will write a class named ComputerPlayer that serves as a blueprint for objects that represent a computer player.

Save it in the same folder as your other classes for this program. Import the java.util package at the start of the file.

Most of the state and behavior needed for a ComputerPlayer is already present in Player. Thus, you should make ComputerPlayer a subclass of Player, so that it will inherit the fields and methods of that class. In addition to the inherited fields and methods, this class will need:

1. its own constructor, which should take the name of the player as its only parameter.

2. a printHand method that overrides the inherited version of that method. This version of the method should simply print the number of cards in the ComputerPlayer‘s hand. For example:

   the computer's hand: 3 cards
   

   • Use the name given to the player when the object was created (which may not always be "the computer").
   • If there is only one card, use the word "card" instead of "cards".

3. a getPlay method that overrides the inherited version of that method. This version of the method should figure out if the computer has a card that matches the card at the top of the discard pile (this card is passed in as the second parameter of the method). If the computer doesn’t have a matching card, the method should return -1 so that the computer will end up drawing a card. If the computer does have one or more matching cards, the method should return the index of the card that should be played.

   • If there is more than one card that matches the card at the top of the discard pile, you should select the one with the highest value.

   • Optionally, you could also factor in the color of the cards. For example, if the computer has multiple cards that match the card at the top of the discard pile, and if two or more of them are tied for the highest value, it might make sense for it to choose the one with the color that is shared by the largest number of other cards in the computer’s hand.

Once you have defined your ComputerPlayer class, modify the line of code in the Buno constructor that assigns a value to the second element of the players array (players[1]). Instead of assigning a Player object, it should now assign a ComputerPlayer object. You should not make any other changes to the Buno class.

If you have implemented everything correctly, the computer’s hand should now be hidden when you run the program, and the computer should determine its own play, rather than asking you to enter it from the keyboard.

Once all of these tasks are completed, you should have a working Buno game!

Testing your code
To get repeatable hands for testing purposes, you can specify a seed for the random-number generator used by the Deck class when it shuffles the deck. To do so, you should run the program from within the Interactions Pane. Compile the program, and then enter the following in the Interactions Pane:

java Buno seed

where you replace seed with an integer.

To make sure that the getPlay method in your ComputerPlayer class is working correctly, you may want to temporarily comment out the printHand method in that class. Doing so will cause all of the dealer’s cards to be displayed, which will allow you to see ifgetPlay is selecting the correct card. Make sure to uncomment printHand before submitting the file.

Problem 5: Adding methods to the ArrayBag class

20 points total; individual-only

Begin by downloading the file ArrayBag.java and opening it in DrJava.

Add the methods described below to the ArrayBag class, and then add code to the main() method to test these methods. You should not add any new fields to the class.

1. public int capacity()

   This method should return the maximum number of items that the ArrayBag is able to hold. This value does not depend on the number of items that are currently in the ArrayBag — it is the same as the maximum size specified when the ArrayBag was created. For example:

   > ArrayBag b1 = new ArrayBag(10);
   > ArrayBag b2 = new ArrayBag(20);
   > b1.capacity()
   10
   > b2.capacity()
   20
   > b1.add("hello");
   > b1.capacity()    // capacity doesn't change as items are added
   10
   

2. public boolean isEmpty()

   This method should return true if the ArrayBag is empty, and false otherwise. For example:

   > ArrayBag b1 = new ArrayBag(10);
   > b1.isEmpty()
   true
   > b1.add("hello");
   > b1.isEmpty()
   false
   

3. public boolean addAll(Object[] newItems)

   This method should attempt to add to the called ArrayBag all of the items found in the array newItems that is passed as a parameter, and it should return a boolean value indicating success or failure.

   • If there is enough room for all of the items to be added, the items should be added and the method should return true.

   • If there isn’t enough room for all of the items to be added, none of them should be added, and the method should simply return false.

   For example:

   > ArrayBag b1 = new ArrayBag(6);
   > String[] words = {"hello", "how", "are", "you?"};
   > b1.addAll(words)
   true
   > b1
   > {hello, how, are, you?}
   > String[] words2 = {"not", "bad", "thanks!"};
   > b1.addAll(words2)
   false
   > b1
   > {hello, how, are, you?}
   > String[] words3 = {"not", "bad!"};
   > b1.addAll(words3)
   true
   > b1
   > {hello, how, are, you?, not, bad!}
   

   For full credit, you should take full advantage of the existing ArrayBag methods.

4. public ArrayBag merge(ArrayBag other)

   This method should create and return an ArrayBag containing one occurrence of any item that is found in either the called object or the parameter other. For full credit, the resulting bag should not include any duplicates. Give the new ArrayBag a maximum size that is the sum of the two bag’s maximum sizes.

   For example:

   > ArrayBag b1 = new ArrayBag(10);
   > String[] letters1 = {"a", "a", "b", "d", "f", "f", "f", "g"};
   > b1.addAll(letters1);
   > ArrayBag b2 = new ArrayBag(8);
   > String[] letters2 = {"a", "b", "c", "d", "d", "e", "f"};
   > b2.addAll(letters2);
   > ArrayBag b3 = b1.merge(b2);
   > b3
   {a, b, d, f, g, c, e}    // order doesn't matter!
   > b3.capacity()
   18
   > b3.numItems()
   7
   > b1     // make sure original bags are unchanged
   {a, a, b, d, f, f, f, g}
   > b2
   {a, b, c, d, d, e, f}
   

   For full credit, you should take full advantage of the existing ArrayBag methods. They will make your job much easier!

   Special cases:

   • If one of the bags is empty, the method should return an ArrayBag containing one occurrence of each item in the non-empty bag.
   • If both of the bags are empty, the method should return an empty ArrayBag.
   • If the parameter is null, the method should throw an IllegalArgumentException.

Problem 6: Recursive string processing

10 points total; individual-only

In a class named Problem6, implement the methods described below, and then create a main() method to test these methods.

Here are the methods you should write:

1. a static method called reflect that takes a string as its parameter and uses recursion to create and return a “reflected” version of the string in which the original string is followed by the characters of the string in reverse order. For example:

   > Problem6.reflect("method")
   "methoddohtem"
   

   This method should not do any printing; rather, it should return the appropriate string.

   Special case: If a null value is passed into the method, it should throw an IllegalArgumentException.

2. a static method called lastIndexOf that takes as its two parameters a string str and a character ch and returns the index of the last occurrence of ch in str. If ch does not appear in str at all, the method should return -1. For example:

   > Problem6.lastIndexOf("Boston", 'o')
   4
   > Problem6.lastIndexOf("banana", 'a')
   5
   > Problem6.lastIndexOf("banana", 'b')
   0
   > Problem6.lastIndexOf("banana", 'x')
   -1
   

   Special case: If a null value is passed into the method, it should throw an IllegalArgumentException.

   In Problem Set 1, you solved this problem using iteration. In this problem, you must use recursion instead.

Submitting Your Work

You should use Apollo to submit the following files:

• your ps3pr1.txt file containing your solutions for Problem 1
• your ps3pr2.txt file containing your solutions for Problem 2;
• your ps3pr3.txt file containing your solutions for Problem 3
• your Player.java and ComputerPlayer.java files containing your solutions for Problem 4; if you worked with a partner, make sure that you each submit a copy of your joint work, and that you include comments at the top of each file specifying the name and email of your partner
• your modified ArrayBag.java file containing your solutions for Problem 5
• your Problem6.java file containing your solutions for Problem 6

Here are the steps:

1. Login to Apollo, using the link in the left-hand navigation bar. You will need to use your Kerberos user name and password.
2. Check to see that your BU username is at the top of the Apollo page. If it isn’t, click the Log out button and login again.
3. Find the appropriate problem set section on the main page and click Upload files.
4. For each file that you want to submit, find the matching upload section for the file. Make sure that you use the right section for each file. You may upload any number of files at a time.
5. Click the Upload button at the bottom of the page.
6. Review the upload results. If Apollo reports any issues, return to the upload page by clicking the link at the top of the results page, and try the upload again, per Apollo’s advice.
7. Once all of your files have been successfully uploaded, return to the upload page by clicking the link at the top of the results page. The upload page will show you when you uploaded each file, and it will give you a way to view or download the uploaded file. Click on the link for each file so that you can ensure that you submitted the correct file.