# Discussion 1: Control, Environment Diagrams disc01.pdf

This is an online worksheet that you can work on during discussions. Your work is not graded and you do not need to submit anything. The last section of most worksheets is Exam Prep, which will typically only be taught by your TA if you are in an Exam Prep section. You are of course more than welcome to work on Exam Prep problems on your own.

## Vitamin

The vitamin for Discussion 1 is worth 1 point and located here.

# Control structures

Control structures direct the flow of a program using logical statements. For example, conditionals (`if-elif-else`) allow a program to skip sections of code, and iteration (`while`), allows a program to repeat a section.

## Conditional statements

Conditional statements let programs execute different lines of code depending on certain conditions. Let’s review the `if-elif-else` syntax.

Recall the following points:

• The `elif` and `else` clauses are optional, and you can have any number of `elif` clauses.
• A conditional expression is an expression that evaluates to either a truthy value (`True`, a non-zero integer, etc.) or a falsy value (`False`, `0`, `None`, `""`, `[]`, etc.).
• Only the suite that is indented under the first `if`/`elif` whose conditional expression evaluates to a true value will be executed.
• If none of the conditional expressions evaluate to a true value, then the `else` suite is executed. There can only be one `else` clause in a conditional statement!

``````if <conditional expression>:
<suite of statements>
elif <conditional expression>:
<suite of statements>
else:
<suite of statements>``````

## Boolean Operators

Python also includes the boolean operators `and`, `or`, and `not`. These operators are used to combine and manipulate boolean values.

• `not` returns the opposite truth value of the following expression (so not will always return either `True` or `False`).
• `and` evaluates expressions in order and stops evaluating (short-circuits) once it reaches the first false value, and then returns it. If all values evaluate to a true value, the last value is returned.
• `or` short-circuits at the first true value and returns it. If all values evaluate to a false value, the last value is returned.

``````>>> not None
True
>>> not True
False
>>> -1 and 0 and 1
0
>>> False or 9999 or 1/0
9999``````

### Q1: Jacket Weather?

Alfonso will only wear a jacket outside if it is below 60 degrees or it is raining.

Write a function that takes in the current temperature and a boolean value telling if it is raining. This function should return `True` if Alfonso will wear a jacket and `False` otherwise.

First, try solving this problem using an `if` statement.

Run in 61A Code
Solution
``````def wears_jacket_with_if(temp, raining):
"""
>>> wears_jacket_with_if(90, False)
False
>>> wears_jacket_with_if(40, False)
True
>>> wears_jacket_with_if(100, True)
True
"""
if temp < 60 or raining:
return True
else:
return False``````

Note that we’ll either return `True` or `False` based on a single condition, whose truthiness value will also be either `True` or `False`. Knowing this, try to write this function using a single line.

Run in 61A Code
Solution
``````def wears_jacket(temp, raining):
return temp < 60 or raining``````

### Q2: Case Conundrum

In this question, we will explore the difference between the `if` and `elif` keywords.

What is the result of evaluating the following code?

``````def special_case():
x = 10
if x > 0:
x += 2
elif x < 13:
x += 3
elif x % 2 == 1:
x += 4
return x

special_case()``````

What is the result of evaluating this piece of code?

``````def just_in_case():
x = 10
if x > 0:
x += 2
if x < 13:
x += 3
if x % 2 == 1:
x += 4
return x

just_in_case()``````

``````def case_in_point():
x = 10
if x > 0:
return x + 2
if x < 13:
return x + 3
if x % 2 == 1:
return x + 4
return x

case_in_point()``````

Which of these code snippets result in the same output, and why? Based on your findings, when do you think using a series of `if` statements has the same effect as using both `if` and `elif` cases?

The calls to `special_case` and `case_in_point` both return 12, while the call to `just_in_case` returns 19. Since the number 10 satisfies all three conditions in each function, the value of the variable `x` is incremented three times when `just_in_case` is called. A series of `if` statements has the same effect as using both `if` and `elif` cases if each `if` clause ends in a `return` statement. Video walkthrough

## While loops

To repeat the same statements multiple times in a program, we can use iteration. In Python, one way we can do this is with a while loop.

``````    while <conditional clause>:
<body of statements>``````

As long as `<conditional clause>` evaluates to a true value, `<body of statements>` will continue to be executed. The conditional clause gets evaluated each time the body finishes executing.

