Skip to content

Instantly share code, notes, and snippets.

@di
Created April 15, 2015 20:57
Show Gist options
  • Save di/56172003bc38f33238ef to your computer and use it in GitHub Desktop.
Save di/56172003bc38f33238ef to your computer and use it in GitHub Desktop.
Chery's Birthday Problem
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment