# Cheryl's Birthday

### How to solve the Cheryl's Birthday puzzle programmatically.¶

- Albert and Bernard just became friends with Cheryl, and they 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, 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.
- So when is Cheryl's birthday?

As with the pytudes solution, the goal is to solve the puzzle in code. A different approach is taken here though, for simplicity and extensibility.

The first step is to model the data. A `set`

of `Date`

objects is suitable to represent the current possible dates. Since `datetime.date`

objects require a year, a minimal `collections.namedtuple`

is used instead.

```
from typing import NamedTuple
DATES = ['May 15', 'May 16', 'May 19',
'June 17', 'June 18',
'July 14', 'July 16',
'August 14', 'August 15', 'August 17']
class Date(NamedTuple):
month: str
day: str
def __repr__(self):
return ' '.join(self) # pretty printing
DATES = {Date(*date.split()) for date in DATES}
DATES
```

As is typical of these kinds of puzzles, it assumes all participants have perfect Theory of Mind. That is, each participant making a statement is applying their private knowledge to what is publicly known, and assuming everyone else will do the same. With that in mind, the claims made fall into 3 categories:

- I know ...
- I don't know ...
- They don't know ...

The temporal variations "now" and "at first" can be modeled by the current set of dates. Any claim then can be implemented functionally in this form:

```
def claim(field: str, dates: set) -> set:
"""Return subset of possible dates which would make the claim true.
:param field: the field known by the claimant
:param dates: the current set of dates publicly known
"""
```

So what does it mean for Albert or Bernard to "know" the correct date? It would mean applying their knowledge of the month or day leaves only one possibility. The "I know ..." function therefore groups and filters for uniqueness.

```
import collections
def known(field, dates):
"""Return subset of possible dates which would make the claim "I know ..." true."""
counts = collections.Counter(getattr(date, field) for date in dates)
return {date for date in dates if counts[getattr(date, field)] == 1}
# test what is already publicly known
assert known('month', DATES) == set()
known('day', DATES)
```

To implement "I don't know ...", `known`

could be parametrized with a different predicate (`> 1`

), or simply use `set.difference`

. "I don't know ..." is so trivial it's arguably not worth the abstraction.

```
def unknown(field, dates):
"""Return subset of possible dates which would make the claim "I don't know ..." true."""
return dates - known(field, dates)
```

The challenging part is what does it mean for Albert to claim Bernard doesn't know. All dates that would be knowable to Bernard must clearly be excluded, but Albert would have to exclude them based on his knowledge of the month. So "They don't know ..." is similar to `unknown`

, but the exclusion is based on a different field.

```
def unknowable(field, dates):
"""Return subset of possible dates which would make the claim "They don't know ..." true."""
other, = set(Date._fields) - {field}
exclude = {getattr(date, field) for date in known(other, dates)}
return {date for date in dates if getattr(date, field) not in exclude}
```

This is sufficient to simply walk through the statements, one at a time.

```
# Albert: I don't know when Cheryl's birthday is, but I know that Bernard does not know too.
dates = unknown('month', DATES)
assert dates == DATES # already public known
dates = unknowable('month', dates)
dates
```

```
# Bernard: At first I don't know when Cheryl's birthday is, but I know now.
assert dates.isdisjoint(known('day', DATES)) # already claimed by Albert
dates = known('day', dates)
dates
```

```
# Albert: Then I also know when Cheryl's birthday is.
known('month', dates)
```

Exactly one date is left, indicating success. Now the succinct in-lined version, with no superfluous statements.

```
known('month', # Albert: I know
known('day', # Bernard: I know
unknowable('month', DATES))) # Albert: Bernard doesn't know
```