CSCI 150: Bonus Lab

This lab is completely optional! Any points earned will be added to your total lab score for the course, but you will not be penalized for any mistakes (or not doing the lab at all). It is an opportunity to get more practice with recursion. The purpose of this lab is to:

• Practice with Sets.
• Work on reading from files and string manipulation.
• Do fun stuff with words!

    team = set()                       # makes a set with 0 elements
    team = {"adam", "liz"}             # makes a set with 2 elements
    len(team)                          # 2 
    team.add("olivia")                 # adds "olivia" to team
    team.remove("adam")                # removes "adam" from the team
    for p in team :                    # iterates through elements of team
    "olivia" in team                   # True
    "apollo" in team                   # False
    "sophia" not in team               # True
                  

Part 1 - Anagrams

anagrams.py: partner encouraged.

An anagram is just a rearrangement of the letters in the word to form another word or words. For example, if you rearrange the letters in

    oberlin student 
                

    let none disturb 
                

   
    intends trouble
                

For this part of the assignment, you'll be writing a program called anagrams.py to generate your own anagrams. To decide which anagrams are at least plausibly interesting, your program will have to decide which strings are legitimate words. Your program should prompt the user for a file containing a word list, and a word for anagrammating (it's vaguely concievable that that is a word...)

Once we get the basic functionality down, we'll add a few other features. For example, we'd like to allow the user to specify that they are only interested in using words of length 4 or greater, or anagrams containing at most 3 words.

Program Outline

1. Read in a text document containing a word list. Here are two (both are also in your repl.it project): words1.txt, words2.txt. The first is very small, just for testing purposes. The second contains about 4000 common words. Even for relatively short strings, we'll need to use some optimizations if we want to generate anagrams using that word list.


