Problem Overview When I was a sophomore in college, I found myself in what would
ID: 3691788 • Letter: P
Question
Problem Overview When I was a sophomore in college, I found myself in what would turn out to be the most influential course that I’ve 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.” It’s 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 can’t add any public
methods. You may add as many nested classes as you would like, but you can’t 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<String> 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<String> 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<String> 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<String> 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<String> EMPTY_LADDER = new ArrayList<>();
// The word list used to validate words.
// Must be instantiated and populated in the constructor.
TreeSet<String> 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<String>();
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. //
///////////////////////////////////////////////////////////////////////////////
}
Explanation / Answer
Please follow the code and the comments for description of the code :
As the code posted is having some bugs and to remove the confusion I am posting the new code. So please check it out :
CODE :
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class WordLadder {
private final HashSet<String> dic= new HashSet<>();
private final List<Node> nodeQ= new LinkedList<>();
private final HashSet<Node> visitedNodes= new HashSet<>();
private final String in;
private final String target;
public WordLadder(String i, String t){
in=i;
target= t;
}
public static void main(String[] args) throws IOException {
WordLadder wl= new WordLadder("stone","money");
//WordLadder wl= new WordLadder("stone","chore");
//WordLadder wl= new WordLadder("stone","choky");
//WordLadder wl= new WordLadder("charge","comedo"); //takes time ~ 3 mins- seems hardest
wl.loadDictionary();
if(!wl.dic.contains(wl.in)||!wl.dic.contains(wl.target)){
System.out.println("error words not in dic");
}
wl.nodeQ.add(new Node(wl.in));
wl.getPaths();
}
private void getPaths(){
long st= System.currentTimeMillis();
while(!isMatchFound()){
Node n= selectNext();
nodeQ.remove(n);
addNextWordsToQ(n);
visitedNodes.add(n);
}
System.out.println("nodeQ- "+nodeQ);
System.out.println("visitedNodes- "+visitedNodes);
long end= System.currentTimeMillis();
System.out.println("time taken in sec~ "+ (end-st)/1000);
System.out.println("time taken in min~ "+ (end-st)/60000);
}
private Node selectNext(){
Node sel= null;
int minMatch=-1;
int match;
for(Node n: nodeQ){
match=0;
for(int i=0; i<target.length(); i++){
if(n.str.charAt(i)== target.charAt(i)) {
match++;
}
}
if(match>minMatch){
sel=n;
minMatch=match;
}
}
// System.out.println(sel.str+" "+minMatch);
return sel;
}
static private int hammingDistance(String s1, String s2) {
assert(s1.length() == s2.length();
int distance = 0;
for (int i = 0; i < s1.length(); ++i) {
distance += (s1.charAt(i) != s2.charAt(i));
}
return distance;
}
//Add next possible combinations to the nodeQ
private void addNextWordsToQ(Node n) {
for (String candidate: subdict) {
if ((!isNodeVisited(d) && (hammingDistance(n.str, d) == 1)) {
nodeQ.add(new Node(d, n));
}
}
}
//Check nodeQ to see if word ladder is solved
private boolean isMatchFound(){
for(Node n: nodeQ){
if(target.equals(n.str)){
System.out.println(n);
return true;
}
}
return false;
}
private boolean isNodeVisited(String add){
for(Node n: visitedNodes){
if(n.str.equals(add)){
return true;
}
}
return false;
}
private void loadDictionary() throws IOException{
InputStream is= WordLadder.class.getClassLoader().getResourceAsStream("dictionary.txt");
BufferedReader br= new BufferedReader(new InputStreamReader(is));
String s= br.readLine();
while(s!=null){
dic.add(s);
s= br.readLine();
}
}
}
class Node{
String str;
final List<String> path= new ArrayList<>();
public Node(String str){
this.str=str;
}
public Node(String str, Node parent){
this.str=str;
path.addAll(parent.path);
path.add(parent.str);
}
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((str == null) ? 0 : str.hashCode());
return result;
}
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Node other = (Node) obj;
if (str == null) {
if (other.str != null)
return false;
} else if (!str.equals(other.str))
return false;
return true;
}
public String toString() {
return " " + str + ", " + path+ "";
}
}
dictionary.txt can be of a file with the user desired strings.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.