**Video Introduction**
(17 minutes) <<--- Watch this video first, then

**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 this**
Next
**
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).

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 playedAsk some yes/no questionsTell 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 ConceptsSequence-- Steps, one by one, in orderIteration-- A sequence that is repeated more than onceConditional-- A sequence that is skipped, depending on some testVariables-- Named values stored in memory, with commands to change the valuesInput/Output-- Bringing values in from outside the computer, or sending them outSubroutines-- 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 questionInput answerNextTell 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 = 100Let bottom = 1Tell 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 " # bottomDone

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-bottomlet tmp = tmp/2Let 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.