Learn How to Think with Karel the Robot. Chapter 13. Lists

Chapter 13
Lists

In this chapter you will learn:

  • What lists are and why they are useful.
  • How to create empty and nonempty lists.
  • How to append values to a list.
  • How to measure the length of a list.
  • How to access list items via their indices.
  • How to parse lists via the for loop.
  • How to check if a given item is in a list.
  • How to remove and return ("pop") items from a list.
  • How to add lists and multiply them with integers.
  • How to delete items from a list.

As usual, first we will cover the necessary theory and then we will show you some cool applications of lists at the end of this chapter.

13.1. What are lists and why they are useful

You already know how to create and use numerical, text string and even Boolean variables. Variables are like containers - every variable can store one value. In contrast to this, a list is like a cargo train which can store many different values.


PIC

Figure 13.1: *

A list is like a cargo train.


The values in a list are ordered, so one knows which one is the first and which one is the last. They can have different types - a list may contain numerical values, text strings, Booleans, and even other lists. Items can be dynamically added and/or removed at runtime as needed.

Lists are Karel’s (and Python’s) most powerful data structure. The implementation of lists in Karel is compatible with Python, although Karel does not provide all the list functionality offered by Python.

13.2. Creating empty and nonempty lists

Throughout this chapter, you will see that there are strong similarities between lists and text strings. To begin with, an empty text string txt is created via txt = ” or txt = ~~. It is also possible to create a nonempty text string such as msg = ’Hi there!’.

An empty list is created using a pair of empty square brackets:

1L = []

Do not use parentheses () or curly braces {} as they have a different meaning. You can also create a non-empty list:

1S = [2, 3, 5]

A list can contain text strings,

1W = [Monday, Tuesday, Wednesday, Thursday, Friday]

Boolean values,

1B = [True, False, False, True, False, True]

and the types of values in a list can even be mixed:

1M = [1, 2, Emily, Jocob, True, False]

picture

13.3. Appending items to a list

Items can be appended to the end of a (empty or nonempty) list using the list method append:

1L = [] 
2print(~L =~, L) 
3L.append(5) 
4print(~L =~, L) 
5L.append(10) 
6print(~L =~, L)

Output:


PIC


Lists are perfect for storing several values at once. Like today, when Karel needs to remember the positions of all the orchids:


PIC


He can do it as follows:

1X = [] 
2while not home 
3  if orchid 
4    X.append(gpsx) 
5  go 
6print(~Orchids are in columns:~, X)

Output:


PIC


picture

13.4. Measuring the length of a list

From Section 9.5 (page 763) you know that len(txt) returns the length of the text string txt. Similarly, when working with lists, calling len(L) will return the length of the list L. The length of a list means the number of its items. For illustration, let’s change the last line of the previous program, and display the length of the list X:

1X = [] 
2while not home 
3  if orchid 
4    X.append(gpsx) 
5  go 
6print(~I found~, len(X), ~orchids.~)

Output:


PIC


13.5. Accessing list items via their indices

You already know from Section 9.8 (page 772) how to access individual characters in a text string using their indices. For example, txt[0] is the first character in the text string txt, txt[1] is the second character, etc. Also, txt[-1] is the last character of the text string, txt[-2] is the second from the end, and so on.

When working with lists, it is possible to access individual list items exactly in the same way. For example, X[0] is the first item of the list XX[1] is its second item, X[-1] is its last item, etc.

Today, Karel is still counting orchids:


PIC


But now he wants to know the position of the first orchid, and the position of the last one before his home square:

1X = [] 
2while not home 
3  if orchid 
4    X.append(gpsx) 
5  go 
6print(~The first orchid was found in column:~, X[0]) 
7print(~The last orchid was found in column: ~, X[-1])

Output:


PIC


picture

13.6. Creating a list of lists

Karel is still in the jungle counting orchids. But now, there can be multiple of them per grid square:


PIC


He needs to not only remember their positions, but also their numbers. This naturally leads to a list of pairs of the form "position, number". In fact, each of these pairs can be a two-item list, and these lists can be stored in a list. Hence one obtains a list of lists. Here is the code from Section 13.3 (page 1101), updated for the current situation:

1# Count orchids in grid square: 
2def count 
3  n = 0 
4  while orchid # collect and count them 
5    get 
6    inc(n) 
7  while not empty # put them back 
8    put 
9  return n 
10 
11# Main program: 
12X = [] 
13while not home 
14  if orchid 
15    o = count 
16    X.append([gpsx, o]) 
17  go 
18print(~List of [position, number] pairs:~) 
19print(X)

