Le but de ce puzzle est de prendre un jeu de 52 cartes et de le mélanger pour que chaque carte soit dans une position aléatoire.
Donné:
- Un tableau,
deck
de 52 entiers distincts représentant les cartes. Lorsque vous commencez,deck
contient exactement une de chaque carte dans un ordre inconnu. - Une fonction
int rand(min, max)
,, qui renvoie un entier aléatoire entre les entiersmin
etmax
, inclus. Vous pouvez supposer que cette fonction est vraiment aléatoire. - Une fonction,
void swap(x, y)
qui échange deux cartes dans le jeu. Si vous appelezswap(x, y)
, les cartes aux positionsx
ety
changeront de place.
Quand:
- Le programme appelle
shuffle()
(oushuffle(deck)
oudeck.shuffle()
ou comme votre implémentation aime s'exécuter),
Alors:
deck
doit contenir exactement une de chaque carte dans un ordre parfaitement aléatoire.
The Catch:
Vous ne pouvez déclarer aucune variable. Appelez swap
et rand
autant que vous le souhaitez, mais vous ne pouvez pas déclarer vos propres variables. Cela inclut les for
compteurs de boucles - même ceux implicites comme dans a foreach
.
Clarifications:
- Vous pouvez modifier des détails mineurs en fonction de la langue choisie. Par exemple, vous pouvez écrire
swap
pour commuter deux entiers par référence. Les changements devraient être de faire fonctionner cela avec votre langue, et non de rendre le puzzle plus facile. deck
peut être une variable globale, ou vous pouvez l'intégrer comme paramètre.- Vous pouvez faire tout ce que vous voulez sur le contenu
deck
, mais vous ne pouvez pas changer sa longueur. - Vos cartes peuvent être numérotées 0-51, 1-52 ou tout ce que vous voulez.
- Vous pouvez écrire ceci dans n'importe quelle langue, mais sans tricher avec la fonction intégrée de votre langue
shuffle
. - Oui, vous pouvez écrire la même ligne 52 fois. Personne ne sera impressionné.
- Le temps d'exécution n'a pas d'importance, mais le vrai hasard le fait.
- Ce n'est pas vraiment du golf de code, mais n'hésitez pas à minimiser / obscurcir votre code.
Edit: code de chaudière et visualiseur
Si vous avez utilisé .NET ou JavaScript, voici un code de test qui peut vous être utile:
JavaScript:
- Visualiseur JavaScript rapide et sale, avec source CoffeeScript: https://gist.github.com/JustinMorgan/3989752bdfd579291cca
- Version exécutable (collez simplement votre
shuffle()
fonction): http://jsfiddle.net/4zxjmy42/
C #:
- Visualiseur ASP.NET avec code C # derrière: https://gist.github.com/JustinMorgan/4b630446a43f28eb5559
- Stub avec uniquement les méthodes
swap
etrand
utilitaires: https://gist.github.com/JustinMorgan/3bb4e6b058d70cc07d41
Ce code trie et mélange le paquet plusieurs milliers de fois et effectue des tests d'intégrité de base: pour chaque mélange, il vérifie qu'il y a exactement 52 cartes dans le paquet sans répétition. Ensuite, le visualiseur trace la fréquence de chaque carte se terminant à chaque endroit du jeu, affichant une carte de chaleur en niveaux de gris.
La sortie du visualiseur doit ressembler à de la neige sans motif apparent. Évidemment, cela ne peut pas prouver le vrai hasard, mais c'est un moyen rapide et facile de vérifier par sondage. Je recommande de l'utiliser ou quelque chose comme ça, car certaines erreurs dans l'algorithme de brassage conduisent à des modèles très reconnaissables dans la sortie. Voici un exemple de la sortie de deux implémentations, l'une avec une faille commune:
La version défectueuse mélange partiellement le jeu, donc pourrait bien paraître si vous avez examiné le tableau à la main. Le visualiseur permet de remarquer plus facilement un motif.
la source
deck
lui-même.swap
votre choix, tant qu'elle remplit son objectif de base. Une partie de ma raison de faireswap
un don était pour que les gens puissent le traiter comme de la «magie» et se concentrer sur le problème principal sans avoir à se soucier qu'il fonctionne dans la langue de son choix. Vous pouvez le faire ou écrire le vôtreswap
, c'est à vous de décider.Réponses:
Javascript
Je crois que c'est la forme de solution envisagée, j'utilise la carte en position 0 pour suivre les progrès, en mélangeant uniquement les cartes qui ont déjà été utilisées comme compteur, cela atteint la norme 52! permutations avec une distribution égale parfaite. La procédure est compliquée par l'échange XOR qui ne permet pas qu'un élément soit échangé par lui-même.
Edit: J'ai intégré un tri qui trie chaque élément en place juste avant son utilisation, permettant ainsi à cela de fonctionner avec un tableau non trié. J'ai également abandonné les appels récursifs en faveur d'une boucle while.
la source
Haskell
Voici une implémentation sans point. Aucune variable, paramètre formel ou récursivité explicite. J'ai beaucoup utilisé la fonction de refactorisation de lambdabot
@pl
("inutile").Voici ma procédure de test pour m'assurer que les nombres ont été uniformément distribués:
Voici l'algorithme d'origine:
la source
((.) .) . (. (++))
et ceci(((.) . (,)) .)
sont mes préférés. Wow lambdabot. Juste wow.J
Ignorer ce deck est une variable, il y a une évidence ...
Bien sûr, si vous voulez vraiment une fonction, il y a celle-ci, qui fonctionnera même si vous oubliez de supprimer les jokers (ou essayez de mélanger autre chose que des cartes).
Pour que...
Ceci est probablement en dehors de l'intention de la question, qui serait d'implémenter vous-même le shuff de rand (
?
). Je pourrais le faire plus tard quand je ne suis pas censé travailler.Explication
Explication de
52 ? 52
:x ? y
est x éléments uniques aléatoires de y.L'explication
{~ (# ? #)
est plus difficile à cause des fourches et des crochets . Fondamentalement, c'est la même chose queshuffle =: 3 : '((# y) ? (# y)) { y'
, qui a un argument implicite (y
).# y
donne la longueur de yx { y
est l'élément de y dans l'index x, ou (dans ce cas) les éléments dans les index de x.Voir J Vocabulaire pour plus de détails sur les opérateurs, bien que la syntaxe et la sémantique soient assez délicates à cause de la programmation de rang et tacite.
la source
{52?⍵}
est une fonction anonyme qui prend 52 éléments aléatoires de son argument, qui serait ici une liste de 52 entiers)Python
la source
[1:]
signifie? Est-ce que cela revient sur un sous-tableau dedeck
?a, b = b, a
astuce.Utilisation de la représentation factorielle
Dans la représentation factorielle d'une permutation, un élément i prend des valeurs de 0 à Ni. Donc, une permutation aléatoire est juste
rand(0,i)
pour chaque Ni.En J:
où
? x
estrand(0,x-1)
et|.>:i.52
est52 51 ... 1
Ensuite, si
a
la valeur du ième factoradic, nous faisons l'échange:swap(deck[i], deck[i+a])
. La liste des paires à échanger est:L'échange que nous utiliserons fonctionne comme ceci:
Ce n'est pas vraiment "par référence" mais il n'y a pas de fonctions réelles dans J.
Nous utiliserons la longueur du deck (
#deck
) pour éviter d'utiliser une constante.Programme complet en J:
la source
C #
Voici ma propre réponse basée sur l'algorithme de Fisher-Yates . Devrait vous donner un mélange parfait si votre générateur de nombres aléatoires est assez bon.
Version anglaise:
deck[0]
avec celle àdeck[v]
, oùv
est la valeur nominale de la carte àdeck[0]
. Répétez jusqu'à ce quev == 0
. Cela triera partiellement le jeu, mais cela n'a pas d'importance. Vous savez maintenant que la carte 0 est à l'avant du paquet, ce qui signifie que vous pouvez voler cet espace dans le tableau et l'utiliser comme compteur de boucles. C'est la clé "triche" pour le problème des variables locales.i
avec celle àrand(i, 51)
. Notez que vous avez besoinrand(i, 51)
, pasrand(1, 51)
. Cela ne garantit pas que chaque carte est randomisée.deck[0]
à 0. Maintenant, le paquet entier est mélangé à l'exception de la première carte, alors échangezdeck[0]
avecdeck[rand(0, 51)]
et vous avez terminé.Version C #:
Version Javascript:
... où
swap(a, b)
échangedeck[a]
avecdeck[b]
.la source
Ruby, une ligne
Est-ce considéré comme de la triche? Cela devrait être aussi aléatoire que possible.
(La
rand
méthode de Ruby ne prend qu'un seul argument, puis génère un nombre n tel que 0 <= nombre <argument.)De plus - similaire à la solution Perl de sogart, mais pour autant que je sache, elle ne souffre pas du problème:
Sort_by de Ruby est différent de sort - il génère d'abord la liste de valeurs pour trier le tableau, puis seulement le trie par eux. C'est plus rapide quand il est coûteux de trouver la propriété par laquelle nous sommes triés, un peu plus lent dans tous les autres cas. Il est également utile dans le golf de code: P
la source
deck[0..51]
contourne quelque peu la règle "pas de variables" en utilisant une fonctionnalité du langage. C'est juste, je pense juste qu'il perd une partie du défi. :) Je ne connais pas Ruby; pouvez-vous expliquer la(0..51).map{deck.delete_at(rand deck.length)}
partie? Est-ce que cela supprime les cartesdeck
?deck
et l'ajoute à la liste interne des résultats quimap
s'accumule. Puis, quand il ne reste plus rien dansdeck
lemap
résultat, il est copiédeck
. Fondamentalement, il y a un temporaire, mais c'est une fonctionnalité de langage plutôt qu'une variable explicite :)deck.sort_by!{rand}
est plus court.Javascript
REMARQUE: cette solution n'est techniquement pas correcte car elle utilise un deuxième paramètre
i
, dans l'appel àshuffle
, qui compte comme une variable externe.Appeler avec
shuffle(deck,52)
Un exemple de travail complet (a dû être
swap
légèrement modifié car il n'y a pas de référence par passage des entiers en JavaScript):la source
shuffle
comme variables, mais je ne l'ai pas spécifié ainsi +1. Belle utilisation de la récursivité aussi.deck[rand(0,i-1)]
place dedeck[rand(0,i-2)]
. Échangez également jusqu'ài=0
au lieu de vous arrêter ài=1
. Est ce que ça aide?C ++
Évite d'échanger des éléments avec eux-mêmes, donc doit appeler deux fois pour être aléatoire.
la source
swap(deck[rand(1, 51)], (deck[0] - 51) / 100);
Commentswap
saurez où mettre la deuxième valeur? Vous manquez également un)
.deck[0]
, mais pas comme vous l'avez fait.ré
la source
Une autre solution Perl, qui produit en fait une sortie uniformément distribuée:
Cette solution utilise Perl
rand
, qui renvoie un nombre aléatoire x dans la plage 0 ≤ x <1. Elle ajoute un tel nombre aléatoire à chaque entier dans l'entrée, trie les nombres en fonction de leurs parties fractionnaires, et finalement supprime à nouveau ces parties fractionnaires .(Je crois que l'utilisation des variables spéciales
$_
,$a
et$b
s'inscrit dans l'esprit du défi, car ce sont la façon dont perl transmet l'entrée àmap
etsort
, et elles ne sont pas utilisées à d'autres fins dans le code. En tout cas, je crois ils sont en fait les homonymes des valeurs d'entrée, pas de copies indépendantes Ce n'est pas en fait un remaniement en place, bien que,. à la foismap
et desort
créer des copies de l'entrée sur la pile).la source
Java
Je suis surpris que personne n'ait déclaré l'évidence: (je suppose que le swap (x, x) ne fait rien.
OK, ok, ça peut être plus court:
la source
Burlesque
Ce que vous demandez réellement, c'est une permutation aléatoire d'une liste d'entiers?
r@
nous donnera toutes les permutations, et nous choisissons simplement une permutation aléatoire.Étant donné que nous avons besoin d'un vrai caractère aléatoire, quelque chose que Burlesque n'est pas capable de faire parce que Burlesque n'a pas de fonctionnalité d'E / S dont vous auriez besoin pour fournir une source de caractère aléatoire via STDIN.
C'est probablement quelque chose que je corrigerai dans la version ultérieure (c'est-à-dire générer une graine aléatoire au démarrage et la pousser vers la pile secondaire ou quelque chose comme ça, mais l'interpréteur Burlesque lui-même n'a pas d'E / S).
la source
Javascript
Je ne sais pas si c'est "tricher" mais ma solution utilise le tableau local natif des arguments d'une fonction. J'ai inclus mes propres fonctions de
rand()
swap()
etfilldeck()
. Fait intéressant, cela devrait fonctionner avec un jeu de n'importe quelle taille.la source
Tcl , 32 octets
time
Fonction abusive qui sert à mesurer le temps passé par un script, mais peut également servir de mécanisme de boucle sans déclarer de variables.Essayez-le en ligne!
la source
perl - ce n'est pas un remaniement approprié comme expliqué dans les commentaires!
Je pense que je n'ai rien utilisé comme échange, etc. était-ce nécessaire dans le cadre du problème?
la source
JavaScript 4 lignes
Réponse originale qui n'était pas assez aléatoire. L'échange n'était pas garanti de toucher chaque élément du jeu.
la source
shuffle
légèrement changé votre code pour qu'il corresponde à monswap
implémentation, mais le voici: textuellement: jsfiddle.net/m7km4u6g