À propos de la série
Tout d'abord, vous pouvez traiter cela comme n'importe quel autre défi de golf de code et y répondre sans vous soucier de la série. Cependant, il existe un classement pour tous les défis. Vous pouvez trouver le classement avec plus d'informations sur la série dans le premier post .
Bien que j'ai un tas d'idées alignées pour la série, les défis futurs ne sont pas encore gravés dans le marbre. Si vous avez des suggestions, faites-le moi savoir sur le post sandbox correspondant .
Trou 6: Rouler un d20
Un dé très courant dans les RPG de table est le dé à vingt faces (un icosaèdre , communément appelé d20 ). C'est votre tâche de lancer un tel dé. Cependant, si vous retourniez simplement un nombre aléatoire entre 1 et 20, ce serait un peu trivial. Votre tâche consiste donc à générer un filet aléatoire pour un dé donné.
Nous utiliserons le filet suivant:
C'est une bande triangulaire, elle peut donc être facilement représentée sous forme de liste d'entiers. Par exemple, si vous recevez l'entrée:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
Cela correspondrait au dé suivant (fait amusant: il s'agit du filet utilisé par Magic: les compteurs de vie Gathering / dés dés).
Cependant, ce n'est pas le seul filet représentant ce dé. Selon la façon dont nous déroulons les visages, il existe 60 filets différents. En voici deux autres:
[1, 8, 9, 10, 2, 3, 4, 5, 6, 7, 17, 18, 19, 11, 12, 13, 14, 15, 16, 20]
[10, 9, 18, 19, 11, 12, 3, 2, 1, 8, 7, 17, 16, 20, 13, 14, 4, 5, 6, 15]
Ou graphiquement (je n'ai pas fait pivoter les étiquettes des visages pour plus de simplicité):
Le défi
Etant donné une liste d'entiers représentant un dé (comme décrit ci-dessus) et un entier N
, sortir N
indépendamment, des réseaux d20 uniformément aléatoires correspondant au dé donné. (Autrement dit, chacun des 60 réseaux possibles devrait avoir la même probabilité d'être généré.)
Bien sûr, en raison des limites techniques des PRNG, une parfaite uniformité sera impossible. Aux fins d'évaluer l'uniformité de votre soumission, les opérations suivantes seront considérées comme produisant des distributions parfaitement uniformes:
- Obtention d'un numéro d'un PRNG (sur n'importe quelle plage), qui est documenté comme étant (approximativement) uniforme.
- Mapper une distribution uniforme sur un ensemble de nombres plus grand sur un ensemble plus petit via modulo ou multiplication (ou une autre opération qui distribue les valeurs uniformément). L'ensemble plus grand doit contenir au moins 1024 fois autant de valeurs possibles que l'ensemble plus petit.
Compte tenu de ces hypothèses, votre algorithme doit produire une distribution parfaitement uniforme.
Votre programme devrait être capable de générer 100 réseaux en moins d'une seconde (alors n'essayez pas de générer des réseaux aléatoires jusqu'à ce qu'un corresponde au dé donné ci-dessus).
Vous pouvez écrire un programme ou une fonction, en prenant une entrée via STDIN (ou l'alternative la plus proche), un argument de ligne de commande ou un argument de fonction et en sortant le résultat via STDOUT (ou l'alternative la plus proche), la valeur de retour de la fonction ou le paramètre de la fonction (out).
L'entrée et la sortie peuvent être dans n'importe quel format de liste plat pratique et sans ambiguïté. Vous pouvez supposer que les valeurs faciales du d20 sont des entiers positifs distincts, qui correspondent au type d'entier naturel de votre langue.
Il s'agit du code golf, donc la soumission la plus courte (en octets) l'emporte. Et bien sûr, la soumission la plus courte par utilisateur entrera également dans le classement général de la série.
Exemples de sorties
Pour l'entrée
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
Les 60 filets possibles (à condition que je ne me sois pas trompé), sans ordre particulier, sont:
[11, 10, 9, 18, 19, 20, 13, 12, 3, 2, 1, 8, 7, 17, 16, 15, 14, 4, 5, 6]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
[8, 7, 17, 18, 9, 10, 2, 1, 5, 6, 15, 16, 20, 19, 11, 12, 3, 4, 14, 13]
[3, 12, 13, 14, 4, 5, 1, 2, 10, 11, 19, 20, 16, 15, 6, 7, 8, 9, 18, 17]
[3, 4, 5, 1, 2, 10, 11, 12, 13, 14, 15, 6, 7, 8, 9, 18, 19, 20, 16, 17]
[11, 19, 20, 13, 12, 3, 2, 10, 9, 18, 17, 16, 15, 14, 4, 5, 1, 8, 7, 6]
[4, 14, 15, 6, 5, 1, 2, 3, 12, 13, 20, 16, 17, 7, 8, 9, 10, 11, 19, 18]
[2, 10, 11, 12, 3, 4, 5, 1, 8, 9, 18, 19, 20, 13, 14, 15, 6, 7, 17, 16]
[4, 5, 1, 2, 3, 12, 13, 14, 15, 6, 7, 8, 9, 10, 11, 19, 20, 16, 17, 18]
[10, 2, 1, 8, 9, 18, 19, 11, 12, 3, 4, 5, 6, 7, 17, 16, 20, 13, 14, 15]
[3, 2, 10, 11, 12, 13, 14, 4, 5, 1, 8, 9, 18, 19, 20, 16, 15, 6, 7, 17]
[7, 8, 1, 5, 6, 15, 16, 17, 18, 9, 10, 2, 3, 4, 14, 13, 20, 19, 11, 12]
[13, 12, 11, 19, 20, 16, 15, 14, 4, 3, 2, 10, 9, 18, 17, 7, 6, 5, 1, 8]
[16, 15, 14, 13, 20, 19, 18, 17, 7, 6, 5, 4, 3, 12, 11, 10, 9, 8, 1, 2]
[15, 16, 17, 7, 6, 5, 4, 14, 13, 20, 19, 18, 9, 8, 1, 2, 3, 12, 11, 10]
[20, 13, 12, 11, 19, 18, 17, 16, 15, 14, 4, 3, 2, 10, 9, 8, 7, 6, 5, 1]
[5, 4, 14, 15, 6, 7, 8, 1, 2, 3, 12, 13, 20, 16, 17, 18, 9, 10, 11, 19]
[10, 11, 12, 3, 2, 1, 8, 9, 18, 19, 20, 13, 14, 4, 5, 6, 7, 17, 16, 15]
[4, 3, 12, 13, 14, 15, 6, 5, 1, 2, 10, 11, 19, 20, 16, 17, 7, 8, 9, 18]
[19, 20, 13, 12, 11, 10, 9, 18, 17, 16, 15, 14, 4, 3, 2, 1, 8, 7, 6, 5]
[1, 8, 9, 10, 2, 3, 4, 5, 6, 7, 17, 18, 19, 11, 12, 13, 14, 15, 16, 20]
[8, 1, 5, 6, 7, 17, 18, 9, 10, 2, 3, 4, 14, 15, 16, 20, 19, 11, 12, 13]
[18, 9, 8, 7, 17, 16, 20, 19, 11, 10, 2, 1, 5, 6, 15, 14, 13, 12, 3, 4]
[12, 3, 2, 10, 11, 19, 20, 13, 14, 4, 5, 1, 8, 9, 18, 17, 16, 15, 6, 7]
[2, 3, 4, 5, 1, 8, 9, 10, 11, 12, 13, 14, 15, 6, 7, 17, 18, 19, 20, 16]
[10, 9, 18, 19, 11, 12, 3, 2, 1, 8, 7, 17, 16, 20, 13, 14, 4, 5, 6, 15]
[9, 8, 7, 17, 18, 19, 11, 10, 2, 1, 5, 6, 15, 16, 20, 13, 12, 3, 4, 14]
[16, 17, 7, 6, 15, 14, 13, 20, 19, 18, 9, 8, 1, 5, 4, 3, 12, 11, 10, 2]
[17, 7, 6, 15, 16, 20, 19, 18, 9, 8, 1, 5, 4, 14, 13, 12, 11, 10, 2, 3]
[1, 5, 6, 7, 8, 9, 10, 2, 3, 4, 14, 15, 16, 17, 18, 19, 11, 12, 13, 20]
[9, 18, 19, 11, 10, 2, 1, 8, 7, 17, 16, 20, 13, 12, 3, 4, 5, 6, 15, 14]
[16, 20, 19, 18, 17, 7, 6, 15, 14, 13, 12, 11, 10, 9, 8, 1, 5, 4, 3, 2]
[5, 1, 2, 3, 4, 14, 15, 6, 7, 8, 9, 10, 11, 12, 13, 20, 16, 17, 18, 19]
[8, 9, 10, 2, 1, 5, 6, 7, 17, 18, 19, 11, 12, 3, 4, 14, 15, 16, 20, 13]
[13, 20, 16, 15, 14, 4, 3, 12, 11, 19, 18, 17, 7, 6, 5, 1, 2, 10, 9, 8]
[6, 15, 16, 17, 7, 8, 1, 5, 4, 14, 13, 20, 19, 18, 9, 10, 2, 3, 12, 11]
[6, 5, 4, 14, 15, 16, 17, 7, 8, 1, 2, 3, 12, 13, 20, 19, 18, 9, 10, 11]
[7, 6, 15, 16, 17, 18, 9, 8, 1, 5, 4, 14, 13, 20, 19, 11, 10, 2, 3, 12]
[19, 18, 17, 16, 20, 13, 12, 11, 10, 9, 8, 7, 6, 15, 14, 4, 3, 2, 1, 5]
[14, 15, 6, 5, 4, 3, 12, 13, 20, 16, 17, 7, 8, 1, 2, 10, 11, 19, 18, 9]
[17, 18, 9, 8, 7, 6, 15, 16, 20, 19, 11, 10, 2, 1, 5, 4, 14, 13, 12, 3]
[6, 7, 8, 1, 5, 4, 14, 15, 16, 17, 18, 9, 10, 2, 3, 12, 13, 20, 19, 11]
[14, 13, 20, 16, 15, 6, 5, 4, 3, 12, 11, 19, 18, 17, 7, 8, 1, 2, 10, 9]
[20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
[7, 17, 18, 9, 8, 1, 5, 6, 15, 16, 20, 19, 11, 10, 2, 3, 4, 14, 13, 12]
[15, 6, 5, 4, 14, 13, 20, 16, 17, 7, 8, 1, 2, 3, 12, 11, 19, 18, 9, 10]
[9, 10, 2, 1, 8, 7, 17, 18, 19, 11, 12, 3, 4, 5, 6, 15, 16, 20, 13, 14]
[2, 1, 8, 9, 10, 11, 12, 3, 4, 5, 6, 7, 17, 18, 19, 20, 13, 14, 15, 16]
[12, 13, 14, 4, 3, 2, 10, 11, 19, 20, 16, 15, 6, 5, 1, 8, 9, 18, 17, 7]
[17, 16, 20, 19, 18, 9, 8, 7, 6, 15, 14, 13, 12, 11, 10, 2, 1, 5, 4, 3]
[18, 17, 16, 20, 19, 11, 10, 9, 8, 7, 6, 15, 14, 13, 12, 3, 2, 1, 5, 4]
[18, 19, 11, 10, 9, 8, 7, 17, 16, 20, 13, 12, 3, 2, 1, 5, 6, 15, 14, 4]
[11, 12, 3, 2, 10, 9, 18, 19, 20, 13, 14, 4, 5, 1, 8, 7, 17, 16, 15, 6]
[15, 14, 13, 20, 16, 17, 7, 6, 5, 4, 3, 12, 11, 19, 18, 9, 8, 1, 2, 10]
[19, 11, 10, 9, 18, 17, 16, 20, 13, 12, 3, 2, 1, 8, 7, 6, 15, 14, 4, 5]
[12, 11, 19, 20, 13, 14, 4, 3, 2, 10, 9, 18, 17, 16, 15, 6, 5, 1, 8, 7]
[20, 16, 15, 14, 13, 12, 11, 19, 18, 17, 7, 6, 5, 4, 3, 2, 10, 9, 8, 1]
[13, 14, 4, 3, 12, 11, 19, 20, 16, 15, 6, 5, 1, 2, 10, 9, 18, 17, 7, 8]
[5, 6, 7, 8, 1, 2, 3, 4, 14, 15, 16, 17, 18, 9, 10, 11, 12, 13, 20, 19]
[14, 4, 3, 12, 13, 20, 16, 15, 6, 5, 1, 2, 10, 11, 19, 18, 17, 7, 8, 9]
Pour tout autre réseau, remplacez simplement chaque occurrence de i
par le i
numéro e dans l'entrée (où i
est basé sur 1).
Défis liés
Classement
Le premier post de la série génère un classement.
Pour vous assurer que vos réponses s'affichent, veuillez commencer chaque réponse par un titre, en utilisant le modèle Markdown suivant:
## Language Name, N bytes
où N
est la taille de votre soumission. Si vous améliorez votre score, vous pouvez conserver les anciens scores dans le titre, en les barrant. Par exemple:
## Ruby, <s>104</s> <s>101</s> 96 bytes
(La langue n'est pas actuellement affichée, mais l'extrait de code l'exige et l'analyse, et je pourrai ajouter un classement par langue à l'avenir.)
la source
Réponses:
Ruby, 160 octets (rév B)
17 octets économisés grâce aux suggestions de Martin Büttner.
Ruby, 177 octets (rév A)
Explication
Il est possible de générer toutes les orientations possibles par des rotations autour d'une face (3 fois), d'un sommet (5 fois) et de deux bords (2 fois). Mais pas n'importe quel visage et bords. Les axes doivent avoir la bonne relation et les rotations doivent être effectuées dans le bon ordre, sinon des choses étranges peuvent se produire.
C'est ainsi que je l'ai fait (même si je comprends que Martin l'a fait différemment.)
Toutes les orientations d'un tétraèdre peuvent être générées par des combinaisons des trois opérations de symétrie suivantes:
a) Rotation autour de deux axes 2 fois à droite à travers les points médians des bords (ceux-ci sont à angle droit l'un par rapport à l'autre. Si nous les multiplions ensemble, nous découvrons un troisième axe 2 fois à travers la paire restante d'arêtes.)
b) Rotation autour d'un axe 3 fois diagonal aux axes 2 fois, passant par un sommet et une face.
La symétrie de l'icosaèdre est un sur-ensemble de celle du tétraèdre. Dans l'image ci-dessous de https://en.wikipedia.org/wiki/Icosaèdre , les faces jaunes et rouges définissent deux tétraèdres différents (ou alternativement un seul octaèdre), tandis que les bords communs à deux faces bleues sont en trois paires à angles droits (et se trouvent sur les faces d'un cube.)
Toutes les orientations de l'icosaèdre peuvent être générées par les opérations de symétrie mentionnées ci-dessus plus une opération supplémentaire de 5 fois.
Les rotations d'environ trois des quatre axes mentionnés ci-dessus sont représentées par les cordes magiques entre les
''
marques. La rotation autour du deuxième axe double est différente et peut être effectuée simplement en inversant le réseaua[]
.Non testé dans le programme de test:
Solution alternative 131 octets (invalide en raison de l'approche de marche aléatoire binaire, ne donne qu'une distribution approximativement correcte.)
Ceci est un brouillage (un peu comme les programmes utilisés pour brouiller le cube de rubik.)
Les rotations spécifiques que j'utilise sont deux des plus évidentes:
-Une rotation de 120 degrés (autour des faces 1 et 20 selon le premier diagramme)
-Une rotation de 72 degrés (autour des sommets communs à 1,2,3,4,5 et 16,17,18,19,20 selon le premier diagramme.)
nous retournons une pièce 99 fois, et chaque fois que nous effectuons l'une de ces deux rotations selon qu'il s'agit de têtes ou de queues.
Notez que l'alternance de ces éléments conduit à des séquences assez courtes. Par exemple, avec les bons sens de rotation, une rotation de 180 degrés peut être produite avec une période de seulement 2.
la source
b.map
ne fonctionne pas directement, je doisb.chars.map
le faire fonctionner (BTW qui ne fonctionne pas sur ma machine car j'ai Ruby 1.9.3 mais il fonctionne sur Ideone.) C'est une bonne économie. Je ne pense pas que changer les chaînes magiques pour les caractères non imprimables pour enregistrer la-64
volonté fonctionnera:%w{}
interprète\n
(ainsi que l'espace) comme séparateur entre les chaînes dans le tableau généré. Je n'ai aucune idée de ce qu'il fera avec les autres caractères ASCII non imprimables.Code machine IA-32, 118 octets
Hexdump:
C'est un peu long, donc certaines explications vont d'abord. Je presque le même algorithme que l'actuel réponse par niveau de la rivière St . Pour rendre ma réponse différente, j'ai pris d'autres permutations de base, qui n'ont pas nécessairement une signification géométrique intuitive, mais qui sont en quelque sorte plus pratiques.
Le code doit essentiellement générer une permutation, qui est une application séquentielle des éléments suivants:
p3
, appliquée 0 ... 2 foisq2
, appliquée 0 ou 1 foisp5
, appliquée 0 ... 4 foisp2
, appliquée 0 ou 1 foisIl existe de nombreux choix possibles pour ces permutations. L'un d'eux est le suivant:
Ce choix est meilleur que d'autres parce que les permutations ici ont de longues séries d'index séquentiels, qui peuvent être compressées par un codage de longueur d'exécution - seulement 29 octets pour les 4 permutations.
Pour simplifier la génération de nombres aléatoires, j'ai choisi les puissances (combien de fois chaque permutation est appliquée) dans la plage 1 ... 30 pour chacune d'elles. Cela entraîne beaucoup de travail supplémentaire dans le code, car par exemple
p3
devient une permutation d'identité à chaque fois qu'il est multiplié par lui-même 3 fois. Cependant, le code est plus petit de cette façon et tant que la plage est divisible par 30, la sortie aura une distribution uniforme.De plus, les puissances doivent être positives pour que l'opération de décodage de longueur soit effectuée au moins une fois.
Le code a 4 boucles imbriquées; le contour est comme ceci:
J'espère que ce pseudo-code est plus clair que le code d'assemblage en ligne ci-dessous.
Quelques détails d'implémentation amusants:
call
et ensuitepop
pour accéder aux données (permutations codées) stockées dans le codejecxz
instruction me permet commodément d'utiliser un octet zéro comme terminaison pour le processus de décodage de longueurPar chance, le nombre 30 (2 * 3 * 5) est presque une puissance de 2. Cela me permet d'utiliser un code court pour générer un nombre compris entre 1 et 30:
J'utilise une instruction "division à usage général" (
aam
) pour séparer un octet en champs de bits (longueur 3 bits et index 5 bits); par chance, à cette position dans le codecl = 0
, donc je profite des deux "côtés" dexchg
la source