Compsci 101, Fall 2012, Lab 5

AnagramFree

Read the AnagramFree APT -- this part of the lab suggests a new Python construct, a set, that makes solving the APT simpler.

In Python a set does not store duplicates, each value is only stored once. For example, the code below generates the output shown:

x = set([1,2,3,1,2,3,1,2,3,1,1,1]) print len(x), x Output is:

  3, set([1,2,3])

A set can be created from a list as shown, and elements can be added to the set using the set method .add, e.g., s = set() s.add("big") s.add("big") s.add("big") s.add("small") s.add("small") print len(s),s will generate

   2, set(['small','big'])

1. Write an expression that determines the number of different strings in the list foods below, e.g., that sets diff to have the value 4, but will work even if the values in food change (answer on handin pages): foods = ["bagel", "bagel", "cheese", "bagel", "hummus" "onion", "bagel", "onion"] diff =
2. For a string s, the value of sorted(s) is a sorted list of the individual characters in the string, e.g., sorted("apple") = ['a','e','l','p','p']

   What's the value of the list comprehension below (write it out) --- you should have a list of lists:

   [sorted(w) for w in ['cow', 'dog', 'ant', 'bat']]
3. The string method join creates a string from a list of strings as shown below.

   method call	result
   ''.join(["a", "r", "t"])	"art"
   ' '.join(["the","big", "dog", "runs"])	"the big dog runs"

   The string to the left of the dot '.' is inserted between each string in the list that's a parameter to the join method and one string is returned as shown --- the new string is formed by concatenation. In the first call above an empty string '' is inserted, in the second a space ' ' is inserted.

   Using sorted and join write a list comprehension to create in unique the sorted string version of each string in words, e.g., to create ["aet", "aet", "aet", "abt", "abt", "deo" "deo"] out of the list ["eat", "aet", "tea", "bat", "tab", "ode", "doe"]

   words = ["eat", "aet", "tea", "bat", "tab", "ode", "doe"] unique =
4. Using the techniques from the previous problems try to write a one line version of getMaximumSubset for the AnagramFree APT. Use set, sorted, join and a list comprehension. If you can't do it one line, use more than one. def getMaximumSubset(words): return len( )

   ---

   ChocolateBar

   Read the ChocolateBar APT.

5. Write a function str_unique that returns true if all the letters in its string parameter are different (no repeats) and false otherwise. Use a set for this, you may want to to use list("help") to change a string "help" to the list ["h","e","l","p"], for example.

   code on handin pages

   Call	Return
   str_unique("slight")	true
   str_unique("differ")	false
   str_unique("monster")	true

6. Write words to describe how to solve this APT. What will be hard in implementing your solution?

   Hangman

   Suppose a variable guessed is a list that represents how many letters of the secret word have been guessed. For example, suppose the secret word is "ukelele". Then guessed is initially ["_", "_", "_", "_", "_", "_", "_'].

   A function process_letter works as follows:

   secret = "ukelele" guessed = ["_"]*len(secret) z = process_letter(guessed,secret,"X") # returns ["_", "_", "_", "_", "_", "_", "_", ] z = process_letter(guessed,secret,"K") # returns ["_", "K", "_", "_", "_", "_", "_", ] guessed = z z = process_letter(guessed,secret,"L") # returns ["_", "K", "_", "L", "_", "L", "_", ]
7. Write the function header for process_letter -- note what the types of the three parameters to your function are (see handin pages).

8. In writing process_letter you'll need to access elements of secret and guessed. Write the code that loops, checks whether a letter has been guessed, and modifies guessed (the list parameter) appropriately?

   Suppose that instead of a word you want to guess a phrase --- like a pro-basketball team: such as "New York Knicks", "Miami Heat", "Los Angeles Lakers". This could lead to this initialization

   secret = "New York Knicks" knowledge = [["_"]*len(p) for p in secret.split()] Write down the value of the list knowledge?

9. Given the existence of process_letter from the previous problem, how can you process a guess from the user to change all elements of knowledge, e.g. what's the value of knowledge after executing the code below? secret = "New York Knicks" slist = secret.split() knowledge = [["_"]*len(p) for p in secret.split()] for i in range(len(knowledge)): knowledge[i] = process_letter(knowledge[i], slist[i],"K")
10. Explain what knowledge represents in words. How will you display it? Write the code that's the equivalent of the previous/one word version for a list of strings: "_" or "a" or "z" or .. print ' '.join(knowledge)
11. Note that knowledge is a list of lists, how can these be displayed for hangman, how do you display all of them like what's below (for New York Knicks), e.g., with extra spaces between the chunks of underscores? Write code to do this.

        _ _ _   _ _ _ _   _ _ _ _ _ _