0. Introduction. Perditio Tempus (pronounced per-DISH-ee-oh TEM-pus) is a solitaire game played with a deck of cards. Its name means a waste of time in Latin. In this project, you will write a Java program that plays Perditio Tempus. Despite the name, this program may still be interesting because it demonstrates some things about how stacks work. Also, if you have a program that plays Perditio Tempus, then you need not waste time playing it yourself.

1. Theory. A standard deck has 52 cards. Each card has one of four suits, called spade, club, heart, and diamond, but suits are not used in Perditio Tempus. Each card also has one of thirteen ranks, called ace, two, three, four, five, six, seven, eight, nine, ten, jack, queen, and king. These ranks correspond to the numbers 1 through 13, respectively.

Perditio Tempus is played in the following way. You shuffle the deck, and the deal the cards face-down into a row of thirteen piles, with four cards in each pile. The row of piles is called the tableau (pronounced tab-LOW). The piles are numbered from 1 to 13, so that each pile corresponds to a card rank. Play now proceeds according to the following rules.

Set the variable p to 1.

If pile number p is empty, then go to step 4.

Turn over the card from the top of pile number p. Reset p to the number given by the cards rank. Throw the card away. Go to step 2.

If all piles are empty, then you have won. If some pile is not empty, then you have lost.

You can use arrays and stacks to play Perditio Tempus. The shuffled deck of cards, before it has been dealt into the tableau, can be represented as an array stack. The tableau itself can be represented as an array of piles. Each pile in the array can be represented as a linked stack.

2. Example. Here is an example game of Perditio Tempus, shown step by step. This game was played automatically by a version of the program you are asked to write for this assignment. It assumes that the deck has been shuffled and dealt to form the tableau.

Got five from pile 1.

Got queen from pile 5.

Got six from pile 12.

Got two from pile 6.

Got two from pile 2.

Got six from pile 2.

Got six from pile 6.

Got nine from pile 6.

Got four from pile 9.

Got six from pile 4.

Got three from pile 6.

Got nine from pile 3.

Got seven from pile 9.

Got ten from pile 7.

Got jack from pile 10.

Got five from pile 11.

Got king from pile 5.

Got ace from pile 13.

Got queen from pile 1.

Got eight from pile 12.

Got seven from pile 8.

Got three from pile 7.

Got nine from pile 3.

Got two from pile 9.

Got king from pile 2.

Got ten from pile 13.

Got jack from pile 10.

Got four from pile 11.

Got three from pile 4.

Got queen from pile 3.

Got jack from pile 12.

Got king from pile 11.

Got jack from pile 13.

Got four from pile 11.

Got five from pile 4.

Got three from pile 5.

Got two from pile 3.

Got seven from pile 2.

Got four from pile 7.

Got eight from pile 4.

Got eight from pile 8.

Got nine from pile 8.

Got king from pile 9.

Got queen from pile 13.

Got ace from pile 12.

Got ten from pile 1.

Got eight from pile 10.

Got seven from pile 8.

Got ten from pile 7.

Got five from pile 10.

Got ace from pile 5.

Got ace from pile 1.

You won! The game was won this time. However, here is another game of Perditio Tempus, played by the same program, which was lost. This is because pile 1 became empty, but there were still cards left in other piles.

Got jack from pile 1.

Got jack from pile 11.

Got three from pile 11.

Got six from pile 3.

Got two from pile 6.

Got ace from pile 2.

Got nine from pile 1.

Got king from pile 9.

Got two from pile 13.

Got king from pile 2.

Got ace from pile 13.

Got three from pile 1.

Got four from pile 3.

Got nine from pile 4.

Got four from pile 9.

Got four from pile 4.

Got king from pile 4.

Got eight from pile 13.

Got three from pile 8.

Got ten from pile 3.

Got queen from pile 10.

Got jack from pile 12.

Got four from pile 11.

Got five from pile 4.

Got seven from pile 5.

Got two from pile 7.

Got queen from pile 2.

Got ace from pile 12.

Got five from pile 1.

Got six from pile 5.

Got king from pile 6.

Got seven from pile 13.

Got queen from pile 7.

Got ten from pile 12.

Got nine from pile 10.

Got six from pile 9.

Got five from pile 6.

Got eight from pile 5.

Got ace from pile 8.

Pile 1 is empty. You lost!

Your program is very unlikely to produce output exactly like either of these example games. It will depend on how Java chooses random numbers to shuffle the deck.

3. Implementation.

Your program will involve Java classes called Random, Card, Deck, Pile, Tableau, and Perditio. Here are brief descriptions of all these classes.

The class Random. The Java class library provides a class called Random that implements a random number generator. You will use it to help shuffle the deck. To use Random, you must put the following line at the start of your program.

