# Homework 1: Variables & Functions, Control hw01.zip

Due by 11:59pm on Wednesday, June 30

## Instructions

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` or `min` 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 divides `a`, you can use the expression `a % b == 0`, which can be read as, "the remainder of dividing `a` by `b` 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.

1. Pick a positive integer `n` as the start.
2. If `n` is even, divide it by 2.
3. If `n` is odd, multiply it by 3 and add 1.
4. 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:

• 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` and `n`: the same parameters as in `summation` and `product`
• `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 all `a`, `b`, and `c`. However, you may not assume `merger` 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 and `if_function` differ, consider the rules of evaluation for `if` statements and call expressions.

Use Ok to test your code:

``````python3 ok -q with_if_statement
python3 ok -q with_if_function``````