Here is the provided WordLadderGame.java file:

1 import java.util.List; 2 3 /** 4 * WordLadderGame.java Defines an interface for games that construct word 5 * ladders. See https://en.wikipedia.org/wiki/Word_ladder for a definition and 6 * history. 7 * 8 * Word ladders are constructed in the context of some predefined list of valid 9 * words. We will refer to this word list as the lexicon. An implementing class 10 * of this interface must provide a way to explicitly set the lexicon. This will 11 * typically be done in the constructor. 12 * 13 * For the purposes of this interface and all implementing classes, a string is 14 * a word if and only if it appears in the current lexicon. In the documentation 15 * of each interface method, the use of 'string' means that the referenced 16 * string does not have to be a word, while the use of 'word' implies that the 17 * referenced string must be a word. 18 * 19 */ 20 public interface WordLadderGame { 21 22 /** 23 * Returns the Hamming distance between two strings, str1 and str2. The 24 * Hamming distance between two strings of equal length is defined as the 25 * number of positions at which the corresponding symbols are different. The 26 * Hamming distance is undefined if the strings have different length, and 27 * this method returns -1 in that case. See the following link for 28 * reference: https://en.wikipedia.org/wiki/Hamming_distance 29 * 30 * @param str1 the first string 31 * @param str2 the second string 32 * @return the Hamming distance between str1 and str2 if they are the 33 * same length, -1 otherwise 34 */ 35 int getHammingDistance(String str1, String str2); 36 37 38 /** 39 * Returns a word ladder from start to end. If multiple word ladders exist, 40 * no guarantee is made regarding which one is returned. If no word ladder exists, 41 * this method returns an empty list. 42 * 43 * Depth-first search with backtracking must be used in all implementing classes. 44 * 45 * @param start the starting word 46 * @param end the ending word 47 * @return a word ladder from start to end 48 */ 49 List getLadder(String start, String end); 50 51 52 /** 53 * Returns a minimum-length word ladder from start to end. If multiple 54 * minimum-length word ladders exist, no guarantee is made regarding which 55 * one is returned. If no word ladder exists, this method returns an empty 56 * list. 57 * 58 * Breadth-first search must be used in all implementing classes. 59 * 60 * @param start the starting word 61 * @param end the ending word 62 * @return a minimum length word ladder from start to end 63 */ 64 List getMinLadder(String start, String end); 65 66 67 /** 68 * Returns all the words that have a Hamming distance of one relative to the 69 * given word. 70 * 71 * @param word the given word 72 * @return the neighbors of the given word 73 */ 74 List getNeighbors(String word); 75 76 77 /** 78 * Returns the total number of words in the current lexicon. 79 * 80 * @return number of words in the lexicon 81 */ 82 int getWordCount(); 83 84 85 /** 86 * Checks to see if the given string is a word. 87 * 88 * @param str the string to check 89 * @return true if str is a word, false otherwise 90 */ 91 boolean isWord(String str); 92 93 94 /** 95 * Checks to see if the given sequence of strings is a valid word ladder. 96 * 97 * @param sequence the given sequence of strings 98 * @return true if the given sequence is a valid word ladder, 99 * false otherwise 100 */ 101 boolean isWordLadder(List sequence); 102 }

Doublets.java file:

1 import java.io.BufferedReader; 2 import java.io.InputStream; 3 import java.io.InputStreamReader; 4 5 import java.util.Arrays; 6 import java.util.ArrayDeque; 7 import java.util.ArrayList; 8 import java.util.Deque; 9 import java.util.LinkedList; 10 import java.util.List; 11 import java.util.Scanner; 12 import java.util.TreeSet; 13 14 /** 15 * Doublets.java 16 * Provides an implementation of the WordLadderGame interface. The lexicon 17 * is stored as a TreeSet of Strings. 18 * 19 */ 20 public class Doublets implements WordLadderGame { 21 22 //////////////////////////////////////////// 23 // DON'T CHANGE THE FOLLOWING TWO FIELDS. // 24 //////////////////////////////////////////// 25 26 // A word ladder with no words. Used as the return value for the ladder methods 27 // below when no ladder exists. 28 List EMPTY_LADDER = new ArrayList(); 29 30 // The word list used to validate words. 31 // Must be instantiated and populated in the constructor. 32 TreeSet lexicon; 33 35 /** 36 * Instantiates a new instance of Doublets with the lexicon populated with 37 * the strings in the provided InputStream. The InputStream can be formatted 38 * in different ways as long as the first string on each line is a word to be 39 * stored in the lexicon. 40 */ 41 public Doublets(InputStream in) { 42 try { 43 lexicon = new TreeSet(); 44 Scanner s = 45 new Scanner(new BufferedReader(new InputStreamReader(in))); 46 while (s.hasNext()) { 47 String str = s.next(); 48 //////////////////////////////////////////////// 49 // Add code here to store str in the lexicon. // 50 //////////////////////////////////////////////// 51 s.nextLine(); 52 } 53 in.close(); 54 } 55 catch (java.io.IOException e) { 56 System.err.println("Error reading from InputStream."); 57 System.exit(1); 58 } 59 } 60 61 /////////////////////////////////////////////////////////////////////////////// 62 // Fill in implementations of all the WordLadderGame interface methods here. // 63 /////////////////////////////////////////////////////////////////////////////// 64 65 }

The focus of the assignment is to implement a word connection game that has been played in one variation or another for at least 130 years. The object of the game is to transform a start word into an end word of the same length by a sequence of steps, each of which consists ofA a one-letter change to the current word that results in another legal word. Charles Lutwidge Dodsgon (Lewis Carroll) invented this game and called it "Doublets.It's now more commonly known as "Word Lad ders." Consider the following examples clash, flash, fiask, fiack, flock, clock, crock, crook, croon, crown, clowm cat, can, con, cog, dog cat, bat, eat, fat, gat, hat Each is a valid word ladder from the start word to the end word since the start and end words are the same length and each word in between is exactly one letter different from the previous word. The game is usually played so that each player tries to find the shortest word ladder between two words. The shortest ladder would, of course, depend on the lericon, or list of words, being used for the game. Using the SOWPODS word list (see Provided Resources), word ladders with minimum length for the start-end pairs above would be: clash, class, claus, clows, clowm cat, cot, dot, dog cat, hat Requirements The interface WordLadderGame defines several methods associated with the generation of word ladders. The class Doublets provides an implementation of this interface. You must provide a correct implemn