Learn How to Think with Karel the Robot. Chapter 5. Conditional Loop

Chapter 5
Conditional Loop

In this chapter you will learn:

  • What the conditional (while) loop is.
  • The conceptual difference between the conditional and counting loops.
  • How to pass through unknown mazes using the First Maze Algorithm.

5.1. Conditional loop and the keyword while

The concept of conditional loop is present in all procedural programming languages. Conditional loops allow us to repeat one or more commands without knowing in advance how many repetitions will be needed. picture

In the Karel language as well as in most other procedural programming languages, the conditional loop is defined using the keyword while.

5.2. The difference between the conditional and counting loops

Imagine that the robot knows that the home square lies 7 steps ahead:


PIC

Figure 5.1: *

The distance between Karel and his home square is 7 steps.


Then he can use the repeat loop to get there:

Program 5.1: Make 7 steps to your home square!
1repeat 7 
2  go

However, what if he only knows that the home square lies ahead, but not how far?


PIC

PIC

PIC

Figure 5.2: *
Number of repetitions is not known in advance.


Then the conditional loop while combined with the condition nothome is the right way to bring the robot safely home:

Program 5.2: Walk until you reach the home square!
1while not home 
2  go

Notice that the keyword while is followed by a condition (in this case nothome). The body of the loop (line 2) is indented. It will be repeated while this condition is satisfied.

5.3. Step by step

Let’s step through the last program to understand exactly what it does! For simplicity, assume that the initial distance between Karel and his home square is three steps (but the robot does not know that):


PIC

Figure 5.3: *

Karel’s position before the program starts.


Initially, the robot is not at his home square. Therefore the condition nothome is satisfied, and the body of the loop is executed for the first time. Karel makes one step forward:


PIC

Figure 5.4: *

Karel’s position before the second cycle.


Before the second cycle, the condition is checked again. Since Karel is not home yet, nothome is satisfied, and the robot makes a second step forward:


PIC

Figure 5.5: *

Karel’s position before the third cycle.


Before the third cycle, the condition is checked again. Since Karel is not at his home square, not home is satisfied, and the robot makes a third step forward:


PIC

Figure 5.6: *

Karel’s position before the fourth cycle.


Before the fourth cycle, the while loop checks the nothome condition again. This time, however, Karel is home and therefore the condition is not satisfied. Hence the fourth cycle is not done and the loop ends. picture

5.4. Climbing a pyramid

In the previous section, the while loop was combined with the condition nothome. This ensured that the body of the loop was repeated as long as the robot was not home. Naturally, all other conditions that you know from Chapter 4 can be used as well. Let’s begin with the condition wall ("is there a wall in front of you?").

Karel’s next task is to climb a pyramid of unknown height:


PIC

Figure 5.7: *

Karel is in front of a pyramid of unknown height.


This task is perfect for the while loop because Karel just needs to keep climbing, one step at a time, while there is wall in front of him. The repeating pattern to climb one step and get ready in front of the next one is formed by four commands:

left  
go  
right  
go

picture

When these four commands are used as the body of a while loop, one obtains the final program:

Program 5.3: Keep climbing until you reach the top!
1while wall 
2  left 
3  go 
4  right 
5  go

When the robot reaches the top, there is no longer a wall in front of him, therefore the condition wall is not satisfied, and the while loop ends:


PIC

Figure 5.8: *

After the program finishes.


To check that our program works for a pyramid of any size, let’s run it with a pyramid of height 3:


PIC

Figure 5.9: *

Testing the program on a pyramid of height 3.


And indeed, the robot stops on the top of the pyramid!


PIC

Figure 5.10: *

The program still works correctly.


5.5. Narrow escape

Let’s have a look at a while loop combined with the condition fire ("is there a fire in front of you?"). The only way for Karel to get to his home square is through a narrow gap between the flames. The length of the fire wall and the position of the gap are unknown.


PIC

Figure 5.11: *

Karel needs to find the gap in the wall of fire.


Here, the repeating pattern is to move one square to the right. It is formed by three commands:

right  
go  
left

When using them as the body of a while loop, and adding two more go commands after the loop finishes, one obtains the final solution program:

Program 5.4: Find the gap and enter the home square!
1while wall 
2  right 
3  go 
4  left 
5repeat 2 
6  go
picture

When the robot finds the gap in the flames, the condition fire is no longer satisfied, and the while loop ends. Then the last two lines make sure that Karel reaches the home square:


PIC

Figure 5.12: *

Karel needs to find the escape and enter his home square.


To check that the program works with an arbitrary length of the fire wall and an arbitrary position of the gap, let’s run it with one additional maze:


PIC

Figure 5.13: *

Same task with different parameters.


When the program finishes, the robot is home again:


PIC

Figure 5.14: *

The program finished successfully.


5.6. Combining the repeat and while loops

Smart combinations of the repeat and while loops can make your programs more elegant and efficient. For example, imagine that Karel’s task is to run along the perimeter of the maze and collect all keys. The maze has width 15 squares and height 12 squares. These numbers are known, therefore it seems more natural to use the repeat loop.


