English IDE
<<--- Click this link and write your game program here. [Q]
When your calculator runs, click the yellow Done
button in the IDE to continue.
Then come back here and click thisNext
link to skip down to the next video.
If it's not a link yet, you might need to refresh your
browser, or else click this button to call a mentor:
If you are like me and prefer to read at your own pace
instead of whatever pace set in some video, You can read
the transcript (and probably come out ahead of the non-readers).
Video Transcript: 5. Guessing Game
Let's do a game. If you and your friend wanted to play the Guessing Game,
you might start off by announcing:
Hi. We are going to play the Guessing Game. You think of a number, then I will ask some yes/no questions, then I will tell you what number you thought of.
That tells your friend how the game will be played, and as such
it's a pretty good start at describing (with some pronoun switches) how
the computer will play the game you just described. So let's do that Top-Down
Design (TDD) thing (in the English
IDE), because it's good practice:
"Guessing Game"
Tell the person how it is played
Ask some yes/no questions
Tell what the number is
Converting the first line of the top level to code is easy (you
just print out the four lines in our original description). The last line
isn't much harder, presumably you have a variable that holds the guessed
number, so you print that out with a descriptive label.
It's that middle line that is the bummer. Of course it says nothing
about how you will decide what questions to ask, nor what you will do with
the answers. Somehow asking the right questions is supposed to let the
computer know (from a yes/no answer alone) something about the number the
person is thinking of.
Steve thinks that TDD can take us to the solution,
or at least kick the can down the road until we can solve it, but he already
knows how to do it. It's called "begging the question" when you solve a
problem by using the answer. The problem is that we don't even know what
kind of question to ask. If we did, then the problem would be as easy as
Steve makes it out to be.
Sometimes the real world programs we are trying to write are like this.
If you don't even know whether the problem can be solved -- or worse, you
don't know what you don't know -- then TDD is a waste
of time. First, figure out in your mind how to solve the problem.
Everybody does it that way. Even Steve knows you must do that. Otherwise
your TDD structure might be all wrong.
But this is a very old problem, and nobody ever figured it out for themselves.
I didn't think it up myself either. 20
million programmers didn't invent it, every one of us got it from somebody
else, except some mathematician eighty or a hundred years ago figured it
out. The rest of us all heard (or read) about it and copied the idea. Google
Knows All -- IF you can think of what to ask for, the right search
terms. I usually can't. So I will tell you: it's called "Binary Search"
and Google will give you a zillion hits on how to do binary search. Now
you know it can be done, we can get on with the program design...
Oh wait, if this is new to you, you still don't know what kind of question
to ask. I call it "Lion* Hunting" because it's like
hunting for a lion in the forest. You don't know where the lion is, so
you divide the forest in half, and the lion is either in one half or the
other. Now your problem is half as big. Now you know what kind of question
to ask, "Is the lion north (or west) of the line I just drew?" There are
some details to figure out, but we can aim our design to help us figure
that part out. We are not writing any code yet, just thinking out loud
(in English) about what needs to be done.
The forest is the range of all possible numbers the person might choose
from. That could get astronomical, so to keep things reasonable, we can
tell them what range to choose from, say "one to 99". They already know
what their number is, so our question to divide the forest in half would
be based on a range of numbers, initially all less than 100, and then half
of that, and then half again, and so on. Now (and not sooner, as Steve
supposes) we know that we can ask questions of the form "Is your number
less than __?" We also now know how to decide what number to fill in the
blank, it will be the middle of the previous range. We still need to figure
out what code to do all that, but we can use TDD for
that.
So let's work on the details for that middle line in our code design,
now expanded to three dots (in green,
because we do not need to look at the grayed-out rest of the program at
this time):
"Guessing Game"
Tell the person how it is played
{Ask some yes/no questions} ... Tell what the number is
Remember, we are aiming to convert everything to good "Six Concepts"
form:
Six Concepts Sequence -- Steps,
one by one, in order
Iteration -- A sequence
that is repeated more than once
Conditional -- A
sequence that is skipped, depending on some test
Variables -- Named
values stored in memory, with commands to change the values
Input/Output --
Bringing values in from outside the computer, or sending them out
Subroutines -- A
named sequence called up from somewhere else by a single command
Previously we did our TDD by breaking out each
line to be explained into its own subroutine, but it is also possible (as
we see today) to do the same analysis directly in-line (using a comment
in place of the subroutine name). The important thing is to go through
the process.
The first thing we might notice from this one-line description (the
green line above) is the word "some" which suggests repetition, the second
of our Six Concepts, let's put that in, along with a (blue)
description of what needs to happen inside that repetition:
"Guessing Game"
Tell the person how it is played
{Ask some yes/no questions} Repeat {Decide what
question to ask, or if done} Ask the question Input answer Next Tell what the number is
Already you see that two of those more detailed lines are already
each one of the Six, so they have no braces. So let's work on what the
question
is. For starters, it needs to be a variable (another of the Six). So whatever
gets decided, it needs to formulate a variable that is a question the computer
can Ask (print out). We already know what the question is:
Let question = "Is your number less than __?"
Of course that blank to be filled in is really a variable -- we
can give it a name now: I called it "lion" but you can name yours
anything you like (like "middle" or "fribble" or whatever),
if it helps you to understand what you are doing -- and it needs to be
outside the quotation marks if we want the value of that variable to be
printed instead of its name:
Let question = "Is your number less than " # lion # "?"
But we still need to figure out where to draw the lion
(I mean line), that is, what value goes into the variable. The first time
through the middle is obviously 50, but the next time, if they said yes
(their number is less than 50) the middle of the range 1..49 is 25, but
if they said no, then you want the middle of the range 50..99, which is
75. So we need to keep track of the range top and bottom, so to know what
to take the middle of. Initially the top is 100 and the bottom is 1, but
those values need to be set outside the loop. Oops, the first line "Tell
the person how it is played" is incomplete, it should be part of a more
general "Initialization" step (now blue
here):
"Guessing Game"
{Initialization} Let top = 100 Let bottom = 1 Tell the person how
it is played
{Ask some yes/no questions} Repeat {Decide what
question to ask, or if done}
{Decide if done}
Let lion = {the middle between top and bottom}
Let question = "Is your number less than " # lion # "?" Ask the question ...
So how do we know if we are done? Let's play the game in our mind,
and to keep things simple, assume the range is one to nine. That's nine
values, so we don't know which number was chosen.
We ask the question, "Is it less than 5?" and the answer is
No, so now we know it must be one of the five numbers 5,6,7,8,9.
"Is it less than 7?" Yes, so it must be either five or six.
"Is it less than 6?" The next time we draw the line through the forest,
there's only one number in the chosen side, so that must the number.
Notice we always ask if the number is "less than" the middle, so
when the answer is Yes, the middle is excluded (recall at the beginning
we chose 100 for the top, but we told the person 99, so top
is always excluded. If you don't do that, then if the person chooses your
specified top, your program can't guess it. After you get your
program working, you can experiment to convince yourself that this is true.
It's called a "boundary condition" and many computer bugs are due to invalid
boundary conditions. You need to always test your programs with values
on both sides of the edge of valid data.
Anyway, because top is always excluded, and bottom
is always included in the range being considered, when these two numbers
(variables) differ by exactly one, then (blue)
bottom
(the included value) is the correct guess:
"Guessing Game"
... Repeat {Decide what question
to ask, or if done} {Decide if
done}
If bottom+1=top then Exit ... Next {Tell
what the number is} Say "Your number is "
# bottom Done
Did you figure out how to find the middle of your range? The most
obvious way is to use a temporary variable to hold the number of elements
in the range (the difference between top and bottom), then divide that
in half, then add the bottom back on.
let tmp = top-bottom let tmp = tmp/2 Let lion = tmp+bottom
Less obvious (but simpler and quicker) is to add the top and bottom
and cut that in half. You should convince yourself (don't take my word
for it, but you can use the test method
in the Variables section) that this always works correctly:
Let lion = (top+bottom)/2
What happens if there are an odd number of numbers in the range?
Then the middle will be a half of a number, which looks bad. You should
round to the nearest integer (whole number). It turns out it doesn't really
matter if you round up or down, any whole number near the middle works
fine, so long as there is at least one number on each side (but you already
checked that).
Round lion
You can figure out where to put this code.
I think there is a small part of the initialization that is incomplete,
where you tell the person what is going on. You can do that without my
help. You might also consider making the Yes/No input easier on the person,
require only a single letter (Y or N, you did the same thing for the operator
in the Calculator) and be sure to tell them as part of your question
what you are expecting them to type.
If you put all that into the IDE and Run it, it will keep asking
the same question over and over, and never get to the correct number. Do
you know why that is? Where is it we are cutting the forest in half? I
don't see any code to do that. I don't see anything that even looks at
the person's answer. Can you figure out where that needs to go, and what
to do about it? If you can't figure it out, get help. Ask another student,
or else call for a Mentor.
Congratulations! Your program ran correctly. Click this link to
advance to the next program: Rock-Paper-Scissors
[2022 September 8]
*Lion The name is a pun on the idea of hunting
by drawing lines (sounds like "lions") across the data to divide it in half.
20
million programmers didn't invent it, every one of us got it from somebody
else, except some mathematician eighty or a hundred years ago figured it
out. The rest of us all heard (or read) about it and copied the idea. Google
Knows All -- IF you can think of what to ask for, the right search
terms. I usually can't. So I will tell you: it's called "Binary Search"
and Google will give you a zillion hits on how to do binary search. Now
you know it can be done, we can get on with the program design...