Problem Overview When I was a sophomore in college, I found myself in what would turn out to be the most influential course that Ive ever taken. Everything about the course was in some way exceptional, but the professor particularly so. She made what could have been an ordinary English Composition class into an examination of thinking. One of the recurring themes in the class was making connections the process that allows us to associate things and see relationships among different things. So, in honor and memory of O.A.L., this assignment is all about making connections. 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 of 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. Its now more commonly known as Word Ladders. Consider the following examples. clash, flash, flask, flack, flock, clock, crock, crook, croon, crown, clown 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 lexicon, 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, claws, clows, clown 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 implementation of the Doublets class by completing its constructor and providing a correct implementation of each WordLadderGame method. You must meet all the requirements specified and implied by the Javadoc comments in these files. You may add as many private methods as you would like, but you cant add any public methods. You may add as many nested classes as you would like, but you cant add any top-level classes. Although you may import other classes that are part of the JDK, the imports already provided are the suggested ones that you will need.

WordLadderGame.java

import java.util.List;

/** * WordLadderGame.java Defines an interface for games that construct word * ladders. See https://en.wikipedia.org/wiki/Word_ladder for a definition and * history. * * Word ladders are constructed in the context of some predefined list of valid * words. We will refer to this word list as the lexicon. An implementing class * of this interface must provide a way to explicitly set the lexicon. This will * typically be done in the constructor. * * For the purposes of this interface and all implementing classes, a string is * a word if and only if it appears in the current lexicon. In the documentation * of each interface method, the use of 'string' means that the referenced * string does not have to be a word, while the use of 'word' implies that the * referenced string must be a word.

public interface WordLadderGame {

/** * Returns the Hamming distance between two strings, str1 and str2. The * Hamming distance between two strings of equal length is defined as the * number of positions at which the corresponding symbols are different. The * Hamming distance is undefined if the strings have different length, and * this method returns -1 in that case. See the following link for * reference: https://en.wikipedia.org/wiki/Hamming_distance * * @param str1 the first string * @param str2 the second string * @return the Hamming distance between str1 and str2 if they are the * same length, -1 otherwise */ int getHammingDistance(String str1, String str2);

/** * Returns a word ladder from start to end. If multiple word ladders exist, * no guarantee is made regarding which one is returned. If no word ladder exists, * this method returns an empty list. * * Depth-first search with backtracking must be used in all implementing classes. * * @param start the starting word * @param end the ending word * @return a word ladder from start to end */ List getLadder(String start, String end);

/** * Returns a minimum-length word ladder from start to end. If multiple * minimum-length word ladders exist, no guarantee is made regarding which * one is returned. If no word ladder exists, this method returns an empty * list. * * Breadth-first search must be used in all implementing classes. * * @param start the starting word * @param end the ending word * @return a minimum length word ladder from start to end */ List getMinLadder(String start, String end);

/** * Returns all the words that have a Hamming distance of one relative to the * given word. * * @param word the given word * @return the neighbors of the given word */ List getNeighbors(String word);

/** * Returns the total number of words in the current lexicon. * * @return number of words in the lexicon */ int getWordCount();

/** * Checks to see if the given string is a word. * * @param str the string to check * @return true if str is a word, false otherwise */ boolean isWord(String str);

/** * Checks to see if the given sequence of strings is a valid word ladder. * * @param sequence the given sequence of strings * @return true if the given sequence is a valid word ladder, * false otherwise */ boolean isWordLadder(List sequence); }

ExampleClient.java

import java.io.File; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Arrays; import java.util.List;

/** * ExampleClient.java * Provides example calls to WordLadderGame methods in an instance of * the Doublets class. * * The word list files must be extracted into the current directory * before running this class. * * jar xf WordLists.jar * */ public class ExampleClient {

/** Drives execution. */ public static void main(String[] args) throws FileNotFoundException { WordLadderGame doublets = new Doublets(new FileInputStream(new File("sowpods.txt")));

System.out.println(doublets.getHammingDistance("tiger", "tiger")); System.out.println(doublets.getHammingDistance("tiger", "eagle")); System.out.println(doublets.getHammingDistance("war", "eagle")); System.out.println(doublets.getHammingDistance("barner", "bammer"));

System.out.println(doublets.isWord("tiger")); System.out.println(doublets.isWord("eagle")); System.out.println(doublets.isWord("aubie"));

System.out.println(doublets.getWordCount());

System.out.println(doublets.isWordLadder(Arrays.asList("cat", "cot", "zot", "dot"))); System.out.println(doublets.isWordLadder(Arrays.asList("cat", "cot", "pot", "dot")));

System.out.println(doublets.getNeighbors("tiger"));

System.out.println(doublets.getLadder("cat", "hat"));

System.out.println(doublets.getMinLadder("cat", "hat")); } }

/*

RUNTIME OUTPUT

0 4 -1 2 true true false 267751 false true [liger, niger, tiler, timer, titer, tiges] [cat, bat, eat, fat, gat, hat] [cat, hat]

*/

Doublets.java

import java.io.BufferedReader; import java.io.InputStream; import java.io.InputStreamReader;

import java.util.Arrays; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Deque; import java.util.LinkedList; import java.util.List; import java.util.Scanner; import java.util.TreeSet;

/** * Doublets.java * Provides an implementation of the WordLadderGame interface. The lexicon * is stored as a TreeSet of Strings. * */ public class Doublets implements WordLadderGame {

//////////////////////////////////////////// // DON'T CHANGE THE FOLLOWING TWO FIELDS. // ////////////////////////////////////////////

// A word ladder with no words. Used as the return value for the ladder methods // below when no ladder exists. List EMPTY_LADDER = new ArrayList<>();

// The word list used to validate words. // Must be instantiated and populated in the constructor. TreeSet lexicon;

/** * Instantiates a new instance of Doublets with the lexicon populated with * the strings in the provided InputStream. The InputStream can be formatted * in different ways as long as the first string on each line is a word to be * stored in the lexicon. */ public Doublets(InputStream in) { try { lexicon = new TreeSet(); Scanner s = new Scanner(new BufferedReader(new InputStreamReader(in))); while (s.hasNext()) { String str = s.next(); //////////////////////////////////////////////// // Add code here to store str in the lexicon. // //////////////////////////////////////////////// s.nextLine(); } in.close(); } catch (java.io.IOException e) { System.err.println("Error reading from InputStream."); System.exit(1); } }

/////////////////////////////////////////////////////////////////////////////// // Fill in implementations of all the WordLadderGame interface methods here. // ///////////////////////////////////////////////////////////////////////////////

}