Java Word Ladder Program output Stack Overflow Error

Question

I have to write the code in java for a word ladder program. The instructions are as follows:

Write a program using recursion to find the word ladder given a start word and an end word, or determines if no word ladder exists. Use the file "words.txt" as a dictionary of valid words. This file contains 87314 words. Your program does not need to find the shortest word ladder between words, any word ladder will do if one exists.

For example, starting from FISH you can make a word ladder to MAST through the following ladder:
         FISH, WISH, WASH, MASH, MAST

Here is the link for words.txt

I feel that my code is very close to working, but I am getting a stack overflow error on my output:

Exception in thread "main" java.lang.StackOverflowError
    at java.io.FileOutputStream.write(FileOutputStream.java:326)
    at java.io.BufferedOutputStream.flushBuffer(BufferedOutputStrea‌​m.java:82)
    at java.io.BufferedOutputStream.flush(BufferedOutputStream.java‌​:140)
    at java.io.PrintStream.write(PrintStream.java:482)
    at sun.nio.cs.StreamEncoder.writeBytes(StreamEncoder.java:221)
    at sun.nio.cs.StreamEncoder.implFlushBuffer(StreamEncoder.java:‌​291)
    at sun.nio.cs.StreamEncoder.flushBuffer(StreamEncoder.java:104)
    at java.io.OutputStreamWriter.flushBuffer(OutputStreamWriter.ja‌​va:185)

My code is as follows:

import java.util.Scanner; import java.io.FileNotFoundException; import java.io.FileInputStream; import java.io.File; import java.io.FileReader; import java.io.PrintWriter; import java.io.FileOutputStream;

public class C11PP8
{
  public static void main(String[] args)
  {
    Scanner inputStream = null;
    PrintWriter outputStream = null;
    int numWords = 0;
    String wordRead = "";
    String[] wordLibrary;
    String startWord, endWord;
    Scanner keyboard = new Scanner(System.in);
    int i;


    //open for writing four letter words
    try
    {
      outputStream = new PrintWriter(new FileOutputStream("FourLetterWords.txt"));
    }//end try

    catch(FileNotFoundException e)
    {
      System.out.println("File not found, program will close.");
      System.exit(0);
    }//end catch


    //open for reading all words
    try
    {
      inputStream = new Scanner(new FileReader("words.txt"));

    }//end try

    catch(FileNotFoundException e)
    {
      System.out.println("File not found, program will close.");
      System.exit(0);
    }//end catch

    while(inputStream.hasNextLine())
    {
      wordRead = inputStream.nextLine();
      if(wordRead.length() == 4)
      {
        wordRead = wordRead.toLowerCase();
        outputStream.println(wordRead);
      }
    }//end while loop

    inputStream.close();
    outputStream.close();

    //open for reading to count number of words
    try
    {
      inputStream = new Scanner(new FileReader("FourLetterWords.txt"));

    }//end try

    catch(FileNotFoundException e)
    {
      System.out.println("File not found, program will close.");
      System.exit(0);
    }//end catch

    while(inputStream.hasNextLine())
    {
      inputStream.nextLine();
      ++numWords;
    }//end while loop

    inputStream.close();

    //declare
    wordLibrary = new String[numWords];

    //open FourLetterWord to read
    //and populate the array of words
    try
    {
      inputStream = new Scanner(new FileReader("FourLetterWords.txt"));

    }//end try

    catch(FileNotFoundException e)
    {
      System.out.println("File not found, program will close.");
      System.exit(0);
    }//end catch

    i = 0;
    while(inputStream.hasNextLine())
    {
      wordLibrary[i] = inputStream.nextLine();
      ++i;
    }//end while loop

    inputStream.close();

    //confirm
    //for(i = 0; i < wordLibrary.length; ++i)
    //   System.out.println(wordLibrary[i]);

    //user input
    do
    {
      System.out.println("Enter your 4 letter start word: ");
      startWord = keyboard.nextLine();
    }while(startWord.length() != 4);
    startWord = startWord.toLowerCase();

    do
    {
      System.out.println("Enter your 4 letter end word: ");
      endWord = keyboard.nextLine();
    }while(endWord.length() != 4);
    endWord = endWord.toLowerCase();

    //call the recursive method
    findTheWord(startWord, endWord, wordLibrary);

  }//end main

