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()
    


Answer: what you are looking for is the classic [binary search
algorithm](http://en.wikipedia.org/wiki/Binary_search_algorithm)

    
    
    def computer_guess(num):
        low = 1
        high = 100
        guess = 50
        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))`

