26
\$\begingroup\$

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

\$\endgroup\$
  • 4
    \$\begingroup\$ A test case for n>3 would be a good idea, because there has been some confusion about repeated characters vs. repeated sequences. \$\endgroup\$ – Laikoni Oct 30 '17 at 19:10
  • \$\begingroup\$ Please comment on the planned follow-up in the sand-box: codegolf.meta.stackexchange.com/a/14133/45211 \$\endgroup\$ – mschauer Oct 30 '17 at 21:22
  • 6
    \$\begingroup\$ I don't think the "natural-language" tag should apply here \$\endgroup\$ – Leo Oct 31 '17 at 4:12
  • 1
    \$\begingroup\$ Ah, "words" got expanded in "natural-language", I removed it. \$\endgroup\$ – mschauer Oct 31 '17 at 7:20
  • 1
    \$\begingroup\$ No, it contains the square SP SP \$\endgroup\$ – mschauer Nov 1 '17 at 15:17

18 Answers 18

20
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You don't need parentheses on grep_v, just a space between it and the slash (save 1 byte) \$\endgroup\$ – G B Oct 31 '17 at 14:47
  • 6
    \$\begingroup\$ "hilariously inefficient" probably describes quite a few answers on this site. \$\endgroup\$ – Nic Hartley Oct 31 '17 at 15:55
10
\$\begingroup\$

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.
\$\endgroup\$
7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I would have repeatedly replaced 1(.*) with $1R¶$1P¶$1S but the byte-count is the same. \$\endgroup\$ – Neil Oct 30 '17 at 22:15
6
\$\begingroup\$

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.

\$\endgroup\$
  • 3
    \$\begingroup\$ 14 bytes to tie with Jelly. \$\endgroup\$ – Zgarb Oct 31 '17 at 7:26
5
\$\begingroup\$

Mathematica, 61 bytes

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

Try it online!

\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ How about this lambda: n->p("",((1<<3*n)+"").replaceAll(".","PRS"),n). Also, why not refactor for(;i<1;p(...)); to while(i<l)p(...);? \$\endgroup\$ – Jakob Oct 31 '17 at 19:15
  • \$\begingroup\$ @Jakob Thanks. And I always use for(;...;) out of codegolfing-habbit to be honest. Worst case it's the same byte-count as while(...), best case something can be placed inside the for-loop to save bytes. So I try to just not use while at all in codegolfing, because it never benefits the byte-count anyway. It either increases it, or remains the same, so I personally don't bother with the better readability. ;) \$\endgroup\$ – Kevin Cruijssen Oct 31 '17 at 20:02
  • 1
    \$\begingroup\$ Yeah, I always try to make my golfed code as readable as possible at a given byte count. Probably a futile pursuit! \$\endgroup\$ – Jakob Oct 31 '17 at 20:14
  • \$\begingroup\$ Wait, does my lambda actually work here? I was a bit careless... It generates a string of n PRS sequences, whereas your original loop generated one with 2^(n-2) sequences. \$\endgroup\$ – Jakob Nov 1 '17 at 2:23
  • \$\begingroup\$ @Jakob n times "PRS" is correct. Mine was generating more because it saved bytes (and decreased performance, but who cares about that with codegolf). ;) \$\endgroup\$ – Kevin Cruijssen Nov 1 '17 at 8:02
4
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

Julia 0.6, 65 bytes

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

Try it online!

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Great use of brace expansion! \$\endgroup\$ – Dom Hastings Oct 31 '17 at 15:19
3
\$\begingroup\$

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

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 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.

\$\endgroup\$
2
\$\begingroup\$

Julia, 88

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

Nothing fancy.

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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")))
\$\endgroup\$
  • \$\begingroup\$ Nice a F# answer! \$\endgroup\$ – aloisdg Nov 3 '17 at 21:27
  • 1
    \$\begingroup\$ It's not the most compact of languages, but hey, any excuse to use it :) \$\endgroup\$ – Jason Handby Nov 3 '17 at 23:12
  • 1
    \$\begingroup\$ I feel you. This language is so nice. \$\endgroup\$ – aloisdg Nov 3 '17 at 23:24
1
\$\begingroup\$

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;,""]}
\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.