15.1. A Guided Solution to Musical Chairs
≪ 15. Week 9 Tuesday: Practise with Designing Structs | Table of Contents | 16. Week 9 Thursday: Classes and File Organisation ≫In class, we went over the following problem together:
Problem 1. Musical Chairs
You’re a teacher at a Kindergarten, but due to the pandemic, you had to move your class to Zoom. You were going to play musical chairs, but due to being on Zoom you’re stuck with just simulating musical chairs while your young students rot at home.
Suppose you have \(n\) students. They start by sitting in a circle of chairs labelled \(1,2,\ldots,n\), increasing clockwise (i.e., the numbering is arranged like a clock). For the first round, the students get up and move some number of seats clockwise before sitting back down. Whoever ends up in the last chair is removed from the game.
Now that \(n-1\) students are left in the game, the above process can be repeated. This time, however, the students move counterclockwise instead of clockwise. The student in position \(n-1\) is eliminated. This repeats, with the students alternating between clockwise and counterclockwise, until one student is left, who is the winner.
Write a C++ program that accepts an integer \(n\) as input (the number of students), followed by the \(n\) students’ names (no spaces). For each round of the game, prompt the user for how many chairs the students move, and print out the name of the student that’s eliminated. At the end of the game, print out who the winner is.
SAMPLE RUN:
INPUT 3
INPUT Adam Barry Claude
OUTPUT Enter the movement for round 1:
INPUT 5
OUTPUT Adam has been eliminated.
OUTPUT Enter the movement for round 2:
INPUT 2
OUTPUT Claude has been eliminated.
OUTPUT Barry is the winner!
We went through this example rather quickly, and here’s a writeup of what we talked about.
Our first step, of course, is to digest the problem into pseudocode. The user needs to input the number chairs (and therefore the number of players), followed by their names, in order. Then, the user needs to input how many chairs everyone moves each round. At the end, the winner is decided. In pseudocode,
- Input an integer \(n\).
- Have the user input a list of \(n\) names, which represent the players in their starting order. Make a list of players.
- Repeat \(n-1\) times:
- Prompt the user for how many chairs everybody moves.
- On odd rounds (rounds 1, 3, 5, …), move each player clockwise.
- On even rounds, move each player counterclockwise.
- Eliminate the player in the last chair.
- Print out the only player left.
This is a prime example of where object-oriented programming is helpful: we need to keep track of each of the players’ names, which chair each player is in, and if each player has been eliminated or not. These comprise the three private variables in a player struct! To create a new player in the game, we just need to tell them what their name is and which chair they start in. Here’s our very minimal struct, with a constructor!
1struct player {
2private:
3 string name;
4 int chair;
5 bool alive = true;
6
7public:
8 player(string new_name, int new_chair) {
9 name = new_name;
10 chair = new_chair;
11 }
12};
No matter what, every player should start the game alive; we thus gave the alive private boolean a default value of true.
This allows us to now implement steps 1 and 2 above. The following code belongs in the main function:
1// 1. input an integer n
2int n;
3cin >> n;
4
5// 2. create a list of n players with the user's inputted names
6vector<player> players;
7for(int chair = 1; chair <= n; chair++) {
8 // ask for a name
9 string name;
10 cin >> name;
11
12 // create a new player with this name in the current chair
13 player new_player(name, chair);
14
15 // add this new player to the list of players
16 players.push_back(new_player);
17}
In the sample run, \(n=3\), and the user inputs the names Adam Barry Claude. If you follow the for loop above, the code will create a list of 3 players: a player named Adam in chair 1, a player named Barry in chair 2, and a player named Claude in chair 3. All of them are alive at the start.
Something we’ll need to keep track of is how many chairs are left in the game. After all, we’ll be looking for the person in the last chair. The last chair goes down by one every round, and it starts at chair \(n\). Thus, we may set up a loop for the main game (step 3) as follows:
1// 3. repeat n-1 rounds of musical chairs
2int last_chair = n;
3for(int round = 1; round <= n - 1; round++) {
4 // have user input movement
5 // on odd rounds, move everyone clockwise
6 // on even rounds, move everyone counterclockwise
7 // eliminate the person in the last chair
8 last_chair--;
9}
Within the intermediate steps, we need a way to move our players in either direction. Since the chair member variable in the player struct is private, we’ll need to write two public member functions to do this for us! We’ll call these public member functions from main, which will in turn modify the private variables. Likewise, when we eliminate the last player, we need to be able to change the alive variable to false. Moreover, we need a way to see which chair everybody’s sitting in. Finally, we need to print out a message that states who got eliminated. This means we need to be able to read each player’s name, even though that’s still a private member variable!
We should update our player struct with some new public member functions. Try to implement these updates yourself before peeking at the answer. You may come up with a different implementation than me, and that’s okay! There are many different approaches to this problem.
Updated player struct
1struct player {
2private:
3 string name;
4 int chair;
5 bool alive = true;
6
7public:
8 player(string new_name, int new_chair) {
9 name = new_name;
10 chair = new_chair;
11 }
12
13 // moves a player clockwise.
14 // not only does the player need to know how many seats
15 // they're moving, but they also need to know how many seats
16 // are in the game! This is because the seats are in a circle,
17 // and moving 5 chairs clockwise produces a different result
18 // depending on the number of chairs left.
19 void move_clockwise(int movement, int chairs_left) {
20 chair = (chair + movement) % chairs_left;
21 if(chair == 0) {
22 chair = chairs_left;
23 }
24 }
25
26 // moves a player counterclockwise
27 void move_counterclockwise(int movement, int chairs_left) {
28 // magic with the % operator -- why does this work??
29 chair = (chair - movement) % chairs_left;
30 if(chair <= 0) {
31 chair += chairs_left;
32 }
33 }
34
35 // eliminates a player from the game
36 void eliminate() {
37 alive = false;
38 }
39
40 // retrieves a player's chair
41 int get_chair() {
42 return chair;
43 }
44
45 // retrieves a player's name
46 string get_name() {
47 return name;
48 }
49};
Using these new public member functions, we can implement step 3 directly from the pseudocode, more or less:
1// 3. repeat n-1 rounds of musical chairs
2int last_chair = n;
3for(int round = 1; round <= n - 1; round++) {
4 // have user input movement
5 int movement;
6 cin >> movement;
7
8 // on odd rounds, move everyone clockwise
9 // on even rounds, move everyone counterclockwise
10
11 // this loops through the list of all players and tells them
12 // to move however many chairs in the right direction.
13 for(int i = 0; i < n; i++) {
14 if(round % 2 == 1) {
15 players.at(i).move_clockwise(movement, last_chair);
16 } else {
17 players.at(i).move_counterclockwise(movement, last_chair);
18 }
19 }
20
21 // eliminate the person in the last chair
22 // this loops through the lits of all players and eliminates
23 // whoever's sitting in the last chair.
24 for(int i = 0; i < n; i++) {
25 if(players.at(i).get_chair() == last_chair) {
26 players.at(i).eliminate();
27 cout << players.at(i).get_name()
28 << " has been eliminated." << endl;
29 }
30 }
31
32 last_chair--;
33}
This code may look intimidating since it’s mixed in with accessing parts of a vector, but it’s a pretty close match to our pseudocode! For instance, line 15 says, “Tell the the index \(i\) player in my list of players to move some number of chairs clockwise”. This updates that player’s chair to wherever they end up.
On line 25, the snippet players.at(i).get_chair() asks the player at index \(i\) for which chair they’re currently sitting in, then checks if that’s equal to the last chair. If it is, line 26 is run, which just tells the player at index \(i\) to get eliminated. Line 27 prints out their name and states that they’ve been eliminated.
Try to finish the last step of the program yourself, if you can! After the for loop concludes, you need to find who the last person standing is. There’s a hint below if you’re stuck, and the full solution is below that.
Hint
Full Solution
1#include <iostream>
2#include <string>
3#include <vector>
4
5using namespace std;
6
7struct player {
8private:
9 string name;
10 int chair;
11 bool alive = true;
12
13public:
14 player(string new_name, int new_chair) {
15 name = new_name;
16 chair = new_chair;
17 }
18
19 // moves a player clockwise.
20 // not only does the player need to know how many seats
21 // they're moving, but they also need to know how many seats
22 // are in the game! This is because the seats are in a circle,
23 // and moving 5 chairs clockwise produces a different result
24 // depending on the number of chairs left.
25 void move_clockwise(int movement, int chairs_left) {
26 chair = (chair + movement) % chairs_left;
27 if(chair == 0) {
28 chair = chairs_left;
29 }
30 }
31
32 // moves a player counterclockwise
33 void move_counterclockwise(int movement, int chairs_left) {
34 // magic with the % operator -- why does this work??
35 chair = (chair - movement) % chairs_left;
36 if(chair <= 0) {
37 chair += chairs_left;
38 }
39 }
40
41 // eliminates a player from the game
42 void eliminate() {
43 alive = false;
44 }
45
46 // retrieves a player's chair
47 int get_chair() {
48 return chair;
49 }
50
51 // retrieves a player's name
52 string get_name() {
53 return name;
54 }
55
56 // determines if this player is still in the game
57 bool is_alive() {
58 return alive;
59 }
60};
61
62int main() {
63 // 1. input an integer n
64 int n;
65 cin >> n;
66
67 // 2. create a list of n players with the user's inputted names
68 vector<player> players;
69 for(int chair = 1; chair <= n; chair++) {
70 // ask for a name
71 string name;
72 cin >> name;
73
74 // create a new player with this name in the current chair
75 player new_player(name, chair);
76
77 // add this new player to the list of players
78 players.push_back(new_player);
79 }
80
81 // 3. repeat n-1 rounds of musical chairs
82 int last_chair = n;
83 for(int round = 1; round <= n - 1; round++) {
84 // have user input movement
85 int movement;
86 cin >> movement;
87
88 // on odd rounds, move everyone clockwise
89 // on even rounds, move everyone counterclockwise
90
91 // this loops through the list of all players and tells them
92 // to move however many chairs in the right direction.
93 for(int i = 0; i < n; i++) {
94 if(round % 2 == 1) {
95 players.at(i).move_clockwise(movement, last_chair);
96 } else {
97 players.at(i).move_counterclockwise(movement, last_chair);
98 }
99 }
100
101 // eliminate the person in the last chair
102 // this loops through the lits of all players and eliminates
103 // whoever's sitting in the last chair.
104 for(int i = 0; i < n; i++) {
105 if(players.at(i).get_chair() == last_chair) {
106 players.at(i).eliminate();
107 cout << players.at(i).get_name()
108 << " has been eliminated." << endl;
109 }
110 }
111
112 last_chair--;
113 }
114
115 // 4. determine who the last person standing is, and print that out.
116 for(int i = 0; i < n; i++) {
117 if(players.at(i).is_alive()) {
118 cout << players.at(i).get_name()
119 << " is the winner!" << endl;
120 }
121 }
122
123 return 0;
124}
}