For this project you are given a program that simulates rolling dice using C’s built-in pseudo-random number generator. The functions that work with dice are in their own module. You will add some functions to this module and write a new program that uses your new functions along with the existing functionality of the module.
Before you write any code, try running the existing program. Running make compiles dice.c and roll_dice.c to create the program roll_dice.
If you run this program without any additional command line arguments, you can see a usage message:
./roll_dice
Usage: ./roll_dice <sides per die> <dice count>When given a number of sides and a number of dice, the program simulates rolling dice with that many sides. For example, to simulate rolling 2 6-sided dice you would run the program like this:
./roll_dice 6 2
Rolled 2 6-sided dice:
3 5The module in dice.h and dice.c contains 3 functions that are used by the program. The functions use the type size_t to represent quantities (number of dice, number of sides) and unsigned int to represent the values shown on the dice.
At the heart of the program is the roll_die() function which rolls a single die:
unsigned int roll_die(size_t sides) {
return rand() % sides + 1;
}The rand() function returns a pseudo-random non-negative integer. By taking rand() % 6 we get a number between 0 and sides - 1, and adding 1 to that gives us a number between 1 and sides.
To roll several dice we use the roll_dice() function:
void roll_dice(unsigned int *dice, size_t sides, size_t count) {
for (size_t i = 0; i < count; i++) {
dice[i] = roll_die(sides);
}
}This function calls roll_die() as many times as there are dice, and stores the results in the array dice.
The print_dice() function prints the contents of an array of dice values separated by spaces.
Having these functions makes main() nice and simple. Read over the code in roll_dice.c so that you understand what is going on in the existing program.
You will add code to this project to implement a Monte Carlo simulation. In a Monte Carlo simulation, a process involving random values is run many times to estimate a solution. Here you will simulate rolling dice many times to find the probability that all of the dice end up having the same value in a single roll.
A probability is a number between 0 and 1 that indicates how likely it is that something will happen. For example, when you flip a coin there is an equal probability that it will be heads or tails (assuming you have a fair coin). The probability that you will flip heads is 0.5, and the probability that you will flip tails is also 0.5. To verify this with a Monte Carlo simulation, you could flip a coin many times and record the number of heads and tails flips. The number of times you flipped heads divided by the total number of flips gives you the estimated probability of flipping heads. If you do this enough times, you should get a value very close to 0.5.
It is also fairly straightforward to calculate the actual probability that a number of dice will end up having the same values when rolled. Because we can calculate the actual probability, we can compare the actual probability that a set of dice will all have the same value to the estimated value produced by our Monte Carlo simulation to see if C’s pseudo-random number generator is good enough to be used in Monte Carlo simulations in general.
Let’s calculate the probability of rolling 2 4-sided dice with the same value. To do this we can think about each roll independently. If you roll one die first by itself and see what its value is, then the second die needs to have the same value as the first die. Since there are 4 possible values for the second die, the probability that the second roll will be the same as the first is \(1/4\) or 0.25.
With 3 dice the probability gets lower. For each additional die, you need to multiply the probability by the probability that one die will have a particular value. So for 3 4-sided dice the probability of rolling all of the same values is 0.25 * 0.25 = 0.0625, which is a 1 in 16 chance.
You will write a new program in monte_carlo.c to run the simulation. This program must take one more command line argument than roll_dice.c, which is the number of times to roll the dice. Then you will simulate rolling dice that many times, count how many times the values are all the same, and divide by the number of rolls to estimate the probability.
This program will also use the code from the dice module. To keep the main() function of this program simple, you will write 2 new functions in dice.c to be used in this simulation. The prototypes for these functions are already written for you in dice.h.
The first function must check to see if an array of dice values all have the same value. Here is the prototype and documentation:
/**
* Determines if an array of dice all have the same value.
*
* Parameters:
* dice - an array of values representing rolled dice
* count - the number of dice
*
* Return:
* true if all of the dice have the same value, false otherwise
*/
bool are_all_same(unsigned int *dice, size_t count);The second function is as follows:
/**
* Uses a Monte Carlo method to extimate the probability of rolling dice that
* all have the same value.
*
* Parameters:
* sides - the number of sides of each die
* roll_count - the number of times to roll the dice
*
* Return:
* The estimated probability that all dice will have the same value, as a
* number between 0 and 1
*/
double all_same_probability(size_t sides, size_t dice_count, size_t roll_count);The all_same_probability() function should use the functions roll_dice() and are_all_same() and a loop to repeatedly roll dice roll_count times and count the number of times that the values are all the same. It will then return the number of times the values were all the same divided by the total number of rolls. Note that this function does not take an array as a parameter, you will need to declare an array of dice values in this function to pass to roll_dice().
In monte_carlo.c, write a main() function that gets the needed values from the command line arguments and reports the result of running the all_same_probability() function with the provided values. As in roll_dice.c, you will need to seed the random number generator. Here is what an example run should look like:
./monte_carlo 4 2 50
The probability of rolling all of the same values with 2 4-sided dice is
approximately 0.280000The above simulates rolling 2 4-sided dice 50 times. The actual probability of rolling the same values for 2 4-sided dice is 0.25, not 0.28, but the value is somewhat close. To get a better approximation you need to run the simulation more times:
./monte_carlo 4 2 1000
The probability of rolling all of the same values with 2 4-sided dice is
approximately 0.243000If you perform more rolls, your results should start to get closer to the actual value more consistently. Once you have written the program, experiment with the number of rolls to see how many you need to roll to consistently get a good approximation. You can try this with dice of different numbers of sides, and different numbers of dice too.
The provided Makefile has a rule to build the monte_carlo program, but it is not built by default when running make because it is not the first rule in the file. To build monte_carlo, you need to explicitly run make monte_carlo. If you want the Makefile to be able to build monte_carlo when simply running make, you can move the rule for building monte_carlo above the rule for building roll_dice if you wish.
The program in roll_dice.c checks to see that the number of command line arguments is correct, but it does not ensure that the values in the arguments are correct. The program uses atoi() to convert the strings to integers, but atoi() does not do any validation for you. For example, atoi("abc") returns 0 and atoi("10abc") returns 10.
Your program must provide better input validation so that the program notifies the user if the numbers provided are not positive integers. The simplest way to do this is to loop over all the characters in each argument string and make sure each character is a digit. The isdigit() function from ctype.h can do this for you. It works like the isalpha() function that we used previously. You will also need to make sure the string is not all zeros (since zero is not a positive integer).
To keep main() clean, write a separate function in monte_carlo.c that validates the parameters and exits the program with a non-zero exit code if they are not valid. You can exit the program from a function other than main() using the exit() function from stdlib.h. The exit() function takes an exit code as its single parameter, so calling exit(0) exits the program with an exit code of 0, and exit(1) exits with an exit code of 1. Your program should print an error and exit with an exit code of 1 if the user has not provided the correct number of command line arguments, and print an error and exit with an exit code of 2 if any of the command line arguments are not positive integers.
Your validation function should take argc and argv as arguments, so its parameters should be of type int and char ** respectively. It can be a void function because it will have no return values if the arguments are valid, and will exit the program if they are invalid.
So the beginning of your main() function should end up looking like this:
int main(int argc, char **argv) {
validate_arguments(argc, argv);
// now you can safely convert the arguments to integers knowing that the
// number of arguments is correct
...Push your modifications (monte_carlo.c and dice.c) to git-keeper. The tests will test the two functions that you write, test that the monte_carlo executable can be built without errors, and test that the appropriate exit codes are used when the program is given invalid arguments. The actual output of the monte_carlo program will not be automatically tested, but will be graded manually. You will also be graded on style.