Homework Assignment #4

Due Friday, April 18, midnight
50 points total
I'll accept the homework without penalty up to Monday April 28 at midnight, but strongly recommend you know the material prior to your Final Exam which you should schedule between April 21-26

1. (20 points) Evil Hangman - write in Java or C++

Rather than spend a lot of effort writing a complicated AI game-playing program, sometimes programmers resort to cheating. For example, monsters might know exactly where you are, even if you are hidden behind walls. Let's apply the idea of cheating to playing the game of hangman. Here are our rules for hangman:

1. One player chooses a secret words and writes out a number of dashes equal to the word length.
2. The other player guesses letters. If the player guesses a letter in the hidden word then the first player reveals each occurrence of that letter in the word. Otherwise the guess is wrong.
3. The game ends when all letters in the word have been revealed or the guesser has run out of guesses.

Here is how the first player can cheat. The first player can change the word as long as there is a possible word that matches all the guesses already made.   In our case, we will make it so the computer picks a new words such that there is the largest number of possible remaining valid words.  Here is an example.  Suppose we have a 4 letter word and English only has the following four letter words:

``` ALLY BETA COOL DEAL ELSE FLEW GOOD HOPE IBEX ```

Now, suppose your opponent picks the letter 'E'. You now need to tell your opponent which letters in the word you've "picked" are E's. But since you are evil, you haven't really picked a word and so you have multiple options about where you reveal the E's. Here is the above word list, with E's highlighted in each word:

``` ALLY BETA COOL DEAL ELSE FLEW GOOD HOPE IBEX ```

Notice that every word in your word list falls into one of five "word families":

• ---- , which contains the words ALLY, COOL, and GOOD
• -E--, which contains the words BETA and DEAL
• E--E, which contains the word ELSE
• --E-, which contains the words FLEW and IBEX
• ---E, which contains the word HOPE

Since the letters you reveal have to correspond to some word in your word list, you can choose to reveal any one of the above five families. In our game we will pick the family with the most words in it.  In this case it means picking the family ----, which reduces your word list down to:

`ALLY COOL GOOD`

In this case, since you didn't reveal any letters, you would tell your opponent that his guess was wrong.  The following diagram shows a few more guesses.

What if the opponent guessed a letter that isn't anywhere in the word list?  For example, when the list contained ALLY COOL GOOD what if the opponent guessed "T"?  This is fine, because the largest word family would be ---- with no T in it, which is all three words, so you pick it and keep the same word list.

To do:

1. Read this file, words.txt, which contains 87314 words, into your program. Note that all the words are in lowercase.
2. Prompt the user for a word length (in our example it was 4 letters).
3. Prompt the user for a number of guesses.
4. Play Evil Hangman using the algorithm described below:
1. Construct a list of English words whose length matches the input length.
2. Print out how many guesses the user has left, letters already guessed, number of words remaining in the pool of possible words, and the current blanked-out version of the word.
3. Prompt the user to enter a single letter guess.
4. Partition the words into groups by word family.
5. Find the most common word family, set the current list of words to only those in the most common word family, and report the position of the letters (if any) to the user. If the word family doesn't contain any copies of the guessed letter, subtract a remaining guess from the user.
6. If the player has run out of guesses, pick a word from the word list and display it as the word that the computer initially "chose."
7. If the player correctly guessed the word then congratulate him or her.

It's up to you how to partition the words into word families, update your word list, etc. Think about what data structures would be best for tracking word families and the master word list. You might consider a heap, binary search tree, stack, or queue.  You are free to use the STL or Java collection classes if you wish.  Think about your design before you start coding and it will save you a lot of time and effort.

Hints:

• Letter position matters just as much as letter frequency. You can't just count up the letter frequency. For example, BEER and HERE have different families even though they have the same number of E's.
• Don't enumerate all possible word families. There are too many of them (2^n). You should get the word families to enumerating through actual words in the word list and looking for patterns.

2. (15 points) Shortest Path on a Map  - Write in Java or C++

The map below represents a crude graph of places around Anchorage. Each location is a node. The red lines indicate edges between nodes. The edges have weights, which is the distance between the nodes. All of this information is stored in the data below, which you can save in a text file and read into your program.

The format of the file is:

Line 1: Number of nodes in the file

The following then repeats for the number of nodes in the file:

Number of node (e.g. 1 on the map)
Name of node (e.g. "JBER" on the map)
Number of edges from this node
NeighboringNodeNumber  WeightOfEdgeToNode
... (repeats for the number of edges)

In the data below, Tikahtnu is node number 2 and has 4 edges. It is connected to Node 1 with weight 2.71, Node 3 with weight 2.21, Node 8 with weight 1.8, and Node 9 with weight 2.39

```15 1 JBER 1 2 2.71 2 Tikahtnu 4 1 2.71 3 2.21 8 1.80 9 2.39 3 Science & Nature Museum 5 2 2.21 5 1.19 7 2.60 8 2.18 13 2.40 4 Sullivan Arena 4 5 1.31 6 0.79 14 1.25 15 0.76 5 Merrill Field 3 3 1.19 4 1.31 14 1.45 6 Anchorage Museum 3 4 0.79 7 0.41 15 1.58 7 AK Railroad 2 3 2.60 6 0.41 8 Cheney Lake 4 2 1.80 3 2.18 9 1.25 13 2.09 9 Totem 8 4 2 2.39 8 1.25 11 1.89 13 2.90 10 Campbell Creek Science Center 1 11 1.61 11 Crime Lab 4 9 1.89 10 1.61 12 1.89 13 1.38 12 Golden Donuts 3 11 1.89 13 0.94 15 1.40 13 UAA 6 3 2.40 8 2.09 9 2.90 11 1.38 12 0.94 14 0.81 14 Don Jose 4 4 1.25 5 1.45 13 0.81 15 1.02 15 Steamdot Coffee 4 4 0.76 6 1.58 12 1.40 14 1.02 ``` To do:  Read this data into a graph.  Let the user enter a source and target destination (by number is OK). Then run Dijkstra's algorithm to find the shortest path between the source and target, and output the total distance and path that should be traveled to reach the destination from the source.  Prompt the user if he or she wishes to repeat the calculation.

3. (15 points) Minimum Spanning Tree on a Map - Write in Java or C++

Using the same graph as problem 2, calculate a Minimum Spanning Tree and output the edges and total edge weight of the MST. The MST could be used if you wanted to connect all the nodes in some way (e.g. water, electrical network connection).