Don't repeat yourself in Rock-Paper-Scissors

Question

Upon the rumor that Codegolf will have a Rock-Paper-Scissors tournament you look into the topic of square-free words. A word made of the letters R, P, S is square-free if it does not contain a sequence that repeats twice. That is to say, the word can not be written as

a x x b

where a and b are words of any length and x is a word of length at least one, all made of the letters R, P, S.

Task

Write a program that generates the square-free words of the letters R, P, S of length n where the number 1 <= n <= 10 is taken as input.

Example

For example the square-free words of length 3 are

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

and those of length 4 are

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

and note that for example SPSP or PRPR are not square-free

Rules

• This is codegolf, shortest program wins, standard loopholes are closed.
• You may print the words or create them in memory.
• Your program may be written as a function.

References

Wikipedia entry on square-free words

The number of square-free ternary words of given length are in https://oeis.org/A006156

Related: Arbitrary-Length Ternary Squarefree Words

Answer 1

Ruby, 39 bytes

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

This hilariously inefficient function generates all strings of length N that lie alphabetically between N Ps and N Ss, then filters out the vast majority that contain non-RPS characters. The actual squarefree check just uses a Regexp backreference: (.+)\1.

More idiomatic 65 bytes that finish in a reasonable amount of time for N=10:

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

Edit: Saved a byte thanks to G B.

Answer 2

Jelly, 15 14 bytes

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

Try it online!

How it works

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

Answer 3

Retina, 28 bytes

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

Try it online!

Takes input in unary.

Explanation

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

This generates all strings made up of RPS of length n. The way we do this is that we repeatedly replace the first 1 in each line. Let's think about the line as <1>, where < is everything in front of the match and > is everything after the match (they're $` and $' respectively in regex substitution syntax, but those look less intuitive). We replace the 1 with R>¶<P>¶<S, where ¶ are linefeeds. So the full result of this substitution is actually <R>¶<P>¶<S>, which is three copies of the line, with the 1 replace with R, P, S, respectively, in each of the three copies. This process stops once all 1s have substituted.

A`(.+)\1

Finally, we simply discard all lines that contain a repetition.

Answer 4

Mathematica, 61 bytes

""<>#&/@{"R","P","S"}~Tuples~#~DeleteCases~{___,x__,x__,___}&

Try it online!

Answer 5

Husk, 15 14 bytes

-1 byte thanks to Zgarb!

fȯεfoE½QΠR"RPS

Try it online!

Builds all possible sequences of the correct length and keeps only the ones whose all substrings (except the empty one) are composed by two different halves.

Damn, I really wanted to beat Jelly here.

Answer 6

Java 8, 285 277 bytes

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));}

Although Java is almost always verbose, in this case it's definitely not the right language for a challenge like this. Generating permutations with substrings is bad for performance and inefficient.

Can definitely be golfed some more, though.

-8 bytes thanks to @Jakob.

Explanation:

Try it here. (Performance is too bad for test cases above 3, but it does work locally..)

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

Answer 7

Python 3, 97 96 bytes

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))}

Returns a set of strings.

Try it online!

Answer 8

Julia 0.6, 65 bytes

!n=n>0?["$c"s for s=!~-n,c="RPS"if~ismatch(r"(.+)\1","$c"s)]:[""]

Try it online!

Answer 9

Perl 5, 37 bytes

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

Try it online!

Function returns an array of the square free strings.

Explained:

The glob generates all combinations of R, S, & P with length equal to the input. The grep statement filters out the ones that are not square free.

Answer 10

R, 97 bytes

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

Try it online!

combn(rep(c('p','r','s'),n),n,paste,collapse='') computes all n-character strings with p, r, s, but it unfortunately duplicates many(*), so we uniquify it, and take those that match the regex (.+)\1, using perl-style matching, then we print out the resultant list.

(*) technically, it generates all combinations of the 3n letters in p,r,s repeated 3 times taken n at a time, then applies paste(..., collapse='') to each combination rather than computing the 3^n strings directly, but this is golfier than an expand.grid (the true Cartesian product).

Answer 11

JavaScript (Firefox 30-57), 69 bytes

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

Since all substrings of square-free words are also square-free the check can be done recursively.

Answer 12

Haskell, 101 98 bytes

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

Try it online!

Answer 13

Julia, 88

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

Nothing fancy.

Answer 14

JavaScript (ES7), 93 bytes

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

Converts all the integers from 0 to 3ⁿ to (reversed padded) base 3 using RPS as digits and filters them for square-free words.

Answer 15

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"))

There has to be a better way to do this :)

Answer 16

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")))

Answer 17

k, 56 bytes

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

The lack of native regex puts k well behind the curve for once. I went with a recursive solution, since the characters to implement it were saved by a simpler squarefree check.

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

is k's ternary operator, here we do interesting stuff for non-zero length, and return a single empty string if asked for zero-length words.

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

takes the cartesian product of "RPS" and all n-1 length squarefree words. ,/:\: joins each element of the right to the left, giving a length 3 array of length n arrays. ,/ flattens this into a length 3n array.

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

takes the first n letters of each string and compares it to the second n, then reduces the array to only where they do not match. Because we know the previous result is square-free, only the substrings starting at the first character need matching - simplifying the check here was worth the characters spent implementing recursion. Finally,

/1_!x

applies the lambda to the initial result set to its left, iterating over each substring length from 1 to (word length)-1. !x generates a list from 0 to x-1, then 1_ removes the first element (since 0-length substrings will always match)

Sacrificing a few characters we can use .z.s to self-reference rather than rely on the function name, and instead of checking substrings up to length n-1 only check floor(n/2) for performance. It finds all length 49 words (of which there are 5207706) in about 120 seconds on a 7700k, above that I run into the 4GB limit of free 32-bit k.

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

Answer 18

Python 2, 99 bytes

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['']

Try it online!