Output:


PIC


picture

13.7. Parsing lists with the for loop

Let’s stay with the previous example for another moment:


PIC


The text output was too compact, and it would be good to make it nicer. It should say something like "I found 2 orchids in column 3, 1 orchid in column 5, ..." etc.

You already know from Section 9.6 (page 766) how to parse text strings one character at a time. Lists can be parsed one item at a time exactly in the same way. For example, with the list X from the previous example, the code

1for x in X 
2  print(x)

will display


PIC


This is still not very nice, but we are getting closer. Each item x in the list X is a two-item list containing a position-number pair. Therefore we know that x[0] is the position and x[1] the corresponding number. Therefore, a nicer output can be arranged as follows:

1print(~I found:~) 
2for x in X 
3  print(x[1], ~orchids in column~, x[0])

This will display


PIC


Although there is a minor English imperfection, this is way better than before. If we wanted to improve line 3, we would have to include one extra condition:

1print(~I found:~) 
2for x in X 
3  if x[1] == 1 
4    print(x[1], ~orchid in column~, x[0]) 
5  else 
6    print(x[1], ~orchids in column~, x[0])

Final output:


PIC


13.8. Checking if an item is in a list

You already know from Section 9.12 (page 809) that Karel can check for the presence of a substring in a text string using the keyword in. The same keyword can be used to check whether an item is present in a list. For illustration, the list X we created in Section 13.3 (page 1101) provides information about the column positions of orchids:


PIC


Karel can now use the list to ask whether there is an orchid in column number 5:

1col = 5 
2if col in X 
3  print(~There is an orchid in column number~, col) 
4else 
5  print(~There is no orchid in column number~, col)

Output:


PIC


Or, he can ask whether there is an orchid in column number 10:

1col = 10 
2if col in X 
3  print(~There is an orchid in column number~, col) 
4else 
5  print(~There is no orchid in column number~, col)

Output:


PIC


The list of two-item lists X that we created in Section 13.6 (page 1119) provides information about positions of orchids and their numbers:


PIC


Karel can use it to ask whether there are two orchids in column number 7:

1col = 7 
2n = 2 
3if [col, n] in X 
4  print(~There are~, n, ~orchids in column number~, col) 
5else 
6  print(~There arent~, n, ~orchids in column number~, col)

Output:


PIC


13.9. Removing and returning ("popping") items from a list

At the beginning of this chapter we said that lists can easily be modified at runtime, but so far we only showed you how to append new items at the end. Karel (and Python) provide the list method pop which will remove and return items from a list. Let’s look at a sample list names = [’Ann’, ’Brett’, ’Charles’, ’Dave’, ’Emily’, ’Frank’].

Calling names.pop() will remove and return the last item, ’Frank’:

1names = [Ann, Brett, Charles, Dave, Emily, Frank] 
2print(~Before:~, names) 
3print(~Popping~, names.pop()) 
4print(~After:~, names)

Output:


PIC


The method pop can also be called with the index of a specific item we want to remove and return. For example, calling names.pop(0) will remove and return the item ’Ann’ from the list:

1names = [Ann, Brett, Charles, Dave, Emily] 
2print(~Before:~, names) 
3print(~Popping~, names.pop(0)) 
4print(~After:~, names)

Output:


PIC


And as a last example, calling names.pop(-2) will remove and return the second item from the end which is ’Dave’:

1names = [Brett, Charles, Dave, Emily] 
2print(~Before:~, names) 
3print(~Popping~, names.pop(-2)) 
4print(~After:~, names)

Output:


PIC


picture

13.10. Adding lists

From Section 9.3 (page 754) you know that text strings can be added just as numbers. Lists can be added in the same way:

1names = [Brett, Charles, Dave, Emily] 
2new_names = [Fred, Gillian, Harry] 
3print(names + new_names)

Output:


PIC


And one can even use the += operator to extend a list with another one:

1names = [Brett, Charles, Dave, Emily] 
2new_names = [Fred, Gillian, Harry] 
3names += new_names 
4print(names)

Output:


PIC


13.11. Multiplying lists with integers

The analogy between lists and text strings goes further. In Section 9.4 (page 760) you have seen that a text string can be multiplied with a positive integer N, which will copy and paste its contents N times. The same can be done with lists:

1morse = [...., ..] 
2print(morse*4)

Output:


PIC


And as you would expect, the *= operator works as well:

1morse = [...., ..] 
2morse *= 4 
3print(morse)