import java.util.Random;

Note that java and util are in lower case, Random begins with an upper case letter, and the line ends with a semicolon. The import statement obtains something from the Java library. The library is divided into packages and subpackages. The package java contains things that are generally useful when writing Java programs. Its subpackage util contains various utilities, one of which is Random.

You need only Randoms constructor and its method nextInt. The constructor call new Random() returns a new instance of the class Random. If r is an instance of Random, then r.nextInt() returns a randomly generated int. It may be negative, and it may have a large absolute value.

For this program, you will need small positive random ints. You can get these by using the Java expression Math.abs(r.nextInt()) % m, where m returns a positive int greater than 0. The expression will return a random int greater than equal to 0, but less than m.

The class Card. Each instance of the class Card represents a playing card. Source code for this class is available on Moodle. To make your program easier to grade, you must use this source code; you must not modify or extend Card in any way. Here is a short description of Cards public methods, and what they do.

public Card(int rank)

Constructor. Make a new instance of Card with a given rank, which must be between 1 and 13.

public int getRank()

Return the rank of this Card.

public String toString()

Return a String that describes this Card. It must be used only for printing. For example, it might return "ace", "two", "queen", "king", etc.

Note that Cards are immutable objects, so no part of them can be changed after they are created by their constructor.

The class Deck. An instance of the class Deck represents a deck of Cards. You must write Deck yourself. It must have the following methods, and they must work as described here.

public Deck() (5 points.)

Constructor. Make an array containing 52 different Cards. You must use one or more loops: you will receive no points if you just write 52 assignment statements. The order of Cards within the array does not matter.

public Card deal() (5 points.)

Return the next Card from the array made by the constructor. You need not pick a Card at random, because the Cards in the array will already be shuffled into random order by the time you call deal. Throw an IllegalStateException if no Cards remain to be dealt from the array. This method must work in O(1) time.

public void shuffle() (10 points.)

Shuffle the deck of Cards that is represented by the array you made in the constructor. The easiest way is the Durstenfeld-Fisher-Yates algorithm, named after its inventors. It exchanges randomly chosen pairs of array elements, and works in O(n) time for an array of size n. You must use the following pseudocode for this algorithm.

Do steps 2 and 3 for integer values of i, starting from the length of the array minus 1, and ending with 1.

Let j be a random integer between 0 and i, inclusive.

Exchange the array elements at indexes i and j.

If shuffle is called after any Cards have been dealt (by the method deal), then it must throw an IllegalStateException. You are not allowed to shuffle the deck after dealing has started.

To implement Deck, you can use ideas from the array stack class that was discussed in the lectures.

The class Pile. Each instance of the class Pile represents a pile of Cards. You must write Pile yourself. It must have the following nested classes and methods, which must work as described here.

private class Layer (5 points.)

An instance of this class represents a layer in the Pile. It must have two slots. One must be called card, and it must point to an instance of the class Card. The other must be called next, and it must point to the next Layer in this Pile. The class Layer must also have a constructor that takes two arguments, called card and next, which determine the values of the two slots.

public Pile() (2 points.)

Constructor. Initialize a new empty Pile of Cards.

public void add(Card card) (3 points.)

Add card on top of this Pile.

public Card turn() (3 points.)

Turn over a Card from the top of this Pile. Return the Card. Throw an IllegalStateException if there are no cards in the Pile.

public boolean isEmpty() (2 points.)

Test if this Pile has no Cards left in it.

To implement Pile, you can use ideas from the linked stack class that was discussed in the lectures.

The class Tableau. Each instance of the class Tableau represents thirteen Piles of Cards, as described previously. You must write Tableau yourself. It must have the following methods, which must work as described here.

public Tableau() (5 points.)

Constructor. Make an array with thirteen empty Piles in it (see below). Also make a new instance of Deck. Shuffle the Deck. Deal four cards from the shuffled Deck into each Pile.

private boolean hasWon() (5 points.)

Test if all thirteen Piles are empty.

public void play() (10 points.)

Play a game of Perditio Tempus. Each time you get a Card from a Pile, write: Got c from pile p. where c is the name of the Card and p is the number of the Pile. At the end of the game, if the program won, then write: You won!

If the program lost, then write: Pile p is empty. You lost! where p is the number of the empty Pile that you tried to get a card from. See the examples for details.

In Java, array indexes are numbered starting from 0, but in Perditio Tempus, piles are numbered starting from 1. The easiest way to handle this is to make an array with indexes 0 through 13, and then never use index 0.

The class Perditio. (0 points.) This class must contain only the main method. It starts the program running. You must write Perditio yourself.