Discussion 1: Control, Environment Diagrams

Attendance

Your TA will come around during discussion to check you in. You can start on the worksheet before being checked in; you don't need to wait for your TA to get started.

If you didn't attend for a good reason (such as being sick), fill out this form (within 2 weeks of your discussion): attendance form

If you get stuck, there are walkthrough videos (@berkeley.edu login to YouTube required).

Ice Breaker

Everyone say your name and some activity you enjoy doing outside. For each activity, ask if anyone else in your group likes to do that too. (Optional: after discussion you could make plans to go do one of these activities together.)

Then, each person share an expression that people say when they really like something, such as "awesome" or "nice one" or "that's tuff." Each person should try to come up with a different expression. Feel free to ask your group for help if you're stuck. You can even use other languages than English. Then, during the discussion, if someone says or does something well, use your expression!

While and If

Learning to use if and while is essential. During this discussion, focus on what we've studied in the first three lectures: if, while, assignment (=), comparison (<, >, ==, ...), and arithmetic. Please don't use any features of Python that we haven't discussed in class yet, such as for, range, and lists. We'll have plenty of time for those later, but now is the time to practice if (textbook 1.5.4) and while (textbook 1.5.5).

Q1: Race

Important facts about Python for this question:

• 0 is a false value and all other numbers are true values.
• x += 1 is the same as x = x + 1 when x is assigned to a number.

The race function below, which is supposed to return how many minutes pass until the tortoise first catches up to the hare, sometimes returns the wrong value or runs forever. Discuss why with your group, studying each line of code and considering different examples.

def race(x, y):
    """The tortoise always walks x feet per minute, while the hare repeatedly
    runs y feet per minute for 5 minutes, then rests for 5 minutes. Return how
    many minutes pass until the tortoise first catches up to the hare.

    The tortoise catches up to the hare when it has gone a greater distance
    than the hare.

    These examples work correctly:

    >>> race(5, 7)  # After 7 minutes, both have gone 35 steps
    7
    >>> race(2, 4) # After 10 minutes, both have gone 20 steps
    10
    """
    assert y > x and y <= 2 * x, 'the hare must be faster but at most 2x faster'
    tortoise, hare, minutes = 0, 0, 0
    while (minutes == 0) or (tortoise - hare):
        tortoise += x
        if minutes % 10 < 5:
            hare += y
        minutes += 1
    return minutes

Find positive integers x and y (with y larger than x but not larger than 2 * x) for which either:

• race(x, y) returns the wrong value or
• race(x, y) runs forever

You just need to find one pair of numbers that satisfies either of these conditions to finish the question, but the most important part is describing why the function doesn't work for your example.

If you want to discuss this problem with a TA, just ask.

Q2: Fizzbuzz

Implement the classic Fizz Buzz sequence. The fizzbuzz function takes a positive integer n and prints out a single line for each integer from 1 to n. For each i:

• If i is divisible by both 3 and 5, print fizzbuzz.
• If i is divisible by 3 (but not 5), print fizz.
• If i is divisible by 5 (but not 3), print buzz.
• Otherwise, print the number i.

Try to make your implementation of fizzbuzz concise.

def fizzbuzz(n):
    """
    >>> result = fizzbuzz(16)
    1
    2
    fizz
    4
    buzz
    fizz
    7
    8
    fizz
    buzz
    11
    fizz
    13
    14
    fizzbuzz
    16
    >>> print(result)
    None
    """

Problem Solving

A useful approach to implementing a function is to:

1. Pick an example input and corresponding output.
2. Describe a process (in English) that computes the output from the input using simple steps.
3. Figure out what additional names you'll need to carry out this process.
4. Implement the process in code using those additional names.
5. Determine whether the implementation really works on your original example.
6. Determine whether the implementation really works on other examples. (If not, you might need to revise step 2.)

Importantly, this approach doesn't go straight from reading a question to writing code.

For example, in the is_prime problem below, you could:

1. Pick n is 9 as the input and False as the output.
2. Here's a process: Check that 9 (n) is not a multiple of any integers between 1 and 9 (n).
3. Introduce i to represent each number between 1 and 9 (n).
4. Implement is_prime (you get to do this part with your group).
5. Check that is_prime(9) will return False by thinking through the execution of the code.
6. Check that is_prime(3) will return True and is_prime(1) will return False.

Try this approach together on the next two problems.

