# Learn How to Think with Karel the Robot. Chapter 12. Randomness and Probability

## Chapter 12

Randomness and Probability

In this chapter you will learn:

- Why is randomness useful in computing.
- How to generate random integers using the function randint.
- How to use the function randint to simulate rolling dice.
- How to calculate the minimum and maximum of a given set of numbers.
- How to generate random Booleans using the function rand.
- How to use the function rand to simulate coin toss.
- How to calculate simple probabilities.
- How to use randomness to solve difficult tasks.

### 12.1. Why is randomness useful in computing

Random numbers are used for many applications starting with gambling and creating unpredictable results in computer games. But one of the major applications of randomness is in cryptography. Cryptography is used to secure data for safe transfer via Internet, to secure data storage, and other tasks. Creating a reliable data encryption requires numbers that nobody can guess. Think about it - if a deterministic (non-random) algorithm was used to encrypt your data, then at least the author of the algorithm would always be able to break it, read your emails, enter into your bank account, or steal your identity.

Randomness is also very important for scientific and engineering simulations. For example, imagine that an engineer computes the strength of a bridge. He or she knows that all the physical properties of the underlying materials such as the quality of the concrete and of the steel come with some amount of uncertainty. Therefore, many computations with varying parameters must be done to ensure that this uncertainty is taken into account. These methods are called Monte Carlo Methods.

### 12.2. Generating random integers

Karel can generate random integers using the function randint which was already mentioned in Section 11.12 (page 973). In summary, calling randint(m, n) returns a random integer between m and n (including m and n). Calling the function with just one argument as in randint(n) is the same as calling randint(1, n). Let’s see some examples.

First, let’s use a repeat loop to generate and display 10 random integers between -1 and 1:

Output:

The following program generates 10 random integers between 1 and 100:

Output:

### 12.3. Karel is rolling a die

When rolling a die, one obtains a random integer between 1 and 6. The same can be done by calling randint(1, 6) or just randint(6). Today, Karel is curious how many attempts it will take him to throw a six. Here is the corresponding program:

2die = -1

3while die != 6

4 die = randint(6)

5 print(die)

6 inc(n)

7print(~Attempts needed:~, n)

Output:

Wow, that was quick! Beginner’s luck, probably. Let’s try this one more time!

### 12.4. Placing objects at random locations

Karel stands in the Southwest corner of the maze, facing East:

He carries one light bulb in his backpack, and his task is to place it at a random location in the maze. The maze is 15 squares wide and 12 squares tall. Here is a program which will do it:

2y = randint(0, 11) # number of steps to make in the North direction

3repeat x

4 go

5left

6repeat y

7 go

8put

Let’s execute the program two times. Keep in mind that the light bulb will not be visible because it will be beneath Karel at the end:

### 12.5. Building a random skyline

Today, Karel has 60 light bulbs in his bag, and his task is to use them to build a skyline.

The skyline will consists of 10 columns of bulbs of random heights between one and six, such as this one:

This is the corresponding program:

2 # Generate a random integer between 1 and 6:

3 n = randint(1, 6)

4 # Build one column:

5 left

6 repeat n

7 put

8 go

9 # Turn around:

10 right

11 right

12 # Return back to the bottom:

13 while not wall

14 go

15 # Get ready for the next column:

16 left

17 go

Let’s execute the program once more to show that the robot will create a different skyline:

### 12.6. Calculating the maximum

One important task in computer science is to calculate the maximum of a given sequence of values. Let’s take a look at a sample sequence 3, 4, 2.

As the first step, create a new variable named (for example) maximum, and initialize it with some value which is less than the lowest value in the sequence:

If you do not know how to safely choose a value which is below all values in the sequence, it is possible to take any value from the sequence. Usually it is easiest to take the first one:

We will take, for example, the initial value maximum = 0. Here is the algorithm:

Step 1:

- The current value of maximum is 0.
- Take the next value in the sequence: m = 3
- Is m greater than maximum? (m is 3, maximum is 0)
- Yes, therefore m is the new maximum: maximum = m
- After this step, the value of maximum is at 3.

Step 2:

- The current value of maximum is 3.
- Take the next value in the sequence: m = 4
- Is m greater than maximum? (m is 4, maximum is 3)
- Yes, therefore m is the new maximum: maximum = m
- After this step, the value of maximum is at 4.

