15-121 Fall 2020 [REID-MILLER]

HOMEWORK 11 - due Wednesday, December 9 by 11:55PM.

PROBLEMS (5 pts)

1. (2 pts) 16 values are being sorted using the following sorting algorithms: Selection Sort, Insertion Sort, Merge Sort, Quick Sort. At some point during each algorithm, we take two snapshots of the order of the elements so far and we get the following four pairs of charts below. Identify which sort algorithm is being used in each snapshot pair and explain how you determined your answer.

   Sorting Algorithm #1:	Sorting Algorithm #1 cont'd:
   Sorting Algorithm #2:	Sorting Algorithm #2 cont'd:
   Sorting Algorithm #3:	Sorting Algorithm #3 cont'd:
   Sorting Algorithm #4:	Sorting Algorithm #4 cont'd:

2. (1 pt) A Date object consists of a month (an int) and a day (an int). A hash table stores Date objects in an array of length 10 using the following hashing function:
   (month + day) % 10

   The following dates are added to an initially empty hash table in the order shown:

   • 2/1 (February 1)
   • 2/16 (February 16)
   • 3/10 (March 10)
   • 5/18 (May 18)
   • 7/4 (July 4)
   • 10/18 (October 18)
   • 11/15 November 15)

   Show the resulting hash table with chaining (buckets) to resolve collisions.

3. (.5 pts) Consider the min-heap below:

                          18
                        /    \
                     33        26
                    /  \      /  \
                  60    46  52    44
                 /  \  
               88    75
   

   Using the min-heap above, remove the minimum value and restore the heap using the algorithm discussed in lecture. For your answer, show how the resulting heap would be stored in an array.

4. (1.5 pts) You are given the following array of integers in the order shown:

        45 24 30 58 82 64 12 36 
   

   1. Trace the algorithm for building a max-heap out of an array of elements, showing the contents of the array after each value is "inserted" into the max-heap. Use a vertical line to separate the elements in the array that are part of max-heap with those that are not. The first four steps are shown below for you along with the corresponding max-heaps. You do not have to draw the max-heaps in your answer.

      45 | 24 30 58 82 64 12 36                     45
      
      
      
      45 24 | 30 58 82 64 12 36                     45
                                                      /
                                                    24
      
      
      45 24 30 | 58 82 64 12 36                     45
                                                      /  \
                                                    24    30
      
      
      58 45 30 24 | 82 64 12 36                     58
                                                      /  \
                                                    45    30
                                                   /
                                                 24
      

   2. Using your heap from part (a), trace the Heap Sort algorithm to transform the array to a sorted array in increasing order. Show the contents of the array each time the element in index 1 (the root of the heap) is moved to its correct position and the remaining heap is fixed. Use a vertical bar to separate the elements that still belong to the heap from those that don't belong to the heap (i.e. the sorted part of the array).

------  []

Guess:  t

-----t  []

Guess:  a

