# Swapless distances

Suppose you have a string $$\s_0\$$ and someone else has a hidden string $$\s_1\$$. You don't know what $$\s_1\$$ is but they tell you that they can get from your string, $$\s_0\$$, to their string by making a certain number of moves $$\d\$$. Each move can be one of the following:

• Insertion : Add a character anywhere in the string

• Deletion : Remove a character from anywhere in the string

• Replacement : Replace one character with another anywhere in the string

• Transposition : swap any two adjacent characters.

(this is Damerau-Levenshtein distance).

The question is how many moves do you need to get from $$\s_0\$$ to $$\s_1\$$ without using the transposition move (this is Levenshtein distance)?

Your task is to write a program or function that takes a string (list of positive integers is fine too) representing $$\s_0\$$ and a positive integer representing $$\d\$$ and output the minimal number of moves required to guarantee you can get to $$\s_1\$$ without transposition in the worst-case scenario.

This is your answer will be scored in bytes with fewer bytes being better.

# Test cases

## Using Strings

"Hello", 3 -> 4
"World", 2 -> 4
"aaaaa", 1 -> 1
"aaaaa", 2 -> 2
"abaaa", 3 -> 4
"Krypyp", 3 -> 5
"", 5 -> 5
"Hello", 0 -> 0


## Using Integer lists

[1,2,3,3,4], 3 -> 5
[1,2,3,4,5], 2 -> 4
[1,1,1,1,1], 1 -> 1
[1,1,1,1,1], 2 -> 2
[1,2,1,1,1], 3 -> 4
[1,2,3,4,3,4], 3 -> 4
[], 5 -> 5
[1,2,3,3,4], 0 -> 0

• It took a while to puzzle out, but I think this is asking for the largest Levenshtein distance among all strings with a given Damerau-Levenshtein distance from a given string. Feb 27, 2019 at 19:49
• @Nitrodon Yep that's another way to say it. Feb 27, 2019 at 19:51
• The Levenshtein distance from Hello to Hleol is 3, so the example test case would need to be something based on eHlol instead. As for the length 6 test case, a distance of 5 is possible (e.g., rrKyypp) Feb 28, 2019 at 5:36
• Actually, Hello and eaHlol have Levenshtein distance 4: HelloHeHloeHloeHloleaHlol
– japh
Feb 28, 2019 at 23:15
• I couldn't find any string that shows "Hello", 3 -> 5. Are you sure it's 5? Otherwise my solution is wrong.
– japh
Mar 1, 2019 at 0:28

-- f :: [Int] -> Int -> Int
f s k|let a=pure<$>0:s;d#(x:z)|let w(y:z)|d>0=[y:x:z];w _=[]=[c++y++z|c<-[]:a,y<-[]:[[x]]]++w z++map(x:)(d#z);_#_=a;d%i=iterate((++)<*>((d#)=<<))[s]!!i=[i|i<-[k..],all(elem0%i)$1%k]!!0


Simple brute force solution. f takes a list of positive integers, and the DL-distance k.

This generates all strings up to the DL-distance limit k, and searches for the smallest L-distance that contains all of those strings (also by generating those strings). This saves bytes by using the same generator code for both types of distances.

Try it online! Note that this is too slow for some of the test cases, so the TIO version uses reduced test cases.

### Pregolfed

Ungolfed version. Unlike the golfed version, this one removes duplicate strings during the generation, so it's also much faster:

import qualified Data.Set as S
import Data.List (sortBy)
import Data.Ord (comparing)

snub x = S.toList $S.fromList x f' s k = let -- 0 = any other symbol not in s alphabet = snub$ toEnum 0 : s
-- all strings with L-distance 1 (if d, DL-distance)
gen1 d s@(x:xs) = snub $del ++ ins ++ sub ++ swap xs ++ map (x:) (gen1 d xs) where del = [xs] ins = map (:s) alphabet sub = map (:xs) alphabet swap (y:ys) | d = [y:x:ys] swap _ = [] gen1 _ _ = map (:[]) alphabet -- as gen1, but distance <= i genAll d i = iterate (\x->snub$ x ++ (gen1 d =<< x)) [s] !! i
-- strings with DL-distance <= k
sDL = S.fromAscList $genAll True k in head [ (i, worstStrings) | -- sL = genAll False i -- zip obtains sL' = genAll False (i-1) for calculating worstStrings ((_, sL'), (i, sL)) <- zip <*> tail$ (,) <*> (S.fromAscList . genAll False) <$> [max 0(k-1)..], -- require that sL covers sDL sDL S.isSubsetOf sL, -- also show some maximal examples let interestingness t = length (filter (==toEnum 0) t) + abs (length t - length s) worstStrings = take 5$ sortBy (comparing interestingness) \$
S.toList (sL S.intersection sDL S.difference sL')
]


Try it online! This uses the full testcases but Krypyp still times out on TIO (it takes a few minutes to solve). Also, it prints some of the strings that have maximal Levenshtein distance. Testcase solutions:

"hello", 3 -> 4 e.g. "eeeol","eehol","eeool","ehheo","ehhho"
"world", 2 -> 4 e.g. "owrdl"
"aaaaa", 1 -> 1 e.g. "_aaaa","a_aaa","aa_aa","aaa_a","aaaa"
"aaaaa", 2 -> 2 e.g. "__aaa","_a_aa","_aa_a","_aaa","_aaa_"
"abaaa", 3 -> 4 e.g. "aabbb","aab_b","aabb_","_aabab","_aabba"
"Krypyp", 3 -> 5 e.g. "rKyKppy","rKyppKy","rKyppry","rpKyppy","r_Kyppy"
"", 5 -> 5 e.g. "_____"


