https://www.dropbox.com/s/jvi46psiaw41lcm/words.txt?dl=0

In this week's lab, you write methods to operate on a list of words and practice using the ArrayList class in the Java Collection Framework. The JUnit test class needs the data file words.txt that contains about 235,000 words of English sorted in ascending dictionary order, so download this file (DropBox link) and copy it into your Lab 9 project folder. Write the following methods in the class WordProblems. From this wordlist file, the JUnit test class is guaranteed to use only the proper words consisting of only the English lowercase characters a to z. Against my usually required principle of "Silence is golden", the JUnit test class will output a message "Read 210687 words from words.txt." at initialization so that you know that the wordlist has been successfully read in. (Your methods should still only "be seen and not heard", though.)

Your methods should not modify their parameter arraylist words in any way. Also, the JUnit tester requires that every method must return the words that it finds in the same alphabetical order that they occur in the parameter list words. This should not be a problem, since your code will most likely process the words in this alphabetical order.

Write the method ArrayList findMatchingWords(ArrayList words, String pattern) that creates and returns a new ArrayList that contains all words in words that match the given pattern so that the found word and the pattern are the same length and contain the same characters in the same positions. The pattern can also contain question mark characters as wildcard characters that match any letter that does not occur anywhere in the pattern, in spirit of the game of Hangman. For example, the words "bridge" and "drudge" would match the pattern "?r??ge", but the words "dredge" and "grunge" would not. (Use the String method indexOf to quickly determine whether some character occurs inside the pattern, or precompute a 26-element boolean array to tell you this.)

Write the method ArrayList findSemordnilaps(ArrayList words) that creates and returns a new ArrayList that contains all semordnilaps in words. A word is (slightly humorously) called a "semordnilap" (the word "palindromes" read backwards) if reading that word backwards gives you another word that is different from the original word. For example, the word "tuba" is a semordnilap, since reading it backwards gives you a new word "abut". However, the word "bob" is not a semordnilap, since it is an ordinary palindrome and reading it backwards produces the same word. Remember that unlike String class, the class StringBuilder has a built in reverse method, which should eliminate one inner loop from your code. You still have to convert back and forth from String to StringBuilder, though. Also, since words is known to be in sorted dictionary order, you can use the utility method Collections.binarySearch to quickly check whether the reverse of the given string is a word, instead of having to act like some "Shlemiel" and look for that reversed word by comparing it individually to every word in words. However, note that this method returns the negation of the insertion position whenever the word you search for is not in the list, so you need to test whether the returned result is greater than -1 to check if that word is in this list.

Write a method ArrayList findAnagrams(ArrayList words, String word) that creates and returns a new ArrayList that contains all words in words that are anagrams of word, that is, contain the exact same characters but possibly in different order. (Note that each word is trivially an anagram of itself.) There are many ways to check whether two given strings are anagrams. Start by checking that both have the same length, which immediately determines for most pairs of strings that they cannot be anagrams. Then you can, for example, use an array of 26 integer counters to count how many times each character from a to z occurs in both strings. Alternatively, you can convert both strings to arrays (the class String has built in toCharArray() method to do this), sort these arrays and compare whether they are equal. The utility class java.util.Arrays offers pretty convenient methods for these last two operations. But there exist even faster ways for anagram checking out there...

Write a method ArrayList findOneLessWords(ArrayList words, String word) that creates and returns a new ArrayList that contains all the words in words that can be constructed by removing exactly one character from the given word and keeping the rest of the characters in the order that they were. For example, when given the word "stopper", this method would return the words "sopper", "stoper" and "topper", and when given the word "ledger", this method would return the words "edger", "ledge" and "leger". Same as previous problems, this method must return the list of words in sorted order and without duplicates. The fastest way to solve this problem is to loop through all the possible positions to remove a character from word, and then use Collections.binarySearch to find out whether removing that character results in a word, adding each word to the result unless it is already there. The list of words is then sorted using Collections.sort and returned to the caller. (As a fun additional exercise, can you find the English language word that produces the largest possible number of words as the answer to this method? Truly hardcore students could even try to find the longest possible chain of words so that each word is constructed from the previous word by removing one letter. The instructor has found several chains of eight words such as "swaddler, waddler, wadder, wader, waer, war, ar, r" or "smaltine, saltine, saline, sline, sine, sie, ie, e", but could there be a chain that contains nine words? How about in other languages whose wordlists you can download from the web?)

TEST:

import static org.junit.Assert.*; import org.junit.After; import org.junit.Before; import org.junit.Test; import java.io.File; import java.util.*; import java.util.zip.Adler32; public class TestWordProblems { private WordProblems wp = new WordProblems(); private static final int SEED = 12345; private static final int MATCHRUNS = 100; private static final int ANARUNS = 300; private static final int PARTRUNS = 50000; private static ArrayList words = new ArrayList(); private static void readWords() { if(words.size() > 0) { return; } try { Scanner s = new Scanner(new File("words.txt")); while(s.hasNextLine()) { String word = s.nextLine(); boolean isGood = true; for(int i = 0; i < word.length(); i++) { char c = word.charAt(i); if(c < 'a' || c > 'z') { isGood = false; break; } } if(isGood) { words.add(word); } } } catch(Exception e) { System.out.println("Failed to read file 'words.txt': " + e); } assertTrue(words.size() > 100000); System.out.println("Read " + words.size() + " words from words.txt."); } private char randomChar(Random rng, char spec) { if(rng.nextDouble() < 0.2) { return spec; } else { return (char)('a' + rng.nextInt(26)); } } private String buildString(Random rng, int len, char spec) { StringBuilder sb = new StringBuilder(); for(int j = 0; j < len; j++) { sb.append(randomChar(rng, spec)); } return sb.toString(); } @Test public void testFindMatchingWords() { readWords(); java.util.Random rng = new java.util.Random(SEED); Adler32 check = new Adler32(); int total = 0; for(int i = 0; i < MATCHRUNS; i++) { String pat = buildString(rng, 1 + i % 10, '?'); ArrayList result = wp.findMatchingWords(words, pat); total += result.size(); for(String word: result) { check.update(word.getBytes()); } } assertEquals(634, total); assertEquals(3266665665L, check.getValue()); } @Test public void testFindAnagrams() { readWords(); java.util.Random rng = new java.util.Random(SEED); Adler32 check = new Adler32(); int total = 0; for(int i = 0; i < ANARUNS; i++) { String pat = words.get(rng.nextInt(words.size())); ArrayList result = wp.findAnagrams(words, pat); total += result.size(); for(String word: result) { check.update(word.getBytes()); } } assertEquals(338, total); assertEquals(1768237328L, check.getValue()); } @Test public void testFindSemordnilaps() { readWords(); java.util.Random rng = new java.util.Random(SEED); Adler32 check = new Adler32(); ArrayList result = wp.findSemordnilaps(words); for(String word: result) { check.update(word.getBytes()); } assertEquals(930, result.size()); assertEquals(4276396468L, check.getValue()); } @Test public void testFindOneLessWords() { readWords(); java.util.Random rng = new java.util.Random(SEED); Adler32 check = new Adler32(); System.out.println(wp.findOneLessWords(words, "ledger")); System.out.println(wp.findOneLessWords(words, "stopper")); int total = 0; for(int i = 0; i < PARTRUNS; i++) { String word = words.get(rng.nextInt(words.size())); ArrayList result = wp.findOneLessWords(words, word); total += result.size(); for(String w: result) { check.update(w.getBytes()); } } assertEquals(11653, total); assertEquals(1505312022L, check.getValue()); } }