Step 3:

- The current value of maximum is 4.
- Take the next value in the sequence: m = 2
- Is m greater than maximum? (m is 2, maximum is 4)
- No, therefore maximum stays unchanged.
- After this step, the value of maximum is at 4.

There are as many steps as there are values in the sequence. Now let’s apply this algorithm to measure the height of a random skyline!

### 12.7. Measuring the height of a skyline

Karel’s next task is to measure the height of a random skyline which is formed by 10 columns of light bulbs. The height of the skyline is the height of the tallest column.

To solve this task, the robot will employ the algorithm from the previous section. We will initialize maximum with 0, and measure the height m of each column. If m > maximum, he will update maximum to m. Otherwise he will leave maximum unchanged. Here is the corresponding program, enhanced with control prints to reveal in more detail what is happening:

2maximum = 0

3# Loop over all columns:

4repeat 10

5 # Measure the height of the next column:

6 m = 0

7 left

8 while bulb

9 inc(m)

10 go

11 # Turn around:

12 right

13 right

14 # Return back to the bottom:

15 while not wall

16 go

17 # Get ready for the next column:

18 left

19 go

20 # If m > maximum, update maximum to m:

21 if m > maximum

22 print(m, ~>~, maximum, ~therefore updating maximum to~, m)

23 maximum = m

24 else

25 print(m, ~<=~, maximum, ~therefore maximum not updated~)

26# Display maximum at the end:

27print(~Height of the skyline is~, maximum)

For the skyline shown above, the program will produce the following output:

### 12.8. Measuring the height of a building

Today Karel needs to measure the height of an unknown building. The building is formed by columns of crates.

This task is different from the previous one because Karel cannot go inside the building (crates are obstacles). Instead, he will use the Second Maze Algorithm (right-handed version) to climb on the crates. He will initialize maximum with 0. After each step along the crates he will measure his gpsy coordinate m. Note that gpsy is the height of the column below Karel. If m is greater than maximum, then he will update maximum with m. This is the corresponding program:

2# Use the Second Maze Algorithm:

3while not home

4 right

5 while wall or crate

6 left

7 go

8 m = gpsy

9 if m > maximum

10 print(m, ~>~, maximum, ~therefore updating maximum to~, m)

11 maximum = m

12 else

13 print(m, ~<=~, maximum, ~therefore maximum not updated~)

14print(~Height of the building is~, maximum)

And here is the output:

### 12.9. Calculating the minimum

Calculating the minimum of a sequence of numbers is another important task in computer science. In Section 12.6 (page 1016) you learned how to calculate the maximum. Calculating the minimum is almost the same, with two differences:

- The initial value of minimum must be greater to or equal than any value in the sequence. Alternatively, one can take the first value of the sequence.
- The value of minimum will be updated if the new value m is less than minimum.

Let us illustrate the algorithm on a sample sequence 7, 9, 5. We will initialize the value of minimum
with 10:

Step 1:

- The current value of minimum is 10.
- Take the next value in the sequence: m = 7
- Is m less than minimum? (m is 7, minimum is 10)
- Yes, therefore m is the new minimum: minimum = m
- After this step, the value of minimum is at 7.

Step 2:

- The current value of minimum is 7.
- Take the next value in the sequence: m = 9
- Is m less than minimum? (m is 9, minimum is 7)
- No, therefore minimum stays unchanged.
- After this step, the value of minimum is at 7.

Step 3:

- The current value of minimum is 7.
- Take the next value in the sequence: m = 5
- Is m less than minimum? (m is 5, minimum is 7)
- Yes, therefore m is the new minimum: minimum = m
- After this step, the value of minimum is at 5.

There will be as many steps as there are values in the sequence. Now let’s apply this algorithm to measure the clearance of an unknown cave!

### 12.10. Measuring the clearance of a cave

Today, Karel is exploring a cave. In order to know whether all his equipment will pass through it, he wants to first measure the clearance (minimum height between the floor and the ceiling).

He will use the algorithm from the previous section. Since the maximum height of the maze is 12 grid squares, a good initial value for minimum is 12:

2while not home

3 # Measure the height of the current column:

4 m = 1

5 left

