<div align=right>Peter Norvig, April 2015</div>
This logic puzzle has been making the rounds:
Albert and Bernard just became friends with Cheryl, and they want to know when her birtxhday is. Cheryl gave them a list of 10 possible dates:
May 15 May 16 May 19 June 17 June 18 July 14 July 16 August 14 August 15 August 17
Cheryl then tells Albert and Bernard separately the month and the day of the birthday respectively.
Albert: I don't know when Cheryl's birthday is, but I know that Bernard does not know too.
Bernard: At first I don't know when Cheryl's birthday is, but I know now.
Albert: Then I also know when Cheryl's birthday is.
So when is Cheryl's birthday?</i>
Cheryl's puzzle was designed to be solved with a pencil, the greatest problem-solving tool in the history of mathematics (although some prefer a pen, chalk, marker, or a stick for drawing in the sand). But I will show how to solve it with another tool: computer code. I choose this tool for four reasons:
We will translate each of the 6 statements in the puzzle into Python code:
DATES = ['May 15', 'May 16', 'May 19', 'June 17', 'June 18', 'July 14', 'July 16', 'August 14', 'August 15', 'August 17']
We'll also define accessor functions for the month and day of a date:
def Month(date): return date.split() def Day(date): return date.split()
We can define the idea of telling, and while we're at it, the idea of knowing a birthdate:
def tell(part, possible_dates=DATES): "Cheryl tells a part of her birthdate to someone; return a new list of possible dates that match the part." return [date for date in possible_dates if part in date] def know(possible_dates): "A person knows the birthdate if they have exactly one possible date." return len(possible_dates) == 1
Note that we use a list of dates to represent someone's knowledge of the possible birthdates, and that someone knows the birthdate when they get down to only one possibility. For example: If Cheryl tells Albert that her birthday is in May, he would have a list of three possible birthdates:
['May 15', 'May 16', 'May 19']
And if she tells Bernard that her birthday is on the 15th, he would end up with two possibilities:
['May 15', 'August 15']
With two possibilities, Bernard does not know the birthdate:
When Cheryl tells Albert
'May' then he knows there are three possibilities, but we (the puzzle solvers) don't, because we don't know what Cheryl said. So what can we do? We will consider all of the possible dates, one at a time. For example, first consider
'May 15'. Cheryl tells Albert
'May' and Bernard
'15', giving them the lists of possible birthdates shown above. We can then check whether statements 3 through 5 are true in this scenario. If they are, then
'May 15' is a solution to the puzzle. Repeat the process for each of the possible dates. If all goes well, there should be exactly one solution.
Here is the main function,
def cheryls_birthday(possible_dates=DATES): "Return a list of the possible dates for which statements 3 to 5 are true." return filter(statements3to5, possible_dates) def statements3to5(date): return statement3(date) and statement4(date) and statement5(date) ## TO DO: define statement3, statement4, statement5
filter(predicate, items) returns a list of all items for which
predicate(item) is true.)
statement3 takes as input a possible birthdate and returns true if Albert's statement is true for that birthdate. How do we go from Albert's English statement to a Python function? Let's paraphrase in a form that is closer to Python code:
Albert: After Cheryl told me the month of her birthdate, I didn't know her birthday. I don't know which day Cheryl told Bernard, but I know that for all of the possible dates, if Bernard is told that day, he wouldn't know the birthdate.
That I can translate directly into code:
def statement3(date): "Albert: I don't know when Cheryl's birthday is, but I know that Bernard does not know too." possible_dates = tell(Month(date)) return (not know(possible_dates) and all(not know(tell(Day(d))) for d in possible_dates))
We can try the function on a date:
In fact, we can see all the dates that satisfy statement 3:
['July 14', 'July 16', 'August 14', 'August 15', 'August 17']
Again, a paraphrase:
Bernard: At first Cheryl told me the day, and I didn't know. Then I considered just the dates for which Albert's statement 3 is true, and now I know.
def statement4(date): "Bernard: At first I don't know when Cheryl's birthday is, but I know now." at_first = tell(Day(date)) return (not know(at_first) and know(filter(statement3, at_first)))
Let's see which dates satisfy both statement 3 and statement 4:
filter(statement4, filter(statement3, DATES))
['July 16', 'August 15', 'August 17']
Wait a minute—I thought that Bernard knew?! Why are there three possible dates remaining? Bernard does indeed know the birthdate, because he knows something we don't know: the day. We won't know the birthdate until after statement 5.
Albert is saying that after hearing the month and Bernard's statement 4, he now knows Cheryl's birthday:
def statement5(date): "Albert: Then I also know when Cheryl's birthday is." return know(filter(statement4, tell(Month(date))))
Success! We have deduced that Cheryl's birthday is July 16. It is now
True that we know Cheryl's birthday: