Help with arrays

[Dave Angel]

Stephen Fairchild wrote:
> Philip Semanchuk wrote:
>
>   
>> On Aug 25, 2009, at 6:14 PM, Gleb Belov wrote:
>>
>>     
>>> Hello! I'm working on an exercise wherein I have to write a Guess The
>>> Number game, but it's the computer who's guessing MY number. I can get
>>> it to work, but there's one obvious problem: the computer generates
>>> random numbers until one of them corresponds to my number, but it will
>>> often generate one number (eg. 4) numerous times, meaning it doesn't
>>> know that this number is invalid. What I mean is, it will sometimes
>>> use 37 tries to guess a number out of 1 - 9, which makes no sense,
>>> since it should only take 9 tries, at most. I was trying to find a way
>>> to make a dynamic list of all the numbers the computer generates in
>>> the loop and then make it re-generate the number if the previous
>>> number is present in the list, so it doesn't keep on generating 4 (as
>>> an example). I don't know if that makes sense... Basically, we humans
>>> know that once something is incorrect, there's no point in trying to
>>> use it as the answer next time, because we already know it's
>>> incorrect. How do I go about coding this in Python? I'm still quite
>>> new to the language so any help will be appreciated...
>>>       
>> One cheap way to do it (not necessarily efficient) is to make a list
>> of your possible guesses (e.g. range(1,10)), use random.shuffle() to
>> put them in random order and then run through the guesses one at a time.
>>     
>
> import random
> import time
>
> l = range(1, 10)
>
> while l:
>     print l.pop(random.randint(0, len(l) - 1))
>     time.sleep(2)
>
>   
While both of these will work well, I'd point out that a direct 
translation of your question is to use a set.  Define an empty set, and 
each time you try a number unsuccessfully, add it to the set.  Then just use
       while x in myset:
               x = newguess()

to find the next guess.  This approach isn't as efficient, but it's a 
useful paradigm to understand.

A separate question is whether the human is supposed to tell the 
computer whether the guess is high or low.  If so, you can eliminate 
many numbers on each guess.   For example, suppose the solution is 8.  A 
guess of 5 would say "too low."  Then you'd cross off now only 5 but 1-4 
as well.

With this change the best solution changes from a random shuffle to a 
binary search.

DaveA