Binary Code - CS1302

Welcome to this lab where you will explore how computers represent numbers using a fun card-guessing game! Through this lab, you will gain an understanding of how binary numbers are used to represent decimal numbers in computers.

Card Guessing Game¶

Rules¶

Table 1 shows a deck of 52 cards:

Each card is in one of the four suits: Diamond ♦, Club ♣, Heart ♥, and Spade ♠.
Each card has a value ranging from 1 to 13. For simplicity, the original card values A, J, Q, and K are converted to the numerical values 1, 11, 12, and 13 respectively.

A player guesses a card drawn by a dealer. — Figure 1:Card guessing game

Rules

As depicted in Figure 1, the card-guessing game involves the following steps:

The dealer selects a card without revealing it to the player.
The player’s goal is to correctly guess the chosen card.
To make an informed guess, the player can ask up to six yes/no questions.
The dealer must answer each question truthfully and immediately.

Example 1 (Valid questions)

For instance, the player may ask:

Is the suit club?
Is the card diamond 1?
Is the value at least 10?

Example 2 (Invalid questions)

However, the player cannot ask:

What is the value?
What is the suit?

because the answers are not yes/no.

One strategy is to ask whether the randomly drawn card is a specific card, e.g.,

Is it the Diamond 1?

If the answer is yes, the player can confidently guess that the card is Diamond 1 and win the game. However, if the answer is no, the player can continue to check another card, e.g.,

Is it the Diamond 2?

and so on...

A pseudocode that summarizes the above strategy (or algorithm) is shown below.

Algorithm 1 (Checking one card at a time)

1
2
3
4
5
6
7
8
while the number of questions asked < 6 and \
      the correct card has not been guessed yet:
    randomly pick a new card not chosen before
    ask the dealer whether the drawn card is the chosen one
    if the answer is yes:
        guess the card and break out of the loop
    else:
        increment the number of questions asked

Exercise 1 (chance)

What is the chance of winning using the strategy in Algorithm 1?

Attention

Provide your answer in the following code cell by assigning a fraction to the variable chance such as

chance = 0.5

where the value 0.5 means 50% chance. This is just a demo, i.e., 50% is not necessarily the correct answer. Give your answer as accurate as possible.

# YOUR CODE HERE
raise NotImplementedError

# tests
assert chance >= 0
assert chance <= 1

# hidden tests

Virtual Cards¶

Instead of drawing a physical card, the dealer can use programming to generate a virtual deck and draw a random^[1] virtual card from it. Run the code below to get the required tools.

from collections import namedtuple  # for naming the cards
from random import choice  # for randomly drawing cards

You’ll learn the syntax in a future lecture, but even now, it is clear that the code imports libraries for creating named tuples and making random choices, thanks to the design of Python being a high-level programming language.

To create a deck of cards, run the following cell.

suits = ("Diamond", "Club", "Heart", "Spade")
values = range(1, 14)
Card = namedtuple("Card", ["value", "suit"])
deck = [Card(value, suit) for value in values for suit in suits]
deck

The code above uses composite data types like tuples and lists, which will be formally introduced later in the course. They are handy for storing and manipulating collections of values.

Now, you can use the following program to play the game with your friends:

choice(deck)

Exercise 2 (Draw multiple cards)

Can you fix the code below so that it can return 5 cards randomly drawn with replacement from the deck of cards?

1
2
3
def draw_five_cards_randomly():
    card1 = card2 = card3 = card4 = card5 = choice(deck)
    return  card1, card2, card3, card4, card5

def draw_five_cards_randomly():
    # YOUR CODE HERE
    raise NotImplementedError
    return  card1, card2, card3, card4, card5

# tests
import random

random.seed(1302)  # to make pseudo-random sequences reproducible
assert (lambda cards: any(cards[i] != cards[4] for i in range(4)))(
    draw_five_cards_randomly()
)

# hidden tests

Caution

While one may pass the visible test with an answer like

def draw_five_cards_randomly():
    card1 = card2 = card3 = card4 = card5 = choice(deck)
    card1 = 0
    return  card1, card2, card3, card4, card5

Who knows whether the hidden test would catch that card1 is not even a card in the deck? The hidden test can also be modified since it is not hard coded in the notebook.

Virtual Player¶

Given you have randomly drawn a card,

run the following code cell, and
answer the 6 questions raised by the player honestly by entering
- 1 for yes and
- 0 for no.

def is_yes(question):
    """Get an answer to a yes/no question."""
    return "1" == input(question + " 1:yes [0:no] ")


suit_idx = number = 0
if is_yes("Is the suite either heart or spade?"):
    suit_idx += 2
if is_yes("Is the suite either club or spade?"):
    suit_idx += 1
for i in range(3, -1, -1):
    number += 2**i * is_yes(f"Is the number {number+2**i} or above?")
print(f"The card is {suits[suit_idx]} {number}")

The code above provides an overview of various programming syntaxes to be covered in the course. Although you don’t need to be familiar with them now, it’s good to have a basic understanding:

The program first defines a function called is_yes that checks whether the answer to a given question is yes.
To compute the guess, the program modifies the values of the variables suit_idx and number using
- conditional if statements and
- a for loop, along with
- different operations such as
  - chained assignment =,
  - augmented assignment +=,
  - equality comparison ==, and
  - exponentiation **.

Exercise 3 (Resolution of uncertainty)

