ipynb/Cheryl.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div align=\"right\" style=\"text-align: right\"><i>Peter Norvig<br>April 2015<br>Python 3: Feb 2019<br>Steve's bus: Apr 2020<br>Mad Cheryl: May 2020</i></div>\n",
    "\n",
    "# When is Cheryl's Birthday?\n",
    "\n",
    "\n",
    "**[This puzzle](https://www.google.com/webhp?#q=cheryl%27s%20birthday)** has been making the rounds:\n",
    "\n",
    "> 1. Albert and Bernard became friends with Cheryl, and want to know when her birthday is. Cheryl gave them a list of 10 possible dates:\n",
    "           May 15     May 16     May 19\n",
    "          June 17    June 18\n",
    "          July 14    July 16\n",
    "        August 14  August 15  August 17\n",
    "> 2. **Cheryl** then privately tells Albert the month and Bernard the day of her birthday.\n",
    "> 3. **Albert**: \"I don't know when Cheryl's birthday is, and I know that Bernard does not know.\"\n",
    "> 4. **Bernard**: \"At first I don't know when Cheryl's birthday is, but I know now.\"\n",
    "> 5. **Albert**: \"Then I also know when Cheryl's birthday is.\"\n",
    "> 6. So when is Cheryl's birthday?\n",
    "\n",
    "Let's work through the puzzle line by line.\n",
    "\n",
    "\n",
    "\n",
    "## 1. Cheryl gave them a list of 10 possible dates:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "dates = ['May 15',    'May 16',    'May 19',\n",
    "        'June 17',   'June 18',\n",
    "        'July 14',   'July 16',\n",
    "      'August 14', 'August 15', 'August 17']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We'll define accessor functions for the month and day of a date:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def month(date): return date.split()[0]\n",
    "def day(date):   return date.split()[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'May'"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "month('May 15')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'15'"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "day('May 15')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Cheryl then tells Albert and Bernard separately the month and the day of the birthday respectively.\n",
    "\n",
    "Now we have to think really carefully about what we're doing. The puzzle is tricky because we're dealing with two types of uncertainty:\n",
    "\n",
    "1. Albert and Bernard are uncertain about the birthdate. *(Cheryl knows something they don't know.)*\n",
    "2. We, the puzzle solvers don't know what Albert and Bernard were told. *(They know something we don't know.)*\n",
    "\n",
    "If Cheryl tells Albert \"May\", then he believes the birthdate could be either May 15, May 16, or May 19. We'll call `{'May 15', 'May 16', 'May 19'}` his **belief state** about the birthdate. We will say that a person **knows** the birthdate when they get down to a belief state with exactly one possibility. The type 2 uncertainty is that we don't know that Albert was told \"May\", so we have uncertainty about his belief state. But we do know some statements about his belief state, and our task is to use those statements to solve the puzzle. \n",
    "\n",
    "The way we will deal with our uncertainty as puzzle solvers is by considering each of the ten dates one at a time and reasoning as follows: \n",
    "- If this date were Cheryl's true birthdate, then we would know what Albert and Bernard were told: we would eliminate the type 2 uncertainty, and we could figure out their belief states. \n",
    "- From that we could figure out if the statements are true (given this date). \n",
    "- If the puzzle is correct and we don't make mistakes, then there will be only one date that makes all the statements true; that's Cheryl's birthday.\n",
    "\n",
    "We can define the idea of Cheryl having **told** someone a component of her birthdate, and  the idea of **knowing** a birthdate as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "BeliefState = set\n",
    "\n",
    "def told(part: str) -> BeliefState:\n",
    "    \"\"\"Cheryl told a part of her birthdate to someone; return a belief state of possible dates.\"\"\"\n",
    "    return {date for date in dates if part in date}\n",
    "\n",
    "def know(beliefs: BeliefState) -> bool:\n",
    "    \"\"\"A person `knows` the answer if their belief state has only one possibility.\"\"\"\n",
    "    return len(beliefs) == 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(Note: one thing I dislike about my code is that `told` uses the global `dates`. Later we will see that `cheryls_birthday` does the same. For that to be an acceptable design choice, we need to think of `dates` as a constant, not a variable.)\n",
    "\n",
    "Let's see what happens as we consider the date `'May 15'`:\n",
    "\n",
    "Cheryl tells Albert `'May'` and Bernard `'15'`, giving them these belief states:  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'May 15', 'May 16', 'May 19'}"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "told('May')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'August 15', 'May 15'}"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "told('15')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can then check whether Albert and Bernard's statements  are true, given this date.  The first part of Albert's first statement is  \"I don't know when Cheryl's birthday is.\" We can verify that that part of the statement is true (given that Albert was told \"May\"):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "not know(told('May'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If the rest of the statements worked out to be true, then `'May 15'` would be a solution to the puzzle.  If not, it must be one of the other dates."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Overall Strategy\n",
    "\n",
    "Here is the main function, `cheryls_birthday`, which computes the subset of dates in the global variable `dates` that satisfy statements 3 through 5.  We will define a **statement** as a boolean function that takes a single date as input and returns true if the statement would be true in the condition that the given date is Cheryl's actual birthday. So a statement only has to consider one date at a time. But the code within a statement may have to consider the belief states of Albert and Bernard, to determine if the statement is true.\n",
    "\n",
    "The function `satisfy` takes a collection of dates and some statement(s) and returns the subset of dates that satisfies all the statements."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cheryls_birthday() -> BeliefState:\n",
    "    \"\"\"Return a subset of the global `dates` for which all three statements are true.\"\"\"\n",
    "    return satisfy(dates, albert1, bernard1, albert2)\n",
    "\n",
    "def satisfy(some_dates, *statements) -> BeliefState:\n",
    "    \"\"\"Return the subset of dates that satisfy all the statements.\"\"\"\n",
    "    return {date for date in some_dates\n",
    "            if all(statement(date) for statement in statements)}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Albert: I don't know when Cheryl's birthday is, and I know that Bernard does not know."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The function `albert1` takes as input a single possible birthdate and returns `True` if Albert's statement is true for that birthdate. How do we go from Albert's English statement to a Python function? Let's paraphrase it in a form that uses the concepts we have defined:\n",
    "\n",
    "> **Albert**: After Cheryl **told** me the **month** of her birthdate, my **belief state** was such that I didn't **know** her birthday.  And I know that Bernard does not know; in other words he could not make the statement that he knows. How do I know that? I can see that for all the possible dates in my **belief state**, if Bernard was **told** the **day** of that date, he would **not know** Cheryl's birthday.\n",
    "\n",
    "That I can translate directly into code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def albert1(date) -> bool:\n",
    "    \"Albert: I don't know when Cheryl's birthday is, and I know that Bernard does not know.\"\n",
    "    albert_beliefs = told(month(date))\n",
    "    return not know(albert_beliefs) and not satisfy(albert_beliefs, bernard_knows)\n",
    "\n",
    "def bernard_knows(date) -> bool: return know(told(day(date))) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We haven't solved the puzzle yet, but let's take a peek and see which dates satisfy Albert's statement:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'August 14', 'August 15', 'August 17', 'July 14', 'July 16'}"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "satisfy(dates, albert1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. Bernard: At first I don't know when Cheryl's birthday is, but I know now.\n",
    "\n",
    "Again, a paraphrase:\n",
    "\n",
    "> **Bernard:** At first Cheryl **told** me the **day**, and I didn't **know**.  After I heard Albert's **statement**, I updated my **belief state**, and now I **know**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bernard1(date) -> bool:\n",
    "    \"Bernard: At first I don't know when Cheryl's birthday is, but I know now.\"\n",
    "    at_first_beliefs = told(day(date))\n",
    "    after_beliefs   = satisfy(at_first_beliefs, albert1)\n",
    "    return not know(at_first_beliefs) and know(after_beliefs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's see which dates satisfy both Albert and Bernard's statements:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'August 15', 'August 17', 'July 16'}"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "satisfy(dates, albert1, bernard1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wait a minute&mdash;I thought that Bernard **knew**?! Why are there three possible dates? \n",
    "\n",
    "Bernard does indeed know; it is just that we, the puzzle solvers, don't know.  That's because Bernard knows something we don't know: the day. If Bernard was told `'15'` then he would know `'August 15'`; if he was told `'17'` he would know `'August 17'`, and if he was told `'16'` he would know `'July 16'`. *We* don't know because we don't know which of these is the case. We'll need more information (coming in statement `albert2`) before *we* know.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5. Albert: Then I also know when Cheryl's birthday is.\n",
    "\n",
    "Albert is saying that after hearing the month and Bernard's statement, he now knows Cheryl's birthday:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def albert2(date) -> bool:\n",
    "    \"Albert: Then I also know when Cheryl's birthday is.\" \n",
    "    then = satisfy(told(month(date)), bernard1)\n",
    "    return know(then)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6. So when is Cheryl's birthday?\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'July 16'}"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cheryls_birthday()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Success!** We have deduced that Cheryl's birthday is **July 16**. It is now `True` that we know Cheryl's birthday:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "know(cheryls_birthday())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "___\n",
    "\n",
    "# New Puzzle: Steve's Bus\n",
    "\n",
    "Here's [another puzzle](https://www.reddit.com/r/riddles/comments/fw7h42/a_riddle_i_couldnt_solve/) that seems to have a very similar format:\n",
    "\n",
    "> 1. Steve tells Alice the hour of his bus departure and he tells Annie at which minute it leaves. He also tells them both that the bus leaves between 06:00 and 10:00.\n",
    "> 2. Alice and Annie consult the timetable and find the following services between those two time: 06:32 06:43 06:50 07:17 07:46 08:19 08:32 09:17 09:19 09:50.\n",
    "> 3. Alice then says “I don’t know when Steve’s bus leaves but I am sure that neither does Annie”\n",
    "> 4. Annie Replies “I didn’t know his bus, but now I do”\n",
    "> 5. Alice responds “Now I do as well!”\n",
    "> 6. When is Steve’s bus?\n",
    "\n",
    "Upon closer inspection, not only is it a similar format, it is **exactly** the same puzzle, except that months are changed to hours and days to minutes.  If we rewrite the times in the same format as `dates`, we can solve the problem without writing a single line of new code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'08 32'}"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "times = '06:32 06:43 06:50 07:17 07:46 08:19 08:32 09:17 09:19 09:50'.split()\n",
    "dates = [time.replace(':', ' ') for time in times]\n",
    "\n",
    "cheryls_birthday()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Steve took the 8:32 bus."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Another New Puzzle: Evil Mad Scientist Cheryl\n",
    "\n",
    "![](https://norvig.com/images/cheryl-trolley.png)\n",
    "\n",
    "Again, we can solve this problem just by changing the format of `dates`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'C 3'}"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pads = 'A2 A3 A6 B4 B5 C1 C3 D1 D2 D4'.split()\n",
    "dates = [L+' '+N for L,N in pads]\n",
    "\n",
    "cheryls_birthday()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Mad scientist Cheryl was refering to pad C3. (But may I point out that this Cheryl is not actually a mad scientist, just a [mad engineer](https://www.evilmadscientist.com/2015/evil-mad-engineers/). A true mad scientist would kill 25 people and use the other 25 as a control group.)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}