Cheryl's Birthday

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").