Strings emparelhados

28

Uma string é parável se puder ser dividida em subtrings, cada uma das quais é uma string repetida duas vezes consecutivas. Por exemplo, aabaaababbbabaé parável como:

aaba aaba
b b
ba ba

Dada uma sequência não vazia de a's' e b's, produza um valor Truthy se for parável e um valor Falsey se não for.

Par:

aa
abaaba
bbababbb
aabaaababbbaba
babababa
bbbbbbbbbbbb
aaababbabbabbbababbaabaabaababaaba
aaaabaab

Não emparelhado:

a
ba
baab
abaabaaba
bbbbbbbbbbbbbbb
baababbabaaaab
aaaaabbaaaaa

Convido você a apresentar soluções não baseadas em regex, mesmo quando já houver uma resposta regex mais curta no seu idioma. Você pode marcá-los como "sem regex". Por regex, refiro-me a um subsistema de correspondência de padrão de seqüência de caracteres interno.


Entre os melhores:

xnor
fonte
Podemos usar outra coisa senão ab?
Erik the Outgolfer 2/16/16
Se bbababbb é parável, por que baab e aaaaabbaaaaa não?
#
@rnso Pelo meu entendimento, o bbababbb pode ser derramado em três pares: bb, abab e bb, que concatenam nessa ordem para formar a string original, enquanto os outros dois não.
Sunny Pun
Pela pergunta "cada um dos quais (substring) é uma sequência repetida duas vezes CONSECUTIVAMENTE" e isso não está satisfeito com o bbababbb. Caso contrário, o baab também pode ser dividido em baab e aaaaabbaaaaa para aaaaa bb aaaaa.
Rnso
@ rnso Não sei ao certo o que você quer dizer com isso. Por consecutivamente, quero dizer que as duas repetições são próximas uma da outra. Em "baa b", os dois b's são separados por a's, para que não funcione.
Xnor

Respostas:

11

Python 2, 68 63 bytes

f=lambda s,n=1:s==2*s[:n]or''<s[n:]>-f(s,n+1)<f(s[n:])*f(s[:n])

Retorna Verdadeiro ou Falso . Teste em Ideone .

Dennis
fonte
4
É uma recursão realmente limpa, usando o índice para o centro da dupla e o centro para particionar. É engraçado que a veracidade seja verificada como sendo menor que algo. Eu vejo algumas melhorias ...
xnor
8

Retina , 11 bytes

^((.+)\2)+$

Experimente todos os casos de teste. Os dois primeiros bytes o tornam multi-linhas.

Uma interpretação bastante literal das regras, obviamente usa regex, como todos os programas Retina.

FryAmTheEggman
fonte
2
Dangit, eu estava esperando por 3 semanas para postar isso ...
ETHproductions
2
Martin estava esperando também .
xnor
5
Ops! Eu só venci ele por 10 segundos também ... Bem, eu tenho certeza que se eu escrever uma resposta Hexagony, ele vai me perdoar!
FryAmTheEggman #
5
@FryAmTheEggman Estou ansioso por isso. :)
Martin Ender
2
É exatamente o mesmo com o Perl:perl -pE '$_=/^((.+)\2)+$/'
Dada
8

Gelatina , 10 bytes

ẆŒPẋ€€2F€ċ

Não é exatamente eficiente ... Experimente online!

Como funciona

ẆŒPẋ€€2F€ċ  Main link. Argument: s (string)

Ẇ           Window, generate the array of all substrings of s.
 ŒP         Powerset; generate all subarrays of substrings of s.
   ẋ€€2     Repeat each substring in each subarray twice.
            For example, ["ab", "a", "b"] becomes ["abab", "aa", "bb"].
       F€   Flatten the subarrays by concatenating their strings.
         ċ  Count how many times s appears in the generated strings.
Dennis
fonte
Isso ... parece ineficiente. Por quanto tempo essas entradas podem ser processadas em um prazo razoável?
John Dvorak
1
É extremamente ineficiente ( O (2 ^ n ^ 2) , eu acho). Eu teria que verificar localmente. O TIO fica sem memória para seqüências de comprimento 6 .
Dennis
8
Uma seqüência de caracteres 6 leva 3:20 minutos na minha máquina e requer 6 GB de memória.
Dennis
1
@ Dennis Não vamos fazer uma entrada de comprimento 100 , pois tudo irá falhar. Sim, mesmo TIO.
Erik the Outgolfer 2/16
@EriktheGolfer Essa é uma boa ideia, pois diminuirá desnecessariamente o TIO para outros usos, mas não o travará. Assim que o sistema fica sem memória, o processo simplesmente é interrompido pelo OOM.
Dennis
5

Haskell, 72 69 bytes (sem regex)

g(a:b:c)|a==b=g c
g x=x==[]
any(g.words.concat).mapM(\c->[[c],c:" "])

Uma abordagem de força bruta. Experimente em Ideone .

Graças ao BlackCap por -3 bytes.

Explicação

A função auxiliar gpega uma lista de cadeias e verifica se consiste em pares de cadeias idênticas, como ["aa","aa","bba","bba","ab","ab"]. A função principal (anônima) divide uma string de todas as maneiras possíveis e verifica se pelo menos uma divisão resulta em uma lista que gaceita.

g(a:b:c)                                  g on list with elements a, b and tail c,
        |a==b                              in the case that a==b,
             =g c                          recurses to the tail c.
g x=                                      g on any other list x
    x==[]                                  checks that x is empty.
                                           This includes the case where a is not equal
                                           to b, resulting in False.
any(g.words.concat).mapM(\c->[[c],c:" "]) The main function:
                    mapM(\c->[[c],c:" "])  Replace each letter c with either "c" or "c "
                                           in all possible ways, return list of results.
any(              ).                       Check that at least one result satisfies this:
            concat                          Concatenate the 1- or 2-letter strings,
      words.                                split again at each space,
    g.                                      apply g.
Zgarb
fonte
Você pode substituir or.mapporany
BlackCap 2/16
@BlackCap Claro, obrigado! Inicialmente, eu tinha any g.map(words.concat)e pensei "hey, eu posso golf o anyde or" ...
Zgarb
5

Python 2, 60 bytes

f=lambda s,t='':''<s>f(s[1:],t+s[0])|f(t and s)*f(t)>-(s==t)

Eu espero que isto esteja correto. Ele roda bem devagar e andnão parece ótimo.

xsot
fonte
1
Tentei usar strings, mas não consegui chegar nem perto da minha pontuação baseada em índice. Essa é uma das suas esperanças and.
Dennis
Parabéns! A repetição na partição foi o truque que eu tinha em mente.
Xnor
4

Gelatina , 12 bytes

ŒṖµœs€2ZEµ€S

Dois bytes a mais que minha outra resposta , mas essa abordagem é muito mais eficiente e lida com todos, exceto um dos casos de teste.

Experimente online!

Como funciona

ŒṖµœs€2ZEµ€S  Main link. Argument: s (string)

ŒṖ            Generate all partitions of s.
  µ      µ€   Map the monadic chain between the µ's over the partitions.
   œs€2         Split each string in the partition into two chunks of equal length.
       Z        Zip/transpose, collecting the first halves in one array and the
                second halves in another.
        E       Test the arrays of halves for equality.
           S  Return the sum of the results, counting the number of different
              ways s can be paired.
Dennis
fonte
3

Pyth - No Regex - 13 12 bytes

Verifica se alguma das partições é composta por todas as cadeias iguais entre si quando cortadas em duas.

sm.AqMcL2d./

Conjunto de Teste .

Maltysen
fonte
3

Braquilog , 14 bytes (sem regex)

lye~l:1j@2zcc?

Experimente online!

Isso é muito lento para alguns dos casos de teste

Explicação

ly                  The list [0, …, length(Input)]
  e~l               A list whose length is an element of the previous list
     :1j            Append itself to this list
        @2zc        Split in half, zip and concatenate so that the list contains pairs of
                      consecutive identical elements
            c?      The concatenation of that list must result in the Input
Fatalizar
fonte
3

JavaScript (ES6), sem regexp, 75 74 bytes

f=s=>!s|[...s].some((_,i)=>i&&s[e='slice'](0,i)==s[e](i,i+=i)&&f(s[e](i)))

