Po plotce, że Codegolf zorganizuje turniej Rock-Paper-Scissors , przyjrzysz się słowu bez kwadratów . Słowo z liter R, P, Sjest plac wolne , jeśli nie zawierają sekwencję który powtarza dwukrotnie. To znaczy, słowa tego nie można zapisać jako

a x x b

gdzie ai bsą wyrazy o dowolnej długości i xjest słowem o długości co najmniej jeden, wszystkie wykonane z liter R, P, S.

Zadanie

Napisz program, który generuje kwadratowych wolnej od słów z liter R, P, Sdługości n, w których liczba 1 <= n <= 10jest traktowana jako wejścia.

Przykład

Na przykład słowa bez kwadratów o długości 3 to

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

a te o długości 4 są

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

i zauważ, że na przykład SPSPlub PRPRnie są kwadratowe

Zasady

• To jest codegolf, najkrótszy program wygrywa, standardowe luki są zamknięte.
• Możesz wydrukować słowa lub utworzyć je w pamięci.
• Twój program może być napisany jako funkcja.

Referencje

Wpis w Wikipedii dotyczący słów bez kwadratów

Liczba kwadratowych słów trójskładnikowych o podanej długości znajduje się w https://oeis.org/A006156

Powiązane: Arbitrary-Length Ternary Squarefree Słowa

Rubin, 39 bajtów

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

Ta przezabawnie nieefektywna funkcja generuje wszystkie ciągi długości N, które leżą alfabetycznie między N Ps i N Ss, a następnie odfiltrowuje ogromną większość, która zawiera znaki spoza RPS. Rzeczywista kontrola kwadratem po prostu wykorzystuje wstecznych RegExp: (.+)\1.

Więcej idiomatycznych 65 bajtów, które kończą się w rozsądnym czasie dla N = 10:

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

Edycja: Zapisano bajt dzięki G B.

Galaretka , 15 14 bajtów

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

Wypróbuj online!

Jak to działa

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

Siatkówka , 28 bajtów

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

Wypróbuj online!

Pobiera dane wejściowe jednoargumentowe .

Wyjaśnienie

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

