Instructions

STAGE 1: BuildGraph.java

1. Write a program called BuildGraph.java to create the word ladder graph.

   1. Download the dictionary.txt file from Google Drive (https://drive.google.com/file/d/19Le_Ork8U2NKwuZIi39anGgUxYXlUvjQ/view?usp=sharing )

   2. Read the contents of the dictionary.txt and add all four letter words to an ADT ArrayList words = new ArrayList<>();

   3. Create an output file called graph.txt

   4. for(int i=0;i

print words.get(i)+ followed by list of words that differ by one letter with

words.get(i)

}

For example, graph.txt will contain

band land sand

bent

bike like mike

boat coat

card cord hard ward

cash cast dash hash mash nash rash

cast cash cost fast last

coat boat cost

cold cord fold hold

STAGE 2: WordLadder.java & Vertex.java (Download from Google Drive)

5. Implement a class called WordLadder.java with the following specification:

import java.io.*;

import java.util.*;

public class WordLadder {

private ArrayList list; // list representing the word graph

private LinkedList ladder = new LinkedList<>(); // representing the ladder

public WordLadder() {

list=new ArrayList<>();

}

/**

* Read the file containing the graph into list

* @param fileName

* @throws IOException

*/

public void loadWordtMap(String fileName) throws IOException {

File infile = new File(fileName);

try(Scanner in = new Scanner(infile);)

{

while(in.hasNextLine()) {

// read a line

// split into a String[] called tokens based on

Node word = // create a new Node based on tokens[0]

// add the reset of the tokens to word.addPath()

// add the word to list

}

}

}

/**

* Find the ladder between start and end city, if it exists. Otherwise return false

* @param start

* @param end

* @return

*/

public boolean findLadder(String start,String end) {

Stack aStack = new Stack<>();

Vertex startWord = new Vertex(start);

Vertex endWord = new Vertex(end);

Check to see if startWord and endWord are part of the graph. Otherwise, print

Error message and return false.

mark all cities as unvisited

private LinkedList visited = new LinkedList<>(); // visited list of vertices

Add startWord to aStack

Mark startWord as visited by adding it to visited

While ( aStack not empty and have not found a path to destCity) {

Get the path of the vertex at top of aStack

If ( path is empty )

Remove vertex from aStack

Else {

Remove any visited vertex from the path until you find an unvisited vertex (v)

Add v to aStack

Add v to visited

} // end of while

If ( aStack is not empty ) {

Build the ladder by adding vertices from aStack to ladder

Print the ladder

Return true;

} else return false;

} // findLadder

/**

* A node in the graph is represented by a Vertex and path to other words

*/

class Node{

private Vertex word; // Graph vertex

private ArrayList path; // list of vertices in the path

public Node() {

path = new ArrayList<>();

}

public Node(Vertex word) {

this.word = word;

path = new ArrayList<>();

}

public void setword(Vertex word) {

this.word = word;

}

public Vertex getword() {

return word;

}

public ArrayList getPath(){

return path;

}

public void addPath(Vertex v) {

path.add(v);

}

public String toString() {

return word +"-->"+path;

}

public boolean equals(Object e) {

Vertex v = ((Node)e).getword();

return this.word.equals(v);

}

}

} // wordLadder

Example

Enter start word:band

Enter end word:fake

aStack:[band]

visited:[band]

path:[land, sand]

___________________________________

aStack:[band, land]

visited:[band, land]

path:[band, sand]

___________________________________

aStack:[band]

visited:[band]

path:[sand]

___________________________________

aStack:[band, sand]

visited:[band, sand]

path:[band, land, sane]

___________________________________

aStack:[band, sand, sane]

visited:[band, sand, sane]

path:[sake, sand, sine]

___________________________________

aStack:[band, sand, sane, sake]

visited:[band, sand, sane, sake]

path:[fake, lake, make, sane]

___________________________________

Found path of 5 cities

[band, sand, sane, sake, fake]

Grading:

Your assignment will be graded as following:

1. Your project must compile. Project will earn 0 points if there is any kind of syntax error. If you are using an IDE that creates a package, make sure to remove the import statement from all submitted files.

SUBMIT:

A zip folder containing:

1. BuildGraph.java

2. WordLadder.java

3. FindLadder.java (driver program)

4. Vertex.java

5. graph.txt FINDLADDER.JAVA

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

public static void main(String[] args) throws IOException{ try(Scanner in = new Scanner(System.in);) { WordLadder ladder = new WordLadder(); ladder.loadWordtMap("graph.txt"); System.out.print("Enter start word:"); String start = in.nextLine(); System.out.print("Enter end word:"); String end = in.nextLine(); if(!ladder.findLadder(start,end)) System.out.println("No Path was found between \""+start+ "\" and \"" + end+"\""); } }

}

VERTEX.JAVA public class Vertex { private String word; public Vertex() { } public Vertex(String word) { this.word=word; } public Vertex(String word, boolean v) { this.word=word; } public void setCity(String word) { this.word=word; } public String getCity() { return word; } public String toString() { return word; } public boolean equals(Object v) { return this.word.equals(((Vertex)v).word); }

}

WORDLADDER.JAVA

import java.io.*; import java.util.*; public class WordLadder { private ArrayList list; // list representing the word graph private LinkedList route = new LinkedList<>(); // list representing the ladder public WordLadder() { list=new ArrayList<>(); } /** * Read the file containing the graph into list * @param fileName * @throws IOException */ public void loadWordtMap(String fileName) throws IOException { File infile = new File(fileName); try(Scanner in = new Scanner(infile);) { while(in.hasNextLine()) { // read a line // split into a String[] called tokens based on   Node word = // create a new Node based on tokens[0] // add the reset of the tokens to word.addPath() // add the word to list } } } /** * Find the ladder between start and end city, if it exists. Otherwise return false * @param start * @param end * @return */ public boolean findLadder(String start,String end) { Stack stack = new Stack<>(); private LinkedList ladder = new LinkedList<>(); // visited list of vertices Vertex startWord = new Vertex(start); Vertex endWord = new Vertex(end); /* Check to see if startWord and endWord are part of the graph. Otherwise, print Error message and return false. mark all cities as unvisited private LinkedList visited = new LinkedList<>(); // visited list of vertices Add startWord to aStack Mark startWord as visited by adding it to visited While ( aStack not empty and have not found a path to destCity) { Get the path of the vertex at top of aStack If ( path is empty ) Remove vertex from aStack Else { Remove any visited vertex from the path until you find an unvisited vertex (v) Add v to aStack Add v to visited } // end while // Rebuild the ladder from startWord to endWord and print if(!stack.isEmpty()) { while(!stack.isEmpty()) route.addFirst(stack.pop()); System.out.println("Found path of "+ route.size()+ " cities"); System.out.println(route); return true; } return false; */ } // end findLadder } // end WordLadder /** * A node in the graph is represented by a Vertex and path to other words */ class Node{ private Vertex word; // Graph vertex private ArrayList path; // list of vertices in the path public Node() { path = new ArrayList<>(); } public Node(Vertex word) { this.word = word; path = new ArrayList<>(); } public void setword(Vertex word) { this.word = word; } public Vertex getword() { return word; } public ArrayList getPath(){ return path; } public void addPath(Vertex v) { path.add(v); } public String toString() { return word +"-->"+path; } public boolean equals(Object e) { Vertex v = ((Node)e).getword(); return this.word.equals(v); } }