This puzzle has been making the rounds:
- Albert and Bernard became friends with Cheryl, and want to know when her birthday 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, and I know that Bernard does not know."
- 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?
Let's work through this puzzle statement by statement.
dates = ['May 15', 'May 16', 'May 19',
'June 17', 'June 18',
'July 14', 'July 16',
'August 14', 'August 15', 'August 17']
We'll define accessor functions for the month and day of a date:
def Month(date): return date.split()[0]
def Day(date): return date.split()[1]
Month('May 15')
'May'
Day('May 15')
'15'
Now we have to think about what we're doing. We'll use a set of dates to represent a belief set: a person who has the belief set {'August 15', 'May 15'} believes that Cheryl's birthday is one of those two days. A person knows the birthdate when they get down to a belief set with only one possibility.
We can define the idea of Cheryl telling someone a component of her birthdate, and while we're at it, the idea of knowing a birthdate:
BeliefSet = set
def tell(part, dates=dates) -> BeliefSet:
"Cheryl tells a part of her birthdate to someone; return a set of possible dates."
return {date for date in dates if part in date}
def know(beliefs) -> bool:
"A person `knows` the answer if their belief set has only one possibility."
return len(beliefs) == 1
For example: If Cheryl tells Albert that her birthday is in May, he would know there is a set of three possible birthdates:
tell('May')
{'May 15', 'May 16', 'May 19'}
And if she tells Bernard that her birthday is on the 15th, he would know there are two possibilities:
tell('15')
{'August 15', 'May 15'}
With two possibilities, Bernard does not know the birthdate:
know(tell('15'))
False
If Cheryl tells Albert 'May' then he knows there are three possibilities, but we (the puzzle solvers) don't know that, because we don't know what Cheryl said.
So what can we do? We can 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 other possible dates. If all goes well, there should be exactly one date for which all the statements are true.
Here is the main function, cheryls_birthday, which takes a set of possible dates, and returns the subset of dates that satisfy statements 3 through 5. The function satisfy is similar to the builtin function filter: satisfy takes a collection of items (here a set of dates) and returns the subset that satisfies all the predicates:
def cheryls_birthday(dates=dates) -> BeliefSet:
"Return a subset of the dates for which all three statements are true."
return satisfy(dates, statement3, statement4, statement5)
def satisfy(items, *predicates):
"Return the subset of items that satisfy all the predicates."
return {item for item in items
if all(pred(item) for pred in predicates)}
## TO DO: define statement3, statement4, statement5
The function statement3 corresponds to the third statement in the problem. It takes as input a single possible birthdate (not a set) 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 it in a form that uses the concepts we have defined:
Albert: After Cheryl told me the month of her birthdate, I didn't know her birthday. But for any of the possible dates, if Bernard was told the day of that date, he would not know Cheryl's birthday.
That I can translate directly into code:
def statement3(date) -> bool:
"Albert: I don't know when Cheryl's birthday is, but I know that Bernard does not know too."
dates = tell(Month(date))
return (not know(dates)
and all(not know(tell(Day(d))) for d in dates))
We haven't solved the puzzle yet, but let's take a peek and see which dates satisfy statement 3:
satisfy(dates, statement3)
{'August 14', 'August 15', 'August 17', 'July 14', 'July 16'}
Again, a paraphrase:
Bernard: At first Cheryl told me the day, and I didn't know. Then, out of the possible dates, 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."
dates = tell(Day(date))
return (not know(dates) and know(satisfy(dates, statement3)))
Let's see which dates satisfy both statement 3 and statement 4:
satisfy(dates, statement3, statement4)
{'August 15', 'August 17', 'July 16'}
Wait a minute—I thought that Bernard knew?! Why are there three possible dates? Bernard does indeed know; it is just that we, the puzzle solvers, don't know. That's because Bernard knows something we don't know: the day. If Bernard was told '15' then he would know 'August 15'; if he was told '17' he would know 'August 17', and if he was told '16' he would know 'July 16'. We don't know because we don't know which of these is the case.
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(satisfy(tell(Month(date)), statement4))
cheryls_birthday()
{'July 16'}
Success! We have deduced that Cheryl's birthday is July 16. It is now True that we know Cheryl's birthday:
know(cheryls_birthday())
True