Lab 4
Note: Some of the content of this lab depends on material that we will only cover on Monday’s lecture. Please make it a priority to attend or listen to the lecture prior to attempting the lab questions.
Note 2: There may be more exercises 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), 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.
Objectives#
The purpose of this week’s lab is to:
- understand the indexing of (1-dimensional) sequence types, such as lists and strings;
- write functions using loops (
for
andwhile
) to solve problems that require iterating through sequences; - investigate some of the functions available for doing things with different sequence types.
The string type#
We have already seen a number of times that all values in python
have a type, such as int
, float
, str
, etc.
To determine the type of a value we can use the function
type(_some expression_)
.
The type of a value (“object”) determines what we can do with it:
For example, we can do arithmetic on numbers, and we can ask for
the length of a string (using the len
function), but we cannot
ask for the length of a number, or do much arithmetic with strings.
Some operations can be done on several value types, but have
different effects for different types. For example, using the
+
operator on two strings concatenates them: thus,
"1.234" + "1.234"
evaluates to "1.2341.234"
, whereas adding
two floating-point numbers 1.234 + 1.234
evaluates to 2.468
.
Exercise 0#
You should begin the lab by working in a python shell
Run the following in the python shell:
In [1]: string1 = "1.234"
In [2]: print(string1)
...
In [3]: type(string1)
Out [4]: ...
In [5]: string2 = string1 + string1
In [6]: print(string2)
...
In [7]: len(string1)
Out [7]: ...
In [8]: len(string2)
Out [8]: ...
In [9]: float1 = float(string1)
In [10]: type(float1)
Out [10]: ...
In [11]: float1 + float1
Out [11]: ...
Writing string literals#
Recall that a literal is an expression that represents a constant
value - like a 1
represents the integer one, or "abc"
represents
the three-letter string abc. String literals in python are written by
enclosing them in either single, double or triple quotation marks:
In [1]: str1 = 'a few words'
In [2]: str2 = "a few words"
In [3]: str3 = '''a few words'''
In [4]: str1 == str2
Out [4]: ...
In [5]: str2 == str3
Out [5]: ...
In [6]: type(str1)
Out [6]: ...
(Note that the triple quote is written by typing three single quotes.) There is no difference between single- and double-quoted strings. The triple quote has the special ability that it can stretch over several lines:
In [1]: many_line_string = '''This is line 1.
This is the second line.
And this is line three.'''
In [2]: many_line_string
Out [2]: ...
In [3]: print(many_line_string)
...
Note the difference between how many_line_string
is displayed when you
evaluate the expression and when you print it. What is the '\n'
character?
Remember that a string enclosed in one type of quotation marks can not contain the same type of quotation marks (unless they are escaped - see the lecture slides on strings), but can contain the other types. (If you happen to like video tutorials better than lecture slides, here are two elementary ones on strings: http://www.youtube.com/watch?v=jECazLigEH8 and http://www.youtube.com/watch?v=yjRkEX4OTyc. The second one also looks at some string methods, which show up a little later in this lab.)
Exercise 1#
Write string literals for each of the following sentences:
- The possessive form of ‘it’ is ‘its’
- “it’s” is an abbreviation of “it is”. - A ‘’’ is three ‘ but two ‘ do not make a “.
Note that the first sentence should be on two lines.
Use the print
function to verify that your strings are displayed
correctly. Try writing them both with and without using triple quotes.
Character encoding#
A string is a sequence (ordered collection) of characters.
Characters (like every other type of information stored in a computer) are represented by numbers. Interpreting a number as a character requires an encoding; python 3 uses the unicode standard for encoding characters in strings.
Python provides the ord
and chr
functions for translating
between numbers and the characters they represent:
ord(a_character)
returns the corresponding character
code (as an int
) while chr(an_integer)
returns the
character that the integer represents.
Try the following:
In [1]: ord('a')
Out [1]: ...
In [2]: ord('A')
Out [2]: ...
In [3]: chr(91)
Out [3]: ...
In [4]: chr(92)
Out [4]: ...
In [5]: chr(93)
Out [5]: ...
In [6]: chr(21475)+chr(20986)
Out [6]: ...
In [7]: chr(5798) + chr(5794) + chr(5809) + chr(5835) + chr(5840) + chr(5830) + chr(5825) + chr(5823)
Out [7]: ...
Remember that characters outside the ASCII range (unicode numbers above 255) may not display properly, if the computer you are using does not have a font for showing those characters. Also, many of the characters below number 32 are so called “non-printable” control characters, which may not be displayed.
Introduction to Lists#
Like strings, lists are another sequence type that exists in python.
However, where each of the elements in a string has to be a character,
the elements of a list can be of any type, str
, int
, bool
, etc.,
even other lists.
For today’s lab we will largely only consider lists where every element is a number, and we will return to lists again after the break to examine them in more detail.
There are several ways to create lists. For each of the following, write a small piece of python code to create that list. Try finding at least two different ways of making each of the lists.
-
Create a list containing 100 elements that all have the same value, e.g. all are 1. Try to find three different approaches. Discuss your three alternatives with your neighbour - did you find the same three, or different ones?
-
Create a list of 100 integers whose value is the same as their index (position in the list) plus 1, that is,
mylist[0] == 1
,mylist[1] == 2
,mylist[2] == 3
, etc.
Just like strings, the list data type has several methods that can be
helpful in solving these problems.
For example, read help(list.append)
, help(list.insert)
and
help(list.extend)
to see the documentation of some of the methods
that modify lists.
List comprehension (optional)#
Python has a mechanism for writing compact expressions that create lists, called list comprehension. The general form of a comprehension is
[ element_exp for varname in iterable_exp ]
iterable_exp
should be an expression that evaluates
to an iterable type (for example, a sequence), and the comprehension
creates a list whose elements are the result of evaluating
element_exp
for each element in the iterable
value. The variable varname
is assigned each value
from the iterable in turn, and can be used in the
element_exp
.
For example,
[ 2 ** k for k in [0, 1, 2, 3, 4] ]
will create the list with elements 2 ** 0
, 2 ** 1
, etc, up to
2 ** 4
, i.e, the list [ 1, 2, 4, 8, 16 ]
and
[ ord(char) for char in "Hello!" ]
will create a list whose elements are the numbers corresponding to the
encoding of the characters in the string "Hello!"
.
You can find out more about them in Section “List comprehensions” of Chapter 19 in Downey’s book, or Section 7.10 in Punch & Enbody’s book.
Try writing expressions to generate the lists in the exercise above using comprehensions.
Indexing sequences#
Every element in a sequence has an index (position). The first element
is at index 0. The length of a sequence is the number of elements in
the sequence. The index of the last element is the length minus one.
The built-in function len
returns the length of any sequence.
Indexing a sequence selects a single element from the sequence (for
example, a character if the sequence is a string).
Python also allows indexing sequences from the end, using negative
indices. That is, -1
also refers to the last element in the sequence,
and -len(seq)
refers to the first.
Exercise 2(a)#
Run the following examples. For each expression, try to work out what the output will be before you evaluate the expression.
In [1]: my_string = "as if on"
In [2]: my_string[1]
Out [2]: ...
In [3]: my_string[4]
Out [3]: ...
In [4]: my_string[-1]
Out [4]: ...
In [5]: L = len(my_string)
In [6]: my_string[L - 1]
Out [6]: ...
In [7]: my_string[1 - L]
Out [7]: ...
Exercise 2(b)#
The statement
In [1]: my_list = [1, 2, 3, 4, 5, 6, 7, 8]
assigns the variable my_list
a list of the integers 1,2,…,8.
(Thus, the length of this list is the same as the length of the string
used in the previous exercise.) Try the indexing expressions from the
previous exercise on my_list
instead of my_string
. They should all
work. Is the result of all expressions what you expect?
Iteration over sequences#
Python has two kinds of loop statements: the while
loop, which
repeatedly executes a suite as long as a condition is true, and the
for
loop, which executes a suite once for every element of a
sequence. (To be precise, the for
loop works not only on sequences
but on any type that is iterable. All sequences are iterable, but
later in the course we will see examples of types that are iterable
but not sequences.)
Both kinds of loop can be used to iterate over a sequence.
Which one is most appropriate to implement some function depends on
what the function needs to do with the sequence.
The for
loop is simpler to use, but only allows you to look at one
element at a time. The while
loop is more complex to use (you must
initialise and update an index variable, and specify the loop condition
correctly) but allows you greater flexibility; for example, you can
skip elements in the sequence (increment the index by more than one)
or look at elements in more than one position in each iteration.
The syntax and execution of while
and for
loops is described in
the lectures, and in the text books (Downey: Sections “The while
Statement” in Chapter 7 and “Traversal with a for loop” in Chapter 8;
Punch & Enbody: Sections 2.1.4, and 2.2.10 to 2.2.13).
Exercise 3(a)#
From here onwards you should switch from working in the shell, to working in files.
The following function takes one argument, a list
, and counts the
number of elements in the list that are negative. It is implemented
using a while
loop.
def count_negative(input_list):
count = 0
index = 0
while index < len(input_list):
if input_list[index] < 0:
count = count + 1
index = index + 1
return count
Rewrite this function so that it uses a for
loop instead.
To test your function, you can use the following inputs - note that while we use list comprehensions to quickly create lists to ‘test’ our functions, you are not required to be familiar with list comprehensions for the mid-semester exam:
[i for i in range(-2, 2)]
(2 negative numbers)[i for i in range(2, -3, -1)]
(2 negative numbers)[i for i in range(-3, 2)]
(3 negative numbers)[math.sin(2 * math.pi * i / 50) for i in range(50)]
(25 negative numbers)[0 for i in range(10)]]
(0 negative numbers)
You can create more test cases by making variations of these, or using other list-creating functions.
Exercise 3(b)#
Write a function called is_increasing
that takes an array (of numbers)
and returns True
if and only if the elements in the array are in (non-strict)
increasing order. This means that every element is less than or equal
to the next one after it.
For example,
- for
[1, 5, 9]
the function should returnTrue
- for
[3, 3, 4]
the function should returnTrue
- for
[3, 4, 2]
the function should returnFalse
Is it best to use a for
loop or a while
loop for this problem?
Test your function with the examples above, and with the examples you used for exercise 3(a).
Also test your function on an empty list (that is, a list with
no elements). An empty list can be created with the expression
[]
or list()
. Does your function work? Does it work on a list
with one element?
Try calling your function with a string argument (for example,
"a B c D"
). Does it work? Does it return a correct answer?
(Remember that character comparison is based on the corresponding
unicode number: a < B
is the same as ord('a') < ord('B')
.)
Slicing#
Python’s built-in sequence types (which include type str
) provide
a mechanism, called slicing, to select parts of a sequence (that is,
substrings if the sequence happens to be a string).
It is done using the notation sequence[start:end]
.
There is also an extended form of slicing, which takes three arguments,
written sequence[start:end:step]
.
(Punch & Enbody’s book has a detailed description of slicing, including its extended form, in Section 4.1.5 (page 183). Downey’s book discusses slicing in Section “String Slices” in Chapter 8; the extended form of slicing is only briefly mentioned in Exercise 8-3.)
Exercise 4(a)#
For these exercises 4(a), 4(b) and String Methods, switch back to writing your code in the shell.
To make sure you understand what the arguments in a slicing expression mean, run through the following examples. For each expression, try to work out what the output will be before you evaluate the expression.
In [1]: my_string = "Angry Public Swamp Methods"
In [2]: L = len(my_string)
In [3]: my_string[1:L]
Out [3]: ...
In [4]: my_string[0:L - 1]
Out [4]: ...
In [5]: my_string[0:L:2]
Out [5]: ...
In [6]: my_string[L:0:-1]
Out [6]: ...
In [7]: my_string[6:6+6]
Out [7]: ...
In [8]: my_string[11:11-6:-1]
Out [8]: ...
In [9]: my_string[2*L]
Out [9]: ...
In [10]: my_string[0:2*L]
Out [10]: ...
(“Angry Public Swamp Methods” - Why such a strange, non-sense string?
It’s designed to make it easier for you to see what happens when you
try different slicing expressions. Can you see what’s special about
it? Hint: Remember from the previous exercise that ord('S')
is not
equal to ord('s')
- ‘S’ and ‘s’ are different characters.)
Exercise 4(b)#
As in Exercise 2(b) above, use the statement
In [1]: my_list = [i for i in range(1, 27)]
to assign my_list
an array of integers of the same length as
the string used in the previous exercise, and try the slicing
expressions on my_list
instead of my_string
.
Is the result of all expressions what you expect?
String methods#
A “method” is the same thing as a function, but it uses a slightly different call syntax. A method is always called on a particular object (value). A method call,
object.method(...)
can be thought of as “on this object, perform that method”.
For now, we will just explore some of the rich set of methods that python provides for performing operations on built-in data types, such as strings. You can find the documentation of pythons string methods at http://docs.python.org/3/library/stdtypes.html#text-sequence-type-str, or by using the built-in help function in the python shell.
Try the following:
In [1]: sentence = "the COMP1730 lectures are boring, but the labs are great"
In [2]: sentence.capitalize()
Out [2]: ...
In [3]: sentence.swapcase()
Out [3]: ...
In [4]: sentence.count("e")
Out [4]: ...
In [5]: sentence.find("lectures")
Out [5]: ...
In [6]: sentence.find("exciting")
Out [6]: ...
In [7]: sentence.split(" ")
Out [7]: ...
In [8]: sentence.upper().find("LECTURES")
Out [8]: ...
In [9]: sentence.find("LECTURES").upper()
Out [9]: ...
In [10]: sentence.swapcase # Note the lack of `(` and `)`
Out [10]: ...
After each method call, try print(sentence)
. Which of the methods
modify the string? Why?
Exercise 5#
For the remainder of the lab, you should switch back to writing your code in files.
There are five string methods that modify case: capitalize
,
title
, swapcase
, upper
and lower
.
-
Look up each of these methods in the python on-line documentation or using the built-in
help
function. (Note: To find the documentation of a string method using help, you must prefix the method name withstr.
; that is, usehelp(str.capitalize)
instead ofhelp(capitalize)
.) -
Based on your understanding, can you predict what will be the effect of each of these methods on the following strings:
s1 = "turner" s2 = "north lyneham" s3 = "AINSLIE" s4 = "NewActon"?
To check if your understanding is correct, write python code to perform the operation, run it and see.
(From Punch & Enbody, Chapter 4: Question 14, on page 221.)
Programming problems#
Note: These are more substantial programming problems. We do not expect that everyone will finish them within the lab time. If you do not have time to finish them during the lab, you should continue working on them later (at home, in the CSIT labs after teaching hours, or on one of the computers available in the university libraries or other teaching spaces).
Closest matches#
(a) Write two functions, smallest_greater(seq, value)
and
greatest_smaller(seq, value)
, that take as argument a sequence
and a value, and find the smallest element in the sequence that
is greater than the given value, and the greatest element in the
sequence that is smaller than the given value, respectively.
For example, if the sequence is “qazrfvujm” and the target value is ‘h’, the smallest greater element is ‘j’ and the greatest smaller element is ‘f’.
- You can assume that all elements in the sequence are of the same type as the target value (that is, if the sequence is a string, then the target value is a letter; if the sequence is a list of numbers, then the target value is a number).
- You can not assume that the elements of the sequence are in any particular order.
- You should not assume that the sequence is of any particular type; it could be, for example, a list, a string, or some other sequence type. Use only operations on the sequence that are valid for all sequence types.
- What happens in your functions if the target value is smaller or greater than all elements in the sequence?
(b) Same as above, but assume the elements in the sequence are sorted in increasing order; can you find an algorithm that is more efficient in this case?
Counting duplicates#
If the same value appears more than once in a sequence, we say that
all copies of it except the first are duplicates. For example, in
[-1, 2, 4, 2, 0, 4]
, the second 2 and second 4 are duplicates;
in the string “Immaterium”, the ‘m’ is duplicated twice (but the ‘i’
is not a duplicate, because ‘I’ and ‘i’ are different characters).
Write a function count_duplicates(seq)
that takes as argument a
sequence and returns the number of duplicate elements (for example,
it should return 2 for both the sequences above). Your function
should work on any sequence type (for example, both lists and
strings), so use only operations that are common to all sequence
types. For the purpose of deciding if an element is a duplicate,
use standard equality, that is, the ==
operator.