Java程序辅导

Lab 6 : Anagram program 
 
Introduction – READ THE INSTRUCTIONS FIRST! 
 
An anagram is a word or phrase containing all the letters of the original word or phrase rearranged to form a 
new word or phrase using each letter of the original word exactly once. 
 
The version of the program to test anagrams given to you has some problems. It is your job to fix it so that it 
meets all the specifications in the comments of the source code and the examples below. 
 
Be sure to keep a running log (Lab Notes) of each observed bug, hypothesize what is wrong, how you fixed it, 
and how you tested the fix. Be sure to include erroneous hypotheses and non-fixes. Learning from mistakes is as 
important (if not more important).  
 
These are mostly relatively minor 1 or 2 line programming fixes; do not redesign the program. Indeed, this 
program is somewhat convoluted and probably not the way to really check for anagrams. It will not run using a 
full dictionary. So if you are to write an anagram checker for another class, do not try to use this one! 
 
Program Specifications 
Make a new Lab6-Anagram directory in your cs15u home directory and copy all the files from 
~/../public/Lab6-Anagram/ to your new Lab6-Anagram directory 
 
There are three files: TestAnagram.java, LetterCount.java, and dictionary. 
 
The program takes two command line arguments: a dictionary file and a root phrase. We will want to use single 
quotes around the root phrase so special shell characters (meta-characters) like bang are not interpreted by the 
shell with their special meaning, but instead are treated as a regular character. 
 
The program generates a list of candidate phrases that are combinations of words from the test dictionary file 
connected by single spaces to form phrases. Each candidate phrase is checked to see if it has the same letter 
count as the root phrase (same number of A's and B's, etc.) ignoring case and ignoring non-alpha characters. For 
example, with a root phrase of "dormitory" an anagram is "dirty room!" because "dirty" and "room!" are in the 
supplied dictionary file named dictionary. A root phrase of "I Nice god" or "god in ice" will display the 
anagram "I code gin" because "I" and "code" and "gin" are in the dictionary file. 
 
This program is still somewhat lame: it can only generate phrases from words in the dictionary file in the order 
the words appear in the dictionary file. For example, it will not generate the phrase "room! dirty" because 
"room!" comes after "dirty" in the dictionary file. Likewise it will not generate the phrase "gin code I" because 
"I" comes before "code" which comes before "gin" in the dictionary file. 
 
The program should display all the anagram phrases found and the number of anagrams found. 
 
Follow these lab instructions: 
 
Compile and run the test program: TestAnagram.java 
 
$ javac TestAnagram.java 
$ java TestAnagram 
Error! Expected 2 string arguments 
 
Let's try it again. 
 
$ java TestAnagram dictionary 'dormitory' 
The root word is: dormitory 
Exception in thread "main" java.lang.NullPointerException 
        at TestAnagram.combineStrings(TestAnagram.java:106) 
        at TestAnagram.findMatches(TestAnagram.java:79) 
        at TestAnagram.getAnagramsOf(TestAnagram.java:59) 
        at TestAnagram.main(TestAnagram.java:29) 
 
Yikes! 
 
If we look at where the exception is being thrown, it could be either the String left or the String right. We may 
want to look at these values later anyway to make sure this method is doing the right thing, so let's add some 
logging here. 
 
Set up the logging framework in TestAnagram.java similar to the last lab. 
 
The logging javadoc we used: http://docs.oracle.com/javase/7/docs/api/java/util/logging/Logger.html 
 
private static Logger log = Logger.getLogger("TestAnagram"); 
 
We will be accessing this logger in static methods, so variable log will need to be static. 
 
Be sure to add a commented  
 
 // log.setLevel(Level.OFF); 
 
line at the top of main() so logging will now be on and we can easily turn it off by uncommenting that line. 
 
At the top of the method combineStrings(), add a log.info logging message to display the value of the String 
left in double quotes and the String right in double quotes. 
 
Do this and recompile TestAnagram.java and run the same TestAnagram. Your output should now look 
something like this (make sure the strings are in double quotes in the log message): 
 
