With binary search, you don’t have to be a mind reader to beat this simple coding activity.
“What number am I thinking of?” your friend asks. Maybe he or she has only one stick of gum left, and the person with the closest guess gets to eat it. Or maybe everyone is bored and “what number am I thinking of” is the most interesting game available. Now, you can play this game any time, any place — because we’re going to program it on a computer in Python.
Python is a simple, flexible programming language with minimal syntax. In other words, you don’t have to worry about forgetting brackets and semi-colons. Instead, Python uses indents to decide which lines of code to execute. An indent is created using either 1 tab or 4 spaces. But don’t mix the two methods!
1) Navigate to www.repl.it
2) Select ‘Python3’ from the language box (not Python; Python3)
3) Write the following code in the left-hand editor:
import random num_to_guess = random.randint(1, 100) tries = 7 while tries > 0: guess = int(input('Guess a number between 1 and 100\n')) tries -= 1 if guess == num_to_guess: print('Congratulations! YOU WIN!!\n') quit() elif guess > num_to_guess: print('Too high. Try again.\n') else guess < num_to_guess: print('Too low. Try again.\n') print('The number to guess was ' + str(num_to_guess)) print('YOU LOSE!\n')
- You used double quotes (“) at the beginning and end of each string
- The double quotes are all inside the brackets
- The while loop statement (line 5) ends with a colon (:)
- The if, elif, and else statements all end with a colon (:)
- Each opening bracket has a closing bracket (double check lines 6 and 16, where you have a double closing bracket!)
- You included ‘import random’ at the beginning of the program
- You used only spaces or only tabs as indents
- In line 9 (the if statement) you used a double equals sign (==) and not a single equals sign (=)
- Your newline characters (\n) are inside the closing double quote
4) Hit the run button at the top left of the screen
If you run into trouble, go through the checklist again.
If you want a pizza, it’s easier to call a pizza expert than to make a pizza yourself. Using a module is like calling an expert. First, you import the module (line 1). Next you call the module and request a service, like a pizza, or a random number between 1 and 100 (line 2).
LINE 3: tries = 7
In this game, the player has 7 guesses. The ‘tries’ variable keeps track of how many guesses are left.
THE MAIN LOOP: LINES 5-15
Each guessing round goes like this:
1) The player’s guess is recorded (line 6)
2) The number of guesses remaining is decreased (line 7)
3) The player’s guess is compared to the computer’s number and the outcome is printed (lines 9-15)
Picture a ‘while loop’ as a a car driving around a track over and over until it runs out of gas. In our case, the ‘gas’ is the ‘tries’ variable. As long as the player has more than 0 tries then our car has gas, and the code inside the while loop (lines 6-15) is repeated. Since ‘tries’ starts at 7, the while loop will execute a maximum of 7 times.
NOTE: A code statement is ‘inside’ a loop if the line starts with an indent and comes after the ‘while’ statement
Inside the circular track the car arrives at a fork in the road: the ‘if-elif-else’ statement. If the player’s guess matches the computer’s number, the car goes to the right (lines 10-11). If the guess is too high the car goes straight (line 13) and if the guess is too low the car goes left (line 15). Only one of these outcomes is possible each round. Then the car drives back to the beginning of the loop and goes through the branch all over again.
Each of the three outcomes contains a print statement that notifies the player about their result. Outcome #1 also has an extra line: quit(). This is a second method of exiting a while loop — by exiting the entire program. It’s the equivalent of driving our car into a brick wall because it stops all code execution.
If the player runs out of guesses the loop stops. The program continues onto lines 16-17, which inform the player that he or she has lost.
INTEGERS vs STRINGS
Computers store information in different ways. Two common information types are strings and integers. Strings store text characters. Integers — shortened as ‘int’ — store whole numbers, like 2, or 27, or 2000.
Each information type behaves differently in a program. For example, If you add the numbers 2 and 5 you will get the number 7. If you add the strings ‘2’ and ‘5’ you will get the string ’25’. You can convert between the two information types using the functions str and int. You can see these in action in lines 6 and 17.
PLAY THE GAME!
Now that you’ve mastered the code, try playing a few rounds against the the computer. Can you come up with a strategy that lets you win every time? (Psst: try it yourself before looking at the answer below).
HOW TO WIN…
Winning the game is all about eliminating possibilities as quickly as you can. At the beginning, all you know is that the computer’s number is between 1 and 100. Therefore you have 100 possibilities.
Let’s say you guess 80 on your first round. If the computer replies that 80 is too low, you know that the number is between 81-100. This leaves 20 possibilities, meaning you’ve eliminated 80 others. Great. But if the computer tells you 80 is too high, you’re left with 80 possibilities (1-79). Not so great.
Instead of gambling, the solution is to always pick the middle value: 50. That way you’re guaranteed to cut the number of possibilities in half at every round. Here are some examples:
We call this technique ‘Binary Search’. It’s one of the most important search techniques in computer science because it’s really fast. Without binary search, you could look at a maximum of 100 numbers to find the right one. But with binary search, you only have to look at a maximum of 7. That’s over 10 times faster!
Binary Search from Khan Academy
Binary Search (simple)
Binary Search (techncial)
Also In The December 2017 Issue
Building and creating your tools with the Minecraft toolbox helps you survive the game.
Sensors give robots the senses humans have.
30+ ideas for all age holiday gifts, from books to apps to board games to VR and more.
There might be a reason that too-real robot and video game character creeps you out.
You computer mouse cursor finally gets a cat to chase it.
Create turtles with Python, the programming language.
This programming language uses colors instead of text and punctuation to add and perform other tasks.
Use micro:bit to water your plants!
Knowing how passwords are cracked can help you create better passwords.
Studying satellite photographs shows a lot about what happens in the world.
There are a number of strategies teachers (plus parents and students) can take to learn programming.
Pigpen ciphers uses alien-like symbols to hide secret messages.
This project uses conductive thread to create a glove to activates your phone.
The repl.it website and React are one way to create mobile apps.
Software programming does neat things with language, in this case, mixing capital letters.
This Scratch game has lots of ways you can customize the game play. No cats were harmed in the making of this article either.
Links from the bottom of all the October 2017 articles, collected in one place for you to print, share, or bookmark.
Interesting stories about computer science, software programming, and technology for October 2017.