Dés de changer de générateur aléatoire

10

introduction

Vous obtenez un générateur d'entiers aléatoires avec l'implémentation suivante

  • La première invocation renvoie toujours 1.
  • La deuxième invocation renvoie un entier aléatoire compris entre 1 et 2.
  • La troisième invocation renvoie un entier aléatoire compris entre 1 et 3.
  • La nième invocation renvoie un entier aléatoire compris entre 1 et n, inclus.

Sur la base de la fonction ci-dessus, écrivez un générateur de dés aléatoire parfaitement aléatoire, renvoyant une valeur comprise entre 1 et 6 (inclus) avec une probabilité égale.

Règles

  • Votre programme / fonction doit résulter en un entier aléatoire compris entre 1 et 6, inclus, sous une forme utilisable, c'est-à-dire vers une sortie standard ou comme valeur de retour de fonction.
  • Le générateur de nombres aléatoires ascendants ci-dessus peut être défini comme une fonction "libre" dans votre programme (c'est-à-dire qu'il ne compte pas dans le nombre de caractères), ou un script / programme distinct qui est exécuté selon les besoins, en supposant que l'état ( n) est persistant entre les appels.
  • Supposons que pas plus de 1000 lancers de dés ne seront jamais demandés dans un seul cas d'utilisation de votre programme, et le générateur de nombres aléatoires initial peut être réinitialisé 1à la fin de 1000 lancers de dés pour éviter un débordement de n.
  • Votre programme ne peut utiliser aucune autre source de nombres aléatoires à l'exception du générateur aléatoire ascendant défini ci-dessus. Vous pouvez bien sûr demander plusieurs nombres aléatoires au générateur de nombres aléatoires pour chaque sortie de jet de dés.
  • Il s'agit de code-golf, donc le gagnant est la réponse la plus courte ou la plupart des votes en cas d'égalité. Si vous pouvez générer 1000 lancers de dés en utilisant moins de 1000 nombres aléatoires générés, offrez-vous un bonus d'efficacité de 10 points .

Exemple

./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
mellamokb
la source
Le programme est-il iterate(6):b=asc-rand(); print billégal ou ne fonctionne-t-il pas? Je peux mal comprendre la troisième règle.
beary605
@ beary605: Le générateur de nombres aléatoires ne peut être réinitialisé qu'après les 1000 lancers de dés, pas entre chaque lancer de dés. La seule raison pour laquelle je mentionne qu'il s'agit de débordements possibles sur la valeur retournée par le générateur de nombres aléatoires n'est pas l' une des préoccupations de ce défi. Edit: J'ai clarifié le but de la règle, j'espère que cela aide.
mellamokb
Lorsque vous dites "nombre aléatoire", voulez-vous dire "entier aléatoire" ou "nombre réel aléatoire (tronqué)"? Il y a peut-être une convention que je ne connais pas.
DavidC
@DavidCarraher: Très bon point. Je voulais dire un entier aléatoire, et je vois que ce n'est pas clair. Je mettrai à jour la question. Edit: mis à jour.
mellamokb
1
Sommes-nous autorisés à demander au randomiseur combien de fois il a généré des nombres aléatoires? J'avais l'impression que nous ne pouvions pas.
Matt

Réponses:

2

J - 13 caractères

Cela fait les mêmes hypothèses que Golfscript: que le nombre de dés est en stdin et nous listons les lancers de dés qui doivent sortir.

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

Expliqué par l'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

Si cela n'est pas satisfaisant, voici un programme plus long de 21 caractères, qui peut être appelé f''pour générer des nombres aléatoires, avec un état et tout.

r=:1+?  NB. free random function
c=:0
f=:3 :'r c=:1+c'
algorithmshark
la source
K analogues: fonction aléatoire libre r:{*1_draw x}, version stdin (10 caractères) r'1+!. 0:` , version fonction (14 caractères) c:0;f:{r@c+:1}appelée par f[].
algorithmshark
6

Python, 31 caractères

De la même manière que pour scleaver, définissez le générateur comme ceci:

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

Puis une fonction pour retourner les lancers de dés:

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

Appelez D()chaque fois que vous avez besoin d'un lancer de dés uniformément aléatoire.

Keith Randall
la source
Ah, utilisation intelligente d'eval, j'aime ça.
scleaver
3

Scala 23

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

La méthode r peut être (approximativement) implémentée comme ceci:

var cnt = 0 
val rnd = new util.Random 

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

un test approximatif:

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)

Chaque 6ème appel devrait produire une distribution égale sur les 6 valeurs, donc je jette 5.

Utilisateur inconnu
la source
2

GolfScript (15 caractères)

Cela suppose que le nombre de rouleaux requis est fourni sur stdin et répertorie ce nombre de résultats à stdout.

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

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

Démo en ligne