Generuje to wszystkie ciągi złożone RPSz długości n. Robimy to w ten sposób, że wielokrotnie zastępujemy pierwszą 1w każdej linii. Pomyślmy o linii jako <1>, gdzie <jest wszystko przed meczem i >wszystko po meczu (są one $`i $'odpowiednio w składni podstawienia wyrażenia regularnego, ale te wyglądają mniej intuicyjnie). Możemy wymienić 1z R>¶<P>¶<S, gdzie ¶są karetki. Tak pełny wynik tego podstawienia jest w rzeczywistości <R>¶<P>¶<S>, która jest trzy kopie linii, przy czym 1zastąpić R, P, S, odpowiednio, w każdym z trzech egzemplarzach. Proces ten kończy się, gdy wszystkie 1s zostaną zastąpione.

A`(.+)\1

Wreszcie po prostu odrzucamy wszystkie wiersze zawierające powtórzenie.

Łuska , 15 14 bajtów

-1 bajt dzięki Zgarb!

fȯεfoE½QΠR"RPS

Wypróbuj online!

Buduje wszystkie możliwe sekwencje o prawidłowej długości i zachowuje tylko te, których wszystkie podłańcuchy (oprócz pustego) składają się z dwóch różnych połówek.

Cholera, naprawdę chciałem pokonać Jelly tutaj.

Mathematica, 61 bajtów

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

Wypróbuj online!

Java 8, 285 277 bajtów

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

Chociaż Java jest prawie zawsze gadatliwa, w tym przypadku zdecydowanie nie jest to odpowiedni język do takich wyzwań. Generowanie permutacji z podciągami jest szkodliwe dla wydajności i nieefektywne.

Zdecydowanie można jednak jeszcze zagrać w golfa.

-8 bajtów dzięki @Jakob .

Wyjaśnienie:

Wypróbuj tutaj. (Wydajność jest zbyt niska dla przypadków testowych powyżej 3, ale działa lokalnie ..)

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

Python 3 , 97 96 bajtów

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

Zwraca zestaw ciągów.

Wypróbuj online!

Julia 0.6 , 65 bajtów

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

Wypróbuj online!

Perl 5 , 37 bajtów

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

Wypróbuj online!

Funkcja zwraca tablicę kwadratowych wolnych ciągów.

Wyjaśnił:

globGeneruje wszystkie kombinacje R, S i P, o długości równej wejściu. Te grepfiltry oświadczenie, te, które nie są kwadratowe darmo.

R , 97 bajtów

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

Wypróbuj online!

combn(rep(c('p','r','s'),n),n,paste,collapse='')oblicza wszystkie ndwuznakowe struny p, r, s, ale niestety powiela wiele (*), więc uniquify go i wziąć te, które pasują do wyrażenia regularnego (.+)\1, używając Perl dopasowanie stylu, potem wydrukować listę wynikową.

(*) technicznie generuje wszystkie kombinacje 3nliter p,r,spowtarzane 3 razy, na następnie stosuje się paste(..., collapse='')do każdej kombinacji zamiast 3^nbezpośrednio obliczać ciągi, ale jest to bardziej golfowe niż expand.grid(prawdziwy produkt kartezjański).

JavaScript (Firefox 30-57), 69 bajtów

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

Ponieważ wszystkie podciągi słów bez kwadratów są również pozbawione kwadratów, sprawdzanie można wykonać rekurencyjnie.

Haskell , 101 98 bajtów

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

Wypróbuj online!

JavaScript (ES6), 93 bajty

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

Konwertuje wszystkie liczby całkowite od 0 do 3ⁿ do (odwróconej) bazy 3 za pomocą RPScyfr i filtruje je pod kątem słów bez kwadratów.

Julia, 88 lat

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

Nic fajnego.

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

Musi być lepszy sposób na to :)

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

k, 56 bajtów

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

Brak natywnego wyrażenia regularnego stawia raz wartość k za krzywą. Poszedłem z rozwiązaniem rekurencyjnym, ponieważ postacie, które go wdrożyły, zostały zapisane przez prostsze sprawdzenie bez kwadratów.

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

jest trójskładnikowym operatorem k, tutaj robimy ciekawe rzeczy dla niezerowej długości i zwracamy pojedynczy pusty ciąg, jeśli zostaniesz zapytany o słowa o zerowej długości.

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

bierze iloczyn kartezjański „RPS” i wszystkich kwadratowych słów o długości n-1. , /: \: łączy każdy element od prawej do lewej, dając tablicę o długości 3 o długości n tablic. , / spłaszcza to do tablicy o długości 3n.

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

bierze pierwsze n liter każdego łańcucha i porównuje je z drugim n, a następnie redukuje tablicę tylko tam, gdzie się nie zgadzają. Ponieważ wiemy, że poprzedni wynik nie zawiera kwadratów, tylko podciągi zaczynające się od pierwszego znaku wymagają dopasowania - uproszczenie zaznaczenia tutaj było warte znaków spędzonych na rekurencji. Wreszcie,

/1_!x

stosuje lambda do początkowego zestawu wyników po jego lewej stronie, iterując po każdej długości podłańcucha od 1 do (długości słowa) -1. ! x generuje listę od 0 do x-1, a następnie 1_ usuwa pierwszy element (ponieważ podciągi o długości 0 zawsze będą pasować)

Poświęcając kilka znaków, możemy użyć .zs do samodzielnego odwoływania się, zamiast polegać na nazwie funkcji, i zamiast sprawdzać podciągi do długości n-1, sprawdzamy tylko wydajność podłogi (n / 2). Znajduje całą długość 49 słów (z których jest 5207706) w około 120 sekund na 7700k, powyżej tego dochodzę do limitu 4 GB wolnego 32-bitowego k.

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

Python 2 , 99 bajtów

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

Wypróbuj online!