Cheryl’s Birthday

How to solve the Cheryl’s Birthday puzzle programmatically.

1. 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

1. Cheryl then tells Albert and Bernard separately the month and the day of the birthday respectively.
2. Albert: I don’t know when Cheryl’s birthday is, but I know that Bernard does not know too.
3. Bernard: At first I don’t know when Cheryl’s birthday is, but I know now.
4. Albert: Then I also know when Cheryl’s birthday is.
5. 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

{August 14,
 August 15,
 August 17,
 July 14,
 July 16,
 June 17,
 June 18,
 May 15,
 May 16,
 May 19}

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)

{June 18, May 19}

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

{August 14, August 15, August 17, July 14, July 16}

# 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

{August 15, August 17, July 16}

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

{July 16}

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

{July 16}