PIC

Figure 5.15: *

Karel is collecting keys.



Program 5.5: Collect all keys!
1repeat 2 
2  repeat 14 
3    go 
4    if key 
5      get 
6  left 
7  repeat 11 
8    go 
9    if key 
10      get 
11  left

This program is perfectly correct, but as you can see, a large part of the code is there twice, just because one time we need it inside a repeat14 loop and another time inside a repeat11 loop. This can be fixed by using the while loop which automatically takes care of the different lengths of the maze walls:

Program 5.6: Last program, improved using a while loop
1repeat 4 
2  while not wall 
3    go 
4    if key 
5      get 
6  left

This program has the same outcome as the previous one, but it is more elegant because it does not contain the same code twice. picture

5.7. First Maze Algorithm (FMA)

Today let’s teach Karel how to pass through an arbitrary maze:


PIC

PIC

PIC

PIC


This can be done using the First Maze Algorithm of robotics:


Algorithm 5.1: *
First Maze Algorithm
1:  While you are not home, do the following:
2:   If there is a wall in front of you, turn left.
3:   If there is still a wall, turn around.
4:   Move one step forward.


The algorithm allows a robot to pass through an arbitrary maze where

  • The path is one square wide.
  • At any time it goes either forward, to the left, or to the right (no forks, no loops, no dead ends).

It can be translated to the following code:

Program 5.7: First Maze Algorithm translated to Karel code
1while not home 
2  if wall 
3    left 
4    if wall 
5      right 
6      right 
7  go

Let’s see what the program does! First, what happens when Karel can just go straight?


PIC

Figure 5.17: *

There is no wall in front of Karel.


In this case there is no wall in front of the robot, so the condition on line 2 is not satisfied. Therefore he skips lines 2 - 6, and just makes one step forward on line 7.

Second, what happens when the path goes to the left?


PIC

Figure 5.18: *

Path goes to the left.


In this case there is a wall in front of the robot. Therefore the condition on line 2 is satisfied. So, he makes a left turn. Then he checks for wall again on line 4, but there is no wall in front of him. Therefore he skips lines 5 and 6, and goes to line 7. In summary, he turns left and makes one step forward.

Third, what happens when the path goes to the right?


PIC

Figure 5.19: *

Path goes to the right.


Now there is a wall in front of the robot, so he condition on line 2 is satisfied and Karel turns left. On line 4 he checks for a wall again. Since there is a wall, he executes lines 5 and 6, and makes a complete 180-degree turn. Then he makes one step forward on line 7. In summary, Karel turns right and makes one step forward. picture

5.8. Three possible failures of the FMA

In the previous section you have learned that the FMA assumes that

  • The path is one square wide.
  • At any time it goes either forward, to the left, or to the right (no forks, no loops, no dead ends).

But what if some of these assumptions are not satisfied?

First, let’s see what happens when Karel gets into a dead end:


PIC

Figure 5.20: *

Karel reached a dead end.


Since there is a wall in front of him, the condition on line 2 is satisfied, and he turns left. Then there is a wall in front of him again, therefore the condition on line 4 is satisfied, and he makes a 180-degree turn. But he faces a wall for a third time, and so the go command on line 7 will crash the program.

Next, why are loops in the path prohibited? Let’s see:


PIC

Figure 5.21: *

The path forms a loop.


In this case Karel first turns left, and then he starts circling through the loop infinitely. He never gets out of this maze!

Last, the FMA requires that the path be one square wide. To explain why, let’s look at a maze where the path is wider:


PIC

Figure 5.22: *

The path is more than one square wide.


In this case, the robot fails to collect the key because he does not visit all squares in the maze.

5.9. Right-handed version of the FMA

With Program 5.7, when the robot arrives at a T-intersection, he first turns left and chooses the left path. Therefore the algorithm is sometimes called "left-handed". Alternatively, we can first make him turn right, then check for a wall, and if there is a wall, turn around. This will be the "right-handed" version:

Program 5.8: Right-handed version of the FMA
1while not home 
2  if wall 
3    right 
4    if wall 
5      left 
6      left 
7  go

The two versions are fully equivalent when the assumptions on the maze are satisfied:

  • The path is one square wide.
  • At any time it goes either forward, to the left, or to the right (no forks, no loops, no dead ends).

But when some of these assumptions are not satisfied, then the two versions may yield different results. For example, consider a maze with a dead end in it:


PIC

Figure 5.23: *

The path contains a dead end.


Here the right-handed version of FMA succeeds while the left-handed version fails because the robot gets into the dead end. Of course, if the dead end was on the right, then the outcome would be reversed. So, it would be wrong to say that one of the versions is better than the other. picture

5.10. Other types of mazes the FMA can handle

Based on the images of mazes shown so far, you might have the impression that all the walls must be at least one square wide. This is not the case! The FMA can also handle mazes with thin walls such as the following one:


PIC

