{ "cells": [ { "cell_type": "markdown", "id": "686fc7cb", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "# Card guessing game" ] }, { "cell_type": "markdown", "id": "8cfc4a13", "metadata": { "slideshow": { "slide_type": "-" }, "tags": [ "remove-cell" ] }, "source": [ "**CS1302 Introduction to Computer Programming**\n", "___" ] }, { "cell_type": "code", "execution_count": 1, "id": "b2ad0ce8", "metadata": {}, "outputs": [], "source": [ "# Run this cell first to initialize the environment\n", "import random # for shuffling of the cards\n", "from collections import namedtuple # for naming the cards" ] }, { "cell_type": "markdown", "id": "26204da2", "metadata": { "slideshow": { "slide_type": "subslide" }, "tags": [] }, "source": [ "## Rules of the game" ] }, { "cell_type": "markdown", "id": "7410accb", "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", "id": "7f565630", "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", "id": "563cd91f", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "The following code creates a deck of cards. (You are not expected to understand the code for now.)" ] }, { "cell_type": "code", "execution_count": 2, "id": "32034df9", "metadata": { "slideshow": { "slide_type": "-" }, "tags": [ "output-scroll" ] }, "outputs": [ { "data": { "text/plain": [ "[Card(value=1, suit='Diamond'),\n", " Card(value=1, suit='Club'),\n", " Card(value=1, suit='Heart'),\n", " Card(value=1, suit='Spade'),\n", " Card(value=2, suit='Diamond'),\n", " Card(value=2, suit='Club'),\n", " Card(value=2, suit='Heart'),\n", " Card(value=2, suit='Spade'),\n", " Card(value=3, suit='Diamond'),\n", " Card(value=3, suit='Club'),\n", " Card(value=3, suit='Heart'),\n", " Card(value=3, suit='Spade'),\n", " Card(value=4, suit='Diamond'),\n", " Card(value=4, suit='Club'),\n", " Card(value=4, suit='Heart'),\n", " Card(value=4, suit='Spade'),\n", " Card(value=5, suit='Diamond'),\n", " Card(value=5, suit='Club'),\n", " Card(value=5, suit='Heart'),\n", " Card(value=5, suit='Spade'),\n", " Card(value=6, suit='Diamond'),\n", " Card(value=6, suit='Club'),\n", " Card(value=6, suit='Heart'),\n", " Card(value=6, suit='Spade'),\n", " Card(value=7, suit='Diamond'),\n", " Card(value=7, suit='Club'),\n", " Card(value=7, suit='Heart'),\n", " Card(value=7, suit='Spade'),\n", " Card(value=8, suit='Diamond'),\n", " Card(value=8, suit='Club'),\n", " Card(value=8, suit='Heart'),\n", " Card(value=8, suit='Spade'),\n", " Card(value=9, suit='Diamond'),\n", " Card(value=9, suit='Club'),\n", " Card(value=9, suit='Heart'),\n", " Card(value=9, suit='Spade'),\n", " Card(value=10, suit='Diamond'),\n", " Card(value=10, suit='Club'),\n", " Card(value=10, suit='Heart'),\n", " Card(value=10, suit='Spade'),\n", " Card(value=11, suit='Diamond'),\n", " Card(value=11, suit='Club'),\n", " Card(value=11, suit='Heart'),\n", " Card(value=11, suit='Spade'),\n", " Card(value=12, suit='Diamond'),\n", " Card(value=12, suit='Club'),\n", " Card(value=12, suit='Heart'),\n", " Card(value=12, suit='Spade'),\n", " Card(value=13, suit='Diamond'),\n", " Card(value=13, suit='Club'),\n", " Card(value=13, suit='Heart'),\n", " Card(value=13, suit='Spade')]" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Create a deck of cards\n", "suits = (\"Diamond\", \"Club\", \"Heart\", \"Spade\")\n", "values = range(1, 14)\n", "Card = namedtuple(\"Card\", [\"value\", \"suit\"]) # namedtuple from collections\n", "\n", "deck = [Card(value, suit) for value in values for suit in suits]\n", "deck # output the deck of cards to the output cell" ] }, { "cell_type": "markdown", "id": "c9ba4bdb", "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. \n", "Press `Ctrl-Enter` on the following code cell to draw a card randomly." ] }, { "cell_type": "code", "execution_count": 3, "id": "63d74894", "metadata": { "slideshow": { "slide_type": "-" } }, "outputs": [ { "data": { "text/plain": [ "Card(value=4, suit='Club')" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "random.choice(deck) # random imported before" ] }, { "cell_type": "markdown", "id": "30b92037", "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", "id": "8b0e3122", "metadata": {}, "source": [ "![Card guessing game](images/card_game.dio.svg)" ] }, { "cell_type": "markdown", "id": "1156da3d", "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", "id": "de82c734", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "However, you cannot ask:\n", "- What is the value?\n", "- What is the suite?" ] }, { "cell_type": "markdown", "id": "2a18c93f", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "**Exercise** \n", "\n", "You win if you can **guess the card correctly with no more than 6 questions**. What is the winning strategy?" ] }, { "cell_type": "markdown", "id": "f90de740", "metadata": { "deletable": false, "nbgrader": { "cell_type": "markdown", "checksum": "147d099f1497a2d05b83d46fb4aa16df", "grade": true, "grade_id": "winning-strategy", "locked": false, "points": 1, "schema_version": 3, "solution": true, "task": false }, "slideshow": { "slide_type": "-" } }, "source": [ "YOUR ANSWER HERE" ] }, { "cell_type": "markdown", "id": "b7cd1e33", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "````{hint} \n", "\n", "- Obviously, you should not ask whether the card is precisely certain card, e.g., Is it Diamond Ace? Is it Diamond 2? ... Why not? \n", " The card may be one of the remaining $52-6=46$ possibilities you did not ask.\n", "- 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**.\n", "- How many questions is required to split the set of 52 cards into groups of size $1$, i.e., with only one possible card?\n", "\n", "````" ] }, { "cell_type": "markdown", "id": "0fc40cb8", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Challenge the computer" ] }, { "cell_type": "markdown", "id": "a199091c", "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": 4, "id": "ff4d3ca2", "metadata": { "slideshow": { "slide_type": "-" }, "tags": [ "remove-output" ] }, "outputs": [ { "ename": "RuntimeError", "evalue": "This frontend does not support input requests", "output_type": "error", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m\n\u001b[0;31mRuntimeError\u001b[0m Traceback (most recent call last)", "File \u001b[0;34m/home/cs1302/my-conda-envs/jb/lib/python3.8/site-packages/IPython/core/interactiveshell.py\u001b[0m, in \u001b[0;32mrun_code\u001b[0m:\nLine \u001b[0;34m3441\u001b[0m: exec(code_obj, \u001b[36mself\u001b[39;49;00m.user_global_ns, \u001b[36mself\u001b[39;49;00m.user_ns)\n", "In \u001b[0;34m[4]\u001b[0m:\nLine \u001b[0;34m4\u001b[0m: \u001b[34mif\u001b[39;49;00m \u001b[33m\"\u001b[39;49;00m\u001b[33my\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m == \u001b[36minput\u001b[39;49;00m(\n", "\u001b[0;31mRuntimeError\u001b[0m: This frontend does not support input requests\n\u001b[0;31m---------------------------------------------------------------------------\u001b[0m" ] } ], "source": [ "suit_idx = 0\n", "number = 0\n", "\n", "if \"y\" == input(\n", " \"Is the suite either heart or spade? (y/[n]) \")[0].lower():\n", " suit_idx += 2\n", "\n", "if \"y\" == input(\"Is the suite either club or spade? (y/[n]) \")[0].lower():\n", " suit_idx += 1\n", "\n", "if \"y\" == input(\n", " f\"Is the number {number+8} or above? (y/[n]) \")[0].lower():\n", " number += 8\n", "\n", "if \"y\" == input(\n", " f\"Is the number {number+4} or above? (y/[n]) \")[0].lower():\n", " number += 4\n", "\n", "if \"y\" == input(\n", " f\"Is the number {number+2} or above? (y/[n]) \")[0].lower():\n", " number += 2\n", "\n", "if \"y\" == input(\n", " f\"Is the number {number+1} or above? (y/[n]) \")[0].lower():\n", " number += 1\n", "\n", "print(f\"The card is {suits[suit_idx]} {number}\")" ] }, { "cell_type": "markdown", "id": "ee52fea5", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "**Exercise** \n", "\n", "Does the above program always win? Explain your answer?" ] }, { "cell_type": "markdown", "id": "4032a15c", "metadata": { "deletable": false, "nbgrader": { "cell_type": "markdown", "checksum": "ed9e95497e24e75cb708cea5946f166b", "grade": true, "grade_id": "computer", "locked": false, "points": 1, "schema_version": 3, "solution": true, "task": false }, "slideshow": { "slide_type": "-" } }, "source": [ "YOUR ANSWER HERE" ] }, { "cell_type": "markdown", "id": "585a6f44", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Challenge your understanding" ] }, { "cell_type": "markdown", "id": "1c07fbfb", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "The following table gives the binary representions of unsigned decimal integers from 0 to 7." ] }, { "cell_type": "markdown", "id": "56ef4c5e", "metadata": {}, "source": [ "| Binary | Decimal |\n", "|:------:|:-------:|\n", "| 000 | 0 |\n", "| 001 | 1 |\n", "| 010 | 2 |\n", "| 011 | 3 |\n", "| 100 | 4 |\n", "| 101 | 5 |\n", "| 110 | 6 |\n", "| 111 | 7 |" ] }, { "cell_type": "markdown", "id": "9b4cc73c", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Observe that the binary representations of 4, 5, 6, and 7 all have **1** in the leftmost (most significant) bit:\n", "\n", "| Binary | Decimal |\n", "|:-------:|:-------:|\n", "| 000 | 0 |\n", "| 001 | 1 |\n", "| 010 | 2 |\n", "| 011 | 3 |\n", "| **1**00 | **4** |\n", "| **1**01 | **5** |\n", "| **1**10 | **6** |\n", "| **1**11 | **7** |\n", "\n", "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", "id": "bda1e74d", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "To convert binary to decimal, we can 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.\n", "\n", "![Decoding tree](images/dt.dio.svg)" ] }, { "cell_type": "markdown", "id": "124921c3", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "**Exercise** \n", "\n", "What are the **yes/no** questions (Q2 and Q3 above) corresponding to the 2nd bit and 3rd bit?" ] }, { "cell_type": "markdown", "id": "f69bb586", "metadata": { "deletable": false, "nbgrader": { "cell_type": "markdown", "checksum": "fe3d19107d6051d4bbb261a17040efea", "grade": true, "grade_id": "questions", "locked": false, "points": 1, "schema_version": 3, "solution": true, "task": false }, "slideshow": { "slide_type": "-" } }, "source": [ "YOUR ANSWER HERE" ] }, { "cell_type": "markdown", "id": "e7214a6e", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "````{hint}\n", "\n", "- [Binary Number System](https://www.mathsisfun.com/binary-number-system.html)\n", "- [Binary Number Conversions](https://www.purplemath.com/modules/numbbase.htm)\n", "\n", "````" ] }, { "cell_type": "markdown", "id": "136e3a67", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Representing negative numbers" ] }, { "cell_type": "markdown", "id": "a7f4e207", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "The following also uses 3 bits to represent 8 numbers but half of the numbers are negative." ] }, { "cell_type": "markdown", "id": "88c4cb75", "metadata": { "slideshow": { "slide_type": "-" } }, "source": [ "| Binary | Decimal |\n", "|:-------:|:-------:|\n", "| 000 | 0 |\n", "| 001 | 1 |\n", "| 010 | 2 |\n", "| 011 | 3 |\n", "| **1**00 | **-4** |\n", "| **1**01 | **-3** |\n", "| **1**10 | **-2** |\n", "| **1**11 | **-1** |" ] }, { "cell_type": "markdown", "id": "82df6294", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- The numbers 0, 1, 2, and 3 have the same binary representations as before, but\n", "- the binary representations for 4, 5, 6, and 7 are now used for -4, -3, -2, and -1." ] }, { "cell_type": "markdown", "id": "8ca38ae5", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "**What is the benefit of the above representation?**" ] }, { "cell_type": "markdown", "id": "55ab1fc2", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "To subtract a positive binary number $x$ from another positive binary number $y$, it seems we can turn it into binary addition\n", "\n", "$$x - y = x + (-y)$$\n", "\n", "of a positive binary number $x$ and a negative binary number $-y$." ] }, { "cell_type": "markdown", "id": "5cd317b1", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "For example,\n", "\n", "$$\n", "\\overbrace{011_2}^{3} + \\overbrace{100_2}^{-4} = \\underbrace{111_2}_{-1}\n", "$$" ] }, { "cell_type": "markdown", "id": "8be3fa02", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "It seem to work as well if there are bits carried forward, e.g., $1 + (- 3)$ in binary is" ] }, { "cell_type": "markdown", "id": "e94fba74", "metadata": { "slideshow": { "slide_type": "-" } }, "source": [ "$$\n", "\\begin{array}{rrrr}\n", " & 0 & \\overset{1}0 & 1 \\\\\n", "+ & 1 & 0 & 1 \\\\\\hline\n", "& 1 & 1 & 0 \n", "\\end{array}\n", "$$" ] }, { "cell_type": "markdown", "id": "54932f53", "metadata": { "slideshow": { "slide_type": "-" } }, "source": [ "which translate to $-2$ in decimal as desired." ] }, { "cell_type": "markdown", "id": "aab03271", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "**Exercise** \n", "\n", "There is a subtlety when computing $3 - 2$ using binary addition because \n", "\n", "$$ \\overbrace{011_2}^3 + \\overbrace{110_2}^{-2} = 1001_2$$\n", "\n", "which overflows to $4$ bits, which is an invalid binary representation. Fortunately, there is a simple fix so binary addition can still apply. Come up with such a fix that also work for all other cases such as $3-3$, $2-1$, etc." ] }, { "cell_type": "markdown", "id": "e5172bdd", "metadata": { "deletable": false, "nbgrader": { "cell_type": "markdown", "checksum": "5aaccd773bae911503a439a767ff66f2", "grade": true, "grade_id": "overflow", "locked": false, "points": 1, "schema_version": 3, "solution": true, "task": false }, "slideshow": { "slide_type": "-" } }, "source": [ "YOUR ANSWER HERE" ] }, { "cell_type": "markdown", "id": "8f8e67bc", "metadata": { "slideshow": { "slide_type": "-" } }, "source": [ "````{hint}\n", "\n", "- Can we drop one of the $4$ bits?\n", "- [Two's complement represenation](https://en.wikipedia.org/wiki/Two%27s_complement).\n", "\n", "````" ] }, { "cell_type": "markdown", "id": "55f8fcca", "metadata": {}, "source": [ "## Building a computer from transistors (Optional)" ] }, { "cell_type": "markdown", "id": "87a7a5fd", "metadata": {}, "source": [ "A computer is build from transistors that operates on binary states, *on/off*, which is also represented as bits *1/0* or boolean values *True/False*." ] }, { "cell_type": "markdown", "id": "2041519f", "metadata": {}, "source": [ "Consider the addition of $2$ bits $A$ and $B$:\n", "\n", "$$\n", "A + B = C\\circ S\n", "$$\n", "\n", "\n", "| A | B | C S |\n", "|:---:|:---:|:----------:|\n", "| 0 | 0 | 00 |\n", "| 0 | 1 | 01 |\n", "| 1 | 0 | 01 |\n", "| 1 | 1 | 10 |" ] }, { "cell_type": "markdown", "id": "03d2cdcd", "metadata": {}, "source": [ "There are transistors, called *logic gates*, that can carry out basic logic operations:\n", "- $A \\operatorname{AND} B$: which returns $1$ if and only if both $A$ and $B$ are $1$, and $0$ otherwise.\n", "- $A \\operatorname{XOR} B$: which returns $1$ if and only if either $A$ and $B$ are $1$ but not both." ] }, { "cell_type": "markdown", "id": "d8d185b1", "metadata": {}, "source": [ "**What is the logic in computing $C$ and $S$ from $A$ and $B$?**" ] }, { "cell_type": "markdown", "id": "6c0d9313", "metadata": {}, "source": [ "Try out a logic gate simulator:\n", "- Visit https://logic.ly/demo/\n", "- Select *1-Bit Full Adder*." ] }, { "cell_type": "markdown", "id": "6912805f", "metadata": {}, "source": [ "If you play minecraft, you can build the following devices based on how computers are built from logic gates:\n", "- an adder for binary addition: https://youtu.be/vtpTri-PZXY\n", "- a calculator for calculus: https://youtu.be/5NzIt9sns6o" ] } ], "metadata": { "jupytext": { "text_representation": { "extension": ".md", "format_name": "myst", "format_version": 0.13, "jupytext_version": "1.10.3" } }, "kernelspec": { "display_name": "Python 3.8 (XPython)", "language": "python", "name": "xpython" }, "language_info": { "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "version": "3.8.10" }, "source_map": [ 14, 18, 23, 29, 33, 119, 124, 128, 143, 148, 156, 160, 164, 171, 177, 183, 187, 198, 202, 206, 241, 247, 251, 255, 259, 272, 291, 299, 305, 309, 318, 322, 326, 339, 344, 348, 356, 364, 368, 378, 382, 392, 396, 405, 409, 413, 429, 435, 439, 445 ] }, "nbformat": 4, "nbformat_minor": 5 }