# CS 61A

Time: Tue 9/12/17 2 pm

## Higher Order Functions

### Digit Fidget (fa15-mt1-3)

IMPORTANT DEFINITION Each digit in a non-negative integer `n` has a digit position. Digit positions begin at `0` and count from the right-most digit of `n`. For example, in `568789`, the digit `9` is at position `0` and digit `7` is at position `2`. The digit `8` appears at both positions `1` and `3`.

1. Implement the find_digit function, which takes a non-negative integer `n` and a digit `d` greater than `0` and less than `10`. It returns the largest (left-most) position in `n` at which digit `d` appears. If `d` does not appear in `n`, then `find_digit` returns `False`. You may not use recursive calls.

``````def find_digit(n, d):
"""
Return the largest digit position in n for which d is the digit.

>>> find_digit(567, 7)
0
>>> find_digit(567, 5)
2
>>> find_digit(567, 9)
False
>>> find_digit(568789, 8) # 8 appears at positions 1 and 3
3
"""

i, k = 0,
while n:
n, last = n // 10, n % 10
if last == :

i = i + 1
return ``````
2. Find all values of `y` between 1 and 9 (inclusive) for which the final expression below evaluates to `True`. Assume that `find_digit` is implemented correctly.

``````def compose1(f, g):
def h(x):
return f(g(x))
return h

f = lambda x: find_digit(234567, x)
compose1(f, f)(y) == y``````

### Lambda at Last (fa14-mt1-4)

1. Fill in the blank below with an expression so that the second line evaluates to 2014. You may only use the names `two_thousand`, `two`, `k`, `four`, and `teen` and parentheses in your expression (no numbers, operators, etc.)

``````two_thousand = lambda two: lambda k:
two_thousand(7)(lambda four: lambda teen: 2000 + four + teen)``````
2. The `if_fn` returns a two-argument function that can be used to select among alternatives, similar to an if statement. Fill in the return expression of factorial so that it is defined correctly for non-negative arguments. You may only use the names `if_fn`, `condition`, `a`, `b`, `n`, `factorial`, `base`, and `recursive` and parentheses in your expression (no numbers, operators, etc.).

``````def if_fn(condition):
if condition:
return lambda a, b: a
else:
return lambda a, b: b

def factorial(n):
"""
Compute N! for non-negative N. N! = 1 * 2 * 3 * ... * N.

>>> factorial(3)
6
>>> factorial(5)
120
>>> factorial(0)
1
"""

def base():
return 1

def recursive():
return n * factorial(n-1)

return ``````

## Tree Recursion

Suppose we have a sequence of quantities that we want to multiply together, but can only multiply two at a time. We can express the various ways of doing so by counting the number of different ways to parenthesize the sequence. For example, here are the possibilities for products of 1, 2, 3 and 4 elements:

• 1 element of 1 possibility
`a`
• 2 elements of 1 possibility
`ab`
• 3 elements of 2 possibilities
`(ab)c`
`a(bc)`
• 4 elements of 5 possibilities
`a(b(cd))`
`a((bc)d)`
`(ab)(cd)`
`(a(bc))d`
`((ab)c)d`

Assume, as in the table above, that we don’t want to reorder elements.
Define a function `count_groupings` that takes a positive integer `n` and returns the number of ways of parenthesizing the product of `n` numbers. (You might not need to use all lines.)

``````def count_groupings(n):
"""
For N >= 1, the number of distinct parenthesizations of a product of N items.

>>> count_groupings(1)
1
>>> count_groupings(2)
1
>>> count_groupings(3)
2
>>> count_groupings(4)
5
>>> count_groupings(5)
14
"""
if n == 1:
return

i =
while :

i += 1
return ``````

## Misc Midterm 1 Prep

### You Complete Me (sp15-mt1-3)

Add parentheses and single-digit integers in the blanks below so that the expression on the second line evaluates to `2015`. You may only add parentheses and single-digit integers. You may leave some blanks empty.

``````lamb = lambda lamb: lambda: lamb + lamb
lamb(1000)__________ + (lambda b, c: b__________ * b__________ - c__________)(lamb(__________), 1)__________``````