Problem Set 8

There is only one part to this problem set.
All problems are due by 11:59 p.m. on Sunday, April 8, 2018.

Preliminaries

In your work on this assignment, make sure to abide by the collaboration policies of the course.

Don’t forget to use docstrings and to take whatever other steps are needed to create readable code.

If you have questions while working on this assignment, please come to office hours, post them on Piazza, or email cs111-staff@cs.bu.edu.

Make sure to submit your work on Apollo, following the procedures found at the end of the assignment.

Problems

Problem 0: Reading and response

5 points; individual-only

This week we are studying objects and the blueprint classes that define their behavior. Objects enable users to define their own types, and they are the building blocks of many large-scale software systems. In addition, we will implement a suprisingly simple text-processing system that can produce some powerful results.

But how would large-scale, natural language processing actually work? This week’s article looks at the successes and limitations of language processing systems today, and suggests that these so-called learning systems will be crucial to building artificial systems that can process text in a natural and meaningful manner. Already, it seems, computers are better Jeopardy players than humans (or most of us, at least!).

The article, by New York Times reporter Steve Lohr, is here.

After reading the article, write a response that addresses both of the following prompts:

1. The article claims that researchers have been “fine-tuning a computer system that is trying to master semantics by learning more like a human.” Based on the article and your own experiences programming computers (in circuit diagrams, assembly language, and Python), how do computers operate and learn differently from the way humans do? Are there any similarities?

2. The NELL system had to have human help in order to avoid the cascade of mistaken conclusions from the statement, “I deleted my Internet cookies.” Do you believe machine-learning systems (like NELL or others) will always need human assistance such as this, or will they be able to overcome such problems in the future? Give a brief explanation for your thoughts.

Put your response in a file named ps8pr0.txt. Don’t forget that the file you submit must be a plain-text file.

Problem 1: String-method puzzles

15 points; individual-only

This problem will give you practice with using the methods that are inside every string object.

Begin by downloading this file: ps8pr1.py.

When you open the file in IDLE, you’ll see that we’ve given you the following strings:

s1 = 'Oh! How now brown cow!'
s2 = 'A maddening method to my MADNESS'

We have also given you the solution to the first puzzle.

Warmup
Run ps8pr1.py in IDLE, so that the strings s1 and s2 will be available to you in the Python Shell.

Next, enter the following method calls and other expressions from the Shell, and take note of the values that are returned:

>>> s1.upper()
>>> s1
>>> s2.lower()
>>> s2
>>> s2.count('d')
>>> s2.lower().count('d')
>>> s1.count('ow')
>>> s2.split()
>>> s2.split('m')
>>> s2.lower().split('m')
>>> s1.replace('o', 'e')
>>> s1.lower().replace('o', 'e')
>>> s2.replace('d', 'x')
>>> s2.replace('dd', 'x')
>>> s1
>>> s2

Make sure that the result of each method call makes sense, and perform whatever additional calls are needed to ensure that you understand what each of these methods does. You may also want to consult the online documentation for Python’s string class.

The Puzzles
Your task is to add answers to ps8pr1.py for the remaining puzzles, following the format that we’ve given you for puzzle 0.

Here are the puzzles:

0. Use s1 and one or more string methods to count all occurrences of the letter O (both upper-case and lower-case) in s1, and assign the count to the variable answer0. The expected answer is 5. We’ve given you the code for this puzzle.

1. Use s2 and one or more string methods to count all occurrences of the word 'mad' in s2–ignoring the case of the letters–and assign the count to the variable answer1. The expected answer is 2.

   Your answer for this and the remaining puzzles should follow the format that we’ve given you for puzzle 0. In other words, it should look like this:

   # Puzzle 1
   answer1 = 
   print('answer1 =', answer1)
   

   where you put the appropriate expression to the right of the assignment operator (=). Please leave a blank line between puzzles to make things more readable.

2. Use s1 and one or more string methods to create the list

   ['Oh! Ho', ' no', ' bro', 'n co', '!']
   

   Assign the result to the variable answer2, and print answer2.

3. Use s2 and one or more string methods to create the list

   ['A ', 'DENING METHOD TO MY ', 'NESS']
   

   Assign the result to the variable answer3, and print answer3.

4. Use s1 and one or more string methods to create the string

   'Oh! Hee nee breen cee!'
   

   Assign the result to the variable answer4, and print answer4.

5. Use s2 and one or more string methods to create the string

   'a saddening sethod to sy sadness'
   

   Assign the result to the variable answer5, and print answer5.

Problem 2: A Date class

50 points; individual-only

Some people have an extraordinary talent to compute (in their heads) the day of the week that any past date fell on. For example, if you tell them that you were born on October 13, 1995, they’ll be able to tell you that you were born on a Friday!

In this problem, you will create a Date class, from which you will be able to create Date objects that represent a day, month, and year. You will add functionality to this class that will enable Date objects to find the day of the week to which they correspond.

Getting started
Begin by downloading the file ps8pr2.py and opening it in IDLE. We have given you the following methods to start:

• The __repr__(self) method, which returns a string representation of a Date object. This method will be called when an object of type Date is printed. It can also be tested by simply evaluating an object from the Shell. This method formats the month, day, and year that represent a Date object into a string of the form 'mm/dd/yyyy' and returns it.

• The is_leap_year(self) method, which returns True if the called object is in a leap year, and False otherwise. In other words, when we create a Date object and call its is_leap_year method, the method will return whether that specific Date object falls in a leap year.

• The copy(self) method, which returns a newly-constructed object of type Date with the same month, day, and year that the called object has. This allows us to create deep copies of Date objects.

Your tasks

Below you will add several new methods to the Date class. Be sure to thoroughly test your methods for all cases to ensure that they are correct. In addition, make sure to include a docstring for each method that you write.

1. Implement the Date constructor – i.e., the __init__ method. We have given you the header for this method, and you should fill in the body so that it initializes the attributes of the Date object (month, day, and year) to the values that are passed in as parameters.

   Don’t forget to use the keyword self when specifying an attribute. For example, when initializing the month attribute, you should write a statement that looks like this:

   self.month = ...
   

   Here is some code you can use to test your constructor:

   >>> d1 = Date(4, 10, 2016)
   >>> d1.month
   4
   >>> d1.day
   10
   >>> d1.year
   2016
   

   Note that we don’t actually use the name __init__ to call the method. Rather, we call it by using the name of the class (Date).

2. Once you have implemented the constructor, read over the rest of the starter code that we’ve given you. Make sure that you understand how the various methods work.

   Try the following interactions in the Python Shell to experiment with the __repr__, and is_leap_year methods:

   >>> d1 = Date(4, 10, 2016)
   
   # An example of using the __repr__ method. Note that no quotes
   # are displayed, even though the function returns a string.
   >>> d1
   04/10/2016
   
   # Check if d1 is in a leap year -- it is!
   >>> d1.is_leap_year()
   True
   
   # Create another object named d2
   >>> d2 = Date(1, 1, 2017)
   
   # Check if d2 is in a leap year.
   >>> d2.is_leap_year()
   False
   

   Next, try the following examples in the Python Shell to illustrate why we will need to override the __eq__ method to change the meaning of the == operator:

   >>> d1 = Date(1, 1, 2016)
   >>> d2 = d1
   >>> d3 = d1.copy()
   
   # Determine the memory addresses to which the variables refer.
   >>> id(d1)
   430542             # Your memory address may differ.
   >>> id(d2)
   430542             # d2 is a reference to the same Date that d1 references.
   >>> id(d3)
   413488             # d3 is a reference to a different Date in memory.
   
   # The == operator tests whether memory addresses are equal.
   >>> d1 == d2
   True               # Shallow copy -- d1 and d2 have the same memory address.
   >>> d1 == d3
   False              # Deep copy -- d1 and d3 have different memory addresses.
   

