Smallest Hamming distance to a palindrome containing a substring

Question

_{This was inspired by a now removed CS.SE question.}

Task

Given two non-empty input strings A and B, output the smallest distance from A to a palindrome that contains B as a substring. Distance is defined by the number of character replacements (Hamming distance).

Restrictions

• Sensible input: a palindrome exists. This means |A| ≥ |B|.
• A and B contain only lower ASCII characters, lowercase and uppercase are distinct (as are all other characters).
• If your language cannot deal with ASCII characters, you may use integers (or some other reasonable data type) as well, and you may choose to limit the range to 128 elements.
• You may take input from stdin, function arguments, command line arguments, etc.
• You may give the result on stdout, return value, etc.
• You do not need to give a working palindrome, the smallest distance to one is sufficient.

Examples

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

Scoring

This is code golf, shortest code in bytes wins.

Answer 1

Pyth, 19 bytes

hSmsnVQd/#z_I#^+Qzl

Demonstration

Extreme brute force approach. Generate all strings of the appropriate length with characters in either string, filter for palindromes and for containing the second input, map to hamming distance from first string, output smallest.

Explanation:

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

Answer 2

Pyth, 45 bytes

hSmsnVQdf}zTsmm+hc2KsXcd+Bklz1z_hc2PKh-lQlz_B

Try it online. Test suite.

I'm still not exactly satisfied with how this turned out. But at least it's quite hard to understand without an explanation now. (Success, I guess?)

Explanation

• Take in A as Q and B as z.
• m…_BQ Compute the following for both A and its reverse as d:
  • m…h-ldlz Compute the following for all k from 0 to len(A) - len(B) inclusive:
    • +Bklz Get the pair k, k + len(B).
    • cd Split d at those indices.
    • X…1z Replace the second (middle) part with B.
    • Ks Concatenate the pieces and save to K. B is now inserted at position k in A or its reverse.
    • hc2 Split the resulting string in two and keep the first piece. This gives half of the string with the possible middle character.
    • hc2PK Remove the last character and do the same split, keeping the first piece. This gives half of the string without the possible middle character.
    • +…_ Add the reverse of the shorter piece to the longer piece. We now have a palindrome.
• s Concatenate the results for A and its reverse.
• f}zT Remove all strings that don't contain B.
• m Compute the following for all the resulting strings d:
  • nVQd Get the pairwise inequality with A. This gives True for pairs that need to be changed.
  • s Sum the list. This gives the Hamming distance.
• hS Take the minimum result.

Answer 3

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

Brute force approach: generate each possible overlap of A and B, make each into a palindrome, calculate Hamming distances from A, and take the smallest of the resulting distances.

Probably could be golfed a bit more...

Test snippet

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>