{ "metadata": { "name": "", "signature": "sha256:b9e2e6c3f7e82432833f1416dd0552c13753f683e1888682faf2910ef7d9f8ff" }, "nbformat": 3, "nbformat_minor": 0, "worksheets": [ { "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "When is Cheryl's Birthday?\n", "===\n", "\n", "
Peter Norvig, April 2015
\n", "\n", "This logic puzzle has been [making the rounds](https://www.google.com/webhp?#q=cheryl%27s+birthday):\n", "\n", "\n", "1. Albert and Bernard just became friends with Cheryl, and they want to know when her birtxhday is. Cheryl gave them a list of 10 possible dates:\n", "
\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",
      "
\n", " \n", "2. Cheryl then tells Albert and Bernard separately the month and the day of the birthday respectively.\n", " \n", "3. **Albert**: I don't know when Cheryl's birthday is, but I know that Bernard does not know too.\n", " \n", "4. **Bernard**: At first I don't know when Cheryl's birthday is, but I know now.\n", " \n", "5. **Albert**: Then I also know when Cheryl's birthday is.\n", " \n", "6. So when is Cheryl's birthday?\n", "\n", "Problem-Solving Tools\n", "---\n", "\n", "Cheryl's puzzle was designed to be solved with a pencil, the greatest problem-solving tool in the history of mathematics (although some prefer a pen, chalk, marker, or a [stick for drawing in the sand](http://www.hellenicaworld.com/Greece/Science/en/Archimedes.html)). But I will show how to solve it with another tool: **computer code**. I choose this tool for four reasons: \n", "- It is a more direct way to find the solution. All I have to do is faithfully describe the problem with code that says: *\"for each of the 10 possible dates, tell Albert the month and Bernard the day and check if statements 3 through 5 are true.\"* The intended [pencil and paper solution](https://scontent-iad.xx.fbcdn.net/hphotos-xpa1/v/t1.0-9/s720x720/11111802_983395601695416_3208022346737572922_n.jpg?oh=15fcb7edc4689dd9c71385b613446465&oe=55DD4488) requires not just understanding the *problem*, but also creatively discovering the steps of the *solution*—a harder task.\n", "- With tested, debugged code, you're less likely to make a mistake that leads you to a [wrong answer](http://www.theguardian.com/science/alexs-adventures-in-numberland/2015/apr/15/why-the-cheryl-birthday-problem-turned-into-the-maths-version-of-thatdress).\n", "- You'll learn how to solve problems that are similar, but can't be solved with pencil and paper because they have millions of possibilities rather than just 10.\n", "- Solving puzzles is fun; programming is fun; solving puzzles with programs is double fun.\n", "\n", "We will translate each of the 6 statements in the puzzle into Python code:" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "1. Cheryl gave them a list of 10 possible dates:\n", "---\n" ] }, { "cell_type": "code", "collapsed": false, "input": [ "DATES = ['May 15', 'May 16', 'May 19',\n", " 'June 17', 'June 18',\n", " 'July 14', 'July 16',\n", " 'August 14', 'August 15', 'August 17']" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 1 }, { "cell_type": "markdown", "metadata": {}, "source": [ "We'll also define accessor functions for the month and day of a date:" ] }, { "cell_type": "code", "collapsed": false, "input": [ "def Month(date): return date.split()[0]\n", "\n", "def Day(date): return date.split()[1]" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 2 }, { "cell_type": "code", "collapsed": false, "input": [ "Month('May 15')" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 3, "text": [ "'May'" ] } ], "prompt_number": 3 }, { "cell_type": "code", "collapsed": false, "input": [ "Day('May 15')" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 4, "text": [ "'15'" ] } ], "prompt_number": 4 }, { "cell_type": "markdown", "metadata": {}, "source": [ "2. Cheryl then tells Albert and Bernard separately the month and the day of the birthday respectively.\n", "---\n", "\n", "We can define the idea of **telling**, and while we're at it, the idea of **knowing** a birthdate:" ] }, { "cell_type": "code", "collapsed": false, "input": [ "def tell(part, possible_dates=DATES):\n", " \"Cheryl tells a part of her birthdate to someone; return a new list of possible dates that match the part.\"\n", " return [date for date in possible_dates if part in date]\n", "\n", "def know(possible_dates):\n", " \"A person knows the birthdate if they have exactly one possible date.\"\n", " return len(possible_dates) == 1" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 5 }, { "cell_type": "markdown", "metadata": {}, "source": [ "Note that we use a *list of dates* to represent someone's knowledge of the possible birthdates, and that someone *knows* the birthdate when they get down to only one possibility. For example: If Cheryl tells Albert that her birthday is in May, he would have a list of three possible birthdates:" ] }, { "cell_type": "code", "collapsed": false, "input": [ "tell('May')" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 6, "text": [ "['May 15', 'May 16', 'May 19']" ] } ], "prompt_number": 6 }, { "cell_type": "markdown", "metadata": {}, "source": [ "And if she tells Bernard that her birthday is on the 15th, he would end up with two possibilities:" ] }, { "cell_type": "code", "collapsed": false, "input": [ "tell('15')" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 7, "text": [ "['May 15', 'August 15']" ] } ], "prompt_number": 7 }, { "cell_type": "markdown", "metadata": {}, "source": [ "With two possibilities, Bernard does not know the birthdate:" ] }, { "cell_type": "code", "collapsed": false, "input": [ "know(tell('15'))" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 8, "text": [ "False" ] } ], "prompt_number": 8 }, { "cell_type": "markdown", "metadata": {}, "source": [ "Overall Strategy\n", "---\n", "\n", "When Cheryl tells Albert `'May'` then *he* knows there are three possibilities, but *we* (the puzzle solvers) don't, because we don't know what Cheryl said. So what can we do? We will consider *all* of the possible dates, one at a time. For example, first consider `'May 15'`. Cheryl tells Albert `'May'` and Bernard `'15'`, giving them the lists of possible birthdates shown above. We can then check whether statements 3 through 5 are true in this scenario. If they are, then `'May 15'` is a solution to the puzzle. Repeat the process for each of the possible dates. If all goes well, there should be exactly one solution. \n", "\n", "Here is the main function, `cheryls_birthday`:" ] }, { "cell_type": "code", "collapsed": false, "input": [ "def cheryls_birthday(possible_dates=DATES):\n", " \"Return a list of the possible dates for which statements 3 to 5 are true.\"\n", " return filter(statements3to5, possible_dates)\n", "\n", "def statements3to5(date): return statement3(date) and statement4(date) and statement5(date)\n", "\n", "## TO DO: define statement3, statement4, statement5" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 9 }, { "cell_type": "markdown", "metadata": {}, "source": [ " (*Python note:* `filter(predicate, items)` returns a list of all items for which `predicate(item)` is true.)\n", " \n", " 3. Albert: I don't know when Cheryl's birthday is, but I know that Bernard does not know too.\n", "---" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The function `statement3` takes as input a 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 in a form that is closer to Python code:\n", "\n", "> **Albert**: After Cheryl told me the month of her birthdate, I didn't know her birthday. I don't know which day Cheryl told Bernard, but I know that for all of the possible dates, if Bernard is told that day, he wouldn't know the birthdate.\n", "\n", "That I can translate directly into code:" ] }, { "cell_type": "code", "collapsed": false, "input": [ "def statement3(date):\n", " \"Albert: I don't know when Cheryl's birthday is, but I know that Bernard does not know too.\"\n", " possible_dates = tell(Month(date))\n", " return (not know(possible_dates) \n", " and all(not know(tell(Day(d)))\n", " for d in possible_dates))" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 10 }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can try the function on a date:" ] }, { "cell_type": "code", "collapsed": false, "input": [ "statement3('May 15')" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 11, "text": [ "False" ] } ], "prompt_number": 11 }, { "cell_type": "markdown", "metadata": {}, "source": [ "In fact, we can see all the dates that satisfy statement 3:" ] }, { "cell_type": "code", "collapsed": false, "input": [ "filter(statement3, DATES)" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 12, "text": [ "['July 14', 'July 16', 'August 14', 'August 15', 'August 17']" ] } ], "prompt_number": 12 }, { "cell_type": "markdown", "metadata": {}, "source": [ "4. Bernard: At first I don't know when Cheryl's birthday is, but I know now.\n", "---\n", "\n", "Again, a paraphrase:\n", "\n", "> **Bernard:** At first Cheryl told me the day, and I didn't know. Then I considered just the dates for which Albert's statement 3 is true, and now I know." ] }, { "cell_type": "code", "collapsed": false, "input": [ "def statement4(date):\n", " \"Bernard: At first I don't know when Cheryl's birthday is, but I know now.\"\n", " at_first = tell(Day(date))\n", " return (not know(at_first)\n", " and know(filter(statement3, at_first)))" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 13 }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's see which dates satisfy both statement 3 and statement 4:" ] }, { "cell_type": "code", "collapsed": false, "input": [ "filter(statement4, filter(statement3, DATES))" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 14, "text": [ "['July 16', 'August 15', 'August 17']" ] } ], "prompt_number": 14 }, { "cell_type": "markdown", "metadata": {}, "source": [ "Wait a minute—I thought that Bernard **knew**?! Why are there three possible dates remaining? Bernard does indeed know the birthdate,\n", "because he knows something we don't know: the day. We won't know the birthdate until after statement 5.\n", "\n", "5. Albert: Then I also know when Cheryl's birthday is.\n", "---\n", "\n", "Albert is saying that after hearing the month and Bernard's statement 4, he now knows Cheryl's birthday:" ] }, { "cell_type": "code", "collapsed": false, "input": [ "def statement5(date):\n", " \"Albert: Then I also know when Cheryl's birthday is.\"\n", " return know(filter(statement4, tell(Month(date))))" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 15 }, { "cell_type": "markdown", "metadata": {}, "source": [ "6. So when is Cheryl's birthday?\n", "---\n", "\n", "Let's see:" ] }, { "cell_type": "code", "collapsed": false, "input": [ "cheryls_birthday()" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 16, "text": [ "['July 16']" ] } ], "prompt_number": 16 }, { "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", "collapsed": false, "input": [ "know(cheryls_birthday())" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 17, "text": [ "True" ] } ], "prompt_number": 17 } ], "metadata": {} } ] }