In this assignment you are to write a Java or Python 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 single-source shortest paths 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 (was due Monday 04/24/2017):

• 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, if you use Java, your Vertex class must extend the HeapElt class from that earlier assignment. For the moment, the record and handle data members will not be used. If you use Python, you must include the handle datamember and the getHandle(), setHandle(), and getKey() methods. These methods won't be used in this phase of the assignment.
  
  
  
• 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" 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.

Part 2 (due Wednesday 05/01/2017):

• Consistent with the specification for Part 1, your program must:
  • Open an input file, exiting if the file is not found, and
  • Read the words from the dictionary file and construct the graph for that file in a reasonable amount of time.
  
  
  
• Your program should play the word game as described below:
  • For each trial, ask the user to provide two five-letter words (as in Part 1, case should not matter). You should read in two words before testing if they are in the dictionary. Treat words of fewer or more than five characters as not in the dictionary. If both words are in the dictionary that was loaded, you should print the minimum cost of transforming the first word to the second using words in that dictionary. After printing the cost, you should print the sequence of words in a minimum-cost transformation of the first word into the second. Such sequences may not be unique, so any least-cost sequence is acceptable. An example interaction is given below:

    Enter the first five-letter word: earth
    
    Enter the second five-letter word: water
    
    The best score for EARTH to WATER is 9 points.
    
            EARTH  DARTS  DARES  DATES  DATER  WATER  
    
    

    If either (or both) of the the input words is not in the dictionary, you should print a message to that effect and end the current trial.
    
    

  • After every trial (successful or otherwise), 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 word game described 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.

  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). That will cause you to lose input from the script, which is entered by redirecting the standard input.

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

  Hints for Part 2:

  Heap Handles: Dijkstra's algorithm for finding shortest paths was explained in lecture, and is discussed in the text. It's a version of priority-first search similar to Prim's algorithm, but with the distance metric changed to include the total distance from the source vertex. You should use your "heap with handles" to implement this algorithm: When you determine the distance to a vertex and remove it from the heap, you update the distances (priorities) of its neighbors. This may involve changing (reducing) priorities, which will require updating the heap. Thus, each vertex must know its position in the heap array so that the proper heapification method can be called if its priority changes. To accomplish this, your Vertex (or equivalent) class should extend the HeapElt class, which includes the data members record (which is Comparable) and handle.

  Printing Shortest Paths: When writing your loop that calls the shortest path algorithm, think about implementation - how do you construct paths using information provided by the algorithm? The predecessor information (which should be stored in the Vertex objects) should be of use. Remember that you need to print paths in order from the first word entered to the second word entered. Note that you are not required to search in that direction. Remember, in an undirected graph a shortest path from u to v is also a shortest path from v to u.

  Reinitializing Between Trials: A common error students make in implementing this program is not reinitializing all objects before the start of an additional trial. Values left around by a previous trial can be misinterpreted by the algorithm and can create incorrect paths. Testing your program from one word to a second, then from the second back to the first, then from the first to the second again will help detect such problems; check to see that the distance is the same each time, though the path may vary in the opposite directions.

  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.
  
  

  There is a file entitled wordgame-script that you can redirect into your program. It contains one of the scripts I will use to test your program, so make sure that your program behaves properly when you use the script.

  The ~csci311/HW08 directory contains an executable neighbors, which you can use to check your program for Part 1. This executable runs directly at the command line on Bucknell's Linux machines; it is not a Java .class file. Note that the order in which neighbors are printed is not specified, and may vary with your implementation, so don't expect that output from your program will exactly match the output of neighbors.

  That directory also contains the executable wordgame, which plays the wordgame. You can use it as a test program to verify that your program is working correctly, and also as a reference to help you understand the specification for the assignment. This executable runs directly at the command line on Bucknell's Linux machines; it is not a Java .class file.

  Here is how to run the wordgame program:

  • Our executables: neighbors 5lw-s.dat < wordgame-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 ./wordgame 5lw-s.dat < wordgame-script
  • If you write your code in Java: java wordgame 5lw-s.dat < wordgame-script
  • If you write your code in Python: python wordgame.py 5lw-s.dat < wordgame-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 can 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. If you worked alone on Part~1 but are working with a partner on Part~2, please let the instructor know via email.

  Hand-in:

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

  Instructions

  To hand in your .java or .py file(s), create a directory named with the last name of one of the team-members, for instance, yourname/. Copy all of the Java or Python files (i.e., those that end in .java or .py) for your solution to this directory. Do not include any other files (dictionary 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 Wordgame Handin".