# 61A Homework 4

Due by 11:59pm on Wednesday, 7/9

Readings: You might find the following references useful:

Submission: See the online submission instructions. We have provided the following starter file: hw4.py

## Required Files

In addition to the hw4.py starter file, you will also need the validguesses.txt file and the ucb.py file, although you will only need to edit and submit hw4.py.

## Introduction

In this assignment, we will implement a word game! In this game, there is a word master and a player. The word master chooses a goal word between 4 and 7 letters long with no repetitions. The player wants to guess the goal word that the word master is thinking of.

Each time the player guesses a word, the word master will respond with the number of letters in common between the guess and the goal word. The player uses this information in order to deduce the goal word. Note that the player is allowed to guess words with repetitions - in this case, each repetition is counted just once. For example, if the goal word is 'play' and the guess is 'ball', then the word master will respond with '2' (and not '3'). The order of the letters within the word is irrelevant for the purpose of counting letters in common.

Here is an example game:

``````>>> play_game()
Playing with a 4 letter word.
Enter a word to get its score, h for a hint, or q to quit.
ball
The word ball has 2 letters in common
Enter a word to get its score, h for a hint, or q to quit.
call
The word call has 2 letters in common
Enter a word to get its score, h for a hint, or q to quit.
back
The word back has 1 letters in common
Enter a word to get its score, h for a hint, or q to quit.
duck
The word duck has 0 letters in common
# At this point, we know c is not in the word, and because of
# call, we know that a and l are in the word.
Enter a word to get its score, h for a hint, or q to quit.
clay
The word clay has 3 letters in common
# Now we know that y is in the word.
Enter a word to get its score, h for a hint, or q to quit.
play
Congratulations! You win!``````

### Question 1

We will need to work with both strings and lists of characters in this assignment. So, we will use data abstraction! Implement the word abstract data type. It's main purpose is to unify the two possible representations, so that we can work with both strings and lists of characters, whichever happens to be more convenient. As a result, it has two constructors and two selectors.

Make sure you do not commit any Data Abstraction Violations (DAVs) in the subsequent questions!

``````def make_word_from_string(s):
"""Creates an instance of the word ADT from the string s.
"""

def make_word_from_list(lst):
"""Creates an instance of the word ADT from the list of characters lst.
"""

def get_string(word):
"""Returns the string representation of word.

>>> get_string(make_word_from_string('hello'))
'hello'
>>> get_string(make_word_from_list(['w', 'o', 'r', 'l', 'd']))
'world'
"""

def get_list(word):
"""Returns the list of characters representation of word.

>>> get_list(make_word_from_string('hello'))
['h', 'e', 'l', 'l', 'o']
>>> get_list(make_word_from_list(['w', 'o', 'r', 'l', 'd']))
['w', 'o', 'r', 'l', 'd']
"""

### Question 2

A key operation in this game is finding the number of letters in common between the goal word and a guess word. Implement `num_common_letters`, which performs this operation. The goal word will not have repetitions, but the guess word may have repetitions. Remember that the only thing you can do with words is to call `get_string` and `get_list` on them. You cannot loop over them, or check equality, or call `len` on them, etc. (You can do these on the strings/lists that you get out of the words though.)

``````def num_common_letters(goal_word, guess):
"""Returns the number of letters in goal_word that are also in guess.
As per the rules of the game, goal_word cannot have any repeated
letters, but guess is allowed to have repeated letters.
goal_word and guess are assumed to be of the same length.
goal_word and guess are both instances of the word ADT.

>>> mwfs, mwfl = make_word_from_string, make_word_from_list
>>> num_common_letters(mwfs('steal'), mwfs('least'))
5
>>> num_common_letters(mwfs('steal'), mwfl(['s', 't', 'e', 'e', 'l']))
4
>>> num_common_letters(mwfl(['s', 't', 'e', 'a', 'l']), mwfs('thief'))
2
>>> num_common_letters(mwfl(['c', 'a', 'r']), mwfl(['p', 'e', 't']))
0
"""

### Question 3

Now, implement the function `make_word_master`. This takes as input a goal word and returns a function that behaves like the word master - it accepts a guess word as input, and returns the number of common letters between the goal word and the guess word. It should also check that the guess word is a valid word of the right length. You may find the `is_valid_guess` function useful, which checks that the word is present in the dictionary. When the guess matches the goal word, it should return `win_message`.

``````def make_word_master(goal_word):
"""Takes in the word to be guessed and returns a function which
takes in a guess and does what the word master does, that is:
If the guess is of incorrect length, it returns bad_num_letters.
If the guess is correct, it returns win_message
Otherwise, it returns the number of letters in common.

>>> mwfs = make_word_from_string
>>> foo = make_word_master(mwfs('least'))
>>> foo(mwfs('water'))
3
True
>>> foo(mwfs('steel'))
4
>>> foo(mwfs('steal'))
5
>>> foo(mwfs('aaaaa')) == not_a_word
True
>>> foo(mwfs('least')) == win_message
True
"""

