Cuerdas deseables

28

Una cadena se puede emparejar si se puede dividir en subcadenas, cada una de las cuales es una cadena que se repite dos veces consecutivas. Por ejemplo, aabaaababbbabaes pavable como:

aaba aaba
b b
ba ba

Dada una cadena no vacía de a'sy b' s, genera un valor de Verdad si es deseable y un valor de Falsey si no lo es.

Deseable:

aa
abaaba
bbababbb
aabaaababbbaba
babababa
bbbbbbbbbbbb
aaababbabbabbbababbaabaabaababaaba
aaaabaab

No se puede pagar:

a
ba
baab
abaabaaba
bbbbbbbbbbbbbbb
baababbabaaaab
aaaaabbaaaaa

Te animo a que encuentres soluciones no basadas en expresiones regulares, incluso cuando ya hay una respuesta de expresión regular más corta en tu idioma. Puede marcarlos como "no regex". Por expresiones regulares, me refiero a un subsistema de coincidencia de patrones de cadena incorporado.


Tabla de clasificación:

xnor
fuente
¿Podemos usar algo más que ab?
Erik the Outgolfer
Si bbababbb es pairable, ¿por qué no son baab y aaaaabbaaaaa?
rnso
@rnso Según tengo entendido, bbababbb se puede dividir en 3 pares: bb, abab y bb, que se concatenan en ese orden para formar la cadena original, mientras que los otros dos no.
Sunny Pun
Por la pregunta "cada uno de los cuales (subcadena) es una cadena repetida dos veces CONSECUTIVAMENTE" y eso no está satisfecho con bbababbb. De lo contrario, baab también se puede dividir en baab, y aaaaabbaaaaa en aaaaa bb aaaaa.
rnso
@rnso No estoy seguro de lo que quieres decir allí. Por consecutivamente, quiero decir que las dos repeticiones están una al lado de la otra. En "baa b", las dos b están separadas por a, por lo que no funciona.
xnor

Respuestas:

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

Devuelve verdadero o falso . Pruébalo en Ideone .

Dennis
fuente
44
Esa es una recursión realmente limpia, usando el índice tanto para el centro del doble como para el centro de partición. Es curioso que la veracidad se compruebe como algo menos que algo. Veo algunas mejoras ...
XNOR
8

Retina , 11 bytes

^((.+)\2)+$

Prueba todos los casos de prueba. Los primeros dos bytes lo hacen de varias líneas.

Interpretación bastante literal de las reglas, obviamente usa expresiones regulares, como lo harán todos los programas Retina.

FryAmTheEggman
fuente
2
Dangit, había estado esperando durante 3 semanas para publicar esto ...
ETHproductions
2
Martin también había estado esperando .
xnor
55
Whoops! También lo vencí por 10 segundos ... Bueno, estoy seguro de que si escribo una respuesta de Hexagony, ¡me perdonará!
FryAmTheEggman
55
@FryAmTheEggman Estoy deseando que llegue. :)
Martin Ender
2
Es exactamente lo mismo con Perl:perl -pE '$_=/^((.+)\2)+$/'
Dada
8

Jalea , 10 bytes

ẆŒPẋ€€2F€ċ

No es exactamente eficiente ... ¡ Pruébelo en línea!

Cómo 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
fuente
Esto ... parece ineficiente. ¿Cuánto tiempo puede manejar esto en un período de tiempo razonable?
John Dvorak el
1
Es extremadamente ineficiente ( O (2 ^ n ^ 2) , creo). Tendría que verificar localmente. TIO se queda sin memoria para cadenas de longitud 6 .
Dennis
8
Una cadena de longitud 6 tarda 3:20 minutos en mi máquina y requiere 6 GB de memoria.
Dennis
1
@Dennis No hagamos una entrada de longitud 100 , porque todo se bloqueará. Sí, incluso TIO.
Erik the Outgolfer
@EriktheGolfer Esa es una buena idea ya que ralentizará innecesariamente el TIO para otros usos, pero no lo bloqueará. Tan pronto como el sistema se queda sin memoria, el proceso simplemente es eliminado por la OOM.
Dennis
5

Haskell, 72 69 bytes (sin expresiones regulares)

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

Un enfoque de fuerza bruta. Pruébalo en Ideone .

