Homework 1: Variables & Functions, Control
Due by 11:59pm on Wednesday, June 30
Instructions
Download hw01.zip.
Submission: When you are done, submit with python3 ok
--submit
. You may submit more than once before the deadline; only the
final submission will be scored. Check that you have successfully submitted
your code on okpy.org. See Lab 0 for more instructions on
submitting assignments.
Using Ok: If you have any questions about using Ok, please refer to this guide.
Readings: You might find the following references useful:
Important: Some of these readings necessary for the homework questions will not be covered until Wednesday's and Thursday's lectures. This homework is fairly long, because you will have 2 more days than a typical homework to work on it. The material required for question 4 will not be covered until Wednesday's lecture, and the material required for questions 5 and 6 will not be covered until Thursday's lecture.
Grading: Homework is graded based on correctness. Each incorrect problem will decrease the total score by one point. There is a homework recovery policy as stated in the syllabus. This homework is out of 3 points.
Required Questions
Assignment Getting Started Video
This video provides some helpful direction for tackling the problems on this assignment.
Functions and Expressions
Q1: A Plus Abs B
Fill in the blanks in the following function for adding a
to the
absolute value of b
, without calling abs
. You may not modify any
of the provided code other than the two blanks.
from operator import add, sub
def a_plus_abs_b(a, b):
"""Return a+abs(b), but without calling abs.
>>> a_plus_abs_b(2, 3)
5
>>> a_plus_abs_b(2, -3)
5
>>> # a check that you didn't change the return statement!
>>> import inspect, re
>>> re.findall(r'^\s*(return .*)', inspect.getsource(a_plus_abs_b), re.M)
['return f(a, b)']
"""
if b < 0:
f = _____
else:
f = _____
return f(a, b)
Use Ok to test your code:
python3 ok -q a_plus_abs_b
Q2: Two of Three
Write a function that takes three positive numbers as arguments and returns the sum of the squares of the two smallest numbers. Use only a single line for the body of the function.
def two_of_three(x, y, z):
"""Return a*a + b*b, where a and b are the two smallest members of the
positive numbers x, y, and z.
>>> two_of_three(1, 2, 3)
5
>>> two_of_three(5, 3, 1)
10
>>> two_of_three(10, 2, 8)
68
>>> two_of_three(5, 5, 5)
50
>>> # check that your code consists of nothing but an expression (this docstring)
>>> # a return statement
>>> import inspect, ast
>>> [type(x).__name__ for x in ast.parse(inspect.getsource(two_of_three)).body[0].body]
['Expr', 'Return']
"""
return _____
Hint: Consider using the
max
ormin
function:>>> max(1, 2, 3) 3 >>> min(-1, -2, -3) -3
Use Ok to test your code:
python3 ok -q two_of_three
Q3: Largest Factor
Write a function that takes an integer n
that is greater than 1 and
returns the largest integer that is smaller than n
and evenly divides n
.
def largest_factor(n):
"""Return the largest factor of n that is smaller than n.
>>> largest_factor(15) # factors are 1, 3, 5
5
>>> largest_factor(80) # factors are 1, 2, 4, 5, 8, 10, 16, 20, 40
40
>>> largest_factor(13) # factor is 1 since 13 is prime
1
"""
"*** YOUR CODE HERE ***"
Hint: To check if
b
evenly dividesa
, you can use the expressiona % b == 0
, which can be read as, "the remainder of dividinga
byb
is 0."
Use Ok to test your code:
python3 ok -q largest_factor
Q4: Hailstone
Douglas Hofstadter's Pulitzer-prize-winning book, Gödel, Escher, Bach, poses the following mathematical puzzle.
- Pick a positive integer
n
as the start. - If
n
is even, divide it by 2. - If
n
is odd, multiply it by 3 and add 1. - Continue this process until
n
is 1.
The number n
will travel up and down but eventually end at 1 (at least for
all numbers that have ever been tried -- nobody has ever proved that the
sequence will terminate). Analogously, a hailstone travels up and down in the
atmosphere before eventually landing on earth.
This sequence of values of n
is often called a Hailstone sequence. Write a
function that takes a single argument with formal parameter name n
, prints
out the hailstone sequence starting at n
, and returns the number of steps in
the sequence:
def hailstone(n):
"""Print the hailstone sequence starting at n and return its
length.
>>> a = hailstone(10)
10
5
16
8
4
2
1
>>> a
7
"""
"*** YOUR CODE HERE ***"
Hailstone sequences can get quite long! Try 27. What's the longest you can find?
Use Ok to test your code:
python3 ok -q hailstone
Curious about hailstones/hailstone sequences? Take a look at these articles:
- Check out this article to learn more about how hailstones work!
- In 2019, there was a major development in understanding how the hailstone conjecture works for most numbers!
Higher Order Functions
Note: We won't be covering the material required to complete this section until Thursday, so you are not expected to be able to start this section until then.
Q5: Product
The summation(n, term)
function from the higher-order functions lecture adds
up term(1) + ... + term(n)
. Write a similar function called product
that
returns term(1) * ... * term(n)
.
def product(n, term):
"""Return the product of the first n terms in a sequence.
n -- a positive integer
term -- a function that takes one argument to produce the term
>>> product(3, identity) # 1 * 2 * 3
6
>>> product(5, identity) # 1 * 2 * 3 * 4 * 5
120
>>> product(3, square) # 1^2 * 2^2 * 3^2
36
>>> product(5, square) # 1^2 * 2^2 * 3^2 * 4^2 * 5^2
14400
>>> product(3, increment) # (1+1) * (2+1) * (3+1)
24
>>> product(3, triple) # 1*3 * 2*3 * 3*3
162
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q product
Q6: Accumulate
Let's take a look at how summation
and product
are instances of a more
general function called accumulate
:
def accumulate(merger, base, n, term):
"""Return the result of merging the first n terms in a sequence and base.
The terms to be merged are term(1), term(2), ..., term(n). merger is a
two-argument commutative function.
>>> accumulate(add, 0, 5, identity) # 0 + 1 + 2 + 3 + 4 + 5
15
>>> accumulate(add, 11, 5, identity) # 11 + 1 + 2 + 3 + 4 + 5
26
>>> accumulate(add, 11, 0, identity) # 11
11
>>> accumulate(add, 11, 3, square) # 11 + 1^2 + 2^2 + 3^2
25
>>> accumulate(mul, 2, 3, square) # 2 * 1^2 * 2^2 * 3^2
72
>>> accumulate(lambda x, y: x + y + 1, 2, 3, square)
19
>>> accumulate(lambda x, y: 2 * (x + y), 2, 3, square)
58
>>> accumulate(lambda x, y: (x + y) % 17, 19, 20, square)
16
"""
"*** YOUR CODE HERE ***"
accumulate
has the following parameters:
term
andn
: the same parameters as insummation
andproduct
merger
: a two-argument function that specifies how the current term is merged with the previously accumulated terms.base
: value at which to start the accumulation.
For example, the result of accumulate(add, 11, 3, square)
is
11 + square(1) + square(2) + square(3) = 25
You may assume that
merger
is commutative. That is,merger(a, b) == merger(b, a)
for alla
,b
, andc
. However, you may not assumemerger
is chosen from a fixed function set and hard-code the solution.
After implementing accumulate
, show how summation
and product
can both be
defined as simple calls to accumulate
:
def summation_using_accumulate(n, term):
"""Returns the sum of term(1) + ... + term(n). The implementation
uses accumulate.
>>> summation_using_accumulate(5, square)
55
>>> summation_using_accumulate(5, triple)
45
>>> from construct_check import check
>>> # ban iteration and recursion
>>> check(HW_SOURCE_FILE, 'summation_using_accumulate',
... ['Recursion', 'For', 'While'])
True
"""
"*** YOUR CODE HERE ***"
def product_using_accumulate(n, term):
"""An implementation of product using accumulate.
>>> product_using_accumulate(4, square)
576
>>> product_using_accumulate(6, triple)
524880
>>> from construct_check import check
>>> # ban iteration and recursion
>>> check(HW_SOURCE_FILE, 'product_using_accumulate',
... ['Recursion', 'For', 'While'])
True
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q accumulate
python3 ok -q summation_using_accumulate
python3 ok -q product_using_accumulate
Submit
Make sure to submit this assignment by running:
python3 ok --submit
Extra Practice
You do not have to submit anything for these problems, but they provide extra practice and can be useful for your learning.
Q7: If Function vs Statement
Let's try to write a function that does the same thing as an if
statement.
def if_function(condition, true_result, false_result):
"""Return true_result if condition is a true value, and
false_result otherwise.
>>> if_function(True, 2, 3)
2
>>> if_function(False, 2, 3)
3
>>> if_function(3==2, 'equal', 'not equal')
'not equal'
>>> if_function(3>2, 'bigger', 'smaller')
'bigger'
"""
if condition:
return true_result
else:
return false_result
Despite the doctests above, this function actually does not do the
same thing as an if
statement in all cases. To prove this fact,
write functions cond
, true_func
, and false_func
such that with_if_statement
prints 61A
, but with_if_function
prints both Welcome to
and 61A
on separate lines.
def with_if_statement():
"""
>>> result = with_if_statement()
61A
>>> print(result)
None
"""
if cond():
return true_func()
else:
return false_func()
def with_if_function():
"""
>>> result = with_if_function()
Welcome to
61A
>>> print(result)
None
"""
return if_function(cond(), true_func(), false_func())
def cond():
"*** YOUR CODE HERE ***"
def true_func():
"*** YOUR CODE HERE ***"
def false_func():
"*** YOUR CODE HERE ***"
Hint: If you are having a hard time identifying how an
if
statement andif_function
differ, consider the rules of evaluation forif
statements and call expressions.
Use Ok to test your code:
python3 ok -q with_if_statement
python3 ok -q with_if_function