write, in Java, programs to investigate word ladders composed of five letter words. A word ladder...

 

Transcribed Image Text:

write, in Java, programs to investigate word ladders composed of five letter words. A word ladder is a sequence of words, each member of the sequence differing from its predecessor in exactly one position. For example, the following ladder, of length 6, 'transforms the word flour into the word bread. flour →floor →flood blood-brood broad → bread A dictionary file words5.txt will be provided, which contains a set of nearly 2000 five-letter words that should be used to construct ladders. Your programs should do the minimum amount of work necessary in each case. Program 1. The first program should read in a dictionary file, together with two more five letter words, i.e. the program should take 3 command-line arguments: 1. a dictionary file 2. a start word; 3. an end word. The program should produce on the standard output channel the length of the shortest path and a path/ladder of shortest length that transforms the start word into the end word, or should report that no ladder is possible. The final line of output should report the execution time of the program in seconds. (The code to generate this output is included in the skeleton programs provided. Note that it represents elapsed time, so may not be an accurate reflection of actual running time depending on other processes that may be executing on the computer.) Program 2. The second program considers a weighted version of the word ladder problem where the weight of a transformation (i.e. edge of the corresponding graph) is the absolute difference in the positions of the alphabet of the non-matching letter. For example, the weight of the edge between angel and anger equals the position of minus the position of / which is 6. This second program should implement Dijkstra's algorithm for finding the shortest paths. Similarly to the first case, the program should read in a dictionary file, together with two more five letter words the program and report on the standard output channel the minimum distance between the words together with a corresponding path, or should report that no ladder is possible. As for the first program, the final line of output should report the execution time of the program in seconds. Clarifications. The dictionary file (words5.txt) contains only words of 5 letters, all in lower-case, one word per line; No data validation is needed: you can assume that input to the first program is provided in the appropriate format, with all words in lower case; You can assume also that each word that is input is actually present in the given word file; a graph representation of the dictionary is the key to an efficient solution; Graphs should be represented using adjacency lists and the program from the warm up labo- ratory exercise provides a very good basis for you programs. write, in Java, programs to investigate word ladders composed of five letter words. A word ladder is a sequence of words, each member of the sequence differing from its predecessor in exactly one position. For example, the following ladder, of length 6, 'transforms the word flour into the word bread. flour →floor →flood blood-brood broad → bread A dictionary file words5.txt will be provided, which contains a set of nearly 2000 five-letter words that should be used to construct ladders. Your programs should do the minimum amount of work necessary in each case. Program 1. The first program should read in a dictionary file, together with two more five letter words, i.e. the program should take 3 command-line arguments: 1. a dictionary file 2. a start word; 3. an end word. The program should produce on the standard output channel the length of the shortest path and a path/ladder of shortest length that transforms the start word into the end word, or should report that no ladder is possible. The final line of output should report the execution time of the program in seconds. (The code to generate this output is included in the skeleton programs provided. Note that it represents elapsed time, so may not be an accurate reflection of actual running time depending on other processes that may be executing on the computer.) Program 2. The second program considers a weighted version of the word ladder problem where the weight of a transformation (i.e. edge of the corresponding graph) is the absolute difference in the positions of the alphabet of the non-matching letter. For example, the weight of the edge between angel and anger equals the position of minus the position of / which is 6. This second program should implement Dijkstra's algorithm for finding the shortest paths. Similarly to the first case, the program should read in a dictionary file, together with two more five letter words the program and report on the standard output channel the minimum distance between the words together with a corresponding path, or should report that no ladder is possible. As for the first program, the final line of output should report the execution time of the program in seconds. Clarifications. The dictionary file (words5.txt) contains only words of 5 letters, all in lower-case, one word per line; No data validation is needed: you can assume that input to the first program is provided in the appropriate format, with all words in lower case; You can assume also that each word that is input is actually present in the given word file; a graph representation of the dictionary is the key to an efficient solution; Graphs should be represented using adjacency lists and the program from the warm up labo- ratory exercise provides a very good basis for you programs.

Answer rating: 100% (QA)

Program 1 Java import javaio Buffered Reader import javaioFileReader import javaioIOException import javautilList public class Program1 public static ... View the full answer