Help with arrays

Dave Angel davea at
Wed Aug 26 17:37:52 CEST 2009

Mart. wrote:
> On Aug 26, 3:02 am, Dave Angel <da... at> 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:  
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
            return mid
    return -1



More information about the Python-list mailing list