# 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:

- With one die with 4 sides, you get the distribution of sum d1 = [1, 1, 1, 1]
- 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

- Using the same reasoning, you can create the distribution array for 3 dice by using the distribution of 2 dice.
- 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

## Leave a Reply