import java.io.*;

import java.util.*;

public class WordTool {

public static String[] getDictionary ()

{

return getDictionary ("words");

}

public static String[] getDictionary (String fileName)

{

String[] words = readDictionary (fileName);

String[] scrubbedWords = scrub (words);

return scrubbedWords;

}

static String[] readDictionary (String fileName)

{

String[] words = null;

try {

// Since we don't know in advance how many words there

// are, we'll use a list instead of an array.

LinkedList stringList = new LinkedList();

// Scanner knows how to skip whitespace.

Scanner scanner = new Scanner (new FileReader (fileName));

while (scanner.hasNext()) {

// At each step, get the next word and place in list.

String s = scanner.next();

stringList.addLast (s);

}

// Now that we know the size, we'll make an array.

words = new String [stringList.size()];

Iterator iter = stringList.iterator();

int i = 0;

while (iter.hasNext()) {

words[i] = iter.next();

i ++;

}

// Done.

return words;

}

catch (IOException e) {

System.out.println (e);

System.exit (0);

return null;

}

}

static String[] scrub (String[] words)

{

// Remove words with caps, and single-letter words

int badWords = 0;

for (int i=0; i

if (words[i].length()

badWords ++;

words[i] = null;

}

else if ( Character.isUpperCase (words[i].charAt(0)) ) {

badWords ++;

words[i] = null;

}

}

// Make space for the good words.

String[] realWords = new String [words.length - badWords];

int j = 0;

for (int i=0; i

while (words[j] == null) {

j ++;

}

realWords[i] = words[j];

j ++;

}

return realWords;

}

}

