Ne vous répétez pas dans Rock-Paper-Scissors

26

Sur la rumeur que Codegolf aura un tournoi Rock-Paper-Scissors, vous vous penchez sur le sujet des mots sans carré . Un mot en lettres R, P, Sest sans carré si elle ne contient pas de séquence qui se répète deux fois. Autrement dit, le mot ne peut pas être écrit comme

a x x b

aet bsont des mots de toute longueur et xest un mot d' une longueur d' au moins un, tout en les lettres R, P, S.

Tâche

Ecrire un programme qui génère les sans carrés mots des lettres R, P, Sde la longueur noù le nombre 1 <= n <= 10est pris comme entrée.

Exemple

Par exemple, les mots sans carré de longueur 3 sont

RPR, RSR, RPS, RSP, SPS, SRS, SRP, SPR, PRP, PSP, PSR,PRS

et ceux de longueur 4 sont

RPRS, RPSR, RPSP, RSRP, RSPR, RSPS, PRPS, PRSR, PRSP, PSRP, PSRS, PSPR, SRPR, SRPS, SRSP, SPRP, SPRS,SPSR

et notez que par exemple SPSPou PRPRne sont pas sans carré

Règles

  • C'est le codegolf, le programme le plus court gagne, les failles standard sont fermées.
  • Vous pouvez imprimer les mots ou les créer en mémoire.
  • Votre programme peut être écrit en fonction.

Les références

Entrée Wikipedia sur les mots sans carré

Le nombre de mots ternaires sans carré de longueur donnée est en https://oeis.org/A006156

En relation: Mots ternaires sans carré de longueur arbitraire

mschauer
la source
4
Un cas de test pour n>3serait une bonne idée, car il y a eu une certaine confusion entre les caractères répétés et les séquences répétées.
Laikoni
Veuillez commenter le suivi prévu dans le bac à
mschauer
6
Je ne pense pas que la balise "en langage naturel" devrait s'appliquer ici
Leo
1
Ah, les "mots" se sont développés en "langage naturel", je les ai supprimés.
mschauer
1
Non, il contient le carré SP SP
mschauer

Réponses:

20

Rubis, 39 octets

->n{(?P*n..?S*n).grep_v /[^RPS]|(.+)\1/}

Cette fonction hilarante et inefficace génère toutes les chaînes de longueur N situées alphabétiquement entre N Ps et N Ss, puis filtre la grande majorité qui contient des caractères non RPS. La vérification réelle utilise juste un quadratfrei backreference Regexp: (.+)\1.

65 octets plus idiomatiques qui se terminent dans un délai raisonnable pour N = 10:

->n{%w[R P S].repeated_permutation(n).map(&:join).grep_v /(.+)\1/}

Edit: Sauvegardé un octet grâce à G B.

histocrate
la source
Vous n'avez pas besoin de parenthèses sur grep_v, juste un espace entre celui-ci et la barre oblique (économisez 1 octet)
GB
6
" hilarante inefficace " décrit probablement pas mal de réponses sur ce site.
Fund Monica's Lawsuit
10

Gelée , 15 14 octets

“RPS”ṗẆ;"f$$Ðḟ

Essayez-le en ligne!

Comment ça marche

“RPS”ṗẆ;"f$$Ðḟ  Main link. Argument: n

“RPS”ṗ          Cartesian power; yield all strings of length n over this alphabet.
            Ðḟ  Filterfalse; keep only strings for which the quicklink to the left 
                returns a falsy result.
           $      Monadic chain. Argument: s (string)
      Ẇ             Window; yield the array A of all substrings of s.
          $         Monadic chain. Argument: A
       ;"             Concatenate all strings in A with themselves.
         f            Filter; yield all results that belong to A as well.
Dennis
la source
7

Rétine , 28 octets

+%1`1
R$'¶$`P$'¶$`S
A`(.+)\1

Essayez-le en ligne!

Prend entrée en unaire .

Explication

+%1`1
R$'¶$`P$'¶$`S

Cela génère toutes les chaînes composées RPSde longueur n. Pour ce faire, nous remplaçons à plusieurs reprises la première 1de chaque ligne. Réfléchissons à la ligne que <1>, où <tout est en face du match et >est tout après le match (ils sont $`et $'respectivement dans la syntaxe de substitution regex, mais ceux regard moins intuitif). Nous remplaçons le 1par R>¶<P>¶<S, où sont les sauts de ligne. Ainsi , le résultat complet de cette substitution est en fait <R>¶<P>¶<S>, ce qui est trois exemplaires de la ligne, le 1remplacer par R, P, Srespectivement, dans chacun des trois exemplaires. Ce processus s'arrête une fois que tous les 1s ont été substitués.