Output:


PIC


picture

13.12. Deleting items from a list

Sometimes one just needs to delete an item from a list (and destroy it) because there is no use for it. This can be done using the keyword del. Typing del L[i] will delete and destroy the item with index i from the list L. Let’s illustrate this on another Morse example:

1morse = [.--, ---, .-., .-.., -..] 
2print(~Before:~, morse) 
3print(~Removing letter L.~) 
4del morse[3] 
5print(~After:~, morse)

Output:


PIC


picture

13.13. Gardener

Let’s show a task which would be difficult to solve without using a list. Karel is working in his garden. In front of him is a flower bed with tulips:


PIC

Figure 13.2: *

Karel is gardening.


The robot does not know the length of the flower bed, or the number or positions of the tulips. His task is to create an identical flower bed on the other side of the wall:


PIC


He has enough tulips in his bag to do it.

The best way to solve this task is to follow the wall until its end, and store the column positions of all the tulips in a list T. Then, on the other side of the wall, Karel will walk towards his home square. In each grid square he will check whether his gpsx coordinate is in the list T. If the value is found, he will place a tulip. Here is the corresponding code:

1T = [] # to store the column positions of the tupils 
2right 
3while wall # follow the wall to its end 
4  left 
5  go 
6  right 
7  if tulip # if theres a tulip, add gpsx to the list T 
8    T.append(gpsx) 
9go # go over to the other side of the wall 
10right 
11while not home # walk home 
12  go 
13  if gpsx in T # if the gpsx value is in T, place an orchid 
14    put

13.14. Expedition Antarctica

The following task is interesting not only because it would be very difficult to solve without using a list, but also because it involves a discussion of different ways to store data in the list.

Karel is part of an expedition to Antarctica, and his task is to find a way through ice and snow. He should record his path in such a way that later he can draw a map.


PIC

Figure 13.3: *

Karel is in Antarctica.


Clearly, the robot can use the First Maze Algorithm to pass through the maze. He will need to store the information about his path in a list (say P). But this can be done in many different ways.

Option #1: For every step he makes, Karel can add 0 to the list P. When he needs to turn right, he can add True. When he needs to turn left, he can add False.

Option #2: At every turn Karel can add to the list P a triplet [gpsx, gpsy, R] where R is True if the path goes to the right and False otherwise.

Option #3: Karel can count his steps and store their number in a variable N. At every turn he can add to the list P a pair [N, R] where R is True if the path goes to the right and False otherwise. He would reset N back to 0 after every turn.

Let’s evaluate these three options: The sample path shown above involves 77 steps and 20 turns. So, option #1 would produce a list of length 77 + 20 = 97. Option #2 would add three values at every turn, hence the resulting list would have length 3 20 = 60. And finally, option #3 would add two values at every turn, yielding a list of length 2 20 = 40. Since option #3 is most memory-efficient, we will implement it.

The following program will do it. Make sure to read the comments in the code:

1P = [] # to store path information 
2N = 0  # counter of steps 
3while not home 
4  go 
5  inc(N)  # increase counter of steps 
6  if wall # First Maze Algorithm 
7    right 
8    if wall 
9      left 
10      left 
11      P.append([N, False]) # path goes left 
12    else 
13      P.append([N, True])  # path goes right 
14    N = 0 # reset counter of steps 
15print(P)

Output:


PIC


Awesome - first part done! The second part of the task is to use this list to draw a map of the path. The program is very simple. Karel will draw the path by placing beepers he has in his bag:

1# Path information: 
2P = [[2, True], [2, True], [1, False], [2, False], [3, False], [4, True], [6, True], [2, True], [4, False], [2, False], [4, True], [6, True], [2, True], [4, False], [7, False], [2, False], [5, True], [2, True], [5, False], [2, False], [10, True]] 
3 
4# Draw the path by placing beepers! 
5for p in P        # pass through all pairs in P 
6  repeat p[0]     # make p[0] steps forward 
7    put           # place a beeper before each step 
8    go 
9  if p[1]         # if p[1] is True, turn right 
10    right 
11  else            # otherwise turn left 
12    left

Let’s start from a clean sheet:


PIC

Figure 13.4: *

Karel is ready to draw the path.


picture

And here is Karel’s drawing after the program finishes:


PIC


13.15. Copycat

Karel’s next task is to copy a random pattern from the left box and paste it in the box on the right:


PIC


Hence the robot needs to visit all grid squares in the left box, learn where the pumpkins are, then visit all grid squares in the box on the right again, and place pumpkins at the corresponding positions.

