Homework 10: War! A Card Game

Goals

Learn how to use classes to implement linked lists and other abstract data types in Java
Learn about building specialized data structures in Java

Introduction

In this project, we will write a program to play a simple card game known as War. In War, a standard deck of 52 playing cards is shuffled and divided evenly among two players (the user and the computer). Players simultaneously turn over the top card of their respective decks, and the player with the high value card takes both cards, adding them to the bottom of their deck. In the case of a tie (the two cards have equal value), there is a war where players each place three cards face down and then one card face up; the player with the higher value takes all (ten) cards. In the case of another tie, this process repeats until there is a winner. For added complexity, a player may choose to shuffle their deck of cards before each battle. The game continues until one player is out of cards. For more details, see War.

In playing the game, there are several piles of cards: the two players' decks, and the piles of cards in the "battle" by each player. Cards are continually moved between these different piles. Since the cards in the pile have a specific order, we will use a List to represent these card piles.

In this assignment, you will implement two variations of the list Abstract Data Type (ADT):

a linked list, exactly as we discussed in class.
a new data structure known as a deck that is based on a linked list. Essentially, the deck is a queue of cards that can be shuffled.

You will also implement a WarGame class that runs the interactive War game.

We have already provided you with a skeleton for the LinkedList class, which you can download here:

LinkedList.java

Additionally, you will also need to download the following files for this assignment:

Be sure to compile all of the .java files you downloaded.

The Card object represents a single playing card, which has both a rank and suit. Aces will be considered 'high'. The Card object uses the following API:



public class Card
----------------------------------------------------------------------------------------------------------
        Card(int rank, int suit)  // constructor
int     compareRank(Card c)       // returns a negative number if this object is lower in rank than c,
                                  //   0 if the cards are equal rank, and a positive number if this object
                                  //   is higher in rank than c. Aces are considered 'high'.
boolean equals(Card c)            // returns true if the cards are the same, false otherwise
int     getRank()                 // returns the rank of the card: 2, 3, ..., 10, JACK, QUEEN, KING, ACE
int     getSuit()                 // returns the suit of the card, either CLUBS, DIAMONDS, HEARTS, SPADES
String  toString()                // returns a string representation of the card
----------------------------------------------------------------------------------------------------------
static final int CLUBS, DIAMONDS, HEARTS, SPADES
static final int JACK, QUEEN, KING, ACE

Note that the Card object provides getters for the rank and suit, which cannot be changed once they are initialized by the constructor. It also provides a set of static final constants to represent face cards and the suits.

Here is a simple example of how to use the Card object:



Card c1 = new Card(Card.ACE, Card.SPADES); // creates the ace of spades
Card c2 = new Card(10, Card.DIAMONDS);     // creates the 10 of diamonds
System.out.println(c1.compareRank(c2));    // prints 1 because Ace of spades > 10 diamonds

The Card class is complete as given -- you should not modify it in completing the assignment.

You should start by implementing the LinkedList class, which should represent a singly linked list as discussed in class. In this case, it will be a list of Card objects. To get you started, we've provided a skeleton LinkedList.java.

The List Interface



public Interface List
-----------------------------------------------------------------------------------------
boolean add(Card x)               // add the object x to the end of the list
boolean add(int index, Card x)    // add the object x at the specified index
int     size()                    // return the number of elements in this list
Card    get(int index)            // return the element at the specified index
Card    set(int index, Card x)    // replace the object at the specified index,
                                  //     returning the replaced object
Card    remove(int index)         // remove the object at the specified index
                                  //     and return it
boolean isEmpty()                 // test whether this list has no elements
boolean contains(Card element)    // test whether the list contains the given element
int     indexOf(Card element)     // return the first index of the specified element
                                  //     or -1 if it is not found in the list

Your LinkedList class must implement the provided List interface (List.java) exactly as it is given. You are not permitted to modify List.java. In Java, an interface is a special type of construct that defines a public API. Essentially it defines a set of public methods that a class which implements that interface must have, but it doesn't provide any implementation.

For example, a TV interface might specify methods: togglePower(), volumeUp(), volumeDown(), and setChannel(int n). Then, any class like PanasonicTelevision or SamsungTelevision that implements this interface must provide these public methods.

We have provided the file List.java that specifies the (minimal) set of public methods that your LinkedList class must contain. In order to have Java enforce this automatically, the LinkedList class must be defined as follows:



public class LinkedList implements List {
    ...
}

The implements keyword in Java allows us to specify the name of an interface that the class must use, in this case, List. The standard LinkedList provides a number of other methods that you are not required to implement in this assignment. For a full list of these methods for a standard LinkedList, you can refer to the javadocs: http://docs.oracle.com/javase/6/docs/api/java/util/LinkedList.html.