class WordGameUnitTests {

// This is a case where a global reference to a dictionary makes sense.

// The dictionary is a read only database of sorts and we wish to have

// this reference available for any unit tests that need to use the

// whole dictionary. We also wish to load it only once.

static String[] dictionary;

// For most cases, this would be a bad decision, but it is acceptable

// here given the above behavior and requirements

/// The main function acts as the test harness. Any unit tests must be

/// registered in this function.

public static void main(String[] args) {

// Get the dictionary.

dictionary = WordTool.getDictionary ();

// fail tracks whether any test has failed.

boolean fail = false;

// * Run the battery of base tests *

System.out.println("Base Test 1 - Begin");

if( baseUnitTest1() ) {

System.out.println("Base Test 1 - Succeeded");

} else {

System.out.println("Base Test 1 - Failed");

fail = true;

}

System.out.println("Base Test 2 - Begin");

if( baseUnitTest2() ) {

System.out.println("Base Test 2 - Succeeded");

} else {

System.out.println("Base Test 2 - Failed");

fail = true;

}

System.out.println("Base Test 3 - Begin");

if( baseUnitTest3() ) {

System.out.println("Base Test 3 - Succeeded");

} else {

System.out.println("Base Test 3 - Failed");

fail = true;

}

System.out.println("Base Test 4 - Begin");

if( baseUnitTest4() ) {

System.out.println("Base Test 4 - Succeeded");

} else {

System.out.println("Base Test 4 - Failed");

fail = true;

}

System.out.println("Base Test 5 - Begin");

if( baseUnitTest5() ) {

System.out.println("Base Test 5 - Succeeded");

} else {

System.out.println("Base Test 5 - Failed");

fail = true;

}

System.out.println("Base Test 6 - Begin");

if( baseUnitTest6() ) {

System.out.println("Base Test 6 - Succeeded");

} else {

System.out.println("Base Test 6 - Failed");

fail = true;

}

System.out.println("Base Test 7 - Begin");

if( baseUnitTest7() ) {

System.out.println("Base Test 7 - Succeeded");

} else {

System.out.println("Base Test 7 - Failed");

fail = true;

}

System.out.println("Base Test 8 - Begin");

if( baseUnitTest8() ) {

System.out.println("Base Test 8 - Succeeded");

} else {

System.out.println("Base Test 8 - Failed");

fail = true;

}

System.out.println("Base Test 9 - Begin");

if( baseUnitTest9() ) {

System.out.println("Base Test 9 - Succeeded");

} else {

System.out.println("Base Test 9 - Failed");

fail = true;

}

System.out.println("Base Test 10 - Begin");

if( baseUnitTest10() ) {

System.out.println("Base Test 10 - Succeeded");

} else {

System.out.println("Base Test 10 - Failed");

fail = true;

}

System.out.println("Base Test 11 - Begin");

if( baseUnitTest11() ) {

System.out.println("Base Test 11 - Succeeded");

} else {

System.out.println("Base Test 11 - Failed");

fail = true;

}

System.out.println("Base Test 12 - Begin");

if( baseUnitTest12() ) {

System.out.println("Base Test 12 - Succeeded");

} else {

System.out.println("Base Test 12 - Failed");

fail = true;

}

System.out.println("Base Test 13 - Begin");

if( baseUnitTest13() ) {

System.out.println("Base Test 13 - Succeeded");

} else {

System.out.println("Base Test 13 - Failed");

fail = true;

}

System.out.println("Base Test 14 - Begin");

if( baseUnitTest14() ) {

System.out.println("Base Test 14 - Succeeded");

} else {

System.out.println("Base Test 14 - Failed");

fail = true;

}

if( fail ) {

System.out.println("Failed Base Unit Testing");

} else {

System.out.println("Passed Base Unit Testing");

}

if( fail ) {

System.out.println("If the base tests are all passed, new tests will be added for the challenge.");

return;

}

// * Run the battery of challenge tests *

System.out.println("Challenge Test 1 - Begin");

if( chalUnitTest1() ) {

System.out.println("Challenge Test 1 - Succeeded");

} else {

System.out.println("Challenge Test 1 - Failed");

fail = true;

}

System.out.println("Challenge Test 2 - Begin");

if( chalUnitTest2() ) {

System.out.println("Challenge Test 2 - Succeeded");

} else {

System.out.println("Challenge Test 2 - Failed");

fail = true;

}

System.out.println("Challenge Test 3 - Begin");

if( chalUnitTest3() ) {

System.out.println("Challenge Test 3 - Succeeded");

} else {

System.out.println("Challenge Test 3 - Failed");

fail = true;

}

System.out.println("Challenge Test 4 - Begin");

if( chalUnitTest4() ) {

System.out.println("Challenge Test 4 - Succeeded");

} else {

System.out.println("Challenge Test 4 - Failed");

fail = true;

}

System.out.println("Challenge Test 5 - Begin");

if( chalUnitTest5() ) {

System.out.println("Challenge Test 5 - Succeeded");

} else {

System.out.println("Challenge Test 5 - Failed");

fail = true;

}

if( fail ) {

System.out.println("Failed Challenge Unit Testing");

} else {

System.out.println("Passed Challenge Unit Testing");

}

}

//--------------------------- Base Unit Tests -----------------------

/// This test validates that contains returns false if word is null

/// @return true if the test is successful; otherwise, the test fails.

public static boolean baseUnitTest1() {

String letters = "ddax";

String word = null;

boolean result = WordGame.contains(word, letters);

if(result != false) {

return false;

}

return true;

}

/// This test validates that contains returns false if letters is null

/// @return true if the test is successful; otherwise, the test fails.

public static boolean baseUnitTest2() {

String letters = null;

String word = "add";

boolean result = WordGame.contains(word, letters);

if(result != false) {

return false;

}

return true;

}

/// This test validates that contains returns false if letters is an

/// empty string

/// @return true if the test is successful; otherwise, the test fails.

public static boolean baseUnitTest3() {

String letters = "";

String word = "add";

boolean result = WordGame.contains(word, letters);

if(result != false) {

return false;

}

return true;

}

/// This test validates that contains returns true if word is an empty

/// string

/// @return true if the test is successful; otherwise, the test fails.

public static boolean baseUnitTest4() {

String letters = "ddax";

String word = "";

boolean result = WordGame.contains(word, letters);

if(result == false) {

return false;

}

return true;

}

/// This test validates that contains returns true if the word can be

/// spelled using the set of letters

/// @return true if the test is successful; otherwise, the test fails.

public static boolean baseUnitTest5() {

String letters = "ddax";

String word = "add";

boolean result = WordGame.contains(word, letters);

if(result == false) {

return false;

}

return true;

}

/// This test validates that contains returns true if the word cannot

/// be spelled using the set of letters

/// @return true if the test is successful; otherwise, the test fails.

public static boolean baseUnitTest6() {

String letters = "zzz";

String word = "add";

boolean result = WordGame.contains(word, letters);

if(result != false) {

return false;

}

return true;

}

/// Test checks whether search properly handles a null dictionary.

/// search should return an empty string if it cannot find a word in the

/// dictionary. The dictionary is invalid, so search should return an

/// empty string.

/// @return true if the test is successful; otherwise, the test fails.

public static boolean baseUnitTest7() {

String letters = "aaaaaa";

String word = WordGame.search(null, letters);

if(word != null) {

return false;

}

return true;

}

/// This test checks whether search properly handles a null set of

/// letters. search should return an empty string if it cannot find a

/// word in the dictionary. The set of letters in invalid, so search

/// should return an empty string.

/// @return true if the test is successful; otherwise, the test fails.

public static boolean baseUnitTest8() {

String word = WordGame.search(dictionary, null);

if(word != null) {

return false;

}

return true;

}

/// Test checks whether search properly handles an empty dictionary.

/// search should return an empty string if it cannot find a word in the

/// dictionary. The dictionary contains nothing, so search should

/// return an empty string.

/// @return true if the test is successful; otherwise, the test fails.

public static boolean baseUnitTest9() {

String letters = "aaaaaa";

// Note: this seems weird. Allocating an array of size 0, WTH?

// You can do it. It also seems weird that this call doesn't store

// that array in a variable at all, it just passes in the new array

// as a parameter. Guess what, you can do that too.

String word = WordGame.search(new String[0], letters);

if(word == null) {

return false;

}

if(word.compareTo("") != 0) {

return false;

}

return true;

}

/// Test checks whether search properly handles an empty set of letters.

/// search should return an empty string if it cannot match letters with

/// a word in the dictionary. letters contains nothing, so search

/// should return an empty string.

/// @return true if the test is successful; otherwise, the test fails.

public static boolean baseUnitTest10() {

String letters = "";

String word = WordGame.search(dictionary, letters);

if(word.compareTo("") != 0) {

return false;

}

return true;

}

/// Tests the case where a set of letters cannot be matched with any

/// word in the dictionary. The test is successful if search returns

/// an empty string "" and otherwise fails.

/// @return true if search returns an empty string; otherwise, false

public static boolean baseUnitTest11() {

// In this test, the word should not exist. This test is

// intentionally designed to search for a word that does not exist

// in the dictionary of words.

String letters = "aaaaaa";

String word = WordGame.search(dictionary, letters);

if(word.compareTo("") != 0) {

return false;

}

return true;

}

/// @return true if the test word is correctly identified in the set of

/// words; otherwise, returns false

public static boolean baseUnitTest12() {

String letters = "ionsomsti";

String word = WordGame.search(dictionary, letters);

if(word.compareTo("omission") != 0) {

return false;

}

return true;

}

/// Tests whether the first word is correctly identified. More than

/// one word may share the set of letters; however, requirements expect

/// search to return the first word in the dictionary that matches the

/// most characters

/// @return true if the earlist word among mulitple words is correctly

/// identified in the set of words; otherwise, returns false

public static boolean baseUnitTest13() {

String letters = "ddaz";

String word = WordGame.search(dictionary, letters);

// dad is a legal word from this set of letters, but it is not the

// first candidate; therefore, if word is dad, the test fails

if(word.compareTo("dad") == 0) {

return false;

}

// add is the first candidate word closest to the front of the

// dictionary that should match. Test successful if word is add

if(word.compareTo("add") != 0) {

return false;

}

return true;

}

/// This test is not really any different than the previous test, but it

/// does check for a long word

/// @return true if the test word correctly identified in the set of

/// words; otherwise, returns false

public static boolean baseUnitTest14() {

String letters = "abcdefghijklmnopqrstuvwxyz";

String word = WordGame.search(dictionary, letters);

if(word.compareTo("ambidextrous") != 0) {

return false;

}

return true;

}

//------------------------ Challenge Unit Tests ---------------------

/// This test validates that collect returns a null reference if the

/// dictionary passed to it is null

/// @return true if the test is successful; otherwise, the test fails.

public static boolean chalUnitTest1() {

String letters = "aaaaaa";

String[] words = WordGame.collect(null, letters);

if(words != null) {

return false;

}

return true;

}

/// This test validates that collect returns a null reference if the

/// set of letters passed to it is null

/// @return true if the test is successful; otherwise, the test fails.

public static boolean chalUnitTest2() {

String[] words = WordGame.collect(dictionary, null);

if(words != null) {

return false;

}

return true;

}

/// This test validates that collect returns an empty set of words when

/// a valid set of letters and a valid dictionary are passed to it

/// @return true if the test is successful; otherwise, the test fails.

public static boolean chalUnitTest3() {

String letters = "aaaaaa";

String[] words = WordGame.collect(dictionary, letters);

if(words == null) {

return false;

}

if(words.length != 0) {

//System.out.println(words);

return false;

}

return true;

}

/// This test validates that collect returns the correct set of words

/// when a valid set of letters and a valid dictionary are passed to it

/// @return true if the test is successful; otherwise, the test fails.

public static boolean chalUnitTest4() {

String letters = "ddaz";

String[] words = WordGame.collect(dictionary, letters);

if(words.length == 0 || words.length > 3) {

return false;

}

String[] expected = {"ad", "add", "dad"};

for(int i = 0; i

//System.out.println(words[i]);

boolean found = false;

for(int j = 0; j

if( words[i].compareTo(expected[j]) == 0 ) {

found = true;

break;

}

}

if( !found ) {

return false;

}

}

return true;

}

/// This test validates that collect returns the correct set of words

/// when a valid set of letters and a valid dictionary are passed to it

/// It is not really any different than the previous test other than

/// the set of found words is rather large

/// @return true if the test is successful; otherwise, the test fails.

public static boolean chalUnitTest5() {

String letters = "ionsomsti";

String[] words = WordGame.collect(dictionary, letters);

if(words.length == 0 || words.length > 45) {

return false;

}

String[] expected = {"ii", "in", "insist", "into", "ion", "is", "it", "mi", "min", "mini", "minot", "mint", "miss", "mission", "mist", "mitosis", "moist", "moo", "moon", "moot", "moss", "most", "mot", "motion", "nit", "no", "not", "oint", "omission", "omit", "on", "onto", "sin", "sis", "sit", "so", "son", "soon", "soot", "ti", "tin", "to", "ton", "too", "toss"};

for(int i = 0; i

//System.out.println(words[i]);

boolean found = false;

for(int j = 0; j

if( words[i].compareTo(expected[j]) == 0 ) {

found = true;

break;

}

}

if( !found ) {

return false;

}

}

return true;

}

}

