Question

stone Atone aLone Clone clonS cOons coNns conEs coneY Money

Word ladders were invented by Lewis Carroll in 1878, the author of Alice in Wonderland. A ladder is a sequence of words that starts at the starting word, ends at the ending word, In a word ladder puzzle you have to change one word into another by altering a single letter at each step. Each word in the ladder must be a valid English word and must have the same length. For example, to turn stone into money, one possible ladder is given on the left. Many ladder puzzles have more than one possible solution. Your program must determine the shortest word ladder. Another path from stone to money is stone store shore chore choke choky cooky cooey coney money Instructions Your program will accept starting and ending words from the input file called "infile.txt". Then, you read the dictionary file called “dictionary.txt '' store all words in a LinkedList. Finally, you build a word ladder between starting and ending words There are several ways to solve this problem. One simple method involves using stacks and queues. The algorithm (that you must implement) works as it follows Get the starting word and search through the dictionary to find all words that are one letter different. Create stacks for each of these words, containing the starting word (pushed first) and the word that is one letter different. Enqueue each of these stacks into a queue. This will create a queue of stacks! Then dequeue the first item (which is a stack) from the queue, look at its top word and compare it with the ending word. If they equal, you are done - this stack contains the ladder. Otherwise, you find all the words one letter different from it. For each of these new words create a deep copy of the stack and push each word onto the stack. Then enqueue those stacks to the queue. And so on. You terminate the process when you reach the ending word or the queue is empty. You have to keep track of used words! Otherwise, an infinite loop occurs. Example The starting word is smart. Find all the words one letter different from smart, push them into different stacks and store stacks in the queue. This table represents a queue of stacks. ---------------------------------------------------- | scart | start   | swart | smalt | smarm | | smart | smart | smart | smart | smart   | ---------------------------------------------------- Now dequeue the front and find all words one letter different from the top word scart. This will spawn seven stacks: --------------------------------------------------------------------- | scant | scatt | scare | scarf | scarp | scars   | scary | | scart | scart | scart | scart | scart | scart   | scart | | smart | smart | smart | smart | smart | smart | smart |    ---------------------------------------------------------------------- which we enqueue to the queue. The queue size now is 11. Again dequeue the front and find all words one letter different from the top word start. This will spawn four stacks: ---------------------------------------- | sturt   | stare | stark | stars | | start   | start   | start   | start   | | smart | smart | smart | smart | ---------------------------------------- Add them to the queue. The queue size now is 14. Repeat the procedure until either you find the ending word or such a word ladder does not exist. Make sure you do not run into an infinite loop! Queue You are to implement a Queue data structure based on Java’s Queue class using LinkedList. Stack You are to use Java's Stack class. Output Your program must output to the console one word ladder from the start word to the end word. Every word in the ladder must be a word that appears in the dictionary. This includes the given start and end words--if they are not in the dictionary, you should print "There is no word ladder between ..." Remember that there may be more than one ladder between the start word and the end word. Your program may output any one of these ladders. The first output word must be the start word and the last output word must be the end word. If there is no way to make a ladder from the start word to the end word, your program must output "There is no word ladder between ..."

import java.util.*;
import java.io.*;
public class WordLadder {

   private static LinkedList dict;
   private static LinkedList visited;
   private static String start, end;

   public static void main(String[] args) throws IOException{
    // TODO Auto-generated method stub
      File dictfile = new File("dictionary.txt");
      File infile = new File("infile.txt");
      dict = new LinkedList<>();
    // load the dictionary
      try(
         Scanner in = new Scanner(dictfile);){
         while(in.hasNext()) {
           
            dict.add(in.next());
         }
      }
      try(Scanner in = new Scanner(infile);)
      {
         while(in.hasNext()) {
       
           
            start = in.next();
           
            end = in.next();
           
            if(start.length()!=end.length() || !dict.contains(start) || !dict.contains(end) ){
               System.out.println("There is no word ladder between "+start+ " and "+end);
               continue;
            }
       
            findLadder(start,end);
       
         }
      }
   


   }
  
   public static void findLadder(String start,String end) {
   
      Queue< Stack < String >> queue = new LinkedList<>();
      visited = new LinkedList<>();
      Stack< String > copiedStack = new Stack<>();
    // Left as exercise
   

   }   

   public static boolean isAnEdge(String w1, String w2) {
        // Left as exercise

}
       

Answer 1

Code:

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

public class WordLadder {
    private static LinkedList<String> dict;
    private static LinkedList<String> visited;
    private static String start, end;

    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        File infile = new File("infile.txt");
        File dictfile = new File("dictionary.txt");
        dict = new LinkedList<>();
        // load the dictionary
        try (
                Scanner in = new Scanner(dictfile);) {
            while (in.hasNext()) {
                dict.add(in.next());
            }
        }
        // load the infile
        try (Scanner in = new Scanner(infile)) {
            while (in.hasNext()) {
                start = in.next();
                end = in.next();
                if (start.length() != end.length() || !dict.contains(start) || !dict.contains(end)) {
                    System.out.println("There is no word ladder between " + start + " and " + end);
                    continue;
                }
                findLadder(start, end);
            }
        }
    }

    public static void findLadder(String start, String end) {
        // Make a visited list
        visited = new LinkedList<>();
        // mark the start as visited
        visited.add(start);

        Queue<Stack<String>> queue = new LinkedList<>();
        Stack<String> oldStack = new Stack<>();
        oldStack.add(start);
        queue.add(oldStack);
        while (true) {
            for (Stack<String> strings : queue) {
                if(strings.peek().equals(end))
                {
                    System.out.println(strings);
                    return;
                }
            }
            if(queue.isEmpty()) {
                System.out.println("There is no word ladder between " + start + " and " + end);
                return;
            }
            oldStack = queue.remove();
            String w = oldStack.peek();

            // Iterate the dictionary and check if there's an edge between s and w
            // and s is not visited
            for (String s : dict) {
                if (isAnEdge(s, w) && !visited.contains(s)) {
                    Stack<String> copiedStack = new Stack<>();
                    copiedStack.addAll(oldStack);
                    copiedStack.push(s);
                    // mark the current node visited
                    visited.add(s);
                    queue.add(copiedStack);
                }
            }
        }
    }


    public static boolean isAnEdge(String w1, String w2) {
        // Can't be edge if length is different
        if(w1.length()!=w2.length())
            return false;
        int check=0;
        for (int i = 0; i < w1.length(); i++) {
            // If the i-th char differs, then it's not an edge
            if (w1.charAt(i) != w2.charAt(i)) {
                check++;
            }
        }
        return check==1;
    }




}

Screenshots:

-------------------------END---------------------

Please give a thumbs up(upvote) if you liked the answer.