Voici un puzzle de programmation pour vous:
À partir d'une liste de paires de chaînes et de numéros correspondants, par exemple [[A,37],[B,27],[C,21],[D,11],[E,10],[F,9],[G,3],[H,2]]
, affichez une autre liste qui contiendra uniquement les chaînes de la manière suivante:
Le nombre total de toute chaîne doit être exactement égal à son nombre correspondant dans les données d'entrée.
Aucune chaîne ne doit être répétée de manière adjacente dans la séquence, et chaque chaîne doit apparaître dans la liste de sortie.
La sélection de la chaîne suivante doit être effectuée de manière aléatoire tant qu'ils ne dépassent pas deux règles. Chaque solution doit avoir une probabilité non nulle d'être choisie.
Si aucune combinaison n'est possible, la sortie doit être juste
0
.
La liste d'entrée peut être donnée dans n'importe quel ordre (trié ou non trié) et les chaînes de la liste peuvent être de n'importe quelle longueur.
Exemple de sortie pour l'entrée d'échantillon ci-dessus 1
[A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,B,A,C,A,C,A,C,A,C,A,C,A,C,A,C,A,C,A,C,A,C,D,C,D,C,D,C,D,C,D,C,D,C,D,C,D,C,D,C,D,C,D,C,E,F,E,F,E,F,E,F,E,F,E,F,E,F,E,F,E,F,E,G,H,G,H,G]
Échantillon d'entrée 2:
[[A,6],[B,1],[C,1]]
Sortie pour la deuxième entrée:
0
car aucune liste n'est possible sur la base de règles.
Exemple d'entrée 3:
[[AC,3],[BD,2]]
sortie valide: [AC,BD,AC,BD,AC]
sortie invalide: [AC,BD,AC,AC,BD]
Si des éclaircissements supplémentaires sont nécessaires, n'hésitez pas à me le dire dans les commentaires et j'agirai rapidement en conséquence.
C'est le code-golf , donc le code le plus court en octets pour chaque langue gagne!
Réponses:
Gelée , 11 octets
Essayez-le en ligne!
la source
Œṙ
ne vectorise pas, cela fonctionnerait sans'
Gelée , 17 octets
Essayez-le en ligne!
la source
["A", 100], ["B", 3]
il ne produit rien, il est bloqué, je pense.Œ!
aura 990290071648618040754671525458177334909016582211449248300528055469987666584162228321414410738835384926535163859772920932228821344151498915840000000000000000000000000000 éléments.O(n!)
mais elle est courte et la vitesse n'a pas d'importance. N'essayez pas avec quoi que ce soit où les nombres totalisent plus de 6 à 8 environ: PŒṙ
aider?["AT", 3], ["B", 3]
et que j'ai obtenuesTBATATBAB
comme sortie incorrectePython 2 ,
114189185 185174 octetsEssayez-le en ligne!
Aie! Beaucoup plus difficile avec la règle 3 ... :). Toujours en essayant d'éviter l'
O(n!)
approche, il peut donc gérer tous les cas de test quelque temps avant la mort par la chaleur de l'univers ...Algorithme: supposons que la somme totale du nombre de chaînes soit
t
. Si une chaîne a un nombren
avec2*n>t+1
, alors il n'est pas possible de satisfaire les contraintes. Par conséquent, si une chaîne (hors précédemment élu) a le nombren
avec2*n=t+1
nous faut donc choisir cette chaîne suivante. Sinon, nous pouvons choisir au hasard n'importe quelle chaîne qui n'est pas la chaîne précédemment choisie.la source
R ,
148141 octetsEssayez-le en ligne! (J'ai copié
combinat::permn
et appelé là-combinatXXpermn
bas.)Solution de force brute O (n!).
Utilise à
permn
partir ducombinat
package pour générer toutes les commandes possibles. Vérifie ensuite si certains suivent les règles et en choisit un au hasard.la source
n<-sum(n|1)
est un octet plus court je crois. Mais la bizarrerie d'sample
une entrée de longueur un est assez frustrante ici.JavaScript, 112 octets
Première passe à cela, plus de golf à suivre (espérons-le).
Essayez-le en ligne
la source
J,
6053 octets-7 grâce à FrownyFrog
original
non golfé
Suggestions d'amélioration bienvenues.
Essayez-le en ligne!
la source
[:*/2~:/\|:
est deux plus courtJavaScript (ES6), 160 octets
Essayez-le en ligne!
la source
Fusain , 38 octets
Essayez-le en ligne! Le lien est vers la version détaillée du code. Explication:
Répétez pendant qu'il y a au moins un compte différent de zéro.
Trouvez tout nombre qui représente plus de la moitié du reste.
S'il n'y en avait pas, prenez simplement les nombres non nuls filtrés plus tôt.
Filtrez la chaîne qui a été sortie la dernière fois.
Attribuez un élément aléatoire de la première liste non vide des deux listes ci-dessus à la dernière chaîne de sortie. Notez que si une combinaison impossible est entrée, le programme se bloque à ce stade.
Imprimez la chaîne.
Décrémenter son compte.
la source
["h4x0r", 1337]
inclus comme chaîne.Rubis , 85 octets
L'approche par force brute (merci Jonah pour l'idée).
Essayez-le en ligne!
Ruby ,
10810096 octetsAuparavant, l'approche Bogosort
Essayez-le en ligne!
la source
Rouille 633 octets
Ce qui le rend un peu différent des autres, c'est qu'il a commencé avec l'idée de réorganiser les cordes en simulant un système physique. Chaque chaîne est d'abord dupliquée le nombre approprié de fois. Ensuite, chaque chaîne individuelle est traitée comme une particule dans un espace. Deux particules avec la même valeur de chaîne "se repoussent", tandis que deux particules avec des valeurs différentes s'attirent. Par exemple, si nous commençons par AAAAAAABBBBCC, les As vont s'abroger les uns les autres, s'éloignant les uns des autres, permettant aux Bs de se déplacer entre eux. Au fil du temps, cela atteint un joli mélange de particules. Après chaque itération de `` mouvement de particules '', le programme vérifie qu'aucune même particule n'est adjacente, puis s'arrête et imprime l'état du système, qui est simplement la liste des chaînes dans l'ordre, telles qu'elles apparaissent dans l'espace 1 dimensionnel.
Maintenant, quand il s'agit de mettre en œuvre ce système physique, il a commencé par utiliser l'ancienne technique de démo / jeu PC pour stocker chaque position et vitesse des particules sous forme de nombres, puis passer par des itérations pour mettre à jour la position et la vitesse. À chaque itération, nous ajoutons de la vitesse à la position (mouvement) et ajoutons de l'accélération à la vitesse (changement de la vitesse de mouvement) et calculons l'accélération (trouvant la force sur la particule). Pour simplifier, le système ne calcule pas la force sur chaque particule sur la base de toutes les autres particules - il vérifie uniquement les particules immédiatement adjacentes. Il y avait également un effet d'amortissement pour que les particules n'accélèrent pas trop et ne s'envolent pas à l'infini (la vitesse est réduite de x% à chaque pas, par exemple).
Grâce au processus de golf, cependant, tout cela a été réduit et simplifié de manière drastique. Maintenant, au lieu de deux particules semblables se repoussant, elles se «téléportent» simplement. Différentes particules «scootent» un tout petit peu pour éviter la stagnation dans le système. Par exemple, si A est à côté de A, il se téléportera. Si A est à côté de B, il ne se déplacera que légèrement. Ensuite, il vérifie si les conditions sont remplies (pas de particules similaires adjacentes) et imprime les chaînes dans l'ordre, en fonction de leur position dans l'espace 1-d. Cela ressemble presque plus à un algorithme de tri qu'à une simulation - là encore, on pourrait voir les algorithmes de tri comme une forme de «dérive» simulée basée sur la «masse». Je digresse.
Quoi qu'il en soit, c'est l'un de mes premiers programmes Rust, j'ai donc abandonné après plusieurs heures de golf, bien qu'il puisse y avoir encore des opportunités. Le bit d'analyse est difficile pour moi. Il lit la chaîne d'entrée à partir de l'entrée standard. Si vous le souhaitez, cela pourrait être remplacé par "let mut s =" [[A, 3], [B, 2]] ". Mais en ce moment, je fais écho [[A, 3], [B, 2]] | cargo run 'sur la ligne de commande.
Le calcul de l'arrêt est un peu un problème. Comment détecter si un état valide du système ne sera jamais atteint? Le premier plan était de détecter si l'état `` actuel '' avait déjà répété un ancien état, par exemple si ACCC passe à CACC, mais de retour à ACCC, nous savons que le programme ne se terminera jamais, car il n'est que pseudo-aléatoire. Il devrait ensuite abandonner et afficher 0 si cela se produisait. Cependant, cela semblait être une énorme quantité de code Rust, alors j'ai simplement décidé que s'il passe par un nombre élevé d'itérations, il est probablement bloqué et n'atteindra jamais un état stable, il affiche donc 0 et s'arrête. Combien? Le nombre de particules au carré.
Code:
la source
regex
caisse.JavaScript (Node.js) , 249 octets
Essayez-le en ligne!
la source
Java (JDK 10) , 191 octets
Essayez-le en ligne!
Cela ne revient jamais s'il n'y a pas de solutions.
la source