### Q3: Square So Slow

What is the result of evaluating the following code?

``````def square(x):
print("here!")
return x * x

def so_slow(num):
x = num
while x > 0:
x=x+1
return x / 0
square(so_slow(5))``````
Solution: This program results in an infinite loop because `x` will always be greater than 0; `x / 0` is never executed. We also know that `here!` is never printed since the operand `so_slow(5)` must be evaluated before `function square(x)` can be called. Here's a video walkthrough.

### Q4: 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.

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

Run in 61A Code
Solution
``````def is_prime(n):
"""
>>> is_prime(10)
False
>>> is_prime(7)
True
"""
if n == 1:
return False
k = 2
while k < n:
if n % k == 0:
return False
k += 1
return True``````

### Q5: Fizzbuzz

Implement `fizzbuzz(n)`, which prints numbers from 1 to `n`. However, for numbers divisible by 3, print "fizz". For numbers divisible by 5, print "buzz". For numbers divisible by both 3 and 5, print "fizzbuzz".

This is a standard software engineering interview question, but we're confident in your ability to solve it!

Run in 61A Code
Solution
``````def fizzbuzz(n):
"""
>>> result = fizzbuzz(16)
1
2
fizz
4
buzz
fizz
7
8
fizz
buzz
11
fizz
13
14
fizzbuzz
16
>>> result == None
True
"""
i = 1
while i <= n:
if i % 3 == 0 and i % 5 == 0:
print('fizzbuzz')
elif i % 3 == 0:
print('fizz')
elif i % 5 == 0:
print('buzz')
else:
print(i)
i += 1``````

# Environment Diagrams

An environment diagram is a model we use to keep track of all the variables that have been defined and the values they are bound to. We will be using this tool throughout the course to understand complex programs involving several different assignments and function calls.

Here's a simple program and its corresponding diagram:

Remember that programs are simply a set of statements, or instructions—so drawing diagrams that represent these programs also involves following sets of instructions! Let’s dive in...

## Assignment Statements

Assignment statements, such as `x = 3`, define variables in programs. To execute one in an environment diagram, record the variable name and the value:

1. Evaluate the expression on the right side of the `=` sign
2. Write the variable name and the expression’s value in the current frame.

### Q6: Assignment Diagram

Use these rules to draw a simple diagram for the assignment statements below:

``````x = 11 % 4
y = x
x **= 2``````
Global frame
Solution

## `def` Statements

A `def` statement creates a function object and binds it to a name. To diagram `def` statements, record the function name and bind the function object to the name. It’s also important to write the parent frame of the function, which is where the function is defined. Very important note: Assignments for def statements use pointers to functions, which can have different behavior than primitive assignments.

