// cards.cpp
#include <iostream>
#include <vector>
#include <cstdlib>
#include <cassert>
#include <algorithm>
#include "cmpt_error.h"
using namespace std;
enum class Color {
red, black
};
ostream& operator<<(ostream& out, Color c) {
if (c == Color::red) {
out << "red";
} else {
out << "black";
}
return out;
}
enum class Suit {
spades, hearts, diamonds, clubs
};
ostream& operator<<(ostream& out, Suit s) {
if (s == Suit::spades) {
out << "spades";
} else if (s == Suit::hearts) {
out << "hearts";
} else if (s == Suit::diamonds) {
out << "diamonds";
} else {
out << "clubs";
}
return out;
}
class Card {
int value;
Suit suit;
public:
Card(int val, Suit s)
: value(val), suit(s)
{
if (val < 1 || val > 13) cmpt::error("bad card value");
}
Suit get_suit() const { return suit; }
int get_value() const { return value; }
string name() const {
switch (value) {
case 1: return "ace";
case 11: return "jack";
case 12: return "queen";
case 13: return "king";
default: return to_string(value);
}
}
Color get_color() const {
if (suit == Suit::spades || suit == Suit::clubs) {
return Color::black;
} else {
return Color::red;
}
}
}; // class Card
ostream& operator<<(ostream& out, const Card& c) {
out << c.name() << " of " << c.get_suit();
return out;
}
vector<Card> make_deck() {
vector<Card> deck;
for(int i = 1; i <= 13; ++i) {
deck.push_back(Card{i, Suit::spades});
deck.push_back(Card{i, Suit::hearts});
deck.push_back(Card{i, Suit::diamonds});
deck.push_back(Card{i, Suit::clubs});
}
return deck;
}
//
// Implements the standard Fisher-Yates shuffle for fairly scrambling n items.
// Note that the expression for initializing r is in the range [i, n), e.g.:
//
// i <= i + rand() % (n - i) < n
//
void shuffle(vector<Card>& cards) {
const int n = cards.size();
for(int i = 0; i < n - 1; ++i) {
int r = i + rand() % (n - i);
swap(cards[i], cards[r]);
}
}
void shuffle_test() {
Card c{3, Suit::hearts};
cout << c << "\n";
vector<Card> deck = make_deck();
shuffle(deck);
for(Card c : deck) cout << c << "\n";
}
// If you look carefully at what a standard "cut" does to a deck of cards, you
// will see that it corresponds to a "rotation", i.e. moving all cards down
// some fixed amount, with cards at the end wrapping around to the start.
//
// This kind of rotation turns out to be a useful operation for many
// algorithms, and so the C++ STL provides std::rotate.
void cut(vector<Card>& cards, int cut_loc) {
assert(0 <= cut_loc && cut_loc <= cards.size());
const int n = cards.size();
rotate(cards.begin(),
cards.begin() + (n - cut_loc),
cards.end());
}
void cut_random(vector<Card>& cards) {
int r = rand() % cards.size();
cut(cards, r);
}
void rotate_test() {
vector<int> v = {1, 2, 3, 4, 5, 6, 7};
rotate(v.begin(), v.begin() + 3, v.end());
for(int x : v) cout << x;
cout << "\n";
}
//
// The following function implements a self-working magic trick that goes like
// this:
//
// 4 jacks, 4 queens, 4 kings and 4 aces meet at a hotel. After dinner,
// they form a stack of cards consisting of all the jacks together,
// followed by all the queens together, followed by all the kinds together,
// followed by all the aces. They then "dance" by cutting the cards at any
// point, any number of times. After dancing, they go back to their rooms
// by dealing cards from the top of the deck into four separate piles.
// Surprisingly, all the cards are in their rooms together!
//
void card_trick() {
vector<Card> room1 = {Card{1, Suit::spades}, Card{1, Suit::hearts},
Card{1, Suit::clubs}, Card{1, Suit::diamonds},
};
vector<Card> room2 = {Card{11, Suit::spades}, Card{11, Suit::hearts},
Card{11, Suit::clubs}, Card{11, Suit::diamonds},
};
vector<Card> room3 = {Card{12, Suit::spades}, Card{12, Suit::hearts},
Card{12, Suit::clubs}, Card{12, Suit::diamonds},
};
vector<Card> room4 = {Card{13, Suit::spades}, Card{13, Suit::hearts},
Card{13, Suit::clubs}, Card{13, Suit::diamonds},
};
// combine all the cards into one pile
vector<Card> pile;
pile.insert(pile.end(), room1.begin(), room1.end());
pile.insert(pile.end(), room2.begin(), room2.end());
pile.insert(pile.end(), room3.begin(), room3.end());
pile.insert(pile.end(), room4.begin(), room4.end());
// do some random cuts
for(int i = 0; i < 9; ++i) {
cut_random(pile);
}
// put the cards back into the rooms
int p = 0;
for(int i = 0; i < 4; ++i) {
room1[i] = pile[p++];
room2[i] = pile[p++];
room3[i] = pile[p++];
room4[i] = pile[p++];
}
cout << "room 1\n";
for (Card c : room1) cout << " " << c << "\n";
cout << "\n";
cout << "room 2\n";
for (Card c : room2) cout << " " << c << "\n";
cout << "\n";
cout << "room 3\n";
for (Card c : room3) cout << " " << c << "\n";
cout << "\n";
cout << "room 4\n";
for (Card c : room4) cout << " " << c << "\n";
cout << "\n";
}
// This is a helper function for the next function. It returns true when the
// first 5 elements of cards have the same suit, and false otherwise.
bool top_5_same_suit(const vector<Card>& cards) {
assert(cards.size() >= 5);
Suit s = cards[0].get_suit();
return cards[1].get_suit() == s && cards[2].get_suit() == s
&& cards[3].get_suit() == s && cards[4].get_suit() == s;
}
//
// What is the probabilty that you will be dealt 5 cards all the same suit
// from a standard deck of 52 shuffled cards?
//
// Another way of stating this is: if you shuffle a standard deck of 52 cards,
// what is the probability that the top 5 cards are all the same suit?
//
// To answer this question, we simulate dealing 5 cards from a deck a few
// thousand times, keeping a count of how often the first 5 cards the same
// suit. If we do this enough time, we can get a pretty good estimate of the
// correct probability.
//
// Note that the exact probability can be derived mathematically, which is
// something that you might learn in a probability and statistics course (or a
// course like MACM 101). It turns out the exact probability is 33/16660,
// which is about 0.00198, i.e. about 0.198% chance.
void top_5_same_suit_experiment() {
vector<Card> cards = make_deck();
int count = 0;
const int num_trials = 1000000;
for(int i = 0; i < num_trials; ++i) {
shuffle(cards);
if (top_5_same_suit(cards)) {
count++;
}
}
cout << count << " out of "
<< num_trials << " deals had first 5 cards all the same suit\n";
cout << 100 * (double(count) / num_trials)
<< "% chance of being dealt 5 cards of the same suit\n";
}
int main() {
srand(time(NULL));
// shuffle_test();
// rotate_test();
// card_trick();
top_5_same_suit_experiment();
}