6 while not wall

7 inc(m)

8 go

9 # Turn around

10 right

11 right

12 # Get back down:

13 while not wall

14 go

15 # Get ready for the next column:

16 left

17 go

18 # Update the minimum if M < minimum:

19 if m < minimum

20 print(m, ~<~, minimum, ~therefore updating minimum to~, m)

21 minimum = m

22 else

23 print(m, ~>=~, minimum, ~therefore minimum not updated~)

24print(~Clearance of the cave is~, minimum)

Output:

### 12.11. Generating random Booleans

Karel has a function rand which returns either True or False with a 50 % probability. In other words, there is the same chance of returning True or False.

For illustration, let’s call the function rand 10 times and display the result:

Output:

### 12.12. Karel is tossing a coin

Calling the function rand is the same as tossing a coin. Today Karel does not know whether he should go to cinema or read a book. The following program which simulates a coin toss will help him decide:

2if heads

3 print(~I got heads, so I will go to the cinema.~)

4else

5 print(~I got tails, so I will read a book.~)

Output:

So, Karel decided to go to the cinema today!

### 12.13. Calculating probabilities

This is easy. Probability is just the number of favorable outcomes divided by the number of all possible outcomes. Let’s return to the coin toss for a moment.

What is the probability of getting heads? The number of favorable outcomes is 1, the number of
all possible outcomes is 2. Therefore, the probability of getting heads is 1/2 which is 0.5. It is
possible to report probabilities in percent, by multiplying the result by 100. Hence, the
probability of getting heads is 50 %.

Now let’s say that we toss the coin twice.

What is the probability of getting heads both times? Well, there are four possible outcomes:
Getting heads in the first toss and the second, getting heads in the first toss and tails in the
second, getting tails in the first toss and heads in the second, and getting tails both times. But
only 1 outcome is favorable - that’s the first one (heads and heads). Therefore, the probability of
getting heads in both cases is 1 / 4 = 0.25, or 25 %.

Next, what is the probability of getting a 6 on a die? There is 1 favorable outcome:

The number of all possible outcomes is 6:

Therefore, the probability of getting a six is 1/6 which is approximately 0.17 or 17
%.

As a last example, let’s roll the dice two times. What is the probability of the sum of the points being at most three? Well, that’s easy. There are 36 possible outcomes: 1 in the first roll and 1 in the second, 1 in the first roll and 2 in the second, ..., 1 in the first roll and 6 in the second. That’s six. Then 2 in the first roll and 1 in the second, 2 in the first roll and 2 in the second, ..., 2 in the first roll and 6 in the second. That’s another six. There are four more sets of six, for getting 3, 4, 5, 6 in the first roll. Hence 6 times 6 is 36.

What is the number of favorable outcomes? Well, the sum can never be 1 because in each roll the minimum is 1. So the minimum score is 1 + 1 = 2. The score of three can only be obtained as 1 + 2 or 2 + 1. Hence, there are 3 favorable outcomes. In summary, the probablity of getting a score of at most three in a double roll is 3 / 36 = 1 / 12. This is approximately 0.08 or 8 %.

### 12.14. Probability of events vs. their frequency

The probability of an event only is an approximate indicator for the frequency of that event. For example, the probability of getting heads when tossing a coin is 50 %. But this does not mean that one gets heads exactly one time when tossing the coin twice. Let’s get Karel’s help to explain this in more detail.

Today, Karel has many ribbons in his bag and he wants to split them into two parts. He will be tossing a coin to do that. When he gets heads (True), he will place a ribbon on the left. When he gets tails (False), he will place a ribbon on the right.

He will use the following program, starting with 20 ribbons:

2 if rand

3 left

4 go

5 go

6 put

7 right

8 right

9 go

10 go

11 left

12 else

13 right

14 go

15 go

16 put

17 left

18 left

19 go

20 go

21 right

Will he get 10 on the left and 10 on the right?

And here is the result - 12 ribbons on the left and 8 on the right!

Let’s do this again, now with 100 ribbons (the number of repetitions on line 1 will be changed to 100). When the program finishes, there are 44 ribbons on the left and 56 on the right:

And one last time, let’s do the same with 500 ribbons. The result is - 238 ribbons on the left and 262 on the right:

