Computing help and support
Bridge: A C++ programming Exercise
This exercise offers practise with user-defined classes, vectors, and the Standard Library’s algorithms.
The vector class
When C++ was developed from C the designers realised that arrays were a weakness and introduced vectors. In the exercise to come you will need to store variables in containers with sizes that change at run time. The vector template class, part of the C++ Standard Library, is just this sort of collection. To declare a vector with elements of type double use
vector<double> v;
The type of element that the vector holds is written between the angle brackets. The vector declared above, holding elements of type double, is initially empty. You can…
- get the number of elements in the vector with the size() member function:
cout << v.size() << endl;
- append an element onto the back of the vector using the push_back(...) member function:
v.push_back(3.14); // increases v.size() by 1 v.push_back(2.71); // increases v.size() by 1
- access the elements of the vector using ‘[]’ as if you were using an array (the index of first element is 0):
cout << v[0] << endl; v[1] = 1.68;
- declare a vector with a known size:
vector<int> some_ints(10); // 10 int elements, uninitialized
- specify a default value in the declaration:
vector<double> some_reals(10, 0.0); // 10 real numbers, all zero
- loop through the vector forwards…
for (unsigned int i=0; i<v.size(); ++i) { cout << v[i] << " "; } - …or backwards:
for (int i=v.size()-1; i>=0; --i) { cout << v[i] << " "; } - C++ has dozens of functions that can be used with vectors to sum, sort, shuffle and search the elements. Here’s a simple example
#include <vector> // needed for vector #include <algorithm> // needed for reverse and count using namespace std; int main() { vector<int> v(3); // Declare a vector of 3 ints v[0] = 7; v[1] = v[0] + 3; v[2] = v[0] + v[1]; // reverse the elements reverse(v.begin(), v.end()); // count the number of elements that have the value 10 int num=count(v.begin(), v.end(), 10); }
Note that this uses the begin() and end() member functions of vector to describe how much of the vector to deal with (in this case all of it)
There’s also a count_if routine to count elements that match a more complicated condition than equality. Rather than taking a value as its final argument, it needs the name of a function. This named function will be given an element of the vector by count_if and needs to return true or false depending on whether the element matches the condition. Here’s an example
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool multiple_of_three(int num) {
return not (num%3);
}
int main() {
// create a vector big enough to hold 10 ints
vector<int> v(10);
fill(v.begin(), v.end(), 1);
partial_sum(v.begin(), v.end(),v.begin() );
// v now contains 1....10
cout << count_if(v.begin(), v.end(), multiple_of_three) << " elements are a multiple of 3" << endl;
}
Using class
In C++, you can group multiple variables together into a named type by defining a class:
class Person {
public:
string name;
int age;
double height, weight;
};
You can access the fields, called members, using the ‘.’ operator, and you can assign variables of the same class type to each other:
Person a, b; // declare two variables of type Person
a.name = "Foo Bar";
a.weight = 70.0;
a.height = 1.5;
a.age = 21;
b = a; // all members of a are assigned from b
cout << b.name << " is " << b.age << " years old, "
<< b.height << "m tall, and weighs " << a.weight << "kg" << endl;
You can pass variables of type Person to functions, and use them as return values. You can also declare a vector with Person elements:
vector<Person> people(7); people[3].age = 47;
Redefining operators
If you are going to use containers with data types you’ve defined, you can’t assume that the standard algorithms will work. Some of the algorithms need to copy elements, so you need to ensure that you provide the appropriate constructors if your data types can’t be naively copied. You may also need to redefining operators. sort uses < on the elements to compare values, so to sort objects of type Person the “less-than” operator (<) could be used to give a result that depends on the age field. The following example shows how to make sort work with a vector of Persons. The notation may look alarming, but once you have a working example you can keep adapting it.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Person {
public:
string name;
int age;
double height, weight;
};
bool operator <(const Person& person1,const Person& person2 ) {
return person1.age < person2.age;
}
vector<Person> people(4);
int main() {
people[0].age=7;
people[1].age=3;
people[2].age=9;
people[3].age=6;
for (int i=0;i<4;i++)
cout << people[i].age << endl;
sort(people.begin(), people.end());
for (int i=0;i<4;i++)
cout << people[i].age << endl;
}
A game of Bridge
Bridge uses a pack of 52 playing cards. There are 4 suits (spades, hearts, diamonds, clubs) each of 13 cards: 1 (the Ace) to 10 and Jack, Queen, King. The Ace is the highest card, followed by the King, Queen, down to the 2. In bridge there are 2 teams of 2 players.
- Create a class called Card to represent a card. It will need 2 fields: one to store the card’s value (1-13) and one to store the suit.
- Create a vector of 52 cards. Call it pack. Set the value of the fields of these cards so that the vector represents a full pack.
- Shuffle the cards.
- In bridge each player’s set of cards is called a hand. The following code creates a vector of 4 hands (hand[0] ... hand[3]), each of which is a vector of cards.
const int numberOfPlayers=4; vector< vector<Card> > hand(numberOfPlayers);
These vectors are initially empty. Write some code that deals the cards out from the shuffled pack so that each player has a hand of 13 cards.
- In bridge people often use a evaluation system where an Ace is worth 4 points, a King 3, a Queen 2 and a Jack 1. Write a function that given a hand of cards evaluates it, returning the number of points it’s worth. Compile and run it.
- In bridge the teams try to win tricks (a set of 4 cards, one put down by each player sequentially). Players should try to “follow suit” – e.g. if the first card of a trick is a Spade, subsequent players must put down a Spade if they have one. In our game the winner of the trick is the person who puts down the highest card with the suit of the first card (like “No Trumps” in bridge). We’ll use the following strategy initially
- The first player puts down a random card
- Subsequent players will try to follow suit. If they can’t, they put down a random card. If they can follow suit then they put down the lowest card they have if they can’t beat the currently best card, otherwise they put down their best card.
A function to play a card will need to know what cards are available to play, the first card put down, and the best card put down so far. The card it puts down will have to be removed from the hand, so the hand parameter needs to be passed by reference (allowing it to be changed). If the card put down is the best so far, then that variable will need changing too. Write a function to implement this with the following prototype
bool playACard(vector<Card> &hand, Card firstCard, Card &bestCardSoFar);
Make it return true if the card put down is the best card so far.
Part of the task involves find the best and worst cards (if any) in the suit of the trick’s first card. As a exercise (non-trivial, but useful) try to do this without using for loops. Perhaps easiest is do the following
- Use remove_copy_if to extract from the hand all cards of the required suit and put them in a new vector (called onesuit say). Use something like
remove_copy_if(hand.begin(), hand.end(), onesuit.begin(), suitTester);
where suitTester is a routine that returns true if the card is the right suit.
- If suitTester isn’t empty, use the max_element and min_element algorithms to find the best and worst cards of the suit. These routines depend on > and < working for the card class, so add 2 lines to the code to make these compare the value fields of the objects.
- Write a routine to play a game using the code you’ve already written, identifying who wins each trick. The player who wins a trick puts the first card of the next trick down (this isn’t too easy – see the step-by-step guide for the answer if you get stuck, but have a go first).
- Add some code to print out how many tricks each team wins (players 0 and 2 are one team, players 1 and 3 the other). Check that a total of 13 tricks are won.
- Try to improve the first player’s strategy by making them play the best card they have rather than a random card.
- Now let’s introduce the idea of “trumps”. In bridge a suit is often chosen to be the trump suit. Create a variable called trumpsuit and set it at random to one of the suits. Write a function called countTrumps that given a hand and the trump suit returns how many trumps are in the hand. If you use count_if you can do this without using a loop.
- If a player can’t follow suit they are allowed to “trump” the card by putting down a card that’s a trump. If subsequent players also can’t follow suit they are allowed to “overtrump” – put a higher trump card down. Change the playACard code to take advantage of the new possibilities.