Problem Set 8

due by 10:00 p.m. on Friday, September 29

suggested self-deadline of Wednesday September 27

Preliminaries

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

If you have questions while working on this assignment, please come to TA help hours, office hours, or post them on Piazza.

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

Problem 1: Thinking in loops

30 points; pair-optional or group-of-three-optional

Put your answers for this problem in Jupyter Notebook named ps8pr1.ipynb.

1. Consider the following Python function, which uses an index-based for loop:

   def mystery(values):
        count = 0
        for i in range(len(values)):
            if values[i] > values[i-1]:
                count += 1
        return count
   

   Trace the execution of the following call to this function:

   mystery([8, 5, 3, 7, 1, 6])
   

   In particular, you should:

   1. Construct a table that illustrates the execution of the loop during this function call. Use the template below as a starting point, and show how the expression at the top of each column changes during the execution of the loop.

          |  i  | values[i] | values[i-1] | count |
          |-----|-----------|-------------|-------|
          |  -  |     -     |      -      |   0   |
          |  0  |           |             |       |
          

      which will render as:

      i	values[i]	values[i-1]	count
      -	-	-	0
      0

      The table begins with a row for the initial value of the variable count. The remaining rows should show what happens for each value of the loop variable i.

   2. State the return value of this function call.

2. Consider the following Python program, which uses a nested loop:

   for x in [2, 4, 6]:
       for y in range(1, x):
           print(x + y)
   print(x, y)
   

   Trace the execution of this program by completing the table below. Show how the variables change over time and the values that are printed.

   | x  | range(1, x) | y | value printed  |
   |----|-------------|---|----------------| 
   | 2  | [1]         | 1 | 3              |
    ...
   

3. Consider the following Python program, which uses a while loop:

   a = 12
   b = 4
   print(a, b)
   
   while a > 2:
       a -= b
       b -= 1
       print(a, b)
   

   Trace the execution of this program by completing the table below. Show how the variables change over time and the values that are printed.

   | a  | b | value printed |
   |----|---|---------------| 
   | 12 | 4 | 12 4          |
    ...
   

   Please ensure that Run All before submitting your .ipynb file.

Problem 2: Estimating pi

30 points; pair-optional or group-of-three-optional

In this problem you will employ loops to estimate the value of the mathematical constant π (3.14159...).

Begin by downloading the file ps8pr2.py and opening it in VS Code. We’ve given you some starter code that you will need for this problem.

Background
The procedure that you will employ to estimate π an example of a more general problem-solving approach known as Monte Carlo simulation.

Imagine that you have a square with sides of length 2 that spans the region of the Cartesian plane in which -1 ≤ x ≤ 1 and -1 ≤ y ≤ 1. If you inscribe a circle within that square, the circle will have a radius of 1, and thus its area will be π.

It you were to throw darts at random locations inside the square, some of them would hit the circle, and some would not. The ratio

area of the circle / area of the square

can be estimated by the ratio

# of darts that hit the circle / total # of darts thrown

As the number of darts increases, the second ratio above gets closer and closer to the first ratio. As a result, we can set the two ratios equal to each other and solve for the area:

area of circle = (# of darts that hit the circle * area of square) / total # of darts thrown

We can then use this expression to approximate the area of the circle, and thus the value of π.

Obviously, we won’t actually be throwing darts! Instead, we’ll use Python’s random module to generate random numbers that simulate the dart-throwing process. This use of random numbers (or, to be more precise, pseudorandom numbers) is at the heart of Monte Carlo simulation.

The functions
Your solution to this problem should include at least the functions described below. You are welcome to include additional helper functions, but doing so is not required.

0. We’ve given you a helper function throw_dart() (with no inputs) that simulates the act of throwing one dart in the square region described above. If the dart hits the circle of radius 1 inscribed in the square, the function returns True. If the dart falls outside the circle, the function returns False.

   Read over this function to see what it does. In particular, notice the following:

   • throw_dart() uses a function called random.uniform() from Python’s random module. It particular, it makes the following function call:

     random.uniform(-1.0, 1.0)
     

     This call chooses a float at random from the range of floating-point numbers between -1.0 and 1.0. Note that throw_dart
     makes this call twice – once to obtain the x coordinate of the dart throw, and once to obtain its y coordinate.

   • A throw is considered to have hit the circle if the sum of x2 and y2 is less than or equal to 1.0. If it is, the function returns True, otherwise it returns False.

1. Write a function for_pi(n) that takes a positive integer n and returns an estimate of π that is based on n randomly thrown darts.

   The function should use a loop and the throw_dart function to throw the n darts. After each dart is thrown, the function should print the following:

   • the number of darts thrown so far
   • the number of the darts that have hit the circle
   • the current estimate of π

   Then, after all n throws have been made, the function should return the final estimate of π.

   Because the throw_dart function is using random numbers, the results obtained for a given input will vary. However, here’s one example of what the output should look like:

   >>> for_pi(10)
   1 hits out of 1 throws so that pi is 4.0
   2 hits out of 2 throws so that pi is 4.0
   3 hits out of 3 throws so that pi is 4.0
   4 hits out of 4 throws so that pi is 4.0
   4 hits out of 5 throws so that pi is 3.2
   5 hits out of 6 throws so that pi is 3.33333333333
   6 hits out of 7 throws so that pi is 3.42857142857
   6 hits out of 8 throws so that pi is 3.0
   7 hits out of 9 throws so that pi is 3.11111111111
   8 hits out of 10 throws so that pi is 3.2
   3.2
   

   Notes/hints:

   • Your for_pi function should call your throw_dart function when it needs to throw a dart, and it should use the return value of that function call to determine whether the throw hit the circle. Your for_pi function should not make its own calls to random.uniform.

   • For a given input n, the function should print n lines of output–one for each dart throw. The final number shown above is the return value, which is displayed when you call the function from the Shell. The function should not actually print this value; it should just return it.

   • You will need accumulator variables for the number of darts thrown and the number of hits. Don’t forget to initialize those variables before the start of the loop.

   • Here again, you should include a docstring and any other comments that might be necessary to explain your code. More generally, you should aim to make your code easy to read. For example, you should choose descriptive names for your variables. In addition, we encourage you to leave a blank line between logical parts of your function.

2. Write a function while_pi(error) that takes a positive floating-point input error and returns the number of dart throws needed to produce an estimate of π that is less than error away from the “actual” value of π (i.e., the value given by math.pi in Python’s math module).

   The function should use a loop and the throw_dart function to throw darts until the absolute difference between the function’s current estimate of π and math.pi is less than error.

   After each dart is thrown, the function should print the same three values that were printed by your for_pi function.

   Once the estimate is accurate enough, the function should return the number of darts thrown in order to achieve that final estimate.

   The results obtained for a given input will vary, but they should look something like this:

   >>> while_pi(0.1)
   1 hits out of 1 throws so that pi is 4.0
   2 hits out of 2 throws so that pi is 4.0
   3 hits out of 3 throws so that pi is 4.0
   4 hits out of 4 throws so that pi is 4.0
   5 hits out of 5 throws so that pi is 4.0
   5 hits out of 6 throws so that pi is 3.33333333333
   6 hits out of 7 throws so that pi is 3.42857142857
   7 hits out of 8 throws so that pi is 3.5
   7 hits out of 9 throws so that pi is 3.11111111111
   9
   

   Notes/hints:

   • You must not call your for_pi function inside while_pi. Rather, you call throw_dart directly inside of while_pi.

   • Here again, your function should call throw_dart when it needs to throw a dart. It should not make its own calls to random.uniform.

   • We have imported Python’s math module for you, so you can use the expression math.pi when comparing your current estimate to the “actual value” of π.

   • You are welcome to use the built-in abs function, which returns the absolute value of its input.

   • You may find it easier to check if your current estimate is close enough inside your while loop, rather than trying to check this as part of your loop condition. If you take this approach, you can just use the following loop header:

      while True:
     

     The resulting loop will keep looping indefinitely, but you can break out of the loop once your estimate is close enough by using an if statement inside the loop, along with either a break statement or a return statement.

   • Here again, your function should not actually print its return value; it should simply return it.

   • Follow the guidelines given for the previous function about making your code readable.

Problem 3: Processing sequences with loops

40 points; pair-optional or group-of-three-optional

In VS Code, use the File -> New File menu option to open a new editor window for your code, and save it using the name ps8pr3.py. Make sure to specify the .py extension.

1. Write a function double(s) that takes an arbitrary string s as input, and that uses a loop to construct and return the string formed by doubling each character in the string. Here are some examples:

   >>> double('hello')
   'hheelllloo'
   >>> double('python')
   'ppyytthhoonn'
   >>> print(double('python'))
   ppyytthhoonn
   >>> double('')
   ''
   

   You solved this problem using recursion in an earlier problem set, but for this problem set you must use a loop.

   Here is a template that you can use to get started:

   def double(s):
       """ your docstring goes here """
       result = ''
   
       for c in s:
           ...
   

   Hint: This function performs a cumulative computation that gradually builds up a string. We discussed a similar function (a loop-based remove_vowels).

2. Write a function weave(s1, s2) that takes as inputs two strings s1 and s2 and uses a loop to construct and return a new string that is formed by “weaving” together the characters in the strings s1 and s2 to create a single string. In other words, the new string should alternate characters from the two strings: the first character from s1, followed by the first character from s2, followed by the second character from s1, followed by the second character from s2, etc. If one of the strings is longer than the other, its “extra” characters – the ones with no counterparts in the shorter string – should appear immediately after the “woven” characters (if any) in the new string.

   Here are some examples:

   >>> weave('aaaaaa', 'bbbbbb')
   'abababababab'
   >>> weave('abcde', 'VWXYZ')
   'aVbWcXdYeZ'
   >>> print(weave('abcde', 'VWXYZ'))
   aVbWcXdYeZ
   >>> weave('aaaaaa', 'bb')    # four extra 'a' characters at the end
   'ababaaaa'         
   >>> weave('aaaa', 'bbbbbb')  # two extra 'b' characters at the end
   'ababababbb'       
   >>> weave('aaaa', '')        # all of the 'a' characters are extra!
   'aaaa'       
   >>> weave('', 'bbbb')        # all of the 'b' characters are extra!
   'bbbb'       
   >>> weave('', '')        
   ''
   

   You solved this problem using recursion in an earlier problem set, but for this problem set you must use a loop.

   Hints:

   • You will need to use an index-based loop so that you can access the corresponding characters from both s1 and s2 at the same time. Here is a template that you can use to get started:

     def weave(s1, s2):
         """ your docstring goes here """
         result = ''
         len_shorter = min(len(s1), len(s2))
     
         for i in range(len_shorter):
             ...
     

     Note that we determine the length of the shorter string before beginning the loop, because the loop should only consider the index values that are present in both loops.

   • After the loop, you will need to handle any “extra” characters from the longer string (for cases in which the strings don’t have the same length). One way to do that is to use conditional execution (e.g., an if-else statement), although other approaches may also be possible.

3. Write a function square_evens(values) that takes a list of integers called values, and that modifies the list so that all of its even elements are replaced with their squares, but all of its odd elements are left unchanged.

   This function should not return a value. Rather, it should should use a loop to modify the internals of the original list as needed. For example, to modify element i of the list values, you should perform an assignment that looks like this:

   values[i] = expression
   

   where expression is replaced with an appropriate expression for the new value of values[i]. For reasons that we will discuss in lecture this week, any changes that the function makes to the internals of the list will still be there after the function returns.

   For example:

   >>> vals1 = [1, 2, 3, 4, 5, 6]
   >>> square_evens(vals1)
   >>> vals1
   [1, 4, 3, 16, 5, 36]
   >>> vals2 = [7, 3, 10, 8]
   >>> square_evens(vals2)
   >>> vals2
   [7, 3, 100, 64]
   

4. Write a function index(elem, seq) that takes as inputs an element elem and a sequence seq, and that uses a loop to find and return the index of the first occurrence of elem in seq. The sequence seq can be either a list or a string. If seq is a string, elem will be a single-character string; if seq is a list, elem can be any value. Don’t forget that the index of the first element in a sequence is 0.

   Important notes:

   • If elem is not an element of seq, the function should return -1.

   • You may not use the in operator in this function to test for the presence of elem in seq. However, you are welcome to use in as part of the header of a for loop. In addition, the only built-in functions that you may use are len and range.

   Here are some examples:

   >>> index(5, [4, 10, 8, 5, 3, 5])
   3
   >>> index('hi', ['well', 'hi', 'there'])
   1
   >>> index('b', 'banana')
   0
   >>> index('a', 'banana')
   1
   >>> print(index('n', 'banana'))
   2
   >>> index('i', 'team')
   -1
   >>> index(8, [4, 10, 5, 3])
   -1
   

   You solved this problem using recursion in Problem Set 5, but for this problem set you must use a loop.

   Hint: One way to solve this problem is to have two return statements: one inside the loop, and one after the loop has completed.

Submitting Your Work

You should use Gradesope to submit the following files:

• your ps8pr1.ipynb file containing your solutions for Problem 1 - Run All cells first.
• your ps8pr2.py file containing your solutions for Problem 2
• your ps8pr3.py file containing your solutions for Problem 3