Help with arrays
Dave Angel
davea at ieee.org
Wed Aug 26 17:37:52 CEST 2009
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 regenerate 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 14
>> 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/binarysearchinpython)
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
More information about the Pythonlist
mailing list