Bien que je puisse obtenir le bonus de 10 points pour l'utilisation de moins de 1000 rouleaux pour générer 1000 numéros, cela me coûterait bien plus de 10 caractères. L'approche triviale d'extraire l'entropie appropriée lorsque N est un multiple d'une puissance de 2 ou 3 est bien en deçà car le nombre de résultats disponibles mod 3 n'est que de 333 + 111 + 37 + 12 + 4 + 1 = 498. Il est donc nécessaire de adopter une approche d'échantillonnage et de rejet. En utilisant cette approche, vous pouvez obtenir un 2242 rouleaux attendus de 1000 appels à r, mais il y a des frais supplémentaires de la comptabilité et basec'est un nom de fonction très long.

Peter Taylor
la source
5
"et baseest un nom de fonction très long" Vous n'utilisez apparemment pas Mathematica . Nous obtenons des merveilles comme NegativeBinomialDistribution, ExponentialGeneratingFunction, MathieuCharacteristicExponent, InverseFourierSequenceTransformet SemialgebraicComponentInstances. :-)
Mr.Wizard
1

Python 65 63

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

La fonction R() est le randomiseur ascendant.

Usage:

$ ./rollDice.py
3
$ ./rollDice.py
5
Mat
la source
Pourquoi ne pas vous débarrasser de votre forboucle et appeler Rune seule fois avant votre whileboucle?
Keith Randall
@KeithRandall Le nombre que je renvoie comme mon lancer de dés est le dernier chiffre du nombre que le générateur ascendant renvoie. J'ai besoin de faire 10 appels au générateur ascendant pour assurer des probabilités égales pour tous les chiffres possibles.
Matt
Pourquoi 10 appels? En principe, si le générateur est aléatoire, chaque appel ne devrait-il pas offrir une probabilité égale pour l'un des (dix) chiffres? Bien sûr, dans la pratique, vous ne pouvez vous attendre à approcher des nombres égaux pour chacun des nombres.
DavidC
@DavidCarraher Le générateur renvoie des nombres aléatoires de 1 à n où n est le nombre de fois que vous l'avez appelé. Je regarde le dernier chiffre de ce numéro retourné. Si n n'est pas un multiple entier de 10, la probabilité ne sera pas uniforme. Par exemple: si n = 13, les probabilités se décomposent comme suit: 1/9 pour les rôles 1,5,6 et 2/9 pour les rôles 2,3,4
Matt
@Matt: J'ai supposé R()renvoyer un flotteur et vous saisissiez le chiffre le moins significatif. Maintenant qu'il a été précisé que R()renvoie un entier, cela a du sens.
Keith Randall
1

Python, 56

r est défini comme:

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

le générateur de dés d:

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

utilisation, par exemple, pour 100 rouleaux:

for i in range(100):print d()
scleaver
la source
vous pouvez probablement supprimer le import mathsi vous le remplacez math.ceil(...)parint(...)+1
Matt
Je le ferais, mais cela produirait 7 comme sortie possible.
scleaver
Oh oui. J'ai manqué ça.
Matt
mellamokb a clarifié une question que j'avais sur le randomiseur ascendant. Vous n'êtes pas autorisé à lui demander n.
Matt
1

Mathematica 51

Le générateur de nombres aléatoires,, rest réinitialisé en définissant la variable globale nsur 1.

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

Code

Pas en lice pour le code le plus court ...

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 lancers de dés ont nécessité 60031 appels vers h. Tallymontre la répartition par numéros 1-6.

60031

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

DavidC
la source
1

Perl, 22 ou 45

Implémentation du générateur de nombres aléatoires ascendants:

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

Générateur:

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

Test:

n nombre 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 lancers de dés ont nécessité 60000042 appels en r et 570.432735 secondes
o_o
la source
0

opcode x86, 15 octets

f:  mov cx, 6
    call r ; return in AX
    loop $-3
    cwd
    div word [f+1]
    inc dx
    ret ; return in DX
l4m2
la source
Apparemment, c'est un article de mauvaise qualité?
Muhammad Salman
0

GolfScript , 8 octets

f;3f*f(-

Essayez-le en ligne!

Il fait éclater le générateur une fois, puis se débarrasse du résultat. Ensuite, il lance f2 et le multiplie par 3 (3 ou 6), puis soustrait f3-1 (0, 1, 2), ce qui donne (3-2, 3-1, 3-0) ou (6-2, 6-1, 6-0) W5.

Golfscript et la fonction aléatoire existaient avant la publication de cette question, tout comme la soumission légale.

Il s'agit de la soumission à exécution unique. Si vous devez l'exécuter plusieurs fois en un seul appel,

GolfScript , 12 octets

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

Essayez-le en ligne!

Cela réinitialise votre appel i à 0 afin de le réinitialiser en conséquence. Ce TIO montre 50 résultats aléatoires.

Mathgeek
la source
0

C (gcc) , 31 octets

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

Tous les 6 appels, la probabilité que chaque nombre compris entre 1 et 6 inclus soit généré est égale.

cest #defined comme un appel à une fonction qui génère les nombres aléatoires parfaits.

Essayez-le en ligne!

SS Anne
la source