A`(.+)\1

Enfin, nous rejetons simplement toutes les lignes contenant une répétition.

Martin Ender
la source
Je l' aurais remplacé à plusieurs reprises 1(.*)avec , $1R¶$1P¶$1Smais l'octet de comptage est le même.
Neil
6

Coque , 15 14 octets

-1 octet grâce à Zgarb!

fȯεfoE½QΠR"RPS

Essayez-le en ligne!

Construit toutes les séquences possibles de la bonne longueur et ne conserve que celles dont toutes les sous-chaînes (sauf la vide) sont composées de deux moitiés différentes.

Merde, je voulais vraiment battre Jelly ici.

Leo
la source
3
14 octets à nouer avec Jelly.
Zgarb
5

Java 8, 285 277 octets

import java.util.*;Set r=new HashSet();n->p("",((1<<3*n)+"").replaceAll(".","PRS"),n)void p(String p,String s,int n){int l=s.length(),i=0;if(l<1&&(s=p.substring(0,n)).equals(s.replaceAll("(.*)\\1","")))r.add(s);for(;i<l;p(p+s.charAt(i),s.substring(0,i)+s.substring(++i,l),n));}

Bien que Java soit presque toujours verbeux, dans ce cas, ce n'est certainement pas le bon langage pour un défi comme celui-ci. Générer des permutations avec des sous-chaînes est mauvais pour les performances et inefficace.

Peut certainement être joué au golf un peu plus, cependant.

-8 octets grâce à @Jakob .

Explication:

Essayez-le ici. (Les performances sont trop mauvaises pour les cas de test supérieurs à 3, mais cela fonctionne localement ..)

import java.util.*;   // Required import for Set and HashSet

Set r=new HashSet();  // Result-Set on class-level

n->                   // Method with integer parameter and no return-type
  p("",((1<<3*n)+"").replaceAll(".","PRS"),n)
                      //  Get all permutations and save them in the Set
                      // End of method (implicit / single-line return-statement)

void p(String p,String s,int n){
                      // Separated method with 2 String & int parameters and no return-type
  int l=s.length(),   //  The length of the second input-String
      i=0;            //  Index-integer, starting at 0
  if(l<1              //  If the length is 0,
     &&(s=p.substring(0,n)).equals(s.replaceAll("(.*)\\1","")))
                      //  and it doesn't contain a repeated part:
    r.add(s);         //   Add it to the result-Set
  for(;i<l;           //  Loop (2) from 0 to `l`
    p(                //   Recursive-call with:
      p+s.charAt(i),  //    Prefix-input + the character of the second input at index `i`
      s.substring(0,i)+s.substring(++i,l),
                      //    and the second input except for this character
      n)              //    and `n`
  );                  //  End of loop (2)
}                     // End of separated method
Kevin Cruijssen
la source
1
Que diriez - vous de cette lambda: n->p("",((1<<3*n)+"").replaceAll(".","PRS"),n). Aussi, pourquoi ne pas factoriser for(;i<1;p(...));à while(i<l)p(...);?
Jakob
@Jakob Merci. Et j'utilise toujours for(;...;)out of codegolfing-habbit pour être honnête. Dans le pire des cas, c'est le même nombre d'octets que while(...)dans le meilleur des cas, quelque chose peut être placé à l'intérieur de la boucle for pour économiser des octets. J'essaie donc de ne pas utiliser whiledu tout dans le golf de code, car cela ne profite jamais au décompte d'octets de toute façon. Soit il l'augmente, soit il reste le même, donc personnellement je ne me soucie pas de la meilleure lisibilité. ;)
Kevin Cruijssen
1
Oui, j'essaie toujours de rendre mon code de golf aussi lisible que possible à un nombre d'octets donné. Probablement une poursuite futile!
Jakob
Attendez, mon lambda fonctionne-t-il vraiment ici? J'étais un peu négligent ... Il génère une chaîne de n PRS séquences, alors que votre boucle d'origine en a généré une avec 2 ^ ( n -2) séquences.
Jakob
@Jakob nfois "PRS" est correct. Le mien générait plus car il économisait des octets (et diminuait les performances, mais qui s'en soucie avec codegolf). ;)
Kevin Cruijssen
4

Python 3 , 97 96 octets

f=lambda n:{c+s for c in'RPS'*n for s in f(n-1)or{''}if all(k-s.find(c+s[:k])for k in range(n))}

Renvoie un ensemble de chaînes.

Essayez-le en ligne!

Dennis
la source
4

Perl 5 , 37 octets

sub r{grep!/(.+)\1/,glob"{R,S,P}"x<>}

Essayez-le en ligne!

La fonction renvoie un tableau des chaînes libres carrées.

Expliqué:

Le globgénère toutes les combinaisons de R, S et P de longueur égale à l'entrée. L' grepinstruction filtre ceux qui ne sont pas sans carré.

Xcali
la source
Grande utilisation de l'expansion de l'accolade!
Dom Hastings
3

R , 97 octets

cat((x=unique(combn(rep(c('p','r','s'),n),n<-scan(),paste,collapse='')))[!grepl("(.+)\\1",x,,T)])

Essayez-le en ligne!

combn(rep(c('p','r','s'),n),n,paste,collapse='')calcule toutes les nchaînes -character avec p, r, smais il fait double emploi , malheureusement , beaucoup (*), donc nous uniquify, et prendre celles qui correspondent à l'expression rationnelle (.+)\1, en utilisant la correspondance de style perl, nous imprimer la liste résultante.

(*) techniquement, il génère toutes les combinaisons de 3nlettres p,r,srépétées 3 fois prises nà la fois, puis s'applique paste(..., collapse='')à chaque combinaison plutôt que de calculer 3^ndirectement les cordes, mais c'est plus golfique qu'un expand.grid(le vrai produit cartésien).

Giuseppe
la source
3

JavaScript (Firefox 30-57), 69 octets

f=n=>n?[for(x of f(n-1))for(y of'RPS')if(!/(.+)\1/.test(y+=x))y]:['']

Comme toutes les sous-chaînes de mots sans carré sont également sans carré, la vérification peut être effectuée de manière récursive.

Neil
la source
2

Haskell , 101 98 octets

f n=[x:r|x:r<-mapM(\_->"RPS")[1..n],[x]#r]
h#t@(x:r)=h/=take(length h)t&&(h++[x])#r&&[x]#r
h#t=1<3

Essayez-le en ligne!

Laikoni
la source
2

JavaScript (ES6), 93 octets

n=>[...Array(3**n)].map(g=(d=n,i)=>d?'RPS'[i%3]+g(d-1,i/3|0):'').filter(s=>!/(.+)\1/.test(s))

Convertit tous les entiers de 0 à 3ⁿ en base (rembourrée inversée) 3 en utilisant RPScomme chiffres et les filtre pour les mots sans carré.

Neil
la source
2

Julia, 88

f(n)=[filter(A->!ismatch.(r"(.+)\1",join(A)),Iterators.product(repeated("RPS",n)...))...]

Rien d'extraordinaire.

mschauer
la source
1

C # / LINQ, 169

Enumerable.Range(0,(int)Math.Pow(3,n)).Select(i=>string.Concat(Enumerable.Range(1,n).Select(p=>"PRS"[(i/(int)Math.Pow(3,n-p))%3]))).Where(s=>!Regex.IsMatch(s,@"(.+)\1"))

Il doit y avoir une meilleure façon de le faire :)

Jason Handby
la source
1

F #, 143

let f n=[1..n]|>List.fold(fun l _->List.collect(fun s->["R";"P";"S";]|>List.map((+)s))l)[""]|>Seq.filter(fun x->not(Regex.IsMatch(x,"(.+)\1")))
Jason Handby
la source
Belle réponse F #!
aloisdg dit Réintégrer Monica
1
Ce n'est pas la langue la plus compacte, mais bon, aucune excuse pour l'utiliser :)
Jason Handby
1
Je te sens . Cette langue est tellement agréable.
aloisdg dit Réintégrer Monica
1

k, 56 octets

f:{$[x;(,/"RPS",/:\:f x-1){x@&~~/'(2,y)#/:x}/1_!x;,""]}

L'absence de regex natif place k bien derrière la courbe pour une fois. Je suis allé avec une solution récursive, car les caractères pour l'implémenter ont été enregistrés par une vérification sans carré plus simple.

$[ test ; if-true ; if-false ]

est l'opérateur ternaire de k, ici nous faisons des choses intéressantes pour une longueur non nulle, et retournons une seule chaîne vide si on lui demande des mots de longueur nulle.

(,/"RPS",/:\:f x-1)

prend le produit cartésien de "RPS" et tous les mots n-1 sans carré. , /: \: joint chaque élément de la droite vers la gauche, donnant un tableau de longueur 3 de tableaux de longueur n. , / aplatit cela en un tableau de longueur 3n.

{x@&~~/'(2,y)#/:x}

prend les n premières lettres de chaque chaîne et les compare au deuxième n, puis réduit le tableau uniquement là où elles ne correspondent pas. Parce que nous savons que le résultat précédent est sans carré, seules les sous-chaînes commençant au premier caractère doivent être mises en correspondance - simplifier la vérification ici valait les caractères dépensés pour implémenter la récursivité. Finalement,

/1_!x

applique le lambda au jeu de résultats initial à sa gauche, en itérant sur chaque longueur de sous-chaîne de 1 à (longueur de mot) -1. ! x génère une liste de 0 à x-1, puis 1_ supprime le premier élément (puisque les sous-chaînes de longueur 0 correspondront toujours)

En sacrifiant quelques caractères, nous pouvons utiliser .zs pour faire référence à soi-même plutôt que de compter sur le nom de la fonction, et au lieu de vérifier les sous-chaînes jusqu'à la longueur n-1, vérifiez uniquement les performances du plancher (n / 2). Il trouve tous les 49 mots de longueur (dont il y a 5207706) en environ 120 secondes sur un 7700k, au-dessus de celui que je rencontre dans la limite de 4 Go de k 32 bits gratuit.

{$[x;(,/"RPS",/:\:.z.s x-1){x@&~~/'(2,y)#/:x}/1+!_x%2;,""]}
ostewart
la source
0

Python 2 , 99 octets

import re
f=lambda n:n and[c+s for c in'RPS'for s in f(n-1)if not re.search(r'(.+)(\1)',c+s)]or['']

Essayez-le en ligne!

Chas Brown
la source