Monte Carlo – Repeated Dice Problem from 404 podcast

Last week a podcast I listen to, the 404, discussed a math problem where you roll six 20-sided die and count how often you get a situation where at least one dice matches another dice.  They discussed the math a little and came to the conclusion that it happens far more than you’d think.  I thought it’d make a good monte carlo programming exercise so I’ve done just that.  Below, you’ll find my C code (though it’s not great) and results for 2-20 dice.

It’s important to note that the code below isn’t particularly good. Ideally, you’d sort the dice first and then count. This would give you the ability to also check for multiple doubles or for triples and up. It’d also make it easier to expand for future problems. I did not do any of that. I wrote this so that it’d be fast to program, and left all that out to keep it simpler. But note that because I’m not sorting, I’m checking for doubles in a very inefficient method that gets worse the more dice you add. It’s fine for six dice but for more, it can start to take awhile. To do 100 million rolls, with six dice it takes 11s but with 20 dice, it takes 107s. So not idea, but fast to write. 🙂

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// Main function was given
int main()
{
	int i, j, k;
	int maxDiceValue = 20;
	int numIterations = 100000000;
	int numDice = 6;
	int roll;
	int rolls[numDice];
	int isMatch;
	int numMatches=0;

	// See RNG with time to get unique results each time
	srand(time(NULL));

	for(k=0; k<numIterations; k++)
	{
		// Fill array with random dice rolls
		for(i=0; i<numDice; i++)
		{
			rolls[i] = 1 + rand() % maxDiceValue;
		}

		// Find if there is any match present in the dice
		// This is the absolute lasiest way to do it and it is pretty
		//  bad code since it isn't easy to expand to other cases and
		//  it's pretty inefficent.  But easy to quick to code.
		// Iterate through all the dice and if there's a match, change
		//  isMatch variable to 1.  After iterating, check this variable
		isMatch = 0;
		for(i=0; i<numDice-1; i++)
		{
			for(j=i+1; j<numDice; j++) 			{ 				if(rolls[i] == rolls[j]) 					isMatch=1; 			} 		} 		if(isMatch > 0)
			numMatches++;
	}

	// Print results
        // Note that we multiply by 100.0 first to convert to double
	printf("%d matches in %d iterations: %2.2lf%% \n", numMatches, numIterations, 100.0*numMatches/numIterations);

	return 0;
}

The result for 6 dice is 56.4%. Below is a graph of the percentage for rolling 2 through 20 dice.

I know this is a dumb example but it was an interesting ten minute problem. Thoughts? Questions? Comments? Leave them below.