Question

In: Computer Science

WordLadder JAVA Program question stone Atone aLone Clone clonS cOons coNns conEs coneY Money Word ladders...

WordLadder JAVA Program 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

Objectives

  • Practice implementing and using a Queue data structure.

  • Gain an understanding of the algorithms used for efficient implementation.

  • Practice working in small teams to solve problems, design algorithms and write code

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.

Dictionary

You read the dictionary file. (POSTED AT THE BOTTOM)

The dictionary file contains exactly one word per line. The number of lines in the dictionary is not specified.

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 ..."

For testing purposes, I provide you with the input file and 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 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> 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

Solutions

Expert Solution


import java.util.*;

class short
{


static int shortestChain(String start,
                           String target,
                           Set<String> D)
{

     
   if (!D.contains(target))
       return 0;

   int level = 0, wordlength = start.length();

   // Push the starting word into the queue
   Queue<String> Q = new LinkedList<>();
   Q.add(start);

  
   while (!Q.isEmpty())
   {

       // Increment the chain length
       ++level;

       // Current size of the queue
       int sizeofQ = Q.size();


  

       for (int i = 0; i < sizeofQ; ++i)
       {

           // Remove the first word from the queue
           char []word = Q.peek().toCharArray();
           Q.remove();

             
           for (int pos = 0; pos < wordlength; ++pos)
           {

              
               char orig_char = word[pos];

              
               for (char c = 'a'; c <= 'z'; ++c)
               {
                   word[pos] = c;

                  
                   if (String.valueOf(word).equals(target))
                       return level + 1;

                  
                   if (!D.contains(String.valueOf(word)))
                       continue;
                   D.remove(String.valueOf(word));

                     
                   Q.add(String.valueOf(word));
               }

              
               word[pos] = orig_char;
           }
       }
   }

   return 0;
}


public static void main(String[] args)
{
   // make dictionary add all words from disctorinay file
   Set<String> D = new HashSet<String>();
Scanner scan = new scanner(System.in)
   D.add("lice");
   D.add("deck");
   D.add("cord");
   D.add("bent");
   //...so on till ent
   String start = scan.nextLine().trim();
   String target = scan.nextLine().trim()
   System.out.print("Length of shortest chain is: "
       + shortestChain(start, target, D));
}
}



Related Solutions

JAVA Wordladder Project stone Atone aLone Clone clonS cOons coNns conEs coneY Money Word ladders were...
JAVA Wordladder Project 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...
stone Atone aLone Clone clonS cOons coNns conEs coneY Money Word ladders were invented by Lewis...
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...
stone Atone aLone Clone clonS cOons coNns conEs coneY Money Word ladders were invented by Lewis...
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...
Write a Java program that prompts the user to input a word (String). The program must...
Write a Java program that prompts the user to input a word (String). The program must print the reversed word with all consecutive duplicate characters removed. The program must contain the following classes: - The StackX class (you can use the Java Stack class). - The Reverse class which must contain a private data field called “word” of type string, a constructor, and a void method called revNoDup(). The revNoDup() method must reverse the word and remove the consecutive duplicate...
Java Project Requirements: 1.Write a Java program that plays a word game with a user. The...
Java Project Requirements: 1.Write a Java program that plays a word game with a user. The program asks the user questions and then creates a paragraph using the user’s answers. 2.The program must perform the following: a.Uses a Scanner object to ask the user: (The program asks for no other information) i.Full Name (First and Last name only) - stores this Full Name in one String object variable. ii.Age – must be read in as an int. iii.Profession or expected...
Write a Java program that directs the user to enter a single word (of at least...
Write a Java program that directs the user to enter a single word (of at least four characters in length) as input and then prints the word out in reverse in the pattern shown below (please note that the spaces added between each letter are important and should be part of the program you write): <Sample Output Enter a word (at least four characters in length): cat Word must be at least four characters in length, please try again. Enter...
(JAVA) We will write a program to check the spelling of the word entered by user,...
(JAVA) We will write a program to check the spelling of the word entered by user, using data from a dictionary, which is text file. The program will ask user to enter a word for spell check, and then check in the text file (dictionary.txt) if the word exists. (The dictionary.txt file is provided) If the word exists in text file, the output will be “Word is correctly spelled”. If the word doesn’t exist in the text file, program will...
Java 176 Lottery Program in Word. Using ArrayLists to Simulate a Lottery Program Simulate a Lottery...
Java 176 Lottery Program in Word. Using ArrayLists to Simulate a Lottery Program Simulate a Lottery Drawing by choosing 7 numbers at random from a pool containing 30 numbers Each time a number is selected, it is recorded and removed from the pool The pool values are 00 to 29 inclusive Your program must output each selected number from the drawing using a two-digit format. For Example, the number 2 would be represented by 02 on the “Picked” line. The...
Java question- Write a java program to process the number.txt file. Then count the numbers and...
Java question- Write a java program to process the number.txt file. Then count the numbers and calculate the total average, even numbers average, odd number average, then print the corresponding information. The result should be displayed in the following format there are XX numebers in the file there are xx even numbers there are xx odd numbers the total number average is xx the odd number average is xx the even number average is xx I am having trouble using...
Write a java program to reverse element of a stack. For any given word (from input),...
Write a java program to reverse element of a stack. For any given word (from input), insert every character (from the word) into a stack. The output from the stack should be the same as the input. Your program should be using a stack and a queue to complete this process. 1. Push into stack 2. Pop from stack 3. Enqueue into queue 4. Dequeue from queue 5. Push into stack 6. Pop from stack and display java
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT