#!/usr/bin/env python
# coding: utf-8

# # When Cheryl Met Eve: A Birthday Story

# <div align=right>Peter Norvig, May 2015</div>
# 
# The "Cheryl's Birthday" logic puzzle  [made the rounds](https://www.google.com/webhp?#q=cheryl%27s+birthday),
# and  I wrote [code](http://nbviewer.ipython.org/url/norvig.com/ipython/Cheryl.ipynb) that solves it. There I said that one reason for solving the problem with code rather than pencil and paper is that you can do more with code.  [Gabe Gaster](http://www.gabegaster.com/) proved me right when he [tweeted](https://twitter.com/gabegaster/status/593976413314777089/photo/1)  that he had extended my code to generate a new list of dates that satisfies the constraints of the puzzle:
# <pre>
# January 15, January 4,
# July 13, July 24, July 30,
# March 13, March 24,
# May 11, May 17, May 30
# </pre>
# In this notebook, I verify Gabe's result, and find some other variations on the puzzle.

# # Code for Original Cheryl's Birthday Puzzle

# Let's recap the puzzle and the code to solve it. I've refactored my previous code, in a few ways:
# - `DATES` is now a global variable, not a constant. 
# - I switched to *sets* of possible dates, not *lists*. 
# - I define a new function, `satisfy`, which is similar to the built-in function `filter`, except that `satisfy` returns a set, not a list, and it allows you to specify more than one function that the candidate elements must satisfy.
# - I changed the name `statement3` to `albert1`, and so on.

# In[1]:


# Albert and Bernard just became friends with Cheryl, and they want to know when her birthday is. 
# Cheryl gave them a set of 10 possible dates:

from __future__ import division, print_function

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

def tell(part):
    "Cheryl tells a part of her birthdate to someone; return a new set of possible dates that match the part."
    return {date for date in DATES if part in date}

def Month(date): return date.split()[0]

def Day(date):   return date.split()[1]

def know(possible_dates):
    "A person knows the birthdate if they know there is exactly one possible date."
    return len(possible_dates) == 1

# Albert and Bernard make three statements:

def albert1(date):
    "Albert: I don't know when Cheryl's birthday is, but I know that Bernard does not know too."
    told = tell(Month(date))
    return (not know(told) 
            and all(not know(tell(Day(d)))
                    for d in told))

def bernard1(date):
    "Bernard: At first I don't know when Cheryl's birthday is, but I know now."
    at_first = tell(Day(date))
    return (not know(at_first)
            and know(satisfy(at_first, albert1)))

def albert2(date):
    "Albert: Then I also know when Cheryl's birthday is."
    return know(satisfy(tell(Month(date)), bernard1))
    
# So when is Cheryl's birthday?

def cheryls_birthday(dates):
    "Return a list of the possible dates for which Albert and Bernard's statements are true."
    global DATES
    DATES = dates # Assign to global DATES here; used by `tell`
    return satisfy(dates, albert1, bernard1, albert2)

def satisfy(items, *predicates):
    "Return the subset of items that satisfy all the predicates."
    return {item for item in items
            if all(p(item) for p in predicates)}


# In[2]:


cheryls_birthday(CHERYL_DATES)


# In[3]:


know(cheryls_birthday(CHERYL_DATES))


# # Verifying Gabe's Version

# Gabe tweeted these ten dates:

# In[4]:


GABE_DATES = [
  'January 15', 'January 4',
  'July 13',    'July 24',   'July 30',
  'March 13',   'March 24',
  'May 11',     'May 17',    'May 30']


# We can verify that they do indeed make the puzzle work, giving a single known birthdate:

# In[5]:


cheryls_birthday(GABE_DATES)


# # Creating Our Own Versions

# If Gabe can do it, we can do it!  Our strategy will be to repeatedly pick a random sample of dates, and check if they solve the puzzle. We'll limit ourselves to a subset of dates (not all 366) to make it more likely a random selection will have multiple dates with the same month and day (otherwise Albert and Bernard would know right away):

# In[6]:


some_dates = {mo + ' ' + d1 + d2
              for mo in ('March', 'April', 'May', 'June', 'July')
              for d1 in '12'
              for d2 in '56789'}


# Here's how to pick a random sample of the dates:

# In[7]:


import random

def sample(dates=some_dates, n=10):
    "Return a random sample of dates."
    return set(random.sample(dates, n))


# In[8]:


sample()


# Now we need to cycle through samples until we hit one that works.  I anticipate wanting to solve other puzzles besides the original `cheryls_birthday`, so I'll make the `puzzle` be a parameter of the function `pick_dates`. Note that `pick_dates` returns two things: the ten dates that form the puzzle, and the one date that is the solution.

# In[9]:


def pick_dates(puzzle=cheryls_birthday):
    "Pick a set of dates for which the puzzle has a unique solution."
    while True:
        dates = sample()
        solutions = puzzle(dates)
        if know(solutions):
            return dates, solutions.pop()


# In[10]:


pick_dates()


# Great! We can make a new puzzle, just like Gabe.  But how often do we get a unique solution to the puzzle (that is, the puzzle returns a set of size 1)?  How often do we get a solution where Albert and Bernard know, but we the puzzle solver doesn't (that is, a set of size greater than 1)?  How often is there no solution (size 0)? Let's make a Counter of the number of times each length-of-solution occurs:

# In[11]:


from collections import Counter

def counter(puzzle=cheryls_birthday, N=10000):
    "Try N random samples and count how often each possible length-of-solution appears."
    return dict(Counter(len(puzzle(sample())) 
                for _ in range(N)))


# In[12]:


counter(cheryls_birthday)


# This says that about 6% of the time we get a unique solution (a set of `len` 1). A little more often than that we get an ambiguous solution (with 2 or more possible birth dates).  And most of the time, the sample of dates leads to no solution.

# # A New Puzzle: Enter Eve

# Now let's see if we can create a more complicated puzzle. We'll introduce a new character, Eve, give her a statement, and alter the rest of the puzzle slightly:
# 
# *Albert and Bernard just became friends with Cheryl, and they want to know when her birthday is. Cheryl wrote down a list of 10 possible dates for all to see.*
#     
# *Cheryl then writes down the month and shows it just to Albert, and also writes down the day and shows it just to Bernard.*
# 
# **Albert**: *I don't know when Cheryl's birthday is, but I know that Bernard does not know either.*
# 
# **Bernard**: *At first I didn't know when Cheryl's birthday is, but I know now.*
#     
# **Albert**: *Then I also know when Cheryl's birthday is.*
# 
# **Eve**: *Hi, my name is Eve and I'm an evesdropper. It's what I do! I peeked and saw the first letter of the month and the first digit of the day. When I peeked, I didn't know Cheryl's birthday, but after listening to Albert and Bernard I do.  And it's a good thing I peeked, because I couldn't have
# figured it out without peeking.*
#     
# *So when is Cheryl's birthday?*
# 
# We can easily code this up:

# In[13]:


def cheryls_birthday_with_eve(dates):
    "Return a list of the possible dates for which Albert, Bernard, and Eve's statements are true."
    global DATES
    DATES = dates
    return satisfy(dates, albert1, bernard1, albert2, eve1)

def eve1(date):
    """Eve: I peeked and saw the first letter of the month and the first digit of the day. 
    When I peeked, I didn't know Cheryl's birthday, but after listening to Albert and Bernard I do. 
    And it's a good thing I peeked, because I couldn't have figured it out without peeking."""
    at_first = tell(first(Day(date))) & tell(first(Month(date)))
    return (not know(at_first)
            and know(satisfy(at_first, albert1, bernard1, albert2)) and
            not know(satisfy(tell(''), albert1, bernard1, albert2)))

def first(seq): return seq[0]


# *Note*: I admit I "cheated" a bit here.  Remember that the function `tell`  tests for `(part in date)`.  For that to work for Eve, we have to make sure that the first letter is distinct from any other character in the date (it is&mdash;because only the first letter is uppercase) and that the first digit is distinct from any other character (it is&mdash;because in `some_dates` I carefully made sure that the first digit is always 1 or 2, and the second digit is never 1 or 2). Also note that `tell('')` denotes the hypothetical situation where Cheryl told Eve nothing, and thus is equal to `DATES`.
# 
# I have no idea if it is possible to find a set of dates that works for this puzzle. But I can try:

# In[14]:


pick_dates(puzzle=cheryls_birthday_with_eve)


# That was easy.  How often is a random sample of dates a solution to this puzzle?

# In[15]:


counter(cheryls_birthday_with_eve)


# About half as often as for the original puzzle.

# # An Even More Complex Puzzle