Gracias a BlackCap por -3 bytes.

Explicación

La función auxiliar gtoma una lista de cadenas y comprueba que consta de pares de cadenas idénticas, como ["aa","aa","bba","bba","ab","ab"]. La función principal (anónima) divide una cadena de todas las formas posibles y comprueba que al menos una división da como resultado una lista que gacepta.

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
fuente
Puede reemplazar or.mapconany
BlackCap
@BlackCap Por supuesto, gracias! Yo inicialmente tenía any g.map(words.concat)y pensé "bueno, me puede golf la anyque 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)

Espero que esto sea correcto. Funciona bastante lento y andno se ve óptimo.

xsot
fuente
1
Intenté usar cadenas, pero no pude acercarme a mi puntaje basado en índices. Ese es uno inteligente andque tienes allí.
Dennis
¡Felicidades! Recurrir en la partición fue el truco que tenía en mente.
xnor
4

Jalea , 12 bytes

ŒṖµœs€2ZEµ€S

Dos bytes más largos que mi otra respuesta , pero este enfoque es mucho más eficiente y maneja todos menos uno de los casos de prueba.

Pruébalo en línea!

Cómo 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
fuente
3

Pyth - Sin expresión regular - 13 12 bytes

Comprueba si alguna de las particiones está formada por todas las cadenas que son iguales entre sí cuando se cortan en dos.

sm.AqMcL2d./

Test Suite .

Maltysen
fuente
3

Brachylog , 14 bytes (sin expresiones regulares)

lye~l:1j@2zcc?

Pruébalo en línea!

Esto es demasiado lento para algunos de los casos de prueba.

Explicación

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
fuente
3

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

Devoluciones 1por pagar de lo contrario 0. Editar: guardado 1 byte gracias a @ edc65.

Neil
fuente
¡Agradable! Mismo recuento usando substrsin modificar i. Pero con slice3 repetidas veces puede guardar 1 byte aliasing
edc65 02 de
@ edc65 ¿Cómo se obtiene el mismo recuento sin modificar i? Me doy cuenta de que eso s.substr(i,i+i)devuelve lo mismo, s.slice(i,i+=i)pero luego uso el valor modificado de imás tarde ...
Neil
son s.substr(i,i)2 bytes menos, luego s.slice(i+i)2 bytes más
edc65
@ edc65 Oh, por supuesto que sí, debo necesitar más café ...
Neil
3

Python, 58 bytes

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

Esto se basa en el método recursivo de Dennis . El truco de negación booleana también se toma de allí.

La nueva idea es recurrir sobre particiones (p,s)de la cadena original comenzando ('',s)y moviendo repetidamente el primer carácter de spara ser el último carácter de p. Esto permite que se haga referencia a las partes directamente sin segmentación de cadenas. Pero, debido a que la partición comienza con pvacío, debemos tener cuidado de evitar bucles infinitos de f(s)llamadas f(s).

xnor
fuente
2

JavaScript (ES6), 24 bytes

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

Probablemente no se acorte más que esto.

ETHproducciones
fuente
¿No debería ser eso \2?
Neil
@Neil Por alguna razón, pensé que funcionaba \1, pero aabregresa true... gracias por la solución.
ETHproductions
2

PHP, 40 bytes

imprime 0 para falso y 1 para verdadero

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

Python, 66 64 bytes

¡Gracias @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)

Devoluciones Trueo False.

Pruébalo en línea!

Cualquier ayuda de golf esto sería apreciada.

Oliver Ni
fuente
1

Raqueta 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 un '!' para cada forma en que la cadena es painable. Imprime un '.' al final.

Sin golf:

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

Pruebas:

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

Salida:

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

Perl, 16 +2 = 18 bytes (con expresiones regulares)

Corre con las -nlbanderas. -Eestá libre.

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

Correr como:

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

Devuelve una lista de los grupos de captura (una verdad) si es deseable, cadena nula si no es deseable.

Explicación

Las -nlbanderas ejecutarán el código en un bucle ( -n), colocando la entrada (con la nueva línea eliminada debido a -l) en la variable $_cada vez, luego evaluando el código cada vez que se ingresa la entrada, hasta que el programa se termina manualmente. El -Eindicador le permite evaluar el código en la línea de comando y habilita el 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

