Lab 3

Note: Like the last lab, there may be more material in this lab than you can finish during the lab time. If you do not have time to finish all exercises (in particular, the programming problems at the end), you can continue working on them later. You can do this at home (if you have a computer with python set up), in the CSIT lab rooms outside teaching hours, or on one of the computers available in the university libraries or other teaching spaces.

Exercise 0: Truth values#

A truth value, or boolean value is a value that has only two possible states: True and False. You get a boolean value as a result of using a comparison operator. Both True and False are reserved words in python, and they are different to strings such as “True” and “False”.

Start up a shell, and try evaluating following expressions. Make sure you understand the results you obtain:

In [1]: 5 > 4
Out [1]: ...

In [2]: type(5 > 4)
Out [2]: ...

In [3]: "aab" > "ab"
Out [3]: ...

In [4]: type("aab" > "ab")
Out [4]: ...

In [5]: type("False")
Out [5]: ...

You can combine boolean values with boolean operators and, or and not.

In [6]: 5 > 4 and 4 > 9
Out [6]: ...

In [7]: not 4 > 9
Out [7]: ...

In [8]: True or False
Out [8]: ...

In [9]: True or True
Out [9]: ...

In [10]: type(True or False)
Out [10]: ...

Note: python allows you to write some compound boolean expressions without a boolean operator:

10 < x <= 20

means the same as

10 < x and x <= 20

The comparisons can be both strict, both non-strict, or a mixture of strict and non-strict.

Exercise 1: Programs with conditional branching#

From here on, you should switch to writing your code in a file rather than typing it into the shell.

You can use boolean values to make decisions in if statements - this is called conditional branching.

Exercise 1(a)#

The lecture slides contain the following function for determining the grade associated with a final mark:

def print_grade(mark):
    if mark >= 80:
        print("High Distinction")
    if mark >= 70:
        print("Distinction")
    if mark >= 60:
        print("Credit")
    if mark >= 50:
        print("Pass")
    else:
        print("Fail")

Copy the function to a file so that you can run it, and test it with a range of different values (keeping in mind that the mark should be a number between 0 and 100) so that you see all the possible outputs. As we saw in the lecture, this function does not perform as intended, and we saw one way to fix it, by replacing each test with a compound test expressions (for example mark < 80 and mark >= 70).

Rewrite the function so that it works correctly using only simple comparison expressions (no boolean operators), if and else statements.

Exercise 1(b)#

There is one more variant of the if statement in python: using elif. elif is an abbreviation of else if, and it allows you to write if statements in the else suite in a more compact way.

if test_expression_1:
    ...suite 1...
elif test_expression_2:
    ...suite 2...
else:
    ...suite 3...

is equivalent to writing

if test_expression_1:
    ...suite 1...
else:
    if test_expression_2:
        ...suite 2...
    else:
        ...suite 3...

However, you can write any number of elif parts into an if statement, not just one.

Rewrite the function print_grade using elif, so that it uses only simple comparison expressions (no boolean operators) and still does the right thing.

Exercise 1(c)#

The median of three numbers, a, b and c, is the one that ends up in the middle when the numbers are sorted in increasing order. For example, the median of -2, 7 and 9 is 7, and the median of 7, 9 and -2 is also 7.

Write a function median with three parameters a b and c, which returns the median of its three arguments. (Of course, the function only works if all three arguments are numbers… or does it? What happens if you call it with three strings? What happens if you call it with a mix of numbers and strings?)

Note that there are many different ways to solve this problem.

Testing your function. You can test the function with sets of small numbers (like 1,2,3); if it works for small numbers, it should work just as well for large numbers. Note that the median of three numbers is the same no matter in which order they are given to the function; that is, median(1,2,3), median(1,3,2), median(2,1,3), median(2,3,1), median(3,1,2) and median(3,2,1) should all return the same result. What happens if you call your function with two or three copies of the same value? (such as median(2,1,2) or median(1,1,1)).

Exercise 2: The robot simulator revisited#

First, if you have not done so already, download a copy of the robot.py module and save it in your working directory for this lab. Make sure that you can import the module: the python interpreter will look for it in the current working directory.

Remember that you must start by initialising the simulation:

robot.init()

(If you need more of a reminder about how to run and program the robot, revisit Lab 1.) For some of these problems, you will need to use the robot’s box sensor. The command robot.sense_color() returns the colour of the box in front of the sensor, as a string (a value of type str). It will return an empty string ('') if there is no box in front of the sensor. For more about how the box sensor works, see last week’s lecture on branching.

Programming problems#

In an early lecture, we introduced the problem of stacking boxes lined up on the shelf into a tower. Even though we could define functions that encapsulate the main steps of picking up, stacking and so on, we still needed to write different programs, with a different number of repetitions, for different numbers of boxes. (For example, here are programs for stacking 3 boxes and stacking 5 boxes.)

Write a single function, make_tower, that stacks any number of boxes that stand in a line on the shelf into a single tower.

To create problems with different sizes, you pass extra arguments to the init function, for example:
```
robot.init(width = 7, boxes = "flat")
```
The “width” is the number of spaces on the table; because the initial setup leaves one empty space between each pair of boxes (otherwise the robot would not be able to pick them up), you need a width of 2*n - 1 to make a problem with n boxes (i.e., width 5 gives you 3 boxes; width 7 gives you 4 boxes; and so on).

There are two important questions to consider in the designing an algorithm for this problem:

What is the sequence of commands that is repeated for every box added to the stack?

How do you determine when to stop? The robot’s sensor can only detect the presence of boxes; how can you tell if it has reached the end of the table?
In last week’s lecture, we developed a function for counting the number of boxes in a stack.

Following the same idea, write a function that finds the position of a box with a given colour in a stack. That is, your function should look like this:
```
def find(colour):
    ...
```
and should return the position (height above the shelf) where a box of that colour is. If there is no box of the specfied colour, the function should return a distinct value, such as -1. (We choose -1 because it can never be the position in a stack, so we can distinguish it from the case where a box has been found.)

You can use either a recursive or an iterative method (or why not try both). Note that there are two cases: either the box is found, or the robot has searched all the way through the stack.

To test your function, you need to set up simulations with a tall stack of different colours. You can do this by passing additional arguments to the init function, for example:
```
init(height = 5, boxes = [["black", "blue", "white", "red"]])
```
The height argument specifies the maximum height that the lift can go.

Exercise 3: The square root algorithm#

The Babylonian algorithm is a method of computing square roots of numbers. The method was recorded as far back as the 1st century, though the name suggests it is older than that. The algorithm can be derived as a special case of the Newton-Raphson method for solving an equation of the form f(x) = 0.

The Babylonian algorithm works as follows: We want to compute the square root of some number a. First, we take a guess: pick some number x. Then check how good is our guess, by computing the (absolute) difference abs(x² - a). If it’s close enough (for example, less than 10^-6) we’re done. Otherwise, calculate an improved guess (x + a/x) / 2; this replaces the previous value of x and we repeat from the test.

Implement a function that computes square roots using the Babylonian algorithm. From the algorithm’s description, you may already have guessed that using a while loop is a good way to go.

Testing your function. The math module provides a square root function, math.sqrt, so you can test your function by comparing its result with what math.sqrt returns. Try changing the threshold for when the answer is close enough and see what effect this has on the values returned by your function.

To get a better understanding of what is happening, you can also try adding a print call inside the loop in your function, so that you can see how the guesses are updated in each iteration. They should be converging towards the correct answer.

(You can find this example, and it’s solution, in both text books. It’s in Chapter 7 in Downey’s book, and Chapter 3 in Punch & Enbody’s book. Note that Punch & Enbody use input for console input to get test values. This is totally unnecessary - write a function instead.)

Exercise 4: Digit Sums#

The digit sum of a (positive) integer number is the sum of the digits of the number when it is written out (in base 10). For example the digit sum of 301 is 3 + 0 + 1 = 4.

Write three functions, sum_odd_digits(number), sum_even_digits(number) and sum_all_digits(number), which compute the sum of the odd digits, the even digits, and all digits, respectively, in a given number. For example,

sum_odd_digits(1282736) should return 11 (because 1 + 7 + 3 = 11)
sum_even_digits(1282736) should return 18 (because 2 + 8 + 2 + 6 = 18)
sum_all_digits(1282736) should return 29 (because 1 + 2 + 8 + 2 + 7 + 3 + 6 = 29)

Hint #1: The modulo (%) and floor division (//) operators are useful for solving this problem. For example, number % 10 will give you the least significant (“rightmost”) digit in number.

Hint #2: Think about whether you could write one or more additional functions that incorporate the common functionality from all three functions.

Search this site

Semester 1, 2022: Lab 3