Lab: a number-guessing game

Time for a game. The computer has picked a secret whole number between 1 and 100. You guess, and it tells you whether your guess is too low, too high or correct. First you’ll play it yourself. Then you’ll write programs that play it for you, and you’ll discover a strategy so good it never needs more than seven guesses.

This lab uses everything from the section: comparisons, if/elif/else, while, for, range, break and careful tracing.

How the computer picks

The page has already run a hidden setup cell. It picked the secret number with Python’s random module and created a helper called check that compares a guess with the secret. You don’t need to understand how check is built yet; you’ll learn to write your own helpers like it in the section on functions. Here’s the one thing to know:

• check(guess) gives back the text "too low", "too high" or "correct".

The secret is chosen with a fixed seed, a starting number for the random generator, so it is the same every time the page loads. That makes the lab repeatable, which is exactly what you want when testing a program. No peeking!

Step 1: play by hand

Real games would ask you to type a guess. Here, you change the variable and run the cell again. Start with 50. Keep a count of your guesses.

guess = 50
result = check(guess)
print(guess, "is", result)

Keep going until you see correct. How many guesses did it take? Most people use a strategy without thinking about it. What was yours?

Step 2: react to the answer

A game needs to respond differently to each answer: a perfect job for if/elif/else. Notice we compare the result to strings, so the spelling must match exactly.

guess = 75
result = check(guess)
if result == "correct":
    print("You got it!")
elif result == "too low":
    print("Higher!")
else:
    print("Lower!")

Step 3: the brute-force player

Now let Python play. The simplest strategy is brute force: try 1, then 2, then 3, and so on until one is correct. A for loop over range(1, 101) tries them all; break stops at the answer. Predict roughly how many guesses it will need, then run it.

guesses = 0
for guess in range(1, 101):
    guesses += 1
    if check(guess) == "correct":
        print("Brute force found it:", guess)
        break
print("Guesses used:", guesses)

Brute force always works, but it’s slow when the secret is big. If the secret were 100, it would take 100 guesses. It also ignores the most useful information the game gives you: too low and too high.

Step 4: the halving player

Here’s the clever strategy. Keep track of the lowest and highest numbers the secret could still be. Always guess the middle. If the guess is too low, the secret must be above it, so move low up. If it’s too high, move high down. Each guess throws away half of the remaining possibilities.

low = 1
high = 100
guesses = 0
while True:
    guess = (low + high) // 2
    guesses += 1
    result = check(guess)
    print(f"Guess {guesses}: {guess} is {result}  (range was {low} to {high})")
    if result == "correct":
        break
    elif result == "too low":
        low = guess + 1
    else:
        high = guess - 1
print("Halving needed", guesses, "guesses")

Read the output line by line: watch the range shrink, roughly halving every time. (low + high) // 2 uses whole-number division so the guess is always a whole number. And look at guess + 1: since the guess was too low, the guess itself is ruled out too. Using low = guess instead would still work most of the time, but it’s exactly the kind of off-by-one slip that occasionally gets stuck. Try tracing it when low is 15 and high is 16.

Step 5: why seven guesses is enough

Each guess cuts the possibilities roughly in half: 100, then 50, then 25, 13, 7, 4, 2, 1. After seven halvings, only one number can be left. You can make Python count the halvings for you with a while loop:

possible = 100
halvings = 0
while possible > 1:
    possible = possible // 2
    halvings += 1
print("Halvings to get down to one:", halvings)

That loop says 6, but the game needs up to 7 guesses: each guess also removes the guessed number itself, and sometimes the last guess is needed just to say the answer. Now change possible to 1,000,000. Brute force could need a million guesses; halving needs about twenty. This idea, called binary search, is one of the most important algorithms in computing, and you’ll meet it again in the last section of this course.

Step 6: test it properly

One game isn’t a test. To try other secrets, add a cell that overrides the secret for testing:

_secret = 99
low, high, guesses = 1, 100, 0
while True:
    guess = (low + high) // 2
    guesses += 1
    result = check(guess)
    if result == "correct":
        break
    elif result == "too low":
        low = guess + 1
    else:
        high = guess - 1
print("Secret", _secret, "found in", guesses, "guesses")

The line low, high, guesses = 1, 100, 0 sets three variables at once; it’s the same as three separate assignments. Try secrets of 1, 50, 64 and 100. Does halving ever need more than 7?

Your turn

Write the halving player yourself for a different secret, using a while loop. The checker tests that you found the secret and used no more than seven guesses.

import random
secret = random.Random(7).randint(1, 100)


def check(guess):
    if guess < secret:
        return "too low"
    elif guess > secret:
        return "too high"
    return "correct"


# ---- your code below: don't print or use secret directly! ----
low = 1
high = 100
guesses = 0
found = None

Section quiz

Ten questions covering the whole section. Each answer comes with an explanation.