3. Write a method tomorrow(self) that changes the called object so that it represents one calendar day after the date that it originally represented.

   Notes:

   • This method should not return anything. Instead, it should change the value of one or more variables inside the called object.

   • Since we are advancing the Date object by one day, self.day will change. Depending on what day it is, self.month and self.year may also change. * You may find it helpful to use the following list by declaring it on the first line of the method:

     days_in_month = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
     

     You can then use this list to quickly determine the number of days in a month. For example, days_in_month[1] is 31 to represent that January (month 1) has 31 days. You can use self.month to index this list to find the number of days in the month that is represented by a Date object.

     If you use this approach, be sure to take into account that the days_in_month list is not accurate for Date objects that represent February during leap years. However, you can use an if statement to account for this case when necessary. We showed you this adjustment in lecture.

   Examples:

   >>> d = Date(12, 31, 2016)
   >>> d
   12/31/2016
   >>> d.tomorrow()
   >>> d
   01/01/2017
   >>> d = Date(2, 28, 2016)
   >>> d.tomorrow()
   >>> d
   02/29/2016
   >>> d.tomorrow()
   >>> d
   03/01/2016
   >>> d.tomorrow()
   >>> d
   03/02/2016
   

4. Write a method add_n_days(self, n) that changes the calling object so that it represents n calendar days after the date it originally represented. Additionally, the method should print all of the dates from the starting date to the finishing date, inclusive of both endpoints.

   Notes:

   • This method should not return anything. Instead, it should change the value of one or more variables inside the called object.

   • Don’t copy code from the tomorrow method. Instead, you should call the tomorrow method in a loop to accomplish the necessary changes.

   • Because the tomorrow method doesn’t explicitly return a value, it will implicitly return the special value None. As a result, you need to be careful how you call it. In particular, you should not call it as part of an assignment or as part of a print statement. For example, this would not work:

     # don't do this!
     print(self.tomorrow())
     

     because you will end up repeatedly printing None. Rather, you should simply call the method on its own line, and ignore the value of None that is returned:

     self.tomorrow()
     

   • To print the current state of the Date object, you can simply do the following:

     print(self)
     

   since doing so will call the __repr__ method to produce a string representation of self that you can print.

   • This method should work for any nonnegative integer n.

   • If n is 0, only the starting date should be printed.

   Examples:

   >>> d = Date(11, 14, 2016)
   >>> d.add_n_days(3)
   11/14/2016
   11/15/2016
   11/16/2016
   11/17/2016
   >>> d
   11/17/2016
   >>> d = Date(11, 14, 2016)
   >>> d.add_n_days(0)
   11/14/2016
   >>> d
   11/14/2016
   

5. Write a method __eq__(self, other) that returns True if the called object (self) and the argument (other) represent the same calendar date (i.e., if the have the same values for their day, month, and year attributes). Otherwise, this method should return False.

   Recall from lecture that the name __eq__ is a special method name that allows us to override the == operator–replacing the default version of the operator with our own version. In other words, when the == operator is used with Date objects, our new __eq__ method will be invoked!

   This method will allow us to use the == operator to see if two Date objects actually represent the same date by testing whether their days, months, and years are the same, instead of testing whether their memory addresses are the same.

   After implementing your __eq__ method, try re-executing the following sequence of statements from Task 0:

   >>> d1 = Date(1, 1, 2016)
   >>> d2 = d1
   >>> d3 = d1.copy()
   
   # Determine the memory addresses to which the variables refer.
   >>> id(d1)
   430542             # Your memory address may differ.
   >>> id(d2)
   430542             # d2 is a reference to the same Date that d1 references.
   >>> id(d3)
   413488             # d3 is a reference to a different Date in memory.
   
   # The new == operator tests whether the internal date is the same.
   >>> d1 == d2
   True               # Both refer to the same object, so their internal
                      # data is also the same.
   >>> d1 == d3
   True               # These variables refer to different objects, but
                      # their internal data is the same!
   

   Notice that we now get True when we evaluate d1 == d3. That’s because the new __eq__ method compares the internals of the objects to which d1 and d3 refer, rather than comparing the memory addresses of the objects.

6. Write a method is_before(self, other) that returns True if the called object represents a calendar date that occurs before the calendar date that is represented by other. If self and other represent the same day, or if self occurs after other, the method should return False.

   Notes:

   • This method is similar to the __eq__ method that you have written in that you will need to compare the years, months, and days to determine whether the calling object comes before other.

   Examples:

   >>> ny = Date(1, 1, 2017)
   >>> d1 = Date(11, 14, 2016)
   >>> d2 = Date(3, 24, 2016)
   >>> tg = Date(11, 24, 2016)
   >>> ny.is_before(d1)
   False
   >>> d1.is_before(ny)
   True
   >>> d1.is_before(d2)
   False
   >>> d2.is_before(d1)
   True
   >>> d1.is_before(tg)
   True
   >>> tg.is_before(d1)
   False
   >>> tg.is_before(tg)
   False
   

