# Dice from Changing Random Generator

## Introduction

You are given a random integer generator with the following implementation

• The first invocation always returns 1.
• The second invocation returns a random integer between 1 and 2.
• The third invocation returns a random integer between 1 and 3.
• The nth invocation returns a random integer between 1 and n, inclusive.

Based on the above function, write a random dice generator that is perfectly random, returning a value between 1 and 6 (inclusive) with equal probability.

## Rules

• Your program/function should result in a random integer between 1 and 6, inclusive, in some usable form, i.e., to standard output or as a function return value.
• The ascending random number generator above can be defined as a "free" function in your program (i.e., doesn't count toward your character count), or a separate script/program that is executed as needed, assuming the state (`n`) is persistent between calls.
• Assume that no more than 1000 dice rolls will ever be requested in a single use case of your program, and the initial random number generator can be reset to `1` at the end of 1000 dice rolls to avoid overflow of `n`.
• Your program may not use any other source of random numbers except the ascending random generator defined above. You may of course request multiple random numbers from the random number generator for each single dice roll output.
• This is code-golf, so winner is shortest answer or most votes in the event of a tie. If you can generate 1000 dice rolls using less than 1000 generated random numbers, give yourself a 10-point efficiency bonus.

## Example

``````./asc-rand
1 # random integer between 1 and 1
./asc-rand
1 # random integer between 1 and 2
./asc-rand
3 # random integer between 1 and 3
./asc-rand
4 # random integer between 1 and 4

# dice-gen generates random dice based on output of asc-rand program.
./dice-gen
3
./dice-gen
6
./dice-gen
5
./dice-gen
1
``````
-
Is the program `iterate(6):b=asc-rand(); print b` illegal or does it not work? I might be misunderstanding the third rule. – beary605 Oct 1 '12 at 23:52
@beary605: The random number generator can only be reset after the entire 1000 dice rolls, not between every dice roll. The only reason I mention that is so dealing with possible overflows on the value returned by the random number generator is not one of the concerns in this challenge. Edit: I clarified the purpose of the rule, hope it helps. – mellamokb Oct 2 '12 at 14:07
When you say "random number" do you mean "random integer" or "random (truncated) real number"? Perhaps there is some convention that I am not aware of. – David Carraher Oct 2 '12 at 14:18
@DavidCarraher: Very good point. I was meaning random integer, and I see that's not clear. I will update the question. Edit: Updated. – mellamokb Oct 2 '12 at 14:24
Are we allowed to ask the randomizer how many times it has generated random numbers? I was under the impression that we could not. – Matt Oct 2 '12 at 16:00
show 1 more comment

## Python, 31 chars

Similarly to scleaver, define the generator like this:

``````from random import randint
n=0
def r():
global n;n+=1
return randint(1,n)
``````

Then a function to return dice rolls:

``````D=lambda:eval('r(),'*6)[-1]%6+1
``````

Call `D()` any time you need a uniformly random dice roll.

-
 Ah, clever use of eval, I like it. – scleaver Oct 2 '12 at 18:38

## GolfScript (15 chars)

This assumes that the number of rolls required is supplied on stdin and lists that many results to stdout.

``````# The free increasing random function
0:N;{N):N rand)}:r;

~{r{;r}5*6%)n}*
``````

Online demo

While I could get the 10 point bonus for using fewer than 1000 rolls to generate 1000 numbers, it would cost me far more than 10 characters. The trivial approach of extracting suitable entropy when N is a multiple of a power of 2 or 3 falls well short because the number of results available mod 3 is only 333 + 111 + 37 + 12 + 4 + 1 = 498. Therefore it's necessary to take a sample-and-reject approach. Using this approach you can get an expected 2242 rolls from 1000 calls to `r`, but there's extra overhead from the book-keeping and `base` is a very long function name.

-
"and `base` is a very long function name" You apparently don't use Mathematica. We get such wonders as `NegativeBinomialDistribution`, `ExponentialGeneratingFunction`, `MathieuCharacteristicExponent`, `InverseFourierSequenceTransform`, and `SemialgebraicComponentInstances`. :-) – Mr.Wizard Oct 4 '12 at 14:24

## Scala 23

``````def s={r;r;r;r;r;r%6+1}
``````

