Homework #5 CMSC 131
Due Nov 4, 6:00 pm Object-Oriented Programming I
Type of Homework: Closed Fall 2004

(Most recent update: Mon, Nov 1 at 4:30pm. Look for red "Update:" tags.)


This homework will give you practice in manipulating one-dimensional arrays, and designing programs that use the MVC (Model-View-Controller) model of interaction.


For this homework you will implement a puzzle game called Jumble. In this game you are presented with a word whose letters have been permuted (e.g. "rotew") and the objective game is to unscramble the letters to determine the original word ("tower"). 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 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.

This homework will be graded as follows:


You will write a program that lets a user play a simple word puzzle. The puzzle consists of a sequence of cells, each with a character. The goal of the game is for a user to unscramble a word, which has been selected and scrambled by your program. The game provides a set of unscrambling transformation, which the user can select from. Here is a short summary of the tasks your program must perform.

Summary of Program Tasks

  1. The program picks a word from a dictionary. We will provide the dictionary.
  2. The program then scrambles the word using a random set of transformations, which are described below.
  3. The program displays the scrambled word and lets the user apply a sequence of transformations. The user wins the game when he/she manages to unscramble the letters, thus producing the original word. The sample run provides an example.

The user's goal is to generate the original word with a minimum number of transformation attempts. Note that your program does not need to solve the problem. It just controls the game, which the user is playing.


Before presenting the specifications, we first describe the possible scrambling/unscrambling transformations that your program will have to perform. You will implement three transformations in this homework:

swap(i, j):
This transformation is given two positions i and j and 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):
This transformation is given two positions i and j. The character at position i is moved 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.

bump(i, j):
In this transformation we successively "bump" characters from one position to another. Before giving the formal definition, let us show an example in the figure below. Let i=1 and j=3. The transformation first moves the character ('a') at position 1 to position 3. This causes the character ('m') at position 3 to be bumped to position 5. Each character proceeds in this manner, moving forward 2 positions and then bumping the character at that position. When we reach the end of the array, the process wraps around to the front of the array (as if position 0 immediately follows position 7). The process continues until a character is bumped into the original position (i).

Here is a more formal definition of bump(i, j). Let the distance j-i be called the bump distance. (Note that if j < i then the bump distance is negative, but the following description applies equally well in that case.) First the character at position i is moved by the bump distance and is put at position j. This causes the character at position j to be bumped, again by the same bump distance, to a new position. The bumping process continues in this manner. If the process ever threatens to go off one end of the array, it then wraps around to the opposite end of the array. (Imagine that the elements of the array are arranged in a big circle, like the numbers on a clock.) Note that it is possible to wrap around the array many times. (The number of times depends on the size of the array and the bump distance. Can you figure it out?) The process ends when a character is bumped into the original position i. The figure below provides another example. In this case the bump distance is negative (-3), and the process wraps around twice before terminating.

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

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. 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. Determine when the puzzle has been solved, that is, when the user has succeeded in unscrambling the word into its original form.
  4. 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.)

Code Distribution

Before you read these specifications, you should access the files associated with this homework 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 cmsc131PuzzleLib has the support classes you need for this homework. The classes you will find in this package are:

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 JOptionPane). 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 your program 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, bring up Eclipse, download the distribution, and execute the main method of the PlayJumble class. The Jumble class provided as part of your code distribution defines some minimal functionality, but it does not actually play the game. However, each method in the class prints a message, so you can see when these methods are being invoked. You must remove these print statements before submitting your homework.

The PuzzleGUI class relies on the Jumble class to implement the game's behavior. When the user clicks on cells in the puzzle, the GUI calls the appropriate methods from the Jumble class in order to perform the required processing. For example, when the user wants to swap two characters, he/she clicks on the two cells to be swapped, the GUI identifies the cells that are clicked (and changes the color) and then calls the method cellsSelected() from your Jumble class to perform the actual swap transformation on an array. The array is stored as an instance variable within the Jumble class.

When you run the main method of the PlayJumble class. On the screen 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 the word "NOTREADY". You will also see messages printed to the console indicating which methods of the Jumble 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.

The three transformations (swap, move, bump) are activated as follows. To request an transformation, the user clicks on two cells. Let these be at positions i and j. (Positions are indexed starting with 0 at the left end.) The actual operation depends on the combination of SHIFT/CTRL keys that are held down.

Recall the above descriptions of these transformations. Of course, nothing will happen until you have implemented the methods of the Jumble class, which we describe in the next section.

If you want to stop the game at any time, just close the puzzle window. You will see a message to the effect that the game has not been solved.

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. You must use two character arrays for storing these.

(Update: The following added, Sat, Oct 30 at 8:30pm.)

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

Take a look at the file Jumble.javaas you go over the description of the following 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.

The generatePuzzle Method

This method has the following signature.

The parameter maxNumLetters is the maximum 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.getRandomWord(maxNumLetters) (described earlier) can be used to get the random word. (Update: method name fixed, Fri, Oct 29 at 2:30pm.) (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 bump (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 the transformation move(4, 7).
  5. Repeat the above steps until the requested number of transformations (numTransformations) have been performed.



Sample Run

Here is an example of playing the game (PlayJumble.java) with 5 as the maximum number of letters and with 2 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 5

After pressing OK and entering 2

After pressing OK and selecting letter h

After selecting letter e (thus invoking swap(1,3))

After holding down SHIFT key while selecting letter e

Still holding down the SHIFT key while selecting letter s (thus invoking move(1, 4))

After releasing SHIFT key, and then holding down the CTRL key while selecting letter u

Still holding down the CTRL key while selecting letter e (thus invoking bump(1, 4))

After releasing the CTRL key and selecting s and o (thus invoking swap(1, 3))

After selecting e and u (thus invoking swap(2, 4))

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

Testing Using PuzzleTests

To provide you with additional confidence that your program works correctly, we have provided a special class for testing purposes, called PuzzleTests. Executing the main method of the class PuzzleTests will allow you to test some of the functionality expected from the Jumble class. There are five tests:

Each test can be selected through the appropriate menu entry. The results for each test can be found in the following files: Test1ResultsSwap.txt, Test2ResultsMove.txt, Test3ResultsBump.txt, Test4ResultsRandomPuzzle.txt, Test5ResultsJumble.txt. (Update: The file names fixed. Wed, Oct 27 at 9:00pm.)

Challenge Problem

Remember that you are not required to implement the following problem. Please visit the course web page for information regarding challenge problems. IMPORTANT: If you decide to complete the challenge problem you must provide its implementation in the file called Challenge.java. The Challenge class defines a modified Jumble class which implements the challenge problem. Make sure you don't modify the main method we have provided in the Challenge.java file.

For this challenge problem, replace the bump transformation (when two cells are clicked with the CTRL key held down) with the following new transformation.

sort(i, j):
This transformation is given two positions i and j and sorts the characters from position i to position j (inclusive). If i < j then the values are sorted in increasing order and if i > j the values are sorted in decreasing order. Note that sort(i, i) has no effect on the word.

For example, if the word was "musicality" the operation sort(1,8) would sort the characters from 'u' to 't' (namely 'u', 's', 'i', 'c', 'a', 'l', 'i', 't') in ascending order, resulting in the word "maciilstuy". On the other hand, if we started with the original word, the operation sort(3,0) would sort the first 4 characters in descending order, resulting in the new word "usmicality". (Update: The preceding example was fixed Mon, Nov 1 at 4:30pm.)


Submit your project using the submit project option associated with Eclipse. Remember to complete your time log before submitting your homework.