Problem Overview

The focus of the assignment is to implement a word connection game that has been played in one variation or another for almost 150 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.

cat, can, con, cog, dog cat, bat, eat, fat, gat, hat clash, flash, flask, flack, flock, clock, crock, crook, croon, crown, clown 

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 below), word ladders with minimum length for the start-end pairs above would be:

cat, cot, dot, dog cat, hat clash, class, claws, clows, clown 

Implementation Details

You must implement your solution to the assignment in terms of WordLadderGame, an interface that specifies all the behavior needed to calculate word ladders, and Doublets, the shell of a class that implements the WordLadderGame interface. You must provide a correct implementation of the Doublets class by completing its constructor and providing a correct implementation of each method. You must not change the WordLadderGame interface in any way. You must meet all the requirements specified and implied by the Javadoc comments in these files. You may add as many methods as you would like, and you may add as many nested classes as you would like. Although you may import other classes that are part of the JDK, the imports already provided are the suggested ones that you will need.

PLEASE FIX THE CODE BELOW:

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.HashSet; import java.util.LinkedList; import java.util.List; import java.util.Scanner; import java.util.TreeSet; import java.util.stream.Collectors; /** * Provides an implementation of the WordLadderGame interface. * * @author Your Name (you@auburn.edu) */ public class Doublets implements WordLadderGame { // The word list used to validate words. // Must be instantiated and populated in the constructor. ///////////////////////////////////////////////////////////////////////////// // DECLARE A FIELD NAMED lexicon HERE. THIS FIELD IS USED TO STORE ALL THE // // WORDS IN THE WORD LIST. YOU CAN CREATE YOUR OWN COLLECTION FOR THIS // // PURPOSE OF YOU CAN USE ONE OF THE JCF COLLECTIONS. SUGGESTED CHOICES // // ARE TreeSet (a red-black tree) OR HashSet (a closed addressed hash // // table with chaining). ///////////////////////////////////////////////////////////////////////////// /** * 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 { ////////////////////////////////////// // INSTANTIATE lexicon OBJECT HERE // ////////////////////////////////////// Scanner s = new Scanner(new BufferedReader(new InputStreamReader(in))); while (s.hasNext()) { String str = s.next(); ///////////////////////////////////////////////////////////// // INSERT CODE HERE TO APPROPRIATELY STORE str IN lexicon. // ///////////////////////////////////////////////////////////// s.nextLine(); } in.close(); } catch (java.io.IOException e) { System.err.println("Error reading from InputStream."); System.exit(1); } } ////////////////////////////////////////////////////////////// // ADD IMPLEMENTATIONS FOR ALL WordLadderGame METHODS HERE // ////////////////////////////////////////////////////////////// }