{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "
Peter Norvig
April 2015
\n", "\n", "# When is Cheryl's Birthday?\n", "\n", "\n", "**[This logic puzzle](https://en.wikipedia.org/wiki/Cheryl%27s_Birthday)** has been making the rounds:\n", "\n", "1. Albert and Bernard became friends with Cheryl, and want to know when her birthday is. Cheryl gives 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", "3. **Cheryl** then privately tells Albert the month and Bernard the day of her birthday.\n", "4. **Albert**: \"I don't know when Cheryl's birthday is, and I know that Bernard does not know.\"\n", "5. **Bernard**: \"At first I didn't know when Cheryl's birthday is, but I know now.\"\n", "6. **Albert**: \"Then I also know when Cheryl's birthday is.\"\n", "7. So when is Cheryl's birthday?\n", "\n", "This puzzle is designed for a paper-and-pencil solution, but I'm going to solve it with code; code is more flexible and can be used to solve other similar puzzles. Let's work through the puzzle line by line.\n", "\n", "## 1. Cheryl gives Albert and Bernard a list of 10 possible dates:\n", "\n", "The result of this is that Albert and Bernard each know the birthday is one of ten dates, but they don't know which date. We'll call a set of possible dates a **belief state**. As additional statements are made, each character's belief state will change. When someone has a belief state with just one possibility, we say they **know** the true value.\n" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "BeliefState = set # A set of possible values\n", "\n", "DATES = BeliefState({'May 15', 'May 16', 'May 19', 'June 17', 'June 18', \n", " 'July 14', 'July 16', 'August 14', 'August 15', 'August 17'})\n", "\n", "def know(beliefs: BeliefState) -> bool:\n", " \"\"\"A person `knows` the correct value if their belief state has only one possibility.\"\"\"\n", " return len(beliefs) == 1" ] }, { "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: str) -> str: return date.split()[0]\n", "def day(date: str) -> str: return date.split()[1]\n", "\n", "assert month('May 15') == 'May'\n", "assert day('May 15') == '15'" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 2. Cheryl then privately tells Albert the month and Bernard the day of her birthday.\n", "\n", "We can define the idea of Cheryl having **told** someone a component of her birthdate, thus updating their belief state:" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "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}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "(*Note*: I dislike it that the function `told` uses the global constant `DATES`. But I can live with it.)\n", "\n", "Let's consider `'May 15'` as a possible birthdate. Cheryl tells Albert `'May'` and Bernard `'15'`, so they would have these belief states, and they would not *know* the birthday:" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": [ "assert told('May') == {'May 15', 'May 16', 'May 19'} # Albert's belief state\n", "assert told('15') == {'August 15', 'May 15'} # Bernard's belief state\n", "assert not know(told('May')) # Albert does not know\n", "assert not know(told('15')) # Bernard does not know" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now consider `'June 18'`; in this case, Bernard would *know*." ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [], "source": [ "assert told('June') == {'June 17', 'June 18'} # Albert's belief state\n", "assert told('18') == {'June 18'} # Bernard's belief state\n", "assert not know(told('June')) # Albert does not know\n", "assert know(told('18')) # Bernard DOES know" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Overall Strategy\n", "\n", "The puzzle is tricky because we're dealing with two types of uncertainty:\n", "\n", "1. Albert and Bernard are initially 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 by Cheryl. *(They know something we don't know.)*\n", "\n", "If Cheryl tells Albert that the month is \"May\", his belief state becomes {May 15, May 16, May 19}. But we the puzzle solvers don't know what month he was told. To deal with this we will consider each of the ten dates one at a time and reason as follows: \n", "- For each date, we know what Albert and Bernard were told; we have eliminated the second type of uncertainty. \n", "- We can thus figure out if Albert and Bernard's statements are true (given this date). \n", "- There should be only one date out of the ten that makes all the statements true; that's Cheryl's birthday.\n", "\n", "Here is the main function, `cheryls_birthday`, which computes the subset of possible dates that satisfy Albert and Bernard's statements. We will implement a **statement** as a boolean function that takes a single date as input and returns true if the statement would be true under the condition that the given date is Cheryl's actual birthday. " ] }, { "cell_type": "code", "execution_count": 6, "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", "## TODO: Implement statements albert1, bernard1, albert2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The function `satisfy` takes a belief state and some statements and returns the subset that satisfies all the statements:" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [], "source": [ "def satisfy(beliefs: BeliefState, *statements) -> BeliefState:\n", " \"\"\"Return the subset of values in `beliefs` that satisfy all the statements.\"\"\"\n", " return {value for value in beliefs if all(statement(value) 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": [ "Let's first rephrase this statement to use the concepts we have defined:\n", "\n", "**Albert**: *After Cheryl **told** me the **month** of her birthdate, my **belief state** is a set of dates such that I didn't **know** her birthday. And I know that Bernard does not know. How do I know that? I can see that there are no possible dates that Bernard would **know** Cheryl's birthday if he was **told** the **day** of that date.*\n", "\n", "That I can translate directly into code:" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [], "source": [ "def albert1(date: str) -> bool:\n", " \"\"\"Albert: I don't know when Cheryl's birthday is, and I know that Bernard does not know.\"\"\"\n", " dates = told(month(date))\n", " return not know(dates) and not satisfy(dates, lambda date: 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 first statement:" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'August 14', 'August 15', 'August 17', 'July 14', 'July 16'}" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "satisfy(DATES, albert1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 4. Bernard: At first I didn'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": 10, "metadata": {}, "outputs": [], "source": [ "def bernard1(date: str) -> bool:\n", " \"Bernard: At first I don't know when Cheryl's birthday is, but I know now.\"\n", " at_first = told(day(date))\n", " now = satisfy(at_first, albert1)\n", " return not know(at_first) and know(now)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's see which dates satisfy the two statements:" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'August 15', 'August 17', 'July 16'}" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "satisfy(DATES, albert1, bernard1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Wait a minute–I thought that Bernard **knew**?! Why are there **three** possible dates? \n", "\n", "According to the puzzle, Bernard does indeed know; it is just that we, the puzzle solvers, don't know yet. That's because Bernard was told 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'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", "A paraphrase:\n", "\n", "**Albert**: *After being **told** the **month** and hearing Bernard's **statement**, I now **know** Cheryl's birthday.*" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [], "source": [ "def albert2(date: str) -> bool:\n", " \"Albert: Then I also know when Cheryl's birthday is.\" \n", " now = satisfy(told(month(date)), bernard1)\n", " return know(now)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 6. So when is Cheryl's birthday?\n", "\n" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'July 16'}" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "cheryls_birthday()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Success!** We have deduced that Cheryl's birthday is **July 16**. We know Cheryl's birthday:" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [], "source": [ "assert know(cheryls_birthday())" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "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.8.15" } }, "nbformat": 4, "nbformat_minor": 4 }