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:
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":
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.
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.
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
... (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
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.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
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).