Amusez-vous avec des chaînes et des chiffres

13

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:

  1. Le nombre total de toute chaîne doit être exactement égal à son nombre correspondant dans les données d'entrée.

  2. 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.

  3. 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.

  4. 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 , donc le code le plus court en octets pour chaque langue gagne!

Stupid_Intern
la source
Beau défi! Je pense que c'est un peu sous-spécifié par nos normes. Je recommande fortement l'utilisation de The Sandbox pour obtenir beaucoup de commentaires avant de poster un défi afin de ne pas obtenir de votes négatifs ou de votes serrés! :-) J'ai hâte de voir de nouveaux défis de votre part!
Giuseppe
@Giuseppe merci, je vais essayer de passer par là. Faites-moi savoir si j'ai besoin d'ajouter des détails si j'ai raté celui-ci.
Stupid_Intern
1
Peut-on prendre 2 entrées, juste les chaînes et juste les chiffres?
FrownyFrog
il peut y avoir une ambiguïté dans l'utilisation de l'expression «aléatoire», plusieurs de ces solutions utilisent des bibliothèques «aléatoires» qui ne sont en fait que pseudo-aléatoires.
don bright

Réponses:

6

Gelée , 11 octets

Œṙ'Œ!⁻ƝẠ$ƇX

Essayez-le en ligne!

Œṙ'Œ!⁻ƝẠ$ƇX Arguments: z
  '         Flat: Apply link directly to x, ignoring its left and right depth properties
Œṙ            Run-length decode
   Œ!       Permutations of x
         Ƈ  Filter; keep elements of x for which the link returns a truthy result
        $     ≥2-link monadic chain
      Ɲ         Apply link on overlapping pairs (non-wrapping)
     ⁻            x != y
       Ạ        Check if all elements of x have a truthy value (+vacuous truth)
          X Pick a random element of x; return 0 if the list is empty.
Erik le Outgolfer
la source
S'il Œṙne vectorise pas, cela fonctionnerait sans'
dylnan
5

Gelée , 17 octets

Wẋ¥Ɲ€ẎẎŒ!Œɠ’SƊÐḟX

Essayez-le en ligne!

HyperNeutrino
la source
Quand j'essaye, ["A", 100], ["B", 3]il ne produit rien, il est bloqué, je pense.
Stupid_Intern
1
@newguy Générer toutes les permutations de 103 éléments n'est pas célèbre pour sa vitesse. Pour référence, le résultat suivant Œ!aura 990290071648618040754671525458177334909016582211449248300528055469987666584162228321414410738835384926535163859772920932228821344151498915840000000000000000000000000000 éléments.
Erik the Outgolfer
@newguy Cette solution est 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
HyperNeutrino
Pourrait Œṙaider?
Arnauld
1
@dylnan Je ne pense pas que cela fonctionne pour les chaînes avec lesquelles j'ai essayé ["AT", 3], ["B", 3]et que j'ai obtenues TBATATBABcomme sortie incorrecte
Stupid_Intern
5

Python 2 , 114 189 185 185 174 octets

from random import*
a=input()
s=u=[]
while a:x,y=a.pop(a.index(next((w for w in a if w[1]>sum(v[1]for v in a+u)/2),choice(a))));s=s+[x];a+=u;u=[[x,y-1]]*(y>1)
print[s,0][y>1]

Essayez-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 nombre navec 2*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 nombre navec 2*n=t+1nous 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.

Chas Brown
la source
1
@Arnauld: complètement raté ça! réparé maintenant.
Chas Brown
4

R , 148 141 octets

function(x,y,p=combinatXXpermn(rep(seq(y),y)),q=which(sapply(lapply(p,diff),all)))"if"(n<-sum(q|1),"if"(n-1,x[p[[sample(q,1)]]],x[p[[q]]]),0)

Essayez-le en ligne! (J'ai copié combinat::permnet appelé là- combinatXXpermnbas.)

Solution de force brute O (n!).

Utilise à permnpartir du combinatpackage pour générer toutes les commandes possibles. Vérifie ensuite si certains suivent les règles et en choisit un au hasard.

ngm
la source
n<-sum(n|1)est un octet plus court je crois. Mais la bizarrerie d' sampleune entrée de longueur un est assez frustrante ici.
Giuseppe
golfez-le un peu aussi, essayez-le ici - j'ai dû retirer le combinatXXpermn de l'en-tête pour obtenir le lien assez petit ...
Giuseppe
J'ai eu quelque chose de très similaire en prenant une entrée en tant que trame de données. Le problème avec bruteforce est qu'il ne gérera pas les entrées qui sont trop grandes ...
JayCe
@JayCe est-il même un algorithme de force non brute, étant donné la règle 3 de ce défi?
ngm
Je suis d'accord que non. Cela aurait été plus intéressant sans la règle 3.
JayCe
3

JavaScript, 112 octets

Première passe à cela, plus de golf à suivre (espérons-le).

f=([i,...a],o=[])=>a.sort((x,y)=>(y[1]-x[1])*Math.random()-n*.5,n=--i[1],o.push(i[0]))+a?f(n?[...a,i]:a,o):n?0:o

Essayez-le en ligne

Hirsute
la source
1
Merci, @Arnauld, je l'avais manqué. J'aurais dû vérifier la spécification plutôt que de suivre aveuglément l'exemple de Chas. Implémenté une solution rapide, devra y revenir plus tard pour voir si je peux mieux jouer au golf.
Shaggy
Oui, la 3ème règle est correcte pour les esolangs qui peuvent de toute façon forcer brutalement toutes les solutions, mais cela rend assez difficile la mise en œuvre d'algorithmes plus courts dans d'autres langues ... BTW: cela semble maintenant retourner 0 sur les entrées valides de temps en temps.
Arnauld
Implémentation d'un autre correctif rapide, @Arnauld - si cela ne le trie pas, je devrai le supprimer à nouveau jusqu'à ce que j'aie plus de temps pour l'examiner. Remarque: J'ai pris la spécification au mot que la chaîne suivante doit être choisie au hasard, ce qui implique que la première sélection n'a pas besoin d'être aléatoire.
Shaggy
1
@Shaggy - Je suis d'accord, vous ne devriez jamais suivre aveuglément tout ce que je fais! :)
Chas Brown
3

J, 60 53 octets

-7 grâce à FrownyFrog

(?@#{])@(#~*/@(2~:/\])"1)@(]i.@!@#@;A.;) ::0(#~>)/&.>

original

(?@#{])@(#~2&([:*/~:/\)"1)@(A.~i.@!@#)@;@:(([#~>@])/&.>) ::0

non golfé

(?@# { ])@(#~ 2&([: */ ~:/\)"1)@(A.~ i.@!@#)@;@:(([ #~ >@])/&.>) ::0

Suggestions d'amélioration bienvenues.

Essayez-le en ligne!

Jonas
la source
Joué à 53
FrownyFrog
génial tyvm @FrownyFrog, je mettrai à jour le post plus tard
Jonah
oups, [:*/2~:/\|:est deux plus court
FrownyFrog
2

JavaScript (ES6), 160 octets

a=>(g=(a,m=[])=>a.map((v,n)=>v==m[0]||g(a.filter(_=>n--),[v,...m]))>[]?0:r=m)(a.reduce((p,[v,n])=>[...p,...Array(n).fill(v)],r=[]).sort(_=>Math.random()-.5))||r

Essayez-le en ligne!

Arnauld
la source
2

Fusain , 38 octets

WΦθ§κ¹«≔‽Φ∨Φι›⊗§κ¹ΣEι§μ¹ι¬⁼κυυ§υ⁰⊞υ⊖⊟υ

Essayez-le en ligne! Le lien est vers la version détaillée du code. Explication:

WΦθ§κ¹«

Répétez pendant qu'il y a au moins un compte différent de zéro.

Φι›⊗§κ¹ΣEι§μ¹

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.

Neil
la source
Cela produit des sorties non valides, comme dans votre exemple avec ["h4x0r", 1337]inclus comme chaîne.
ngm
@ngm J'ai réorganisé le code et il se bloque maintenant si vous le faites ... une validation correcte va malheureusement coûter plus d'octets.
Neil
2

Rubis , 85 octets

L'approche par force brute (merci Jonah pour l'idée).

->l{l.flat_map{|a,b|[a]*b}.permutation.select{|p|r=0;p.all?{|a|a!=r&&r=a}}.sample||0}

Essayez-le en ligne!

Ruby , 108100 96 octets

Auparavant, l'approche Bogosort

->l{w=[];l.map{|a,b|w+=[a]*b;b}.max*2>w.size+1?0:(w.shuffle!until(r='';w.all?{|a|a!=r&&r=a});w)}

Essayez-le en ligne!

GB
la source
en voici un pour 93: Essayez-le en ligne!
Jonah
2

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:

extern crate regex;
struct P {s:String,x:i32,v:i32}
fn main() {
    let (mut i,mut j,mut p,mut s)=(0,0,Vec::new(),String::new());
    std::io::stdin().read_line(&mut s);
    for c in regex::Regex::new(r"([A-Z]+),(\d+)").unwrap().captures_iter(&s) {
        for _j in 0..c[2].parse().unwrap() {p.push(P{s:c[1].to_string(),x:i,v:0});i+=1;}
    }
    let l=p.len(); while i>1 {
        j+=1;i=1;p.sort_by_key(|k| k.x);
        for m in 0..l {
            let n=(m+1)%l;
            if p[m].s==p[n].s {p[m].v=p[m].x;if n!=0 {i=2}} else {p[m].v=1}
            p[m].x=(p[m].x+p[m].v)%l as i32;
        }
        if j>l*l{p.truncate(1);p[0].s="0".to_string();i=1}
    }
    for k in &p{print!("{}",k.s)};println!();
}
Don Bright
la source
C'est une façon intéressante de penser à ce problème, j'aime ça. Comment cela fonctionne-t-il dans la pratique? J'ai l'impressionl2la limite peut être trop basse, qu'il peut y avoir trop de faux négatifs où l'algorithme pense qu'il n'y a pas de sortie valide quand il y en a - mais je n'ai pas pu tester cette théorie car TIO n'a apparemment pas la regexcaisse.
sundar
il a passé les exemples que je lui ai donnés, même si je ne l'ai pas flou. je l'ai modifié pour fonctionner dans TIO, vous devez modifier le 'let s = [("A", 3), ("B", 2), ("ZZ", 4)];' line, bit.ly/2LubonO
don bright
1

JavaScript (Node.js) , 249 octets

l=>(a=[],g=(r,s)=>s.length?s.forEach((x,i)=>g([...r,x],s.filter((y,j)=>j-i))):a.push(r),g([],l.reduce(((a,x)=>[...a, ...(x[0]+' ').repeat(x[1]).split(' ')]),[]).filter(x=>x)),p=a.filter(a=>a.every((x,i)=>x!=a[i+1])),p[~~(Math.random()*p.length)]||0)

Essayez-le en ligne!

WaffleCohn
la source
1

Java (JDK 10) , 191 octets

S->N->{var l=new java.util.Stack();int i=0,j;for(var s:S)for(j=N[i++];j-->0;)l.add(s);for(;i>0;){i=0;java.util.Collections.shuffle(l);for(var s:S)if(s.join("",l).contains(s+s))i++;}return l;}

Essayez-le en ligne!

Cela ne revient jamais s'il n'y a pas de solutions.

Olivier Grégoire
la source