-----t  [a]  (There are no a's.)

Guess:  e

-e--et  [a]

Guess:  n

-e--et  [a, n]

Guess:  s

se--et  [a, n]

Guess:  r

se-ret  [a, n]

Guess:  c

secret  [a, n]

• HangmanState.java - You will implement the rules of the game of Hangman in this class.
• HangmanTester.java - This class has a main method, which uses your HangmanState class to play a simple console-based game of Hangman. This class has already been implemented for you.
• words.txt - A text file containing a lot of words. HangmanTester uses these words to play a game of Hangman.

This assignment consists of a series of exercises that guide you through the implementation of a very clever Hangman game. You are strongly encouraged to complete these methods in the specified order.

Note: You will be working with Set and Map interfaces throughout this assignment. You may find it helpful to know that Java's TreeSet and HashSet classes implements the Set interface, and Java's TreeMap and HashMap classes implements the Map interface. You are encouraged to use these classes where appropriate.

Note: Feel free to implement additional methods in HangmanState to help you write and test your code.

Assignment

• theAnswer - The original word that the computer chose randomly to be the answer. In the sample game shown earlier, the answer was "secret".
• lettersGuessed - The set of all letters (1-character strings) that the user has guessed so far (including both right and wrong guesses). In the sample game shown earlier, this set contained [a, c, e, n, r, s, t] at the end of the game.
• feedbackToUser - This is the string of blanks and correct letters that has been revealed to the user. For example: -e--et
• possibleAnswers - This is the set of all words that are consistent with the feedback shown to the user, for the letters guessed so far. We'll say a lot more about this later.

Exercises

1. A HangmanState is constructed at the beginning of a game of Hangman. Complete the HangmanState constructor, so that it initializes each of the fields, as follows:
   • lettersGuessed - Initialize this to be an empty set, since at the beginning of a game of Hangman, no letters have been guessed yet.
   • possibleAnswers - For now, simply initialize this to be the set of known words passed as an argument to the constructor. (At the very beginning of a game of Hangman, every word is a possible answer.)
   • theAnswer - Initialize this to be a random word from the set of known words provided. The probability of choosing a particular word should be exactly the same as the probability of choosing any other word. For example, if the set of known words contains the 5 words [the, of, to, and, a], then there should be a 20% chance that your program chooses "the" to be theAnswer, a 20% chance that your program chooses "of" to be theAnswer, and so on.
   • feedbackToUser - Initialize this to contain one blank (hyphen) for each letter in theAnswer. For example, if theAnswer is "secret", then feedbackToUser should be "------".

   As always, you are encouraged to write helper methods when appropriate.

   ---

2. Complete the feedbackFor method, which takes in an answer word, examines lettersGuessed, and returns a feedback string to the user, consisting of blanks and the correct letters that have been revealed to the user. For example, if lettersGuessed contains the letters [a, e, n, t], then feedbackFor("secret") should return the string "-e--et", and feedbackFor("hangman") should return "-an--an".

   Note: We are not looking at the theAnswer field in this method. Later on, we will use this method to determine the feedback for a variety of possible words--not just theAnswer itself. Also, your code should not modify or use the feedbackToUser field.

   ---

3. Complete the wrongGuesses method, which should return a set of all guesses the user has made (as found in lettersGuessed) that did not result in the revealing of a letter in feedbackToUser. For example, if lettersGuessed contains the letters [a, e, n, t], and feedbackToUser is "-e--et", then wrongGuesses() should return the set [a, n].

   Note: Do not use the theAnswer field in this method.

---

4. Complete the letterGuessedByUser method, which is called whenever the user guesses a letter. This method should add this letter to lettersGuessed and update feedbackToUser. For example, if lettersGuessed originally contained [a, n, t] and theAnswer is "secret", and the letter "e" is passed to letterGuessedByUser, then lettersGuessed should now contain [a, e, n, t] and feedbackToUser should now be "-e--et". For now, your code should ignore the mode parameter.

   The HangmanTester class can now play through a complete game of Hangman, prompting you to guess letters and calling letterGuessedByUser after each guess. Compile and run HangmanTester.java to test that you can now play a game of hangman against the computer. (For now, ignore the number printed on the right side of the computer's responses.) Hint: you may find it helpful to print theAnswer while you are testing your code.

---

5. We now come to the fun part of the assignment. We're going to program our computer to cheat at Hangman! Here's the key idea. Suppose the user has received the feedback "hear-" in a game of Hangman. There are only 3 words in the English language that are consistent with this feedback: "heard", "hears", and "heart" (assuming that the user has not already guessed "d", "s", or "t"). The user now appears to have a 1/3 chance of guessing the answer correctly on the next guess. But what if the computer cheats and hasn't decided which of these three words is "the answer"? Instead, the computer can report that the user's guess is wrong no matter what the user guesses, even if they guess "d", "s", or "t"! For example, if the user guesses "d", the computer eliminates "heard" as a possible answer.

   Likewise, we can program the computer to cheat in the user's favor. So, if the feedback is "hear-", the computer can tell the user they are correct for a "d", "s", or "t".

   The remainder of this assignment will guide you through programming your computer to cheat. From this point on, the only purpose of the random theAnswer word is to determine the length of the an unknown word the user has to guess.

   (There is no code for you to write in this exercise.)

---

6. The purpose of possibleAnswers is to keep track of all known words that could turn out to be the answer based on what letters have been guessed so far and what feedback has been revealed. For example, suppose that the list of known words are only:

   the, be, top, and, that, car, have, for, not, you

   Suppose the letters [i, o, t] have been guessed, and the feedback for these guesses is "-o-". Which words are consistent with this information, and are therefore are possible answers?

   Only 2 of the known words are consistent with this information: "for" and "you". Therefore, possibleAnswers should only contain [for, you]. (Note that "top" and "not" are not a possible answer. If they were the answers, the feedback would have been "to-" and "-ot", respectively.)

   Initially, possibleAnswers is all the words. Once the computer has picked a random word, though, we know the only possible answers are words that have the same length as that word.

   Complete updatePossibleAnswers method, so that it removes any words from possibleAnswers that would not have the same feedback already provided to the user. Hint: Use a method you have already written to check if a possible answer is consistant with the feedback to the user.

   Also, call updatePossibleAnswers at the end of the HangmanState constructor, and at the end of letterGuessedByUser. (We need to update possibleAnswers any time feedbackToUser might change, and these are the two places where that might happen.)

   When you use HangmanTester, the number on the right side of the computer's responses should now shrink as you guess letters. This number is the size of possibleAnswers. (This string is generated by HangmanState's toString method.)

7. Complete the generateFeedbackMap method. We will use this method to prepare to cheat! When we call this method we know all the words that the computer could have picked consistent with the feedback the computer has given to the user so far. After the user gives the computer another guess, the we need to determine what feedback to give the user. Instead of updating the user feedback based on theAnswer, we'll completely ignore theAnswer. The end goal is to give feedback that is consistent with all the information the user has been provided so far but keeps possibleAnswers as large as possible. First consider the feedback strings we would provide for every possible answer. For example, suppose that lettersGuessed contains [a, c, l, u], and that possibleAnswers contains:

   what, pump, pull, lute, bump, that, junk, lump, from, jump, will

   If we generate feedback for each of these possible answers, we get:

   possible word	feedback
   what	--a-
   pump	-u--
   pull	-ull
   lute	lu__
   bump	-u--
   that	--a-
   junk	-u--
   lump	lu--
   from	----
   jump	-u--
   will	--ll

   Notice that some feedback strings appear multiple times in this example. The feedback string "--a-" was generated for 2 possible answers ("what" and "that"), and the feedback string "-u--" was generated for 4 possible answers ("pump", "bump", "junk", and "jump"). The generateFeedbackMap method should return an inverted map where the keys are these feedback strings and the values are the number of possible answers that result in that feedback string. For the example above, generateFeedbackMethod should return the following map:

   Key	Value
   -ull	1
   -u--	4
   lu--	2
   ----	1
   --a-	2
   --ll	1

---

8. Complete the mostCommonFeedback method. The output of generateFeedbackMap will eventually be passed as the input to this method. This method should simply return the feedback string that occurred most often (and therefore corresponded to the greatest number of possible words). For example, if the feedback map shown at the end of the previous exercise is passed as the input to this method, then mostCommonFeedback should return "-u--", since this is the feedback string corresponding to the highest value (5) in this map. (If multiple feedback strings are tied for the highest value, it does not matter which of those feedback strings you return.)

---

9. Modify letterGuessedByUser so that it behaves as follows:
   • If mode is NORMAL_MODE (1 of 3 integer constants defined at the top of the file), then letterGuessedByUser should behave exactly as it did before.
   • If mode is HURTFUL_MODE, then letterGuessedByUser will cheat! Instead of updating feedbackToUser based on the theAnswer, we will completely ignore theAnswer (except for its length). We will update feedbackToUser to be consistent with all the information the user has been provided so far but keep possibleAnswers as large as possible. For example, suppose that feedbackToUser is -u-- and the user now guesses a l, resulting in the feedback map shown in the previous exercise. Because -u-- is consistent with the greatest number of possible answers, feedbackToUser should remain -u--. That way, the user will have to keep guessing until there is only 1 possible answer. Hint: How can you use the two previous methods?

   Modify HangmanTester so that it plays in HangmanState.HURTFUL_MODE. It should now take a lot more guesses to win a game of Hangman. (This is a great way to make your friends look stupid!)

---

10. Finally, modify letterGuessedByUser so that, in HELPFUL_MODE, the computer cheats in the user's favor. Actually, HELPFUL_MODE should behave exactly like HURTFUL_MODE, but with one difference. In HELPFUL_MODE, the computer should modify feedbackToUser to be the most common feedback string (consistent with the most possible answers) that reveals a letter. For example, suppose again that feedbackToUser is -u-- and the user now guesses a l, resulting in the feedback map shown above. Although -u-- is consistent with the greatest number of possible answers, we should not choose this feedback string, because it is exactly the same as the old value of feedbackToUser, and this would not be helpful to the user. Instead, we'll update feedbackToUser to be lu--, because this is the most common feedback string that reveals a letter. On the other hand, if the user guesses r, and the letter r does not appear in any of the possible answers, then the feedbackToUser should not change (because it is impossible for the computer to reveal a letter). In this situation, there will be only one feedback string in the map.

    (Here's the rationale. Whenever possible, the computer will be forced to reveal a letter, instead of telling the user that their guess was wrong. And by otherwise leaving possibleAnswers as large as possible, the computer will have plenty of options for cheating in the user's favor on the next guess.)

    Hint: If there is more than one feedback string in the map, remove feedbackToUser from the map (in the above example -u--) before getting the most common feedback.

    Test out your code in HangmanState.HELPFUL_MODE. (This is a great way to make your friends feel better.)

Documentation & Style

Write comments to document all of the public features. Include documentation for all the parameters and return value or changes to the state of the instance of the class. Add additional comments in your methods to explain your code where necessary. Use appropriate variable names for self-documentation and indent properly.

Hand-In Instructions

Make sure to keep a copy of your work just in case!