Newb ??

[Dennis Lee Bieber]

Re: Newb ??

On Thu, 10 Nov 2005 17:00:38 +0000, Norman Silverstone
<norman@littlet ank.org> declaimed the following in comp.lang.pytho n:
[color=blue]
> Thanks for that but I think it is too simplistic. It appears OK for the
> first guess, which is 50 but, what about the next guess. If the guess is
> too high then the next guess has to be 50/2. However, if it is too low
> then the next guess must be first guess + (100-second guess)/2. In general
> terms, if guess is too high then next guess must (guess - lowest
> possible)/2 and if too low then it is guess + (highest possible -
> guess)/2.
>[/color]
I'm having trouble following that -- I think you may be complicating
things more than you need to...

The basic algorithm only needs to know the "current" low and high
end of the range.

new_guess = (current_low + current_high) / 2

Match: break out of loop, with a successful guess
Low: current_low = new_guess; repeat #could be new_guess +1
#as you know it can not
#be "new_guess"
High: current_high = new_guess; repeat #or new_guess-1


Say the number is 78
low high guess result
0 100 (0+100)/2 => 50 LOW
50 100 (50+100)/2 => 75 LOW
75 100 (75+100)/2 => 88 HIGH (rounded up)
75 88 (75+88)/2 => 82 HIGH (rounded up)
75 82 (75+82)/2 => 79 HIGH (rounded up)
75 79 (75+79)/2 => 77 LOW
77 79 (77+79)/2 => 78 MATCH

NOTE: if you use the +1/-1 adjustments (to eliminate the guess
itself from being an end-point, as you know it can not be that value)
the above will converge to a match one step sooner.
--[color=blue]
> =============== =============== =============== =============== == <
> wlfraed@ix.netc om.com | Wulfraed Dennis Lee Bieber KD6MOG <
> wulfraed@dm.net | Bestiaria Support Staff <
> =============== =============== =============== =============== == <
> Home Page: <http://www.dm.net/~wulfraed/> <
> Overflow Page: <http://wlfraed.home.ne tcom.com/> <[/color]

[Steven D'Aprano]

Re: Newb ??

On Thu, 10 Nov 2005 17:31:18 +0000, Steve Holden wrote:
[color=blue]
> Effectively you want to start with a minposs and maxposs, which are set
> to 0 and 100 respectively. Your guess should bisect the range (as nearly
> as it can given that you are dealing with integers, and you have to be
> careful to get the awkward boundary conditions right). So your first
> guess will be 50. If your guess is too low then replace minposs with
> your guess (in this case 50); if too high, replace maxposs with your
> guess; loop to generate the next guess, and so on. In practice since
> log2(100) > 5 your five guesses won't always be enough (though seven
> should be).[/color]

Dude, that's what my code does, although I admit I took zero care to get
the awkward boundary conditions right, nor did I put code in to stop the
game after five attempts.

--
Steven.

[Fredrik Lundh]

Re: Newb ??

Steven D'Aprano wrote:
[color=blue]
> Dude, that's what my code does, although I admit I took zero care to get
> the awkward boundary conditions right, nor did I put code in to stop the
> game after five attempts.[/color]

as my simulator shows, your code needs 5.87 attempts to make a correct
guess, on average.

if you add a 5-guess limit, it will find the right number only in 30% of all
runs. here's a complete list of (max number of guesses; % chance that
you'll find the right answer given an even distribution of target numbers)

1 1.0
2 3.0
3 6.9
4 14.9
5 30.7
6 62.4
7 100.0

fwiw, you may improve things slightly by special-casing the first guess:

http://www.pomona.edu/Magazine/pcmfl00/1.shtml

</F>

[Norman Silverstone]

Re: Newb ??

[color=blue]
> did you test the script? here's a simulator:[/color]

< snip>

Fredrik, thank you very much indeed for taking the trouble to show me the
way. I am sorry that I made the comment I did, that will teach me to read
more carefully. It is said that there is no fool like an old fool and, as
I am approaching 78 years old, I think I qualify. It is also said that you
are never too old to learn so I am trying.

Now, I put the script you gave into an editor and ran it , (I use Ubuntu
Linux by the way). It certainly showed how the computer arrived at the
number guessed but guessed the number itself and gave me no chance to say
whether high or low. I noticed also that the numbers were all greater than
50 and the loop ran until the number guessed was 100, then it stopped.
Perhaps you can point out to me how I should go about debugging.

Incidentally, I am only just starting to learn about functions and have
not come across the module 're'. Also why is it (lo+hi)//2 and not
(lo+hi)/2.

Thanks again for your help.

Norman



[color=blue]
> # end
>[color=green]
>> Comments please.[/color]
>
> if this had been a java "let's pretend you're the java runtime"
> certification question, you would have failed.
>
> </F>[/color]

[Alex Martelli]

Re: Newb ??

Norman Silverstone <norman@littlet ank.org> wrote:
...[color=blue]
> Incidentally, I am only just starting to learn about functions and have
> not come across the module 're'. Also why is it (lo+hi)//2 and not
> (lo+hi)/2.[/color]

Using // ensures truncation, which is what you want. A single / may mean
truncating division in the default legacy/compatibility mode, but with
the new division behavior (which one day will become standard) it means
true division, so that for example 1/2 means 0.5 -- better get used to
the new behavior ASAP (which is why you can ask for new division
behavior with -Qnew on Python's commandline or 'from __future__ import
division' at the top of your module -- to help you get used to it).


Alex

[Fredrik Lundh]

Re: Newb ??

Norman Silverstone wrote:
[color=blue][color=green]
> > did you test the script? here's a simulator:[/color]
>
> < snip>
>
> Fredrik, thank you very much indeed for taking the trouble to show me the
> way. I am sorry that I made the comment I did, that will teach me to read
> more carefully. It is said that there is no fool like an old fool and, as
> I am approaching 78 years old, I think I qualify. It is also said that you
> are never too old to learn so I am trying.
>
> Now, I put the script you gave into an editor and ran it , (I use Ubuntu
> Linux by the way). It certainly showed how the computer arrived at the
> number guessed but guessed the number itself and gave me no chance to say
> whether high or low. I noticed also that the numbers were all greater than
> 50 and the loop ran until the number guessed was 100, then it stopped.
> Perhaps you can point out to me how I should go about debugging.[/color]

debugging? the script I posted was intended to show you that given an
honest human (simulated by the raw_input function), the posted algorithm
found the right answer for all values in the given range. (if the algorithm
had been broken, the simulator wouldn't have finished).

if you want to play yourself, use Steven's original code, and follow the in-
structions...

</F>