$ java TestAnagram dictionary 'dormitory' 
The root word is: dormitory 
Jul 17, 2011 6:12:54 PM TestAnagram combineStrings 
INFO: left = "null", right = "I" 
Exception in thread "main" java.lang.NullPointerException 
        at TestAnagram.combineStrings(TestAnagram.java:113) 
        at TestAnagram.findMatches(TestAnagram.java:84) 
        at TestAnagram.getAnagramsOf(TestAnagram.java:64) 
        at TestAnagram.main(TestAnagram.java:34) 
 
Now we know it is left that is null right away the very first time combineStrings() is called. 
 
Let's trace the call to see how this value is passed. Your line numbers may be different depending on blank lines 
in your file. In the above example, line 84 is where combineStrings() was called from within findMatches(). We 
see the argument partialResult is being passed through from findMatches() to combineStrings(), so let's go to 
where findMatches() is being called: line 64 in my example. 
 
Here we see partialResult being initialized to null. But look at the comment! Fix the initialization 
expression so we really are initializing partialResult to an empty String. Hey while we are at it, should we 
look around to see what else we can change? Heck no! We just made one change. So … Recompile and test it 
again. 
 
Now we are eventually getting null in the right String. Trace how the String value for right gets passed 
down. The right String is from the dict ArrayList. This is a list of all the Strings in the dictionary file. Looks 
like we had better make sure this list is being built correctly first. 
 
We can see from the back trace that findMatches() is called from getAnagramsOf() at line 64. And 
getAnagramsOf() is called from main() at line 34. So right before the call to getAnagramsOf() at line 34 (or so) 
in main(), let's add some instrumentation to log the contents of the ArrayList that was built from the Strings in 
the dictionary file. We can easily do this with the toString() implementation of the Collection type ArrayList. 
 
 log.info("dict: " + dict);  // implicitly invoking dict.toString() 
 
This prints each element in the ArrayList (Collection) dict enclosed in square brackets ("[ ]") separated by a 
comma and space (", "). 
 
Put this line above the call to getAnagramsOf() [line 34 in my example]. 
 
Compile and run again. 
 
Wow! Too much going on here. Let's make a small test dictionary file that is more manageable so we can see 
what is going on. Create a file named small_dict that just has the words: 
 
a 
dirty 
room! 
zip 
 
First and last words from the larger dictionary plus the two words we are interested in with our "dormitory" 
example. 
 
Test with this smaller test dictionary file. 
 
$ java TestAnagram small_dict 'dormitory' 
 
Look for the instrumentation we just added - the one that looks like: 
 
INFO: dict: [dirty, zip] 
 
Hmmm. Look at the dictionary file we are using - small_dict. Hey! The ArrayList is not getting built correctly. 
Looks like every other word starting with the second word is getting added to the ArrayList (and every other 
word starting with the first word is NOT getting added to the ArrayList). The ArrayList is being built right 
above our logging statement. Looks like we need to fix how each line is being read in from the dictionary file 
and added to the ArrayList dict. 
 
Fix it. Hopefully by now you know the template/structure to use readLine() correctly! Compile and run with the 
small_dict test dictionary file again.  
 
 
Now you should see all four words are in your ArrayList. 
 
INFO: dict: [a, dirty, room!, zip]  
 
And we can see the values of the left and right Strings in combineStrings(). It even found an anagram phrase of 
"dirtyroom!" but a couple things are wrong! 
 
1) combineStrings() is supposed to concatenate the left and right Strings with a space between them. 
    We are supposed to get the anagram phrase "dirty room!" 
 
2) the final message says "Result: none found" – this is wrong. 
 
Let's tackle the combineStrings() not putting a space between the words first. Look at the logic in 
combineStrings() used to determine if it should concatenate left and right with or without a space. Understand 
what it is supposed to do (read the comments) and what it is actually doing and fix it. 
 
