{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "
Peter Norvig
May 2015
Updated: 2020, 2025
\n", "\n", "# When Cheryl Met Eve: A Birthday Story\n", "\n", "The ***Cheryl's Birthday*** logic puzzle [made the rounds](https://www.google.com/search?q=cheryl%27s+birthday),\n", "and I wrote [code](Cheryl.ipynb) that solves it. In that notebook I said that one reason for solving the puzzle 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 used my code to generate a new list of dates that satisfies the constraints of the puzzle:\n", "\n", " January 15, January 4,\n", " July 13, July 24, July 30,\n", " March 13, March 24,\n", " May 11, May 17, May 30\n", "\n", "In this notebook, I verify Gabe's result, and explore some other variations on the puzzle.\n", "\n", "First, let's recap [the original Cheryl's Birthday puzzle](https://en.wikipedia.org/wiki/Cheryl%27s_Birthday):\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?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Code for Original Cheryl's Birthday Puzzle" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This is a slight modification of my [previous code](Cheryl.ipynb). The puzzle concerns these key concepts:\n", "\n", "- **Possible dates** that might be Cheryl's birthday.\n", "- **Knowing** which dates are still possible; knowing for sure when only one is possible.\n", "- **Telling** Albert and Bernard specific facts about the birthday.\n", "- **Statements** made by Albert or Bernard about their knowledge of the birthday.\n", "\n", "I implement them as follows:\n", "- The global variable `DATES` is a set of all possible dates (each date is a string).\n", "- `know(possible_dates)` is a function that returns `True` when there is only one possible date.\n", "- `told(part)` is a function that returns the set of possible dates that remain after Cheryl tells a part (month or day).\n", "- A statement is a function, *statement*`(date)`, that returns true if the statement is true given that `date` is Cheryl's birthday.\n", "- `satisfy(possible_dates, statement,...)` returns a subset of possible_dates for which all the statements are true.\n", "\n", "In the [previous code](Cheryl.ipynb) I treated `DATES` as a constant, but in this version the whole point is exploring different sets of possible dates. The easiest way to refactor the code was to keep `DATES` as a global variable, and provide the function `set_dates` to set the value of the global variable. (It would be cleaner to package the dates into a non-global object, but it would be a big change to the code to inject this all the way down to the function `told`, where it is needed.)" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "BeliefState = set # A set of possible values that a person believes might be the birthday\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\n", "\n", "def month(date) -> str: return date.split()[0]\n", "def day(date) -> str: return date.split()[1]\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 cheryls_birthday(dates: BeliefState) -> BeliefState:\n", " \"\"\"Return a subset of the dates for which all three statements are true.\"\"\"\n", " return satisfy(set_dates(dates), albert1, bernard1, albert2)\n", "\n", "def set_dates(dates: BeliefState) -> BeliefState: \n", " \"\"\"Set the global variable DATES to dates.\"\"\"\n", " global DATES\n", " DATES = dates\n", " return dates\n", "\n", "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)}\n", "\n", "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))))\n", "\n", "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)\n", "\n", "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": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "# Some simple tests\n", "\n", "assert month('May 19') == 'May'\n", "assert day('May 19') == '19'\n", "\n", "assert told('May') == {'May 15', 'May 16', 'May 19'} # Albert's belief state for May 15\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\n", "\n", "assert told('June') == {'June 17', 'June 18'} # Albert's belief state for June 18\n", "assert told('18') == {'June 18'} # Bernard's belief state for June 18\n", "assert not know(told('June')) # Albert does not know\n", "assert know(told('18')) # Bernard DOES know" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Below we trace through how this works.\n", "\n", "First Albert says that he doesn't know, and that Bernard doesn't either. So the possible remaining dates are:" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'August 14', 'August 15', 'August 17', 'July 14', 'July 16'}" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "satisfy(DATES, albert1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Bernard says he initially didn't know, but now he does. He knows, but we the puzzle-solvers don't. The remaining possible dates for us are:" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'August 15', 'August 17', 'July 16'}" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "satisfy(DATES, albert1, bernard1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now Albert knows, and so do we:" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'July 16'}" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "satisfy(DATES, albert1, bernard1, albert2)" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [], "source": [ "assert cheryls_birthday(DATES) == {'July 16'}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Verifying Gabe's Version" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Gabe Gaster tweeted these ten dates:" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [], "source": [ "gabe_dates = [\n", " 'January 15', 'January 4',\n", " 'July 13', 'July 24', 'July 30',\n", " 'March 13', 'March 24',\n", " 'May 11', 'May 17', 'May 30']" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can verify that they do indeed make the puzzle work:" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [], "source": [ "assert know(cheryls_birthday(gabe_dates))\n", "assert cheryls_birthday(gabe_dates) == {'July 30'}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Creating Our Own Versions" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "If Gabe can do it, so can we! 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 that a random selection will have multiple dates with the same month and day (otherwise Albert and/or Bernard would know right away):" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "96" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "many_dates = {mo + ' ' + tens + ones\n", " for mo in {'April', 'August', 'July', 'June', 'March', 'May'}\n", " for tens in '12'\n", " for ones in '34567890'}\n", "\n", "len(many_dates)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now we need to cycle through random samples of these possible dates until we hit one that works. I anticipate wanting to solve other puzzles besides the original `cheryls_birthday`, so I'll define the function `good_dates` to take a parameter, `puzzle`, and keep trying a set of `n` random dates until we `know(puzzle(random_dates))`:" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [], "source": [ "import random\n", "\n", "def good_dates(puzzle, n=10) -> BeliefState:\n", " \"\"\"Pick a set of `n` dates for which the `puzzle` has a unique solution.\"\"\"\n", " while True:\n", " random_dates = set(random.sample(many_dates, n))\n", " if know(puzzle(random_dates)):\n", " return random_dates" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'April 13',\n", " 'April 17',\n", " 'April 29',\n", " 'August 23',\n", " 'June 10',\n", " 'June 23',\n", " 'June 28',\n", " 'March 10',\n", " 'March 28',\n", " 'May 27'}" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "good_dates(cheryls_birthday)" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'August 27', 'August 29', 'July 18', 'July 27', 'July 29', 'March 18'}" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "good_dates(cheryls_birthday, n=6)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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 don't know (that is, a belief set of size greater than 1)? How often is there no solution (a set of size 0)? Let's make a Counter of the number of times each length-of-solution occurs:" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [], "source": [ "from collections import Counter\n", "\n", "def solution_lengths(puzzle, N=10000, n=10, many_dates=many_dates):\n", " \"\"\"Try N random samples of k dates and count how often each possible \n", " length-of-puzzle-solution appears.\"\"\"\n", " solutions = (puzzle(random.sample(many_dates, n)) for _ in range(N))\n", " return Counter(sorted(map(len, solutions)))" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Counter({0: 9595, 1: 146, 2: 259})" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "solution_lengths(cheryls_birthday)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This says that a bit over 1% of the time we get a unique solution (a set of length 1). More often than that we get an ambiguous solution (with 2 or more possible birth dates), and about 95% of the time the sample of dates has no solution (a set of length 0).\n", "\n", "What happens if Cheryl changes the number of possible dates? Let's try 6 possible dates:" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Counter({0: 99914, 1: 18, 2: 68})" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "solution_lengths(cheryls_birthday, n=6, N=100_000)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "With 6 dates, we get no solution 99.9% of the time, but there are a few good solutions (of length 1). Let's try a whole range of values for `n`:" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{4: Counter({0: 10000}),\n", " 5: Counter({0: 10000}),\n", " 6: Counter({0: 9996, 1: 1, 2: 3}),\n", " 7: Counter({0: 9972, 1: 5, 2: 23}),\n", " 8: Counter({0: 9881, 1: 40, 2: 79}),\n", " 9: Counter({0: 9782, 1: 65, 2: 153}),\n", " 10: Counter({0: 9617, 1: 135, 2: 248}),\n", " 11: Counter({0: 9403, 1: 229, 2: 366, 3: 2}),\n", " 12: Counter({0: 9173, 1: 317, 2: 506, 3: 4}),\n", " 13: Counter({0: 8888, 1: 537, 2: 562, 3: 13}),\n", " 14: Counter({0: 8633, 1: 685, 2: 645, 3: 36, 4: 1}),\n", " 15: Counter({0: 8377, 1: 870, 2: 711, 3: 42})}" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "{n: solution_lengths(cheryls_birthday, n=n) for n in range(4, 16)}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We found no solutions with 4 or 5 dates (although we haven't proven it is impossible). In general, the more dates, the more good solutions." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# A New Birthday Puzzle: All About Eve" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's create a more complicated puzzle. We'll introduce a new character, Eve, and keep the same puzzle as before, except that after Albert's second statement, Eve says:\n", "\n", "- **Eve**: \"Hi, Everybody. 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 otherwise I couldn't have\n", "figured it out.\"\n", "\n", "We can easily code this up:" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [], "source": [ "def cheryls_birthday_with_eve(dates):\n", " \"Return a set of the dates for which Albert, Bernard, and Eve's statements are true.\"\n", " return satisfy(set_dates(dates), albert1, bernard1, albert2, eve1)\n", "\n", "def eve1(date):\n", " \"\"\"Eve: I peeked and saw the first letter of the month and the first digit of the day. \n", " When I peeked, I didn't know Cheryl's birthday, but after listening to Albert and Bernard \n", " I do. And it's a good thing I peeked, because otherwise I couldn't have figured it out.\"\"\"\n", " at_first = told(first_character(day(date))) & told(first_character(month(date)))\n", " return (not know(at_first) and\n", " know(satisfy(at_first, albert1, bernard1, albert2)) and\n", " not know(satisfy(DATES, albert1, bernard1, albert2)))\n", "\n", "def first_character(part: str) -> str: return part[0]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Note*: I admit I \"cheated\" a bit here. Remember that the function `told` 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—because only the first letter is uppercase) and that the first digit is distinct from any other character (it is—because in `many_dates` I made sure that the first digit is always 1 or 2, and the second digit is never 1 or 2). \n", "\n", "I have no idea if it is possible to find a set of dates that works for this puzzle. But I can try:" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'April 16',\n", " 'April 25',\n", " 'August 10',\n", " 'June 10',\n", " 'June 19',\n", " 'March 14',\n", " 'March 17',\n", " 'March 25',\n", " 'May 16',\n", " 'May 17'}" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "good_dates(cheryls_birthday_with_eve)" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'May 17'}" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "cheryls_birthday_with_eve(_)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "That was easy. How often is a random sample of dates a solution to this puzzle?" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Counter({0: 9765, 1: 103, 2: 132})" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "solution_lengths(cheryls_birthday_with_eve)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "A unique solution (a set of length 1) occurs about 1% of the time." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# An Even More Complex Birthday Puzzle" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's make the puzzle even more complicated by making Albert wait one more time before he finally knows:\n", "\n", "- 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.\n", "- **Cheryl** then writes down the month and shows it just to Albert, and also writes down the day and shows it just to Bernard.\n", "- **Albert**: I don't know when Cheryl's birthday is, but I know that Bernard does not know either. \n", "- **Bernard**: At first I didn't know when Cheryl's birthday is, but I know now.\n", "- **Albert**: I still don't know.\n", "- **Eve**: Hi, Everybody. 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 otherwise I couldn't have\n", "figured it out.\n", "- **Albert**: OK, now I know.\n", "- So when is Cheryl's birthday?\n", "\n", "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`, `albert3c`, and `eve1c` (`c` for \"complex\") to represent the new statements:" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [], "source": [ "def cheryls_birthday_complex(dates):\n", " \"Return a set of the dates for which Albert, Bernard, and Eve's statements are true.\"\n", " return satisfy(set_dates(dates), albert1, bernard1, albert2c, eve1c, albert3c)\n", "\n", "def albert2c(date):\n", " \"Albert: I still don't know.\"\n", " return not know(satisfy(told(month(date)), bernard1))\n", "\n", "def eve1c(date):\n", " \"\"\"Eve: I peeked and saw the first letter of the month and the first digit of the day. \n", " When I peeked, I didn't know Cheryl's birthday, but after listening to Albert and Bernard \n", " I do. And it's a good thing I peeked, because otherwise I couldn't have figured it out.\"\"\"\n", " at_first = told(day(date)[0]) & told(month(date)[0])\n", " return (not know(at_first)\n", " and know(satisfy(at_first, albert1, bernard1, albert2c)) and\n", " not know(satisfy(DATES, albert1, bernard1, albert2c)))\n", "\n", "def albert3c(date):\n", " \"Albert: OK, now I know.\"\n", " return know(satisfy(told(month(date)), bernard1, eve1c))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Again, I don't know if it is possible to find dates that works with this story, but I can try:" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'April 15',\n", " 'August 27',\n", " 'July 17',\n", " 'March 15',\n", " 'March 16',\n", " 'March 20',\n", " 'March 26',\n", " 'May 16',\n", " 'May 17',\n", " 'May 20'}" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "good_dates(cheryls_birthday_complex)" ] }, { "cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'May 20'}" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" } ], "source": [ "cheryls_birthday_complex(_)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "It worked! Were we just lucky, or are there many sets of dates that work?" ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Counter({0: 9363, 1: 636, 2: 1})" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "solution_lengths(cheryls_birthday_complex)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Interesting. It was actually easier to find good dates for this story than for the simpler versions." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Analyzing a Solution to the Complex Puzzle" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now we will go through a solution step-by-step. We'll use these dates:" ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [], "source": [ "complex_dates = {\n", " 'April 28',\n", " 'July 27',\n", " 'June 19',\n", " 'June 16',\n", " 'July 15',\n", " 'April 15',\n", " 'June 29',\n", " 'July 16',\n", " 'May 24',\n", " 'May 27'}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's find the solution:" ] }, { "cell_type": "code", "execution_count": 26, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'July 27'}" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" } ], "source": [ "cheryls_birthday_complex(complex_dates)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now the first step is that Albert was told \"July\":" ] }, { "cell_type": "code", "execution_count": 27, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'July 15', 'July 16', 'July 27'}" ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" } ], "source": [ "told('July')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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." ] }, { "cell_type": "code", "execution_count": 28, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 28, "metadata": {}, "output_type": "execute_result" } ], "source": [ "not know(told('15')) and not know(told('16')) and not know(told('27'))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Meanwhile, Bernard is told the day:" ] }, { "cell_type": "code", "execution_count": 29, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'July 27', 'May 27'}" ] }, "execution_count": 29, "metadata": {}, "output_type": "execute_result" } ], "source": [ "told('27')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "There are two dates with a 27, so Bernard did not know then. But only one of these dates is still consistent after hearing Albert's statement:" ] }, { "cell_type": "code", "execution_count": 30, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'July 27'}" ] }, "execution_count": 30, "metadata": {}, "output_type": "execute_result" } ], "source": [ "satisfy(told('27'), albert1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "So after Albert's statement, Bernard knows. Poor Albert still doesn't know (after being told `'July'` and hearing Bernard's statement):" ] }, { "cell_type": "code", "execution_count": 31, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'July 15', 'July 16', 'July 27'}" ] }, "execution_count": 31, "metadata": {}, "output_type": "execute_result" } ], "source": [ "satisfy(told('July'), bernard1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Then along comes Eve. She evesdrops the \"J\" and the \"2\":" ] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'July 27', 'June 29'}" ] }, "execution_count": 32, "metadata": {}, "output_type": "execute_result" } ], "source": [ "told('J') & told('2')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Two dates, so Eve doesn't know after evesdropping. But only one of the dates works after hearing the three statements made by Albert and Bernard:" ] }, { "cell_type": "code", "execution_count": 33, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'July 27'}" ] }, "execution_count": 33, "metadata": {}, "output_type": "execute_result" } ], "source": [ "satisfy(told('J') & told('2'), albert1, bernard1, albert2c)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "But Eve wouldn't have known if she hadn't evesdropped:" ] }, { "cell_type": "code", "execution_count": 34, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'July 15', 'July 16', 'July 27'}" ] }, "execution_count": 34, "metadata": {}, "output_type": "execute_result" } ], "source": [ "satisfy(DATES, albert1, bernard1, albert2c)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "What about Albert? After hearing Eve's statement he finally knows:" ] }, { "cell_type": "code", "execution_count": 35, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'July 27'}" ] }, "execution_count": 35, "metadata": {}, "output_type": "execute_result" } ], "source": [ "satisfy(told('July'), eve1c)" ] }, { "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:\n", " - 06:32, 06:43, 06:50, 07:17, 07:46, 08:19, 08:32, 09:17, 09:19, 09:50.\n", "4. Alice then says “I don’t know when Steve’s bus leaves but I am sure that neither does Annie”\n", "5. Annie Replies “I didn’t know his bus, but now I do”\n", "6. Alice responds “Now I do as well!”\n", "7. 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 change the colons in the times to spaces, we can solve the problem without changing the `cheryls_birthday` function:" ] }, { "cell_type": "code", "execution_count": 36, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'08 32'}" ] }, "execution_count": 36, "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'.replace(':', ' ').split(', ')\n", "cheryls_birthday(times)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Steve took the 8:32 bus.\n", "\n", "# Another New Puzzle: Evil Mad Scientist Cheryl\n", "\n", "I saw this posting:\n", "\n", "![](https://norvig.com/images/cheryl-trolley.png)\n", "\n", "Again, we can solve this problem just by passing in a different set of \"dates\":" ] }, { "cell_type": "code", "execution_count": 37, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'C 3'}" ] }, "execution_count": 37, "metadata": {}, "output_type": "execute_result" } ], "source": [ "cheryls_birthday({'A 2', 'A 3', 'A 6', 'B 4', 'B 5', 'C 1', 'C 3', 'D 1', 'D 2', 'D 4'})" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The correct pad is \"C 3\". \n", "\n", "(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.)\n", "\n", "\n", "# Yet Another Puzzle: Sum and Product\n", "\n", "Consider this puzzle:\n", "\n", "- A pair of numbers are chosen at random. They are both positive integers smaller than 100.\n", "- **S**am is told the **S**um of the numbers, while **P**at is told the **P**roduct of the numbers.\n", "- Then, this dialog occurs:\n", "- 1) Pat: I don't know the numbers.\n", "- 1) Sam: I don't know the numbers.\n", "- 2) Pat: I don't know the numbers.\n", "- 2) Sam: I don't know the numbers.\n", "- 3) Pat: I don't know the numbers.\n", "- 3) Sam: I don't know the numbers.\n", "- 4) Pat: I don't know the numbers.\n", "- 4) Sam: I don't know the numbers.\n", "- 5) Pat: I don't know the numbers.\n", "- 5) Sam: I don't know the numbers.\n", "- 6) Pat: I don't know the numbers.\n", "- 6) Sam: I don't know the numbers.\n", "- 7) Pat: I don't know the numbers.\n", "- 7) Sam: I don't know the numbers.\n", "- 8) Pat: Finally, I know the numbers.\n", "- What are the two numbers?\n", "\n", "In this version of the puzzle, each person has 7 iterations of \"I don't know.\" What could the two numbers be if instead of 7 iterations there are anywhere from 2 to 8 iterations? \n", "\n", "I could solve this using our existing `told` and `know` functions, but that would require encoding the pair of numbers, their sum, and their product into a string. So I'll introduce new functions instead. At first I thought I would need two belief states, one for Pat and one for Sam. It is true that their belief states are different as the story progresses. But because we are only interested in the final answer, and because none of their statements refers to the other one's belief state (e.g. Sam never says \"I know that Pat does not know.\") we can get by with just one overall belief state over the possible pairs of integers." ] }, { "cell_type": "code", "execution_count": 38, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{2: {(1, 6), (1, 8), (72, 92), (75, 96)},\n", " 3: {(81, 88)},\n", " 4: {(77, 90)},\n", " 5: {(76, 90)},\n", " 6: {(80, 84)},\n", " 7: {(77, 84)},\n", " 8: set()}" ] }, "execution_count": 38, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from collections import Counter\n", "from itertools import combinations\n", "from typing import Dict\n", "from math import prod\n", "\n", "def sum_and_product(integers=range(1, 100), N=9) -> Dict[int, BeliefState]:\n", " \"\"\"Solves the Sum and Product puzzle for various numbers of repetitions of Pat and Sam saying \n", " \"I don't know\" (up to `N` times) and for integers within a given range.\n", " Returns a dictionary of {repetitions: {(x, y), ...}}.\"\"\"\n", " pairs = set(combinations(integers, 2))\n", " solutions = {}\n", " for i in range(2, N):\n", " pairs = unknown_pairs(prod, pairs) # Pat doesn't know\n", " pairs = unknown_pairs(sum, pairs) # Sam doesn't know\n", " solutions[i] = known_pairs(prod, pairs) # Pat knows\n", " return solutions\n", " \n", "def known_pairs(function, pairs: BeliefState) -> BeliefState:\n", " \"\"\"Pairs for which function(pair) has a unique value.\"\"\"\n", " counter = Counter(map(function, pairs))\n", " return {pair for pair in pairs if counter[function(pair)] == 1}\n", "\n", "def unknown_pairs(function, pairs: BeliefState) -> BeliefState:\n", " \"\"\"Pairs for which function(pair) does not have a unique value.\"\"\"\n", " counter = Counter(map(function, pairs))\n", " return {pair for pair in pairs if counter[function(pair)] != 1}\n", "\n", "sum_and_product()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "With 2 iterations there are 4 possible answers, so Pat wouldn't know for sure. But with anywhere from 3 to 7 iterations, there is a unique solution. For 8 iterations (and beyond) there are no solutions." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "\n", "# What Next?\n", "\n", "There are many other directions you could take this:\n", "\n", "- Could you create a Cheryl-puzzle that goes one or two rounds more before everyone knows?\n", "- Could you add new characters: Faith, and then George, and maybe even a new Hope?\n", "- Should we include the year or the day of the week, as well as the month and day?\n", "- Perhaps a puzzle that starts with [Richard Smullyan](http://en.wikipedia.org/wiki/Raymond_Smullyan) announcing that one of the characters is a liar.\n", "- Or you could make a puzzle harder than [the hardest logic puzzle ever](https://en.wikipedia.org/wiki/The_Hardest_Logic_Puzzle_Ever).\n", "- Try the \"black and white hats\" [Riddler Express](https://fivethirtyeight.com/features/can-you-solve-these-colorful-puzzles/) stumper.\n", "- It's up to you ..." ] } ], "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 }