Bulgarian Solitaire "Live" Case Study


This case study describes the development of a solution to a Java programming problem.  This case study was not rehearsed in advance.  The documents here are the actual work products created during an onsight attempt at solving the problem.  The steps in italics describe the process to be followed.

Program Development Process

Step 1  Read the problem.  Note anything that is unclear, ambiguous, or omitted.

 The problem is called Bulgarian Solitaire, is given in Horstmann's Big Java as problem 7.12.
"In this assignment, you will model the game of Bulgarian Solitaire. The game starts with 45 cards. ( They need not be playing cards. Unmarked index cards work just as well.) Randomly divide them into some number of piles of random size. For example, you might start with piles of size 20, 5, 1, 9, and 10. In each round, you take one card from each pile, forming a new pile with these cards. For example, the sample starting configuration would be transformed into piles of size 19, 4, 8, 10, and 5. The solitaire is over when the piles have size 1, 2, 3, 4, 5, 6, 7, 8, and 9, in some order. ( It can be shown that you always end up with such a configuration.) In your program, produce a random starting configuration and print it. Then keep applying the solitaire step and print the result. Stop when the solitaire final configuration is reached."

Questions:  
1. "Unmarked index cards" ... so, no ranks or suits at all?  What kind of solitaire is this?
2. When I try the example,
20  5  1  9 10
I get 19  4  0  8  9, not 19, 4, 8, 10, 5.  Am I misunderstanding the rules?
3. "you always end up with such a configuration"   Who is "you"?  Me the reader?  The player of the game?  Does "always end up with" mean every game ends this way?  
Does that mean every game concludes with a winning configuration?
Assumptions:
After re-reading the problem several times, I conclude it's a very boring game where the user has no decisions to make at all, and every game is winnable.   Thus, in the simulation, there is no user input required.
I assume that piles of size zero get eliminated.
I think the problem has a typographical error, the 10 should be a 9.

 
Step 2  Analyze the problem.  Write a description of what is required.  
1. What functions must be performed? (Include any error handling.)
2. What are the input and output data to the program?
3. How does the user interface operate (if appropriate)?
Note any assumptions made.

Functions
1. Generate a random board.
2. Play a round, producing a new board.
3. Determine if the game is over
   3a.  Does the board have the proper number of piles?
   3b.  Do the piles have the correct number of cards?
4. Print the board.
Then, to make it more interesting, I'm adding an additional requirement
5. Count the number of rounds and display it at the end of the game.

Inputs
There is no external data input to the program.

Outputs
Display of the board after each round.  
Display the number of rounds.  

User Interface
The board is displayed as a sequence of numbers where each number
shows the number of cards in that pile.  There's a blank between each number.  
All numbers are on one line.
E.g.,
20 5 1 9 10

The game over message text is: "Game over after __ rounds."   

Step 3  Create Test Data

Since there is no input data, there's no obvious way to provide test data to the program.  In the worst case,  the output of the program would have to be manually verified by following each round and verifying the piles are calculated correctly.  This could be very time-consuming, as a game might easily last 50 or 60 rounds.

An alternative would be to modify the program so that it can accept an initial board configuration.   Then the tester can provide a starting configuration for which the expected output can be determined in advance.  So I'll add a new functional requirement
6. Accept an initial configuration on the command line.
E.g.,
  java Solitaire 20 5 1 9 10
Assume that only integers are entered, separated by blanks.

Now I can create test cases:
Test Case 1 - shortest possible game
Input                
2 3 4 5 6 7 8 10
Output
1 2 3 4 5 6 7 9 8
Game over after 1 rounds.

Test Case 2  - shortest possible game reversed
Input                
10 8 7 6 5 4 3 2
Output
9 7 6 5 4 3 2 1 8
Game over after 1 rounds.

Test Case 3 - shortest possible game scrambled
Input         
3 8 4 7 5 6 2 10
Output
2 7 3 6 4 5 1 9 8
Game over after 1 rounds.

Test Case 4 - rounds greater than 1
Input         
2 2 2 4 5 6 7 8 9
Output
1 1 1 3 4 5 6 7 8 9
2 3 4 5 6 7 8 10
1 2 3 4 5 6 7 9 8
1 2 3 4 5 6 7 8 9
Game over after 3 rounds.

Test Case 5 - start with a single pile
Input
45
Output
44 1
43 2
42 1 2
41 1 3
40 2 3
39 1 2 3
38 1 2 4
37 1 3 4
36 2 3 4
35 1 2 3 4
....
10 2 3 4 5 6 7 8
9 1 2 3 4 5 6 7 8
Game over after 36 rounds

Test Case 6: Run the game several times and verify it starts with a different random configuration each time.

Step 4  Create a design of the solution

4a Identify the classes.
Create a list of candidate classes from the nouns in the functional requirements:
Game
Board
Pile
Card
Round

I decide I can omit card, because it's just a placeholder.
 
A pile is really just a positive integer representing the number of cards it contains.  We don't actually need any cards.

A board is a collection of piles.  

The game is the simulation itself.

A round is just a counter.

4b Identify the attributes for each class.
  class Board
     The primary data being encapsulated by Board is the collection of piles.  Since each pile is just an integer, we don't need a Pile class.
     private Collection<Integer>;

  class Game
     The game has a Board and a counter for rounds.
     private Board board;
     private int rounds;

4c Identify the responsibilities of each class.
(Usually these are derived from the functional requirements).
  1. The board can generate a random initial configuration.
  2. The board can setup a desired preset initial configuration.
  3. The board can perform the "solitaire step" to determine the next configuration.  
  4. The board knows if it's a winning configuration or not.
  5. The board can return a printable representation of itself.
  1. The Game initializes the board.
  2. The Game performs rounds until the game is over.

4d Determine the relationships between each class:  Inheritance, Aggregation, or Dependency
   Game aggregates Board

4e Draw the class diagram
   Game   <>-----   Board

4f Design the public interface to each class.  This is the compilable class skeleton.

Completed class skeletons.

Step 5 Write JUnit tests for each class.   Add minimal implementation for each class so the tests will run and fail.
BoardTest.java
 GameTest.java
Step 6 Write the algorithm for each method (in pseudocode)

Completed pseudocode.

Step 7 Desk check the algorithms with a hand trace (using the test cases for input data)

Completed Desk Check.

Step 8 Translate the algorithms into program statements.
8a. Start with lowest level classes.  
8b. Run the unit tests on each class as it is completed.
8c. Correct any defects until the unit tests all pass.
See finished implementation below.

Step 9 Run the Test Cases. Correct any defects until the test cases all pass.

View Compile and Test Log.

Completed source code: BulgarianSolitaire.zip
Download jar: Solitaire.jar