copyright Steve J. Hodges   http://steveh.net/cs19/cs19-hw06.html

CS19 Fall 2014

Assignment 6 (Six Degrees Of Bacon)

Project Directory

19-6

Resulting Executable

p6

Useful diagram


Description of the program

Allow the user to select a known five letter word. Find a path of adjacent words from that word to "bacon." Adjacent words are words with one letter different between them (i.e. "baron" and "bacon" are adjacent because only their third letter is different.) Inform the user if they've entered an unknown word, or if there is no path from their word to "bacon." Implement this assignment using the techniques described in this assignment and in class.

User Interface

Your program should run with one or two parameters on the command line. One parameter is the file name of the word list file to open. Words in the file are one per line and unsorted (see the sample file sgb-words.txt in your home directory on Pengo.) An optional parameter is the "-r" option which you will ignore unless you implement the extra credit given below. Use the first two lines of output for your name, email, etc. Prompt the user for the word to search from, and then output the path of words, one word per line, starting from "bacon" or inform the user that no path exists.

Word Node

Instead of using a string to represent a word, you will use the WNode class. The WNode class contains a string and it also contains a WNode pointer. This allows you to link WNodes together. You'll need to do this to recreate the path from your starting word to "bacon." Your program will feature many Vector<WNode*> variables, and the data structure for the search will be an Vector< Vector<WNode> >. In order to simplfy the syntax, I recomend the use of two typedef commands — one to create an alias for a "pointer to WNode" and the other "a Vector of pointers to WNodes."

#ifndef W_NODE__H
#define W_NODE__H

#include <vector>

// "Linkable" (to create a trace) string (a word) 
struct WNode{
  WNode(std::string s=""){word = s; link = 0;}
  std::string word;
  WNode *link;
};

typedef WNode* WNodePtr;
typedef std::vector<WNodePtr> WNodePtrVector;

#endif

Program Dictionary

For this assignment, you'll need to maintain a list of five letter words. Unlike the Cinco assignment, you'll need the ability to remove words from the list. For this assignment, then you should use a unordered word list (not alphabetical) with linear searching and the "fast array delete" technique as described in class. I recomend that you use a Vector for this, or you could use your own partially filled array or linked list class.

Searching for the Word

Start with (a pointer to) your starting word WNode in an Vector by itself. This Vector will be the first (index of zero) in your Vector of Vectors). Add every (pointer to) WNode to another Vector (and remove it from your word list dictionary) if it is adjacent to your starting word. This Vector will be the second (index of one) in your Vector of Vectors). Continue creating additional Vectors with all of the words that are adjacent to words in the previous Vector until one of two things happens. One, you'll find the WNode with "bacon" or the next Vector is empty (in which case you've exhausted all of your search options and determined that no path to "bacon" from your word exists.

Extra Credit

If the user specifies the optional, "-r" parameter, reverse the order of the word list that you print(i.e. from starting word to "bacon" instead of from "bacon" to the starting word.) You will only get credit for this if your program functions correctly, so don't attempt this until a through testing of your project.

Sample Runs

[...]$ ./p6 sgb-words.txt
Six Degrees of Bacon Sample Solution
Steve J. Hodges, sthodges@cabrillo.edu
Your word?draft
bacon
baron
caron
capon
capos
capes
canes
banes
bands
bends
beads
brads
brans
brant
grant
graft
draft
[...]$ 

[...]$ ./p6 sgb-words.txt -r
Six Degrees of Bacon Sample Solution
Steve J. Hodges, sthodges@cabrillo.edu
Your word?caper
caper
capes
capos
capon
caron
baron
bacon
[...]$ 

[...]$ ./p6 -r sgb-words.txt
Six Degrees of Bacon Sample Solution
Steve J. Hodges, sthodges@cabrillo.edu
Your word?epoch
no path from epoch to bacon.
[...]$