Nie powtarzaj się w Rock-Paper-Scissors

26

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

mschauer
źródło
4
Przypadek testowy n>3byłby dobrym pomysłem, ponieważ pojawiły się pewne nieporozumienia dotyczące powtarzanych znaków w porównaniu z powtarzanymi sekwencjami.
Laikoni
Proszę o komentarz w sprawie planowanych działań następczych w piaskownicy: codegolf.meta.stackexchange.com/a/14133/45211
mschauer
6
Nie sądzę, żeby tag „język naturalny” miał zastosowanie tutaj
Leo
1
Ach, „słowa” zostały rozwinięte w „języku naturalnym”, usunąłem je.
mschauer
1
Nie, zawiera kwadrat SP SP
mschauer

Odpowiedzi:

20

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.

histocrat
źródło
Nie potrzebujesz nawiasów na grep_v, wystarczy spacja między nim a ukośnikiem (zapisz 1 bajt)
GB
6
przezabawnie nieefektywne ” prawdopodobnie opisuje sporo odpowiedzi na tej stronie.
Pozew funduszu Moniki z
10

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.
Dennis
źródło
7

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.

Martin Ender
źródło
I byłby wielokrotnie zastąpione 1(.*)z $1R¶$1P¶$1Sale bajt-count jest taka sama.
Neil
6

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

Lew
źródło
3
14 bajtów do powiązania z galaretką.
Zgarb
5

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
Kevin Cruijssen
źródło
1
Jak o tym lambda: n->p("",((1<<3*n)+"").replaceAll(".","PRS"),n). Ponadto, dlaczego nie for(;i<1;p(...));dokonać refaktoryzacji while(i<l)p(...);?
Jakob
@Jakob Thanks. I for(;...;)szczerze mówiąc, zawsze używam kodegolfing-habbit. W najgorszym przypadku jest to ta sama liczba bajtów while(...), co w najlepszym przypadku coś można umieścić wewnątrz pętli for, aby zaoszczędzić bajty. Dlatego staram się po prostu nie używać whilew kodegolfingu, ponieważ i tak nigdy nie korzysta z liczenia bajtów. To albo go zwiększa, albo pozostaje takie samo, więc osobiście nie zawracam sobie głowy lepszą czytelnością. ;)
Kevin Cruijssen
1
Tak, zawsze staram się, aby mój kod do gry w golfa był jak najbardziej czytelny przy danej liczbie bajtów. Prawdopodobnie bezcelowa pogoń!
Jakob
Zaraz, czy moja lambda faktycznie tu działa? Byłem trochę nieostrożny ... Generuje ciąg n PRS sekwencji, podczas gdy twoja oryginalna pętla wygenerowała jedną z 2 ^ ( n -2) sekwencjami.
Jakob
@Jakob nrazy „PRS” jest poprawny. Mój generował więcej, ponieważ oszczędzał bajty (i zmniejszał wydajność, ale kogo to obchodzi z codegolfem). ;)
Kevin Cruijssen
4

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!

Dennis
źródło
4

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!

Dennis
źródło
4

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.

Xcali
źródło
Świetne wykorzystanie rozszerzenia nawiasów klamrowych!
Dom Hastings
3

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

Giuseppe
źródło
3

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.

Neil
źródło
2

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!

Laikoni
źródło
2

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.

Neil
źródło
2

Julia, 88 lat

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

Nic fajnego.

mschauer
źródło
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"))

Musi być lepszy sposób na to :)

Jason Handby
źródło
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
źródło
Fajna odpowiedź F #!
aloisdg mówi Przywróć Monikę
1
To nie jest najbardziej kompaktowy język, ale hej, jakaś wymówka, aby go użyć :)
Jason Handby
1
Czuję cię . Ten język jest taki miły.
aloisdg mówi Przywróć Monikę
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;,""]}
ostewart
źródło
0

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!

Chas Brown
źródło