Dice from Changing Random Generator

Question

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

Answer 1

J - 13 char

This makes the same assumptions as Golfscript: that the number of dice is in stdin and we list the dice rolls that are to come out.

r=:1+?  NB. free random function
r>:i.".1!:1]1

Explained by explosion:

r=:1+?           NB. r(x) = 1 + a random number between 0 and n-1
           ]1    NB. input file handle
       1!:1      NB. read in a string
     ".          NB. convert to integer
 >:i.            NB. make a list of numbers, from 1 to that integer
r                NB. apply the random function

If that is somehow unsatisfactory, here is a longer, 21-char program, that can be called with f'' to generate random numbers, featuring a state and everything.

r=:1+?  NB. free random function
c=:0
f=:3 :'r c=:1+c'

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 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

Answer 6

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()

Answer 7

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}}

Answer 8

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

Answer 9

JavaScript (Node.js), 35 bytes

//random number generating function
g=1;f=()=>(1+g>1000?g++:5*Math.random())|0

i=0;while(i++<5)f();t=()=>f()%6+1|0

Try it online!

Answer 10

x86 opcode, 15 bytes

f:  mov cx, 6
    call r ; return in AX
    loop $-3
    cwd
    div word [f+1]
    inc dx
    ret ; return in DX

Answer 11

GolfScript, 8 bytes

f;3f*f(-

Try it online!

It pops the generator once, then gets rid of the result. Then it rolls f2, and multiplies it by 3 (3 or 6), then subtracts f3-1 (0, 1, 2) which results in (3-2, 3-1, 3-0) or (6-2, 6-1, 6-0) W5.

Golfscript and the random function existed before this question was posted, so is a legal submission.

This is the run-only-once submission. If you need to run it several times in one call,

GolfScript, 12 bytes

f;3f*f-)0:i;

Try it online!

This resets your i call to 0 so it resets accordingly. This TIO shows 50 random results.

Answer 12

C (gcc), 31 bytes

f(i){for(i=5;i--;)c;i=~-c%6+1;}

Every 6 calls, the probability of every number between 1 and 6 inclusive being generated is equal.

c is #defined as a call to a function that generates the perfect random numbers.

Try it online!