CODEWITHSUNDEEP
javarandomrangedice
yohm
yohm

Reputation: 462

From 5 dice rolls, generate a random number in the range [1 - 100]

I was going through some coding exercises, and had some trouble with this question:

From 5 dice (6-sided) rolls, generate a random number in the range [1 - 100].

I implemented the following method, but the returned number is not random (called the function 1,000,000 times and several numbers never show up in 1 - 100).

public static int generator() {

     Random rand = new Random();
     int dices = 0;

     for(int i = 0; i < 5; i++) {
         dices += rand.nextInt(6) + 1;
     }

     int originalStart = 5;
     int originalEnd = 30;
     int newStart = 1;
     int newEnd = 100;

     double scale = (double) (newEnd - newStart) / (originalEnd - originalStart);
     return (int) (newStart + ((dices - originalStart) * scale));
}

Upvotes: 5

Views: 3632

Answers (3)

JSLigon
JSLigon

Reputation: 49

Rolling a 6 sided die 5 times results in 6^5 = 7776 possible sequences, all equally probable. Ideally you'd want to partition those sequences into 100 groups of equal size and you'd have your [1 - 100] rng, but since 7776 isn't evenly divisible by 100 this isn't possible. The best you can do to minimize the bias is 76 groups mapped to by 78 sequences each and 24 groups mapped to by 77 sequences each. Encode the (ordered) dice rolls as a base 6 number n, and return 1 + (n % 100).

Not only is there no way to remove the bias with 5 dice rolls, there is no number of dice rolls that will remove the bias entirely. There is no value of k for which 6^k is evenly divisible by 100 (consider the prime factorizations). That doesn't mean there's no way to remove the bias, it just means you can't remove the bias using a procedure that is guaranteed to terminate after any specific number of dice rolls. But you could for example do 3 dice rolls producing 6^3 = 216 sequences encoded as the base 6 number n, and return 1 + (n % 100) if n < 200. The catch is that if n >= 200 you have to repeat the procedure, and keep repeating until you get n < 200. That way there's no bias but there's also no limit to how long you might be stuck in the loop. But since the probability of having to repeat is only 16/216 each time, from a practical standpoint it's not really much of a problem.

Upvotes: 2

Slavic
Slavic

Reputation: 1962

The problem is there aren't enough random values in 5-30 to map one to one to 1-100 interval. This means certain values are destined to never show up; the amount of these "lost" values depends on the size ratio of the two intervals.

You can leverage the power of your dice in a way more efficient way, however. Here's how I'd do it:

Approach 1

  1. Use the result of the first dice to choose one subinterval from the 6 equal subintervals with size 16.5 (99/6).
  2. Use the result of the second dice to choose one subinterval from the 6 equal sub-subintervals of the subinterval you chose in step one.
  3. Use... I guess you know what follows next.

Approach 2

Construct your random number using digits in a base-6 system. I.E. The first dice will be the first digit of the base-6 number, the second dice - the second digit, etc.
Then convert to base-10, and divide by (46656/99). You should have your random number. You could in fact only use 3 dice, of course, the rest two are just redundant.

Upvotes: 1

Guy Flavell
Guy Flavell

Reputation: 151

Ok, so 5 dice rolls, each with 6 options. if they are un-ordered you have a range of 5-30 as mentioned above - never sufficient for 1-100.

You need to assume an order, this gives you a scale of 1,1,1,1,1 - 6,6,6,6,6 (base 6) assuming 1 --> 0 value, you have a 5 digit base 6 number generated. As we all know 6^5 = 7776 unique possibilities. ;)

For this I am going to give you a biased random solution.

int total = 0;
int[] diceRolls;
for (int roll : diceRolls) {
    total = total*6 + roll - 1;
}

return total % 100 + 1;

thanks to JosEdu for clarifying bracket requirement

Also if you wanted to un-bias this, you could divide range by the maxval given in my description above, and subsequently multiply by your total (then add offset), but you would still need to determine what rounding rules you used.

Upvotes: 6

Related Questions