In this assignment you are to write a Java program that implements a word game based on manipulating five-letter words. The idea behind the game is to transform a given word into another given word by repeatedly changing either one or two letters. Each transformation must result in a legal word (the set of legal words is specified in a dictionary file that is read in when the program is started). A solution is scored as follows: Each single-letter change has a cost of one point, and each two-letter change has a cost of five points. Following these rules, the word GOOFY can be transformed into the word YAHOO by the following steps:

You are to write a program that, given the dictionary file and two input words, finds a minimum-cost sequence that transforms the first input word to the second. This involves representing the dictionary as a weighted graph: Vertices in the graph represent words; edges represent legal moves in the game, with weights equal to the costs of the moves (1 or 5 points). The minimum-cost sequence is determined using a graph search algorithm.

You are to implement the project in two stages. In the first, you are to write a program that reads in the dictionary and constructs the graph of legal moves. In the second, you are to write the graph search algorithm and implement the game.

Part 1 (due Friday 11/22/2019):

• Open and read an input file specified as a command line argument. If the argument is not a valid filename, the program should print an error message and exit. If the named file can be opened, you may assume that it is a correct dictionary file.
  
  
• Read the words from the dictionary file, and construct the graph for that file in a reasonable amount of time. Your program should do this only once; after the dictionary is read and the graph is constructed, that graph is used for all trials during that run of the program.
  • Dictionary files contain a sequence of five-letter words in upper case. You may assume that the files are correct (i.e., all words are five letters and consist of only upper-case characters); error checking is not required. DO NOT CHANGE THE INPUT FILES! Your programs will be tested with the inputs provided.
  • The graph consists of one vertex for each word read, and an edge between each pair of words that differ by no more than two characters.
  • The graph is sparse but large. Use an adjacency list implementation for your graph.
  • You will need to implement a vertex class as part of your graph implementation. In Part 2 you will need to insert vertex objects into the heap with handles you implemented in Assignment 2. Thus, your Vertex class must extend the HeapElt class from that earlier assignment. For this phase of the project, the record and handle data members will not be used.
  
  
  
• To test your graph implementation, you should provide the following functionality once the graph is constructed (NOTE that I will test your programs using a script, and if you deviate from the following requirements, I will deduct points):
  • You should ask the user to provide a five-letter word. If the word is in the graph, you should print out a list of all neighbors of that word (that is, all words connected to the input word by an edge). If the input word is not in the dictionary, you should print out a message to that effect and end the current trial. The test of whether or not the word is in the graph should be case-insensitive; if the user enters "break" or "bREaK", for example, and "BREAK" is in the graph, the neighbors of "BREAK" should be printed. After each neighbor is printed, the weight of the edge to that neighbor should be printed in parentheses:

    Enter a five-letter word: Shale
    
    The neighbors of SHALE are:
            WHOLE (5)  WHALE (1)  THANE (5)  SWARE (5)  STAVE (5)  STAGE (5)  
            SPATE (5)  SNARE (5)  SMILE (5)  SMALL (5)  SLAVE (5)  SHULS (5)  
            SHELF (5)  SHAWS (5)  SHARP (5)  SHANK (5)  SHAFT (5)  SCAPE (5)  
            SCALP (5)  SABLE (5)  DHALS (5)  
    

  • After a trial, you should ask the user if another trial is desired. Using input validation, make sure that the user inputs is one of the four strings "Y", "Yes", "N", or "No" ignoring case; that is, input should not be case-sensitive (i.e., "y" or "yes" or "yEs" or "n" etc. are acceptable inputs). If the user answers "Y" or "Yes", repeat the neighbor check above. If the user enters "N" or "No", terminate the program. You must handle all four allowed inputs correctly, and query the user again if anything else is entered. Repeat until the user has entered an acceptable response.

    If the user answers "Y" or "Yes", repeat the neighbor check above. If the user enters "N" or "No", terminate the program.

Assumptions:

You may assume that you don't need to deal with graphs containing more that 10,000 vertices.

You may assume that the dictionary files are in alphabetical order.

Hints for Part 1:

Design is critical for this assignment. If you do not think about what you are doing ahead of time, you will end up with space or time problems. Further, the problem is complicated enough that if you just start writing code and try to add capabilities as you go, you may very likely end up with a program that does inexplicable things.

Develop this program incrementally, debugging as you go. If you try to write all the code, and don't compile until it's all written, you'll have a difficult time debugging it. For example, implement code to read the file, then implement the main loop with placeholders for calls into the graph object. Then, once you know what graph methods you need, implement the graph itself.

You will need to provide a map between vertex names (words) and the vertex object you create. Note that you are given the words in alphabetical order; an ordered array will be sufficiently efficient for this assignment. When a word is input to the neighbor search, you can use hashing or linear search or binary search to find the corresponding word in the array. Internal to the program, you may want to use either a reference to a vertex object or the vertex's index in the array to access a particular vertex; this will depend on your design. Depending on your design choices, it may prove useful to store each vertex's index as a data member within the vertex itself.

Think about your I/O and work through the design carefully. You must be able to conduct multiple trials following the rules above. Thus, you will have a problem if you create multiple I/O readers (e.g., in Java if you create them using new every time you go through the loop running the game).

Particularly in Part 2, vertices will contain useful information that will change over time. In order to keep the data consistent, you will want to keep only a single copy of each vertex, and use references in data structures that need to access it.

Remember when constructing the graph that an edge from v to u is also an edge from u to v. But be careful: Since the number of edges is large, you may run into space problems if you put too much data in an edge. Again, use references or indices to other objects instead of copying large amounts of data into the objects used to represent edges.

Test Files:

The directory ~csci311/HW08 contains three dictionary files:

• 5lw-s.dat, a small dictionary containing 12 words. This is particularly useful for initial development, and allows you to print out full data structures (e.g., the whole graph if you'd like).
  
  
• 5lw-m.dat, a medium-size dictionary containing 1390 words. This will be useful in tuning your program once you've basically got things working.
  
  
• 5lw.dat, the full dictionary file of 8938 words. This file contains the complete list of five-letter English words legal in Scrabble. If your program is not space- and time-efficient, this file will give it fits.

• Our executables: neighbors 5lw-s.dat < neighbor-script
  Note that you can substitute any of the dictionary file names for 5lw-s.dat.
  Depending on your execution path, you may need to run ./neighbors 5lw-s.dat < neighbor-script
• For your code in Java, you can run it as follows: java neighbors 5lw-s.dat < neighbor-script

By the way, you are encouraged to report any bugs in either sample program to the instructor.

Working in teams: For this assignment you are asked to work in teams of no more than 2. If you need someone to work with on this project, please let me know as soon as possible. Also please email me to let me know who is in your team.

Hand-in:

Email your instructor a zipfile of all your source files (*.java files).

Instructions

To hand in your .java files, create a directory named with the last name of one of the team-members, for instance, yourname/. Copy all of the Java files (i.e., those that end in .java) for your solution to this directory. Do not include any other files (dictionary files, class files, scripts, back-up files, etc.) in this directory.

Zip this directory into a zip file, and mail it to your instructor with the subject line "CSCI 311 Neighbors Handin".