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

Table of Contents

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.
    """
    return s

def make_word_from_list(lst):
    """Creates an instance of the word ADT from the list of characters lst.
    """
    word = ""
    for char in lst:
        word += char
    return word

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'
    """
    return word

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']
    """
    return [c for c in word]

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
    """
    goal_word_str, guess_str = get_string(goal_word), get_string(guess)
    num_common = 0
    for c in goal_word_str:
        if c in guess_str:
            num_common += 1
    return num_common

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
    >>> foo(mwfs('player')) == bad_num_letters
    True
    >>> foo(mwfs('steel'))
    4
    >>> foo(mwfs('steal'))
    5
    >>> foo(mwfs('aaaaa')) == not_a_word
    True
    >>> foo(mwfs('least')) == win_message
    True
    """
    def compare(guess):
        if not is_valid_guess(guess):
            return not_a_word

        guess_str, goal_word_str = get_string(guess), get_string(goal_word)
        if len(guess_str) != len(goal_word_str):
            return bad_num_letters
        if guess_str == goal_word_str:
            return win_message
        return num_common_letters(goal_word, guess)
    return compare

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]
    """
    if n == 0:
        return [[]]
    if len(lst) == n:
        return [lst]
    use_first = [ [lst[0]] + x for x in subsets(lst[1:], n - 1) ]
    dont_use_first = subsets(lst[1:], n)
    return use_first + dont_use_first

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
    """
    return score == num_common_letters(make_word_from_list(letter_list), guess)

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']]
    """
    return [x for x in possible_subsets if compatible(word, score, x)]

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 = []
    for letter in letters:
        subs = [sub for sub in possible_subsets if letter in sub]
        if len(subs) == len(possible_subsets):
            present += [letter]
        elif subs == []:
            not_present += [letter]
    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: