Contexte
J'ai une collection de "chaussettes de semaine", qui sont sept paires de chaussettes étiquetées par les jours de la semaine. Quand je lave mes chaussettes, elles finissent en tas, et je dois les disposer en paires correctes avant de les mettre dans le placard. Ma stratégie consiste à retirer une chaussette au hasard de la pile et à la mettre dans un tiroir. Chaque fois qu'il y a une paire de chaussettes assortie sur le tiroir, je les attache ensemble et les mets dans le placard. Votre tâche consiste à simuler ce processus aléatoire et à renvoyer le nombre de tirages requis pour trouver la première paire correspondante.
Contribution
Votre entrée est un entier N ≥ 1 . Il représente le "nombre de jours dans une semaine": il y a N paires de chaussettes dans la pile, et chaque paire a une étiquette distincte. Si nécessaire, vous pouvez également prendre une graine PRNG en entrée.
Production
Votre résultat est le nombre de chaussettes que je dois dessiner avant de trouver la première paire correspondante. Par exemple, si les deux premières chaussettes forment déjà une paire correspondante, la sortie est 2
.
Bien sûr, la sortie est aléatoire et dépend de l'ordre de dessin. Nous supposons que tous les ordres de dessin sont également probables , de sorte que chaque fois qu'une chaussette est tirée, le choix est uniforme et indépendant de tous les autres choix.
Exemple
Soit N = 3 , pour avoir au total 6 chaussettes, étiquetées AABBCC . Une exécution possible du «protocole de dessin de chaussettes» est la suivante:
| Pile | Drawer | Pairs
Begin | AABBCC | - | -
Draw B | AABCC | B | -
Draw C | AABC | BC | -
Draw B | AAC | C | BB
Draw A | AC | AC | BB
Draw A | C | C | AA BB
Draw C | - | - | AA BB CC
La première paire correspondante a été trouvée après avoir dessiné le deuxième B , qui était la troisième chaussette à tirer, donc la sortie correcte est 3
.
Règles et notation
Vous pouvez écrire un programme complet ou une fonction. Le nombre d'octets le plus bas l'emporte et les failles standard sont interdites. L'entrée et la sortie peuvent être dans n'importe quel format raisonnable, y compris unaire (chaîne de 1
s).
Vous pouvez supposer que le RNG intégré à votre langue est parfait. Vous n'avez pas besoin de simuler réellement le protocole de dessin de chaussettes, tant que vos sorties ont la distribution de probabilité correcte.
"Cas de test"
Voici les probabilités approximatives de toutes les sorties pour l'entrée N = 7 :
Output 2 3 4 5 6 7 8
Probability 0.077 0.154 0.210 0.224 0.186 0.112 0.037
Pour tester votre solution, vous pouvez l'exécuter, disons, 40 000 fois et voir si la distribution de sortie est raisonnablement proche de cela.
Draw all socks. End up with an odd number.
Réponses:
Gelée , 8 octets
Essayez-le en ligne! ou vérifiez la distribution pour N = 7 .
Contexte
Soit n le nombre de paires; il y a 2n chaussettes individuelles.
Pour le premier tirage, il y a 2n chaussettes et 0 d'entre elles donnerait une paire assortie. Par conséquent, la probabilité de réussite est de 0 / 2n = 0 .
Étant donné que le premier tirage n'a pas réussi, il y a 2n - 1 chaussettes sur la pile et 1 d'entre elles entraînerait une paire correspondante. Par conséquent, la probabilité de réussite est de 1 / (2n - 1) .
Si le deuxième tirage n'a pas réussi, il y a 2n - 2 chaussettes sur la pile et 2 d'entre elles donneraient une paire correspondante. Par conséquent, la probabilité de réussite est de 2 / (2n - 2) .
En général, si les k premiers tirages ont échoué, il y a 2n - k chaussettes sur la pile et 2 d'entre elles donneraient une paire correspondante. Par conséquent, la probabilité de réussite est k / (2n - k) .
Enfin, si aucun des n premiers tirages n'a réussi, il y a 2n - k chaussettes sur la pile et toutes aboutiraient à une paire assortie. Par conséquent, la probabilité de réussite est n / (2n - n) = 1 .
Comment ça fonctionne
la source
Gelée, 8 octets
Essayez-le en ligne!
Pour vérifier, voici une version qui affiche à la fois la sortie souhaitée et le résultat de l'opération "shuffle list" (pour voir dans quel ordre les chaussettes ont été dessinées).
la source
Python, 66 octets
Dennis a imaginé une manière intelligente de réorganiser les choses en économisant 5 octets.
la source
MATL ,
1615 octetsEssayez-le en ligne! Ou observez la distribution empirique de 1000 échantillons dans le N = 7 (cela prend un certain temps).
Cela génère directement la variable aléatoire représentant le résultat, en fonction de sa distribution de probabilité. Soit N le nombre de paires de chaussettes, et soit p ( k ) la probabilité que le k- ème tirage soit réussi, à condition que le k -1-ème tirage n'aboutisse pas. Ensuite (voir aussi ici ):
Ainsi, le code itère pour un maximum de N +1 tirages. Au k -ième tirage, une variable aléatoire est générée qui est égale à 1 avec la probabilité ( k -1) / (2 * N - k ), ou 0 sinon. Chaque fois que la variable aléatoire est égale à 1 (le tirage a réussi), le processus s'arrête et le courant k est sorti.
la source
MATL ,
1413 octetsEssayez-le en ligne! Ou observez la distribution empirique de 4000 échantillons dans le cas N = 7 (cela prend un certain temps).
la source
JavaScript,
7773 octetsExplication
la source
f=(n)=>
parn=>
(ou deux, si vous souhaitez conserver l'affectation, certains la conservent , d' autres la suppriment ).CJam, 17 octets
Testez-le ici.
la source
Python 3,
142105104 octetsGrâce à Eʀɪᴋ ᴛʜᴇ Gᴏʟғᴇʀ d' avoir sauvé un octet!
Ma première réponse:
Ma nouvelle réponse:
Les deux sortent avec un
NameError
ons
.la source
R, 49
Je suis sûr qu'il doit y avoir une meilleure façon de faire cela dans R! J'ai essayé de faire quelque chose de plus intelligent, mais cela n'a pas fonctionné.
Edit: Amélioré par @bouncyball car il ne doit pas être une fonction.
la source
function(N)
? l'utilisationN=scan();
économiserait 2 octetsPython 2, 101 octets
la source
VBA, 61 octets
- modélise la probabilité de changement de correspondance des chaussettes en raison d'un échec antérieur. Au point d'évaluation, K est "chaussettes en main", donc le numéro de tirage est un de plus.
la source
Pyth, 14 octets
Explication:
la source