Help with arrays

[Gleb Belov]

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...

 

[Philip Semanchuk]

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.

HTH
Philip

 

[Mart.]

import random
import time

l = range(1, 10)

while l:
    print l.pop(random.randint(0, len(l) - 1))
    time.sleep(2)

Perhaps generate all of the possible moves at the outset in some form
of lookup table that you can refer to? I think it is a similar thing
to how computers play chess, I think it is called "hash tables"

 

[Dave Angel]

Philip Semanchuk wrote:



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

 

[Mart.]

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!

 

[Dave Angel]

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