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:


PIC

Figure 15.1: *

Karel is going to put beepers in all accessible squares.


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:


PIC

Figure 15.2: *

At the end, the maze is "flooded".


15.2. Contraband (recursion)

An ancient story has it that robbers hid gems in this maze.


PIC

Figure 15.3: *

Sample maze with an unknown number of hidden gems.


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:


PIC

Figure 15.4: *

Sample binary tree.


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:


PIC

Figure 15.5: *

Random initial sequence.


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):


PIC

Figure 15.6: *

After the 1st cycle.


In the 2nd cycle, he switches (5, 3) (3, 5), (5, 4) (4, 5), (5, 4) (4, 5) and (5, 1) (1, 5):


PIC

Figure 15.7: *

After the 2nd cycle.


In the 3rd cycle, he only switches (4, 1) (1, 4):


PIC

Figure 15.8: *

After the 3rd cycle.


In the 4th cycle, he only switches (3, 1) (1, 3):


PIC

Figure 15.9: *

After the 4th cycle.


In the 5th cycle, he only switches (2, 1) (1, 2), and he is done:


PIC

Figure 15.10: *

After the 5th cycle, the sequence is sorted.


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:


PIC

Figure 15.11: *

Reading Braille text.


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:


PIC

Figure 15.12: *

Karel’s own name in Braille.


For reference, this is the complete English alphabet in Braille:


PIC

Figure 15.13: *

All 26 English letters 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".


PIC

Figure 15.14: *

Sample Cardan grille.


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?


PIC

Figure 15.15: *

Flawed Cardan grille.


On the other hand, the following grille is designed correctly and the above problem does not occur:


PIC

Figure 15.16: *

Well-designed Cardan grille.


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.


PIC

Figure 15.17: *

Sample fenced area.


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:


PIC

Figure 15.18: *

If you face South, decrease A by gpsy+1.


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:


PIC

Figure 15.19: *

If you face North, increase A by gpsy.


If Karel faces East or West, the value of A will not change:


PIC   PIC

Figure 15.20: *

If you face East or West, do not change A.


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:


PIC


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:


PIC

Figure 15.21: *

One of 92 existing solutions.


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.


PIC

Figure 15.22: *

Queens are represented by masks.


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 
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:

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


Table of Contents

Created on September 27, 2018 in Karel.
Add Comment
1 Comment(s)
www.theequitydesk.com

 

Commented on December 19, 2018.
Add Comment

Your Comment

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