public class WordGame {

// ---------------------------------------------------------------------

// Base

// ---------------------------------------------------------------------

/// contains determines whether word can be spelled using the characters

/// in letters

/// @param word the word that will try to be spelled

/// @param letters the set of letters with which to try to spell word

/// @return true if word can be spelled using letters; otherwise, false

static boolean contains(String word, String letters)

{

//TODO: FILL IN YOUR CODE HERE

// default assumption. you are welcome to change this as needed

return false;

}

/// search locates the longest word in the set of words that can be

/// spelled using the characters in letters.

/// @param letters the set of letters with which to try to spell word

/// @param words the dictionary of words that is to be searched

/// @return null if any of the parameters are invalid references, an

/// empty string if no word in words is found, or a word

/// selected from words if a word is found

public static String search(String[] words, String letters) {

//TODO: FILL IN YOUR CODE HERE

// default assumption. you are welcome to change this as needed

return "";

}

// ---------------------------------------------------------------------

// Challenge

// ---------------------------------------------------------------------

/// collect composes a list of all words in the set of words that can be

/// spelled using the characters in letters.

/// @param letters the set of letters with which to try to spell word

/// @param words the dictionary of words that is to be searched

/// @return null if any of the parameters are invalid references, an

/// empty array if no word in words is found, or the set of all

/// words selected from words that are found that can be spelled

/// using letters

static String[] collect(String[] words, String letters) {

//TODO: FILL IN YOUR CODE HERE

return null;

}

// ---------------------------------------------------------------------

// Utilities

// ---------------------------------------------------------------------

/// This method trims out all characters that are not alphas and then

/// converts the string to lowercase.

/// @param s the string to clean

/// @return the cleaned string

private static String clean(String s)

{

return s.replaceAll("[^a-zA-Z]","").toLowerCase();

}

}

