Generador de cierre palindrómico bidireccional

24

Introducción

Un cierre palindrómico de una cadena de entrada es el palíndromo más corto que se puede construir a partir de la cadena de entrada donde el palíndromo final comienza con la cadena de entrada.

Para este desafío, consideraremos un cierre palindrómico bidireccional tal que

  • El cierre palindrómico izquierdo de una cadena de entrada es el palíndromo más corto posible que comienza con la cadena de entrada.
  • El cierre palindrómico derecho de una cadena de entrada es el palíndromo más corto posible que termina con la cadena de entrada.
  • El cierre palindrómico bidireccional de una cadena de entrada es el más corto del cierre palindrómico izquierdo o derecho de la cadena de entrada.

Tarea

Tu tarea es simple. Dada una cadena (que consiste solo en ASCII imprimible, nuevas líneas y espacios en blanco), genera el cierre palindrómico bidireccional de esa cadena. En caso de empate, cualquiera de los cierres palindrómicos izquierdo o derecho son salidas válidas.

Puede escribir un programa o función, tomando la entrada a través de STDIN (o la alternativa más cercana), argumento de línea de comando o argumento de función, e imprimiendo el resultado en STDOUT (o la alternativa más cercana) o devolviéndolo como una cadena.

Puede suponer que la entrada nunca será una cadena vacía.

Pocos ejemplos:

<Input>   -> <Output>
"abcdef"  -> "abcdefedcba"  (or "fedcbabcdef")
"abcba"   -> "abcba"
"abcb"    -> "abcba"
"cbca"    -> "acbca"

El crédito de la idea inicial va a VisualMelon, la idea final con la ayuda de Martin y Zgarb

Los términos cierre palindrómico, cierre palindrómico izquierdo y cierre palindrómico derecho se usaron y definieron por primera vez en este documento .

Optimizador
fuente
1
Me gustaría ver una solución palindrómica ...
ojdo
2
@ojdo Pensé en agregar eso como un extra, pero estoy bastante seguro de que la mayoría de las respuestas habrían utilizado comentarios para crear el palíndromo. Si alguna respuesta realmente puede ser un palíndromo también, sin depender de los comentarios, ¡dejaría una recompensa por esa respuesta!
Optimizador

Respuestas:

11

Pyth, 22 19

hfq_TTsm,+z_d+_dzyz

Pruébalo en línea .

Explicación

El cierre palindrómico bidireccional es de la forma AXo XA, donde Xes la cadena de entrada y Aes una subcadena de X. De hecho, tengo que ser una subcadena contigua de X, un prefijo para una forma, un sufijo para la otra forma. Pero no me importan estos defectos. Una subcadena (contigua o no) es todo lo que necesito en Pyth.

                        Implicit: z = raw_input() // Read a string
                 yz     A list with all substrings (contiguous or not) of z
       m                For each of these substrings d, build
        ,                  a pair of two strings:
         +z_d              ( z + inveres(d) ,
             +_dz            inverse(d) + z )
      s                 Sum (put all created pairs into a list)
 fq_TT                  filter elements T, where inverse(T) == T (Palindrom)
h                          Take the first element

Editar

La versión anterior ordenó las cadenas después de filtrar por longitud .olN.... Acabo de darme cuenta, que ydevuelve las subcadenas ordenadas por longitud. Entonces estos palíndromos ya están ordenados.

Jakube
fuente
6

Clip , 40

