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

• beary605: Is the program iterate(6):b=asc-rand(); print b illegal or does it not work? I might be misunderstanding the third rule.
• mellamokb: @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.
• DavidC: 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.
• mellamokb: @DavidCarraher: Very good point. I was meaning random integer, and I see that's not clear. I will update the question. Edit: Updated.
• Matt: Are we allowed to ask the randomizer how many times it has generated random numbers? I was under the impression that we could not.

Answer 1

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.

• scleaver: Ah, clever use of eval, I like it.

Answer 2

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 3

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'

• algorithmshark: K analogues: free random function r:{*1_draw x}, stdin version (10 char) r'1+!. 0:` , function version (14 char) c:0;f:{r@c+:1} called by f[].

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.

• Mr.Wizard: "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. :-)

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

• Keith Randall: Why not get rid of your for loop and just call R once before your while loop?
• Matt: @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.
• DavidC: 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.
• Matt: @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
• Keith Randall: @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.

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

• Matt: you can probably delete the import math if you replace math.ceil(...) with int(...)+1
• scleaver: I would, but it would produce 7 as a possible output.
• Matt: Oh, yeah. I missed that.
• Matt: mellamokb clarified a question I had about the ascending randomizer. You aren't allowed to ask it for n.

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

• Muhammad Salman: Apparently this is a low quality post ?

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!