Guess the number game optimization (user creates number, computer guesses)

Question

I am very new to programming so I decided to start with Python about 4 or 5 days ago. I came across a challenge that asked for me to create a "Guess the number" game. After completion, the "hard challenge" was to create a guess the number game that the user creates the number and the computer (AI) guesses.

So far I have come up with this and it works, but it could be better and I'll explain.

from random import randint

print ("In this program you will enter a number between 1 - 100."
       "\nAfter the computer will try to guess your number!")

number = 0

while number < 1 or number >100:
    number = int(input("\n\nEnter a number for the computer to guess: "))
    if number > 100:
        print ("Number must be lower than or equal to 100!")
    if number < 1:
        print ("Number must be greater than or equal to 1!")

guess = randint(1, 100)

print ("The computer takes a guess...", guess)

while guess != number:
    if guess > number:
        guess -= 1
        guess = randint(1, guess)
    else:
        guess += 1
        guess = randint(guess, 100)
    print ("The computer takes a guess...", guess)

print ("The computer guessed", guess, "and it was correct!")

This is what happened on my last run:

Enter a number for the computer to guess: 78

The computer takes a guess... 74

The computer takes a guess... 89

The computer takes a guess... 55

The computer takes a guess... 78

The computer guessed 78 and it was correct!

Notice that it works, however when the computer guessed 74, it then guessed a higher number to 89. The number is too high so the computer guesses a lower number, however the number chosen was 55. Is there a way that I can have the computer guess a number that is lower than 89, but higher than 74? Would this require additional variables or more complex if, elif, else statements?

Thank you Ryan Haining

I used the code from your reply and altered it slightly so the guess is always random. If you see this, let me know if this is the best way to do so.

from random import randint

def computer_guess(num):
    low = 1
    high = 100
    # This will make the computer's first guess random
    guess = randint(1,100)
    while guess != num:
        print("The computer takes a guess...", guess)
        if guess > num:
            high = guess
        elif guess < num:
            low = guess + 1
        # having the next guess be after the elif statement
        # will allow for the random guess to take place
        # instead of the first guess being 50 each time
        # or whatever the outcome of your low+high division
        guess = (low+high)//2    

    print("The computer guessed", guess, "and it was correct!")


def main():
    num = int(input("Enter a number: "))
    if num < 1 or num > 100:
        print("Must be in range [1, 100]")
    else:
        computer_guess(num)

if __name__ == '__main__':
    main()

Solution 1

what you are looking for is the classic binary search algorithm

def computer_guess(num):
    low = 1
    high = 100
    guess = (low+high)//2
    while guess != num:
        guess = (low+high)//2
        print("The computer takes a guess...", guess)
        if guess > num:
            high = guess
        elif guess < num:
            low = guess + 1

    print("The computer guessed", guess, "and it was correct!")


def main():
    num = int(input("Enter a number: "))
    if num < 1 or num > 100:
        print("Must be in range [1, 100]")
    else:
        computer_guess(num)

if __name__ == '__main__':
    main()

The algorithm works by selecting a low and high limit to start with (in your case low=1 and high=100). It then checks the midpoint between them.

If the midpoint is less than number, the midpoint becomes the new lower bound. If the midpoint is higher, it becomes the new upper bound. After doing this a new midpoint is generated between the upper and lower bound.

To illustrate an example let's say you're looking for 82.

Here's a sample run

Enter a number: 82
The computer takes a guess... 50
The computer takes a guess... 75
The computer takes a guess... 88
The computer takes a guess... 82
The computer guessed 82 and it was correct!

So what's happening here in each step?

1. low = 1, high = 100 => guess = 50 50 < 82 so low = 51
2. low = 51, high = 100 => guess = 75 75 < 82 so low = 76
3. low = 76, high = 100 => guess = 88 88 > 82 so high = 88
4. low = 76, high = 88 => guess = 82 82 == 82 and we're done.

Note that the time complexity of this is O(lg(N))

Solution 2

I briefly made the game which you need with follows:

                  import random

                  guess=int(input("Choose a number you want the computer to guess from  1-100: "))

                  turns=0
                  a=None

                  compguess=random.randint(1,100)

                 while turns<10 and 100>guess>=1 and compguess!=guess: #computer has 10 turns to guess number, you can change it to what you want
                  print("The computer's guess is:  ", compguess)
                  if compguess>guess:
                   a=compguess
                   compguess=random.randint(1,compguess)

                 elif compguess<guess:
                  compguess=random.randint(compguess,a)
                  turns+=1


               if compguess==guess and turns<10:
                print("The computer guessed your number of:" , guess)
                turns+=1

              elif turns>=10 and compguess!=guess:
               print("The computer couldn't guess your number, well done.")


             input("")

This is a bit rusty, but you could improve it by actually narrowing down the choices so the computer has a greater chance of guessing the right number. But where would the fun in that be? Notice how in my code, if the computer guesses a number which is greater than than the number the user has inputed, it will replace 100 from the randint function with that number. So if it guesses 70 and its too high, it won't choose a number greater than 70 after that. I hope this helps, just ask if you need any more info. And tell me if it's slightly glitchy

Solution 3