7. Write a method is_after(self, other) that returns True if the calling object represents a calendar date that occurs after the calendar date that is represented by other. If self and other represent the same day, or if self occurs before other, the method should return False.

   Notes:

   • There are two ways of writing this method. You can either emulate your code for is_before OR you can think about how you could call __eq__ (==) and is_before to make writing this method very simple.

   Examples:

   >>> ny = Date(1, 1, 2017)
   >>> d1 = Date(11, 14, 2016)
   >>> d2 = Date(3, 24, 2016)
   >>> tg = Date(11, 24, 2016)
   >>> ny.is_after(d1)
   True
   >>> d1.is_after(ny)
   False
   >>> d1.is_after(d2)
   True
   >>> d2.is_after(d1)
   False
   >>> d1.is_after(tg)
   False
   >>> tg.is_after(d1)
   True
   >>> tg.is_after(tg)
   False
   

8. Write a method diff(self, other) that returns an integer that represents the number of days between self and other.

   Notes:

   • This method should not change self nor should it change other during its execution.

   • The sign of the return value is important! In particular:

     • If self and other represent the same calendar date, this method should return 0.
     • If self is before other, this method should return a negative integer equal to the number of days between the two dates.
     • If self is after other, this method should return a positive integer equal to the number of days between the two dates.

   Suggested Approach:

   • Since this method should not change the original objects, you should first use the copy method to create true copies of self and other.
   • Then, use is_before or is_after to figure out which date comes first.
   • You can use the tomorrow method that you have already written in a similar way to how you used it in the add_n_days method to count up from one date to another. However, unlike in that method, in diff it is not clear how many times you need to call tomorrow to get an appropriate count from one date to the other. What kind of loop is well-suited for this kind of problem?
   • Once you know how many days separate the two values, you can again use is_before or is_after to figure out whether the returned result should be positive or negative.
   • You should not try to subtract years, months, and days between the two dates. This technique is too prone to mistakes.
   • You should also not try to use add_n_days to implement your diff method. Checking all of the possible difference amounts will be too slow!

   Examples:

   >>> d1 = Date(11, 14, 2016)
   >>> d2 = Date(12, 21, 2016)
   >>> d2.diff(d1)
   37
   >>> d1.diff(d2)
   -37
   >>> d1           # Make sure the original objects did not change.
   11/14/2016
   >>> d2
   12/21/2016
   
   # Here are two that pass over a leap day.
   >>> d3 = Date(12, 1, 2015)
   >>> d4 = Date(3, 15, 2016)
   >>> d4.diff(d3)
   105
   

9. Write a method day_of_week(self) that returns a string that indicates the day of the week of the Date object that calls it. In other words, the method should return one of the following strings: 'Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday', 'Sunday'.

   Suggested Approach:

   • Try using the diff method from a known date. For example, how could it help to know the number of days between the called object and a Date object representing Monday, April 2, 2018? How might the modulus (%) operator help?
   • Calling diff will give you a negative number if the Date you are operating on comes before the known date used by day_of_week. You should leave the result as a negative number in such cases; you should not take its absolute value.
   • It will be useful to copy and paste the following list to the first line of your method:

     day_of_week_names = ['Monday', 'Tuesday', 'Wednesday', 'Thursday',
                          'Friday', 'Saturday', 'Sunday']
     

   Examples:

   >>> d = Date(4, 2, 2018)
   >>> d.day_of_week()
   'Monday'
   >>> Date(4, 3, 2018).day_of_week()
   'Tuesday'
   >>> Date(4, 4, 2018).day_of_week()
   'Wednesday'
   >>> Date(1, 1, 2100).day_of_week()
   'Friday'
   >>> Date(7, 4, 1776).day_of_week()
   'Thursday'
   

Problem 3: Markov text generation

30 points; pair-optional

This is the only problem of the assignment that you may complete with a partner. See the rules for working with a partner on pair-optional problems for details about how this type of collaboration must be structured.