Retorna 1para emparelhado caso contrário 0. Editar: salvou 1 byte graças a @ edc65.

Neil
fonte
Agradável! Mesma contagem usando substrsem modificar i. Mas com slicerepetidos 3 vezes você pode economizar 1 byte aliasing lo
edc65
@ edc65 Como você obtém a mesma contagem sem modificar i? Eu percebo que s.substr(i,i+i)retorna a mesma s.slice(i,i+=i), mas eu, em seguida, usar o valor modificado de imais tarde ...
Neil
é s.substr(i,i)2 bytes menos, então s.slice(i+i)2 bytes mais
edc65
@ edc65 Oh, claro que é, devo precisar de mais café ...
Neil
3

Python, 58 bytes

f=lambda s,p='':s>''and(f(p)>-(s==p)<f(s))|f(s[1:],p+s[0])

Isso é baseado no método recursivo de Dennis . O truque de negação booleana também é adotado a partir daí.

A nova idéia é repetir as partições (p,s)da sequência original iniciando ('',s)e movendo repetidamente o primeiro caractere de spara ser o último caractere de p. Isso permite que as peças sejam referenciadas diretamente sem cortar as cordas. Mas, como a partição começa com pvazio, devemos ter cuidado para evitar ciclos infinitos de f(s)chamadas f(s).

xnor
fonte
2

JavaScript (ES6), 24 bytes

x=>/^((.+)\2)+$/.test(x)

Provavelmente não fica mais curto que isso.

ETHproductions
fonte
Isso não deveria ser \2?
Neil
@ Neil Por alguma razão, eu pensei que funcionava \1, mas aabretorna true... obrigado pela correção.
ETHproductions
2

PHP, 40 bytes

imprime 0 para falso e 1 para verdadeiro

<?=preg_match("#^((.+)\\2)+$#",$argv[1]);
Jörg Hülsermann
fonte
2

Python, 66 64 bytes

Obrigado @Zgarb por -1 byte!

f=lambda x,s=1:x>x[:s]and(x==2*x[:s])|f(x[:s])&f(x[s:])|f(x,s+1)

Retorna Trueou False.

Experimente online!

Qualquer ajuda no golfe seria apreciada.

Oliver Ni
fonte
1

Raquete 230 bytes

(let((sl string-length)(ss substring))(if(odd?(sl s))(printf ".~n")(begin(let p((s s))(if(equal? s "")(printf "!")
(for((i(range 1(add1(/(sl s)2)))))(when(equal?(ss s 0 i)(ss s i(* 2 i)))(p(ss s(* 2 i)(sl s)))))))(printf ".~n"))))

Imprime um '!' para cada maneira em que a sequência é pareada. Imprime um '.' no fim.

Ungolfed:

(define (f s)
  (let ((sl string-length)                              ; create short names of built-in fns
        (ss substring))
    (if (odd? (sl s))  (printf ".~n")                   ; odd length strings cannot be pairable; end here.
        (begin
          (let loop ((s s))                             ; start testing here
            (if (equal? s "") (printf "!")              ; if no remaining string, it must be pairable
                (for ((i (range 1 (add1 (/(sl s)2)))))  ; ch lengths varying from 1 to half of string length
                  (when (equal? (ss s 0 i)              ; ch if substrings are same
                                (ss s i (* 2 i)))
                    (loop (ss s (* 2 i) (sl s) ))))))   ; if yes, loop to check remaining string.
          (printf ".~n")))))                            ; End of testing.

Teste:

(println "Following should be pairable")
(f "bbaabbaa")            ; should produce 2 '!' since 2 ways are possible.
(f "aa")
(f "abaaba")
(f "bbababbb")
(f "aabaaababbbaba")
(f "babababa")                    ; should be pairable in 2 ways.
(f "bbbbbbbbbbbb")                ; should be pairable in many ways.
(f "aaababbabbabbbababbaabaabaababaaba")
(f "aaaabaab")
(println "Following should be unpairable")
; (f "a")
(f "ba")
(f "baab")
(f "abaabaaba")
(f "bbbbbbbbbbbbbbb")
(f "baababbabaaaab")
(f "aaaaabbaaaaa")

Saída:

"Following should be pairable"
!!.
!.
!.
!.
!.
!!.
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!.
!.
!.
"Following should be unpairable"
.
.
.
.
.
.
rnso
fonte
1

Perl, 16 +2 = 18 bytes (com regex)

Corra com as -nlbandeiras. -Eé grátis.

say/^((.+)\2)+$/

Correr como:

perl -nlE 'say/^((.+)\2)+$/'

Retorna uma lista dos grupos de captura (uma verdade) se emparelhados, cadeia nula se não emparelhados.

Explicação

o -nl sinalizadores executam o código em um loop ( -n), colocando a entrada (com a nova linha à direita removida por causa -l) na variável a $_cada vez e avaliando o código cada vez que a entrada é inserida, até que o programa seja finalizado manualmente. O -Esinalizador permite avaliar o código na linha de comando e habilita o saycomando.

say/^((.+)\2)+$/

   /^((.+)\2)+$/  #The regex engine
      (.+)\2      #Find any set of at least one character, followed by itself
     (      )+    #Do this at least one time
   /^         $/  #Make sure that this matches the entire string from start to end
say               #Output the result of the regex

Se uma correspondência for encontrada (por exemplo, se a sequência for emparelhada), o regex retornará uma lista dos grupos de captura, que são avaliados para uma verdade, que depois são passados ​​para saye emitidos. Se nenhuma correspondência for encontrada, o regex retornará a cadeia vazia, avaliada como falsa, que é passada para saye emitida.

Amostra:

$ perl -nlE 'say/^((.+)\2)+$/'
aaababbabbabbbababbaabaabaababaaba
baababaababaaba                      #Truthy
baababbabaaaab
                                     #Falsy
bbababbb
bbb                                  #Truthy
aabaaababbbaba
bababa                               #Truthy
abaabaaba
                                     #Falsy
Gabriel Benamy
fonte
1

GNU Prolog, 49 46 bytes

Provavelmente também funciona em outras variantes, embora nem todas representem seqüências de caracteres da mesma maneira; A representação do GNU Prolog é útil para este problema.

Não está claro se isso conta como usar regex ou não. Não está usando nenhum recurso parecido com regex, mas toda a semântica da linguagem é semelhante à do regex.

Nova versão (usa o truque de recursão visto em outras respostas):

s(X):-append(A,B,X),(A=B;A\=X,B\=X,s(A),s(B)).

Versão antiga:

s(X):-X=[];append(A,B,X),B\=X,append(C,C,A),s(B).

Este é um predicado (equivalente a uma função do Prolog) chamado s, não um programa completo. Use-o assim:

| ?- s("aa").
true ?
yes
| ?- s("aaababbabbabbbababbaabaabaababaaba").
true ?
yes
| ?- s("baababbabaaaab").
no
| ?- s("bbbbbbbbbbbbbbb").
no

Uma característica interessante da solução mais antiga é que, se você perguntar ao intérprete "existem mais soluções?" via uso de ;no true ?prompt (em vez de perguntar "existe alguma solução", pressionando return no prompt, como fiz acima), ele retorna "true" várias vezes igual ao número de maneiras diferentes pelas quais a string pode ser expressa na forma especificada (por exemplo, retorna "true" duas vezes com s("aaaa")., pois isso pode ser analisado como (a a)(a a)ou como (aa aa)).

Programas Prolog são geralmente reversíveis (permitindo sa gerar uma lista de strings com a propriedade dada). O mais antigo não é (entra em um loop infinito), mas é por causa do método de golfe que eu usei para garantir que C não seja vazio; se você reescrever o programa para especificar C como não vazio explicitamente, ele gerará sequências do formato "aa", "aabb", "aabbcc" e assim por diante (Prolog sendo Prolog, ele não especifica identidades para os caracteres que os fazem apenas uma especificação de quais caracteres são iguais). O mais recente gera sequências do formato "aa", "abab", "abcabc" e assim por diante; esse é um loop infinito por si só e, portanto, nunca atinge o ponto em que ficaria preso devido à falha em detectar uma cadeia de comprimento zero.


fonte
1

Brainfuck, 177 bytes

+[<<<<,]>>>>[>+[>+[[>>]<+<[<<]>+>-]<[>+<-]>>>,>>[>>]+<<[<+>>-<-]<[>+<-]>>[,>[-<<
<<]<[<<<<]>]<[[<<]>]>>]>>[[>+>>>]>>>[>]<<<<[>+[-<<<,<]<[<<<[[<<<<]>>]<]>]>>]<[[-
>>>>]>>[<]<]<<]<.

Formatado:

+[<<<<,]
>>>>
[
  >+
  [
    >+
    [
      [>>]
      <+<[<<]
      >+>-
    ]
    <[>+<-]>
    >>,>>[>>]
    +<<[<+> >-<-]
    <[>+<-]>
    >
    [
      not equal
      ,>[-<<<<]
      <[<<<<]
      >
    ]
    <
    [
      equal
      [<<]
      >
    ]
    >>
  ]
  >>
  [
    mismatch
    [>+>>>]
    >>>[>]
    <<<<
    [
      backtrack
      >+[-<<<,<]
      <
      [
        not done yet
        <<<
        [
          [<<<<]
          >>
        ]
        <
      ]
      >
    ]
    >>
  ]
  <
  [
    match
    [->>>>]
    >>[<]
    <
  ]
  <<
]
<.

Espera entrada sem uma nova linha à direita. Imprime \x00para falso e \x01verdadeiro.

Experimente online.

Isso implementa a pesquisa em profundidade. Em particular: verifique se há prefixos repetidos de tamanho crescente a partir do sufixo atual e, em seguida, passe para o próximo sufixo se uma correspondência for encontrada, caso contrário, volte.

No início, a corda é invertida e uma sentinela \x01é colocada no final.

A fita é dividida em nós de 4 células. O layout da memória de um nó é:

c h x 0

onde cestá o caractere, hé um sinalizador para saber se o personagem está na primeira metade de um prefixo repetido e xé um sinalizador para acompanhar o par atual de caracteres sendo comparado. As hbandeiras permanecem no lugar enquanto as xbandeiras formam uma janela em movimento.

Se a sequência for emparelhada, o ponteiro cairá próximo à sentinela no final do loop principal; caso contrário, o ponteiro cai do lado esquerdo da corda durante o retrocesso.

Mitch Schwartz
fonte
1

Braquilog , 5 bytes

~c~jᵐ

Experimente online!

Observe que esse algoritmo pode levar muito tempo, especialmente em casos falsey, pois verifica todas as partições possíveis da string de entrada.

Explicação

~c     Reversed concatenate: find a list that, when concatenated, results in the input string
       This examines all partitions of the input
  ~jᵐ  Map reversed juxtapose: for each string in that list, is it the result of concatenating
       a string to itself?

Para uma sequência de entrada como "ababcc", ~ctenta partições diferentes até que cheguem ["abab", "cc"], momento em que ~jos itens da lista, saídas ["ab", "c"]e o predicado são bem-sucedidos.

DLosc
fonte
1

R , 31 bytes

grepl("^((.+)\\2)+$",scan(,""))

Experimente online!

Com base na resposta da Retina.

R , 129 bytes

E aqui está uma resposta original e não regular:

o=(y=utf8ToInt(scan(,"")))<0;for(i in 2*1:(sum(y>0)/2))for(j in 1:(i/2)){w=i:(i-j+1);v=w-j;if(all(y[w]==y[v]))o[c(v,w)]=T};all(o)

Experimente online!

Nick Kennedy
fonte
0

Lithp , 57 caracteres

#S::((? (!= (null) (match S "^((.+)\\2)+$")) true false))

Uso da amostra:

% pairable_strings.lithp
(
    (def f #S::((? (!= (null) (match S "^((.+)\\2)+$")) true false)))
    (print (f "aa"))
    (print (f "aabaaababbbaba"))
    (print (f "aaababbabbabbbababbaabaabaababaaba"))
    (print (f "ba"))
)

# ./run.js pairable_strings.lithp
AtomValue { value: 2, type: 'Atom', name: 'true' }
AtomValue { value: 2, type: 'Atom', name: 'true' }
AtomValue { value: 2, type: 'Atom', name: 'true' }
AtomValue { value: 3, type: 'Atom', name: 'false' }
Andrakis
fonte