Project #5 CMSC 131
Due:  April 2nd, 11:00 pm Object-Oriented Programming I
Type of Project: Closed Spring 2006


This project will give you practice in manipulating one-dimensional arrays, and designing programs that use the MVC (Model-View-Controller) design pattern.


For this project you will implement a puzzle game called Jumble. The game consists of a sequence of cells, each containing a character. The goal of the game is for a user to unscramble a word that has been selected and scrambled by your program. The game provides a set of transformations (e.g., swapping two characters) that are used by the game to scramble a word. The same set of transformations are available to the user to unscramble the word. The goal of the game is for the user to unscramble the word with the minimum number of transformations. In addition to implementing the management of these transformations, you must implement a "hint" capability whereby the cells that are close to their correct position are colored yellow.

Your task in this program is to implement the class that controls the game, that is, the code that modifies the state of the game based on user input, determines the cells' color, and detects when the word has been guessed. More details about the program are provided in the Specifications section. You may want to take a look at the Sample Run section before you read the detailed description.



Before presenting the specifications, we first describe the set of possible scrambling/unscrambling transformations. You will implement three transformations in this project:

swap(i, j):
Given two positions i and j, this transformation swaps the characters at these positions. An example is shown in the figure below.

The transformation swap(i, i) is allowed, but has no effect on the word.

move(i, j):
Given two positions i and j, this transformation moves the character at position i to position j. All the characters in between are then shifted by one position, either to the right or left, to make room for the moved character. This is illustrated in the following figure.

The transformation move(i, i) is allowed, but has no effect on the word.

multipleSwaps(i, j):
Given two positions i and j, this transformation swaps pairs of characters between i and j, from the outermost pair to the innermost pair. That is, the character at index i will be swapped with the character at index j, the character at index i+1 will be swapped with the character at index j-1, the character at index i+2 will be swapped with the character at index j-2 and so on and so forth. An example is shown in the figure below.

Note that you must consider two cases: (1) the number of characters between i and j is even; (2) the number of characters between i and j is odd. In the latter case, the middle-most character remains in place. The transformation multipleSwaps(i, i) is allowed, but has no effect on the word. Note: You are not required to write your code so that multipleSwaps calls swap.

What you must implement, in a nutshell

Using a library we will provide, you will implement a class called Jumble that will allow a user to play the puzzle game. [Edit 3/21/06: You must create the Jumble class yourself and add it to the rest of the project files.] (Among other things, the library includes a dictionary.) The Jumble class implements methods that, among other things, will allow the program to:

  1. Select a random word from a dictionary and apply some number of random transformations to the word in order to generate the initial scrambled word, which will be presented to the user.
  2. Apply a set of transformations chosen by the user to the current set of characters representing the game state.
  3. Provide a hint to the user (in the form of yellow-coloring) when a character has been placed in a position close to its position in the unscrambled word.
  4. Determine when the puzzle has been solved, that is, when the user has succeeded in unscrambling the word into its original form.
  5. Determine the number of transformations that the user needed in order to solve the puzzle. This is needed for scoring.

To make it easy (and more fun) to play we have provided a Graphical User Interface (GUI) that will allow you to apply transformations to the current set of characters representing the game state. The class PuzzleGUI provides this interface. More details about this class are provided below. (Note: In spite of the similarity of names, Graphical User Interfaces and Java interfaces are two separate concepts.)

Keep in mind that you are implementing the model component of the MVC system. You can develop this program by not using the GUI at all. Actually, the set of tests in the JUnit module tests the Jumble class without using the GUI . The game can be played without the GUI we have provided, but it will not be as much fun as input and output will be based on Dialog Boxes and/or system.out.println. If you understand the MVC model associated with this project you will realize that:

Code Distribution

Before you read these specifications, you should access the files associated with this project by checking out the project named p5. The code distribution provides you with the following:

Here is a description of each of these components.

Java Files

The Puzzle Library

The puzzleLib has the support classes you need for this project. The classes you will find in this package are:

  1. Constructor - Takes a character (char) and an integer (int) as parameters. The character represents the cell's letter and the integer the cell's color.
  2. getCharacter - Accessor that returns the cell's character.
  3. getColor - Accessor that returns an integer representing the cell's color.
  4. getColorCharacter - Accessor that returns a character representing the cell's color. 'W' represents white and , 'Y' represents yellow.
  5. toString - Returns a string with the cell's character followed by a letter representing the cell's color.

Your Assignment

Your assignment is to implement the Jumble class. (Everything else is provided.) Because we have provided the GUI you do not need to perform any input or output (e.g., using Dialog Boxes). Before you implement the Jumble class methods you should familiarize yourself with the GUI.

Interacting with the GUI

Before discussing what you need to do, we explain how the class you are expected to implement (Jumble) interacts with the GUI to play the game. The GUI is provided in the class PuzzleGUI, which we have implemented. The GUI does all the work of interacting with the user and displaying the images. It calls methods in your Jumble class to perform the actual transformations, which define the game's behavior. You implement these transformations. The relationship is shown in the figure below. (We will explain the meaning of generatePuzzle, getContents, etc. below.)

