There are four java files and two text file. BuildGraph.java, Vertex.java, WordLadder, java, FindLadder.java (driver program). The two text files are "graph.txt" and "dictionary.txt". The only java files that should be worked on is BuildGraph.java, WordLadder.java, and graph.txt. The other java files should not be messed with. Please try not to modify the existing code and methods already given in each java file.

(the dictionary.txt file is too large so this is the google drive link to the text file: https://drive.google.com/file/d/19Le_Ork8U2NKwuZIi39anGgUxYXlUvjQ/view?usp=sharing)

Overview: 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 solutions. Another path from stone to money is: stone store shore chore choke choky cooky cooey coney money.

stone

Atone

aLone

Clone

clonS

cOons

coNns

conEs

coneY

Money Objectives

Practice using the Stack ADT

Practice using ArrayList ADT

Practice using File Input/Output

********BuildGraph.java*******

Instructions STAGE 1: BuildGraph.java 1) Write a program called BuildGraph.java to create the word ladder graph.

a) Download the dictionary.txt file from Google Drive

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

c) Create an output file called graph.txt

d) for(int i=0;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

***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); } }

****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); } } Example output:

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:Iband, 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] 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:Iband, 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]