Implementing LinkedList

You must complete the provided LinkedList.java skeleton. You must also implement the inner class: Node. (Hint: Your node will need two fields: a next reference and a Card data element). Skeleton methods and explanations for LinkedList are provided in the file.

Notes:

Review the three *LinkedQueueOfDouble.java examples posted on the syllabus webpage. You are welcome to use sentinel nodes or not, and to use recursion or not in your own linked list methods.
The add() method is overloaded in the List. One version, add(element), adds an element to the end of the list and always returns true. The other version, add(index, element), adds an element to a specific index of the list.
- Although it might seem odd to have add(element) always return true, this choice makes the List interface suitable for different types of lists. For example, it would also work for implementing a UniqueList where duplicate entries are not allowed. In the UniqueList, add(element)would not always return true, but in our case, it does.
Several methods, such as get(index), take in an index and return an object. In situations where the index is invalid, it doesn't make sense for the method to signify this by returning null, since null is a valid value for an object (and could certainly be contained in the list). Instead, your implementation should throw an IllegalArgumentException (with an appropriately detailed message) when index is invalid.
add(index, element) should work correctly if 0 <= index <= size(). For example, this would allow you to call add(0, new Card(Card.ACE, Card.SPADES)) on an empty list and have it insert the ace of spaces as the new head (and tail) element.
In contrast to the above note, a node must already exist at the specified index for set(index, element) to work. Therefore, set(index, element) can't be used to add new nodes to a list.
Your War Game program may not use all of the methods in the List interface, but your LinkedList class must still implement them. The reason for this is that we're writing a general LinkedList of cards that can be used in any program; those other programs may use LinkedList methods that are not necessary to write WarGame.

Hint: To get started implementing the LinkedList, start by implementing the Node inner class, the constructor, add(), and get(). Then, use the unit testing code described below to ensure that you can add items and print out the list. Once these methods are working, move on to implement the others.

Test your LinkedList implementation before continuing to the next part of the assignment. Copy the following code into the main function of LinkedList to test add() and get().



LinkedList l = new LinkedList();
l.add(new Card(Card.ACE, Card.SPADES));
l.add(new Card(2, Card.DIAMONDS));
l.add(new Card(3, Card.HEARTS));
l.add(new Card(4, Card.CLUBS));

for (int i = 3; i >= 0; i--) {
    System.out.println(l.get(i));
}

You should see the following output when you run LinkedList.



4 of clubs
3 of hearts
2 of diamonds
ace of spades

Add additional code to your main method to test the other methods of LinkedList. If you do not have tests for your LinkedList implementation, we cannot guarantee we can help you on later parts of the assignment.
The submission script runs extensive testing on your LinkedList implementation, so you should also try submitting your LinkedList.java file before moving on to the next part of this assignment. You can always re-submit it later, and the submission script testing may prove very useful for helping to identify problems in your LinkedList implementation. Note that the online submission testing is not a substitute for doing your own unit testing in main(); the online tests only identify that you have a problem in a particular method, but do not help you debug that problem like your unit tests will.

Once you've completely finished and tested your LinkedList class, move on to your Deck class.

The Deck object will represent complete or partial decks of cards. The deck will operate like a queue, allowing you to remove cards from the top of the deck and add cards to the bottom of the deck. It will also allow you to shuffle the cards in the deck, randomizing their order.

Building the Deck from LinkedList
While we could completely re-implement this class from scratch, the best way is to build the Deck off of LinkedList. The Deck class should have a LinkedList of cards as a private field. The various methods for the Deck class will then call the corresponding methods on the private LinkedList field to implement the functionality.

Hint: your Deck class should be much shorter than your LinkedList class. By building Deck off of LinkedList, you gain much of the functionality you need with minimal effort.

Implementing Deck
Your Deck class must conform to the following API:



public class Deck
--------------------------------------------------------------------------------------------------------------------------
         Deck()                   // creates an empty deck
    void add(Card x)              // add the object x to the bottom of the deck
    Card draw()                   // remove the object at the top of the deck, returning it.
                                  //     if the deck is empty, returns null
    void fill()                   // replaces all current cards in deck with 52 playing cards to make it a standard deck
boolean isEmpty()                 // test whether this deck is empty
   void shuffle()                 // randomize the order of the cards in the deck
    int size()                    // returns the number of cards in the deck

Unit Testing Deck (Except shuffle())

To test your Deck, copy the following code into your main method:



    Deck deck = new Deck();
    deck.fill();
    deck.add(new Card(Card.ACE, Card.SPADES)); // add a duplicate ace of spades as the last card
    while(!deck.isEmpty()) {            
       System.out.println(deck.draw());
    }

