MCS 275 Spring 2024 Homework 4 Sample Solution¶

import time

class TimedBlock:
    """
    Context manager that tracks and prints total time 
    spent in the with-block
    """
    def __init__(self,title):
        "Initialize a named, timed block context manager"
        self.title = title
    def __enter__(self):
        "Display message and begin timing"
        print("Starting timed block '{}'".format(self.title))
        self.t0 = time.time()
    def __exit__(self,a,b,c):
        "Compute and print elapsed time"
        self.t1 = time.time()
        print("Exited timed block '{}' after {:.4f}s".format(self.title,self.t1-self.t0))

# Sample usage to time a bunch of calculations
with TimedBlock("Gigantic integer arithmetic"):
    digits = 0
    for k in range(5000):
        x = 3**k - 2**k
        digits += len(str(x))
    print("Total of {} digits".format(digits))

# Sample usage showing we still get timing data if the with-block
# raises an exception
with TimedBlock("Float arithmetic that eventually fails"):
    for k in range(5000):
        x = 1 / (3**(4000-k) - 2**(4000-k))

# Sample usage showing output is only printed when we enter the with-block
# and NOT when the class is instantiated
B = TimedBlock("Notice the constructor doesn't print anything")

# Sample usage showing that timing begins when the with-block begins
# and NOT whent he TimedBlock constructor is called.
B = TimedBlock("Should take about 0.5 seconds")
# The next delay isn't part of the timing
time.sleep(1.5)
with B:
    # This delay IS part of the timing
    time.sleep(0.5)

def DRB(n):
    """
    Recursive implementation of 'digital recursion breath' sequence
    """
    if n<=2:
        return 1
    d = len(str(n))
    x = 0
    for i in range(d+2):
        x += DRB(n-1-i)
    return x

[DRB(n) for n in range(15)]

def DRB_iterative(n):
    """
    Iterative implementation of 'digital recursion breath' sequence
    """
    if n<=2:
        return 1
    # Store d+2 recent terms in `context`
    context = [1,1,1]
    # At the end of each iteration of this loop,
    # the last element of `context` will be DRB(k)
    for k in range(3,n+1):
        # make sure `context` has the right length
        if len(context) > len(str(k))+2:
            context = context[1:]
        # Note: sum(L) returns sum of list items, which is useful
        # (But we could just as well use a for loop)
        context.append(sum(context))
    return context[-1]

[DRB_iterative(n) for n in range(15)]

agree = True
print("{:>3} {:>5} {:>5}".format("n","rec","iter"))
for n in range(20):
    xrec = DRB(n)
    xiter = DRB_iterative(n)
    print("{:3d} {:5d} {:5d}".format(n,xrec,xiter))
    assert xrec==xiter

print("\nAll computed values agree.")