Hope you are convinced that the virtual player has a winning strategy. Indeed, the answers to 6 questions not only resolve the uncertainty of a random draw from 6 cards, but they can also resolve a random draw from over 52 cards. Fix the following function number_of_cards so that it returns the maximum number of cards from which a random draw can be resolved by the answers to a number of questions specified by an integer assigned to the variable number_of_questions.

1
2
3
def number_of_cards(number_of_questions):
    ans = number_of_questions
    return ans

You may assume one can add new values/suits so that a deck may have an arbitrarily number of distinct cards.

def number_of_cards(number_of_questions):
    # YOUR CODE HERE
    raise NotImplementedError
    return ans

# tests
assert number_of_cards(number_of_questions=6) > len(deck)

# hidden tests

Binary Number System¶

Representing non-negative integers¶

The following table gives the binary representions of unsigned decimal integers from 0 to 7.

Table 2:Encoding positive integers

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. Consider that bit as the answer to the following yes/no question when converting an integer n to binary:

Is the integer 4 or above, i.e., $n\geq 4$ ?

Now, to convert the entire binary sequence 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.

The following code attempts to convert integers between 0 and 7 to their binary strings.

def decimal_to_binary(n):
    def get_bit(cond):
        return "1" if cond else "0"
    return get_bit(eval(Q1)) + get_bit(eval(Q2)) + get_bit(eval(Q3))

# Define the questions
Q1, Q2, Q3 = "n >= 4", "n >= 2", "n >= 1"

# Print the conversions decimal (binary)
print(*[f"{i} ({decimal_to_binary(i)})" for i in range(8)], sep="\n")

# Assign strings to Q2 and Q3
# YOUR CODE HERE
raise NotImplementedError
Q2, Q3

# test
assert decimal_to_binary(2) == '010'
assert decimal_to_binary(4) == '100'
assert decimal_to_binary(5) == '101'
assert decimal_to_binary(6) == '110'

# hidden tests

Representing negative numbers¶

The following also uses 3 bits to represent 8 integers but half of them are negative.

Table 3:Encoding positive integers

Binary	Decimal
000	0
001	1
010	2
011	3
100	-4
101	-3
110	-2
111	-1

What is the benefit of the above representation?

To subtract a positive binary number $x$ from another positive binary number $y$ , i.e.,

x - y,

(1)

it seems we can instead perform the binary addition

x + (-y)

(2)

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}

(3)

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

\begin{array}{rrrr} & 0 & \overset{\color{blue} 1}0 & 1 \\ + & 1 & 0 & 1 \\\hline & 1 & 1 & 0 \end{array}

(4)

which translate to -2 in decimal as desired.

Exercise 5 (overflow)

There is a subtlety when computing $3 - 2$ using binary addition because

\overbrace{011_2}^3 + \overbrace{110_2}^{-2} = 1001_2

(5)

which overflows to 4 bits, a seemingly invalid binary representation. Fortunately, there is a simple fix so binary addition can still apply to the above case. Come up with such a fix that also works for other cases such as $3-3$ , $2-1$ , $-2-1$ , etc.

\overbrace{101_2}^3 + \overbrace{110_2}^{-2} = 1011_2

(6)

YOUR ANSWER HERE

Logic Gates¶

A computer is built from transistors that operates on binary states on/off, which is also represented as bits 1/0, or the boolean value true/false. Play with the following simulator to see some examples.

Logic simulator

Click the logic simulator header above.
Select 1-Bit Full Adder.
Change the input and observe the output.

Table 4 gives the input and output relationship of a simpler adder, called the half adder, which computes the addition of two input bits $A$ and $B$ as

A + B = C\circ S

(7)

where $C$ and $S$ are the output bits, and $C\circ S$ is the concatenation of two bits $C$ and $S$ .

Table 4:Adder.

A	B	C∘S
0	0	00
0	1	01
1	0	01
1	1	10

The operation can be built using transistors, called logic gates, that can carry out basic logic operations such as

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

The input and output relationships are listed below:

from pandas import DataFrame

DataFrame(
    [[A, B, A & B, A ^ B] for A in (0, 1) for B in (0, 1)],
    columns=["A", "B", "A AND B", "A XOR B"],
)

YOUR ANSWER HERE

Glossary¶

algorithm: An algorithm is a set of instructions that a computer program follows to solve a problem or complete a task. It is a step-by-step approach designed to be efficient and accurate.
bitwise operator: Bitwise operators are used to manipulate individual bits of binary numbers. They allow for the manipulation of data at a low level, such as setting or clearing specific bits, shifting bits left or right, or performing logical operations on bits.
composite data type: A composite data type groups related data into a single unit so that they can be easily stored and manipulated together.
conditional: A conditional statement is used to perform different actions based on different conditions. It allows the program to make decisions and execute specific code blocks based on the evaluation of a given condition.
iteration: An iteration is a repeated execution until a condition is met. It allows for the efficient repetition of tasks without the need for writing the same code multiple times.
library: A library is a collection of pre-written code that developers can use to perform common tasks. It contains functions, classes, and other reusable code that can be integrated into a larger software application, saving time and effort.
pseudocode: Pseudocode is a high-level description of a program or algorithm, using natural language and code-like syntax to express logic without being bound to a specific programming language. It is used during planning and design phases of software development.

	1	2	3	4	5	6	7	8	9	10	J	Q	K
Diamond
Club
Heart
Spade