Question

In: Computer Science

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 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 which has the contents at the bottom of this page "dictionary.txt"

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  

  • 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
        }
    }
    
    
  • "Dictionary.txt" CONTENTS (save to txt file)
  • 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
  • "infile.txt" CONTENT (save to a txt file)
  • line fine
    dear fear
    stone money
    fake coat
    like help
    blue pink
    face like
    help mind
    lice help
    door lice

Solutions

Expert Solution

PLEASE GIVE IT A THUMBS UP, I SERIOUSLY NEED ONE, IF YOU NEED ANY MODIFICATION THEN LET ME KNOW, I WILL DO IT FOR YOU

 ---------------------------------------------------------

--------------QueueInterface.java--------------

---------------------------------------------------------

public interface QueueInterface<E> {
/**
* Tests if the queue is logically empty
*/
public boolean isEmpty();
/**
* Puts a value into the back of the queue.
*  
*
* @param value the item to insert.
* @return true if successful
* @throws ClassCastException
*/
public boolean enqueue (E value);
/**
* Returns the first element in the queue.
*
* @return element at front of the queue
* @throws java.util.NoSuchElementException if the queue is empty.
*/

public E peek() throws java.util.NoSuchElementException;
/**
* Returns and removes the front element of the queue. It works with wraparound.
*
* @return element at front of the queue
* @throws java.util.NoSuchElementException if the queue is empty.
*/
public E dequeue() throws java.util.NoSuchElementException;
/**
* Makes the queue physically empty.
*/
public void clear();
}

---------------------------------------------------------

---------------------Queue.java-------------------

---------------------------------------------------------

import java.util.*;

public class Queue<E> implements QueueInterface<E>{

private Stack<E> inbox;

private Stack<E> outbox;

public Queue(){

inbox = new Stack<E>();

outbox = new Stack<E>();

}

public boolean enqueue(E e){

try{

inbox.push(e);

} catch (ClassCastException ex) {

return false;

}

return true;

}

public E dequeue(){

try{

if(outbox.isEmpty()){

while(!inbox.isEmpty()){

outbox.push(inbox.pop());

}

}

}catch(NoSuchElementException ex){}

return (E)outbox.pop();

}

public E peek(){

try{

if(outbox.isEmpty()){

while(!inbox.isEmpty())

outbox.push(inbox.pop());

}

}catch(NoSuchElementException ex){}

return (E)outbox.pop();

}

public boolean isEmpty(){

return (inbox.isEmpty() && outbox.isEmpty());

}

public void clear(){

// Implementation left as exercise

}

}

---------------------------------------------------------

-----------------MainDriver.java------------------

---------------------------------------------------------

import java.io.*;

import java.util.*;

public class MainDriver {

public static void main(String[] args) throws IOException {

// TODO code application logic here

Ladder wordLadder = null; new Ladder();

Scanner in=null;

try{

in = new Scanner(new File("input.txt"));

while (in.hasNext()){

// Build word ladders for the given input and print them

String start = in.next();

String end = in.next();

wordLadder = new Ladder();

Stack ladder = wordLadder.buildLadder(start, end);

if (ladder.isEmpty())

System.out.println("There is no word ladder between " + start + " and " + end + "!");

else

System.out.println(ladder);

}

}

catch (FileNotFoundException e){

System.out.println("Wrong file name!");

System.exit(0);

}

in.close();

}

}

---------------------------------------------------------

-------------------Ladder.java---------------------

---------------------------------------------------------

import java.util.*;

import java.io.*;

public class Ladder {

private Set<String> dictionary;

private Set used;

private Queue wordLadder;

/**

* Constructor.

* Initialize private data fields

*/

public Ladder()throws IOException{

dictionary = new HashSet<String>();

wordLadder = new Queue<>();

used = new HashSet<>();

readDictionary("dictionary.txt");

}

/**

* Reads the dictionary and store it in the hash table

*/

public void readDictionary(String urlString) throws IOException{

FileInputStream dataStream = new FileInputStream(urlString);

Scanner fileIn = new Scanner(dataStream);

String word;

while(fileIn.hasNextLine()){

word = fileIn.nextLine();

dictionary.add(word);

}

}

public Stack buildLadder(String start, String end){

Stack ladder = new Stack<>();

Queue q = new Queue<>();

Stack temp = new Stack<>();

temp.push(start);

q.enqueue(temp);

dictionary.remove(start);

while(!q.isEmpty()){

temp = (Stack)q.dequeue();

String last = (String)temp.peek();

// System.out.println(temp);

Iterator<String> iter = dictionary.iterator();

while (iter.hasNext()) {

String s = iter.next();

if (isAnEdge(last,s)) {

// System.out.println(last);

// System.out.println(s);

Stack stack2 = (Stack)temp.clone();

stack2.push(s);

iter.remove();

q.enqueue(stack2);

if(s.equals(end)){

ladder = stack2;

return ladder;

}

}

}

}

return ladder;

}

private boolean isAnEdge(String w1, String w2) {

if(w1.length()!=w2.length()) return false;

int numdiff = 0;

for(int i=0;i<w1.length();i++){

if(w1.charAt(i)!=w2.charAt(i)) numdiff++;

if(numdiff>1) break;

}

return numdiff==1;

}

}

Related Solutions

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