Provides an implementation of the WordLadderGame interface. The lexicon is store
ID: 3917487 • Letter: P
Question
Provides an implementation of the WordLadderGame interface. The lexicon is stored as a HashSet of Strings.
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.stream.Collectors;
/**
* Provides an implementation of the WordLadderGame interface. The lexicon
* is stored as a HashSet of Strings.
*
* @author Your Name (you@auburn.edu)
* @author Dean Hendrix (dh@auburn.edu)
* @version 2018-04-06
*/
public class Doublets implements WordLadderGame {
// The word list used to validate words.
// Must be instantiated and populated in the constructor.
private HashSet<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 HashSet<String>();
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 //
//////////////////////////////////////////////////////////////
}
Explanation / Answer
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;
/**
* Provides an implementation of the WordLadderGame interface. The lexicon
* is stored as a HashSet of Strings.
*
* @author Your Name (you@auburn.edu)
* @author Dean Hendrix (dh@auburn.edu)
* @version 2018-04-06
*/
public class Doublets implements WordLadderGame {
// The word list used to validate words.
// Must be instantiated and populated in the constructor.
private final List<Node> nodeQ= new LinkedList<>();
private final HashSet<Node> visitedNode= new HashSet<>();
private final String in;
private final String target;
private HashSet<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 HashSet<String>();
Scanner s =new Scanner(new BufferedReader(new InputStreamReader(in)));
while (s.hasNext()) {
String str = s.next();
lexicon.add(str);
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 //
//////////////////////////////////////////////////////////////
public WordLadder(String i, String t){
in=i;
target= t;
}
public static void main(String[] args) throws IOException {
WordLadder wl= new WordLadder("stone","money");
wl.loadDictionary();
if(!wl. lexicon.contains(wl.in)||!wl. lexicon.contains(wl.target)){
System.out.println("error words not in lexicon ");
}
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);
visitedNode.add(n);
}
System.out.println("nodeQ- "+nodeQ);
System.out.println("visitedNode - "+ visitedNode);
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;
}
}
return sel;
}
//Add next combinations to the nodeQ
private void addNextWordsToQ(Node n){
String s= n.str;
for(int i=0;i<s.length();i++){
String regex= s.substring(0,i)+"."+s.substring(i+1);
Pattern p= Pattern.compile(regex);
for(String d: lexicon){
Matcher m= p.matcher(d);
if(!d.equals(s) && s.length()==d.length()
&& m.find() && !isNodeVisited(d)){
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: visitedNode){
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){
lexicon.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+ "";
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.