Introducción

Se le proporciona un generador de enteros aleatorio con la siguiente implementación

• La primera invocación siempre devuelve 1.
• La segunda invocación devuelve un entero aleatorio entre 1 y 2.
• La tercera invocación devuelve un entero aleatorio entre 1 y 3.
• La enésima invocación devuelve un entero aleatorio entre 1 yn, inclusive.

Con base en la función anterior, escriba un generador de dados aleatorio que sea perfectamente aleatorio, devolviendo un valor entre 1 y 6 (inclusive) con igual probabilidad.

Reglas

• Su programa / función debe dar como resultado un número entero aleatorio entre 1 y 6, inclusive, en alguna forma utilizable, es decir, a la salida estándar o como un valor de retorno de la función.
• El generador de números aleatorios ascendentes anterior se puede definir como una función "libre" en su programa (es decir, no cuenta para su recuento de caracteres), o un script / programa separado que se ejecuta según sea necesario, suponiendo que el estado ( n) sea persistente entre llamadas.
• Suponga que nunca se solicitarán más de 1000 tiradas de dados en un solo caso de uso de su programa, y ​​el generador inicial de números aleatorios puede reiniciarse al 1final de 1000 tiradas de dados para evitar el desbordamiento n.
• Su programa no puede usar ninguna otra fuente de números aleatorios, excepto el generador aleatorio ascendente definido anteriormente. Por supuesto, puede solicitar múltiples números aleatorios del generador de números aleatorios para cada salida de tirada de dados.
• Este es el código de golf, por lo que el ganador es la respuesta más corta o la mayoría de los votos en caso de empate. Si puedes generar 1000 tiradas de dados usando menos de 1000 números aleatorios generados, obtén un bono de eficiencia de 10 puntos .

Ejemplo

./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

J - 13 char

Esto hace las mismas suposiciones que Golfscript: que la cantidad de dados está en stdin y enumeramos las tiradas de dados que saldrán.

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

Explicado por explosión:

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

Si eso es de alguna manera insatisfactorio, aquí hay un programa más largo de 21 caracteres, al que se puede llamar f''para generar números aleatorios, con un estado y todo.

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

Python, 31 caracteres

De manera similar a Scleaver, defina el generador de esta manera:

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

Luego, una función para devolver tiradas de dados:

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

Llame D()cada vez que necesite una tirada de dados uniforme al azar.

Scala 23

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

El método r se puede implementar (aprox.) De esta manera:

var cnt = 0 
val rnd = new util.Random 

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

una prueba aproximada:

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)

Cada sexta llamada debería producir una distribución igual sobre los 6 valores, por lo que descarto 5.

GolfScript (15 caracteres)

Esto supone que el número de rollos requeridos se proporciona en stdin y enumera tantos resultados para stdout.

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

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

Demostración en línea

Si bien podría obtener la bonificación de 10 puntos por usar menos de 1000 tiradas para generar 1000 números, me costaría mucho más de 10 caracteres. El enfoque trivial de extraer la entropía adecuada cuando N es un múltiplo de una potencia de 2 o 3 se queda muy corto porque el número de resultados disponibles mod 3 es solo 333 + 111 + 37 + 12 + 4 + 1 = 498. Por lo tanto, es necesario adopte un enfoque de muestra y rechazo. Usando este enfoque, puede obtener 2242 rollos esperados de 1000 llamadas a r, pero hay una sobrecarga adicional de la contabilidad y basees un nombre de función muy largo.

Python 65 63

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

La función R()es el aleatorizador ascendente.

Uso:

$ ./rollDice.py
3
$ ./rollDice.py
5

Python, 56

r se define como:

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

el generador de dados d:

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

uso, por ejemplo, para 100 rollos:

for i in range(100):print d()

Mathematica 51

El generador de números aleatorios r, se restablece estableciendo la variable global, na 1.

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

Código

No en la carrera por el código más corto ...

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

Uso

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

60000 lanzamientos de dados requieren 60031 llamadas a h. Tallymuestra el desglose por los números 1-6.

60031

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

Perl, 22 o 45

Implementación del generador de números aleatorios ascendentes:

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

Generando:

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

Prueba:

n número 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 tiradas de dados tomaron 60000042 llamadas a r y 570.432735 segundos

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

Pruébalo en línea!

código de operación x86, 15 bytes

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

GolfScript , 8 bytes

f;3f*f(-

Pruébalo en línea!

Hace estallar el generador una vez, luego se deshace del resultado. Luego tira f2, y lo multiplica por 3 (3 o 6), luego resta f3-1 (0, 1, 2) que resulta en (3-2, 3-1, 3-0) o (6-2, 6-1, 6-0) W5.

Golfscript y la función aleatoria existían antes de que se publicara esta pregunta, por lo que es una presentación legal.

Este es el envío de solo una vez. Si necesita ejecutarlo varias veces en una sola llamada,

GolfScript , 12 bytes

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

Pruébalo en línea!

Esto restablece su llamada a 0, por lo que se restablece en consecuencia. Este TIO muestra 50 resultados aleatorios.

C (gcc) , 31 bytes

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

Cada 6 llamadas, la probabilidad de que se genere cada número entre 1 y 6 inclusive es igual.

ces #defined como una llamada a una función que genera los números aleatorios perfectos.

Pruébalo en línea!