Figure 5.24: *

A maze with thin walls.


Here is the FMA again, step through it in your mind to make sure it will work!

Program 5.9: First Maze Algorithm
1while not home 
2  if wall 
3    left 
4    if wall 
5      right 
6      right 
7  go

5.11. Improving Program 4.9 "Finding North"

As promised in Chapter 4, let’s revisit some programs we wrote there, and show that they can be improved using the while loop. We can start with Program 4.9 from page 320 which turns Karel to face North no matter which direction he is facing initially:

1repeat 3 
2  if north 
3    pass 
4  else 
5    left

Using the while loop, the same can be achieved using just two lines:

1while not north 
2  left

5.12. Improving Program 4.12 "Emptying bag"

Program 4.12 from page 342 makes Karel remove all objects from his bag and place them on the ground. Importantly, because it uses the repeat loop, it needs to make an unnatural assumption that Karel has at most 10 objects in his bag:

1repeat 10 
2  if not empty 
3    put

Using the while loop, one can forget the limiting assumption, and just write

1while not empty 
2  put

5.13. Improving Program 4.17 "Danger"

Program 4.17 from page 373 helps Karel locate his home square within a wall of fire, water and acid. Again, because it uses the repeat loop, it needs to make an assumption on the maximum length of the wall:

1repeat 10 
2  if fire or water or acid 
3    # Move one square to the right: 
4    right 
5    go 
6    left 
7  else 
8    # You are in front of the home square - do nothing: 
9    pass 
10# Make one final step home: 
11go

With the while loop, the wall can be arbitrarily long, and the code becomes much simpler:

1while fire or water or acid 
2  # Move one square to the right: 
3  right 
4  go 
5  left 
6# Make one final step home: 
7go

5.14. Improving Program 4.18 "Tunnel"

As a last example, Program 4.18 from page 376 helps Karel locate his home square in a tunnel. It as well uses a limiting assumption on the number of steps Karel can take:

1repeat 15 
2  if home 
3    pass 
4  else 
5    go

Once more, the version based on the while loop is much simpler and more elegant:

1while not home 
2  go

5.15. Other types of loops: do-while, until, and for

Some languages provide the do-while or until loops. These are basically the same. The (big) difference vs. the while loop is that they execute the body at least once before the condition is checked at the end. However, picture

On the other hand, Python provides a for loop which is more powerful than the same type of loop in most other programming languages. Karel has the Python for loop, and we will get to it soon!

5.16. More is coming!

In this chapter we have only shown you the basic use of the while loop. There is much more to it. In the following chapters we will introduce the Boolean values True and False, as well as Boolean expressions, variables and functions. All these will expand the possibilities of what can be done with the while loop. Therefore, keep reading!

5.17. Review questions

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

QUESTION 5.1. The while loop should be used when

A
The number of repetitions is known in advance.
B
The number of repetitions is not known in advance.
C
The repeat loop already is used elsewhere.
D
The repeat loop is broken.

QUESTION 5.2. Which of the following codes are valid?

A
while repeat not home
B
repeat while not home
C
repeat if not home
D
while not home

QUESTION 5.3. At what time is the condition checked in the while loop?

A
Before every cycle.
B
After every cycle.
C
In the middle of every cycle.
D
When the loop has finished.

QUESTION 5.4. Does the body of the while loop need to always be indented?

A
No.
B
Yes.
C
Not when it contains multiple commands.
D
Not when it contains a single command.

QUESTION 5.5. What forms of the while loop are valid?

A
while wall
B
while not wall
C
while not empty
D
while empty

QUESTION 5.6. When using the while loop, does one need to identify repeating patterns?

A
Yes.
B
No, this is only needed when using the repeat loop.
C
Yes but only when the condition does not contain not.
D
Yes but only when the condition contains not.

QUESTION 5.7. What is the First Maze Algorithm (FMA) designed for?

A
To help Karel find a treasure in the maze.
B
To help Karel pass through unknown mazes.
C
To help Karel place collectible objects in mazes.
D
To help Karel place obstacles in mazes.

QUESTION 5.8. What are the limiting assumptions on the maze for the FMA to work correctly?

A
The path should be one square wide.
B
The path should not contain forks.
C
The path should not contain loops.
D
The path should not contain dead ends.

QUESTION 5.9. How can the FMA fail when the maze contains a dead end?

A
Karel can return to where he started.
B
Karel can run in an infinite loop.
C
Karel can crash.
D
Karel can stall without moving.

QUESTION 5.10. How can the FMA fail when the maze contains forks?

A
Karel can stall without moving.
B
Karel can crash.
C
Karel can return to where he started.
D
Karel can run in an infinite loop.

QUESTION 5.11. How can the FMA fail when the path is more than one square wide?

A
Karel can return to where he started.
B
Karel may miss some squares.
C
Karel can crash.
D
Karel can stall without moving.

QUESTION 5.12. What types of loops does Karel provide?

A
repeat loop
B
until loop
C
while loop
D
do-while loop


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.