Now that you have implemented `make_word_master`, you can play the game! However, the hint system will not work yet (that's the next part). You can run the game by typing

``python3 hw4.py``

### Question 4

Now, we will add a system that makes logical deductions about the goal word based on the scores that the word master has assigned to each of the guessed words.

The main idea is that we will keep a list of all of the possible combinations of letters that could work based on the information we have. At the beginning, we have no information, and so any subset of the right size would be a possible subset.

To solve this, implement `subsets`, which takes in a Python list `lst` and a non-negative integer `n`, and returns a list of all of the subsets of `lst` that have size `n`.

Then, if the goal word has `l` letters, the initial list of possible combinations of letters is just `subsets(letters, l)`

``````def subsets(lst, n):
"""Returns all subsets of lst of size exactly n in any order.
lst is a Python list, and n is a non-negative integer.

>>> three_subsets = subsets(list(range(5)), 3)
>>> three_subsets.sort()  # Uses syntax we don't know yet to sort the list.
>>> for subset in three_subsets:
...     print(subset)
[0, 1, 2]
[0, 1, 3]
[0, 1, 4]
[0, 2, 3]
[0, 2, 4]
[0, 3, 4]
[1, 2, 3]
[1, 2, 4]
[1, 3, 4]
[2, 3, 4]
"""

### Question 5

Now that we can get the initial list of letter combinations, we need to figure out how to update the list when we get more information from the word master. The way we will do this is by throwing out any letter combinations that are not compatible with the answer given by the word master.

First, implement the `compatible` function, which returns `True` if the letter combination is compatible with the score given by the word master for a particular word. Hint: Do not overthink this problem. There is a function that you have already implemented that will help.

``````def compatible(guess, score, letter_list):
"""Returns True if it is possible for the word to get the score,
assuming that the true word only contains letters from
letter_list.
Precondition:  len(word) == len(letter_list)

>>> mwfs = make_word_from_string
>>> compatible(mwfs('steal'), 5, ['l', 'e', 'a', 's', 't'])
True
>>> compatible(mwfs('blanket'), 6, ['a', 'b', 'e', 'l', 'n', 'r', 't'])
True
>>> compatible(mwfs('cool'), 4, ['c', 'o', 'l', 'd'])
False
>>> compatible(mwfs('found'), 1, ['d', 'e', 'f', 'g', 'h'])
False
"""

Now, using your `compatible` function, implement `filter_subsets`, which returns a new list containing only those letter combinations that are compatible with the score given by the word master for a particular word.

``````def filter_subsets(word, score, possible_subsets):
"""Returns the subsets for which word would get the given score.

>>> word = make_word_from_string('steel')
>>> sub1 = ['a', 'b', 'e', 'l', 's']
>>> sub2 = ['b', 'e', 'l', 't', 'z']
>>> sub3 = ['s', 't', 'e', 'a', 'l']
>>> sub4 = ['b', 'l', 'e', 's', 't']
>>> sub5 = ['p', 'e', 'a', 'r', 's']
>>> filter_subsets(word, 3, [sub1, sub2, sub3, sub4, sub5])
[['a', 'b', 'e', 'l', 's'], ['b', 'e', 'l', 't', 'z']]
"""

### Question 6

Finally, we need to present the information in a human-readable format. (It is not very helpful to print out a giant list of possible letter combinations.) One way to do this is to list out the letters that must be in the goal word, and to list out the letters that cannot be in the goal word.

Write `make_deductions`, which does exactly this. We know that a letter must be in the goal word if it is in every possible letter combination. We know that a letter cannot be in the goal word if it is in none of the possible letter combinations.

``````def make_deductions(possible_subsets, letters):
"""Infers which letters must be in the word to be guessed, and
which letters must not be in the word.
A letter must be in the word if it is in every possible subset.
A letter is not in the word if it is not in any possible subset.

>>> letters = ['a', 'b', 'c', 'd', 'e', 'f']
>>> subsets = [['a', 'b', 'c'], ['b', 'a', 'e'], ['e', 'a', 'c']]
>>> present, not_present = make_deductions(subsets, letters)
>>> present
['a']
>>> not_present
['d', 'f']
"""
present = []
not_present = []
return present, not_present``````

Once you have completed `make_deductions`, the hint system will be fully functional. Try it out - it is quite powerful! In fact, the game becomes a little too easy with these hints.

### Question 7

Now that you are done with all the questions, it's time to check if you committed any data abstraction violations. Go back to your code for the word ADT and change it so that a word is represented by a function. (Or if you already used a function representation, try some other representation.) Then make sure that all of your code for the other questions still work.

Note: You do not need to submit anything for this part. This question is present to make sure you have not made any data abstraction violations in the previous questions.

### Question 8: Challenge Problem (optional)

Extend the game and make it more interesting and/or useful. If you do something especially cool and show it to us, we may add it so that future semesters can also benefit from it. Here are some ideas, some of which would require knowledge of Python beyond that which we have taught you (but don't let that stop you!) They are sorted in order of increasing estimated difficulty:

• Come up with a good name for this game.
• The `play` function is rather large and ugly. Figure out a good way to abstract it away in order to make the code more readable.
• Make a better hint system that doesn't give all possible deductions, just one small hint. Perhaps limit the number of hints.
• Add a scoring system to the game. Have it take into account both the number of guesses and the time taken to find the goal word.
• Make a GUI (graphical user interface) for the game, similar to the GUI for hog (which was in `hog_gui.py`)
• Create an AI for this game, that is, make a program that will guess words until it finds the goal word. Try to minimize the number of guesses until it finds the goal word.