Swapless distances

Question

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

Answer 1

Haskell, 186 bytes

-- 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(`elem`0%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. "_____"

Answer 2

Java 11, 790 764 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