// WordLadder.java
// from https://rosettacode.org/wiki/Word_ladder#Java
// Modified by Andrew Davison, ad@coe.psu.ac.th, Dec. 2022

/* The program is supplied with two words -- a begin word and
   an end word, and attempts to convert the first into the 
   second by changing one letter at a time. 
   Each change represents one step (rung) in a ladder.

   The other aim to create a ladder with the shortest number of steps.

   I've coded two versions of this problem -- the one here, and 
   Doublets.java (doublets is Lewis Carroll's name for these puzzles).

   For more on word ladders, see
   https://en.wikipedia.org/wiki/Word_ladder

   Two other great resources:

     * "Selected Papers on Fun and Games", Donald E. Knuth,
       CSLI Lecture Notes no. 192, CSLI Pub., 2010,
       chapters 32, 33, 34. Chapters 32 and 33 originally
       appeared in "Games" magazine, No. 6, July 1978, which
       is online at
       https://archive.org/details/games-6-1978-july/page/n3/mode/2up

    * "A Gardner’s Workout", Martin Gardner, 
       A.K. Peters, 2001, chapter 18.

   The code here loads a file of dictionary words (words.txt), and
   optimizes the search by only keeping those words of the same length
   as the begin and end words. The code also deletes used words from the 
   list during execution. Neither of these optimizations is
   possible with Hunspell, so I decided to code both versions to 
   compare their ladder lengths and speeds.

   This version uses breadth-first search, where multiple developing
   ladders are inverstigated in turn, with each one being extended by one
   step. Since many extensions are normally possible, a single
   ladder at one level will normally be replaced by multiple 
   extensions at the next level.

   The Hunspell version uses a priority queue and a simple scoring
   scheme to indicate if a word is a good candidate to change. Higher scoring
   words are processed first.

   The two versions take about the same time to find typical ladders,
   but the BFS ladders are sometimes shorter. The problem is due to
   the scoring code in the Hunspell version which means that once a letter is 
   used that is in its correct position in the end word, it will 
   not be changed again. This can lead to long ladders in some cases. 

   Usage:
     > compile WordLadder.java
     > run WordLadder <begin word> <end word>
   e.g.

     boy man		// boy -> bay -> ban -> man
     ape man        // ape -> apt -> opt -> oat -> mat -> man
     cat dog		// cat -> cot -> cog -> dog

     girl lady		// girl -> gill -> gall -> gale -> gaze -> laze -> lazy -> lady
     john jane
     lead gold   	// lead -> load -> goad -> gold
     star wars
     link golf

     child adult
     white black 	// white -> whine -> chine -> chink -> clink -> blink -> blank -> black
     grass green
     tears smile
     pitch tents
     black white
     diets liter
     quite diets
     rains plain
     rouge cheek

     bubble tickle
       //    bubble -> babble -> gabble -> garble -> gargle -> gaggle -> giggle ->
             jiggle -> jingle -> tingle -> tinkle -> tickle
   
*/

import java.io.*;
import java.util.*;


public class WordLadder
{
  private static final String DICT_FNM = "words.txt";


  public static void main(String[] args)
  {
    if (args.length != 2) {
      System.out.println("Usage: java WordLadder <begin word> <end word>");
      return;
    }
    String beginWord = args[0];
    String endWord = args[1];
    if (beginWord.length() != endWord.length()) {
      System.out.println("Words must be the same length");
      System.exit(1);
    }

    List<String> words = loadWords(DICT_FNM, beginWord.length());
    if (words.isEmpty())
      return;

    System.out.println("\nBuilding ladder for " + beginWord + " -> " + endWord);
    if (!makeLadder(words, beginWord, endWord))
      System.out.println("-- no ladder found");
  } /* main */


  private static List<String> loadWords(String fnm, int len)
  // return a list of loaded words only of the specified length
  {
    List<String> words = new ArrayList<>();
    try (BufferedReader br = new BufferedReader( new FileReader(fnm))) {
      System.out.println("Loading " + fnm);
      String line;
      while((line = br.readLine()) != null) {
        line = line.trim();
        if (line.length() == len) 
          words.add(line);
      }
    }
    catch (Exception e)  
    {  System.out.println("Unable to load " + fnm);
       System.exit(1);
    }
    System.out.println("No. of words of length " + len + 
                                        ": " + words.size());
    return words;
  }  // end of loadWords()


  private static boolean makeLadder(List<String> words,
                         String beginWord, String endWord)
  /* Look for the shortest ladder between beginWord and endWord
     using a breadth-first search and the words list.

    The function maintains growing ladders in a list,
    and cycles through them making all possible single word changes 
    to each in turn, which are stored as new ladders.
  */
  {
    List<String> ladder = new ArrayList<String>();
    ladder.add(beginWord);

    List<List<String>> ladders = new ArrayList<>();
       // a list of ladders whic is considered breadth-first
    ladders.add(ladder);

    while (!ladders.isEmpty()) {
      List<String> currLadder = ladders.remove(0);  // remove a ladder 
      Iterator<String> i = words.iterator();
         /* the words list is traversed using an iterator since
            a used word is deleted from the list
         */

      // extend this ladder with all possible one word changes
      while (i.hasNext()) {  // look for a suitable word
        String possWd = i.next();
        if (!differByOne(possWd, currLadder.get(currLadder.size()-1)))
          // possWd is not one character away, so isn't used
          continue;

        if (endWord.equals(possWd)) {  // reached the endWord, so report
          currLadder.add(endWord);
          System.out.println(String.join(" -> ", currLadder));
          System.out.println("No. of steps: " + (currLadder.size()-1));
          return true;
        }
    
        /* Make a new ladder by copying the current ladder and
           add possWd to the end. Add this ladder to the list of
           ladders, and remove possWd from the words list.
           The copy is necessary since this loop will continue looking
           for other ways to extend this same ladder with other words.
        */
        List<String> nLadder = new ArrayList<>(currLadder);
        nLadder.add(possWd);
        ladders.add(nLadder);
        i.remove(); 
      }
    }
    return false;
  } /* makeLadder */


  private static boolean differByOne(String s1, String s2)
  // do s1 and s2 differ by one character?
  {
    if (s1.length() != s2.length())
      return false;

    int numDiffs = 0;
    for (int i = 0; i < s1.length(); i++)
      if (s1.charAt(i) != s2.charAt(i))
        numDiffs++;

    return (numDiffs == 1);
  } /* differByOne */


}  // end of WordLadder class