In this problem, you will write a program that is capable of generating meaningful text all by itself! You will accomplish this by implementing what is known as a Markov text-generation algorithm.

Background

English is a language with a lot of structure. Words have a tendency (indeed, an obligation) to appear only in certain sequences. Grammatical rules specify legal combinations of different parts of speech. For example, the phrase “The cat climbs the stairs” obeys a legal word sequence. “Stairs the the climbs cat” does not. Additionally, semantics (the meaning of a word or sentence) further limits possible word combinations. “The stairs climbs the cat” is a perfectly legal sentence, but it doesn’t make much sense and you are very unlikely to encounter this word ordering in practice.

Even without knowing the formal rules of English or the meaning of English words, we can get an idea of which word combinations are legal simply by looking at well-formed English text and noting the combinations of words that tend to occur in practice. Then, based on our observations, we can generate new sentences by randomly selecting words according to commonly occurring sequences of these words. For example, consider the following text:

I love roses and carnations. I hope I get roses for my birthday.

If we start by selecting the word “I”, we notice that “I” may be followed by “love,” “hope,” and “get” with equal probability in this text. We randomly select one of these words to add to our sentence: “I get.” We can repeat this process with the word “get,” necessarily selecting the word “roses” as the next word. Continuing this process could yield the phrase:

I get roses and carnations.

Note that this is a valid English sentence, but not one that we have seen before. Other novel sentences we might have generated include “I love roses for my birthday.” and “I get roses for my birthday.”

More formally, the process used to generate these sentences is called a first-order Markov process. A first-order Markov process is a process in which the state at time t + 1 (i.e., the next word) depends only on the state at time t (i.e., the previous word). In a second-order Markov process, the next word would depend on the two previous words, and so on. Our example above was a first-order process because the choice of the next word depended only on the current word.

Your tasks

Implementing a first-order Markov text generator will involve writing two functions: one to process a file and create a dictionary of legal word transitions, and another to actually generate the new text.

We will consider words to be different even if they only differ by capitalization or punctuation. For example, 'spam', 'Spam', and 'spam!' will all be considered distinct words.

To start, open a new file in IDLE and save it as ps8pr3.py. Put all of the code that you write for this problem in that file. Don’t forget to include appropriate comments at the top of the file, and a docstring for each function.

1. Write a function create_dictionary(filename) that takes a string representing the name of a text file, and that returns a dictionary of key-value pairs in which:

   • each key is a word encountered in the text file

   • the corresponding value is a list of words that follow the key word in the text file.

   For example, the dictionary produced for the text “I love roses and carnations. I hope I get roses for my birthday.” would include the following key-value pairs, among others:

   'I': ['love', 'hope', 'get']
   'love': ['roses']
   'roses': ['and', 'for']
   'my': ['birthday.']
   # as well as others!
   

   Guidelines:

   • You should not try to remove the punctuation from the words of the text file.

   • The keys of the dictionary should include every word in the file except the sentence-ending words. A sentence-ending word is defined to be any word whose last character is a period ('.'), a question mark ('?'), or an exclamation point ('!'). A sentence-ending word should be included in the lists associated with the words that it follows (i.e., in the value parts of the appropriate key-value pairs), but it not appear as its own key.

   • If a word w1 is followed by another word w2 multiple times in the text file, then w2 should appear multiple times in the list of words associated with w1. This will allow you to capture the frequency with which word combinations appear.

   • In addition to the words in the file, the dictionary should include the string $ as a special key referred to as the sentence-start symbol. This symbol will be used when choosing the first word in a sentence. In the dictionary, the list of words associated with the key '$' should include:

     • the first word in the file
     • every word in the file that follows a sentence-ending word.

     Doing this will ensure that the list of words associated with '$' includes all of the words that start a sentence. For example, the dictionary for the text “I scream. You scream. We all scream for ice cream.” would include the following entry for the sentence-start symbol:

     '$': ['I', 'You', 'We']
     

   • You may find it helpful to consult the word_frequencies function from lecture. We will also discuss some additional strategies for create_dictionary in lecture.

   Examples:

   To test your code, download the sample.txt file into the same directory that contains ps8pr3.py. This sample text file contains the following contents:

   A B A. A B C. B A C. C C C.
   

   Once this file is in place, run your ps8pr3.py in IDLE and test your function from the Shell:

   >>> word_dict = create_dictionary('sample.txt')
   >>> word_dict
   {'A': ['B', 'B', 'C.'], 'C': ['C', 'C.'],
    'B': ['A.', 'C.', 'A'], '$': ['A', 'A', 'B', 'C']}
   

   The order of the keys–or of the elements within a given key’s list of values–may not be the same as what you see above, but the elements of the lists should appear in the quantities shown above for each of the four keys 'A', 'B', 'C', and '$'.

   Here are some additional files you can use for testing:

   • edited_mission.txt - an edited version of BU’s mission statement, and the dictionary that we derived from it.

   • brave.txt - lyrics from the song Brave by Sara Bareilles, and its dictionary.

   Here again, the ordering that you obtain for the keys and list elements in the dictionaries may be different. In addition, we have edited the formatting of the dictionaries to make them easier to read.