# Let's make the puzzle even more complicated by making Albert wait one more time before he finally knows:
# 
# *Albert and Bernard just became friends with Cheryl, and they want to know when her birtxhday is. Cheryl wrote down a list of 10 possible dates for all to see.*
#     
# *Cheryl then writes down the month and shows it just to Albert, and also writes down the day and shows it just to Bernard.*
#     
# **Albert**: *I don't know when Cheryl's birthday is, but I know that Bernard does not know either.*
#     
# **Bernard**: *At first I didn't know when Cheryl's birthday is, but I know now.*
#     
# **Albert**: *I still don't know.*
# 
# **Eve**: *Hi, my name is Eve and I'm an evesdropper. It's what I do! I peeked and saw the first letter of the month and the first digit of the day. When I peeked, I didn't know Cheryl's birthday, but after listening to Albert and Bernard I do.  And it's a good thing I peeked, because I couldn't have figured it out without peeking.*
# 
# **Albert**: *OK, now I know.*
#     
# *So when is Cheryl's birthday?*
# 
# Let's be careful in coding this up; Albert's second statement is different; he has a new third statement; and Eve's statement uses the same words, but it now implicitly refers to a different statement by Albert. We'll use the names `albert2c`,  `eve1c`, and `albert3c` (`c` for "complex") to represent the new statements:

# In[16]:


def cheryls_birthday_complex(dates):
    "Return a list of the possible dates for which Albert, Bernard, and Eve's statements are true."
    global DATES
    DATES = dates
    return satisfy(dates, albert1, bernard1, albert2c, eve1c, albert3c)

def albert2c(date):
    "Albert: I still don't know."
    return not know(satisfy(tell(Month(date)), bernard1))

def eve1c(date):
    """Eve: I peeked and saw the first letter of the month and the first digit of the day. 
    When I peeked, I didn't know Cheryl's birthday, but after listening to Albert and Bernard I do. 
    And it's a good thing I peeked, because I couldn't have figured it out without peeking."""
    at_first = tell(first(Day(date))) & tell(first(Month(date)))
    return (not know(at_first)
            and know(satisfy(at_first, albert1, bernard1, albert2c)) and
            not know(satisfy(tell(''), albert1, bernard1, albert2c)))

def albert3c(date):
    "Albert: OK, now I know."
    return know(satisfy(tell(Month(date)), eve1c))


# Again, I don't know if it is possible to find dates that works with this story, but I can try:

# In[17]:


pick_dates(puzzle=cheryls_birthday_complex)


# It worked!  Were we just lucky, or are there many sets of dates that work?

# In[18]:


counter(cheryls_birthday_complex)


# Interesting. It was actually easier to find dates that work for this story than for either of the other stories.

# ## Analyzing a Solution to the Complex Puzzle

# Now we will go through a solution step-by-step.  We'll use a set of dates selected in a previous run:

# In[19]:


DATES = {
  'April 28',
  'July 27',
  'June 19',
  'June 16',
  'July 15',
  'April 15',
  'June 29',
  'July 16',
  'May 24',
  'May 27'}


# Let's find the solution:

# In[20]:


cheryls_birthday_complex(DATES)


# Now the first step is that Albert was told "July":

# In[21]:


tell('July')


# And no matter which of these three dates is the actual birthday, Albert knows that Bernard would not know the birthday, because each of the days (15, 16, 27) appears twice in the list of possible dates.

# In[22]:


all(not know(tell(Day(d)))
    for d in tell('July'))


# Next, Bernard is told the day:

# In[23]:


tell('27')


# There are two dates with a 27, so Bernard did not know then. But only one of these dates satisfies Albert's statement:

# In[24]:


satisfy(tell('27'), albert1)


# So now Bernard knows. Poor Albert still doesn't know:

# In[25]:


satisfy(tell('July'), bernard1)


# Then along comes Eve. She evesdrops the "J" and the "2":

# In[26]:


tell('J') & tell('2')


# Two dates, so Eve doesn't know yet. But only one of the dates satisfies the statements:

# In[27]:


satisfy(tell('J') & tell('2'), albert1, bernard1, albert2c)


# But she wouldn't have known if she had been told nothing:

# In[28]:


satisfy(tell(''), albert1, bernard1, albert2c)


# What about Albert?  After hearing Eve's statement he finally knows:

# In[29]:


satisfy(tell('July'), eve1c)


# # What Next?

# If you like, there are many other directions you could take this:
# 
# - Could you create a puzzle that goes one or two rounds more before everyone knows?
# - Could you add new characters: Faith, and then George, and maybe even a new Hope?
# - Would it be more interesting with a different number of possible dates (not 10)?
# - Should we include the year or the day of the week, as well as the month and day?
# - Perhaps a puzzle that starts with [Richard Smullyan](http://en.wikipedia.org/wiki/Raymond_Smullyan) announcing that one of the characters is a liar.
# - Or you could make a puzzle harder than [the hardest logic puzzle ever](https://en.wikipedia.org/wiki/The_Hardest_Logic_Puzzle_Ever).
# - It's up to you ...

# In[ ]: