Find the closest swap

Question

Take as input two strings \$A\$ and \$B\$. Output a string \$C\$ that is \$A\$ but with two characters swapped such that the Levenshtein distance \$d(C,B)\$ is as small as possible. You must swap two characters and you cannot swap a character with itself, although you may swap two identical characters in different positions.

This is code-golf the goal is to minimize the size of your source code as measured in bytes.

Instead of strings you may instead choose to handle lists of positive integers.

Examples

Here are some examples of inputs and possible outputs along with the Levenshtein distance achieved.

A	B	C	Distance
abcd	adcb	adcb	0
ybgh	epmn	ygbh	4
slime	slime	silme	2
yeboc	yoqqa	yobec	3
unnua	muuna	uunna	2
oobis	oobi	oobis	1
yuace	yuac	yuaec	1

Answer 1

JavaScript (ES6), 163 bytes

Expects (a)(b), where a and b are arrays of characters. Returns another array of characters.

This really just tries all possibilities and computes the Levenshtein distance for each of them. It seems very likely that there's a smarter/shorter way.

a=>M=b=>a.map((x,i)=>a.map((y,j,[...s])=>j<=i|(s[i]=y,s[j]=x,n=b.length,g=m=>v=m*n?1+Math.min(g(m,--n),g(--m)-(s[m]==b[n++]),g(m)):m+n)(s.length)>M||(M=v,o=s)))&&o

Try it online!

Answer 2

05AB1E, 17 bytes

\ā<.ÆεèyRǝ}Σ¹.L}н

Inputs in the order \$B,A\$.

Try it online or verify all test cases.

ā<.Æεèy could alternatively be .ā.Æεø` for the same byte-count:
Try it online or verify all test cases.

Explanation:

\           # Discard the first (implicit) input `B`
 ā          # Push a list in the range [1, length of second (implicit) input `A`]
  <         # Decrease it to range [0, length_A)
   .Æ       # Get all pairs without duplicates
     ε      # Map over each pair:
      è     #  Index them into the second (implicit) input `A`
       yR   #  Push the pair reversed
         ǝ  #  Insert them into the second (implicit) input `A`
     }Σ     # After the map: sort the strings by:
        .L  #  The Levenshtein distance with
       ¹    #  the first input `B`
      }н    # After the sort: pop and leave the first string
            # (which is output implicitly as result)

 .ā         # Enumerate the second (implicit) input,
            # pairing each character with its index
   .Æ       # Get all pairs without duplicates
     ε      # Map over each pair:
      ø     #  Zip/transpose; swapping rows/columns
       `    #  Pop and push the pair of characters and pair of indices separated to
            #  the stack
        R   #  Reverse the indices-pair

Answer 3

Vyxal, 15 bytes

ė2ḋƛ∩÷Ṙ¹∇Ȧ;‡⁰꘍∵

Try it Online!

ė2ḋƛ∩÷ could be ẏ2ḋƛ¹İ for the same byte count.

ė2ḋƛ∩÷Ṙ¹∇Ȧ;‡⁰꘍∵
ė                # Enumerate, make a list [index, x] for each x in the first input.
 2ḋ              # Combinations without replacement of length 2; pairs.
   ƛ             # For each:
    ∩            #  Transpose
     ÷           #  Dump; push both items onto the stack.
      Ṙ          #  Reverse the top pair (the pair of two characters). Call this Y, and the other pair X.
       ¹         #  Push the first input
        ∇        #  Push it under the top two values of the stack, aka c,a,b.
         Ȧ       #  Assign; replace each of the indices in X with the corresponding value in Y.
          ;      # Close map.
           ‡  ∵  # Minimum by:
            ⁰꘍   #  Levenshtein distance with the second input.

Answer 4

R, 130 97 bytes

\(A,B,x=combn(seq(a<-utf8ToInt(A)),2,\(i)intToUtf8(`[<-`(a,i,a[rev(i)]))))x[order(adist(x,B))[1]]

Attempt This Online!

Another brute-force solution.

Answer 5

Python, 216 bytes

lambda a,b:(n:=len(a))and min(w(c:=[*a],k%n,k//n)or d(c,[*b])for k in range(n*n)if k%n<k//n)
d=lambda s,t:-~min(d(S:=s[1:],T:=t[1:])-(s[0]==t[0]),d(S,t),d(s,T))if s>""<t else len(s+t)
def w(a,i,j):a[i],a[j]=a[j],a[i]

Attempt This Online!

A very bloated answer which just iterates through all pairs of swaps. The Levenshtein distance is adapted from an answer to this question, but slightly shortened.