Chery's Birthday Problem

cheryl.py

class Date:
    def __init__(self, day, month):
        self.day = day
        self.month = month
    def __repr__(self):
        return "(%d, %s)" % (self.day, self.month)

dates = [
    Date(15, 'may'),
    Date(16, 'may'),
    Date(19, 'may'),
    Date(17, 'jun'),
    Date(18, 'jun'),
    Date(14, 'jul'),
    Date(16, 'jul'),
    Date(14, 'aug'),
    Date(15, 'aug'),
    Date(17, 'aug'),
]

def remove_duplicate_days(xs):
    return [x for x in xs if sum(1 for d in xs if d.day == x.day) == 1]

def remove_duplicate_months(xs):
    return [x for x in xs if sum(1 for d in xs if d.month == x.month) == 1]

'''
Albert knows the month, Bernard knows the day. Albert does not know when
Cheryl's birthday is, but he knows Bernard doesn't either. This means that the
the month of Cheryl's birthday is not a month with a unique day.
'''

# Select the months which have a unique day
months_with_one_date = [date.month for date in remove_duplicate_days(dates)]
# >>> ['may', 'jun']

# Remove the dates which has a month which has a unique day
dates = [date for date in dates if date.month not in months_with_one_date]
# >>> [(14, jul), (16, jul), (14, aug), (15, aug), (17, aug)]

'''
Now, since Bernard knows the day, if it is unique, he knows the answer. He
says he knows the answer, so the day must be unique.
'''

# Remove the dates which do not have a unique day
dates = remove_duplicate_days(dates)
# >>> [(16, jul), (15, aug), (17, aug)]

'''
Now, since Albert says he knows the answer too, so the month must be unique
'''

# Remove the dates which do not have a unique month
dates = remove_duplicate_months(dates)
# >>> [(16, jul)]

'''
Only one date remains: July 16th.
'''

print dates