Okay so I posted a thread about my project before, how I need to create generated word ladders and all that. Now I am to the point where I need to create a method which will find the shortests path between a start word and an end word. For example:
startWord: Head
endWord: Feet
And then a wordLadder would be something like...
Head, Heat, Feat, Feet,
Now I know that I am expected to use a graph here, and I was suggested to use a Breath First Search as I believe this works between two points or something along those lines. Expect I am not sure how to use this with my program. Here is my current code to give you guys an idea of how I made the program so far.
I've bolded and put the discover method in Italic to make sure it stands out more than the other methods, easier to read hopefully...
Quote:
package uk.ac.aber.dcs.cs21120.wordplay.data;
import java.util.*;
import java.io.*;
/**
* This class has all the records to run the menu aspect to the game,
* as well as the main method to start the program.
*/
public class WordLadder {
private String word;
private ArrayList<String> words = new ArrayList<String>();
private String fileName = "";
private InputStream in;
private BufferedReader buf;
private int number;
private Hashtable<String,String> hashWords;
private Scanner scan, scanGen;
/**
* This is the method for the WordLadder class, though it wouldn't have anything added to it.
*/
public WordLadder() {
}
/**
* This method is used to read in what the user enters at the start of the program,
* and then load a dictionary text file depending on the value they entered.
*/
public void initialize() {
in = System.in; //keyboard input
scan = new Scanner(in);
/*
* Ask user for length of word input.
*/
System.out.println("How many characters does the word contain?\n" +
"Enter a value between 2 and 7 inclusive.");
String wordLength = scan.nextLine();
int wl = 0;
try {
wl = Integer.parseInt(wordLength);
} catch (NumberFormatException e) {
wl = 0;
}
while (!((wl>=2)&&(wl<=7))) {
System.out.println("Sorry, could not understand your request.\n" +
"Re-enter a value between 2 and 7 inclusive.");
wordLength = scan.nextLine();
try {
wl = Integer.parseInt(wordLength);
//used to turn any input that isn't a number into '0'.
} catch (NumberFormatException e) {
wl = 0;
}
}
fileName = "dict" + wordLength + ".dat";
readFromFile(fileName);
}
/**
*
* @param fileName -
*/
public void readFromFile(String fileName) {
words.clear();
try {
/*
* Construct the BufferedReader object
*/
buf = new BufferedReader(new FileReader(fileName));
String line = null;
while ((line = buf.readLine()) != null) {
/*
* Process the data, here we just print it out
*/
words.add(line);
}
} catch (FileNotFoundException ex) {
System.out.println("Sorry this file could not be found.");
ex.printStackTrace();
this.initialize();
} catch (IOException ex) {
ex.printStackTrace();
this.initialize();
} finally {
/*
* Try-Catch to close the BufferedReader
*/
try {
if (buf != null)
buf.close();
} catch (IOException ex) {
ex.printStackTrace();
this.initialize();
}
/*
* Create the HashTable with the same capacity as the number of words
* in the ArrayList (Dictionary)
*/
hashWords = new Hashtable<String,String>(words.size());
/*
* Loop through the ArrayList and place each word into the HashTable.
*/
for (String w: words)
{
hashWords.put(w,w);
}
}
}
/**
* This is used to create a word ladder of word between the values of 2 and 8.
* This is done by using methods from the class including validate and searchForNewWord,
* while also using ArrayLists and a HashTable.
* @throws IOException - Input/Output Exception for any invalid string text
* entered when scanners ask for them.
*/
public void generate() throws IOException {
int stepNumber=0;
scanGen = new Scanner(in);
/*
* Ask user for word input.
*/
System.out.println("What word would you like to use?");
String userWord=scanGen.nextLine();
userWord=userWord.toLowerCase();
/*Must check that the word is in the dictionary.
* Calls validate() method.
*/
if(!(validate(userWord))) {
System.out.println("Sorry, this word is not in my dictionary." +
" Please try again.");
return;
}
System.out.println("How many Numbers do you want generated?\n" +
"Enter a value between 2 and 8 inclusive.");
try {
stepNumber = Integer.parseInt(scanGen.nextLine());
}
catch (NumberFormatException e) {
stepNumber = 0;
}
/*
* Must check if stepNumber is more than or equal to 2 or less than or equals to 8
*/
while (!((stepNumber>=2)&&(stepNumber<=8))) {
System.out.println("Sorry, could not understand your request.\n" +
"Re-enter a value between 2 and 8 inclusive.");
try {
stepNumber = Integer.parseInt(scanGen.nextLine());
}
catch (NumberFormatException e) {
stepNumber = 0;
}
}
/*
* Calls the searchForNewWord() method for passing in the userWord and stepNumber
*/
String ladder = "Your word ladder is\n" + userWord + "\n";
String nextWord;
ArrayList<String> ladderWords = new ArrayList<String>();
ladderWords.add(userWord);
for(int g=0;g<stepNumber-1;g++) {
nextWord = searchForNewWord(userWord);
/*if(nextWord==null) {
System.out.println("Sorry, I could only find " + (g+1) + " steps for this ladder.");
break;
}
else if(ladderWords.contains(nextWord)) {
g--;
}*/
if(nextWord==null) {
System.out.println("Sorry, I could only find " + (g+1) + " steps for this ladder.");
break;
}
if(ladderWords.contains(nextWord)) {
System.out.println("Sorry, I could only find " + (g+1) + " steps for this ladder.");
break;
//g--; Infinite loop?
}
else {
userWord = nextWord;
ladderWords.add(userWord);
ladder = ladder +nextWord+"\n";
}
}
System.out.println(ladder);
}
/**
* validate is used to check if the userWord (which the user has input) is
* actually in the text file.
* @param wordToCheck - which is the userWord.
* @return true or false.
*/
public boolean validate(String wordToCheck) {
if(hashWords.contains(wordToCheck)) {
return true;
}
else {
return false;
}
}
/**
* This method is used to search for a new word while removing the word that was
currently used to search for this new word.
* @param word - This is the word that is entered by the user.
* @return
*/
public String searchForNewWord(String word) {
String userWord = word;
int numChars = userWord.length();
ArrayList<String> pileWords = new ArrayList<String>();
/*
* finds all words for the amount of steps given, so a loop is needed
*/
for(String w:words) {
int match = 0;
for(int p=0;p<numChars;p++) {
if(w.charAt(p)==userWord.charAt(p)) {
match++;
}
}
if(match==numChars-1) {
pileWords.add(w);
}
}
int pileNumber = pileWords.size();
if(pileNumber==0) {
return null;
}
else if(pileNumber==1) {
return pileWords.get(0);
}
/*
* A Random() is used to produce a random selection of pileWords
* from the pileNumber arrayList.
*/
else {
Random rand = new Random();
int ranWord = rand.nextInt(pileNumber);
return pileWords.get(ranWord);
}
}
public void discover() {
//get word from user
//Ask user for starting word.
System.out.println("What word would you like to start with?");
String startWord=scanGen.nextLine();
startWord=startWord.toLowerCase();
//Must check that the starting word is in the dictionary.
if(!(validate(startWord))) {
System.out.println("Sorry, this word is not in my dictionary." +
" Please try again.");
return;
}
//Ask user for step number input.
System.out.println("What word would you like to find the path to?");
String endWord=scanGen.nextLine();
endWord=endWord.toLowerCase();
//Must check that the ending word is also in the dictionary.
if(!(validate(endWord))) {
System.out.println("Sorry, this word is not in my dictionary." +
" Please try again.");
return;
}
String wordPath;
String ladder = "The shortest word path between " +startWord+ " and "
+endWord+ " is\n" + wordPath + "\n";
ArrayList<String> ladderWords = new ArrayList<String>();
ladderWords.add(startWord);
ladderWords.add(endWord);
}
/**
* This runMenu() method runs the many options that are linked to the printMenu() method.
* @throws IOException - This Input Output Exception is used in case any input that
* isn't shown in the menu commands is entered.
*/
public void runMenu()throws IOException{
String response="";
do {
printMenu();
response=scan.next();
if (response.equals("1")|| response.equals("Generate")|| response.equals("exit")) {
generate();
}
else if (response.equals("2")|| response.equals("Discover")|| response.equals("discover")) {
discover();
}
else if (response.equals("3")|| response.equals("Re-Enter")|| response.equals("re-enter")|| response.equals("Reenter")|| response.equals("reenter")) {
initialize();
}
else if (response.equals("Q")|| response.equals("q")|| response.equals("Quit")|| response.equals("quit")) {
System.out.println("Thanks you for using Word Play, I hope you enjoyed your time!");
}
else {
System.out.println("Sorry, didn't quite get that. Could you repeat yourself?");
}
} while (! ( (response.equals("Q")|| (response.equals("q")|| response.equals("Quit")|| response.equals("quit")))));
}
/**
* printMenu() method runs from the menu and shows all commands for the runMenu() method.
* This shows what the main menu will looks like when it is run from the 'WordPlay'class.
*/
private void printMenu() {
System.out.println("What would you like to do?");
System.out.println("1 - Generate");
System.out.println("2 - Discover");
System.out.println("3 - Re-enter character length");
System.out.println("Q - Quit the game");
}
}
Depending if I cant understand graphs in the next hour or not, I may be able to edit in my other problems I am having, otherwise explaining to to use BFS Graphs would be brilliant, especially in this example.