When run, this should output all of the cards in the deck, with the last card being a duplicate ace of spades.

Write a few other tests in Deck.main() to make certain that your Deck class works.

Implementing shuffle(). Shuffling a deck of cards works very much like selection sort. However instead of picking the smallest remaining card to swap into position, you should pick a random card. There is example code for shuffling an array in Section 1.4 of the textbook (and booksite).

Since you are shuffling a linked list, not an array, you can simply move the cards into position; there is no need to swap. Moreover, you can always move cards to the very front (or very back) of the array, rather than to position i as the array version does.

Your shuffle() implementation must be entirely linked list-based. You may not use arrays.

Testing shuffle(). Add a call to shuffle() immediately after the call to fill() in the testing code above. Your deck should now print in random order, with an extra ace of spades at the end. You should get a different random order each time you run your unit test.

Your WarGame.java program should simulate a game of War, as described in the Introduction. It should not take in any command line arguments. Each round of play, the user will have the option of pressing the 'Enter' key to play a card against the computer or the 'S' (or 's') key to shuffle the deck. The game is over when one player runs out of cards. If there is a war, and one player has fewer than four remaining cards, the other player wins.

You can read input from the user via StdDraw.nextKeyTyped().

Here is an example of how your WarGame program should operate. You may enhance the text of the program as you like, but the interaction (keys the user can press and their effect) must be the same as in this example.



> java WarGame
It's a war of cards!
Deck sizes: 26 (yours) vs. 26 (computer's)

Press 'ENTER' to fight another battle or 'S' to shuffle your deck!    [The user presses ENTER]
You drew a jack of diamonds
The computer drew a 2 of diamonds
You won 2 cards!  Deck sizes: 27 (yours) vs. 25 (computer's)

Press 'ENTER' to fight another battle or 'S' to shuffle your deck!    [The user presses ENTER]
You drew a 6 of spades
The computer drew a ace of spades
The computer won 2 cards!  Deck sizes: 26 (yours) vs. 26 (computer's)

Press 'ENTER' to fight another battle or 'S' to shuffle your deck!    [The user presses ENTER]
You drew a 10 of hearts
The computer drew a 2 of hearts
You won 2 cards!  Deck sizes: 27 (yours) vs. 25 (computer's)

Press 'ENTER' to fight another battle or 'S' to shuffle your deck!    [The user presses S]
Your deck has been shuffled

Press 'ENTER' to fight another battle or 'S' to shuffle your deck!    [The user presses ENTER]
You drew a 6 of clubs
The computer drew a 8 of diamonds
The computer won 2 cards!  Deck sizes: 26 (yours) vs. 26 (computer's)

Press 'ENTER' to fight another battle or 'S' to shuffle your deck!    [The user presses ENTER]
You drew a 4 of clubs
The computer drew a 4 of diamonds
It's a tie! Battle Again!
You and the computer each lay down 3 cards.
You drew a 9 of diamonds
The computer drew a king of clubs
The computer won 10 cards!  Deck sizes: 21 (yours) vs. 31 (computer's)

Press 'ENTER' to fight another battle or 'S' to shuffle your deck!    [The user presses ENTER]
. . .

You won the war!!                                                     [The program terminates]

Extra Credit 1: Animating the game

Write a program, AnimatedWarGame.java that plays war and draws and animates the cards using StdDraw. Submit your code and any images in your extra.zip file. You should be able to find card images you like on the internet. Here is a link to two sets of card images, but you can find many others. Make sure to credit the source of your images in your readme and in a comment in your .java file.

Extra Credit 2: Java Generics

The LinkedList class we wrote above can contain only Card objects; however, it is often useful to implement data structures in a more generic way such that they can hold any type of data. Java provides Generics specifically for this purpose.

For extra credit, modify your LinkedList class to be based upon the interface GenericList.java instead of List.java. The methods in GenericList are exactly the same as in List, but they are based on a generic type T that is specified when the LinkedList is declared and initialized. This will enable your LinkedList to contain any type of object, not just Card objects. You will likely need to modify your other classes as well to enable them to use the generic form of the LinkedList.

If you do the extra credit, you will submit two versions of the assignment: the original (non-generic) version of all files as normal, and an extra.zip file containing new versions of all three .java files (LinkedList.java, Deck.java, WarGame.java) modified to work with the generic LinkedList. Even if one or more of these files are unchanged from your non-generic version, you should still include it in extra.zip.

Submit LinkedList.java, Deck.java, WarGame.java, and a completed readme_war.txt.

Extra credit: submit a zip file named extra.zip that contains a complete version of your program (all .java files) based on Java generics where LinkedList is based on the GenericList.java interface.