Important: Don't check your work using a computer right away. Instead, talk to your group and think to try to figure out if an answer is correct. On exams, you won't be able to guess and check because you won't have a Python interpreter. Now is a great time to practice checking your work by thinking through examples. You could even draw an environment diagram!

If you're not sure about how something works or get stuck, ask for help from the course staff.

Q3: Is Prime?

Write a function that returns True if a positive integer n is a prime number and False otherwise.

A prime number n is a number that is not divisible by any numbers other than 1 and n itself. For example, 13 is prime, since it is only divisible by 1 and 13, but 14 is not, since it is divisible by 1, 2, 7, and 14.

Use the % operator: x % y returns the remainder of x when divided by y.

def is_prime(n):
    """
    >>> is_prime(10)
    False
    >>> is_prime(7)
    True
    >>> is_prime(1) # one is not a prime number!!
    False
    """

Hint 1 (at the end)

Description Time: Come up with a one sentence description of the process you implemented to solve is_prime that you think someone could understand without looking at your code. Try not to just read your code, but instead describe the process it carries out.

Q4: Unique Digits

Write a function that returns the number of unique digits in a positive integer.

Tips:

• You can use // and % to separate a positive integer into its one's digit and the rest of its digits.
• You may find it helpful to first define a function has_digit(n, k), which determines whether a number n has digit k.

def unique_digits(n):
    """Return the number of unique digits in positive integer n.

    >>> unique_digits(8675309) # All are unique
    7
    >>> unique_digits(13173131) # 1, 3, and 7
    3
    >>> unique_digits(101) # 0 and 1
    2
    """


def has_digit(n, k):
    """Returns whether k is a digit in n.

    >>> has_digit(10, 1)
    True
    >>> has_digit(12, 7)
    False
    """
    assert k >= 0 and k < 10

Hint 2 (at the end)

Environment Diagrams

Q5: Bottles

An environment diagram keeps track of names and their values in frames, which are drawn as boxes.

Answer the following questions about the code below and afterwards, step through the diagram to check your answers.

bottles = 99
take = 1

def pass_it(around):
    bottles = 98
    return take

remaining = bottles - pass_it(bottles)
bottles = remaining

1) What determines how many different frames appear in an environment diagram?
a) The number of functions defined in the code
b) The number of call expressions in the code
c) The number of return statements in the code
d) The number of times user-defined functions are called when running the code

2) What happens to the return value of pass_it(bottles)?
a) It is used for the new value of remaining in the global frame
b) It is used for the new value of bottles in the global frame
c) It is used for the new value of pass_it in the global frame
d) None of the above

3) What effect does the line bottles = 98 have on the global frame?
a) It temporarily changes the value bound to bottles in the global frame.
b) It permanently changes the value bound to bottles in the global frame.
c) It has no effect on the global frame.

To check your answers, step through the environment diagram in Python Tutor (opens a new tab).

Q6: Double Trouble

Draw the environment diagram for the code below on paper or a whiteboard (without having the computer draw it for you)!

def double(x):
    return x * 2

def triple(x):
    return x * 3

hat = double
double = triple

Then step through the environment diagram in Python Tutor (opens a new tab) to check your work.

Optional: Exam Practice

If you all finish early, it's a great idea to get ready for Midterm 1 by trying out this slight variant of a CS 61A Spring 2023 Midterm 1 question.

Q7: Repeating

Definition: A positive integer n is a repeating sequence of positive integer m if n is written by repeating the digits of m one or more times. For example, 616161 is a repeating sequence of 61, but 61616 is not.

Implement repeating which takes positive integers t and n. It returns whether n is a repeating sequence of some t-digit integer.

def repeating(t, n):
    """Return whether t digits repeat to form positive integer n.

    >>> repeating(1, 6161)
    False
    >>> repeating(2, 6161)  # repeats 61 (2 digits)
    True
    >>> repeating(3, 6161)
    False
    >>> repeating(4, 6161)  # repeats 6161 (4 digits)
    True
    >>> repeating(5, 6161)  # there are only 4 digits
    False
    """
    if pow(10, t-1) > n:  # make sure n has at least t digits
        return False
    end = _____
    rest = n
    while rest:
        if rest % pow(10, t) != end:
           return _____
        _____
    return True

Hint 3 (at the end)

i = 2
while i < n:
    ...
    i = i + 1