Here is the provided WordLadderGame.java file: 1 import java.util.List; 2 3 /**

Question

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<String> 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<String> 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<String> 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<String> 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<String> EMPTY_LADDER = new ArrayList<>();
29
30 // The word list used to validate words.
31 // Must be instantiated and populated in the constructor.
32 TreeSet<String> 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<String>();
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

Explanation / Answer

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<String> 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<String> 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<String> 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<String> 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
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<String> EMPTY_LADDER = new ArrayList<>();
29
30 // The word list used to validate words.
31 // Must be instantiated and populated in the constructor.
32 TreeSet<String> 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<String>();
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 ///////////////////////////////////////////////////////////////////////////////

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---