# Practice problems: Control structures

## Easy

### Question 1: Fix the Bug

The following snippet of code doesn't work! Figure out what is wrong and fix the bugs.

```
def compare(a, b):
""" Compares if a and b are equal.
>>> compare(4, 2)
'not equal'
>>> compare(4, 4)
'equal'
"""
if a = b:
return 'equal'
return 'not equal'
```

The line `a = b`

will cause a `SyntaxError`

. Instead, it should be

`if a == b:`

### Question 2: Last square

Implement the function `last_square`

, which takes as input a positive
integer and returns the largest perfect square less than its argument.
A perfect square is any integer multiplied by itself:

*Hint:* If you're stuck, try writing a function that prints out the
first 5 perfect squares using a `while`

statement: 1, 4, 9, 16, 25.
Then, adapt that `while`

statement to this question by changing the
header.

```
def last_square(x):
"""Return the largest perfect square less than X, where X>0.
>>> last_square(10)
9
>>> last_square(39)
36
>>> last_square(100)
81
>>> result = last_square(2) # Return, don't print
>>> result
1
>>> cases = [(1, 0), (2, 1), (3, 1), (4, 1), (5, 4), (6, 4),
... (10, 9), (17, 16), (26, 25), (36, 25), (46, 36)]
>>> [last_square(s) == t for s, t in cases].count(False)
0
"""
"*** YOUR CODE HERE ***"
k = 0
while k * k < x:
k = k + 1
return (k-1) * (k-1)
```

We iterate over perfect squares until we find the first one larger or
equal to the input. The answer is then the square *before* that one.
This solution is inefficient, but an efficient solution requires taking
a square root.

### Question 3

An *open interval* is a range of numbers that does not include its end
points. For example, (10, 15) stands for all numbers that are strictly
greater than 10 and strictly less than 15. Two intervals *overlap* if
they contain any points in common. For example (10, 15) overlaps (14,
16), but not (1, 5) or (15, 16). The intervals (10, 10) or (10, 9)
contain no numbers, since nothing is both greater than and less than
10, or greater than 10 and less than 9. Implement the function
`overlaps`

to take four numbers as arguments, representing the bounds
of two intervals, and return `True`

if the intervals overlap and
`False`

otherwise.

```
def overlaps(low0, high0, low1, high1):
"""Return whether the open intervals (LOW0, HIGH0) and (LOW1, HIGH1)
overlap.
>>> overlaps(10, 15, 14, 16)
True
>>> overlaps(10, 15, 1, 5)
False
>>> overlaps(10, 10, 9, 11)
False
>>> result = overlaps(1, 5, 0, 3) # Return, don't print
>>> result
True
>>> [overlaps(a0, b0, a1, b1) for a0, b0, a1, b1 in
... ( (1, 4, 2, 3), (1, 4, 0, 2), (1, 4, 3, 5), (0.1, 0.4, 0.2, 0.3),
... (2, 3, 1, 4), (0, 2, 1, 4), (3, 5, 1, 4) )].count(False)
0
>>> [overlaps(a0, b0, a1, b1) for a0, b0, a1, b1 in
... ( (1, 4, -1, 0), (1, 4, 5, 6), (1, 4, 4, 5), (1, 4, 0, 1),
... (-1, 0, 1, 4), (5, 6, 1, 4), (4, 5, 1, 4), (0, 1, 1, 4),
... (5, 5, 3, 6), (5, 3, 4, 6), (5, 5, 5, 5),
... (3, 6, 5, 5), (4, 6, 5, 3), (0.3, 0.6, 0.5, 0.5) )].count(True)
0
"""
"*** YOUR CODE HERE ***"
return low1 < min(high0, high1) > low0
```

There are many solutions to this problem. One way to look at it is to
consider conditions under which the intervals *don't* overlap. Clearly
for two non-empty not to overlap, one has to come entirely before the
other. This becomes `high1 <= low0 or high0 <= low1`

, which when
negated is `high1 > low0 and high1 > low1`

. In addition, both lower
bounds must be less than their respective upper bounds (or the
intervals are empty). The solution given combines these observations.

### Question 4: Triangular numbers

The *n*th triangular number is defined as the sum of all integers from 1 to
*n*, i.e.

`1 + 2 + ... + n`

The closed-form formula for the *n*th triangular
number is

`(n + 1) * n / 2`

Define `triangular_sum`

, which takes an integer `n`