Compile and run. The program should now show the anagram found as "dirty room!" (with a space between the 
words) and you can see in the logs at one point "dirty" and "room!" being combined with a space between them. 
 
Now let's tackle the problem with the program erroneously reporting no anagrams being found. 
 
Find the part of the code that does this reporting. Look to see what could be causing this problem. Add logging 
if you need to. Fix it. 
 
When fixed, the last line with the 'dormitory' test using the small_dict test file should be  
 
 Result: found 1 anagram 
 
While you are looking at this general area, observe how the code is handling the plural of anagram – anagrams? 
 
While we still have the small test dictionary file "small_dict", let's try another simple example. 
 
$ java TestAnagram small_dict 'piza' 
... 
Anagram phrases found: 
a zip 
Result: found 1 anagram 
 
Great! But let's try something that should fail. 
 
$ java TestAnagram small_dict 'pizza' 
... 
Anagram phrases found: 
a zip 
Result: found 1 anagram 
 
Oops! That should not happen. The root word "pizza" has two 'z' characters, but our program erroneously 
reported that the phrase "a zip" is an anagram. 
 
In findMatches(), there is a check to see if the LetterCount of a combined string (candidate) is equal to the 
LetterCount of the root string (target), and if so then add the combined string (candidate string) to the list of 
results. We better instrument the LetterCount class. 
 
Looking at LetterCount.java, there is an array count that holds the number of occurrences of each letter in a 
String. It will be a lot easier for us if we add a String instance variable to associate with this array to make sure 
the constructor is building the array correctly. 
 
Add an instance variable 
 
 private String s; 
 
and initialize s in the LetterCount ctor. 
 
Add logging framework and then add a logging statement at the end of the ctor, something like 
 
 log.info(s + ": " + Arrays.toString(count)); 
 
Class Arrays is in the java.util package. This is a convenient way to display the contents of an array similar to 
the toString() implementation for Lists/Collections. Check out the toString() method in class Arrays in the 
java.util package. 
 
Let's make a smaller dictionary file (say, smaller_dict) with just 
 
a 
zip 
 
in it. Compile TestAnagram (remember why we do not need to explicitly compile LetterCount.java?) and run 
 
$ java TestAnagram smaller_dict 'pizza' 
 
Look specifically for the logging output that displays the string and letter count array for "pizza" and "a zip" 
 
This will make it easier: 
 
$ java TestAnagram smaller_dict 'pizza' 2>&1 | egrep 'pizza:|a zip:' 
 
INFO: pizza: [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2] 
INFO: a zip: [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] 
 
This redirects file descriptor 2 stderr (where the logging output is going) to the same stream as file descriptor 1 
stdout then pipes the combined output to the program egrep to pattern match 'pizza:' OR 'a zip:' (vertical bar '|' in 
the pattern is the OR operator) since these two lines are the only ones we really care about in this test run and 
this puts them one on top of the other for easy comparison. 
 
First, are they correct? And then what do you notice that is different between the two? They should be different, 
right? But the equals() method in LetterCount is reporting they are the same. 
 
Look at the equals() method in LetterCount.java. What is wrong. Fix. Recompile. Test. 
 
Once you feel your program is working correctly, disable logging in both source files. 
 
Make sure your program works correctly for the following root phrases using the supplied dictionary file. For 
example: 
 
$ java TestAnagram dictionary 'Angriest' 
 
How many anagrams are found with each of the phrases? 
 
 Angriest _____ 
 
 Opts  _____ 
 
 A Glen _____ 
 
 Santa  _____ 
 
 Z z Z  _____ 
 
 Castle  _____ 
 
 I ate range str! _____ 
 
 god in ice _____ 
 
 
 
Be sure to keep a running log (Lab Notes) of each observed bug, hypothesize what is wrong, how you fixed it, 
and how you tested the fix. Be sure to include erroneous hypotheses and non-fixes. Learning from mistakes is as 
important (if not more important). 
 
Get one of the CSE 15L staff to check you off for the lab. You will need to go through your log describing each 
bug interaction and demo your fixed version with all three unit tests.