Cheryl's Birthday is a word problem that has been floating around the internet for the past couple of weeks that originated in Singapore math competition. I first saw the problem on Hacker News, then later in both The Guardian and The New York Times.

Frustratingly, I got the problem incorrect on my first try. I thought it would be interesting to break out the problem into pieces and see if we can write a program to find Cheryl's Birthday for us.

Problem Statement

Albert and Bernard have just become friends with Cheryl, and they want to know when her birthday is. Cheryl gives 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 day of her 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 didn't know when Cheryl's birthday is, but now I now.

Albert: Then I also know when Cheryl's birthday is.

So when is Cheryl's birthday?

By now I am sure that many of you know that the answer is "July 16".

We can encode the parameters of the question in any programming language, for this problem I chose Standard ML.

First thing first, we need a way to encode the list of possible dates. For this we can simply use a list of 2-tuples, where the 2-tuples here are defined a Month name and a day number (both of type string):

val dates = [
("May", "15"), ("May", "16"), ("May","19"),
("June", "17"), ("June", "18"),
("July", "14"), ("July", "16")
("August", "14"), ("August", "15"), ("August", "17")
];


We can also define simple accessor method to pull a single piece of the tuple out:

fun day   ((_,d)) = d
fun month ((m,_)) = m


Now we need a way to filter the list of possible dates by a piece of information that we are told. So for Albert that would be a month name, and for Bernard it would be a day number. We can define a function that filters the list of possible dates by the information that we are being told:

fun tell p =
List.filter
(fn date => (day date) = p orelse (month date) = p) dates


given a piece of information p which we here assume to be either a Month name or a Day number, look through all of the 10 possible dates and return a list of dates that match p.

> tell "May";
val it = [
("May", "15"), ("May", "16"), ("May", "19")
]: (string * string) list

> tell "15";
val it = [
("May", "15"), ("August", "15")
]: (string * string) list


We can tell a piece of information, now we need a way to know if we have found an answer.

fun know possible_dates =
(List.length possible_dates) = 1


We know that we have found the answer when we have eliminated all but 1 date.

> know (tell "May");
val it = false: bool


There are three statements that are made that must be true for us to have found the correct date:

1. Albert: I don't know when Cheryl's birthday is, but I know that Bernard does not know too.

2. Bernard: At first I don't know when Cheryl's birthday is, but I know now.

3. Albert: Then I also know when Cheryl's birthday is.

We can encode this logic in three separate functions, then to find Cheryl's birthday we simply test those functions against each possible date:

fun check_all_dates date =
(f1 date) andalso (f2 date) andalso (f3 date)

val cheryls_birthday =
List.filter (check_all_dates) dates


Now we just need to implement f1, f2, and f3:

(* I don't know when Cheryl's birthday is, but I know that Bernard does not know too *)
fun f1 date =
let
val possible_dates = tell (month date)
in
not know(possible_dates)
andalso List.all
(fn date => not (know (tell (day date)))) possible_dates
end

(* At first I don't know when Cheryl's birthday is, but I know now *)
fun f2 date =
let
val at_first = tell (day date)
in
not (know at_first) andalso know (List.filter f1 at_first)
end

(* Then I also know when Cheryl's birthday is *)
fun f3 date =
let
val possible_dates = tell (day date)
in
know (List.filter f2 possible_dates)
end


Now we can simply load our source file in the SML interpreter:

[hunter@eros: play]\$ poly --use cheryls_birthday.sml
Poly/ML 5.5.2 Release
val dates =
[("May", "15"), ("May", "16"), ("May", "19"), ("June", "17"),
("June", "18"), ("July", "14"), ("July", "16"), ("August", "14"),
("August", "15"), ("August", "17")]: (string * string) list
val check_all_dates = fn: string * string -> bool
val cheryls_birthday = [("July", "16")]: (string * string) list
val day = fn: 'a * 'b -> 'b
val f1 = fn: string * 'a -> bool
val f2 = fn: 'a * string -> bool
val f3 = fn: string * 'a -> bool
val know = fn: 'a list -> bool
val month = fn: 'a * 'b -> 'a
val tell = fn: string -> (string * string) list
>


If you examine the cheryls_birthday variable, you will see the correct answer ("July", "16").