IMPORTANT In this question, assume that all of f, g, and h are functions that take one non-negative integer argument and return a non-negative integer. You do not need to consider negative or fractional numbers.
Implement the higher-order function decompose1, which takes two functions f and h as arguments. It returns a function g that relates f to h in the following way: For any non-negative integer x, h(x) equals f(g(x)). Assume that decompose1 will be called only on arguments for which such a function g exists. Furthermore, assume that there is no recursion depth limit in Python.
def decompose1(f, h):
"""
Return g such that h(x) equals f(g(x)) for any non-negative integer x.
>>> add_one = lambda x: x + 1
>>> square_then_add_one = lambda x: x * x + 1
>>> g = decompose1(add_one, square_then_add_one)
>>> g(5)
25
>>> g(10)
100
"""
def g(x):
def r(y):
if :
return
else:
return
return r(0)
Write a number in the blank so that the final expression below evaluates to 2015. Assume decompose1 is implemented correctly.
def make_adder(a):
def add_to_a(b):
return a + b
return add_to_a
def compose1(f, g):
def h(x):
return f(g(x))
return h
e, square = make_adder(1), lambda x: x*x
decompose1(e, compose1(square, e))(3) + Implement the combine function, which takes a non-negative integer n, a two-argument function f, and a number result. It applies f to the first digit of n and the result of combining the rest of the digits of n by repeatedly applying f (see the doctests). If n has no digits (because it is zero), combine returns result.
from operator import add, mul
def combine(n, f, result):
"""
Combine the digits in non-negative integer n using f.
>>> combine(3, mul, 2) # mul(3, 2)
6
>>> combine(43, mul, 2) # mul(4, mul(3, 2))
24
>>> combine(6502, add, 3) # add(6, add(5, add(0, add(2, 3)))
16
>>> combine(239, pow, 0) # pow(2, pow(3, pow(9, 0)))
8
"""
if n == 0:
return result
else:
return combine(, , )Implement the memory function, which takes a number x and a single-argument function f. It returns a function with a peculiar behavior that you must discover from the doctests. You may only use names and call expressions in your solution. You may not write numbers or use features of Python not yet covered in the course.
square = lambda x: x * x
double = lambda x: 2 * x
def memory(x, f):
"""
Return a higher-order function that prints its memories.
>>> f = memory(3, lambda x: x)
>>> f = f(square)
3
>>> f = f(double)
9
>>> f = f(print)
6
>>> f = f(square)
3
None
"""
def g(h):
print()
return
return gSuppose 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:
aab(ab)ca(bc)a(b(cd))a((bc)d)(ab)(cd)(a(bc))d((ab)c)dAssume, 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 A classic puzzle called the Towers of Hanoi is a game that consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with n disks in a neat stack in ascending order of size on a start rod, the smallest at the top, forming a conical shape.
The objective of the puzzle is to move the entire stack to an end rod, obeying the following rules:
Complete the definition of move_stack, which prints out the steps required to move n disks from the start rod to the end rod without violating the rules.
def print_move(origin, destination):
"""
Print instructions to move a disk.
"""
print("Move the top disk from rod", origin, "to rod", destination)
def move_stack(n, start, end):
"""
Print the moves required to move n disks on the start pole to the end pole without violating the rules of Towers of Hanoi.
n -- number of disks
start -- a pole position, either 1, 2, or 3
end -- a pole position, either 1, 2, or 3
There are exactly three poles, and start and end must be different. Assume
that the start pole has at least n disks of increasing size, and the end
pole is either empty or has a top disk larger than the top n start disks.
>>> move_stack(1, 1, 3)
Move the top disk from rod 1 to rod 3
>>> move_stack(2, 1, 3)
Move the top disk from rod 1 to rod 2
Move the top disk from rod 1 to rod 3
Move the top disk from rod 2 to rod 3
>>> move_stack(3, 1, 3)
Move the top disk from rod 1 to rod 3
Move the top disk from rod 1 to rod 2
Move the top disk from rod 3 to rod 2
Move the top disk from rod 1 to rod 3
Move the top disk from rod 2 to rod 1
Move the top disk from rod 2 to rod 3
Move the top disk from rod 1 to rod 3
"""
assert 1 <= start <= 3 and 1 <= end <= 3 and start != end, "Bad start/end"
"*** YOUR CODE HERE ***"Solution
def print_move(origin, destination):
"""
Print instructions to move a disk.
"""
print("Move the top disk from rod", origin, "to rod", destination)
def move_stack(n, start, end):
"""
Print the moves required to move n disks on the start pole to the end pole without violating the rules of Towers of Hanoi.
n -- number of disks
start -- a pole position, either 1, 2, or 3
end -- a pole position, either 1, 2, or 3
There are exactly three poles, and start and end must be different. Assume
that the start pole has at least n disks of increasing size, and the end
pole is either empty or has a top disk larger than the top n start disks.
>>> move_stack(1, 1, 3)
Move the top disk from rod 1 to rod 3
>>> move_stack(2, 1, 3)
Move the top disk from rod 1 to rod 2
Move the top disk from rod 1 to rod 3
Move the top disk from rod 2 to rod 3
>>> move_stack(3, 1, 3)
Move the top disk from rod 1 to rod 3
Move the top disk from rod 1 to rod 2
Move the top disk from rod 3 to rod 2
Move the top disk from rod 1 to rod 3
Move the top disk from rod 2 to rod 1
Move the top disk from rod 2 to rod 3
Move the top disk from rod 1 to rod 3
"""
assert 1 <= start <= 3 and 1 <= end <= 3 and start != end, "Bad start/end"
if n == 1:
print_move(start, end)
else:
other = 6 - start - end
move_stack(n - 1, start, other)
print_move(start, end)
move_stack(n - 1, other, end)
Fill in the blanks of the implementation of sixty_ones below, a function that takes a Link instance representing a sequence of integers and returns the number of times that 6 and 1 appear consecutively.
def sixty_ones(s):
"""
Return the number of times that 1 directly follows 6 in linked list s.
>>> once = Link(4, Link(6, Link(1, Link(6, Link(0, Link(1))))))
>>> twice = Link(1, Link(6, Link(1, once)))
>>> thrice = Link(6, twice)
>>> apply_to_all(sixty_ones, [Link.empty, once, twice, thrice])
[0, 1, 2, 3]
"""
if :
return 0
elif :
return 1 +
else:
return Fill in the blanks of the implementation of no_eleven below, a function that returns a list of all distinct length-n lists of ones and sixes in which 1 and 1 do not appear consecutively.
def no_eleven(n):
"""
Return a list of lists of 1’s and 6’s that do not contain 1 after 1.
>>> no_eleven(2)
[[6, 6], [6, 1], [1, 6]]
>>> no_eleven(3)
[[6, 6, 6], [6, 6, 1], [6, 1, 6], [1, 6, 6], [1, 6, 1]]
>>> no_eleven(4)[:4] # first half
[[6, 6, 6, 6], [6, 6, 6, 1], [6, 6, 1, 6], [6, 1, 6, 6]]
>>> no_eleven(4)[4:] # second half
[[6, 1, 6, 1], [1, 6, 6, 6], [1, 6, 6, 1], [1, 6, 1, 6]]
"""
if n == 0:
return
elif n == 1:
return
else:
a, b = no_eleven(), no_eleven()
return [ for s in a] + [ for s in b]