2. Build a set words containing each word from the text file. Since we have a lot of words, by using a set rather than a list will save us a lot of time when testing membership (which is basically all we'll be using it for). Hint: don't forget to use the strip() function to remove the newline character from each line in the file so that none of the words end with "\n".


3. Create a function called contains(s, word) which returns two values. The first value should be a boolean indicating whether the string s contains the letters necessary to spell word. If the answer is True, the second value should be what remains of word after the letters in s have been removed. If the answer is False, the second value returned should just be an empty string. For example,
   
   

   
     	contains("zombiepig", "bozo")        # returns False, ""
     	contains("zombiepig", "biz")         # returns True, "omepig"
                   	

4. Create a recursive function called grams(s, words, sofar) that takes in a string s, a set of words words, and a list of words sofar. This function finds all anagrams of s using elements found in words. Each of these anagrams is printed, along with the words in sofar, on its own line.
   
   

   You might be wondering why we're passing around the variable sofar. Indeed, when we want to find the anagrams of a string given by the user, we'll pass in an empty list. However, that list will be critical for making use of recursion. Let's look at an example to see why. Suppose we want to find anagrams of

      
         robopirate 
                   	

   We'll look through our wordlist for words that are contained in this string. The string "cat" doesn't appear in "robopirate", but "air" does. So one thing our function call will do is begin looking through the remainder of "robopirate" with "air" removed, looking for further anagrams. That is, it'll continue to look for strings contained in
   
   

       	robopte
               	    

   Our list includes "bro", which is contained in "robopte", so another recursive call will be made on the remains, namely "opte". Our wordlist contains "poet", leaving us with an empty string. At this point we've used up all the letters in the string, so we have an anagram, namely
   
   

         air bro poet 
                     

   Unfortunately, if we want to print our anagram, we're in trouble, since we haven't kept a record of the previous words we found. (Could we have just printed words as we found them?) That's where sofar comes in. This list will track the words we've found so far in this particular branch of the recursion. That is,
   
   

   
         grams("robopirate", words, [])
                     

   will call (among other things)
   
   

   
     	  grams("robopte", words, ["air"]) 
                   	

   which in turn calls
   
   

   
     	  grams("opte", words, ["air", "bro"]) 
                   	

   which in turn calls
   
   

   
     	  grams("", words, ["air", "bro", "poet"]) 
                   	

   which can now print the complete anagram. (Hint: we know it is a complete anagram because s is an empty string, which might tell you what your base case for the recursion is.)

   With this in mind, we're ready to describe the overall structure of this function. We loop over every word w in our wordlist. For each word w that's found in our string s, we make a recursive call on the remainder of s, and with a new list, equal to the current list with w added on. (Why does it need to be a new list? I.e., why would sofar.append(w) be the wrong thing to do? Then every recursive call would add to the same list, and we'd be saving words that we won't eventually use in case they don't work out.) If we make a call where s is the empty string, we can just print the contents of sofar.

Suggestions and Tips

• When trying to determine whether one string s contains a word w, the string replace function is very useful. In particular,
  
  

  
    	  s.replace(ch,'',1) 
                  	

  creates a new string that is identical to s except the first occurence (parameter 3) of ch (parameter 1) is replaced by the empty string (parameter 2).


• When printing a list of strings, the string join function is pretty handy:
  
  

  
      	" ".join(L) 
                  	

  returns a new string containing every element of the list L, glued together with a space. Of course, you could join the elements with any string, but a space makes the most sense here.

Test output

      or bro rat bat air ape poet poor ripe taboo orbit
                

     or ape orbit
     or orbit ape
     bro air poet
     bro poet air
     air bro poet
     air poet bro
     ape or orbit
     ape orbit or
     poet bro air
     poet air bro
     orbit or ape
     orbit ape or
                

Improvements

Once that's working, add in the following optimization and improvements:

• Things slow down a lot when we have longer word lists. One nice optimization makes use of the following observation: if the user's string s doesn't contain a particular word w, then no remainder of s will contain w either. So instead of iterating through the set of all words at each step of the recursion, we need only iterate through the "plausible" words.
  
  Add a "preprocessing" step: Instead of adding every string found in the word file to the set words, only add those that are contained in the user's input string. Fortunately you already have created a function that can help you out here!


• Let the user specify a minimum length of words allowable in their anagrams.


• Let the user specify a maximum number of words (not a maximum length of words) allowable in their anagrams.


• Have all parameters (the string, the word file, min length, and max words) input via command line arguments. In particular, we'd like to be able to type in the Command Line Window:
  
  

            python3 anagrams.py robopirate words1.txt 3 4
                    

  to annagramate "robopirate" using words from words1.txt, require at least 3 characters per words, and allow at most 4 words per anagram, or
  
  

            python3 anagrams.py robopirate words2.txt 2 10
                    

  to annagramate "robopirate" using words from words2.txt, require at least 2 characters per words, and allow at most 10 words per anagram.
  
  How can your program make use of the arguments you add after the program name? Easy -- if you add import sys at the beginning of your program, you'll get access to the variable sys.argv, which is a list of the arguments passed to Python. The first of these is always the name of the program itself. But if you were to run
  
  

            python3 anagrams.py robopirate words2.txt 2 10
                    

  and that program included the statement print(sys.args), we'd get as output
  
  

            ['anagrams.py', 'robopirate', 'words2.txt', '2', '10']
                    

  Given this (and possibly judicious use of the int function), you should be able to get all the input you need from command-line arguments. This way, your program does not need to use input() statements, meaning you do not need to wait for the user to give you a response to know how to run the program.

Part 2 - Wrap Up

Congratulations! You have finished the bonus lab. As with every lab, your last job prior to submission is to complete a brief write-up by filling out a Google Form, which is also how you submit your Honor Code statement (so please do not forget to do this).

Handin

Finally, all you need to do is submit your solution to the assignment. To do so, please click on the "Submit" button in the top right of your programming environment. This will save all of your programs for myself and the graders to look at. You are welcome and encouraged to submit partial solutions to your assignment -- you can always resubmit by pushing the "Resubmit" button in the top right, which will save the latest version of your programs. We will only grade the latest version that you submitted. By submitting multiple times, you avoid accidentially forgetting to turn in any completed part of your assignment, especially in case you become busy around the lab due date.