  public static void findTheWord(String startWordPassed, String endWordPassed, String[] libraryPassed)
  {
    String currentWord = "";
    int count = 0;
    //base case
    if(endWordPassed.equals(startWordPassed))
    {
      System.out.println("Word found: " + endWordPassed);
    }//end if
    else
    {
      //change a single letter of the startWordPassed and make that the new startWordPassed
      // if the new word is in the array

      //OR

      //iterate through the array and find a word that is only one letter different than startWordPassed
      //make that the new startWordPassed

      for(int i = 0; i < libraryPassed.length; ++ i)
      {
        currentWord = libraryPassed[i];
        for(int j = 0; j < startWordPassed.length(); ++ j)
        {
          if(startWordPassed.charAt(j) == currentWord.charAt(j))
          ++count;
        }//end for loop
        if( count == 3)
        libraryPassed[i] = "    ";   
      }//end for loop
      System.out.println(currentWord);
      startWordPassed = currentWord;
      //recursive call
      findTheWord(startWordPassed, endWordPassed, libraryPassed);
    }//end else 
  }//end method

}//end class

The output that I am getting is multiple "zuni"'s and then the stack overflow. "zuni" is the last 4-letter word in the text document.

Any help with getting this to run correctly would be greatly appreciated.

Answer 1

Your recursive method should return something in order for the program to detect when the recursion needs to be stopped.

Moreover, your recursive method call should be called only if the condition is satisfied (count == 3).

Replace your findTheWord() method with:

public static boolean findTheWord(String startWordPassed, String endWordPassed, String[] libraryPassed)
{
    String currentWord = "";
    //base case
    if(endWordPassed.equals(startWordPassed))
    {
        System.out.println("Word found: " + endWordPassed);
        return true;
    }//end if
    else
    {
        for(int i = 0; i < libraryPassed.length; ++ i)
        {
            currentWord = libraryPassed[i];
            int count = 0;
            for(int j = 0; j < startWordPassed.length(); ++ j)
            {
                if(startWordPassed.charAt(j) == currentWord.charAt(j))
                    ++count;
            }//end for loop
            if(count == 3) {
                libraryPassed[i] = "    ";
                System.out.println(currentWord);
                startWordPassed = currentWord;
                //recursive call
                if (findTheWord(startWordPassed, endWordPassed, libraryPassed)) {
                    return true;
                }
            }
        }//end for loop
    }//end else

    return false;
}//end method

In order to cover the case when no ladder exists, then you can use the return value of the findTheWord() from within the main method:

public static void main(String[] args) {
    ...
    ...
    //call the recursive method
    if (!findTheWord(startWord, endWord, wordLibrary)) {
        System.out.println("No ladder exists");
    }
}

Answer 2

Use this method for the "findTheWord" and you will get the results as you wanted

public static void findTheWord(String startWordPassed,
        String endWordPassed, String[] libraryPassed) {
    String currentWord = "";
    int count = 0;
    // base case
    if (endWordPassed.equals(startWordPassed)) {
        System.out.println("Word found: " + endWordPassed);
    }// end if
    else {
        // change a single letter of the startWordPassed and make that the
        // new startWordPassed
        // if the new word is in the array

        // OR
        Map<String, Integer> index = new HashMap<String, Integer>();

        for (int i = 0; i < libraryPassed.length; i++) {
            index.put(libraryPassed[i], i);
        }
        System.out.println("Start Index:" + index.get(startWordPassed));
        System.out.println("End Index:" + index.get(endWordPassed));
        // iterate through the array and find a word that is only one letter
        // different than startWordPassed
        // make that the new startWordPassed
        System.out.println("Start Word:" + startWordPassed);
        int startIndex = index.get(startWordPassed) + 1;
        int endIndex = index.get(endWordPassed);
        for (int i = startIndex; i < endIndex; i++) {
            currentWord = libraryPassed[i];
            //System.out.println("current word:"+currentWord);
            count = 0;
            for (int j = 0; j < startWordPassed.length(); ++j) {
                if (startWordPassed.charAt(j) == currentWord.charAt(j))
                    ++count;
            }// end for loop
            if (count == 3)
            {
                startWordPassed = currentWord;
                System.out.println("Ladder Word:"+startWordPassed);
            }
        }// end for loop
    }// end else
}// end method