La distancia de Hamming más pequeña a un palíndromo que contiene una subcadena

17

Esto se inspiró en una pregunta CS.SE ahora eliminada .

Tarea

Dadas dos cadenas de entrada no vacías A y B, genera la distancia más pequeña de A a un palíndromo que contiene B como una subcadena. La distancia se define por el número de reemplazos de caracteres ( distancia de Hamming ).

Restricciones

  • Entrada sensible: existe un palíndromo. Esto significa | A | ≥ | B |.
  • A y B contienen solo caracteres ASCII inferiores, las minúsculas y mayúsculas son distintas (al igual que todos los demás caracteres).
  • Si su idioma no puede tratar con caracteres ASCII, también puede usar números enteros (o algún otro tipo de datos razonable), y puede elegir limitar el rango a 128 elementos.
  • Puede recibir información de stdin, argumentos de función, argumentos de línea de comando, etc.
  • Puede dar el resultado en stdout, valor de retorno, etc.
  • No necesita dar un palíndromo que funcione, la distancia más pequeña a uno es suficiente.

Ejemplos

A                   B            Output
thilloaoyreot       hello        4 (thelloaolleht)
benjonson           stack        9 (stackcats)
neversaynever!      odd          9 (neveroddoreven)
ppcggcpp            gg           0 (ppcggcpp)
stars               tat          1 (stats)

Puntuación

Este es el código de golf, el código más corto en bytes gana.

code-golf string palindrome Comunidad
fuente

Respuestas:

5

Pyth, 19 bytes

hSmsnVQd/#z_I#^+Qzl

Demostración

Enfoque de fuerza bruta extrema. Genere todas las cadenas de la longitud adecuada con caracteres en cualquiera de las cadenas, filtre para palíndromos y para contener la segunda entrada, asigne a la distancia de Hamming desde la primera cadena, la salida más pequeña.

Explicación:

hSmsnVQd/#z_I#^+Qzl
hSmsnVQd/#z_I#^+QzlQ     Variable introduction
                         Q = string A, z = string B.
               +Qz       Concatenate A and B
              ^   lQ     Form every string of length equal to len(A)using
                         characters from the concatenation.
             #           Filter on
           _I            Invariance under reversal (palindrome)
         #               Filter on
        / z              Nonzero occurences of B
  m                      Map to
    nV                   !=, vectorized over
      Qd                 A and the map input
   s                     Sum (gives the hamming weight)
hS                       Min
isaacg
fuente
Algo como esto es lo que pensé, pero decidí que O ((m + n) ^ n) era demasiado O (malo). : D
PurkkaKoodari
3

Pyth, 45 bytes

hSmsnVQdf}zTsmm+hc2KsXcd+Bklz1z_hc2PKh-lQlz_B

Pruébalo en línea. Banco de pruebas.

Todavía no estoy exactamente satisfecho con cómo resultó esto. Pero al menos es bastante difícil de entender sin una explicación ahora. (¿Éxito, supongo?)

Explicación

  • Tome A como Qy B como z.
  • m… _BQCalcule lo siguiente para A y su reverso como d:
    • m… h-ldlzCalcule lo siguiente para todos kdesde 0 hasta len(A) - len(B)inclusive:
      • +BklzConsigue el par k, k + len(B).
      • cdDividido den esos índices.
      • X... 1zReemplace la segunda parte (del medio) con B.
      • KsConcatenar las piezas y guardar en K. B ahora se inserta en la posición ken A o en su reverso.
      • hc2Divide la cuerda resultante en dos y mantén la primera pieza. Esto le da a la mitad de la cadena el posible carácter del medio.
      • hc2PKElimina el último personaje y haz la misma división, manteniendo la primera pieza. Esto le da la mitad de la cadena sin el posible carácter del medio.
      • +… _Agregue el reverso de la pieza más corta a la pieza más larga. Ahora tenemos un palíndromo.
  • s Concatenar los resultados para A y su reverso.
  • f}zT Elimine todas las cadenas que no contengan B.
  • mCalcule lo siguiente para todas las cadenas resultantes d:
    • nVQd Obtenga la desigualdad por pares con A. Esto da verdadero para los pares que necesitan ser cambiados.
    • sSuma la lista. Esto le da a Hamming la distancia.
  • hS Toma el resultado mínimo.
PurkkaKoodari
fuente
1

JavaScript (Firefox 30+), 152 146 bytes

(A,B)=>Math.min(...[...Array(A[l='length']-B[l]+1)].map((_,i)=>[for(c of q=A.slice(j=t=0,i)+B+A.slice(i+B[l]))t+=(c!=A[j])+(c!=q[q[l]-++j])/2]|t))

Enfoque de fuerza bruta: genere cada posible superposición de A y B, convierta cada uno en un palíndromo, calcule las distancias de Hamming desde A y tome la menor de las distancias resultantes.

Probablemente podría jugar al golf un poco más ...

Fragmento de prueba

Mostrar fragmento de código

ETHproducciones
fuente