Info2 SS2014

Website of Prof. Dr. Barne Kleinen, Professor for Media Informatics (Bachelor/Master) at HTW Berlin
HTW Berlin
Programming and Web Technology @ IMI

Info2: Exercise 12: Scrabble Cheater - Basic Edition

     <prev next>

Scrabble Foto by Mags_cat

Pre-Lab

  1. Review the rules of Scrabble, if you have never played it before.
  2. What was a permutation?
  3. What would a normalization function for different permutations of characters words look like? That is, “JAVA” and “VAJA” are permutations, what would a normalized permutation look like?
  4. How do you determine if two strings are permutations of each other?
  5. How can you generate all permutations of the characters in a String? What if some of the letters are the same. Hint: Look at the binomial coefficient.
  6. how many different 2,3,4,5 and 6-letter subsets are there for each 7-letters?
  7. Can you find lists of valid words for Scrabble in English online? Are there perhaps any sorted by number of letters in the word? Or maybe one file for each word size? Note down the URLs!

Assignment

This week 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. Next week you will extend this cheater by also searching for subsets (that is, shorter words) as well as optimizing the underlying data structure for performance.

There is a lot to do, so you might want to split up the work in your group. I’ve prepared a scaffold for the interfaces along with some testcases. You can find them on github https://github.com/htw-imi-info2/ScrabbleCheater

  1. 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.
  2. Implement the getNormalized() and equals() methods in Permutation. Two Permutations 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.
  3. To make the tests for Permutation work, also implement the methods that create Permutations in PermutationUtilities
  4. now implement the permutations() method in SimpleWordList that returns a Set of all the Words that are permutations of a given tile rack.
  5. How can you use the Permutation class to make looking up the permutations more efficient? (Hint: how often will normalize() be called a) for initialisation and b) for a lookup in your WordList?)
  6. In preparation of the final ScrabbleCheater, implement the method “subsets” in PermutationUtilities which should determine all of the Strings that are substrings in the sense that they only contain letters from the given String, with multiples only up to the number of multiples available. The order of the letters is irrelevant, so this is a bag. For example with 4 letters “JAVA” this would be {“AAJV”, “AJV”, “AAJ”, “AAV”, “AA”, “AJ”, “AV”, “JV”}.
  7. you might want to 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)

Lab Report / What to turn in

Your report is due by 23:00 am the night before your next lab. Submit a Report in PDF Format and the Source Code as Zipped file.

As in Informatics 1, I am more interested in process than in product, although we are now getting more interested in products as well. Your report should include any collaborators on top of the first page, summarize what you learned, and note the time you invested in this exercise. Both of you need to upload the same report in PDF format to Moodle before the deadline.

Special Questions for your report

How many lines of code did you write for each class? Record this statistic in your report.