CSCI 103 Spring 2018: Introduction to Programming
Spare a Square
In this programming assignment you will solve the very important toilet paper problem, first posed by Donald E. Knuth (famous mathematician and computer scientist) in 1984. Restrooms are equipped with two rolls of toilet paper so that when one is empty there will be a back-up. The one closest to the patron will be called roll1 and the other roll2. Initially each roll starts with N squares and patrons invariably fall into two groups: big-roll choosers (always pick squares from the bigger roll) with probability, p, and little-roll choosers (always pick squares from the smaller roll) with probability, 1-p. [Assume if the rolls are of the same size, patrons pick the closest (i.e. roll1).] Assume each patron uses (unrealistically) only 1 square each.
The goal of this program is to compute the average size of the non-empty roll (i.e. how many squares are left on the non-empty roll) at the moment the other roll becomes empty. This is important to know since we desire that there is plenty left on the other roll. We could try to solve this problem analytically as a function of p and N (the starting size of both rolls) but it becomes complex quickly. Thus, we can use a program to compute the solution.
This programming assignment should be performed INDIVIDUALLY. You may re-use portions of code from previous examples and labs provided in this class, but any other copying of sections of code is prohibited. We will use software tools that check all students’ code and known Internet sources to find hidden similarities.
What you will learn
After completing this programming assignment you will:
- Write a non-trivial C++ program from scratch by combining knowledge from previous examples and modifying them appropriately
- Select appropriate data types: int, double, etc.
- Select appropriate control structures including for loops, while loops, conditionals / selection mechanisms (i.e. if statements) to solve a problem
- Use the random number generation capabilities of the standard C library.
Background Information and Notes
To solve the problem, we will run “simulations” of the situation. We will generate a random number to represent a patron and then, based on p, we will determine if that patron should be treated as a big- or little-chooser, deducting 1 square from the appropriate roll. We will repeat this process many times until a roll becomes empty. At that point we will record how many squares are left on the non-empty roll. However this answers the questions only for a single possible sequence…If p=0.5 (50-50 big to little chooser ratio) it may be that the random numbers generated for that one simulation were all big-choosers and thus we get a result that doesn’t match the average solution. To find the average solution, we will repeat a large number of simulations to arrive at an average number of squares remaining on the non-empty roll. (This process of simulating something a large number of times to find the average answer is known as Monte Carlo simulation due to its resemblance to how casinos bank on the fact that games of chance will yield on average what a probabilistic mathematical formula predicts). This can be easily accomplished by writing a kernel of code for a single simulation starting with the rolls each with N squares and playing out the sequence describe above and then repeating that simulation kernel a large number of times (say 100,000 though your program should allow the user to enter the number of desired simulations).
One of the primary reasons that it may be easier to simulate this problem rather than attempting to find an analytic solution (besides the fact that you probably have not had a probability class) is that to simulate a whether a person is a big- or little-chooser we can just use the random number generation capabilities of the standard C library (or any another programming environment) through the rand() function. Most random number generators will produce a number that is uniformly distributed over a certain range. A uniform distribution means that theoretically every number over the range has equal probability of being produced.
rand() returns an integer number in the range
RAND_MAX (which is a constant defined in
cstdlib which is where
rand() is declared/prototyped as well). You will need to think about how to convert the random number to represent a big- or little-chooser based on the appropriate probability, p. (Note: p is not the random number...it is the fraction of random numbers that should be considered big-choosers.)
Important note: p can be any legal double value between 0 and 1. You cannot assume it will be only accurate to a tenth (e.g. 0.4), a hundredth (e.g. 0.41) or even a thousandth (e.g. 0.412). It can be any legal double and you should write code that determines whether someone is a big- or little-chooser to the best accuracy possible.
Your program shall meet the following requirements for features and approach:
- Write code to accept 3 values from the user:
- An integer N (number of initial squares on each roll)
- A double p (probability of a big-chooser)
- An integer sims (number of simulations to run and average over)
- Use a function that generates and returns a random number between [0,1] which can be used to determine whether a patron is a big-chooser or little-chooser.
Inside this function use the
rand()function and the
RAND_MAXconstant to generate random numbers and scale them appropriately to produce a random value between [0-1].
- Use a function that performs a single simulation of two-rolls being used until one becomes empty. It should take the initial value, N, and the probability of big-choosers, p, as input arguments, perform the simulation and then return the number of squares left on the non-empty roll once the other roll is empty.
int single_sim(int N, double p);
- Remember, if both rolls have the same number of squares remaining, then roll1 will be selected regardless of big- or little-chooser.
- Write code to call single_sim() sims (recall sims was entered by the user) times and calculate the average of the remaining squares.
- Display the result of your program using the exact syntax:
For example with N=3, p=0.5, sims=100,000 your program should output:
The number maybe slightly different (hundredths/thousandths off but be sure to use this format).
Before you begin
BEFORE beginning to code, consider the following questions. Use your expectation to test your program when you believe you have written the code correctly. Does it produce the values that you expect?
- Given N starting squares what is the expected # of squares remaining if p=0 (i.e. everyone is a little-chooser?)
- Given N starting squares what is the expected # of squares remaining if p=1 (i.e. everyone is a big-chooser?)
Perform the following.
- Create a
tpdirectory on your VM
$ mkdir tp $ cd tp
- Download the skeleton (incomplete) file
.cppby executing the command
$ wget http://bits.usc.edu/files/cs103/tp/tp.cpp
We have provided a bit of structure for you but you will need to complete everything else.
- Write your code adhering to the given requirements.
- Comment your code as you write your program documenting what abstract operation a certain for, while, or if statement is performing as well as other decisions you make along the way that feel particular to your approach.
- Compile and run your program:
$ compile tp.cpp
- Run your program:
And input appropriate values of N, p, and the number of simulations.
- Compare your results to those you determined from your prelab. Further, we have also included a few results in the table below (all for
sims=100,000). If there are any run-time errors debug your program using
gdbor by adding
Init. # of Squares (N) Prob. of Big Chooser (p) Result
(should be accurate to about 0.02 error)
10 0.5 3.524 10 0.732 1.567 25 0.5 5.612 25 0.2 19.087
- Next, experiment with number of simulations holding the other parameters constant at N=10 and p=0.5. Manually run your program several times varying the number of simulations for sims=
1,000,000. Create a neatly formatted table in your readme.txt showing the number of simulations and the resulting average. This experiment is important so that we can understand how the results change based on number of trials. Why run more simulations and wait longer if an accurate result can be found with fewer simulations? Use your table to suggest the point of “diminishing returns” (indicate a number of simulations to perform) where performing more games simulations does not improve the accuracy significantly.
If you have learned anything from this assignment it should be that to ensure the most amount of toilet paper remains when the first roll becomes empty we should all be ???-choosers (fill in the blank).
Create and submit your
tp.cpp file and a
readme.txt (just create one yourself) that includes your table of accuracy vs. number of simulations as well as your suggested point of diminishing returns (i.e. suggested number of simulations).