''' Purpose: play guess a number
'''

# thought experiment
# how do we guess a random number within a large range of numbers correctly
# find the middle, then check whether it is too high or too low and go from there (repeat)
# this is an algorithm in CS called binary search
# each time through, we throw away half of the remaining numbers --> make our search space smaller

# specify max number
n = 10000

# start the game
print( 'Think of a number from 0 to', n )  # the target number

# set the variables for the range of numbers
low = 0
high = n

# set our looking variable
looking_for_the_number = True

# get the middle number between our max number and our min number
# is the middle number greater than or less than the target number?
# we need to keep track of the range of numbers we are looking at:
#   what is the min (low) number in this range?
#   what is the max (high) number in this range?

# at the start, our min is 0, max is n

# while we are still looking for the correct number
while ( looking_for_the_number == True ):
    print('low =', low, 'high =', high)

    # get the middle number between low and high of our current range
    middle = ( low + high ) // 2

    # is middle in the upper range?
    # want to ask user if their number is greater than the middle
    prompt = "Is your number greater than " + str( middle ) + '? (yes/no): '
    # convert int middle to a string to concatenate

    reply = input( prompt )

    # if the reply is greater than middle
    if ( reply == 'yes' ):
        # the number must be in the range middle + 1 to the high
        low = middle + 1

    else: # if the reply is not greater than (less than) the middle
        # check if the number is equal to middle
        prompt = 'Is your number equal to ' + str( middle ) + '? (yes/no): '
        reply = input( prompt )

        # if the number is equal to the middle, then we've found the number
        if ( reply == 'yes' ):
            looking_for_the_number = False # set the looking variable to False
            print( 'Got it' )
        else: # if reply is not 'yes' (reply == 'no')
            # reply must be less than the middle
            # so the high must be at most middle - 1
            # low is still the same as previous
            high = middle - 1