# Learn How to Think with Karel the Robot. 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:

1# Back one step:
2def back
3  left
4  left
5  go
6  right
7  right

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:

1# Put a beeper in every accessible square:
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:

1# Return one step back:
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:

1# Check both branches:
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:

Program 15.1: Bubble sort
1# Number of piles:
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.

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.

Program 15.2: Reading Braille text - part 1
1# Translate one letter into numbers:
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:

Program 15.3: Reading Braille text - part 2
1# Read one letter as a string and analyze it:
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.

Program 15.4: Checking a Cardan grille - part 1
1# Create a list of the GPS coordinates of all holes. Lower left corner of grille is [0, 0]:
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.

Program 15.5: Checking a Cardan grille - part 2
1# Return True if position [i, j], rotated by 0, 90, 180 and 270 degrees, is
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:

Program 15.6: Checking a Cardan grille - part 3
1# Main program:
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:

1# Are you facing South?
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:

1# Add the GPS positions of all queens to a list:
2def sweep
3  q = []
4  while gpsx != 10 or gpsy != 2
5    go
7      q.append([gpsx, gpsy])
8    if wall
9      if north
10        right
11        go
13          q.append([gpsx, gpsy])
14        right
15      else
16        left
17        go
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:

1# Analyze the list:
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