10
\$\begingroup\$

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

10 Answers 10

2
\$\begingroup\$

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'
\$\endgroup\$
  • \$\begingroup\$ 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[]. \$\endgroup\$ – algorithmshark Mar 7 '14 at 3:29
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Ah, clever use of eval, I like it. \$\endgroup\$ – scleaver Oct 2 '12 at 18:38
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • 5
    \$\begingroup\$ "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. :-) \$\endgroup\$ – Mr.Wizard Oct 4 '12 at 14:24
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Why not get rid of your for loop and just call R once before your while loop? \$\endgroup\$ – Keith Randall Oct 2 '12 at 3:23
  • \$\begingroup\$ @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. \$\endgroup\$ – Matt Oct 2 '12 at 11:19
  • \$\begingroup\$ 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. \$\endgroup\$ – DavidC Oct 2 '12 at 14:25
  • \$\begingroup\$ @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 \$\endgroup\$ – Matt Oct 2 '12 at 15:34
  • \$\begingroup\$ @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. \$\endgroup\$ – Keith Randall Oct 2 '12 at 16:24
1
\$\begingroup\$

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()
\$\endgroup\$
  • \$\begingroup\$ you can probably delete the import math if you replace math.ceil(...) with int(...)+1 \$\endgroup\$ – Matt Oct 2 '12 at 15:47
  • \$\begingroup\$ I would, but it would produce 7 as a possible output. \$\endgroup\$ – scleaver Oct 2 '12 at 15:50
  • \$\begingroup\$ Oh, yeah. I missed that. \$\endgroup\$ – Matt Oct 2 '12 at 16:02
  • \$\begingroup\$ mellamokb clarified a question I had about the ascending randomizer. You aren't allowed to ask it for n. \$\endgroup\$ – Matt Oct 2 '12 at 17:13
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Apparently this is a low quality post ? \$\endgroup\$ – Muhammad Salman Jun 3 '18 at 9:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.