This worksheet focuses on the Jupyter notebook interface, context managers, and the start of our unit on recursion.
There is a sequence of integers $T_n$ defined by the conditions
$$\begin{split} T_0 &= 0\\ T_1 &= 1\\ T_2 &= 2\\ T_{n} &= T_{n-1} + T_{n-2} + T_{n-3} \text{ if } n \geq 3\end{split}$$This sequence begins $0, 1, 2, 3, 6, 11, 20, 37, 68, 125, 230, 423, 778, 1431, 2632, \ldots$.
Write a recursive function that calculates $T_n$.
Write an iterative function that calculates $T_n$.
Add code to the recursive function that will allow you to count how many times the function is called in any single computation. (You probably want to have a global dictionary in which every function call changes the value associated with a certain key.)
Make a table of how many calls are involved for $n=1,2,3,\ldots,15$.
def T(n):
"""Returns n-th entry in sequence T"""
if n == 0 or n == 1 or n == 2:
return n
elif n > 0:
return T(n-1) + T(n-2) + T(n-3)
else:
raise ValueError("`n` must be nonnegative")
def T_iterative(n):
"""Iterative version of T_n"""
if n == 0:
return 0
a,b,c = 0,1,2
for line in range(n-2):
a,b,c = b,c,a+b+c
return c
Here's a version of T that records each call.
call_counts = {}
def T_count(n):
"""Returns n-th entry in sequence T while logging each call"""
# log
if "T_count" not in call_counts:
call_counts["T_count"] = 0
call_counts["T_count"]+=1
# calculate
if n == 0 or n == 1 or n == 2:
return n
else:
return T_count(n-1) + T_count(n-2) + T_count(n-3)
print("call counts, using logging")
for n in range(16):
call_counts.clear()
assert T(n)==T_count(n)
print(n,call_counts["T_count"])
Alteranatively, here's a function that computes the call count using the observation that there is one call for $n=0,1,2$ and for $n>2$ we have T_call_count(n) = T_call_count(n-1) + T_call_count(n-2) + T_call_count(n-3) + 1.
def T_call_count(n):
"""Returns number of times T calls itself when calculating T_n"""
if n == 0 or n == 1 or n == 2:
return 1
else:
return T_call_count(n-1) + T_call_count(n-2) + T_call_count(n-3) + 1
print("call counts, using the recursive formula they satisfy")
for n in range(16):
print(n,T_call_count(n))
Sometimes, a program will read or write a data file which might also be accessed by another program at the same time. In such cases, it may be necessary for one program to have exclusive access to the file at certain times (e.g. to make changes without fear another program will read partially updated or corrupted data).
There are a lot of mechanisms for handling this situation. One of the oldest approaches is to use a second file, a lockfile, that will be created when a program needs exclusive access to the data file and removed when the period of exclusive access ends.
To make this precise, imagine there might be a file called keyring.dat that is used by a password manager system. It might be used by a Python program that lets you view or edit passwords stored there, and by a web application that integrates the password database with a browser. Each of these programs may need exclusive access to keyring.dat at various times. A lockfile system for this purpose might look like this:
keyring.dat, it checks to see whether a different file named locked-keyring.dat already existslocked-keyring.dat and considers its exclusive access to keyring.dat to be obtainedkeyring.dat is finished using it, it removes locked-keyring.dat, allowing other programs to claim exclusive use of it.While there can be problems with lock files in general, this structure is a good candidate for implementation using a context manager.
Make a context manager class OpenWithLock whose constructor accepts a filename fn (such as keyring.dat) and a mode (such as "w" or "r" or "a", specifying the type of access to a file). When entering an associated with-block, this context manager will
"locked-"+fn exists"locked-"+fnfn in mode mode and return the file objectAnd when exiting the with-block, this context manager will
fn"locked-"+fnYou might use this context manager as follows:
print("I'm about to attempt to open reserved-seats.txt for exclusive use.")
print("If another process already has it locked, there may be a delay.")
with OpenWithLock("reserved-seats.txt","r") as fp:
print("Ok, I have exclusive access to reserved-seats.txt")
print("A lock file named 'locked-reserved-seats.txt' was created so other programs know that.")
x = fp.read()
# maybe do things with x...
print("I have relinquished my exclusive access to reserved-seats.txt")
print("The lock file has been removed.")
# Based on solution prepared for MCS 275 Spring 2023
class OpenWithLock:
"""Context manager for locking a file when in use"""
def __init__(self, fn, mode):
"""Save file name and file opening mode as attributes"""
self.fn = fn
self.mode = mode
def __enter__(self):
"""Wait until lockfile no longer exists, then create lockfile and open given file"""
# Wait until lockfile no longer exists
while os.path.exists("locked-" + self.fn):
time.sleep(0.1)
# Create lockfile by opening and closing
open("locked-" + self.fn, "a").close()
self.file = open(self.fn, self.mode)
return self.file
def __exit__(self, exc_type, exc, tb):
"""When finished, close file and remove lockfile."""
self.file.close()
os.remove("locked-" + self.fn)
How can you test that this context manager behaves as expected? If you haven't tested the behavior when the lock file already exists, it is hard to know whether the context manager is working!
If we write a+b+c+d, then we are using the associativity of addition to avoid the need for any parentheses.
There are lots of ways to put parentheses into the expression so that each time we use addition, it is a binary operation. For example:
((a+b)+(c+d)) (i.e. first add a+b, then add c+d, then sum the results)(a+(b+(c+d))) (i.e. first add c+d, then add b to that, then add a to that)Write a Python function that takes a list of integers and returns all possible ways of parenthesizing the sum fully.
This requires a choice of how to represent the input sum and output parenthesized sums. Instead of using strings, make your function so it expects a list of summands as input and returns a list of possible parenthesized versions that use nested Python lists to represent the parentheses, as in the following example:
put_parens([2,1,5,8]) # find all ways to put parentheses in the expression 2+1+5+8
The return value is a list of length 5, which means there are five ways to add parentheses. Each item in the list describes one of the ways in to add parentheses, with nested lists instead of nested parentheses. So the five items shown above represent the expressions:
(2+(1+(5+8)))
(2+((1+5)+8))
(2+1)+(5+8)
((2+(1+5))+8)
(((2+1)+5)+8)put_parens may call itself many times, with the exact number of times depending on its argument.# Based on solution prepared for MCS 275 Spring 2023
def put_parens(L):
"""Finds all ways to put parentheses"""
if len(L) == 1: # No way to put parentheses
return L
if len(L) == 2: # Only one way to put parentheses
return [L]
output = []
# At each index `i`, split the list into two halves
for i in range(1, len(L)):
# Make a recursive call on each half
first_halves = put_parens(L[:i])
second_halves = put_parens(L[i:])
# Then for every possible combination of parentheses from the first half, ...
# ... match them with a possible combination from the second half.
# This gives us every combination of parentheses for the whole list `L`.
for first in first_halves:
for second in second_halves:
output.append([first, second])
return output
Work on this if you have extra time. No solutions will be given. Feel free to ask the instructor if you work on this outside of lab and have questions!
It would be nice if the lock file created by the context manager from problem didn't just capture the fact that some program was using a file, but also which program.
The module os contains a function os.getpid() which returns a numerical identifier (process ID or PID) that the operating system gives to the currently-running program, like so:
import os
os.getpid()
Modify the OpenWithLock class so that the lock file's name is not fixed, but instead incorporates the PID of the program that locked it. Thus if process 21256 locks keyring.dat, it would do so by creating a file named locked-21256-keyring.dat
But when the class is checking whether or not the file is already locked, it needs to look for any file whose name begins with "locked-" and ends with "-keyring.dat". If any such file exists, then it waits until that file is gone before creating its own lock file.
To check whether a file whose name matches a certain pattern exists, you have a couple of choices:
glob.glob, a function built for enumerating all files whose names match a pattern; read how to use it in Python documentation of the glob moduleos.listdir to get a listing of all files, and then check them one by one to see if they start with "locked-" and end with "-" + fn.This continues the work from problem 3.
Suppose we define a new sequence $c_n$ as follows: $c_n$ is the number of function calls that occur when calculating $T_n$ recursively. That is, $c_n$ is ths sequence of call counts you saw in part C of problem 3.
Can you determine a formula that gives $c_n$, perhaps as a sum of previous terms?
The function T_call_count given above is based on the observation that $c_n = c_{n-1} + c_{n-2} + c_{n-3} + 1$.