15. Week 9 Tuesday: Practise with Designing Structs
≪ 14. Week 8 Tuesday: Object-Oriented Programming and Structs | Table of Contents | 15.1. A Guided Solution to Musical Chairs ≫Last week, we introduced structs and described their purpose in the context of object-oriented programming. Today, we’ll do a quick recap of the syntax and different components in each struct before getting some practise with them.
The primary focus will be program organisation. The ideal is to have code that’s as close to natural language as possible. On one hand, this improves maintainability since the code will be easier to understand, expand, and rewrite. On the other hand, this forces us to modularise our code, a reflection of how our own minds usually organise information.
Recap: What’s in a Struct?
Remember that a struct describes a new data type for C++. We generally refer to these user-defined data types as “objects”. Not only do objects hold collections of data (which may include other objects), but they may also perform actions that advance the state of the program or obtain important features and information.
The syntax of a struct is as follows:
1struct [struct name] {
2private:
3 // private variables and functions
4
5public:
6 // public variables and functions
7};
One may declare variables and functions exactly the same way one usually would outside of a struct. Private variables and functions are only accessible from within the struct, whereas public variables and functions may be accesses from anywhere in the program.
Remark 1. Encapsulation
A cornerstone of object-oriented programming is the concept of encapsulation: the program should not have access to the internal data of any objects, and it should interface with the object and its internal data only through the use of public functions.
Most often, the reason for this design paradigm is so that the struct can enforce restrictions on its internal data, which in turn allow it to make simplifying assumptions. For instance, think about making a struct that represents a date and a time. Under no circumstances should the month be 13. If the month were a public variable, the only way to enforce this restriction is if every programmer to use your struct just knows not to set the month to 13, which I think is a big ask.
A special function that you may want to declare is the constructor, which is ran the moment you declare an object. The constructor typically sets up all of the member variables in the struct based on several pieces of information provided through its parameters. The syntax of a constructor is very similar to the syntax of a regalur function, but it has some differences:
- The constructor’s name must match the struct’s name exactly, including capitalisation.
- The constructor cannot have a return type. This does not mean that the constructor should be a void type; see below.
Here’s an example of declaring a struct that contains some information about annual income:
1struct income_record {
2private:
3 double gross_income, net_income;
4 double deductibles, federal_tax, state_tax;
5
6public:
7 // constructor!
8 // the program must provide a gross income and deductibles;
9 // the other fields are computed from these two pieces of
10 // information.
11 income_record(double gross, double deduct) {
12 gross_income = gross;
13 deductibles = deduct;
14
15 double taxable = gross - deduct;
16 if(taxable < 0) {
17 taxable = 0;
18 }
19
20 federal_tax = 0.375 * taxable;
21 state_tax = 0.05 * taxable;
22 net_incom = gross_income - federal_tax - state_tax;
23 }
24
25 // other public functions
26 // prints out a completed tax return form for this year.
27 void print_tax_return() {
28 // ...
29 }
30};
Common Mistake 2. Parameter Names in Constructors
In the above example, it’s very tempting to declare the constructor as
However, lines 12 and 13 become very messy: there are two different variables named gross_income — one is the private member variable, and the other is a parameter for the constructor! For this class, you should avoid reusing the same name in the struct and in the constructor.
Beyond this class, one convention is to prepend an underscore to each private variable, e.g. double _gross_income, _net_income; replacing line 3. Another workaround is to use the this keyword.
Practise with Designing and Writing Structs
For the following scenarios, provide pseudocode that describes a program that completes the tasks at hand. If you will be using any objects, describe the structs that define them — indicate all of the member variables, describe the constructor, and describe all of the public member functions you will use in pseudocode.
At this stage, our programs are becoming quite complex, and they involve numerous design decisions based on how you think about and approach each problem. This means that two different programmers may come up with very different answers to these problems, and that’s totally okay!
If you have time, go ahead and try to code up your solutions. If you think the pseudocode is too cumbersome and boring, feel free to skip it and code a solution directly. I will warn you that when approaching very complex projects, you may encounter an unforseeable difficulty that necessitates a radical shift in how you organise your objects and functions throughout your program. These are often clear when you write pseudocode, and changing pseudocode is rather painless. However, scrapping an entire program and rewriting it with a different structure is frustrating and painful, and I hope this doesn’t happen to you.
Problem 3. 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!
Problem 4. Tic Tac Toe
You and your hypercompetitive friend want to see who’s better at Tic Tac Toe. Since you’re environmentally conscious, you opt to write a computer program to simulate Tic Tac Toe instead of wasting paper.
Write a C++ program that asks for the two players’ names, then asks for an integer \(n\). Then, the program allows the two players to play Tic Tac Toe until someone has won \(n\) times (i.e., first to \(n\) wins). Player one goes first in the first round, and the leading player alternates from there. The program ends once \(n\) wins have been reached, and that player is the champion.
Note: it is up to you how you take input for each move, how you handle illegal moves, etc.
Challenge 5. Flight Boarding
(This problem was inspired by a CGP Grey video.)
You work for a major airline, which has determined that long boarding times are a major cause of customer disatisfaction. They approach you, one of the world’s best programmers, to simulate the boarding process and to better understand why everything is so inefficient.
They’ll start you off on the smaller planes, which have a single aisle. Each row has two seats on either side of the aisle:
1A 2A 3A 4A
1B 2B 3B 4B <-- More seats -->
HEAD ...AISLE... TAIL
1C 2C 3C 4C <-- More seats -->
1D 2D 3D 4D
The aisle is only wide enough for one person at a time, so passengers must board in a single file line. It takes each passenger 2 seconds to walk from one row to the next. Due to social distancing, each passenger takes up an entire rows’ worth of space.
When a passenger finds their row, it takes them 2 seconds to get in their seat. However, if they have a bag with them, they need an additional 8 seconds to stow it. Moreover, if a passenger’s seat is on the window (say, 4A) and someone’s already sitting in the aisle (say, 4B), it takes an additional 12 seconds for them to shuffle around.
All passengers in the line walk simultaneously. However, when a passenger finds their seat and wrangles their bags, everybody behind them has to stop and wait before they can keep walking towards their seat.
Write a program that first takes an integer \(n\) as input, which represents how many rows are in the airplane. Then, take a second integer \(m\) as input, which represents how many passengers are on the plane. Finally, take \(m\) additional inputs consisting of a row number, a letter A-D, and possibly an asterisk that indicates whether or not each passenger has a bag. For instance:
4 2
3D 4C*
This input represents a plane with 4 rows and 2 passengers. First, the passenger seated at 3D boards the plane. The passenger seated at 4C boards immediately after, and they carry a bag with them. It takes the first guy 6 seconds to walk to the third row, then 2 seconds to get in his seat. After these 8 seconds, the second passenger is still at row 2 waiting for the first one; he takes 4 seconds to walk to his row, 8 seconds to stow his bag, and 2 seconds to get in his seat. This boarding took 22 seconds.
Determine how many seconds it takes for everyone to board the plane.