10 Questions or Less: Guess the Date (Python)

Question

I have been tasked with to write a program that guesses a date the user is thinking of where the AI asks 10, or less, 'yes' or 'no' questions. Essentially this is just a reverse number guessing game. I have written a function that creates a list of all the days of the year, from Jan 1 to Dec 31, basically 365 entries.

def Calendar(monthNames, numDaysInMonth):
'''Return a list of elements, each element
    is a date in a calendar year'''

    if len(monthNames) != len(numDaysInMonth):
        return []

    dates = []
    idx = 0

    while idx < len(monthNames):
        for date in range(1, numDaysInMonth[idx] + 1):
            dates.append(monthNames[idx] + " " + str(date))
        idx = idx + 1
    return dates
months = ["Jan", "Feb", "Mar", "Apr", "May", "Jun",
          "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"]
numDays = [31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31] 
print(Calendar(months, numDays))

Obviously the print statement is not needed, but was used to check my work. Now, my question is, where do I go from here? Since the computer is asking 'yes' or 'no' questions, I'd like for the program to narrow down by dividing the number in half until the "date" is zeroed in, and then use that number to point to the index from the function I've already created. By no means am I asking for this to be done for me, but a nice nudge in the right direction would be nice. I'm lost on what to do next.

https://stackoverflow.com/questions/9501337/binary-search-algorithm-in-python — perigon, Jul 31 '17 at 03:33
It will be easier to handle if you associate each date with a plain numeric value 1-365. A dict would work, where the keys are the items in your `dates` list, and the values start at 1 and count up from there. — John Gordon, Jul 31 '17 at 03:43
By the way, your `while` loop is not very Pythonic; a cleaner loop would be `for month in monthNames:` — John Gordon, Jul 31 '17 at 03:45
@JohnGordon More like this? `for month in monthNames: for date in range(1, numDaysInMonth[idx] + 1): dates.append(monthNames[idx] + " " + str(date)) idx = idx + 1` — DubStep, Jul 31 '17 at 04:01
@HariomSingh The only input would be the user answering yes or no from the questions being asked by the program. The next question asked would be dependant on how the previous question was answered. For example: `q1 = input("Is the date your thinking of between Jan 1 and Jul 1 (inclusive)?)` — DubStep, Jul 31 '17 at 04:10
If answered yes, then the following question would be something like, between Jan 1 and Apr 1 (inclusive)? until finally the program correctly guesses the date the user is thinking of. — DubStep, Jul 31 '17 at 04:11

score 0 · Answer 1 · answered Jul 31 '17 at 04:51

I can see it as Binary tree implementation ..total is 365 days keep dividing by 2 based on user input yes or no

365/2  - step 1 yes or no 
182    -2
91 .   -3
45     -4
22     -5
11     -6
5      -7
2      -8 
1,2 .  - 9, 10

its a rough estimate but I guess optimizing the algo will help

score 0 · Answer 2 · answered Jul 31 '17 at 06:39

It seems like you were asked to write a program that applys some kind of binary search.

Because your computer is asked to answer a Y/N question let's define a function that will ask the question, recieve the answer and return a coresponding boolean value:

def is_earlier(guess):

    answer = input("is {} earlier then your date? Y - earlier /N - not earlier".format(guess))

    if answer.upper() == "Y":
        return True

    else:
        return False

So basically, this code, will ask user everytime if it is the earlier then the property and will react according to user's response.

Next, let's use binary search: every the program will ask the user if d, the current date it is pointing on, is earlier. If d is earlier, we will "throw away" everything that is later then d-1(day before) on the list. If d is later or it is the exact date, we will "throw away" everything that is earlier then d. When we are left with lst with one value only- we return this value-- this is our date.

def guess_game(lst = Calendar(months,numDays)):

    if len(lst) == 1:
        return lst[0]

    mid = len(lst)//2

    if is_earlier(lst[mid]):
        return guess_game(lst[:mid])
    else:
        return guess_game(lst[mid:])

And now why less then 10 questions? If we know that binary search takes rougly LOG(N) operation (where N is the length of the list), and we know there's arround 365 days a year, we will reach something like 8-10 questions, depending on the the location of the date that the user picked, in the list.

This makes WAY more sense now. I was having a hard time actually figuring out how to keep asking the questions and pointing to the place in the index automatically without hard coding it in. — DubStep, Jul 31 '17 at 23:54

10 Questions or Less: Guess the Date (Python)

2 Answers2