# Java 11, 790764 760 bytes

import java.util.*;t->n->{var S=new HashSet<String>();int m=n;for(;m>0;)p(S,"",t+"x".repeat(m--));for(var s:(HashSet<String>)S.clone())for(m=s.length()-n;m-->1;)S.add(s.substring(m));S.removeIf(s->d(1,s,t)!=n);for(var s:S)m=Math.max(d(0,s,t),m);return m;}void p(Set S,String p,String s){int l=s.length(),i=0;if(l<1)S.add(p);for(;i<l;)p(S,p+s.charAt(i),s.substring(0,i)+s.substring(++i));}int d(int f,String s,String t){int l=s.length()+1,L=t.length()+1,d[][]=new int[l][L],i=l,j,c,q,A,B;for(;i-->0;)d[i][0]=i;for(j=0;++j<L;)for(d[i=0][j]=j;++i<l;B=t.charAt(j-1),c=A==B?0:1,d[i][j]=q=Math.min(Math.min(d[i-1][j]+1,d[i][j-1]+1),d[i-1][j-1]+c),d[i][j]=f>0&i>1&j>1&&A==t.charAt(j-2)&s.charAt(i-2)==B?Math.min(q,d[i-2][j-2]+c):q)A=s.charAt(i-1);return d[l-1][L-1];}


Will golf it down (substantially I hope) from here.

Try it online.

### Explanation:

General approach:

Input-String = t and input-integer = n in the explanation below.

1. Generate all permutations of t with up to n added characters, and add them to a Set
2. For each permutation, add a substring with up to n removed characters to the Set as well
3. Remove any String from this Set that does not have a Damerau-Levenshtein distance of n in comparison to t
4. Calculate the Levenshtein distance of each remaining String in comparison to t
5. Take the maximum, which is our result

Code explanation:

import java.util.*;               // Required import for the Set and HashSet

t->n->{                           // Method with String and integer parameters and integer return-type
var S=new HashSet<String>();    //  Create a String-Set
int m=n;for(;m>1;)              //  Loop m in the range [input-integer, 0):
p(S,"",t                      //   Determine all permutations of the input-String
+"x".repeat(m--));          //   With up to m additional "x" added
for(var s:(HashSet<String>)S.clone())
//  Loop over all generated permutations:
for(m=s.length()-n;m-->1;)    //   Inner loop m in the range [permutation-length - input-integer, 1]:
S.add(s.substring(m));      //    Add the permutation with the first m characters removed to the Set as well
//  (NOTE: After these loops, m is 0 which we'll re-use later on)
S.removeIf(s->                  //  Now remove any permutation from this Set which:
d(1,s,t)!=n);                //   Does not have a DL-distance equal to the input-integer
for(var s:S)                    //  Loop over all remaining Strings:
m=Math.max(d(0,s,t),m);       //   Determine the maximum L-distance
return m;}                      //  And return that maximum L-distance as result

// Separated recursive method to get all permutations from a String
void p(Set S,String p,String s){  // Method with Set and two String parameters and no return-type
int l=s.length(),                 //  Get the length of the input-String s
i=0;                          //  Index-integer i, starting at 0
if(l<1)                           //  If the length is 0:
S.add(p);                       //   Add the prefix-String p to the Set
for(;i<l;)                        //  Loop i in the range [0, length):
p(S,p+s.charAt(i),              //   Append the i'th character to the prefix-String p
s.substring(0,i)+s.substring(++i));}
//   Remove the i'th character from the String s
//   And do a recursive call

// Separated method to determine the DL or L distance of two Strings
int d(int f,String s,String t){   // Method with integer and two String parameters and String return-type
int l=s.length()+1,             //  Length l of the source-String + 1
L=t.length()+1,             //  Length L of the target-String + 1
d[][]=new int[l][L],        //  Create an integer matrix of those dimensions
i=l,j,                      //  Index-integers
c,q,A,B;                    //  Temp integers
for(;i-->0;)                    //  Loop i in the range (l, 0]:
d[i][0]=i;                    //   Set the i,0'th cell to i in the matrix
for(j=0;++j<L;)                 //  Loop j in the range [0, L):
for(d[i=0][j]=j;              //   Set the 0,j'th cell to j in the matrix
++i<l                     //   Inner loop i in the range [0, l):
;                         //     After every iteration:
B=t.charAt(j-1),         //      Set B to the j-1'th character of the target-String
c=A==B?                  //      If the characters A and B are the same:
0                     //       Set c to 0
:                      //      Else:
1,                    //       Set c to 1
d[i][j]=                 //      Set the i,j'th value to:
q=Math.min(            //       The minimum of:
Math.min(           //        The minimum of:
d[i-1][j]+1,      //         The i-1,j'th value + 1
d[i][j-1]+1),     //         And the i,j-1'th value + 1
d[i-1][j-1]+c),     //        And the i-1,j-1'th value + c
d[i][j]=                 //      Then, set the i,j'th value to:
f>0              //       If the given DL-flag is 1
&i>1&j>1         //       And both i and j are at least 2
&&A              //       And the character A
==t.charAt(j-2)//       equals the j-2'th character in the target-String
&s.charAt(i-2)   //       And the i-2'th character in the source-String
==B?            //       equals the character B:
Math.min(       //        Set the i,j'th value to the minimum of:
q,             //         The i,j'th value
d[i-2][j-2]+c) //         And the i-2,j-2'th value + c
:                //       Else (the given DL-flag is 0):
q)              //        Leave the i,j'th value the same
A=s.charAt(i-1);            //    Set A to the i-1'th character of the source-String
return d[l-1][L-l];}            //  Return the l-1,L-1'th value as result