This is how I went about mine...

     __author__ = 'Ghengis Yan'

     print("\t This is the age of the computer")
     print("\n The computer should impress us... the Man")

     import random

     #User chooses the number
     the_number = int(input("Human Choose a number between 0 and 100 "))
     tries = 1
     computer = random.randint(0,100)
     # User choose again loop
     while the_number > 100:
         the_number = int(input("I thought Humans are smarter than that... \nRetype the number... "))
     if the_number <= 100:
         print("Good")

     # Guessing Loop
     while computer != the_number:
         if computer > the_number:
             print(computer, "lower... Mr. Computer")
         else:
             print(computer, "higher... Mr. Computer")
         computer = int(random.randint(0,100))
         tries += 1

     print("Computer Congratulations... You beat the human! The Number was ", the_number)
     print("It only took a computer such as yourself", tries, "tries to guess it right...          pathetic")
     input("\nPress the enter key to exit.")

Solution 4

What I did for the same challenge was:

1) Define a variable that records the max value input by guessing computer. Ex:

max_guess_number = 0

2) Define another variable with the lowest guessed value. Ex.

min_guess_number = 0

3) Added in the "if computer_guess > secret_number" clause the following code (I added -1 so that the computer wouldn't try to guess the already previously tried number):

max_guess_number = guess - 1
computer_guess = random.randint(min_guess_number, max_guess_number)

4) Added the following code in the "if computer_guess < secret_number":

min_guess_number = guess + 1
computer_guess = random.randint(min_guess_number, max_guess_number)

Worth noting is the fact that I set my while loop to loop until another variable "guess_status" changes into a value 1 (the default I set to 0). This way I actually saw the result when the while loop finished.

Solution 5

print 'Please think of a number between 0 and 100!'
low = 0
high = 100
while(True):
    rand = (high+low)/2
    print 'Is your secret number '+str(rand)+'?'
    ans = raw_input("Enter 'h' to indicate the guess is too high. Enter 'l' to indicate the guess is too low. Enter 'c' to indicate I guessed correctly.")
    if ans=='h':
        high = rand
    elif ans=='l':
        low = rand
    elif ans=='c':
        print "Game over. Your secret number was:",rand
        break
    else:
        print "Sorry, I did not understand your input"

View more solutions

Comments

[hivert]

Isn't it supposed to work the other way around ? The computer choose the number, the user guesses ?

[mccdlibby]

It is normally, however the "hard challenge" was to switch that aspect of the program around. Making the user choose the number and the computer (AI) to guess.

[Paddy3118]

Hi @mccdlibby, The above task has a python solution on Rosetta Code here: rosettacode.org/wiki/Guess_the_number/… If you liked that, you might want to take a look at the "Bulls and cows task" which is a progression from this task.

[mccdlibby]

I changed it a little bit to make the computers first guess be random instead of always 50. I imported the randint() function. where you have random = 50 I changed random = randint(1,100) I moved guess = (low+high)//2 after the elif statement - this way the computer will always guess a random number and the same constraints remain to the next guess.

[Ryan Haining]

@mccdlibby but guessing a random number first is suboptimal, you always want to cut out half of the possible results with each guess. If you want to optimize, leave the original guess as 50. Miklos Aubert posted a solution below that uses randoms all the way through. Both of ours have a best case of O(1). but mine has a worst case of O(lg(N)) and his has a worst case of O(N). why do you want to guess randomly at first?

[mccdlibby]

It really isn't that important to have it random, I mainly wanted to do it so you could choose 50 as a number and not have it be guessed immediately. I do see what you are saying though.

[Ryan Haining]

@mccdlibby I suppose for the purposes of the "game" it doesn't really matter too much, I just wanted to be sure you realize it isn't a performance advantage.

[James Waldby - jwpat7]

Actually, no low and high limit variables are needed ... in the question's code, just change guess = randint(1, 100) to guess = number and the program suddenly gets a lot shorter and simpler.

[TZHX]

This answer just... doesn't work, even when you try and sort out the formatting issues.

[Prune]

The question asks for help with a search refinement. Your code regresses from that to pure guessing, a method that is already covered in previous postings.

[Eugenio M Parages]

True. But I reached this thread by googling the question. In case anyone else does the same - I'd like to help that person.

[Teepeemm]

@EugenioMParages But how are you helping that person? The question begins with code that is better than pure guessing. What is your answer contributing?

[Ghos3t]

Can this really be called as the computer guessing the number?. To me, it seems like the word guess would mean something more random. By checking if the guess is greater or less than the user input number are we not getting extra information. Imagine two people playing the guess game, is the person who is guessing allowed to ask if his answer is greater or less than the number the user has picked in his mind.

[Sykhow]

Your answer is the best one I found here. Just typecast the rand value below while to int

[Edward]

my version. tried and lucky to get it working. user and pc can take turn to guess. 5 tries each.

[alan.elkin]

Welcome to SO. While this code snippet may be the solution, including an explanation really helps to improve the quality of your post. Remember that you are answering the question for readers in the future, and those people might not know the reasons for your code suggestion.

[Timo]

You fixed guess ( guess = 50), but maybe it is better guess=high/2 ?

[Ryan Haining]

@Timo yeah, I think I was probably trying to make it clearer for OP. It doesn't make a big difference because it recalculates the guess inside the loop. It could be guess = None. But who knows what I was doing 7 years ago

[Timo]

Can we do a recursive function? Such that 1 is returned if guess>num, -1 if guess<num and 0 if guess=num(function exits). Recursion seems cool here, there need to be parameters low, high, guess,num,counter: function guess(low, high, guess,num,counter)?.

[Ryan Haining]

@Timo you could do it recursively if you wanted, yeah, though you wouldn't need to pass the guess down, you would just recurse with a different high or low.

[Timo]

Thanks, do you mean this way: def fun(number); if guess > num:high = guess;return 1+ fun(high); if guess<num...

[Ryan Haining]

roughly, you'd need to call it with both low and high, but the function can calculate the guess rather than take it as an argument.