# Find the closest swap

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

# 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!

• m*n?…:m+n -> m+n>0&&… save 1 byte.
– tsh
Jul 29 at 2:00
• @tsh Would it really work? It would compute an invalid Levenshtein distance in some cases (e.g. this one). Jul 29 at 7:30

# 05AB1E, 17 bytes

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


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

ā<.Æεè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


# 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.


# 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.

# 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.