9
\$\begingroup\$

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
\$\endgroup\$

5 Answers 5

3
\$\begingroup\$

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!

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

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
\$\endgroup\$
2
\$\begingroup\$

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.
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.