Lab 9 will allow you to refine your Anagram Generator from Lab 4, enhance your Binary Tree class from Lab 8, experiment with the BitSet class from the Java API, as well as get more practice with Linked Lists and program development techniques. Once you're done, you will use the Intro-CS Assignment Dropoff form to hand in your finished program.
The object of the game is to create a real TextTwist helper - a program that, when given a string of letters (no more than 8), generates all possible words that can be made from that string. This may not seem difficult, but there's a fair amount of hair on this assignment as will be seen below.
Copy your Lab 8 Folder and the MyLinkedList.java file from Lab 7 into a Lab 11 folder.
You will be creating a Binary Search Tree of Words ordered by their sorted (canonical) representation. Thus, you'll need to modify the implementation of compareTo in the Word class to use the sorted word instead of the "normal" word. We also are going back to filtering the words that are read from the file as they're inserted (i.e., words longer than 8 characters are not to be inserted).
In addition to each node of the tree storing a word object, it must also have a linked list of all words that coalesce to the same canonical (sorted) form. For example, star, arts, tsar, and rats all will be found at the same node. Further, the program should be able to search on that canonical form and receive a list of all words that resolve to it (i.e., if it finds star, all four words will be printed). This will require modifying the BinaryNode class to allow for a MyLinkedList instance variable, as well as changing your insert routine in the BinaryTree class. You will also need to implement this new "find" member function.
I suggest adding the following to your words.txt file to test that you are indeed resolving multiple words with the same canonical form to the same location in the tree. You'll need to think about how to print things out as you traverse the tree to make sure things are working well (I'd suggest enhancing your InOrder traversal to print the word and all other words that resolve to that node in the tree).
artsy dog god tam rats mat
Once you've got the new tree working correctly, you're going to need to accept a letter sequence from the user (until they input a sentinel value of your choosing) and print ALL possible words that can be formed from that string. Note that strings of length > 8 should be ignored.
As an example, if I enter "star", I should see the following output (when using the enhanced words.txt file as input to build the initial tree):
arts -> star -> rats
If I enter "star" when using the dictionary.txt file, I should see something like the following (the displayed words do not have to be alphabetically ordered, but they do have to be grouped by length):
2: ar -> at -> ta -> as 3: tar -> art -> rat -> ars -> ras -> tas -> sat 4: rats -> arts -> star -> tars -> tsar
This involves generating the set of all subsets (the powerset) of the initial string. We'll discuss one way to do this in class using a BitSet, but you're free to implement this however you want. This should be written and tested in pieces: first make sure you can generate the powerset correctly, then make sure you're correctly printing all the words that should be generated. In particular, realize that if you input a word like starry, the powerset will generate the star substring twice, but the words that coalesce to star should only be printed once. Also, the words should be grouped by length. You may thus need an auxiliary structure (can you say array of linked lists?) to store the words before printing...
As I said, there's a lot of hair on this one. Again, you should write this code incrementally. And test it on words.txt before trying the larger file.
Use the Intro Programming dropoff form to submit your zip file.