{ "cells": [ { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "# Card guessing game" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "-" }, "tags": [ "remove-cell" ] }, "source": [ "**CS1302 Introduction to Computer Programming**\n", "___" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "## Rules of the game" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Consider a deck of 52 cards:\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
1 (A)234567891011 (J)12 (Q)13 (K)
Diamond\"Cards-A-Diamond\"\"Cards-2-Diamond\"\"Cards-3-Diamond\"\"Cards-4-Diamond\"\"Cards-5-Diamond\"\"Cards-6-Diamond\"\"Cards-7-Diamond\"\"Cards-8-Diamond\"\"Cards-9-Diamond\"\"Cards-10-Diamond\"\"Cards-J-Diamond\"\"Cards-Q-Diamond\"\"Cards-K-Diamond\"
Club\"Cards-A-Club\"\"Cards-2-Club\"\"Cards-3-Club\"\"Cards-4-Club\"\"Cards-5-Club\"\"Cards-6-Club\"\"Cards-7-Club\"\"Cards-8-Club\"\"Cards-9-Club\"\"Cards-10-Club\"\"Cards-J-Club\"\"Cards-Q-Club\"\"Cards-K-Club\"
Heart\"Cards-A-Heart\"\"Cards-2-Heart\"\"Cards-3-Heart\"\"Cards-4-Heart\"\"Cards-5-Heart\"\"Cards-6-Heart\"\"Cards-7-Heart\"\"Cards-8-Heart\"\"Cards-9-Heart\"\"Cards-10-Heart\"\"Cards-J-Heart\"\"Cards-Q-Heart\"\"Cards-K-Heart\"
Spade\"Cards-A-Spade\"\"Cards-2-Spade\"\"Cards-3-Spade\"\"Cards-4-Spade\"\"Cards-5-Spade\"\"Cards-6-Spade\"\"Cards-7-Spade\"\"Cards-8-Spade\"\"Cards-9-Spade\"\"Cards-10-Spade\"\"Cards-J-Spade\"\"Cards-Q-Spade\"\"Cards-K-Spade\"
" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- Each card is in one of the four suits: **Diamond**, **Club**, **Heart**, and **Spade**.\n", "- Each card has a value $1 \\text{ (A)} < 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < 11 \\text{ (J)} < 12 \\text{ (Q)} < 13 \\text{ (K)}$." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "The following code creates a deck of cards. (You do not need to understand the code for now.)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "ExecuteTime": { "end_time": "2020-08-24T06:32:14.899767Z", "start_time": "2020-08-24T06:32:14.891659Z" }, "slideshow": { "slide_type": "-" } }, "outputs": [], "source": [ "# Create a deck of cards\n", "from collections import namedtuple\n", "\n", "suits = (\"Diamond\", \"Club\", \"Heart\", \"Spade\")\n", "values = range(1, 14)\n", "Card = namedtuple('Card', ['value', 'suit'])\n", "\n", "deck = [Card(value, suit) for value in values for suit in suits]\n", "print(deck)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "To play the game, a dealer randomly pick a card without letting you know, and you're going to guess what exactly that card is." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "ExecuteTime": { "end_time": "2020-08-24T06:32:21.728471Z", "start_time": "2020-08-24T06:32:21.722384Z" }, "slideshow": { "slide_type": "-" } }, "outputs": [], "source": [ "# Randomly draw a card from the deck with replacement\n", "import random\n", "print(random.choice(deck))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "You are allowed to make an informed guess after the dealer answers some of your **yes/no** questions." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "For instance, you may ask:\n", "- Is the suit club?\n", "- Is the card diamond 1 (ace)?\n", "- Is the value at least 10?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "However, you cannot ask:\n", "- What is the value?\n", "- What is the suite?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "**Exercise** You win if you can **guess the card correctly with no more than 6 questions**. What is the winning strategy?" ] }, { "cell_type": "markdown", "metadata": { "deletable": false, "nbgrader": { "cell_type": "markdown", "checksum": "4c6cc73b95ea527fcaba1557556ef42d", "grade": true, "grade_id": "cell-31a1b5a128062b4a", "locked": false, "points": 1, "schema_version": 3, "solution": true, "task": false }, "slideshow": { "slide_type": "-" } }, "source": [ "YOUR ANSWER HERE" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Hint 1: Obviously, you should not ask whether the card is precisely certain card, e.g., Is it Diamond Ace? Is it Diamond 2? ... Why not? The card may be one of the remaining $52-6=46$ possibilities you did not ask." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Hint 2: Think of each **Yes/No** question as splitting the set of possible cards into two smaller groups of possible cards corresponding to each possible answer **Yes/No**." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Hint 3: How many questions is required to split the set of 52 cards into groups of size $1$, i.e., with only one possible card?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Challenge the computer" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Play the role of the dealer and test if the program below can guess the card correctly after 6 questions." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "ExecuteTime": { "end_time": "2020-08-24T06:34:11.494355Z", "start_time": "2020-08-24T06:32:33.101128Z" }, "slideshow": { "slide_type": "-" } }, "outputs": [], "source": [ "suitIdx = 0\n", "number = 0\n", "\n", "if \"y\" == input(\n", " \"Is the suite either heart or spade? (y/[n]) \").strip().lower():\n", " suitIdx += 2\n", "\n", "if \"y\" == input(\"Is the suite either club or spade? (y/[n]) \").strip().lower():\n", " suitIdx += 1\n", "\n", "if \"y\" == input(\n", " f\"Is the number {number+8} or above? (y/[n]) \").strip().lower():\n", " number += 8\n", "\n", "if \"y\" == input(\n", " f\"Is the number {number+4} or above? (y/[n]) \").strip().lower():\n", " number += 4\n", "\n", "if \"y\" == input(\n", " f\"Is the number {number+2} or above? (y/[n]) \").strip().lower():\n", " number += 2\n", "\n", "if \"y\" == input(\n", " f\"Is the number {number+1} or above? (y/[n]) \").strip().lower():\n", " number += 1\n", "\n", "print(f\"The card is {suits[suitIdx]} {number}\")" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "**Exercise** Does the above program always win? Explain your answer?" ] }, { "cell_type": "markdown", "metadata": { "deletable": false, "nbgrader": { "cell_type": "markdown", "checksum": "ed044740d01dabcbf82c56ce0a744078", "grade": true, "grade_id": "cell-d020c0eb31353627", "locked": false, "points": 1, "schema_version": 3, "solution": true, "task": false }, "slideshow": { "slide_type": "-" } }, "source": [ "YOUR ANSWER HERE" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Challenge your understanding" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "The following table gives the binary representions of unsigned decimal integers from 0 to 7." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "-" } }, "source": [ "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
BinaryDecimal
0000
0011
0102
0113
1004
1015
1106
1117

" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "To convert binary to decimal, think of the conversion as a guessing game where\n", "- the binary sequence is a sequence of **yes (1)** or **no (0)** answers to certain **yes/no** questions, and\n", "- the informed guess is the integer represented by the binary sequence." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "For instance, observe that the binary representation of 4, 5, 6, and 7 actually have 1 in the leftmost (most significant) bit. Therefore we can consider that bit as the answer to the following **yes/no** question:\n", "\n", "> Is the integer 4 or above?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "**Exercise** What are the **yes/no** questions corresponding to the 2nd bit and 3rd bit?" ] }, { "cell_type": "markdown", "metadata": { "deletable": false, "nbgrader": { "cell_type": "markdown", "checksum": "de1bf862a69e23844d4f4b148fc8bc1b", "grade": true, "grade_id": "cell-feebf3b664ed4c0a", "locked": false, "points": 1, "schema_version": 3, "solution": true, "task": false }, "slideshow": { "slide_type": "-" } }, "source": [ "YOUR ANSWER HERE" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "

References

\n", "" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3.7", "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.6" }, "latex_envs": { "LaTeX_envs_menu_present": true, "autoclose": false, "autocomplete": true, "bibliofile": "biblio.bib", "cite_by": "apalike", "current_citInitial": 1, "eqLabelWithNumbers": true, "eqNumInitial": 1, "hotkeys": { "equation": "Ctrl-E", "itemize": "Ctrl-I" }, "labels_anchors": false, "latex_user_defs": false, "report_style_numbering": false, "user_envs_cfg": false }, "toc": { "base_numbering": 1, "nav_menu": {}, "number_sections": true, "sideBar": true, "skip_h1_title": true, "title_cell": "Table of Contents", "title_sidebar": "Contents", "toc_cell": false, "toc_position": {}, "toc_section_display": true, "toc_window_display": false } }, "nbformat": 4, "nbformat_minor": 4 }