Skip to content
April 14, 2011 / oop123

Project Euler #205 – Java

You can see the problem here: Problem #205.

Given the question is 205 but is ranked so low in difficulty (a lot people solved it), I though it would be simple so I pick it. I was right. I first wanted to brute force it, but I realized there will be a lot of copy and pasting and I didn’t want to do that. I thought for a while and I just used some simple dynamic programming to do it (which is just as easy and a good programming exercise).

The whole idea goes like this:

  1. With one die with 4 sides, you get the distribution of sum d1 = [1, 1, 1, 1]
  2. With two die with 4 sides, you create a new empty distribution d2: [0, 0, 0, 0, 0, 0, 0, 0]
    • If you roll a 1, you would get a distribution of [0, 1, 1, 1, 1, 0, 0, 0] by moving d1 one step to the right
    • If you roll a 2, you would get a distribution of [0, 0, 1, 1, 1, 1, 0, 0] by moving d1 two steps to the right
    • If you roll a 3, you would get a distribution of [0, 0, 0, 1, 1, 1, 1, 0] by moving d1 three steps to the right
    • If you roll a 4, you would get a distribution of [0, 0, 0, 0, 1, 1, 1, 1] by moving d1 four steps to the right
    • If you add each of the partial distribution together, you get d2 = [0, 1, 2, 3, 4, 3, 2, 1] which is the distribution of dice sum for step 2
  3. Using the same reasoning, you can create the distribution array for 3 dice by using the distribution of 2 dice.
  4. So on and so on…

The function (note: I made it so the dice distributions starts at 1, so an index of 6 would correspond to a sum of 6):

private static double[] diceDistribution(int diceSize, int numOfDice) {
	//initialize one die's distribution first
	int[] last = new int[diceSize + 1], current = new int[0];
	Arrays.fill(last, 1);
	last[0] = 0;

	for (int i = 2; i <= numOfDice; i++) {
		current = new int[diceSize * i + 1];

		//using the last dize distribution to calculate the new distribution
		for (int j = 0; j < diceSize; ++j) {
			for (int m = i - 1, n = i + j, len = last.length; m < len; n++, m++) {
				current[n] += last[m];
			}
		}

		last = current;
	}

	//change the distribution of the possible sums of the dice into probabilities
	double[] probabilities = new double[current.length];
	double totalPossibility = Math.pow(diceSize, numOfDice);
	for (int i = numOfDice, len = current.length; i < len; i++) {
		probabilities[i] = current[i] / totalPossibility;
	}

	return probabilities;
}

The main program is then trivial.

double[] Colin = diceDistribution(6, 6), Peter = diceDistribution(4, 9);
double partialProb = 0, totalProb = 0;
for (int i = 9, len = Peter.length; i < len; i++) {
	//partialProb: keeps track of the running total probability for Colin's dice losing to Peter's dice
	partialProb += Colin[i - 1];
	totalProb += partialProb * Peter[i];
}
System.out.println(totalProb);

Runs in less than 1 millisecond on my computer.

Yes! I didn’t use brute force like most of the people in the forum! From the forum, it turned out my method is essentially a modified algorithm of Pascal’s Triangle algorithm. Oh well, at least I did it myself.

Each question from now on is going to take me at least 5 days to do, why are they so hard? CU

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: