// Doublets.java
// https://www.programcreek.com/2012/12/leetcode-word-ladder/
// 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 
   WordLadder.java. Please read the comments in that file for
   more on word ladders.

   Although the resulting ladders for both programs are usually
   the same length, they rarely use exactly the same words.

  Usage:
    > compile Doublets.java
    > run Doublets <begin word> <end word>
  e.g.
     boy man		// boy -> bay -> may -> man
     ape man        // ape -> apt -> opt -> oat -> mat -> man
     cat dog		// cat -> cot -> dot-> dog

     girl lady		// girl -> girt -> gist -> list -> last -> lase -> lade -> lady
     john jane
     lead gold   	// lead -> load -> goad -> gold
     star wars
     link golf

     child adult
     white black 	// white -> write -> trite -> trice -> trace -> track -> crack -> clack -> bla
ck
     grass green
     tears smile
     pitch tents
     black white
     diets liter
     quite diets  

   One problem relates to the way that Hunspell scores 
   words to decide which word to modify at the next step. 
   The problem showed itself in two examples:

    rains plain  
      - 20 steps vs. 9 in WordLadder.java
      - the extra length is due to changing the first
        letter to 'p' at too early a stage

    rouge cheek  
      - 18 steps vs. 11 in WordLadder.java
      - the extra length is due to changing the first
        letter to 'c' at too early a stage
*/

import java.util.*;


public class Doublets
{

  public static void main(String[] args)
  {
    if (args.length != 2) {
      System.out.println("Usage: run Doublets <begin word> <end word>");
      System.exit(1);
    }
    String beginWord = args[0];
    String endWord = args[1];
    System.out.println("Building ladder for " +
                              beginWord + " -> " + endWord);

    HunspellChecker hsc = new HunspellChecker();
/*
    hsc.add("tippy");  // words added to speed up some examples;
    hsc.add("litre");  // not used in final code
    hsc.add("suets");
*/
    ArrayList<String> triedWords = new ArrayList<>();
      // prevents the reuse of words in the ladder

    boolean ladderFound = false;

    PriorityQueue<WordNode> pq = new PriorityQueue<>();
     /* a WordNode stores a word, its score, and a link to 
        the word that generated it (its parent)
     */
    pq.add( new WordNode(beginWord, 0, null));   // score == 0; no parent
    triedWords.add(beginWord);

    while (!pq.isEmpty() && !ladderFound) {
      WordNode wn = pq.poll();
      // System.out.println("Polled " + wn);
      if (wn.getWord().equals(endWord)) {
        ladderFound = true;
        reportLadder(wn);
      }
      else
        genWords(wn, endWord, pq, triedWords, hsc);
    }

    hsc.close();

    if (!ladderFound)
      System.out.println("No ladder found");
  } /* main */


  private static void genWords(WordNode wn, String endWord,
                            PriorityQueue<WordNode> pq,
                            ArrayList<String> triedWords,
                            HunspellChecker hsc)
  /* Every letter of the input word (stored in wn)
     is varied, and if that results in an unused 
     dictionary word, then it is scored and added
     to the priroty queue
  */
  { char[] arr = wn.getWord().toCharArray();
    char[] endArr = endWord.toCharArray();

    // vary every letter of the supplied word in wn
    for (int i = 0; i < arr.length; i++) {
      for (char ch = 'a'; ch <= 'z'; ch++) {
        char temp = arr[i];
        arr[i] = ch;
        String word = new String(arr);
        if (hsc.isCorrect(word) && !triedWords.contains(word)) {
          // created an unused dictionary word, so add to queue
          int score = scoreWord(arr, endArr);   
              // score it relative to the end word
          pq.add( new WordNode(word, score, wn)); 
                             // wn is the word's parent
          triedWords.add(word);
        }
        arr[i] = temp;
      }
    }
  }  // end of genWords()


  private static int scoreWord(char[] arr, char[] endArr)
  /* The scoring has three parts:
      * a word with a matching letter in the end word gets +5
      * a word with a vowel gets +2
      * a word with a 'popular' letter gets +1
  */
  {
    int score = 0;
    for (int i = 0; i < arr.length; i++) {
      if (arr[i] == endArr[i])
        score += 5;
      else if ((arr[i] == 'a') || (arr[i] == 'e') ||
               (arr[i] == 'i') || (arr[i] == 'o') ||
               (arr[i] == 'u'))  // vowels
        score += 2;
      else if ((arr[i] == 't') || (arr[i] == 'n') ||
               (arr[i] == 's'))   // popular letters
        score += 1;
    }
    return score;
  }  // end of scoreWord()



  private static void reportLadder(WordNode wn)
  /* The ladder is constructed by following the 
     WordNode.parent link of the final word back
     to the begin word. 
     The words are added to the front of the list
     so they appear in begin word --> end word order.
  */ 
  {
    ArrayList<String> ladder = new ArrayList<>();
    ladder.add(0, wn.getWord());    

    WordNode parent = wn.getParent();
    while (parent != null) {   // this occurs in the begin WordNode
      ladder.add(0, parent.getWord());
      parent = parent.getParent();
    }

    System.out.println(String.join(" -> ", ladder));
    System.out.println("No. of steps: " + (ladder.size()-1));
  }  // end of reportLadder()

}  // end of Doublets class