To see how the GUI operates, execute the main method of the PuzzleExample class. The PuzzleExample class defines some minimal functionality, but it does not implement a game's logic. Its purpose is to show you the interaction between GUI and a class implementing the Puzzle interface. Each method in the class prints a message, so you can see when these methods are being invoked. Your Puzzle class is basically the PuzzleExample class where each method will implement code that will support the game logic of the puzzle game you are expected to implement. Actually, you can copy the file to a file and then start your implementation using the new file. (Make sure you remove the code associated with methods once you have copied the file.)

The PuzzleGUI class relies on the PuzzleExample class to implement the game's behavior. When the user clicks on cells in the puzzle, the GUI calls the appropriate methods from the PuzzleExample class in order to perform the required processing. When you run the main method of the PuzzleExample class it will first ask for the number of characters and number of transformations. Type in two numbers, say 7 and 2. You will then see a window containing a sequence of letters. You will also see messages printed to the console indicating which methods of the PuzzleExample class have been called. We will discuss these below. Experiment by clicking on pairs of cells (also while holding the SHIFT or CTRL keys down) and observe the messages produced in the console below. Each time you click on a pair of cells the method cellsSelected is called. When called, the cellsSelected method receives the indices of the cells that have been selected, in addition to an integer value indicating whether no keys were held down (0), the Shift key was held down (1), or the Ctrl key was held down (2). This set of values will allow us to identify which kind of transformation the user wants. Note that when clicking on a pair of cells the first cell selected turns blue. This feature is implemented by the PuzzleGUI and you don't need to worry about it (it has been taken care for you).

The puzzleGUI interacts with the Jumble class in the same way it interacts with the PuzzleExample class. Different types of games can be implemented by providing different versions of classes that implement the Puzzle interface.

If you want to stop the game at any time, just close the puzzle window. Once you have finished the Jumble class implementation you will either see a message to the effect that the game has not been solved, or a message indicating you have solved the game after a particular number of attempts.

Jumble Class Implementation

The Jumble class must implement the Puzzle interface. The following are the specifications associated with this class:

Instance Variables

You may decide the type and number of instance variables you will need for this class. At a minimum, you will need to store the set of characters in the original (unscrambled) solution word as well as the characters in the (partially scrambled) current word.

Except for instance variables that are constant (static final), all instance variables in class Jumble must be nonstatic and must be explicitly initialized in the method generatePuzzle (described below). This is required for our testing software to run correctly.

Required Public Methods

Feel free to add any private methods you understand can simplify the implementation process. However, you may not add any public methods. Remember that avoiding code duplication is important and defining private methods can help you accomplish this goal.

     public String getSolution();

   cumpotre (current word)

Important notes:

  1. Those cells that are in their final position are colored white. 
  2. If there are more than one of a particular character involved in the same puzzle, you do not have to keep track of which one is which.  If the character in the current word matches the corresponding character of the solution word, color it white; otherwise, check one unit to each side in the solution word -- if you find a match, color it yellow..
  3. Keep in mind that you must do a "wrap around" check for both the first and last cell of the current puzzle. That is, if the first cell of the current word corresponds to the last cell in the solution word or the last cell in the current word corresponds to the first cell in the solution word then the cells must be colored in yellow.

The generatePuzzle Method

This method has the following signature:

The parameter numLetters is the length of the word to be randomly selected from the dictionary. The parameter numTransformations is the number of random transformations to apply to this word to create the initial scrambled word. The method Dictionary131.getRndWord(int numLetters) (described earlier) can be used to get the random word. After obtaining the word, apply the following algorithm to scramble it. (You must follow this outline, or else we cannot test your program.)

  1. Generate a random integer r in the range [0...2] (using Random131.getRandomInteger()). Depending on its value the transformation to be applied will be either swap (r=0), move (r=1), and multiple swaps (r=2), respectively.
  2. Select a random integer i in the range [0...size-1], where size is the length of the selected word to be scrambled.
  3. Select another random integer j in the range [0...size-1]. (Note that i and j may be equal. This is okay.)
  4. Apply the transformation (as determined in the first step) to the cells at positions i and j. For example, if the first three random numbers had been r=1, i=4, j=7, then you would perform move(4,7).
  5. Repeat the above steps until the requested number of transformations (numTransformations) have been performed.


Testing Using JUnit Testing

To provide you with additional confidence that your program works correctly, we have included a JUnit module called PublicTests. This module tests some of the functionality expected from the Jumble class. There are five tests:

The results for each test can be found in the code distribution files with a "pub" prefix. These tests represent the public tests you will find in the submit server.


Sample Run

Here is an example of playing the game ( with 8 as the number of letters and with 4 initial transformations. Because the words are generated randomly, your initial random word will likely be different when you play.

After starting the game and entering 8

After pressing OK and entering 4

After pressing OK

After selecting letter m

After selecting letter p (thus invoking swap(3,4))

After holding down Ctrl key while selecting letter e

Still holding down the Ctrl key while selecting letter o (thus invoking multipleSwaps(1, 5))

After releasing Ctrl key, and then holding down the Shift key while selecting letter e

Still holding down the Shift key while selecting letter r (thus invoking move(5, 7))

After releasing the Shift key and selecting r

After selecting e (thus invoking swap(6,7))

At this point the puzzle has been solved. After pressing OK the game ends.


Your grade will be computed as follows: