Com o boato de que Codegolf terá um torneio de Pedra, Papel e Tesoura, você analisa o tema das palavras sem quadrados . A palavra feita das letras R
, P
, S
é square-livre , se ele não contém uma sequência que se repete duas vezes. Ou seja, a palavra não pode ser escrita como
a x x b
onde a
e b
são as palavras de qualquer comprimento e x
é uma palavra de comprimento pelo menos um, todos feitos das letras R
, P
, S
.
Tarefa
Escreva um programa que gera os free-quadrados palavras das letras R
, P
, S
de comprimento n
, onde o número 1 <= n <= 10
é tomada como entrada.
Exemplo
Por exemplo, as palavras sem quadrado do comprimento 3 são
RPR
, RSR
, RPS
, RSP
, SPS
, SRS
, SRP
, SPR
, PRP
, PSP
, PSR
,PRS
e os de comprimento 4 são
RPRS
, RPSR
, RPSP
, RSRP
, RSPR
, RSPS
, PRPS
, PRSR
, PRSP
, PSRP
, PSRS
, PSPR
, SRPR
, SRPS
, SRSP
, SPRP
, SPRS
,SPSR
e observe que, por exemplo, SPSP
ou PRPR
não são quadrados
Regras
- Este é o codegolf, o programa mais curto vence, as brechas padrão estão fechadas.
- Você pode imprimir as palavras ou criá-las na memória.
- Seu programa pode ser escrito como uma função.
Referências
Entrada da Wikipedia em palavras sem quadrados
O número de palavras ternárias sem quadrados e de comprimento determinado está em https://oeis.org/A006156
Relacionados: arbitrária de comprimento ternário Squarefree Words
n>3
seria uma boa idéia, porque houve alguma confusão sobre caracteres repetidos versus sequências repetidas.Respostas:
Ruby, 39 bytes
Essa função hilariamente ineficiente gera todas as seqüências de comprimento N que estão em ordem alfabética entre N Ps e N Ss e, em seguida, filtra a grande maioria que contém caracteres não RPS. A verificação squarefree real apenas usa um backreference Regexp:
(.+)\1
.65 bytes mais idiomáticos que terminam em um período de tempo razoável para N = 10:
Editar: salvou um byte graças a G B.
fonte
Geléia ,
1514 bytesExperimente online!
Como funciona
fonte
Retina , 28 bytes
Experimente online!
Recebe entrada em unário .
Explicação
Isso gera todas as strings compostas
RPS
de comprimenton
. A maneira como fazemos isso é que substituímos repetidamente o primeiro1
de cada linha. Vamos pensar sobre a linha como<1>
, onde<
é tudo na frente do jogo e>
é tudo após o jogo (eles são$`
e$'
, respectivamente, em regex substituição de sintaxe, mas aqueles olhar menos intuitivo). Substituímos1
porR>¶<P>¶<S
, onde¶
estão os feeds de linha. Assim, o resultado completo desta substituição é, na verdade<R>¶<P>¶<S>
, que é três cópias da linha, com a1
substituição comR
,P
,S
, respectivamente, em cada uma das três cópias. Esse processo para quando todos os1
s são substituídos.Finalmente, simplesmente descartamos todas as linhas que contêm uma repetição.
fonte
1(.*)
por,$1R¶$1P¶$1S
mas a contagem de bytes é a mesma.Casca ,
1514 bytes-1 byte graças ao Zgarb!
Experimente online!
Constrói todas as sequências possíveis do comprimento correto e mantém apenas aquelas cujas subseqüências (exceto a vazia) são compostas por duas metades diferentes.
Porra, eu realmente queria vencer Jelly aqui.
fonte
Mathematica, 61 bytes
Experimente online!
fonte
Java 8,
285277 bytesEmbora o Java seja quase sempre detalhado, nesse caso, definitivamente não é a linguagem certa para um desafio como esse. Gerar permutações com substrings é ruim para o desempenho e ineficiente.
Definitivamente pode ser jogado um pouco mais, no entanto.
-8 bytes graças a @Jakob .
Explicação:
Experimente aqui. (O desempenho é muito ruim para casos de teste acima de 3, mas funciona localmente ..)
fonte
n->p("",((1<<3*n)+"").replaceAll(".","PRS"),n)
. Além disso, por que não refatorarfor(;i<1;p(...));
parawhile(i<l)p(...);
?for(;...;)
fora do codegolfing-habbit para ser honesto. Na pior das hipóteses, é a mesma contagem de bytes quewhile(...)
, na melhor das hipóteses, algo pode ser colocado dentro do loop for para salvar bytes. Portanto, tento simplesmente não usáwhile
-lo no codegolfing, porque ele nunca beneficia a contagem de bytes de qualquer maneira. Ou aumenta, ou permanece o mesmo, então eu pessoalmente não me importo com a melhor legibilidade. ;)PRS
seqüências, enquanto o loop original gera uma com 2 ^ ( n -2).n
times "PRS" está correto. O meu estava gerando mais porque economizava bytes (e diminuía o desempenho, mas quem se importa com isso com o codegolf). ;)Python 3 ,
9796 bytesRetorna um conjunto de strings.
Experimente online!
fonte
Julia 0.6 , 65 bytes
Experimente online!
fonte
Perl 5 , 37 bytes
Experimente online!
A função retorna uma matriz de cadeias livres quadradas.
Explicado:
O
glob
gera todas as combinações de R, S e P com comprimento igual à entrada. Agrep
instrução filtra os que não são livres de quadrados.fonte
R , 97 bytes
Experimente online!
combn(rep(c('p','r','s'),n),n,paste,collapse='')
computa todas asn
cordas -character comp
,r
,s
, mas infelizmente duplica muitos (*), de modo que uniquify-la e leve aqueles que correspondem a regex(.+)\1
, usando a correspondência de estilo perl, então imprimir a lista resultante.(*) tecnicamente, gera todas as combinações de
3n
letrasp,r,s
repetidas três vezesn
por vez, depois se aplicapaste(..., collapse='')
a cada combinação, em vez de calcular3^n
diretamente as cordas, mas isso é mais golfista que umexpand.grid
(o verdadeiro produto cartesiano).fonte
JavaScript (Firefox 30-57), 69 bytes
Como todas as substrings de palavras sem quadrados também são sem quadrados, a verificação pode ser feita recursivamente.
fonte
Haskell ,
10198 bytesExperimente online!
fonte
JavaScript (ES6), 93 bytes
Converte todos os números inteiros de 0 a 3ⁿ para (base invertida) 3 usando
RPS
como dígitos e os filtra para palavras sem quadrados.fonte
Julia, 88
Nada chique.
fonte
C # / LINQ, 169
Tem que haver uma maneira melhor de fazer isso :)
fonte
F #, 143
fonte
k, 56 bytes
A falta de regex nativo coloca k bem atrás da curva pela primeira vez. Fui com uma solução recursiva, já que os caracteres para implementá-la foram salvos por uma verificação mais simples, sem quadrados.
é o operador ternário de k, aqui fazemos coisas interessantes com comprimento diferente de zero e retornamos uma única string vazia, se solicitadas palavras com comprimento zero.
pega o produto cartesiano de "RPS" e todas as palavras n-1 de comprimento. , /: \: une cada elemento da direita para a esquerda, fornecendo uma matriz de comprimento 3 de matriz de comprimento n. , / nivela isso em uma matriz de comprimento 3n.
pega as primeiras n letras de cada string e a compara com o segundo n, depois reduz a matriz para apenas onde elas não coincidem. Como sabemos que o resultado anterior é livre de quadrados, apenas as subseqüências que começam no primeiro caractere precisam ser correspondidas - simplificando a verificação aqui valia os caracteres gastos implementando a recursão. Finalmente,
aplica o lambda ao resultado inicial definido à sua esquerda, repetindo o comprimento de cada substring de 1 a (comprimento da palavra) -1. ! x gera uma lista de 0 a x-1 e, em seguida, 1_ remove o primeiro elemento (uma vez que as substrings de comprimento 0 sempre correspondem)
Sacrificando alguns caracteres, podemos usar .zs para se auto-referenciar em vez de confiar no nome da função e, em vez de verificar substrings com o comprimento n-1, verifique apenas o piso (n / 2) quanto ao desempenho. Ele encontra todo o comprimento de 49 palavras (das quais existem 5207706) em cerca de 120 segundos em um 7700k, acima do que eu me deparo com o limite de 4 GB de k de 32 bits livre.
fonte
Python 2 , 99 bytes
Experimente online!
fonte