Info2: Exercise 12: Scrabble Cheater - Basic Edition

Pre-Lab

P1. Review the rules of Scrabble, if you have never played it before.

P2. What is a permutation?

P3. What would a normalization function for different permutations of words look like? That is, “JAVA” and “VAJA” are permutations, what would a normalized permutation look like?

P4. How do you determine if two Strings are permutations of each other?

P5. For the bored: How can you generate all permutations of the characters in a String? See Back to Back SWE “How To Permute A String - Generate All Permutations Of A String” for a clear explanation of a backtracking solution. See Sedgewick 1977 (available with VPN) for theoretical details on several different solutions. What if some of the letters are the same? Hint: Look at the multinomial coefficient.

Assignment

You will implement a simple scrabble cheater that will read in words from a scrabble word list, and find all permutations for a 7-letter tile rack.

There is a lot to do, so you might want to split up the work in your group.

Use the prepared scaffold for the interfaces. It also contains some testcases. You can find it on GitHub https://github.com/htw-imi-info2/ScrabbleCheater.
Implement initFromFile in SimpleWordList that initializes the ScrabbleCheater from a given file. For now, simply store the words in a suitable Collection of the Java Collections Framework.
Implement the getNormalized and equals methods in Permutation. Two Permutation instances should be equal if one is a permutation of the other - regardless of the actual words they represent. Having a look at the provided test cases and making them run might help with the implementation.
Implement the validWordsUsingAllTiles method in SimpleWordList that returns a Set of all the Words that are permutations of a given tile rack. That is, all words of the same length of the tile rack that can be build with it and that are in the word list, thus valid scrabble words.
Use the Permutation class to make looking up the validWordsUsingAllTiles() more efficient. Hint: how often will normalize() be called a) for initialisation and b) for a lookup in your WordList?
Provide a second implementation of WordList using a HashMap as the underlying collection for storing the words. Note that you need to make sure that equals() and hashCode() work correctly on permutations in order to store Permutations at the same place in the HashMap.
Add a main method or some sort of interface to input words that should be looked up by your scrabble cheater (e.g. taking a parameter or reading in tile racks from standard in).
For the bored: Measure the time improvement introduced by the HashMap implementation. The measured time might be small, so chose an adequate unit or use a loop to execute the code often.

Lab Report

All info on the lab reports can be found on the Labs page.