copyright Steve J. Hodges   http://steveh.net/cs20j/cs20j-hw07.html

CS20j Fall 2018

Assignment 7 (Six Degrees Of Bacon)

Project Directory

20j-7

Main Class Name

Program7

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. 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 reference. This allows you to link WNodes together. You'll need to do this to recreate the path from your starting word to "bacon." You may define the WNode class to be an inner class. You program will feature many ArrayList<WNode> objects, and the data structure for the search will be an ArrayList< ArrayList<WNode> >.


class WNode{
  public WNode(String s){word = s; link=null;}
  String word;
  WNode link;
}

Program Dictionary

For this assignment, you'll need to maintain a list of five letter words (your "dictionary.") Unlike the Cinco assignment, you'll need the ability to remove words from the dictionary as they are "discovered." Use a HashSet, HashMap, or ArrayList to store the words in your dictionary. These words may be stored as Strings or WNodes.

Searching for the Word

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

Reversed List

Implement support for the optional "-r" parameter which reverses the order of the word list that you print(i.e. from starting word to "bacon" instead of from "bacon" to the starting word.)

What to turn in

For this assignment, you will be creating a project with several files. All of your project files, should be placed in a directory named 20j-7 inside your home directory on Pengo. This directory should not contain any files not part of your project, and it should not contain any subdirectories. I will collect all of the files from this directory.

Sample Runs

[...]$ java Program7 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
[...]$ 

[...]$ java Program7 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
[...]$ 

[...]$ java Program7 -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.
[...]$