The method r can be (approx.) implemented like this:

``````var cnt = 0
val rnd = new util.Random

def r = {
cnt %= 1000
cnt += 1
rnd.nextInt (cnt)
}
``````

a rough test:

``````scala> (1 to 6).map (i => ((1 to 600) map (_=>s)).filter (_ == i).size)
res26: scala.collection.immutable.IndexedSeq[Int] = Vector(110, 105, 91, 96, 106, 102)
``````

Every 6th call should produce an equal distribution over the 6 values, so I throw away 5.

-

# Python 65 63

``````i=7
while i>5:[R()for x in range(9)];i=int(`R()`[-1])
print i+1
``````

The function `R()` is the ascending randomizer.

### Usage:

``````\$ ./rollDice.py
3
\$ ./rollDice.py
5
``````
-
 Why not get rid of your `for` loop and just call `R` once before your `while` loop? – Keith Randall Oct 2 '12 at 3:23 @KeithRandall The number I return as my dice roll is the last digit of the number that the ascending generator returns. I need to make 10 calls to the ascending generator to ensure equal probabilities for all possible digits. – Matt Oct 2 '12 at 11:19 Why 10 calls? In principle, if the generator random, shouldn't each call offer equal probability for any of the (ten) digits? Of course, in practice, you can only expect to approach equal counts for each of the numbers. – David Carraher Oct 2 '12 at 14:25 @DavidCarraher The generator returns random numbers from 1 to n where n is the number of times you have called it. I'm looking at the last digit of this returned number. If n is not an integer multiple of 10 the probability will not be uniform. For example: If n=13 the probabilities will break down as follows: 1/9 for rolls 1,5,6 and 2/9 for rolls 2,3,4 – Matt Oct 2 '12 at 15:34 @Matt: I assumed `R()` was returning a float and you were grabbing the least-significant digit. Now that it has been clarified that `R()` returns an integer, it makes sense. – Keith Randall Oct 2 '12 at 16:24

# Python, 56

r is defined as:

``````from random import randint
n=0
def r(z):
global n;n+=1
return randint(1,n)
``````

the dice generator d:

``````import math;d=lambda:math.ceil(6.*r(r(r(r(r(r(0))))))/n)
``````

usage, eg, for 100 rolls:

``````for i in range(100):print d()
``````
-
 you can probably delete the `import math` if you replace `math.ceil(...)` with `int(...)+1` – Matt Oct 2 '12 at 15:47 I would, but it would produce 7 as a possible output. – scleaver Oct 2 '12 at 15:50 Oh, yeah. I missed that. – Matt Oct 2 '12 at 16:02 mellamokb clarified a question I had about the ascending randomizer. You aren't allowed to ask it for n. – Matt Oct 2 '12 at 17:13

# Mathematica 51

The random number generator, `r`, is reset by setting the global variable, `n` to 1.

``````n = 1; r[c_] := RandomInteger[{1, c}]
``````

Code

Not in the running for the shortest code...

``````h := (n++; If[n < 4 \[Or] (y = r@n) > 6 Quotient[n, 6], h, y~Mod~6 + 1])
``````

Usage

``````t = Table[h, {60000}];
n
SortBy[Tally[t], First]
``````

60000 rolls of the dice required 60031 calls to `h`. `Tally` shows the breakdown by numbers 1-6.

60031

{{1, 9923}, {2, 9966}, {3, 10016}, {4, 10028}, {5, 10009}, {6, 10058}}

-

## Perl, 22 or 45

Implementation of the ascending random number generator:

``````my \$n=0;
sub r { \$n++; return 1+int(rand\$n); }
``````

Generating:

``````#copy of the Scala solution; short code; uses 6N rolls
sub s{r;r;r;r;r;1+r%6}
#more efficient implementation, uses approximately 6+N+lnN rolls
sub roll { do{\$a=r-1}while(\$a>\$n-\$n%6);return 1+(1+\$a)%6 }
``````

Testing out:

```n number   chisquare
1 10001867 0.348569
2 10004853 2.355161
3 9994395  3.141602
4 10000177 0.003133
5 9999227  0.059753
6 9999481  0.026936
T 60000000 5.935154
60000000 dice rolls took 60000042 calls to r and 570.432735 seconds
```
-