Rather than writing a complicated code for the robot to visit all grid squares in the first box, let’s use the method from the previous section. Here is a path through the first box, stored in a list named H:

1# Path to visit all grid squares in the box: 
2H = [[7, True], [6, True], [1, True], [5, False], [1, False], [5, True], [1, True], [5, False], [1, False], [5, True], [1, True], [5, False], [1, False], [5, True], [1, False]]

We will use this list and the previous program to visit all grid squares in the left box, and then also in the box on the right. This time we will use a Boolean list B to store the pattern. Initially, this list will be empty. After each step, Karel will append to it True if he found a pumpkin, and False if he did not. In the box on the right, the list B will be used to place pumpkins at the corresponding positions. Here is the complete code:

1# Path to visit all grid squares in the box: 
2H = [[7, True], [6, True], [1, True], [5, False], [1, False], [5, True], [1, True], [5, False], [1, False], [5, True], [1, True], [5, False], [1, False], [5, True], [1, False]] 
3 
4# Go through the box on the left: 
5B = []          # create an empty Boolean list 
6for p in H      # pass through all pairs in the list H 
7  repeat p[0]   # make p[0] steps forward 
8    go 
9    B.append(pumpkin) # if pumpkin, append True, else append False 
10  if p[1]       # if p[1] is True, turn right 
11    right 
12  else          # otherwise turn left 
13    left 
14 
15# Move to the second box: 
16go 
17go 
18left 
19 
20# Go through the box on the right: 
21for p in H      # pass through all pairs in the list H 
22  repeat p[0]   # make p[0] steps forward 
23    go 
24    if B.pop(0) # get the first item from the list B 
25      put 
26  if p[1]       # if p[1] is True, turn right 
27    right 
28  else          # otherwise turn left 
29    left

When the program finishes, Karel has reproduced the pattern from the left box:


PIC


To make sure that the program works for other patterns as well, let’s try at least one more:


PIC


And here is the corresponding output:


PIC


13.16. Review questions

Friendly reminder - for every question either none, one, or several answers may be correct.

QUESTION 13.1. Check all true statements about variables and lists!

A
Variables can store numerical values, lists cannot.
B
Lists can store Boolean values, variables cannot.
C
A variable can only store a single value.
D
A list can store multiple values.

QUESTION 13.2. How can one create a list named L containing the letters ’A’, ’B’ and ’C’?

A
L = (’A’, ’B’, ’C’)
B
L = [’A’, ’B’, ’C’]
C
L = {’A’, ’B’, ’C’}
D
L = ~’A’ ’B’ ’C’~

QUESTION 13.3. How can the value of a variable v be appended to a list V ?

A
V.append(v)
B
V.add(v)
C
V.pop(v)
D
V += v

QUESTION 13.4. How can one measure the length of a list X ?

A
length(X)
B
length X
C
len(X)
D
len X

QUESTION 13.5. In the list [6, 4, 8, 9, 2, 3], what is the index of the value 2 ?

A
4
B
5
C
-1
D
-2

QUESTION 13.6. In the list [[1, 2], [3, 4], [5, 6]], what is the index of the value 5 ?

A
[3][1]
B
[3][0]
C
[2][0]
D
[2][1]

QUESTION 13.7. There is a list L = [2, 3, 5, 7, 11, 13, 17, 19]. What will the list become after executing n = L.pop(5) ?

A
[2, 3, 7, 11, 13, 17, 19]
B
[2, 3, 5, 7, 11, 17, 19]
C
[2, 3, 5, 7, 11, 13, 19]
D
[13, 17, 19]

QUESTION 13.8. There are lists L1 = [1, 1, 1] and L2 = [2, 2, 2]. What will be the result of L1 + L2 ?

A
[3, 3, 3]
B
[1, 1, 1, [2, 2, 2]]
C
[1, 1, 1, 2, 2, 2]
D
An error message

QUESTION 13.9. There is a list C = [’a’, ’b’, ’c’, ’d’]. What will be the result of C*2 ?

A
[’aa’, ’bb’, ’cc’, ’dd’]
B
[’a’, ’b’, ’c’, ’d’, ’a’, ’b’, ’c’, ’d’]
C
[’a’, ’a’, ’b’, ’b’, ’c’, ’c’, ’d’, ’d’]
D
An error message


Table of Contents

Created on September 27, 2018 in Karel.
Add Comment
0 Comment(s)

Your Comment

By posting your comment, you agree to the privacy policy and terms of service.