Contents

Card guessing game

# Run this cell first to initialize the environment
import random  # for shuffling of the cards
from collections import namedtuple  # for naming the cards

Rules of the game

Consider a deck of 52 cards:

1 (A) 2 3 4 5 6 7 8 9 10 11 (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

  • 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)}\).

The following code creates a deck of cards. (You are not expected to understand the code for now.)

# 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

[Card(value=1, suit='Diamond'),
 Card(value=1, suit='Club'),
 Card(value=1, suit='Heart'),
 Card(value=1, suit='Spade'),
 Card(value=2, suit='Diamond'),
 Card(value=2, suit='Club'),
 Card(value=2, suit='Heart'),
 Card(value=2, suit='Spade'),
 Card(value=3, suit='Diamond'),
 Card(value=3, suit='Club'),
 Card(value=3, suit='Heart'),
 Card(value=3, suit='Spade'),
 Card(value=4, suit='Diamond'),
 Card(value=4, suit='Club'),
 Card(value=4, suit='Heart'),
 Card(value=4, suit='Spade'),
 Card(value=5, suit='Diamond'),
 Card(value=5, suit='Club'),
 Card(value=5, suit='Heart'),
 Card(value=5, suit='Spade'),
 Card(value=6, suit='Diamond'),
 Card(value=6, suit='Club'),
 Card(value=6, suit='Heart'),
 Card(value=6, suit='Spade'),
 Card(value=7, suit='Diamond'),
 Card(value=7, suit='Club'),
 Card(value=7, suit='Heart'),
 Card(value=7, suit='Spade'),
 Card(value=8, suit='Diamond'),
 Card(value=8, suit='Club'),
 Card(value=8, suit='Heart'),
 Card(value=8, suit='Spade'),
 Card(value=9, suit='Diamond'),
 Card(value=9, suit='Club'),
 Card(value=9, suit='Heart'),
 Card(value=9, suit='Spade'),
 Card(value=10, suit='Diamond'),
 Card(value=10, suit='Club'),
 Card(value=10, suit='Heart'),
 Card(value=10, suit='Spade'),
 Card(value=11, suit='Diamond'),
 Card(value=11, suit='Club'),
 Card(value=11, suit='Heart'),
 Card(value=11, suit='Spade'),
 Card(value=12, suit='Diamond'),
 Card(value=12, suit='Club'),
 Card(value=12, suit='Heart'),
 Card(value=12, suit='Spade'),
 Card(value=13, suit='Diamond'),
 Card(value=13, suit='Club'),
 Card(value=13, suit='Heart'),
 Card(value=13, suit='Spade')]

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.

random.choice(deck)  # random imported before

Card(value=4, suit='Club')

You are allowed to make an informed guess after the dealer answers some of your yes/no questions.

Card guessing game

For instance, you may ask:

  • Is the suit club?

  • Is the card diamond 1 (ace)?

  • Is the value at least 10?

However, you cannot ask:

  • What is the value?

  • What is the suite?

Exercise

You win if you can guess the card correctly with no more than 6 questions. What is the winning strategy?

YOUR ANSWER HERE

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?

Challenge the computer

Play the role of the dealer and test if the program below can guess the card correctly after 6 questions.

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}")

Exercise

Does the above program always win? Explain your answer?

YOUR ANSWER HERE

Challenge your understanding

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

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

100

4

101

5

110

6

111

7

Therefore we can consider that bit as the answer to the following yes/no question:

Is the integer 4 or above?

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

Exercise

What are the yes/no questions (Q2 and Q3 above) corresponding to the 2nd bit and 3rd bit?

YOUR ANSWER HERE

Hint

Representing negative numbers

The following also uses 3 bits to represent 8 numbers but half of the numbers are negative.

Binary

Decimal

000

0

001

1

010

2

011

3

100

-4

101

-3

110

-2

111

-1

  • 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.

What is the benefit of the above representation?

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\).

For example,

\[ \overbrace{011_2}^{3} + \overbrace{100_2}^{-4} = \underbrace{111_2}_{-1} \]

It seem to work as well if there are bits carried forward, e.g., \(1 + (- 3)\) in binary is

\[\begin{split} \begin{array}{rrrr} & 0 & \overset{1}0 & 1 \\ + & 1 & 0 & 1 \\\hline & 1 & 1 & 0 \end{array} \end{split}\]

which translate to \(-2\) in decimal as desired.

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.

YOUR ANSWER HERE

Hint

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:

If you play minecraft, you can build the following devices based on how computers are built from logic gates: