Help with arrays

[Dave Angel]

Mart. wrote:
> On Aug 26, 3:02 am, Dave Angel <da... at ieee.org> wrote:
>   
>> 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
>>     
>
> That's a good point if you can define whether the computer has guessed
> too low/high, then you could use the previous guess to set a bounds
> and rescale the next random guess.
>
> min + (random_number * max)
>
> although I think random.randomint does this for you!
>
>   
Actually, if you change the specs this way, you don't need random at 
all.  Just guess halfway through the remaining range.  To guess a number 
between 1 and 100 this way takes 7 guesses, worst case.  (plus/minus 1, 
I haven't checked)   Same problem as searching a sorted list.

This code (from:  
http://stackoverflow.com/questions/212358/binary-search-in-python)  
appears to search a sorted list

|def binary_search(a, x, lo=0, hi=None):
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        midval = a[mid]
        if midval < x:
            lo = mid+1
        elif midval > x: 
            hi = mid
        else:
            return mid
    return -1

|


DaveA