Si se encuentra una coincidencia (por ejemplo, si la cadena se puede emparejar), la expresión regular devuelve una lista de los grupos de captura, que se evalúa como verdadera, que luego se pasa a say , y se . Si no se encuentra ninguna coincidencia, entonces la expresión regular devuelve la cadena vacía, que se evalúa como falsa, que luego se pasa sayy se emite.

Muestra:

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

GNU Prolog, 49 46 bytes

Probablemente también funciona en otras variantes, aunque no todas representan cadenas de la misma manera; La representación de GNU Prolog es útil para este problema.

No está claro si esto cuenta como usar expresiones regulares o no. No utiliza ninguna característica similar a la expresión regular, pero toda la semántica del lenguaje es similar a la de la expresión regular.

Nueva versión (utiliza el truco de recursión visto en algunas otras respuestas):

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

Versión antigua:

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

Este es un predicado (equivalente de Prolog de una función) llamado s, no un programa completo. Úselo así:

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

Una característica interesante de la solución anterior es que si le pregunta al intérprete "¿hay más soluciones?" mediante el uso de ;en el true ?indicador (en lugar de preguntar "¿hay alguna solución" al presionar la tecla de retorno en el indicador, como hice anteriormente), devuelve "verdadero" una cantidad de veces igual al número de formas diferentes en que la cadena se puede expresar en la forma dada (por ejemplo, devuelve "verdadero" dos veces con s("aaaa")., ya que esto se puede analizar como (a a)(a a)o como (aa aa)).

Programas Prolog son a menudo reversible (permitiendo sa generar una lista de cadenas con la propiedad dada). El anterior no lo es (entra en un bucle infinito), pero eso se debe al método de golf que utilicé para asegurarme de que C no esté vacío; si reescribe el programa para especificar C como no explícitamente explícito, genera cadenas de la forma "aa", "aabb", "aabbcc", etc. (Prolog es Prolog, no especifica identidades para los caracteres que los hacen arriba, solo una especificación de qué caracteres son iguales). El más nuevo genera cadenas de la forma "aa", "abab", "abcabc", y así sucesivamente; este es un bucle infinito por derecho propio y, por lo tanto, nunca llega al punto en el que se atascaría al no detectar una cadena de longitud cero.


fuente
1

Brainfuck, 177 bytes

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

Formateado:

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

Espera entrada sin una nueva línea final. Imprime \x00para falso y \x01para verdadero.

Pruébalo en línea.

Esto implementa la búsqueda de profundidad primero. En particular: verifique los prefijos repetidos de longitud creciente a partir del sufijo actual, luego vaya al siguiente sufijo si se encuentra una coincidencia; de lo contrario, retroceda.

Al principio, la cadena se invierte y \x01se coloca un centinela al final.

La cinta se divide en nodos de 4 celdas. El diseño de memoria de un nodo es:

c h x 0

dónde cestá el carácter, hes un indicador de si el carácter está en la primera mitad de un prefijo repetido y xes un indicador para realizar un seguimiento del par de caracteres actual que se compara. Las hbanderas permanecen en su lugar mientras elx banderas forman una ventana móvil.

Si la cadena es deseable, el puntero aterriza junto al centinela al final del bucle principal; de lo contrario, el puntero se cae del lado izquierdo de la cadena mientras retrocede.

Mitch Schwartz
fuente
1

Brachylog , 5 bytes

~c~jᵐ

Pruébalo en línea!

Tenga en cuenta que este algoritmo puede tomar muy largo tiempo, especialmente en los casos Falsey, ya que comprueba cada posible partición de la cadena de entrada.

Explicación

~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 una cadena de entrada como "ababcc", ~cintenta diferentes particiones hasta que llega ["abab", "cc"], en cuyo punto ~jtiene éxito para ambos elementos de la lista, salidas ["ab", "c"]y el predicado tiene éxito.

DLosc
fuente
1

R , 31 bytes

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

Pruébalo en línea!

Basado en la respuesta de Retina.

R , 129 bytes

Y aquí hay una respuesta original, no regex:

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)

Pruébalo en línea!

Nick Kennedy
fuente
0

Lithp , 57 caracteres

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

Uso de la muestra:

% 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
fuente