A word ladder is a word game. The player is given a start word and an end word and must come up with a "ladder" of words where each word in the ladder is no more than one letter different than the word before it and the word after it.
Here are a few word ladder examples:
For this assignment, you will write a program to find the smallest word ladder given a start word and an end word. To keep things simple, you will only be working with 5 letter words.
You can download the dictionary of 5 letter words we will be using to grade your program here: words5.dict.
The program will take as command line arguments the name of the dictionary file, the start word, and the end word. Your program will output to standard output the word ladder. The output must start with the start word and end with the end word, and output no other characters other than whitespace. We will have a program that will take your output in this format as its input and verify you have a valid word ladder.
There are many algorithms out there to solve this problem including some that are much more efficient than the one we will be using. This assignment has been designed to give you practice implementing and using stacks and queues, therefore you must use the following algorithm.
Create a stack of strings.
Push the start word on this stack.
Create a queue of stacks.
Enqueue this stack.
While the queue is not empty
For each word in the dictionary
If a word is one letter different (in any position) than the top string of the front stack
If this word is the end word
You are done! The front stack plus this word is your word ladder. Don't forget to output this word ladder.
Make a copy of the front stack.
Push the found word onto the copy.
Enqueue the copy.
Dequeue front stack.
You must also implement a WordLadder class with the following public interface:
The dictionary is in a file. You will want to read in the dictionary once and store it. Which of the "linear" data structures we've learned so far should we choose to store this dictionary in: vector, list, queue, or stack? Once you begin to understand the algorithm, you will find that you can make this algorithm run much faster if you take out of the dictionary, or at least ignore, any word you've added to a potential word ladder.
You are required to use STL's list or slist (whichever is the most efficient possible given your algorithm) to store the dictionary. Do not make your own linked list as I want you to have practice using the STL list along with their iterator. Why is a linked list a good choice here?
What modules should you create and what should each module be responsible for? You should have several private member functions in the WordLadder class.
Much of the grading of this assignment will be based on your OOP and general programming skills. Be sure to use good programming techniques where possible (use of classes, functions, good parameter passing techniques, error checking, encapsulation, object oriented programming). Make sure your program is user friendly.
You must at least use the compilation flags -W -Wall -Werror -pedantic. Programs will be graded under linux on bell.cs.ucr.edu. Programs that do not compile will receive a zero. Be sure to download and re-test your submission from iLearn.
You should ALWAYS turn in what you have thus far on our program at least 5 hours before the due date (by 4pm). Then continue to work on your program and turn in more current versions as you get them working.
You must turn in a tar file that contains a Makefile and all source code necessary to builf your program. The grader should only have to type the command "make", and everything should just work. If your code does not compile this way, you will get a zero.
DO NOT turn in any files that are not required for the final compilation of your assignment. Do not turn in your temporary .cc files or your saved/old revisions of your .cc files or your debug folders. If you turn in files that aren't required for your assignment, it hinders the grading processes. You will be docked points if you turn in extraneous files.
Please remember, at-home programming assignments are not lab assignments and you may not team-code with your lab partner or any other individual. Limited collaboration may be acceptable, but programs must represent YOUR OWN original work. Sharing code or team-coding are strictly not allowed. Copying code from ANY source (any book, current or past students, past solutions (inluding your own past solutions), web, etc) is strictly not allowed even with citation. Collaboration may consist of discussing the general approach to solving the problem, but should not involve communicating in code or even pseudo-code. Students may help others find bugs. Your code MUST be unique -- the odds of randomly producing similar code is very low. Computing, like surgery or driving a car or playing golf, can only be learned by doing it yourself!