You can observe one very interesting thing here. If the exact half is the perfect outcome, then the first time the result was 2 ribbons off (12 instead of 10), the second time the result was 6 ribbons off (44 instead of 50), and the last time the result was 12 ribbons off (238 instead of 250). That number seems to be growing. But to be fair, one has to make it proportional to the number of events - which means to divide it by the number of coin tosses. Hence, in the first case we obtain 2 / 20 = 0.1, in the second case 6 / 100 = 0.06, and in the third case 12 / 500 = 0.024.

This number is the relative discrepancy between the frequency of the event and its predicted probability. As you can see, the value steadily decreases from 0.1 to 0.06 to 0.024. In other words, the relative frequency of the event is getting closer to its predicted probability. In mathematics, this is called the Law of Large Numbers (LLN). If you are interested, you can find more about it on Wikipedia.

### 12.15. Karel and random walks

The Boolean function rand allows us to do very interesting things. Such as - we can let Karel make random walks in the maze! What does it mean? Instead of just letting him make one step forward, we can let him make the step forward with probability 50 %. The other 50 % we can split between turning left and turning right. In other words, he will turn left with probability 25 % or right with probability 25 %. This is the corresponding program (the number of steps can be changed as needed):

2 if rand # go straight with probability 50%

3 if not wall

4 go

5 else # the else branch is executed with probability 50%

6 if rand # turn left with probability 25%

7 left

8 else # turn right with probability 25%

9 right

As you can see, we also added a check for a wall on line 3 - without it, the robot would crash into a wall in no time. Here is the maze where we will try this program out:

And here you can see where Karel went when the program was executed:

Notice a few "dead ends". They occur when Karel turns twice in a row and goes back.

### 12.16. Using randomness to solve difficult tasks

Some tasks are very difficult to solve using deterministic (non-random) algorithms.

This maze is not suitable for the maze algorithms we know. The First Maze Algorithm fails to find the rugs (green line) and so does the Second Maze Algorithm (red line).

Both these algorithms actually get into an infinite loop. One possible solution is to let Karel walk randomly in the maze until he finds the rugs. Well, for simplicity, let us have him stop after he finds the first one. Here is the corresponding program:

2 if rand # go straight with probability 50%

3 if not wall

4 go

5 else # the else branch is executed with probability 50%

6 if rand # turn left with probability 25%

7 left

8 else # turn right with probability 25%

9 right

10 if rug # if you find a rug, collect it

11 get

This works. Use the Karel App in NCLab to re-create the maze, and try it yourself!

### 12.17. Review questions

QUESTION 12.1. Which of the following areas of computing benefit from randomness?

- A
- logic
- B
- cryptography
- C
- game design
- D
- scientific computing

QUESTION 12.2. What function in Karel is used to generate random integers?

- A
- random
- B
- rint
- C
- randomint
- D
- randint

QUESTION 12.3. What is the equivalent of rolling a die?

- A
- randint(1, 6)
- B
- randint(0, 6)
- C
- randint(1, 7)
- D
- randint

QUESTION 12.5. If maximum is the current value of the maximum, and the next value is m, what condition is used to update maximum?

- A
- if m > maximum
- B
- if m < maximum

QUESTION 12.7. If minimum is the current value of the minimum, and the next value is m, what condition is used to update minimum?

- A
- if m > minimum
- B
- if m < minimum

QUESTION 12.8. When tossing a coin, what is the probability of getting heads?

- A
- 50 %
- B
- 0.5
- C
- 5.0
- D
- 100 %

QUESTION 12.9. When tossing a coin two times, what is the probability of getting heads both times?

- A
- 50 %
- B
- 25 %
- C
- 0.5
- D
- 0.25

QUESTION 12.11. When rolling a die, what is the probability of getting an even number?

- A
- 1/2
- B
- 1/6
- C
- 1/3
- D
- 0

QUESTION 12.12. When rolling a die two times, what is the probability of getting a combined score of 2?

- A
- 0
- B
- 1/2
- C
- 1/18
- D
- 1/36

QUESTION 12.13. A favorable event has probability 50%, and we do 10 experiments. How many times will the favorable event occur?

- A
- 5 times
- B
- 4 times
- C
- 6 times
- D
- This is impossible to say.

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