Reading: Finish Chapter 6 in the Objects
First
text. Work along
with it, using BlueJ. Start Chapter 7.
A) Beneath Chopin: The Piano Bench
1) Look at the JavaDocs for the class HashMap, Scanner,
and Random. Also look at the String class .toCharArray()
method which returns an array of type char[]. And see the
static Arrays.sort() method, which sorts an array in
place. (Note the "s" in Arrays.) Think about how they can
be used in implementing the anagram
algorithm described below.
2) Design a UserWordList class to get a list of words
from the Console input. It has a constructor (with no parameters)
which, when run, prompts the user for words and saves them. With a line
Scanner in = new Scanner(System.in) you create the scanner and
then use in.nextLine() to get each line of input. Have an empty
line signal the end of the list. Make a getWords() method which
returns a List of the Strings entered.
3) As we have not covered files yet, I wrote a FileWordList()
class for you. Its constructor takes a filename in the form of a
String. It has a getWords() method which returns a List of
Strings. Download this class and
these files to use with it: testwordlist.txt
and wordlist.txt (1.9MB). The first
file has six words (stop, test,
opts, art, pots, tar) to use while debugging your program. The second
file has some 175000 words, so only use it after everything is working.
4) Design an Anagram class. Its constructor works by taking a
list of words and making a database of pairs like:
(opst, {stop, opts, pots))
(art, {art, tar})
(estt, {test})
The first element of each pair is an alphabetized version of the string
(or an alphabetized list of characters). The second element in each
pair is a set of strings---the words
from the given list that have those letters. When words are anagrams,
they appear in the same list. The entire database can be stored as a Map,
so that given a new word, we can quickly process it into an
alphabetized list of characters and then find the list of words it maps
to.
Write a sortedChars() method that takes a String and returns
the sorted list of its letters, e.g., given "post" it returns "opst".
The type of the method can be either String or ArrayList<Character>
as long as you are consistent in how you use it below. (If you
want, this can be a static method as it does not depend on the
wordlist.) (Just as we used "autoboxing" last week between int and
Integer, here you can use an ArrayList<Character> but think of
each element as a char.) The following method takes a String and
returns
a String with the same letters in alphabetic order; it is something
like a static method as it does not involve this, so you can
call the method simply as sort("xyz")
without any dot thing before it:
private String sort(String w)
{
char [] letters = w.toCharArray();
Arrays.sort(letters);
return new String(letters);
}
The Anagram constructor should take a list of Strings, as provided by
one of the getWords() methods above. For each, find its
alphabetized list of characters. Look it up in the map. If there is no
entry for it yet, make a new entry which maps it to a list containing
just the one word. If there is already an entry for it, modify the
entry by adding the word to the list of anagrams.
Write an anagramsOf() method that takes a string and using the
database returns the set of its anagrams, or an empty set (not
null) if it has no anagrams.
Write a userInput() method which uses your UserWordList() class
to get a list of words from the user, and then prints out all the
anagrams for each. Nothing is returned.
Write a printSetsOfLength() method that takes an integer n
and prints all sets containing two or more n-letter words.
Write a printSetsofSize() method that takes an integer n
and prints all sets containing exactly n words.
Write a printRandomSet() method that prints a random anagram
set of size greater than one.
5)
Send your .jar file to the TA and include in your email the following:
Give ten random anagram sets. Find all the anagram sets in the big
dictionary with 8 or more anagrams.
Find all the 10-letter anagrams.
B) Automated Unit Testing (Nothing to hand in)
1) Do the automated Junit testing exercises in Section 6.4 of the text.
2) Test your Seive code that
finds the
primes under 100. Let's automate six similar tests, then
modify the code, and then retest to verify that the code modifications
did not affect the result:
Write a method getLargest() similar to your printLargest(),
but which returns an int value. Check it returns 19 as the largest
prime under 20.
Write a method getCount() which returns the number of primes
found, as an int value. Check it returns 8 as the number of primes
under 20.
Create a TestSieve class behind Sieve. Within it, record three
separate
tests: In the first, set N=20 and run getLargest and getCount and
assert their values of 19 and 8. Make a second and third test
with N set respectively to100 and some larger number. Run all the tests
to make sure your code passes them.
Temporarily put a bug in your code, e.g., initialize the candidates
starting with 5 instead of 2, and make sure you fail at least one test.
Then fix the bug and make sure you again pass the tests.
Make the following modifications to your code, which should not
affect the output. After each,
run all the tests to make sure the code still works:
- Change the type of set you use in all of the internal
variables, switching between HashSet, TreeSet, and LinkedHashSet.
- Initialize the candidates to only the odd numbers, 3...N, and
initialize the set of primes to {2}.
- Change the way you create the multiples so values greater than N
are
not put in the set of multiples.