Votre programme / fonction doit
- produire exactement un entier
- sortie tout entier avec une probabilité positive
- sortie un entier supérieur à 1.000.000 ou inférieur à -1.000.000 avec au moins une probabilité de 50%.
Exemples de sorties (toutes doivent être possibles):
59875669123
12
-42
-4640055890
0
2014
12
24
-7190464664658648640055894646646586486400558904644646646586486400558904646649001
Précisions:
- Un saut de ligne arrière est autorisé.
- Les zéros non significatifs ne sont pas autorisés.
-0
est autorisé.
Le code le plus court gagne.
way too long to fit in an integer
- Ceci n'est vrai que si vous supposez que celainteger
signifie leint
type de données sur un arc 32/64 bits, ce qui n'est pas nécessairement une hypothèse valide. "Entier" a commencé comme un terme mathématique , qui n'a pas de contraintes de taille.Réponses:
CJam,
161413 octetsCela fonctionnera très longtemps, car il utilise l'horodatage actuel (de l'ordre de 10 12 ) pour déterminer si la boucle doit se terminer. J'utilise ceci comme mémoire, car c'est le plus court, mais il y a deux alternatives de 14 octets, qui ont leurs propres mérites:
Celui-ci n'est pas limité par la période du PRNG, car la plage de tous les nombres aléatoires dépend de l'horodatage actuel. Par conséquent, cela devrait être en mesure de produire n'importe quel nombre, bien que la probabilité de nombres négatifs, voire de petits nombres positifs, disparaisse.
Vous trouverez ci-dessous une version équivalente qui utilise
3e5
au lieu de l'horodatage. Et20
pour la première plage (comme la soumission de 13 octets). C'est beaucoup plus rapide et respecte également toutes les règles. C'est en quelque sorte le cas limite pour obtenir la probabilité de 50% pour les nombres au-delà de 1 000 000 tout en conservant un temps d'exécution raisonnable et une petite taille de code. L'explication et la justification mathématique se réfèrent à cette version:Cela prend généralement quelques secondes. Vous pouvez remplacer le
5
par un2
pour le faire fonctionner encore plus rapidement. Mais alors l'exigence sur la probabilité de 50% ne sera remplie que pour 1 000 au lieu de 1 000 000.Je commence à 0. Ensuite, j'ai une boucle, dont je casse avec une probabilité 1 / (3 * 10 5 ). Dans cette boucle, j'ajoute un entier aléatoire entre -1 et 18 (inclus) à mon total cumulé. Il y a une probabilité finie (quoique faible) que chaque entier soit sorti, les entiers positifs étant beaucoup plus susceptibles que les négatifs (je ne pense pas que vous en verrez un négatif dans votre vie). Sortir avec une si faible probabilité et incrémenter la plupart du temps (et ajouter bien plus que soustraire) garantit que nous dépasserons généralement 1 000 000.
Quelques justifications mathématiques:
La probabilité que nous fassions moins que ce nombre d'étapes est
qui évalue à
0.324402
. Par conséquent, dans environ les deux tiers des cas, nous ferons plus de 117 647 pas, et facilement chacun 1 000 000.9e9
sans ajouter d’octets (mais des années d’exécution).... ou 11 octets?
Enfin, il existe une version à 11 octets, qui n'est pas non plus limitée par la période du PRNG, mais qui manquera de mémoire à peu près à chaque fois. Il ne génère qu'un seul nombre aléatoire (basé sur l'horodatage) à chaque itération, et l'utilise à la fois pour l'incrémentation et la fin. Les résultats de chaque itération restent sur la pile et ne sont résumés qu'à la fin. Merci à Dennis pour cette idée:
la source
Kmr
dans une période est probablement toujours un grand nombre positif supérieur à la période. Et il ne peut pas produire tous les nombres possibles dans ce cas.Java,
133149Exemples de sorties
Non golfé
Ancienne réponse (avant le changement de règle)
la source
-
.Mathematica - 47
Fondamentalement, il suffit de générer un nombre aléatoire en utilisant une distribution normale avec une variance égale à 1500000. Cela produira un entier entre -10 ^ 6 et 10 ^ 6 avec une probabilité de 49,5015%.
la source
Python 2,
7569 octetsIl est trivial de vérifier que la boucle while au milieu peut générer tous les entiers (bien que biaisée vers zéro). "12" est choisi de telle sorte qu'il y ait environ la moitié des nombres dépassant ± 10 6 .
Solution plus ancienne:
Python 2, 44 octetsBasé sur la solution Mathematica .Ne fonctionne pas vraiment car Python
float
n'a qu'une précision limitée.la source
Rubis, 70
Pour rendre possible la génération de très grands nombres, je renvoie le nombre en tant que
String
d'un lambda. Si ce n'est pas autorisé, comptez 8 caractères supplémentaires (pourputs f[]
) pour en faire un programme au lieu d'une fonction.Explication
Générez un nombre entre
-1,000,000
et1,000,000
. Si le nombre est1
ou supérieur, le nombre est renvoyé sous la forme d'unString
.Si le nombre est inférieur à
1
, la fonction est appelée récursivement pour renvoyer un nombre en dehors de la plage de nombres. Pour vous assurer que des nombres négatifs peuvent également être générés, un-
est préfixé au résultatString
si le nombre initial est supérieur à-500,000
.J'espère avoir bien compris le défi!
la source
R, 38
Tirages de la distribution gaussienne avec une moyenne de 2 000 000, choisis au hasard et un écart-type de 1 000 000, de sorte qu'environ 2/3 des tirages se situeront entre 1 000 000 et 3 000 000. La distribution est illimitée donc en théorie cela peut générer n'importe quel entier. Le package Rmpfr remplace les R intégrés dans les flotteurs doubles avec une précision arbitraire.
la source
sample(c(1,-1),1)
réflexion. Un simple centrage sur 1e6 devrait suffire.Perl, 53 caractères
Je ne vois certainement aucune raison de travailler avec des entiers lors de l'impression d'un :)
A la même probabilité d'imprimer un nombre avec ou sans un "-".
Imprime un nombre à 1 chiffre 10% du temps, un nombre à 2 chiffres 9% du temps, un nombre à 3 chiffres 8,1% du temps, un nombre à 4 chiffres 7,29% du temps, un nombre à 5 chiffres 6,56% du temps, un nombre à 6 chiffres 5,9% du temps, etc. Toute longueur est possible, avec une probabilité décroissante. Les nombres d'un à cinq chiffres représentent environ 41,5% des cas de sortie, et le nombre 1 000 000 (ou -1 000 000) seulement 6 millionièmes de pour cent, de sorte que le nombre de sortie sera en dehors de la plage de -1 000 000 à 1 000 000 environ 54,6 % du temps.
"0" et "-0" sont des sorties possibles, ce qui, je l'espère, n'est pas un problème.
la source
print int(rand(20)-10)||1
. J'ai besoin d'un moyen de générer 0 en sortie, cependant. Peut-être || mourir 0, si la poubelle de fin après le zéro est autorisée. Sinon, il faut un court chemin pour imprimer le zéro et sortir sans autre sortie siint(rand(20)-10)==0
.Perl, 114 caractères
Panne:
La probabilité d'obtenir une valeur comprise entre -1 000 000 et 1 000 000 tend vers zéro MAIS c'est possible.
Perl, 25Génère un entier aléatoire dans la plage de +/- 2 ^ 99.
Panne
Testé avec 1 million d'échantillons:
Cela répond à toutes les règles:
Éditer:
J'ai dû augmenter l'exposant pour que des entiers plus grands soient générés. J'ai choisi 99 car il maintient le code aussi court que possible.la source
-2^31
et+2^31-1
(32bits). Vous pouvez facilement augmenter les exposants si vous souhaitez générer des entiers plus grands, mais cela peut échouer en fonction de l'implémentation de Perl.1.#INF
pour être exact)C #,
126107 octetsNon golfé:
La chance de générer un nombre de n chiffres est 1/2 ^ (n-10), ce qui est supérieur à 0 pour tous les n positifs et 1/2 pour n = 11.
Crée également des zéros non significatifs, qui ne semblent pas interdits dans la question d'origine ni dans aucun de ses commentaires.la source
using System;
, vous n'avez pas besoin deSystem.Random
deux fois, mais justeRandom
, non?using
instructions. De toute façon, cela ne sauverait qu'un seul caractère.-1E6, 1E6+1
.Perl, 62 octets
print $n=int rand(20)-10;while($n&&rand>.1){print int rand 10}
J'ai eu la même idée que @Hobbs, de générer un chiffre à la fois, mais son code ne satisfaisait pas à l'exigence supplémentaire sans zéros non significatifs. La génération du premier chiffre au lieu du simple signe a résolu cela. Et à moins qu'il n'y ait un moyen plus court de quitter si nous imprimons un zéro, ou un moyen plus court de générer le premier -9 à 9, cela devrait le faire pour la taille.
Dans une boucle shell:
while perl -e '...'; do echo;done |less
Je pense que c'est l'un des plus courts qui ne nécessite pas de RAM infinie pour satisfaire le problème. En prime, la sortie n'est pas fortement biaisée vers quoi que ce soit et l'exécution est très rapide.
J'ai essayé d'utiliser bit à bit et d'enregistrer un caractère dans la condition while, mais je pense que cela finit par être vrai plus souvent, donc la boucle se termine plus tôt. Aurait besoin de plus de caractères pour ajuster d'autres choses pour contrer cela, pour maintenir la probabilité de générer des abs (sortie)> 1M.
la source
Javascript (73)
Cette solution utilise que vous pouvez construire un nombre avec la base n en multipliant le nombre précédent par n et en ajoutant un chiffre dans la base n . Nous en avons un supplémentaire
..?..:..
pour pouvoir créer tous les entiers négatifs. Le code suivant doit être testé dans une console de navigateur.La probabilité d'obtenir un entier> =
2^1
(ou <=-(2^1)
) est égale à la chance que la boucle soit exécutée 2 fois. La chance que cela se produise est(98/99)^2
. La chance d'obtenir un nombre supérieur à2^20
(ou <=-(2^20)
) est donc de(98/99)^21 = 0.808
81%. C'est tout en théorie cependant, et en supposant que Math.random est vraiment aléatoire. Ce n'est évidemment pas le cas.Extrait testant ce code. Également d'une manière plus lisible.
Afficher l'extrait de code
la source
GolfScript, 20 octets
Ouais, celui-ci est aussi un peu lent.
Comparé à des langages comme CJam et Pyth, GolfScript souffre d'un mot-clé de génération de nombres aléatoires (
rand
). Pour surmonter ce handicap, j'avais besoin de trouver un moyen de ne l'utiliser qu'une seule fois.Ce code fonctionne en choisissant à plusieurs reprises un nombre aléatoire entre 0 et 8 8 -1 = 16 777 215 inclus, et en incrémentant un compteur jusqu'à ce que le nombre aléatoire se trouve être 0. La valeur du compteur résultant a une distribution géométrique avec une médiane d' environ -1 / log 2 (1 - 1/8 8 ) ,6 11 629 080, il satisfait donc au test "plus de 1 000 000 au moins 50% du temps".
Hélas, le nombre aléatoire ainsi généré est toujours strictement positif. Ainsi, la
.2&(*4/
partie supplémentaire est nécessaire pour la laisser devenir négative ou nulle. Il fonctionne en extrayant le deuxième bit le plus bas du nombre (qui est donc soit 0 ou 2), en le décrémentant pour le rendre -1 ou 1, en le multipliant par le nombre d'origine et en divisant le résultat par 4 (pour se débarrasser de les deux bits les plus bas, qui sont maintenant corrélés avec le signe, et aussi pour permettre au résultat de devenir nul). Même après la division par 4, la valeur absolue du nombre aléatoire a toujours une médiane de -1 / log 2 (1 - 1/8 8 ) / 4 ≈ 2 907 270, il passe donc toujours le test de 50%.la source
JavaScript, 81 octets
Ce code remplit toutes les règles:
0
dans la sortieEn prime, l'algorithme s'exécute avec une complexité temporelle de O (log 10 n) , il renvoie donc l'entier presque instantanément.
Cela suppose un environnement REPL. Essayez d'exécuter le code ci-dessus dans la console de votre navigateur ou utilisez l'extrait de pile ci-dessous:
Algorithme :
s
jusqu'à ce que aMath.random() > 0.1
.Math.random() > 0.5
, rendez le nombre négatif (en ajoutant la chaînes
avec-
).Cet algorithme n'a pas de distribution uniforme sur tous les entiers. Les nombres entiers avec un nombre de chiffres plus élevé sont moins probables que les nombres inférieurs. Dans chaque boucle d'itération, il y a 10% de chances que je m'arrête au chiffre actuel. Je dois juste m'assurer que je m'arrête après 6 chiffres plus de 50% du temps.
Cette équation de @nutki explique la valeur maximale du pourcentage de chance d'arrêt basée sur la condition ci-dessus:
Ainsi, 0,1 est bien dans la plage pour satisfaire aux trois règles de la question.
la source
TI-BASIC, 14 octets
Semblable à la réponse R de @ ssdecontrol, celle-ci s'appuie sur la distribution gaussienne avec une moyenne de -1 000 000 ou 1 000 000, choisie au hasard, et l'écart-type 9. La distribution n'est pas bornée, donc en théorie, cela peut générer n'importe quel entier.
Explication :
la source
:
signifie «imprimer» en raison de la façon dont l'explication est présentée). Mais peut-il générer des nombres de plus de 20 chiffres?randNorm
?Bash, 66
Il imprime presque toujours 5000000. Mais s'il trouve un numéro valide dans
/dev/random
, il imprimera ce numéro à la place.Et celui-ci est plus rapide:
la source
/dev/urandom
ce qui est moins aléatoire./dev/urandom
dans un script shell est fondamentalement la même chose que d'appelerrand()
dans d'autres langues. Bien que si vous utilisez vraiment bash, pas POSIX sh, vous pouvez obtenir des nombres aléatoires à partir deecho $RANDOM
. wiki.ubuntu.com/DashAsBinSh donnehexdump /dev/urandom
comme équivalent pour bare-POSIX-minimum/bin/dash
.C ++, 95 octets
Étendu:
Explication:
La fonction continue d'imprimer des chiffres aléatoires consécutifs jusqu'à ce qu'un commutateur à valeur aléatoire prenne la valeur requise pour arrêter la fonction. d est la variable qui conserve la valeur du chiffre suivant à imprimer. s est la variable de commutation qui prend des valeurs entières aléatoires dans l'intervalle [0, 9], si s == 9 alors plus aucun chiffre n'est imprimé et la fonction se termine.
Les variables d et s sont initialisées afin de donner un traitement particulier au premier chiffre (en le prenant dans l'intervalle [-9, 9] et si le premier chiffre est nul alors la fonction doit se terminer pour éviter les zéros non significatifs). La valeur de d peut être affectée comme d = rand ()% 10 mais le premier chiffre ne peut pas être négatif. d est assigné à la place comme d = (rand ()% 19 + d + 9)% 10 et initialisé à -18 de sorte que la première valeur de d sera comprise entre [-9, 9] et les valeurs suivantes seront toujours comprises entre [0 , 9].
La variable s varie aléatoirement de [0, 9], et si s est égal à 9, la fonction se termine, donc après l'impression du premier chiffre, le suivant sera imprimé avec une probabilité de 90% (en supposant que rand () est vraiment aléatoire, et afin de satisfaire à la troisième condition). s peut être facilement attribué comme s = rand ()% 10, cependant, il y a une exception, si le premier chiffre est zéro, la fonction doit se terminer. Afin de gérer une telle exception, s a été attribué à s = 9-rand ()% 10 * min (d * d + s + 1,1) et initialisé à -1. Si le premier chiffre est zéro, le min renverra 0 et s sera égal à 9-0 = 9. L'affectation de la variable s sera toujours comprise entre [0, 9], donc l'exception ne peut se produire qu'au premier chiffre.
Caractéristiques (en supposant que rand () est vraiment aléatoire)
L'entier est imprimé chiffre par chiffre, avec une probabilité fixe de 90% d'imprimer un autre chiffre après avoir imprimé le dernier.
0 est l'entier avec la plus grande chance d'être imprimé, avec une probabilité d'environ 5,2%.
La probabilité d'imprimer un entier sur l'intervalle [-10 ^ 6, 10 ^ 6] est d'environ 44% (le calcul n'est pas écrit ici).
Les entiers positifs et négatifs sont imprimés avec la même probabilité (~ 47,4%).
Tous les chiffres ne sont pas imprimés avec la même probabilité. Par exemple: au milieu de l'impression de l'entier, si le dernier chiffre était 5, le chiffre 3 aura une chance légèrement inférieure d'être imprimé ensuite. En général, si le dernier chiffre était d, le chiffre (d + 18)% 10 aura une chance légèrement inférieure d'être imprimé ensuite.
Exemples de sorties (10 exécutions)
la source
Bash, 42 octets
printf "%d\n" 0x$(xxd -p -l5 /dev/random)
/ dev / random sur OSX est juste des octets aléatoires, et
xxd -p -l5
convertit 5 des caractères ascii en hexadécimal, et leprintf
transforme en format décimal.la source
Pyth , 11 octets
Remarque: ce programme se bloquera probablement avec une erreur de mémoire sur n'importe quel ordinateur réel. Pour le tester, essayez de le remplacer
G
par une chaîne plus courte, comme dans ce code, qui génère des nombres en moyenne autour de 28000:Ce code boucle, en ajoutant un nombre aléatoire de -1 à 8
Z
, avec une probabilité de 2 ^ -26 de quitter la boucle à chaque répétition. La probabilité 2 ^ -26 est atteinte en sélectionnant un élément aléatoire (O
) de l'ensemble de tous les sous-ensembles (y
) de l'alphabet (G
).Détails techniques et justification:
La probabilité 2 ^ -26 est dérivée de deux faits:,
y
lorsqu'elle est appelée sur des séquences, est la fonction power-set, an construit la liste de tous les sous-ensembles de l'entrée. Depuis l'entrée,,G
est de 26 caractères de long, ce bloc d'alimentation,yG
a 2 ^ 26 entrées.OyG
sélectionne un élément aléatoire parmi ces 2 ^ 26 entrées. Exactement l'une de ces entrées, la chaîne vide, sera évaluée comme fausse lorsqu'elle est passée àW
, la boucle while. Par conséquent, il y a une probabilité de 2 ^ -26 de sortir de la boucle à chaque fois.Dans tout nombre fixe de cycles de boucle K, la probabilité d'obtenir le nombre K * 3,5 + m et d'obtenir K * 3,5 - m est égale, car chaque séquence d'additifs qui atteint un total peut être inversée, -1 -> 8, 0 -> 7, etc., pour réaliser l'autre. De plus, les nombres plus proches de K * 3,5 sont nettement plus probables que les nombres plus éloignés. Ainsi, si K> 2000000 / 3,5 = 571428,5, la probabilité d'obtenir un nombre supérieur à 1000000 est supérieure à 75%, car certains des résultats supérieurs à ce nombre peuvent être mis en correspondance un à un avec tous les résultats inférieurs à ce nombre, et la moitié inférieure supérieure, peuvent être mis dans une correspondance un à un avec ceux de moins de 1000000. La probabilité d'obtenir au moins 571429 boucles est (1-2 ^ -26) ^ 571429, ce qui n'est pas moins de (1-2 ^ -26 * 571429), le nombre attendu de sorties de boucle au cours des 571429 premiers essais, soit 99,1%. Ainsi, sur 99,1% ou plus des essais, il y a 75% ou plus de chances d'obtenir au moins 1000000, donc il y a plus de 50% de chances de dépasser 1000000.
Ce code repose sur un comportement de l'
O
endroit où un bogue a été introduit accidentellement il y a 3 jours et a été corrigé aujourd'hui. Il devrait fonctionner sur n'importe quelle version de Pyth 3 avant le 22 décembre ou après aujourd'hui. Le code suivant est équivalent et a toujours fonctionné:la source
Java, 113 octets
Ce programme imprime un nombre binaire sur le flux de sortie standard. Vous devrez peut-être attendre un certain temps car la probabilité qu'il termine le nombre (ou qu'il soit positif) est d'environ 0. L'idée que la valeur absolue d'un nombre généré est inférieure à 1 million est amusante, mais possible.
Non golfé:
Exemple de sortie: sera publié lorsqu'un nombre sera généré.
la source
Java (JDK) ,
140127 octets-13 bytes
en insérant plus de logique dans l'en-tête de la boucle - grâce à @ceilingcatEssayez-le en ligne!
la source