Anagram Solver
Generating anagrams with recursive backtracking.
Table of contents
An anagram is a word or phrase made by rearranging the letters of another word or phrase. For example, the words “midterm” and “trimmed” are anagrams. If you ignore spaces and capitalization and allow multiple words, a multi-word phrase can be an anagram of some other word or phrase. For example, the phrases “Clint Eastwood” and “old west action” are anagrams.
AnagramSolver
Implement an AnagramSolver class that uses recursive backtracking to print all anagram phrases of a given word or phrase.
Method summary
public AnagramSolver(List<String> dictionary)- Initializes a new
AnagramSolverobject using the givendictionary, precomputing all of the letter inventories in advance and storing them in aHashMap(Note that we should be using aHashMapand not aLinkedHashMap). This method should not change the list in any way. Assume that thedictionaryis a non-empty collection of non-empty sequences of letters, and that it contains no duplicates. public void print(String text, int max)- Prints all anagrams of
textthat include at mostmaxwords (or an unlimited number of words ifmaxis 0) toSystem.outusing an optimized recursive backtracking algorithm. Do not make any assumptions about the length of the input or output ifmaxis 0. Throw anIllegalArgumentExceptionifmaxis less than 0.
Development strategy
Represent text using LetterInventory objects to keep track of counts of each letter in the text. By choosing this abstraction, we can now rely on the subtract method to figure out when one group of letters can be formed from another group of letters.
LetterInventory letters = new LetterInventory("midterm");
LetterInventory candidate = new LetterInventory("term");
letters.subtract(candidate); // [dim]
Since the result of letters.subtract(candidate) is not null, candidate could be one of the words in an anagram phrase for letters.
print must produce anagrams in the same format as in the complete example execution as well as the Output Comparison Tool. The easiest way to do this is to build up the answer one word at a time in a List or Stack and then print the resulting data structure. On each recursive call, search the dictionary from beginning to end and to explore each word that is a match for the current set of letters. The possible solutions should be explored in the same order as they appear in the given dictionary file. Note that if you are removing from your List, there are two versions of the remove method. One that removes an element at an index and one that removes the first occurence of an element in your List; it is up to you to decide which one is best suited for this program. You should start by implementing this method without considering max, and then add logic for max.
Once you have a working print method, add the following optimization to speed up the recursive backtracking and avoid unnecessary recursive calls. For any given phrase, reduce the dictionary to a smaller dictionary containing only relevant words. A word is relevant if it can be subtracted from the given phrase. To implement this, construct a smaller dictionary for each phrase that includes only the words relevant to that phrase. Do this once before the recursion begins—not on each recursive call. A further, optional optimization would be to prune the dictionary on each recursive call. If you decide to prune on each recursive call, clearly document it.
To test the pruning optimization, print the size of the original dictionary and the pruned dictionary and manually check that the output matches what you would expect for the eleven.txt dictionary. As another example, when processing “george bush” on dict1.txt, the original dictionary of size 56 is pruned to a new dictionary of size 31.
The print method can sometimes produce too much output for jGRASP to handle. jGRASP will only display 500 lines of output. If you want to see more, go to the Build menu and select the “Run in MSDOS Window” option. In the new window, right-click on the title bar of the window, select Properties, and under the “Layout” tab adjust the “Screen Buffer Size” to 9999 lines, for example.
Complete example
Suppose we want to print all anagrams of “eleven plus two” given the dictionary file eleven.txt.
- zebra
- one
- plus
- won
- potato
- twelve
The letters in “eleven plus two” do not support all the words in the dictionary. In particular, “potato” and “zebra” contain letters (“a” and “z”, respectively) that are not in elevenplustwo. So, we prune the dictionary to the following:
- one
- plus
- won
- twelve
Using the pruned dictionary, we explore the possible anagram words with recursive backtracking, keeping track of the remaining letters at each recursive call.
Welcome to the cse143 anagram solver.
What is the name of the dictionary file? eleven.txt
phrase to scramble (return to quit)? eleven plus two
Max words to include (0 for no max)? 0
[one, plus, twelve]
[one, twelve, plus]
[plus, one, twelve]
[plus, twelve, one]
[twelve, one, plus]
[twelve, plus, one]
phrase to scramble (return to quit)?
"george bush" example with dict0.txt
explore [beegghorsu]
bee
choose bee
explore [gghorsu]
bee
go
choose go
explore [ghrsu]
bee
go
gush
choose gush
explore [r]
bee
go
gush
shrug
unchoose
shrug
choose shrug
explore []
print [bee, go, shrug]
unchoose
unchoose
gush
choose gush
explore [gor]
bee
go
choose go
explore [r]
bee
go
gush
shrug
unchoose
gush
shrug
unchoose
shrug
choose shrug
explore [go]
bee
go
choose go
explore []
print [bee, shrug, go]
unchoose
gush
shrug
unchoose
unchoose
go
choose go
explore [beeghrsu]
bee
choose bee
explore [ghrsu]
bee
go
gush
choose gush
explore [r]
bee
go
gush
shrug
unchoose
shrug
choose shrug
explore []
print [go, bee, shrug]
unchoose
unchoose
go
gush
choose gush
explore [beer]
bee
choose bee
explore [r]
bee
go
gush
shrug
unchoose
go
gush
shrug
unchoose
shrug
choose shrug
explore [bee]
bee
choose bee
explore []
print [go, shrug, bee]
unchoose
go
gush
shrug
unchoose
unchoose
gush
choose gush
explore [beegor]
bee
choose bee
explore [gor]
bee
go
choose go
explore [r]
bee
go
gush
shrug
unchoose
gush
shrug
unchoose
go
choose go
explore [beer]
bee
choose bee
explore [r]
bee
go
gush
shrug
unchoose
go
gush
shrug
unchoose
gush
shrug
unchoose
shrug
choose shrug
explore [beego]
bee
choose bee
explore [go]
bee
go
choose go
explore []
print [shrug, bee, go]
unchoose
gush
shrug
unchoose
go
choose go
explore [bee]
bee
choose bee
explore []
print [shrug, go, bee]
unchoose
go
gush
shrug
unchoose
gush
shrug
unchoose
Grading
In terms of external correctness, your class must provide all of the functionality described above. In terms of style, we will be grading on your use of comments, good variable names, consistent indentation and good coding style to implement these operations.
There are several places where unnecessary or repeated logic is typically introduced.
- Don’t compute a value more than once if it doesn’t need to be recomputed.
- Don’t continue to explore recursive branches that will never be printed.
- Don’t introduce unnecessary base cases or recursive cases.
Your class may have other methods besides those specified, but any other methods you add should be private.
Reflection
Create a new file reflection.txt and write a paragraph-long reflection answering the following questions (along with anything else you find appropriate):
- What did you learn this week?
- What did you enjoy in the course this week?
- What did you find challenging or frustrating this week?
- What did you find particularly helpful for your learning this week?
Submission
Submit AnagramSolver.java and reflection.txt to Grade-It!