WordLadder JAVA Program question

stone Atone aLone Clone clonS cOons coNns conEs coneY Money

Word ladders were invented by Lewis Carroll in 1878, theauthor of Alice in Wonderland. A ladder is a sequence of words thatstarts at the starting word, ends at the ending word, In a wordladder puzzle you have to change one word into another by alteringa single letter at each step. Each word in the ladder must be avalid English word and must have the same length. For example, toturn stone into money, one possible ladder is given on theleft. Many ladder puzzles have more than one possiblesolution. Your program must determine the shortest word ladder.Another path from stone to money is stone store shore chore choke choky cooky cooey coneymoney Objectives Practice implementing and using a Queue datastructure. Gain an understanding of the algorithms used forefficient implementation. Practice working in small teams to solve problems,design algorithms and write code Instructions Your program will accept starting and ending words fromthe input file called \"infile.txt\". Then, you read the dictionaryfile called “dictionary.txt '' store all words in a LinkedList.Finally, you build a word ladder between starting and endingwords There are several ways to solve this problem. One simplemethod involves using stacks and queues. The algorithm (that youmust implement) works as it follows Get the starting word and search through the dictionaryto find all words that are one letter different. Create stacks foreach of these words, containing the starting word (pushed first)and the word that is one letter different. Enqueue each of thesestacks into a queue. This will create a queue of stacks! Thendequeue the first item (which is a stack) from the queue, look atits top word and compare it with the ending word. If they equal,you are done - this stack contains the ladder. Otherwise, you findall the words one letter different from it. For each of these newwords create a deep copy of the stack and push each word onto thestack. Then enqueue those stacks to the queue. And so on. Youterminate the process when you reach the ending word or the queueis empty. You have to keep track of used words! Otherwise, aninfinite loop occurs. Example The starting word is smart. Find all the words oneletter different from smart, push them into different stacks andstore stacks in the queue. This table represents a queue ofstacks. ---------------------------------------------------- | scart | start | swart | smalt | smarm | | smart | smart | smart | smart | smart | ---------------------------------------------------- Now dequeue the front and find all words one letterdifferent from the top word scart. This will spawn sevenstacks: --------------------------------------------------------------------- | 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 differentfrom 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. Repeatthe procedure until either you find the ending word or such a wordladder does not exist. Make sure you do not run into an infiniteloop! Queue You are to implement a Queue data structure based onJava’s Queue class using LinkedList. Stack You are to use Java's Stack class. Dictionary You read the dictionary file. (POSTED AT THEBOTTOM) The dictionary file contains exactly one word per line.The number of lines in the dictionary is notspecified.

Output

Your program must output to the console one word ladderfrom the start word to the end word. Every word in the ladder mustbe a word that appears in the dictionary. This includes the givenstart and end words--if they are not in the dictionary, you shouldprint \"There is no word ladder between ...\" Remember that there maybe more than one ladder between the start word and the end word.Your program may output any one of these ladders. The first outputword must be the start word and the last output word must be theend word. If there is no way to make a ladder from the start wordto the end word, your program must output \"There is no word ladderbetween ...\"

For testing purposes, I provide you with the input fileand the expected output.

SAMPLE OUTPUT:

[line, fine]

[dear, fear]

There is no word ladder between stone and money

[fake, lake, lase, last, cast, cost, coat]

[like, line, fine, fire, fore, core, cord, cold, hold, held,help]

There is no word ladder between blue and pink

[face, fake, lake, like]

[help, held, hold, cold, cord, core, fore, fire, fine, find,mind]

[lice, line, fine, fire, fore, core, cord, cold, hold, held,help]

There is no word ladder between door and lice

Starter Code:

• WordLadder.java

WordLadder.java CONTENT

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 stubFile dictfile = new File(\"dictionary.txt\");File infile = new File(\"infile.txt\");dict = new LinkedList<>();// load the dictionarytry(  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> queue = new LinkedList<>();  visited = new LinkedList<>();  Stack copiedStack = new Stack<>();  // Left as exercise}

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

infile.txt CONTENT

line fine
dear fear
stone money
fake coat
like help
blue pink
face like
help mind
lice help
door lice

dictionary.txt CONTENT

lice
deck
cord
bent
band
cast
bike
cash
card
boat
cold
coat
dear
slow
core
dash
cost
dame
fish
dorm
dine
deer
dear
dime
fast
blue
deme
dive
dish
dinn
door
dome
fake
slow
pink
face
find
fast
fire
fear
fine
finn
help
held
hash
fore
folk
fold
hard
hear
here
host
hold
hire
lase
land
knot
lake
kunn
kuns
last
mind
main
line
lime
like
lost
live
linn
love
lunn
mike
maze
mash
make
mice
meta
mien
milk
vice
silk
neck
mink
mine
must
most
more
nash
sick
nice
rain
pour
pine
nick
pain
nine
nuns
pond
pony
poor
sake
rick
rash
rime
rust
sane
sand
sine
sure
sony
tiny
warm
vide
ward
worm