A console-based program that finds all possible words that can be made from a rack of Scrabble tile
Date
October 28, 2022
My Role
Developer
A console-based program that finds all possible words that can be made from a rack of Scrabble tile
The game of scrabble can easily get difficult especially when you can't think of any words. Here comes Descrambler, which is a console based program that help users find all list of possible words that can be made from a rack of scrabble tiles. For example, if the rack has the letters C M A L. It could be rearranged to form the words calm or clam, but you could also form shorter words from a subset of the letters, e.g., lam or ma.
The program will display all such words, with the corresponding Scrabble score for each word, in decreasing order by score. Each letter has a score associated with it, the score for a word is the sum of the scores of each letter in that word. For words with the same scrabble score, the words will appear in alphabetical order
The program will take an optional command-line argument for the dictionary file name. If that argument is left off, it will use the Scrabble dictionary file sowpods.txt
How to run the program: java WordFinder [dictionaryFile]
First, the dictionary is preprocessed, then the words are organized by the set of letters each one contains (this set is a multiset because letters can appear more than once in a word). For each rack, all subset of that multiset of letters is generated, and for each subset, all the words from the dictionary that have the same elements as that subset are added. This approach favors faster processing of the rack.
ScoreTable
The class contains two static methods, a public "getWordValue" and a private "point". The class alsouses an array data structure (this contains the point value associated with each letter)The array is private static and final. Private as the data structure is onlyaccessed through the "point" function and final since point value does not change.getWordValue loops through each character in the word and returns the total point value of the wordruntime for "getWordValue" is O(n)."point" returns the point value of each character.Each point value of each character a-z is stored in the array[26] with 0 corresponding to 'a' and 25 to 'z'.With the numeral codes of letters being sequential ('b' - 'a' = 1, 'c' - 'a' = 2) the array is accessed using this.With arrays being random access (O(1)). The point function runs in O(1)
Rack
This class contains two static methods "getSubsets" and "allSubsets". "getSubSets" uses two data structures - a map andand array. The map holds each character as its key and the number of occurrences of the character as its value.getSubsets loops through the string and adds each letter to the map and increments the count of each letter as necessaryThe array is then created to match the size of the keySet of the map. The array holds the values(count) of each of thekeySet. The runtime of getSubsets is O(n^2) + the time taken by the recursive call to allSubsets
AnagramDictionary
This has two methods - the constructor and getAnagramsOf methods. It also has a private Map variable.This uses a hashMap with a string of keys and an arraylist to hold all multiset of letters that match with the key.The key is a string of letters which has been arranged alphabetically. Any word that matches this form when sortedalphabetically is added to the arraylist(value). The runtime of the constructor is O(n) where n is the number of wordsin the file.getAnagrams converts the string to a charArray and then sorts the string into the alphabetically order. Creates anew string from the sorted word and uses that to access the map data structure. The runtime for this function is O(n)(minus the time to sort the string) which comes from converting the string to charArray.
WordFinder
The contains the main method and handles input/output with the user. It has 3 helper static method -createScoreWordMap, getTotalWordCount and print. The main method also calls the other classes such as rack, scoretableand anagramDictionary. It receives the optional filename from the user console which is used to create theanagramDictionary if available else the default is used. It then requests the user to input the current rack. It callsthe rack allsubset method to get all the available multiset of the rack. Wordfinder then calls createWordMap which takesin a rack and a dictionary and returns a treeMap sorted in reverse order containing all words with length >= 2 and theirscore value. getTotalWordCount takes in the created map and gets the total number of words in the map. print prints outall the words and the score value in the required format.The runtime for createWordMap is O(n^2), getTotalWordCount is O(n), print is O(n^2)
View Source code here
