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.

Exception in thread "main" java.lang.StackOverflowError at java.io.FileOutputStream.write(FileOutputStream.java:326) at java.io.BufferedOutputStream.flushBuffer(BufferedOutputStream.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.java:185) — Sheriff44, Dec 08 '16 at 17:33
Also, see this http://stackoverflow.com/questions/214741/what-is-a-stackoverflowerror There is likely a loop in the recursive `findTheWord` function calls causing the program to run out of stack memory. — Boo Radley, Dec 08 '16 at 17:37
Look at this logically. You know the problem is a stack overflow, you know it's caused within a `FileOutputStream`. Where do you have a `FileOutputStream` within a loop? Start looking for your problem there. The single greatest command in Java is `System.out.println("here");`. Use it to track where your program is. — MrB, Dec 08 '16 at 18:10

sanastasiadis · Answer 1 · 2016-12-09T09:55:01.870

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");
    }
}

Thank you sanastasiadis. I hadn't considered creating a boolean method, but this works the way I need it to. Much appreciated. — Sheriff44, Dec 10 '16 at 19:00
Do you want to accept it as an answer to your question here in SO? — sanastasiadis, Dec 12 '16 at 11:23

score -1 · Answer 2 · answered Dec 08 '16 at 18:05

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

Why do you limit the search area between the start and the end index? — sanastasiadis, Dec 08 '16 at 18:17
My understanding initially was to check the Ladder words in between the 2 words, if that is not the case, the end index can be removed which is very simple — murthy, Dec 09 '16 at 03:22
The startIndex and the endIndex are the main contributions of your code, that is not solving the problem. If we remove them, then the code will be as the code of the question, that is causing a stack overflow. — sanastasiadis, Dec 09 '16 at 09:08
The Original problem is taking the Start and End Words and the expectation is to find the Ladder words in between. So my solution holds good. Regarding the Stack Overflow problem that is reported, there is a a. Recursive Call b. n is not intialized in the loop — murthy, Dec 09 '16 at 09:37
[Ladder steps](https://en.wikipedia.org/wiki/Word_ladder) are between words that differ for only 1 letter. That's why we go from FISH to WISH or DISH. The position of the words in the words.txt is of no interest. — sanastasiadis, Dec 09 '16 at 09:40
@sanastasiadis Try running the Original code provided by sheriff and see that it is asking the start and the end words and his expectation was to get the data in between of them. but not from the whole list of words — murthy, Dec 09 '16 at 10:32
The expectation is to find a word ladder connecting the given start word and the given end word. I don't see any requirement restriction about positioning of the words in the words.txt. — sanastasiadis, Dec 09 '16 at 10:40

Java Word Ladder Program output Stack Overflow Error

2 Answers2