--- 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 --- +++ {"slideshow": {"slide_type": "slide"}} # Card guessing game +++ {"slideshow": {"slide_type": "-"}, "tags": ["remove-cell"]} **CS1302 Introduction to Computer Programming** ___ ```{code-cell} # Run this cell first to initialize the environment import random # for shuffling of the cards from collections import namedtuple # for naming the cards ``` +++ {"slideshow": {"slide_type": "subslide"}, "tags": []} ## Rules of the game +++ {"slideshow": {"slide_type": "fragment"}} Consider a deck of 52 cards:

	1 (A)	2	3	4	5	6	7	8	9	10	11 (J)	12 (Q)	13 (K)
Diamond
Club
Heart
Spade

+++ {"slideshow": {"slide_type": "fragment"}} - Each card is in one of the four suits: **Diamond**, **Club**, **Heart**, and **Spade**. - 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)}$. +++ {"slideshow": {"slide_type": "subslide"}} The following code creates a deck of cards. (You are not expected to understand the code for now.) ```{code-cell} --- slideshow: slide_type: '-' tags: [output-scroll] --- # Create a deck of cards suits = ("Diamond", "Club", "Heart", "Spade") values = range(1, 14) Card = namedtuple("Card", ["value", "suit"]) # namedtuple from collections deck = [Card(value, suit) for value in values for suit in suits] deck # output the deck of cards to the output cell ``` +++ {"slideshow": {"slide_type": "subslide"}} 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. Press `Ctrl-Enter` on the following code cell to draw a card randomly. ```{code-cell} --- slideshow: slide_type: '-' --- random.choice(deck) # random imported before ``` +++ {"slideshow": {"slide_type": "subslide"}} You are allowed to make an informed guess after the dealer answers some of your **yes/no** questions. +++ ![Card guessing game](images/card_game.dio.svg) +++ {"slideshow": {"slide_type": "fragment"}} For instance, you may ask: - Is the suit club? - Is the card diamond 1 (ace)? - Is the value at least 10? +++ {"slideshow": {"slide_type": "fragment"}} However, you cannot ask: - What is the value? - What is the suite? +++ {"slideshow": {"slide_type": "subslide"}} **Exercise** You win if you can **guess the card correctly with no more than 6 questions**. What is the winning strategy? +++ {"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": "-"}} YOUR ANSWER HERE +++ {"slideshow": {"slide_type": "fragment"}} ````{hint} - 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. - 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**. - How many questions is required to split the set of 52 cards into groups of size $1$, i.e., with only one possible card? ```` +++ {"slideshow": {"slide_type": "slide"}} ## Challenge the computer +++ {"slideshow": {"slide_type": "fragment"}} Play the role of the dealer and test if the program below can guess the card correctly after 6 questions. ```{code-cell} --- slideshow: slide_type: '-' tags: [remove-output] --- suit_idx = 0 number = 0 if "y" == input( "Is the suite either heart or spade? (y/[n]) ")[0].lower(): suit_idx += 2 if "y" == input("Is the suite either club or spade? (y/[n]) ")[0].lower(): suit_idx += 1 if "y" == input( f"Is the number {number+8} or above? (y/[n]) ")[0].lower(): number += 8 if "y" == input( f"Is the number {number+4} or above? (y/[n]) ")[0].lower(): number += 4 if "y" == input( f"Is the number {number+2} or above? (y/[n]) ")[0].lower(): number += 2 if "y" == input( f"Is the number {number+1} or above? (y/[n]) ")[0].lower(): number += 1 print(f"The card is {suits[suit_idx]} {number}") ``` +++ {"slideshow": {"slide_type": "fragment"}} **Exercise** Does the above program always win? Explain your answer? +++ {"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": "-"}} YOUR ANSWER HERE +++ {"slideshow": {"slide_type": "slide"}} ## Challenge your understanding +++ {"slideshow": {"slide_type": "fragment"}} The following table gives the binary representions of unsigned decimal integers from 0 to 7. +++ | Binary | Decimal | |:------:|:-------:| | 000 | 0 | | 001 | 1 | | 010 | 2 | | 011 | 3 | | 100 | 4 | | 101 | 5 | | 110 | 6 | | 111 | 7 | +++ {"slideshow": {"slide_type": "fragment"}} Observe that the binary representations of 4, 5, 6, and 7 all have **1** in the leftmost (most significant) bit: | Binary | Decimal | |:-------:|:-------:| | 000 | 0 | | 001 | 1 | | 010 | 2 | | 011 | 3 | | **1**00 | **4** | | **1**01 | **5** | | **1**10 | **6** | | **1**11 | **7** | Therefore we can consider that bit as the answer to the following **yes/no** question: > Is the integer 4 or above? +++ {"slideshow": {"slide_type": "fragment"}} To convert binary to decimal, we can think of the conversion as a guessing game where - the binary sequence is a sequence of **yes (1)** or **no (0)** answers to certain **yes/no** questions, and - the informed guess is the integer represented by the binary sequence. ![Decoding tree](images/dt.dio.svg) +++ {"slideshow": {"slide_type": "subslide"}} **Exercise** What are the **yes/no** questions (Q2 and Q3 above) corresponding to the 2nd bit and 3rd bit? +++ {"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": "-"}} YOUR ANSWER HERE +++ {"slideshow": {"slide_type": "fragment"}} ````{hint} - [Binary Number System](https://www.mathsisfun.com/binary-number-system.html) - [Binary Number Conversions](https://www.purplemath.com/modules/numbbase.htm) ```` +++ {"slideshow": {"slide_type": "slide"}} ## Representing negative numbers +++ {"slideshow": {"slide_type": "fragment"}} The following also uses 3 bits to represent 8 numbers but half of the numbers are negative. +++ {"slideshow": {"slide_type": "-"}} | Binary | Decimal | |:-------:|:-------:| | 000 | 0 | | 001 | 1 | | 010 | 2 | | 011 | 3 | | **1**00 | **-4** | | **1**01 | **-3** | | **1**10 | **-2** | | **1**11 | **-1** | +++ {"slideshow": {"slide_type": "fragment"}} - The numbers 0, 1, 2, and 3 have the same binary representations as before, but - the binary representations for 4, 5, 6, and 7 are now used for -4, -3, -2, and -1. +++ {"slideshow": {"slide_type": "subslide"}} **What is the benefit of the above representation?** +++ {"slideshow": {"slide_type": "fragment"}} To subtract a positive binary number $x$ from another positive binary number $y$, it seems we can turn it into binary addition $$x - y = x + (-y)$$ of a positive binary number $x$ and a negative binary number $-y$. +++ {"slideshow": {"slide_type": "subslide"}} For example, $$ \overbrace{011_2}^{3} + \overbrace{100_2}^{-4} = \underbrace{111_2}_{-1} $$ +++ {"slideshow": {"slide_type": "subslide"}} It seem to work as well if there are bits carried forward, e.g., $1 + (- 3)$ in binary is +++ {"slideshow": {"slide_type": "-"}} $$ \begin{array}{rrrr} & 0 & \overset{1}0 & 1 \\ + & 1 & 0 & 1 \\\hline & 1 & 1 & 0 \end{array} $$ +++ {"slideshow": {"slide_type": "-"}} which translate to $-2$ in decimal as desired. +++ {"slideshow": {"slide_type": "subslide"}} **Exercise** There is a subtlety when computing $3 - 2$ using binary addition because $$ \overbrace{011_2}^3 + \overbrace{110_2}^{-2} = 1001_2$$ 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. +++ {"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": "-"}} YOUR ANSWER HERE +++ {"slideshow": {"slide_type": "-"}} ````{hint} - Can we drop one of the $4$ bits? - [Two's complement represenation](https://en.wikipedia.org/wiki/Two%27s_complement). ```` +++ ## Building a computer from transistors (Optional) +++ 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*. +++ Consider the addition of $2$ bits $A$ and $B$: $$ A + B = C\circ S $$ | A | B | C S | |:---:|:---:|:----------:| | 0 | 0 | 00 | | 0 | 1 | 01 | | 1 | 0 | 01 | | 1 | 1 | 10 | +++ There are transistors, called *logic gates*, that can carry out basic logic operations: - $A \operatorname{AND} B$: which returns $1$ if and only if both $A$ and $B$ are $1$, and $0$ otherwise. - $A \operatorname{XOR} B$: which returns $1$ if and only if either $A$ and $B$ are $1$ but not both. +++ **What is the logic in computing $C$ and $S$ from $A$ and $B$?** +++ Try out a logic gate simulator: - Visit https://logic.ly/demo/ - Select *1-Bit Full Adder*. +++ If you play minecraft, you can build the following devices based on how computers are built from logic gates: - an adder for binary addition: https://youtu.be/vtpTri-PZXY - a calculator for calculus: https://youtu.be/5NzIt9sns6o