1. Draw the function object to the right-hand-side of the frames, denoting the intrinsic name of the function, its parameters, and the parent frame (e.g. `func square(x) [parent = Global]`
2. Write the function name in the current frame and draw an arrow from the name to the function object.

### Q7: def Diagram

Use these rules and the rules for assignment statements to draw a diagram for the code below.

``````def double(x):
return x * 2

def triple(x):
return x * 3

hat = double
double = triple``````
Objects
Global frame
Solution

## Call Expressions

Call expressions, such as `square(2)`, apply functions to arguments. When executing call expressions, we create a new frame in our diagram to keep track of local variables:

1. Evaluate the operator, which should evaluate to a function.
2. Evaluate the operands from left to right.
3. Draw a new frame, labelling it with the following:

• A unique index (`f1`, `f2`, `f3`, ...)
• The intrinsic name of the function, which is the name of the function object itself. For example, if the function object is `func square(x) [parent=Global]`, the intrinsic name is `square`.
• The parent frame ([`parent=Global`])
4. Bind the formal parameters to the argument values obtained in step 2 (e.g. bind `x` to 3).
5. Evaluate the body of the function in this new frame until a return value is obtained. Write down the return value in the frame.

If a function does not have a return value, it implicitly returns `None`. In that case, the “Return value” box should contain `None`.

Note: Since we do not know how built-in functions like `min(...)` or imported functions like `add(...)` are implemented, we do not draw a new frame when we call them, since we would not be able to fill it out accurately.

### Q8: Call Diagram

Let’s put it all together! Draw an environment diagram for the following code. You may not have to use all of the blanks provided to you.

``````def double(x):
return x * 2

hmmm = double
wow = double(3)
hmmm(wow)``````
Objects
Global frame
f1: [parent=]
 Return value
f2: [parent=]
 Return value
Solution

### Q9: Nested Calls Diagrams

Draw the environment diagram that results from executing the code below. You may not need to use all of the frames and blanks provided to you.

``````def f(x):
return x

def g(x, y):
if x(y):
return not y
return y

x = 3
x = g(f, x)
f = g(f, 0)``````
Objects
Global frame
f1: [parent=]
 Return value
f2: [parent=]
 Return value
f3: [parent=]
 Return value
f4: [parent=]
 Return value
Solution

# Exam prep

We recommending reading sections 1.1-1.5 from the textbook for these problems.

### Q10: Unique Digits

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

Hint: You may find it helpful to first define a function `has_digit(n, k)`, which determines whether a number `n` has digit `k`.

Run in 61A Code
Solution
``````def unique_digits(n):
"""Return the number of unique digits in positive integer n

>>> unique_digits(8675309) # All are unique
7
>>> unique_digits(1313131) # 1 and 3
2
>>> unique_digits(13173131) # 1, 3, and 7
3
>>> unique_digits(10000) # 0 and 1
2
>>> unique_digits(101) # 0 and 1
2
>>> unique_digits(10) # 0 and 1
2
"""
unique = 0
while n > 0:
last, n = n % 10, n // 10
if not has_digit(n, last):
unique += 1
return unique

# unique = 0
# i = 0
# while i < 10:
#     if has_digit(n, i):
#         unique += 1
#     i += 1
# return unique

def has_digit(n, k):
while n > 0:
last, n = n % 10, n // 10
if last == k:
return True
return False``````

We have provided two solutions:

• In one solution, we look at the current digit, and check if the rest of the number contains that digit or not. We only say it's unique if the digit doesn't exist in the rest. We do this for every digit.
• In the other, we loop through the numbers 0-9 and just call `has_digit` on each one. If it returns true then we know the entire number contains that digit and we can one to our unique count.

Video walkthrough: https://youtu.be/3rOVJZn5x3Y

### Q11: Run, K, Run

An increasing run of an integer is a sequence of consecutive digits in which each digit is larger than the last. For example, the number 123444345 has four increasing runs: 1234, 4, 4 and 345. Each run can be indexed from the end of the number, starting with index 0. In the previous example, the 0th run is 345, the first run is 4, the second run is 4 and the third run is 1234.

Implement `get_k_run_starter`, which takes in integers n and k and returns the 0th digit of the kth increasing run within n. The 0th digit is the leftmost number in the run. You may assume that there are at least k+1 increasing runs in n.

Run in 61A Code
Solution
``````def get_k_run_starter(n, k):
"""
>>> get_k_run_starter(123444345, 0) # example from description
3
>>> get_k_run_starter(123444345, 1)
4
>>> get_k_run_starter(123444345, 2)
4
>>> get_k_run_starter(123444345, 3)
1
>>> get_k_run_starter(123412341234, 1)
1
>>> get_k_run_starter(1234234534564567, 0)
4
>>> get_k_run_starter(1234234534564567, 1)
3
>>> get_k_run_starter(1234234534564567, 2)
2
"""
i = 0
final = None
while i <= k:        while n > 10 and (n % 10 > (n // 10) % 10):            n = n // 10        final = n % 10        i = i + 1        n = n // 10    return final``````

### Q12: Environment Diagrams - Challenge

These questions were originally developed by Albert Wu and are included here for extra practice. We recommend checking your work in PythonTutor after filling in the diagrams for the code below.

#### Challenge 1

Draw the environment diagram that results from executing the code below.

Guiding Notes:

• Pay special attention to the names of the frames!
``````def funny(joke):
hoax = joke + 1
return funny(hoax)

hoax = joke - 1
return hoax + hoax

Objects
Global frame
f1: [parent=]
 Return value
f2: [parent=]
 Return value
f3: [parent=]
 Return value
Solution

#### Challenge 2

Draw the environment diagram that results from executing the code below.

``````def double(x):
return double(x + x)

first = double

def double(y):
return y + y

result = first(10)``````
Objects
Global frame
f1: [parent=]
 Return value
f2: [parent=]
 Return value
f3: [parent=]
 Return value
Solution