(sl`f[a=ava}+m[i+v+ixx}Rlxm[i+xvu0ix}Rlx

Ejemplo

Documents>java -jar Clip4.jar palindrome.clip
abcb
abcba

Explicación

(sl`                                        .- The shortest                     -.
    f[a=ava}                                .- palindrome                       -.
            +                               .- among the following two sets:    -.
             m[i      }Rlx                  .- For each number up to length(x)  -.
                +                           .- combine                          -.
                 v+ix                       .- the last i chars of x, reversed  -.
                     x                      .- and x.                           -.
                          m[i       }Rlx    .- For each number up to length(x)  -.
                             +              .- combine                          -.
                              x             .- x and                            -.
                               vu0ix        .- the first i chars of x, reversed.-.
Ypnypn
fuente
6

CJam, 30 bytes

Realmente esperaba ver una respuesta de CJam por ahora ... Así que aquí va: P

q:Q,{)QW%/(Q+Q@+s}%{,}${_W%=}=

Realmente odio ese {,}$bloqueo allí, pero obtengo una lista desordenada de posibles palíndromos debido al algoritmo de generación que estoy usando.

Explicación del código

q:Q,{            }%             "Read the input string, store in Q, take length and";
                                "run the code block that many times";
     )QW%                       "Increment the iteration index and Put reversed Q on stack";
         /                      "Split reversed Q into parts of incremented iteration index";
          (Q+                   "Take out the first part and prepend it to Q";
             Q@+s               "Take the rest of the parts and append them to Q";
                   {,}$         "At this point, we have all possible prepended and appended";
                                "sequences of the input string. Sort them by length";
                       {_W%=}=  "Take the first sequence which is a palindrome";

Pruébalo en línea aquí

Optimizador
fuente
66
¡Realmente odio ese {,}$bloque allí también! Es broma, no tengo idea de lo que hace CJam.
Alex A.
4

Python 2, 115 113 109 105 96 bytes

f=lambda x:[x for x in sum([[x[:~i:-1]+x,x+x[i::-1]]for i in range(len(x))],[])if x==x[::-1]][0]

Con suerte puede jugar golf más abajo. Bits posiblemente dignos de mención:

  • usando la suma de dos comprensiones de listas en una
  • construir términos en orden ordenado para evitar la necesidad de min (sugerido por @Jakube)
Uri Granta
fuente
1
Los elementos no están completamente ordenados, por lo que esto falla para cadenas como a.
Sp3000
4

Mathematica, 96 bytes

Debe haber una forma más elegante que esta ...

""<>#&@@SortBy[r=Reverse;#/.{b___,a__/;r@{a}=={a}}:>{b,r@{b,a}}&/@{r@#,#}&@Characters@#,Length]&

Esto define una función sin nombre que toma una cadena y devuelve el resultado.

La idea básica es

  • Divide la cuerda en Characters.
  • Forme una matriz con esta lista y su reverso.
  • Use la coincidencia de patrones para encontrar el palindrómico correcto de cada uno de ellos:

    {b___,a__/;r@{a}=={a}}:>{b,r@{b,a}}
    

    Tenga en cuenta que esto en realidad no devuelve una lista plana. Por ejemplo, para {a,b,c}obtener

    {a,b,{c,b,a}}
    
  • Ordenar los dos resultados por longitud.

  • Elige el más corto y vuelve a unirlo en una cuerda con ""<>#&@@.
Martin Ender
fuente
Sale abacabacuando la entrada es abac. La respuesta correcta es cabac. Creo que deberías aplanarlos antes de ordenarlos por longitud.
alephalpha
1
@alephalpha Encontré una solución mejor que no requería cambiar el tamaño del código (y que en realidad era mi intención detrás de no ordenarlo).
Martin Ender
2

Brachylog (2), 6 bytes, desafío de fechas posteriores al idioma

~{↔?a}

Pruébalo en línea!

Como es habitual en Brachylog, esta es una función, no un programa completo.

Explicación

~{↔?a}
~{   }   Find a value that produces {the input} upon doing the following:
  ↔        reversing it;
   ?       asserting that we still have the same value;
    a      and taking either a prefix, or a suffix.

Hasta donde yo sé (no es mi idioma, pero parece poco probable), ano se agregó a Brachylog para este desafío, pero es realmente útil aquí. Usamos el método "revertir y afirmar que no ha cambiado" para afirmar que el valor que encontramos es un palíndromo.

En cuanto a por qué esto produce el palíndromo más corto , el orden de evaluación de Prolog (y, por lo tanto, de Brachylog) está muy influenciado por lo primero que evalúa. En este caso, se trata de un comando "inverso" y (como la mayoría de las operaciones de lista) establece un orden de evaluación que tiene como objetivo minimizar el tamaño de la lista resultante. Como es lo mismo que el tamaño de la salida, el programa felizmente termina minimizando exactamente lo correcto por casualidad, lo que significa que no necesité agregar ninguna pista explícita.


fuente
a- No se agregó Adfix para este desafío. No tenía ningún símbolo disponible con buenos mnemónicos para el prefijo y el sufijo, por lo tanto, fusioné ambos en un adfix que puede tomar subíndices para seleccionar prefijos o sufijos solo si es necesario.
Fatalize
1

Rubí, 76 + 2 = 78

Con indicadores de línea de comandos -pl( lpuede que no sean necesarios dependiendo de cómo esté haciendo la entrada), ejecute

$_=[[$_,r=$_.reverse]*"\0",r+"\0#$_"].min_by{|s|s.sub!(/(.*)\0\1/){$1}.size}

Dada una cadena 'abaa', genera las cadenas 'cbca 0 acbc' y 'acbc 0 cbca', donde 0 es el carácter no imprimible con el código ascii 0. Luego elimina una copia del marco de cadena repetido más largo 0 que encuentra en cada uno, 'a' en el primero y 'cbc' en el segundo, para obtener los dos cierres. Luego genera el resultado más corto.

Lo único realmente extraño del código de golf es que acorta las cadenas en su lugar mientras las ordena, lo que podemos evitar porque min_bysolo ejecuta el bloque una vez por elemento que se compara (tanto porque es una transformación de Schwartzian como porque solo hay dos elementos para comparar).

histocrat
fuente
1

Python 3, 107 bytes


f=lambda a:[i for i in[a[:i:-1]*j+a+a[-1-i::-1]*(1-j)for i in range(len(a))for j in(0,1)]if i==i[::-1]][-1]

Probar:

>>> print("\n".join(map(f, ["abcdef", "abcba", "abcb", "cbca"])))
abcdefedcba
abcba
abcba
acbca
matsjoyce
fuente
1

Haskell, 107 bytes

import Data.List
r=reverse
f s=snd$minimum[(length x,x)|x<-map(s++)(tails$r s)++map(++s)(inits$r s),x==r x]

Prueba:

*Main> mapM_ (putStrLn.f) ["abcdef", "abcba", "abcb", "cbca"]
abcdefedcba
abcba
abcba
acbca
nimi
fuente
1

J, 66 62 bytes

3 :'>({~[:(i.>./)(#%~[-:|.)@>),(<@([,|.@{.~)"#:i.@#"1)y,:|.y'

Bastante sencillo. Los dos trucos que uso:

El cierre palindrómico derecho es el cierre palindrómico izquierdo de la cuerda invertida.

Encontrar la longitud de la cadena con longitud mínima y palindromidad con la expresión min (is_palindrome / length).

   f=.3 :'>({~[:(i.>./)(#%~[-:|.)@>),(<@([,|.@{.~)"#:i.@#"1)y,:|.y'

   f 'lama'
lamal

Pruébelo en línea aquí.

randomra
fuente