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'

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)

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

Question 4: Triangular numbers

The nth 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 nth 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 nth 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:

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.

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

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)