Updates

• Have questions ready for Monday!
• Submit code files in a zip file with a text document of comments to: ns48@cornell.edu by Friday, 5:00 PM.
• Put you name in the text file.
• Do not include class files in the zip file!
  

Due date
Friday, 4 February 2000 at 5:00pm

Advice

• Start today. This is a long assignment. Don't leave it until the witching hour on Thursday night.
• Even if we have not covered the Java language details, make sure you understand what the assignment asks of you at an algorithmic level.
• Make use of office hours and email. Ask for help, clarification.
• Check the web site and newsgroup frequently for updates
• Don't copy. The consequences are severe.
• Use the test driver (a1test.java) to make sure you have the right method definitions in your solution.

Overall Goal of Assignments
Over the course of cs202 we will be constructing various parts of a game you are all familiar with. The entire implementation will be in Java and hence the name, Javlle. The assignments have been constructed to teach you various concepts and techniques as you go along. You will build some parts and the complement will be provided. Each assignment builds on the previous ones, and in the end we will have a functioning prototype. Of course it is not going to be fully featured, as I am trying to cut down on your workload, while still getting across the fundamental Java concepts. You are encouraged to extend the basic design requirements as you please; it will be a great learning experience.

Part A: Classes, objects and inheritance
As with any program of substantial size, it is important to undertake the implementation in clearly defined steps. The first thing we wish to do is define some data structures for our game. Since we are taking an object-oriented view of programming, we will also define the operations on that data.

A basic object in Javlle is the Piece. Pieces have various properties, such as the letter they represent, their value, and their multiplicity count. There are also special types of pieces called WildcardPiece, which can represent any letter, but have a zero value.

Your task is to define a Piece class with the following static (class) interface methods:

• getValue: taking a character, returning the integer letter value
• getCount: taking a character, returning the integer letter count

• <constructor>: create a piece object, representing given character
• getLetter: return letter on piece
• getValue: return integer value of piece
• getCount: return integer count of piece

A WildcardPiece must perform the piece operations correctly, and the following additional operations:

• <constructor>: create a wildcard piece (not representing any letter)
• setLetter: set this piece to represent some letter

You should use internal data structures, such as arrays, to store the letter value and count tables provided. You may specify some constant to be used to represent a wildcard that has not been assigned a letter.

Very important:
Throughout this design process, you should think about all the modifiers you have learned (static, public, protected, private, final, abstract) and use them accordingly. Also take care to ensure valid parameters; if a constructor or method is called with invalid parameters throw an appropriate exception. The entire point of this exercise to teach these concepts; make sure you understand them. This is a relatively straight forward problem, so make sure your resulting code is clean and professional.

Part B: Enumeration interface, Arrays
If you think about it, this entire game is about making words out of permutations of letters. So a good start at implementing a computer player is to devise an algorithm to generate permutations. Instead of using real letters, we can permute the numbers representing positions, and use these numbers later to generate permuted words.

For example, if we take the word "cornell", and the permutation vector <2,6,1,0,5,3,4>, we produce "rloclne". We can then check this word against the valid dictionary words. A permutation vector tells us the new order of the letter based on their previous positions.

It would be useful to generate all the permutations of all lengths of words up to some given upper limit. Say, for example, we take a limit of 3. That means we wish to generate all the permutations of {0,1,2}, namely: <0,1,2>; <0,2,1>; <1,0,2>; <1,2,0>; <2,0,1>; <2,1,0>. Notice, that they are in ascending lexicographic order. This is important, because it can save a lot of time during dictionary lookup.

Your task is to create an object Permute, which generates all the permutations in order. We might as well expose methods of the Enumeration interface, because it fits our task so well. The constructor should take an integer representing the permutation vector length. You should then implement the Enumeration interface (refer to Java documentation) methods. Each permutation should be represented as an integer array. You can configure the internals of your object any way you like, as long as you produce the complete and correct permutation sequence. A good way to approach this is to create a private method that when given a permutation array, returns the next in sequence, or throws an exception if this is the last.

Because this permutation generation can get a little messy and takes some time, we should pre-generate a table once and use it on each turn. This one table, containing the permutation vectors of our set, is an array of arrays. Create a static method called createTable, which takes an integer, and produces a table containing all the permutations of that vector {0,1,..,n-1}, in order.

Of course, not all words are the same length, and we need not use all our letters. We would really like to produce permutations of all subsets. But that's really easy... Once we have the permutations of the entire set we can split each permutation vector into a left and a right components. The left component will be the subset we want, and the right component is the subset we throw away (or the letters we don't use). The left component of the table represents all the permutations we want! There just may be some duplicates to eliminate. For example, projecting the permutation vectors above to length 2 produces: <0,1>; <0,2>; <1,0>; <1,2>; <2,0>; <2,1>. Projecting them to length 1 produces: <0>; <0>; <1>; <1>; <2>; <2>. After eliminating duplicates we get: <0>; <1>; <2>. Instead of "eliminating" duplicates we can just create indices into our table. For vectors of length 3, we need to look at all the positions. Similarly for vectors of length 2. For vectors of length 1, we need only look at positions 0, 2 and 4. Your task is to write a method createIndices, that generates an array of indices into our table, another array of arrays! This time the sub-arrays are of different lengths. Note that the permuation table is highly ordered so we don't even have to look at it to generate the indices. The indices only depend on the size of our original vector. Play with some examples until you figure out the pattern. Hint: Use factorials on the values of n (size of original set we are permuting) and r (size of subsets we are choosing), to determine the size of the table and the skip factor for each of the indices.

To assist you I have provide a short explanation of some permutation generation algoritms.

Testing and documentation
Some parts of your assignment will be tested electronically with a driver program similar to the one provided. Ensure that your code works with it.

Documentation is not required for this assignment. However, ALL classes, methods and fields, must have comments (JavaDoc style) explaining them. You should split the definitions in your class into static and non-static, and keep your field declarations together within these sections. (For some types of classes it makes more sense to split among private and public declarations).

Submission
Before the assignment deadline you are expected to submit three files:

• Piece.java
• WildcardPiece.java
• Permute.java

Submit code files in a zip file with a text document of comments to: ns48@cornell.edu by Friday, 5:00 PM.