15-112 Midterm 2 – Spring 2012
80 minutes

1.       [25 pts; 6 pts each; 1 free pt] Indicate what each will print or draw (assume a 400x400 canvas):
For graphics output, do not explain the output in words, but simply draw the resulting canvas.

Statement(s):

Prints/Draws:

class A(object):
    def __init__(self, x): self.x = x
    def __str__(self): return "A%d" % self.x
class B(A):
    def __init__(self):
        super(B, self).__init__(5)   
    def __str__(self): return "B%d" % self.x
class C(B):
    def __init__(self, a): self.x = 2*a.x
def p(a):
    # Note: each call to p(a) prints 1 line
    print a,
    print type(a).__name__,
    print 1*isinstance(a,A),
    print 1*isinstance(a,B),
    print 1*isinstance(a,C)
p(A(1))
p(B())
p(C(A(3)))

  

canvas.create_rectangle(50, 50, 350, 350)
canvas.create_line(200, 200, 350, 50)
for i in range(1,4):
    (x,y) = (100*i,100*(3-i%2))
    canvas.create_oval(x-20,y-5,x+20,y+5,
                       fill="gray")
    font = "Arial %d" % (20*i)
    canvas.create_text(200,50,text="O",
                       font=font,anchor=E)

 

  

canvas.create_rectangle(50, 50, 350, 350)
def f(canvas, x, y, level):
   if (level == 0):
      canvas.create_oval(x-5,y-5,x+5,y+5)
   else:
      r = 20*level
      if (level%2 == 0):
         (x1,y1) = (x-r,y)
      else:
         (x1,y1) = (x, y-r)
      canvas.create_line(x,y,x1,y1)
      f(canvas, x1, y1, level-1)
f(canvas, 200, 200, 3)

  

def f(x, y):
    print "f", x, y  # don't miss this!
    if (x*y < 10):
        return [(x,y)]
    else:
        return f(x/3, y) + f(x/2, y/2)
print f(6,5)
# Hint: 6 total lines are printed!

 

  

 

2.       [25 pts] Free Response: Monte Carlo
Say that a student is taking a multiple choice test  with 10 questions, where each question has 4 options.  The student did not study for the test, and so guesses randomly on every question.  Write a Python function that uses Monte Carlo methods to return the probability that the student passes the exam by answering at least 6 questions correctly.

3.       [25 pts]  Free Response:  Recursion
Note:  you may not use loops to solve the problems in this section.
a) [5 pts] Write the recursive function factorial(n) that takes a positive integer and returns n!, which is the product of the integers from 1 to n.  So factorial(4) returns 24 (which 4*3*2*1).


b) [10 pts]  Write the recursive function, hanoiMoves(n), that returns the total number of moves required to solve the n-disk Towers of Hanoi problem.  Hint: this is a small change from the Towers of Hanoi solution we covered in class.

c) [10 pts]  Write the function emptyFolderCount(path) that takes the path to a folder and returns the number of empty folders in that folder (or any of its subfolders), where a folder is empty if it contains no folders or files.  Hint:  There is no function like os.path.isEmptyDir.  Just use the os and os.path functions that we have already covered.
 

4.       [25 pts; 8 pts each, 1 free pt]  Free Response:  Graphics and Animation
For each of these problems, assume run() is already written and the canvas is 500x500.  Do not write the part of timerFired that calls timerFired again. Write all other functions that are needed in each case.

a) [8 pts] Write an animation that displays a simple digital timer, where the elapsed time is shown centered in the screen to the nearest tenth of a second.  So initially the time shown is 0.0.  When the user presses “s”, the timer resets to 0.0 and starts.  When the user presses “s” again, the timer stops.  The next press of “s” would reset and start the timer again, and so on.  Note:  you should assume that (1) timerFired is called more frequently than 10 times per second; but also (2) that you do not know exactly how frequently timerFired is called (so your code cannot depend on the exact frequency of those calls, yet must accurately display the elapsed time to the nearest 1/10th of a second).  Hint:  time.time() returns the time in seconds (typically since some time  1970) as a floating-point number.

b) [8 pts] Write an animation where the screen is initially empty.  Each time the user presses the mouse, a new small blue square appears centered on the mouseclick position .  Each time the user presses the ‘d’ key, the oldest still-visible blue square disappears (or, if there are no visible blue squares, a new blue square appears in a random location).

c) [8 pts] Write an animation where a red ball starts in the middle of the screen and sweeps left-to-right (with no vertical movement) with wraparound.   When the ball gets back to the middle, it switches to sweeping top-to-bottom (with no horizontal movement) with wraparound.  And when it gets back to the middle, it keeps switching between vertical and horizontal motion.

Bonus/Optional

a.  Bonus/Optional:  [2.5 pts]  What will this print?

def f(g,a): return sum([g(i) for i in a])
def g(x,d=0): return 2 if x<2 else d+g(x-1,d+1)+g(x-2,d+1)
print f(g,range(4))
 

b.      Bonus/Optional:  [2.5 pts]  What will this print?

a = [1,2]
def f(x,y):
    if (x == f): return y
    elif (type(x) == type(f)): return x(f(y,y),y)
    try: return y(a,a[0])
    except: return 2+f(f,x)
def g(x,y): return 1+x*y
print f(g,f(g,1))