Data Structures Assignment#1 Solution

OVERVIEW



Purpose: To refresh your Java programming skills and to emphasize the object-oriented programming approach used in Java. Specifically, you will work with control structures, class-building, interfaces and generics to create and utilize a simple array-based data structure.

Goal 1: To design and implement a simple class MultiDS<T> that will act as a simple data structure for accessing Java Objects. Your MultiDS<T> class will primarily implement 2 interfaces – PrimQ<T> and Reorder. The details of these interfaces are explained in the files PrimQ.java and Reorder.java. Read these files over very carefully before implementing your MultiDS<T> class.

Goal 2: To utilize your MultiDS<T> class by implementing a simple version of the card game "Snap". In this case your program will be a client using MultiDS<T> and the details of the MultiDS<T> implementation will be abstracted out.

DETAILS


Details 1: For the details on the functionality of your MultiDS<T> class, carefully read over the files PrimQ.java, Reorder.java and Assig1A.java provided on the CourseWeb folder where you find this assignment description. You must use these files as specified and cannot remove/alter any of the code that is already written in them. There are different ways of implementing the PrimQ<T> and Reorder interface methods, some of which are more efficient than others. Try to think of the best way of implementing these methods in this assignment, but the most important thing at this point is getting them to work. A lot of pencil and paper work is recommended before actually starting to write your code. Later we will discuss the relative merits of different implementations. Your MultiDS<T> class header should be:


public class MultiDS<T> implements PrimQ<T>, Reorder

Important Note: The primary data within your MultiDS<T> class must be an array. You may not use any predefined Java collection class (e.g., ArrayList) for your MultiDS<T> data.



    1 Assignment adapted from Dr. John Ramirez’s CS 445 class.


After you have finished your coding of MultiDS<T>, the Assig1A.java file provided for you should compile and run correctly, and should give output identical to the output shown in the sample executions (except for the segments where the data is shuffled, since it will be pseudo-random in that case).



Details 2: Snap is a simple card game that has many variations. You will implement a simple version as described below:

This is a multi-player game. The number of players is between 2 and 7, inclusive. Let’s use the symbol n to denote the number of players.

Initially shuffle a 52-card standard deck of cards.

Deal the cards out completely to the players, alternating cards to each player. If 52%n != 0, assign each player 52/n cards and move the remaining cards (52%n) to the snap-pool.

Each player puts his cards into his face-down card pile and has his face-up pile initially empty. A snap-pool pile (at the center of the table) is initially empty as well.

