# 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:

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.

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

.