2. Write a function generate_text(word_dict, num_words) that takes as parameters a dictionary of word transitions (generated by the create_dictionary function) named word_dict and a positive integer named num_words. The function should use word_dict to generate and print a string of num_words words.

   Guidelines:

   • The first word should be chosen randomly from the words associated with the sentence-start symbol, '$'. The second word should be chosen randomly from the list of words associated with the first word, etc. When the current word ends in a period ('.'), question mark ('?'), or exclamation point ('!'), the function should detect this and start a new sentence by again choosing a random word from among those associated with '$'.

   • Do not include '$' in the output text. It should only be used as an internal marker for your function.

   • You can use the random.choice function to choose from a list of possible words. Don’t forget to include import random at the top of your file. Then, if wordlist is the list of possible words at a given point in the generated text, you can do something like the following:

     next_word = random.choice(wordlist)
     

   • Here again, you shouldn’t try to remove or change the punctuation associated with the words, and you don’t need to worry if the generated text doesn’t end with appropriate punctuation. The generated text won’t be perfect, but most of the time it will at least be meaningful!

   • If your function encounters a word that doesn’t have any words associated with it in the dictionary, the function should start a new sentence. This situation can occur if the last word in the file used to create the dictionary was unique and did not end with punctuation.

   • Here again, we will discuss some strategies for generate_words in lecture.

   Example:

   Here are two examples using the same text file as above. Your output may differ because of the randomness involved in the generation.

   >>> word_dict = create_dictionary('sample.txt')
   >>> generate_text(word_dict, 20)
   B C. C C C. C C C C C C C C C C C. C C C. A
   
   >>> generate_text(word_dict, 20)
   A B A. C C C. B A B C. A C. B A. C C C C C C.
   

   Try some other examples using longer documents containing English words, such as the works of William Shakespeare. In particular, we are providing a text file containing the first act of Romeo and Juliet, along with the files that we provided above in the examples for create_dictionary.

Submitting Your Work

You should use Apollo to submit the following files:

• your ps8pr0.txt file containing your response to the reading for Problem 0
• your ps8pr1.py file containing your solution for Problem 1
• your modified ps8pr2.py file containing your solution for Problem 2
• your ps8pr3.py file containing your solution for Problem 3; if you worked with a partner, make sure that you each submit a copy of your joint work, and that you include comments at the top of the file specifying the name and email of your partner

Here are the steps:

1. Login to Apollo, using the link in the left-hand navigation bar. You will need to use your Kerberos user name and password.
2. Check to see that your BU username is at the top of the Apollo page. If it isn’t, click the Log out button and login again.
3. Find the appropriate problem set section on the main page and click Upload files.
4. For each file that you want to submit, find the matching upload section for the file. Make sure that you use the right section for each file. You may upload any number of files at a time.
5. Click the Upload button at the bottom of the page.
6. Review the upload results. If Apollo reports any issues, return to the upload page by clicking the link at the top of the results page, and try the upload again, per Apollo’s advice.
7. Once all of your files have been successfully uploaded, return to the upload page by clicking the link at the top of the results page. The upload page will show you when you uploaded each file, and it will give you a way to view or download the uploaded file. Click on the link for each file so that you can ensure that you submitted the correct file.