RE: Learn How to Think with Karel the Robot. Chapter 15. Advanced Applications
Chapter 15
Advanced Applications
The objective of this section is to present a few advanced applications of various techniques and algorithms which you have learned so far. We will begin with recursion.
15.1. Flood (recursion)
Karel’s first task is to "flood" the maze with beepers. This means - place a beeper in every grid square he can access. The layout of the maze is random, but there are no other obstacles besides walls, no containers, and no collectible objects. Notice that the robot is not able to access all grid squares because some areas in the maze are surrounded with walls:
This task is perfect for recursion, and in a moment we are going to show you why. But first a technicality - let’s define a new command back for Karel to back one step:
Then we can write the recursive command fill. The idea is as follows: If you stand on a beeper, the grid square was already "flooded". So do nothing and just return (this is when the recursion will stop). Otherwise (there is no beeper where you stand), place a beeper. Then, you will step one by one in the squares on your right, in front of you, and on your left, and always start a new "flood" from there. Of course you always need to check for a wall before making a step forward. Amazingly, this is it! Below is the code of the command fill:
2def fill
3 if beeper
4 return
5 else
6 put
7 right
8 repeat 3
9 if not wall
10 go
11 fill
12 back
13 left
14 right
15 right
16
17# Main program:
18fill
Before executing the program, one has to ensure that the robot has enough beepers in his bag. Since the maze has 15 columns and 12 rows, the best is to give him 12 ⋅ 15 = 180 beepers. After the program ends, the maze will look as follows:
15.2. Contraband (recursion)
An ancient story has it that robbers hid gems in this maze.
If there were any, they would be in unreachable squares. Hence, your task is to calculate the number of unreachable squares!
One way to do this, is to "flood" the maze as we did in the previous section. When the robot begins with 12 ⋅ 15 = 180 beepers in his bag, and finishes with B beepers, then there are 180 - B unreachable squares. Here is the corresponding program:
2def back
3 left
4 left
5 go
6 right
7 right
8
9# Put a beeper in every accessible square:
10def fill
11 if beeper
12 return
13 else
14 put
15 right
16 repeat 3
17 if not wall
18 go
19 fill
20 back
21 left
22 right
23 right
24
25# Main program:
26N = 180
27# Place beepers into all accessible squares:
28fill
29# How many beepers were you not able to place?
30while not empty
31 put
32U = -1
33while beeper
34 get
35 inc(U)
36print(~There are~, U, ~hidden gems in this maze!~)
15.3. Traversing binary trees (recursion)
Binary trees are an important data structure in computer science, and traversing them is one of the fundamental tasks. In Karel, binary trees can be represented by trees of apples:
Why do we use the word "binary"? The reason is that at any position in the tree, there can be at most two branches - to the left and/or to the right.
The idea of the recursive algorithm is that at each position in the tree there can be at most two branches, which themselves are binary trees. Hence, Karel first needs to check for an apple beneath him. If there is no apple, the recursion stops. Otherwise (there is an apple beneath him), he needs to check whether a tree starts in the Northwest square. If so, he needs to traverse it and return to his initial position. Then he also needs to check if a tree starts in the Northeast square. If so, he needs to traverse it and return to his initial position. Finally, Karel needs to collect the apple beneath him.
The corresponding code can be found below:
2def collect
3 go
4 left
5 go
6 right
7 if apple # check Northwest square
8 collect
9 else
10 right
11 right
12 left
13 go
14 go
15 left
16 if apple # check Northeast square
17 collect
18 else
19 left
20 left
21 right
22 go
23 left
24 go
25 if apple # check for apple at the initial position
26 get
27
28# Main program:
29go
30collect
31go
32left
33go
A short video of Karel performing this program is available at https://youtu.be/Z659mYXHWuc.
15.4. Bubble sort
Sorting algorithms constitute another important chapter of computer science. Bubble sort
is not the most sophisticated one, but it is great as a stepping stone before learning QuickSort and other more advanced sorting algorithms.
In Karel, a sequence of numbers could be represented by a list. But that would not be fun. So, let’s represent the numbers visually as piles of beepers. Of course the sequence is random. Let’s say that it contains 6 numbers:
The idea of the bubble sort algorithm is simple: Karel passes through the sequence from left to right, and whenever he sees that the next number is less than the current one, he switches them.
Of course, it is not sufficient to only do this once, because the sequence 2, 1, 1, 1 would
just become 1, 2, 1, 1 which is not sorted yet. When the sequence has N numbers, Karel
needs to make N-1 passes. Here is the corresponding program:
2n = 6
3
4# Place p objects:
5def place(p)
6 repeat p
7 put
8
9# Move back n steps:
10def back(s)
11 left
12 left
13 repeat n
14 go
15 right
16 right
17
18# Collect all beepers in the pile and return their number:
19def getall
20 c = 0
21 while beeper
22 get
23 inc(c)
24 return c
25
26# Main program:
27done = False
28dec(n)
29while not done
30 go
31 a = getall
32 done = True
33 repeat n
34 go
35 b = getall
36 back(1)
37 if a > b
38 done = False
39 place(b)
40 else
41 place(a)
42 a = b
43 go
44 while not empty
45 put
46 back(n+1)
47 dec(n)
48print(~Done!~)
In the 1st cycle, Karel switches (5, 2) → (2, 5), (6, 3) → (3, 6), (6, 4) → (4, 6) and (6, 1) → (1, 6):
In the 2nd cycle, he switches (5, 3) → (3, 5), (5, 4) → (4, 5), (5, 4) → (4, 5) and (5, 1) → (1, 5):
In the 3rd cycle, he only switches (4, 1) → (1, 4):
In the 4th cycle, he only switches (3, 1) → (1, 3):
In the 5th cycle, he only switches (2, 1) → (1, 2), and he is done:
A short video of Karel performing this program is available at https://youtu.be/b2_YzJscFuo.
15.5. Reading Braille
Braille is a system of raised dots that can be read with the fingers by people who are blind or who have low vision:
Teachers, parents, and others who are not visually impaired ordinarily read Braille with their eyes. Braille is not a language. Rather, it is a code analogous to the Morse code. Each letter is formed by 1 - 6 dots in a box of width 2 and height 3. For illustration, here is the word "Karel" in Braille:
For reference, this is the complete English alphabet in Braille:
The algorithm is straightforward: First we write a function braillenum to translate the Braille
symbols to numerical codes. To do this, we enumerate the six positions in the 2 × 3 box by 1, 2, 3
(left column, top to bottom) and by 4, 5, 6 (right column, top to bottom). Then for each Braille
letter, we will use these numbers to create a text string. For each dot, the text string will
contain the corresponding number. For example, ’a’ is ’1’, ’b’ is ’12’, ’c’ is ’14’
etc.
2def braillenum
3 s = ’’
4 go
5 if beeper
6 s += ’1’
7 go
8 if beeper
9 s += ’2’
10 go
11 if beeper
12 s += ’3’
13 left
14 go
15 left
16 if beeper
17 s6 = 1
18 else
19 s6 = 0
20 go
21 if beeper
22 s5 = 1
23 else
24 s5 = 0
25 go
26 if beeper
27 s4 = 1
28 else
29 s4 = 0
30 if s4 == 1
31 s += ’4’
32 if s5 == 1
33 s += ’5’
34 if s6 == 1
35 s += ’6’
36 repeat 2
37 go
38 right
39 return s
Then we write the resulting function braille to translate the numerical codes to English letters.
Actually this is just one long if-elif-else statement:
2def braille
3 b = braillenum
4 if b == ’1’
5 return ’a’
6 elif b == ’12’
7 return ’b’
8 elif b == ’14’
9 return ’c’
10 elif b == ’145’
11 return ’d’
12 elif b == ’15’
13 return ’e’
14 elif b == ’124’
15 return ’f’
16 elif b == ’1245’
17 return ’g’
18 elif b == ’125’
19 return ’h’
20 elif b == ’24’
21 return ’i’
22 elif b == ’245’
23 return ’j’
24 elif b == ’13’
25 return ’k’
26 elif b == ’123’
27 return ’l’
28 elif b == ’134’
29 return ’m’
30 elif b == ’1345’
31 return ’n’
32 elif b == ’135’
33 return ’o’
34 elif b == ’1234’
35 return ’p’
36 elif b == ’12345’
37 return ’q’
38 elif b == ’1235’
39 return ’r’
40 elif b == ’234’
41 return ’s’
42 elif b == ’2345’
43 return ’t’
44 elif b == ’136’
45 return ’u’
46 elif b == ’1236’
47 return ’v’
48 elif b == ’2456’
49 return ’w’
50 elif b == ’1346’
51 return ’x’
52 elif b == ’13456’
53 return ’y’
54 elif b == ’1356’
55 return ’z’
56 else
57 return ’?’
58
59# Main program:
60word = ’’
61while not home
62 word += braille
63print(word)
15.6. Cardan grille
The Cardan grille is an old encryption technique which assumes that the text is written in a square table. The size of the table corresponds to the number of letters. For example, a 5 × 5 table is enough for a 25-letter text. A table of the size 8 × 8 can be used for a text of up to 64 letters.
The grille itself is a square cloth (or paper) whose size matches the size of the table of letters. The cloth contains holes so that when laid over the text, certain letters appear. The following example shows a 6 × 6 table of letters, and a grille which when laid over the text reveals "JULESVERN".
The sender and the addressee each have a copy of the grille, and the grille never travels along with the encrypted text message.
After the addressee reads the first group of letters, s/he rotates the grille by 90 degrees and reads part 2. Then s/he rotates the grille by another 90 degrees and reads part 3. And finally, s/he rotates the grille one last time and reads part 4.
If the grille is designed well, then rotating it each time reveals a different group of letters. However, if the grille is flawed, it can happen that rotating the grille reveals a position which was already revealed before. This problem is present in the following grille (where the gold coins represent the holes). Can you find it?
On the other hand, the following grille is designed correctly and the above problem does not occur:
Karel’s task is to analyse a given 6 × 6 Cardan grille and count the flaws. A zero result means that the grille is well designed.
The algorithm is as follows: As a first step, we will write a function findholes to locate all
holes and store their GPS coordinates (relative to the bottom-left corner of the grille) in a helper
list H.
2def findholes
3 holes = []
4 repeat 6
5 repeat 6
6 go
7 if coin
8 holes.append([gpsx - 5, gpsy - 3])
9 left
10 left
11 repeat 6
12 go
13 right
14 go
15 right
16 return holes
Next, we will write a Boolean function check(i, j, L) to check whether the list L contains
the position [i, j] rotated by 90, 180 or 270 degrees.
2# (a) not found or (b) is found more than once in the list L.
3# Otherwise return 0:
4def check(i, j, L)
5 count = 0
6 if [i, j] in L
7 inc(count)
8 if [5-j, i] in L
9 inc(count)
10 if [5-i, 5-j] in L
11 inc(count)
12 if [j, 5-i] in L
13 inc(count)
14 if count == 0 or count > 1
15 return True
16 return False
And in the main program we will check all nine positions in the lower-left 3 × 3 quadrant of the
6 × 6 grille:
2H = findholes
3res = 0
4l = [0, 1, 2]
5for ipos in l
6 for jpos in l
7 f = check(ipos, jpos, H)
8 if f == 1
9 print(~Problem found at~, ipos, jpos)
10 inc(res, f)
11print(~Flaws found:~, res)
15.7. Land surveyor
Karel works as a land surveyor. Today he needs to measure the area of a fenced garden.
But he cannot enter because there is a big dog inside, and Karel is afraid of dogs. Fortunately, he
knows how this can be done without entering the garden!
Let’s demonstrate his method on a small one-square garden shown below. Karel creates a new variable A = 0 for the area and walks along the fence. After each step, he positions himself to face away from the fence. Depending whether he is facing South, East, North or West, he does the following:
Since his gpsy is 1 and A was 0, after this operation A will be -2.
Here Karel’s gpsy is 3. Adding 3 to A will change the value of A to 1:
If Karel faces East or West, the value of A will not change:
Hence Karel correctly calculated that the area A of this mini-garden is 1.
Below is the corresponding program which moreover uses the Second Maze Algorithm to walk around the garden. Karel stores his initial GPS coordinates so that he knows where to stop:
2def south
3 left
4 left
5 s = north
6 right
7 right
8 return s
9
10# Remember GPS coordinates:
11x = gpsx
12y = gpsy
13# Variable A for the area:
14A = 0
15# Make the first step:
16while wall
17 if north
18 dec(A, gpsy)
19 if south
20 inc(A, gpsy)
21 dec(A)
22 right
23go
24# Walk around fence:
25while (x != gpsx) or (y != gpsy)
26 left
27 while wall
28 if north
29 dec(A, gpsy)
30 if south
31 inc(A, gpsy)
32 dec(A)
33 right
34 go
35# Print the result:
36print(~Area =~, A)
For the K-shaped garden shown at the beginning of this section, Karel obtains:
15.8. The Eight Queens puzzle
This is a classical puzzle whose objective is to place eight queens on the chess board so that they do not threaten each other. Recall that the queen is the most powerful figure on the chess board - she dominates the column, the row, and both diagonals from where she stands. In other words, no two queens can stand in the same row, in the same column, or on the same diagonal. Below is a sample solution:
The queens will be represented by masks. Karel’s task is to analyse the positions of the eight queens and determine whether or not some of them threaten each other.
The task will be solved in two steps. First, the function sweep will be used to go through the entire chess board, locate all queens, and store their GPS coordinates in a list:
2def sweep
3 q = []
4 while gpsx != 10 or gpsy != 2
5 go
6 if mask
7 q.append([gpsx, gpsy])
8 if wall
9 if north
10 right
11 go
12 if mask
13 q.append([gpsx, gpsy])
14 right
15 else
16 left
17 go
18 if mask
19 q.append([gpsx, gpsy])
20 left
21 return q
In the next step, this list will be analysed. If Karel finds two pairs of coordinates which have the same X component and a different Y component, then he knows he found two queens in the same column. If he finds two pairs of coordinates which have the same Y component and a different X component, then he knows that he found two queens in the same row.
How can he check the diagonals? Notice that positions on the same diagonal, such as [1, 6], [2, 5], [3, 4], 4, 3, [5, 2], [6, 1] satisfy that the sum of the X and Y coordinates is constant (in this case 7). This is true for all diagonals which go from from Northwest to Southeast, just the constants differ. For the remaining diagonals which go from from Southwest to Northeast, such as [4, 1], [5, 2], [6, 3], [7, 4] etc. it holds that the difference Y - X is constant (in this case -3). Again the constant differs from one diagonal to another.
In the function analyze below, Karel considers all 8 rows, all 8 columns, and all NW-SE and SW-NE diagonals. In each case he is looking into the list L to see whether two (or more) queens are there, threatening each other:
2def analyze(L)
3 # We will go through the list once, counting queens in every column, row, and diagonal:
4 cols = [0, 0, 0, 0, 0, 0, 0, 0]
5 rows = [0, 0, 0, 0, 0, 0, 0, 0]
6 dia1 = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
7 dia2 = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
8 for pos in L
9 posx = pos[0] - 3
10 posy = pos[1] - 2
11 cols[posx] += 1
12 rows[posy] += 1
13 dia1[posx + posy] += 1
14 dia2[posy - posx + 7] += 1
15 print(cols)
16 print(rows)
17 print(dia1)
18 print(dia2)
19 # Check if there is more than one queen in some column, row, or diagonal:
20 success = True
21 for x in cols
22 if x == 0
23 print(~No queen found in column~, x)
24 success = False
25 if x > 1
26 print(~More than one queen found in column~, x)
27 success = False
28 for y in rows
29 if y == 0
30 print(~No queen found in row~, y)
31 success = False
32 if y > 1
33 print(~More than one queen found in row~, y)
34 success = False
35 for n in dia1
36 if n > 1
37 print(~More than one queen found on a NW-SE diagonal.~)
38 success = False
39 for n in dia2
40 if n > 1
41 print(~More than one queen found on a SW-NE diagonal.~)
42 success = False
43 return success
44
45# Main program:
46Q = sweep
47ok = analyze(Q)
48if ok
49 print(~No threats found.~)
50else
51 print(~Threats found!~)
52go
Table of Contents
- About
- 1. Introduction
- 2. Basic Commands
- 3. Counting Loop
- 4. Conditions
- 5. Conditional Loop
- 6. Custom Commands
- 7. Variables
- 8. Functions
- 9. Text Strings
- 10. Testing Your Programs
- 11. Boolean Values, Variables, Expressions, and Functions
- 12. Randomness and Probability
- 13. Lists
- 14. Recursion
- 15. Advanced Applications
- Appendix A. Karel App in NCLab
- Appendix B. Self-Paced Karel Course in NCLab
