_{Isso foi inspirado por uma pergunta CS.SE agora removida .}

Tarefa

Dadas duas seqüências de entrada não vazias A e B, produza a menor distância de A até um palíndromo que contém B como uma substring. A distância é definida pelo número de substituições de caracteres ( distância de Hamming ).

Restrições

• Entrada sensível: existe um palíndromo. Isso significa | A | ≥ | B |.
• A e B contêm apenas caracteres ASCII inferiores, minúsculas e maiúsculas são distintas (como todos os outros caracteres).
• Se seu idioma não puder lidar com caracteres ASCII, você também poderá usar números inteiros (ou algum outro tipo de dados razoável) e poderá optar por limitar o intervalo a 128 elementos.
• Você pode obter informações de stdin, argumentos de função, argumentos de linha de comando etc.
• Você pode fornecer o resultado em stdout, valor de retorno etc.
• Você não precisa dar um palíndromo em funcionamento, a menor distância a um é suficiente.

Exemplos

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

Pontuação

Este é o código golf, o código mais curto em bytes vence.

Pitão, 19 bytes

hSmsnVQd/#z_I#^+Qzl

Demonstração

Abordagem de força bruta extrema. Gere todas as seqüências de caracteres do comprimento apropriado com caracteres em qualquer uma das seqüências, filtre os palíndromos e contenha a segunda entrada, mapeie a distância da primeira sequência e a menor saída.

Explicação:

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

Pitão, 45 bytes

hSmsnVQdf}zTsmm+hc2KsXcd+Bklz1z_hc2PKh-lQlz_B

Experimente online. Suíte de teste.

Ainda não estou exatamente satisfeito com o resultado. Mas pelo menos é muito difícil de entender sem uma explicação agora. (Sucesso, eu acho?)

Explicação

• Pegue A como Qe B como z.
• m… _BQCalcule o seguinte para A e seu reverso como d:
  • m… h-ldlzCalcule o seguinte para todos kde 0 a len(A) - len(B)inclusivo:
    • +BklzPegue o par k, k + len(B).
    • cdDividir dnesses índices.
    • X… 1zSubstitua a segunda parte (do meio) por B.
    • KsConcatene as peças e salve em K. B agora está inserido na posição kA ou em seu reverso.
    • hc2Divida a sequência resultante em duas e mantenha a primeira peça. Isso fornece metade da string com o possível caractere do meio.
    • hc2PKRemova o último caractere e faça a mesma divisão, mantendo a primeira peça. Isso fornece metade da string sem o possível caractere do meio.
    • +… _Adicione o verso da peça mais curta à peça mais longa. Agora temos um palíndromo.
• s Concatene os resultados para A e seu reverso.
• f}zT Remova todas as seqüências que não contêm B.
• mCalcule o seguinte para todas as cadeias resultantes d:
  • nVQd Obtenha a desigualdade aos pares com A. Isso fornece True para pares que precisam ser alterados.
  • sSoma a lista. Isso dá a distância de Hamming.
• hS Tome o resultado mínimo.

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

Abordagem de força bruta: gere cada possível sobreposição de A e B, transforme cada uma em um palíndromo, calcule as distâncias de Hamming de A e faça a menor das distâncias resultantes.

Provavelmente poderia ser jogado um pouco mais ...

Snippet de teste

f=(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))
g=(A,B)=>console.log("A:",A," B:",B," f(A,B):",f(A,B))

g("thilloaoyreot", "hello")
g("benjonson", "stack")
g("neversaynever!", "odd")
g("ppcggcpp", "gg")

<input id=A value="amanaplanacanalrussia">
<input id=B value="panama">
<button onclick="g(A.value,B.value)">Run</button>