import java.util.*;

class Countdown {

/// Takes unformatted string input from the console and returns it.

/// @return A string input from the console

static String getStringIn()

{

System.out.print( "Enter a set of characters: " );

Scanner scanner = new Scanner( System.in );

return scanner.nextLine( );

}

public static void main(String[] args) {

// Get the dictionary.

String[] dictionary = WordTool.getDictionary( );

// Get the set of letters

String letters = getStringIn();

// Search the dictionary for candidate words

String word = WordGame.search( dictionary, letters );

// Report the results

if( word == null ) {

System.err.println( "ERROR: Unhandled exception in WordGame.search" );

} else if( word == "" ) {

// output strings may violate conventions due to message lengths

System.out.println( "Could not find a word in the dictionary that can be spelled with the set of letters \"" + letters + "\"" );

} else {

// output strings may violate conventions due to message lengths

System.out.println( "The longest word found in the dictionary that can be spelled with the set of letters \"" + letters + "\" is \"" + word + "\"" );

}

}

}

Introduction This is intended to reinforce your understanding of working with one-dimensional arrays and to encourage you to think algorithmically. Your task is to develop an algorithm that solves the problem described using the provided framework. Countdown "Countdown" is a long running English gameshow where a number of games a featured. In one of the Countdown games, contestants are given a set of nine random letters which the contestants unscramble to find the longest word that they can make using a subset from the randomly chosen letters. For example, given the set of letters "Tonsomali", we can form the following words: "in", "insist", "mission", "mitosis", "omission". Out of these words, the longest word is "omission", 50 "omission" would be the winning word from the set of letters. Note that once a letter is used, it is removed/checked off and cannot be used again unless there are available uncheckedoff copies of that letter. For example, given a different but similar set of letters "ionsmati" where we no longer have a repeat 'o, we can still form the words "in", "insist", "mission", and "mitosis : however, we can no longer form the word "omission" because there are not enough o's in the set of letters. In this case, "mission" would be the winning word. In our game model, we will not bound the maximum number of characters in the set of letters. We will instead pass a string of letters and the string will dictate the maximum length of the available letters to choose from. If two words of the same length can be spelled by the set of words, we will choose the one that comes before the other in the dictionary as the winning word. Instructions This problem is similar to trying to find all anagrams in a dictionary for a given word or determining if a sentence is a pangram; however, it is slightly more challenging because there is no guarantee that it is possible to use all letters provided in the scrambled set of letters. We will use the WordTool class and a dictionary of words to try to find the longest word possible to form from the scramble. I have edited the words file to remove entries from the dictionary that contain special characters like contractions and abbreviations, so you should use the words file provided in the assignment file. A framework for this program has been provided which consists of the files Word Game.java, WordGameUnitTests.java, Countdown java, WordTooljava, and words. Your focus should be on implementing methods in the Word Game class; however, you will find the programs in the Word GameUnitTests and Countdown classes useful, both of which use the WordGame class. For the base implementation, you must implement the WordGame methods: - contains - Search There is an additional method for the challenge. You will receive no credit for the challenge if you have errors in your base implementation, so you should focus first on getting your base implementation fully working, debugged, and documented. For the challenge implementation, you must implement the WordGame method: . collectYou will not alter any of the other code in the framework, you will use the interfaces described later in this document "as is" for the above methods. In the framework, the methods that you will implement are marked with TODO. Read the documentation associated with each method and fulfill the requirements outlined by that method's documentation. search iterates over the a set of words or dictionary and then uses the contains method to determine whether that word can be spelled using a subset of provided letters. The contains method determines if the word is contained in the set of letters. Given the dependence of search on contains, ie. search must use contains and can therefore only work if contains works, you should focus on implementing contains first. The framework provides a set of "Unit Tests" to evaluate your algorithms. The unit tests specifically check the edge cases that you might not consider when developing your methods such as what should happen when a parameter is null. When you run the unit tests, if a test indicates a failure, you should look at the unit test file and see what conditions it checks which should lead you toward a correction in your method implementation. To receive full credit for the base implementation, your program must pass all base unit tests. To receive full credit for the challenge, your program must pass all challenge unit tests. There may be a number of words with the same length that can be formed using the set of letters. We do not necessarily need to know all words that can be formed using the set of letters in the base implentation, so search wil pick the first word in the dictionary that is the longest word. This offers a slight optimization but mostly it ensures that everyone gets the same answer to the first two unit tests. In the challenge, collect will build a new list of all the words that can be spelled with the set of characters. Once you have implemented your WordGame class and validated it with WordGameUnitTests, you can play the game interactively through the Countdown program. The Countdown program allows a user to input a set of letters at the command prompt and then searches the dictionary for the longest candidate word, and it is a basic simulation of the Countdown game. Notes A function clean has been provided that will remove any non-alpha characters from a string, will lowercase the cleaned string, and will return the lowercase, cleaned string. This method will ensure both that only legal letters are evaluated and will eliminate edge cases that we really don't want to deal with when preparing to compare string information. The methods are documented using a style defined by Doxygen. This format allows documentation to be automatically generated from source code. Note how this formal documents what a function does, what each of the inputs represents. and what the return value represents. In the future, your programs must include documentation of functions that you develop yourself, and your function documentation must meet these three criteria. You will not be expected to conform to the Doxygen format, but you will not be discouraged from doing so. Base Requirements The base assignment represents the minimal learning goal. boolean contains String word, String letters) contains determines whether the word specified by the parameter word can be spelled using the characters in the parameter letters. The parameter letters contains the set of letters with which to try to spell the word specified by the parameter word. This method returns true if word can be spelledusing letters; otherwise, the method returns false. There are some edge cases that must be addressed and these edge cases are clearly enumerated by the unit tests. In general, you need to handle what happens if any of the parameters are null. String search(String words, String letters) search searches through the dictionary of words provided by the words parameter and identifies the longest word that can be spelled using the characters provided by the letters parameter. search returns null if any of the parameters are invalid references, returns an empty string if no word is found, or retums the word if a ward is found. Again, there are a number of edge cases that must be addressed and these edge cases are enumerated by the unit tests and accompanying documentation. In addition to handling null parameters, you must also handle what happens when a second word is found that has the same length as an already identified word. Challenge Requirements String[ collect(String words, String letters) collect searches through the dictionary of words provided by the words parameter and identifies all words that can be spelled using the characters provided by the letters parameter. contains returns null if any of the parameters are invalid references, retums an empty amay if no words can be spelled, or the set of all words selected from words that can be spelled using letters. Again, there are a number of edge cases that must be addressed and these edge cases are enumerated by the unit tests and accompanying documentation. You must handle null parameters. You will also need to consider allocations of the array that you are building. FAQ 1. Can I use the AmayList class or any other advanced Java data structure? No. 2. Can I add one or more global variables? Sure, but that would probably be a mistake. You should focus on implementing the methods in WordGame.java, none of which require global variables. 3. Can I change the function retum type? No, the unit tests are designed to evaluate very specific criteria and the functions are specifically designed to plug in to the unit tests. If you change any function signature, i.e. the return type, name, and parameters, you will break the function and your program. Everyone must use the same function interfaces and everyone's code will tested against the same unit tests. 4. Can I change the function parameters? No, see the answer to the above question. 5. Can I add new functions? You mary, but for this particular assignment it is not necessary. Typically, when you define a new function, you must provide unit tests to validate the function and we will be using a rather strict set of unit tests so any custom unit tests you provide will probably be overlooked and not graded.B. Can I change any unit tests? Sort of. You may turn them on and off to help you get started or focus on particular problems; however, your program will have to pass all the unit tests, so don't forged to run the complete battery of tests. You should not permanently change the unit tests as that may mislead you with respect to the tests we will run. 7. Can I add new unit tests? We have tried to be comprehensive in the unit tests provided by testing the important edge cases. You should not need to add unit tests, but you are encouraged to study and understand them as this is a typical validation model and we will regularly use it to evaluate your work in this and future classes