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 privately tells Albert the month and Bernard the day of her birthday.
- 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 the puzzle line by line.
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 really carefully about what we're doing. The puzzle is tricky because we're dealing with two types of uncertainty:
If Cheryl tells Albert "May", then he believes the birthdate could be either May 15, May 16, or May 19. We'll call {'May 15', 'May 16', 'May 19'}
his belief state about the birthdate. We will say that a person knows the birthdate when they get down to a belief state with exactly one possibility. The type 2 uncertainty is that we don't know that Albert was told "May", so we have uncertainty about his belief state. But we do know some statements about his belief state, and our task is to use those statements to solve the puzzle.
The way we will deal with our uncertainty as puzzle solvers is by considering each of the ten dates one at a time and reasoning as follows:
We can define the idea of Cheryl having told someone a component of her birthdate, and the idea of knowing a birthdate as follows:
BeliefState = set
def told(part: str) -> BeliefState:
"""Cheryl told a part of her birthdate to someone; return a belief state of possible dates."""
return {date for date in dates if part in date}
def know(beliefs: BeliefState) -> bool:
"""A person `knows` the answer if their belief state has only one possibility."""
return len(beliefs) == 1
(Note: one thing I dislike about my code is that told
uses the global dates
. Later we will see that cheryls_birthday
does the same. For that to be an acceptable design choice, we need to think of dates
as a constant, not a variable.)
Let's see what happens as we consider the date 'May 15'
:
Cheryl tells Albert 'May'
and Bernard '15'
, giving them these belief states:
told('May')
{'May 15', 'May 16', 'May 19'}
told('15')
{'August 15', 'May 15'}
We can then check whether Albert and Bernard's statements are true, given this date. The first part of Albert's first statement is "I don't know when Cheryl's birthday is." We can verify that that part of the statement is true (given that Albert was told "May"):
not know(told('May'))
True
If the rest of the statements worked out to be true, then 'May 15'
would be a solution to the puzzle. If not, it must be one of the other dates.
Here is the main function, cheryls_birthday
, which computes the subset of dates in the global variable dates
that satisfy statements 3 through 5. We will define a statement as a boolean function that takes a single date as input and returns true if the statement would be true in the condition that the given date is Cheryl's actual birthday. So a statement only has to consider one date at a time. But the code within a statement may have to consider the belief states of Albert and Bernard, to determine if the statement is true.
The function satisfy
takes a collection of dates and some statement(s) and returns the subset of dates that satisfies all the statements.
def cheryls_birthday() -> BeliefState:
"""Return a subset of the global `dates` for which all three statements are true."""
return satisfy(dates, albert1, bernard1, albert2)
def satisfy(some_dates, *statements) -> BeliefState:
"""Return the subset of dates that satisfy all the statements."""
return {date for date in some_dates
if all(statement(date) for statement in statements)}
The function albert1
takes as input a single 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 it in a form that uses the concepts we have defined:
Albert: After Cheryl told me the month of her birthdate, my belief state was such that I didn't know her birthday. And I know that Bernard does not know; in other words he could not make the statement that he knows. How do I know that? I can see that for all the possible dates in my belief state, if Bernard was told the day of that date, he would not know Cheryl's birthday.
That I can translate directly into code:
def albert1(date) -> bool:
"Albert: I don't know when Cheryl's birthday is, and I know that Bernard does not know."
albert_beliefs = told(month(date))
return not know(albert_beliefs) and not satisfy(albert_beliefs, bernard_knows)
def bernard_knows(date) -> bool: return know(told(day(date)))
We haven't solved the puzzle yet, but let's take a peek and see which dates satisfy Albert's statement:
satisfy(dates, albert1)
{'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. After I heard Albert's statement, I updated my belief state, and now I know.
def bernard1(date) -> bool:
"Bernard: At first I don't know when Cheryl's birthday is, but I know now."
at_first_beliefs = told(day(date))
after_beliefs = satisfy(at_first_beliefs, albert1)
return not know(at_first_beliefs) and know(after_beliefs)
Let's see which dates satisfy both Albert and Bernard's statements:
satisfy(dates, albert1, bernard1)
{'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. We'll need more information (coming in statement albert2
) before we know.
Albert is saying that after hearing the month and Bernard's statement, he now knows Cheryl's birthday:
def albert2(date) -> bool:
"Albert: Then I also know when Cheryl's birthday is."
then = satisfy(told(month(date)), bernard1)
return know(then)
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
Here's another puzzle that seems to have a very similar format:
- Steve tells Alice the hour of his bus departure and he tells Annie at which minute it leaves. He also tells them both that the bus leaves between 06:00 and 10:00.
- Alice and Annie consult the timetable and find the following services between those two time: 06:32 06:43 06:50 07:17 07:46 08:19 08:32 09:17 09:19 09:50.
- Alice then says “I don’t know when Steve’s bus leaves but I am sure that neither does Annie”
- Annie Replies “I didn’t know his bus, but now I do”
- Alice responds “Now I do as well!”
- When is Steve’s bus?
Upon closer inspection, not only is it a similar format, it is exactly the same puzzle, except that months are changed to hours and days to minutes. If we rewrite the times in the same format as dates
, we can solve the problem without writing a single line of new code:
times = '06:32 06:43 06:50 07:17 07:46 08:19 08:32 09:17 09:19 09:50'.split()
dates = [time.replace(':', ' ') for time in times]
cheryls_birthday()
{'08 32'}
Steve took the 8:32 bus.
Again, we can solve this problem just by changing the format of dates
:
pads = 'A2 A3 A6 B4 B5 C1 C3 D1 D2 D4'.split()
dates = [L+' '+N for L,N in pads]
cheryls_birthday()
{'C 3'}
Mad scientist Cheryl was refering to pad C3. (But may I point out that this Cheryl is not actually a mad scientist, just a mad engineer. A true mad scientist would kill 25 people and use the other 25 as a control group.)