and returns the sum of the
first `n`

triangular numbers, while printing each of the triangular numbers
between 1 and the `n`

th triangular number.

```
def triangular_sum(n):
"""
>>> t_sum = triangular_sum(5):
1
3
6
10
15
>>> t_sum
35
"""
"*** YOUR CODE HERE ***"
count = 1
t_sum = 0
while count <= n:
t_number = count * (count + 1) // 2
print(t_number)
t_sum += t_number
count += 1
return t_sum
```

## Medium

### Question 5: Same hailstone

Implement `same_hailstone`

, which returns whether positive integer arguments
`a`

and `b`

are part of the same hailstone sequence. A hailstone sequence is
defined in Homework 1 as the following:

- 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.

```
def same_hailstone(a, b):
"""Return whether a and b are both members of the same hailstone
sequence.
>>> same_hailstone(10, 16) # 10, 5, 16, 8, 4, 2, 1
True
>>> same_hailstone(16, 10) # order doesn't matter
True
>>> result = same_hailstone(3, 19) # return, don't print
>>> result
False
Extra tests:
>>> same_hailstone(19, 3)
False
>>> same_hailstone(4858, 61)
True
>>> same_hailstone(7, 6)
False
"""
"*** YOUR CODE HERE ***"
return in_hailstone(a, b) or in_hailstone(b, a)
def in_hailstone(a, b):
"""Return whether b is in hailstone sequence of a."""
while a > 1:
if a == b:
return True
elif a % 2 == 0:
a = a // 2
else:
a = a * 3 + 1
return False
```

### Question 6

Implement the function `nearest_two`

, which takes as input a positive number
`x`

and returns the power of two (..., 1/8, 1/4, 1/2, 1, 2, 4, 8, ...) that is
nearest to `x`

. If `x`

is exactly between two powers of two, return the larger.

You may change the starter implementation if you wish.

```
def nearest_two(x):
"""Return the power of two that is nearest to x.
>>> nearest_two(8) # 2 * 2 * 2 is 8
8.0
>>> nearest_two(11.5) # 11.5 is closer to 8 than 16
8.0
>>> nearest_two(14) # 14 is closer to 16 than 8
16.0
>>> nearest_two(2015)
2048.0
>>> nearest_two(.1)
0.125
>>> nearest_two(0.75) # Tie between 1/2 and 1
1.0
>>> nearest_two(1.5) # Tie between 1 and 2
2.0
>>> nearest_two(3)
4.0
>>> nearest_two(.01)
0.0078125
"""
power_of_two = 1.0
"*** YOUR CODE HERE ***"
if x < 1:
factor = 0.5
else:
factor = 2
while abs(power_of_two * factor - x) < abs(power_of_two - x):
power_of_two = power_of_two * factor
if abs(power_of_two * 2 - x) == abs(power_of_two - x):
power_of_two = power_of_two * 2 return power_of_two
```

This implementation repeatedly doubles or halves the number `power_of_two`

until reaching the closest number to `x`

. The last three lines enforce the
tie-breaking policy when `x`

is exactly betweeen two powers of two.

### Question 7

Complete the implementation of `pi_fraction`

, which takes a positive number
`gap`

and prints the fraction that is no more than `gap`

away from `pi`

and has
the smallest possible positive integer denominator. See the doctests for the
format of the printed output.

*Hint*: If you want to find the nearest integer to a number, use the built-in
`round`

function. It's possible to solve this problem without using `round`

.

You may change the starter implementation if you wish.

```
from math import pi
def pi_fraction(gap):
"""Print the fraction within gap of pi that has the smallest denominator.
>>> pi_fraction(0.01)
22 / 7 = 3.142857142857143
>>> pi_fraction(1)
3 / 1 = 3.0
>>> pi_fraction(1/8)
13 / 4 = 3.25
>>> pi_fraction(1e-6)
355 / 113 = 3.1415929203539825
>>> pi_fraction(1e-3)
201 / 64 = 3.140625
>>> pi_fraction(1/32)
19 / 6 = 3.1666666666666665
"""
numerator, denominator = 3, 1
"*** YOUR CODE HERE ***"
while abs(numerator/denominator-pi) > gap:
denominator = denominator + 1
numerator = round(pi * denominator) print(numerator, '/', denominator, '=', numerator/denominator)
```

This implementation repeatedly increases `denominator`

until the nearest
fraction to `pi`

is within `gap`

.