In total, we have 2n+1 card piles, n+1 piles with face-up cards (each player’s face-up pile and the snap-pool and n face-down piles.

Do the following until the first player runs out of cards or the number of iterations is equal to the specified number of rounds (whichever happens first should stop the loop):

        1. Each player moves the top card of his face-down pile into his face-up pile.

        2. If two cards at the top of any of the face-up piles have the same rank (suits don't matter), a match is declared.

        3. Each player has a probability of shouting “Snap!” when a match occurs and another probability of (incorrectly) shouting “Snap!” when no match occurs. These two probabilities are 0.4 and 0.01, respectively, for all players.

        4. The player who correctly shouts “Snap!” when no other player shouts wins the round. She then moves the matching piles into the bottom of her own face-down pile after shuffling them. The winning player in the round gets the face-up pile of the other player and the snap-pool pile into his face-down pile.

        5. Any player (can be more than one player) who incorrectly shouts “Snap!” moves his face-up cards into the bottom of the snap-pool pile after shuffling.

The following rules also apply to the game:

If at any point in the game a player's face-down pile is empty, the player should move the cards in his face-up pile into his face-down pile after shuffling.

If at any point in the game a player has no cards remaining in both his piles, he/she is out of the game.

If more than one player have cards remaining after the set number of rounds, the player with the most cards (face-up + face-down) is the winner. In this case, it is possible for a tie between p players to occur, with each player having 52/p cards.



2
IMPLEMENTATION REQUIREMENTS


Your initial card deck, the players' face-up and face-down piles, and the snap-pool pile must all be stored in MultiDS<Card> objects.

The Card class must be used as provided and cannot be changed.

The number of players and the maximum number of rounds for the game must be read in from the command line.

To allow better testing of your program, you must output when correct and incorrect snaps occur and when piles are reshuffled. See the various sample output files for required output information.

SUBMISSION REQUIREMENTS


You must submit, in a single .zip file, at least the following six complete, working source files for full credit:

    1. PrimQ.java

    2. Reorder.java

    3. Assig1A.java

    4. Card.java

The above four files are given to you and must not be altered in any way.

    5. MultiDS.java

    6. Snap.java

The above two files must be created so that they work as described. If you create any additional files, be sure to include those as well.

The idea from your submission is that your TA can unzip your .zip file, then compile and run both of the main programs (Assig1A.java and Snap.java) from the command line WITHOUT ANY additional files or changes, so be sure to test it thoroughly before submitting it.

If you cannot get the programs working as given, clearly indicate any changes you made and clearly indicate why (e.g., "I could not get the reverse() method to work, so I eliminated code that used it") on your Assignment Information Sheet. You will lose some credit for not getting it to work properly, but getting the main programs to work with modifications is better than not getting them to work at all. A template for the Assignment Information Sheet can be found in the assignment’s CourseWeb folder. You do not have to use this template but your sheet should contain the same information.

Note: If you use an IDE such as NetBeans, Eclipse, or IntelliJ, to develop your programs, make sure they will compile and run on the command line before submitting – this may require some modifications to your program (such as removing some package information).




RUBRICS


Please check the grading rubric on CourseWeb.

3

HINTS / NOTES


    1. See program A1Help.java for some help with the Card class and using the MultiDS<T> class with Card objects.

    2. See file A1Out.txt to see how your output for Assig1A should look. As noted, your output when running Assig1A.java should be identical to this with the exception of the order of the values after being shuffled.

    3. See files SnapOut1.txt, SnapOut2.txt, SnapOut3.txt, and SnapOut4.txt for example runs of my Snap.java program. Your Snap program output does not have to look exactly like this but the functionality should be the same.

    4. Your MultiDS<T> class will need to allow for a variable number of objects, up to some maximum number (set by the initial size). You can implement this by having an integer instance variable (e.g., "count") that indicates how many slots in the MultiDS<T> are filled. For example, you could have a MultiDS<Card> with a capacity of 52 cards for a pile with anywhere from 0 up to 52 Cards in it. In this case, the array length (i.e., physical size) would be 52 but the "count" (i.e., logical size) would be some value between 0 and 52. When implementing MultiDS<T> be careful to use the "count" value rather than the array length when doing operations such as the toString() method.

    5. In order for the Assig1A.java output to show correctly, you must override the toString() method in the MultiDS class. You should be familiar with the toString() method from CS 0401.

    6. You can easily generate the "deck" of cards for your Snap game with nested for loops. You should NOT have 52 individual statements to do this! See A1Help.java for some hints about how to generate the deck of cards.

    7. Note that for the most part, all of your methods (in both interfaces) in your MultiDS class should act on the logical data structure -- accessing only the locations in the array that actually are storing data (See note 4 above).

    8. You can use an object of the MultiDS<Integer> class to determine winning and incorrect Snaps conditions each round.

    9. MultiDS<T> can be the type of the elements stored in your data structure. That is, you can define an object of type MultiDS<MultiDS<Card>>. You may add the below static method to the MultiDS class. It retrieves the item with logical order index inside a MultiDS object --- without affecting the order. It does that by calling shiftLeft(), top(), and shiftRight(). Of course, this way is not efficient at all. Some data structures perform poorly if you ask them to do an operation they are not designed for! You may be able to do slightly better without the getItem method. We will see data structures that more

efficiently gets an item using an index later in the course.

static public <T> T getItem(MultiDS<T> container, Integer index){ for(int i=0; i<index; i++) {

container.shiftLeft();

}

T result = container.top();

for(int i=0; i<index; i++) {

container.shiftRight();

}

return result;

4
}

You can call that static method from elsewhere in the code as MultiDS.getItem().

    10. If you have never used command line arguments in Java you can find information about them in your CS 0401 text or by Googling "Java command line argument". Note that it is required that you obtain the number of players and the number of rounds from the command line -- you

should not prompt the user to enter it once the program has started.

    11. Your program should output “Usage: java Main <# rounds> <# players between 2 and 7>” if it got the wrong number of arguments or the number of players is outside the specified range.

    12. For Javadoc comments and code style, please refer to Appendix A of the textbook.





















































5